From 46df7f7566778f6e653d25f063fc6a57649e36a6 Mon Sep 17 00:00:00 2001
From: dgp <dgp@users.sourceforge.net>
Date: Thu, 14 Feb 2013 21:04:25 +0000
Subject: New branch bug-3604074 with improved patch to correct fixempties()
 failure to converge.

---
 generic/regc_nfa.c | 80 ++++++++++++++++++++++++++++++++++--------------------
 tests/regexp.test  |  5 +++-
 2 files changed, 54 insertions(+), 31 deletions(-)

diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c
index 48f56a9..459968a 100644
--- a/generic/regc_nfa.c
+++ b/generic/regc_nfa.c
@@ -1139,6 +1139,7 @@ FILE *f;			/* for debug output; NULL none */
 {
 	struct state *s;
 	struct state *nexts;
+	struct state *to;
 	struct arc *a;
 	struct arc *nexta;
 	int progress;
@@ -1146,14 +1147,41 @@ FILE *f;			/* for debug output; NULL none */
 	/* find and eliminate empties until there are no more */
 	do {
 		progress = 0;
-		for (s = nfa->states; s != NULL && !NISERR()
-			&& s->no != FREESTATE; s = nexts) {
+		for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
 			nexts = s->next;
-			for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
+			for (a = s->outs; a != NULL && !NISERR();
+				a = a->outchain)
+				if (a->type == EMPTY)
+					/* Mark a for deletion; copy arcs
+					 * to preserve graph connectivity
+					 * after it is gone. */
+					unempty(nfa, a);
+
+			/* Now pass through and delete the marked arcs.
+			 * Doing all the deletion after all the marking
+			 * prevents arc copying from resurrecting deleted
+			 * arcs which can cause failure to converge.
+			 * [Tcl Bug 3604074] */
+			for (a = s->outs; a != NULL; a = nexta) {
 				nexta = a->outchain;
-				if (a->type == EMPTY && unempty(nfa, a))
+				if (a->from == NULL) {
 					progress = 1;
-				assert(nexta == NULL || s->no != FREESTATE);
+		    			to = a->to;
+					a->from = s;
+					freearc(nfa, a);
+					if (to->nins == 0) {
+						while ((a = to->outs))
+							freearc(nfa, a);
+						if (nexts == to)
+							nexts = to->next;
+						freestate(nfa, to);
+					}
+					if (s->nouts == 0) {
+						while ((a = s->ins))
+							freearc(nfa, a);
+						freestate(nfa, s);
+					}
+				}
 			}
 		}
 		if (progress && f != NULL)
@@ -1174,7 +1202,6 @@ struct arc *a;
 {
 	struct state *from = a->from;
 	struct state *to = a->to;
-	int usefrom;		/* work on from, as opposed to to? */
 
 	assert(a->type == EMPTY);
 	assert(from != nfa->pre && to != nfa->post);
@@ -1184,33 +1211,26 @@ struct arc *a;
 		return 1;
 	}
 
-	/* decide which end to work on */
-	usefrom = 1;			/* default:  attack from */
-	if (from->nouts > to->nins)
-		usefrom = 0;
-	else if (from->nouts == to->nins) {
-		/* decide on secondary issue:  move/copy fewest arcs */
-		if (from->nins > to->nouts)
-			usefrom = 0;
+	/* Mark arc for deletion */
+	a->from = NULL;
+
+	if (from->nouts > to->nins) {
+		copyouts(nfa, to, from);
+		return 1;
 	}
-		
-	freearc(nfa, a);
-	if (usefrom) {
-		if (from->nouts == 0) {
-			/* was the state's only outarc */
-			moveins(nfa, from, to);
-			freestate(nfa, from);
-		} else
-			copyins(nfa, from, to);
-	} else {
-		if (to->nins == 0) {
-			/* was the state's only inarc */
-			moveouts(nfa, to, from);
-			freestate(nfa, to);
-		} else
-			copyouts(nfa, to, from);
+	if (from->nouts < to->nins) {
+		copyins(nfa, from, to);
+		return 1;
+	}
+
+	/* from->nouts == to->nins */
+	/* decide on secondary issue:  move/copy fewest arcs */
+	if (from->nins > to->nouts) {
+		copyouts(nfa, to, from);
+		return 1;
 	}
 
+	copyins(nfa, from, to);
 	return 1;
 }
 
diff --git a/tests/regexp.test b/tests/regexp.test
index 70ee47e..a7b81b2 100644
--- a/tests/regexp.test
+++ b/tests/regexp.test
@@ -630,7 +630,10 @@ test regexp-21.13 {multiple matches handle newlines} {
 test regexp-22.1 {Bug 1810038} {
     regexp ($|^X)* {}
 } 1
-
+test regexp-22.2 {Bug 3604074} {
+    # This will hang in interps where the bug is not fixed
+    regexp ((((((((a)*)*)*)*)*)*)*)* a
+} 1
 
 # cleanup
 ::tcltest::cleanupTests
-- 
cgit v0.12


From 6265c896a313dac8630f75042b2ab9df77013882 Mon Sep 17 00:00:00 2001
From: dgp <dgp@users.sourceforge.net>
Date: Fri, 15 Feb 2013 15:15:48 +0000
Subject: revise test numbering for forward merging

---
 tests/regexp.test | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/tests/regexp.test b/tests/regexp.test
index a7b81b2..2b4eb36 100644
--- a/tests/regexp.test
+++ b/tests/regexp.test
@@ -630,7 +630,10 @@ test regexp-21.13 {multiple matches handle newlines} {
 test regexp-22.1 {Bug 1810038} {
     regexp ($|^X)* {}
 } 1
-test regexp-22.2 {Bug 3604074} {
+test regexp-22.2 {regexp compile and backrefs, Bug 1857126} {
+    regexp -- {([bc])\1} bb
+} 1
+test regexp-22.3 {Bug 3604074} {
     # This will hang in interps where the bug is not fixed
     regexp ((((((((a)*)*)*)*)*)*)*)* a
 } 1
-- 
cgit v0.12