From 25d0a5d71accc14622ace3a24ca06a5b6c12f843 Mon Sep 17 00:00:00 2001
From: Ulya Trofimovich <skvadrik@gmail.com>
Date: Sat, 8 Apr 2017 19:37:32 +0100
Subject: [PATCH] Merged a couple of slightly different 'topsort' versions into
 one.

---
 re2c/src/dfa/cfg/normalize.cc | 24 ++++++++-----
 re2c/src/dfa/find_state.cc    |  2 +-
 re2c/src/dfa/tcmd.cc          | 64 +----------------------------------
 re2c/src/dfa/tcmd.h           |  1 -
 4 files changed, 18 insertions(+), 73 deletions(-)

diff --git a/re2c/src/dfa/cfg/normalize.cc b/re2c/src/dfa/cfg/normalize.cc
index 4a7104d2..215ff80c 100644
--- a/re2c/src/dfa/cfg/normalize.cc
+++ b/re2c/src/dfa/cfg/normalize.cc
@@ -27,20 +27,28 @@ void cfg_t::normalization(cfg_t &cfg)
 	cfg_bb_t *b = cfg.bblocks, *e = b + cfg.nbbfall;
 	for (; b < e; ++b) {
 
-		for (tcmd_t *x = b->cmd, *y; x;) {
+		// We cannot normalize the list of commands as a whole: the
+		// relative order of some commands might be significant.
+		// Therefore we split the list in continuous sublists of
+		// 'copy', 'save without history' and 'save with history'
+		// commands and normalize each sublist in a proper way.
+		tcmd_t **px, **py, *x;
+		for (px = &b->cmd; (x = *px);) {
 			if (tcmd_t::iscopy(x->rhs)) {
-				for (y = x; x && tcmd_t::iscopy(x->rhs); x = x->next);
-				normalize(y, x);
+				for (py = px; (x = *px) && tcmd_t::iscopy(x->rhs); px = &x->next);
+				*px = NULL;
+				normalize(*py, NULL);
+				tcmd_t::topsort(py, indeg);
+				for (px = py; *px; px = &(*px)->next);
+				*px = x;
 			} else if (tcmd_t::isset(x)) {
-				for (y = x; x && tcmd_t::isset(x); x = x->next);
-				normalize(y, x);
+				for (py = px; (x = *px) && tcmd_t::isset(x); px = &x->next);
+				normalize(*py, x);
 			} else {
-				for (y = x; x && tcmd_t::isadd(x); x = x->next);
+				for (py = px; (x = *px) && tcmd_t::isadd(x); px = &x->next);
 				// don't normalize, histories may have complex dependencies
 			}
 		}
-
-		tcmd_t::topsort(&b->cmd, indeg);
 	}
 
 	delete[] indeg;
diff --git a/re2c/src/dfa/find_state.cc b/re2c/src/dfa/find_state.cc
index 9a36b217..95a85423 100644
--- a/re2c/src/dfa/find_state.cc
+++ b/re2c/src/dfa/find_state.cc
@@ -292,7 +292,7 @@ tcmd_t *kernels_t::actions(tcmd_t *acts)
 	*pa = acts;
 
 	// see note [topological ordering of copy commands]
-	tcmd_t::topsort1(&copy, indeg);
+	tcmd_t::topsort(&copy, indeg);
 
 	return copy;
 }
diff --git a/re2c/src/dfa/tcmd.cc b/re2c/src/dfa/tcmd.cc
index 2ea2f4d8..ec4d29ee 100644
--- a/re2c/src/dfa/tcmd.cc
+++ b/re2c/src/dfa/tcmd.cc
@@ -72,75 +72,13 @@ bool tcmd_t::isadd(const tcmd_t *cmd)
 	return !tcmd_t::iscopy(cmd->rhs) && cmd->pred != TAGVER_ZERO;
 }
 
-static tcmd_t **topsort_(tcmd_t **phead, uint32_t *indeg);
-
-void tcmd_t::topsort(tcmd_t **phead, uint32_t *indeg)
-{
-	tcmd_t *x = *phead, **py = phead, **py0;
-
-	for (x = *phead; x;) {
-
-		*py = x;
-		for (; x && !tcmd_t::iscopy(x->rhs); x = x->next) {
-			py = &x->next;
-		}
-
-		py0 = py;
-		for (; x && tcmd_t::iscopy(x->rhs); x = x->next) {
-			py = &x->next;
-		}
-		*py = NULL;
-
-		py = topsort_(py0, indeg);
-	}
-}
-
-tcmd_t **topsort_(tcmd_t **phead, uint32_t *indeg)
-{
-	tcmd_t
-		*x0 = *phead, **px, *x,
-		*y0 = NULL, **py, **py1;
-
-	// initialize in-degree
-	for (x = x0; x; x = x->next) {
-		++indeg[x->rhs];
-	}
-
-	for (py = &y0;;) {
-		// reached end of list
-		if (!x0) break;
-
-		px = &x0;
-		py1 = py;
-		for (x = x0; x; x = x->next) {
-			if (indeg[x->lhs] == 0) {
-				--indeg[x->rhs];
-				*py = x;
-				py = &x->next;
-			} else {
-				*px = x;
-				px = &x->next;
-			}
-		}
-		*px = NULL;
-
-		// only cycles left
-		if (py == py1) break;
-	}
-	*py = x0;
-
-	*phead = y0;
-	for (; *py; py = &(*py)->next);
-	return py;
-}
-
 static tagver_t depend(const tcmd_t *x)
 {
 	const tagver_t r = x->rhs, h = x->pred;
 	return tcmd_t::iscopy(r) ? r : h;
 }
 
-void tcmd_t::topsort1(tcmd_t **phead, uint32_t *indeg)
+void tcmd_t::topsort(tcmd_t **phead, uint32_t *indeg)
 {
 	tcmd_t
 		*x0 = *phead, **px, *x,
diff --git a/re2c/src/dfa/tcmd.h b/re2c/src/dfa/tcmd.h
index 93aa6334..1dbd3f80 100644
--- a/re2c/src/dfa/tcmd.h
+++ b/re2c/src/dfa/tcmd.h
@@ -21,7 +21,6 @@ struct tcmd_t
 	static void swap(tcmd_t &x, tcmd_t &y);
 	static bool equal(const tcmd_t &x, const tcmd_t &y);
 	static void topsort(tcmd_t **phead, uint32_t *indeg);
-	static void topsort1(tcmd_t **phead, uint32_t *indeg);
 	static bool iscopy(tagver_t rhs);
 	static bool isset(const tcmd_t *cmd);
 	static bool isadd(const tcmd_t *cmd);
-- 
2.40.0