From 8989dae638fd0e71a3fc39dcbe664b79fb4ce8ad Mon Sep 17 00:00:00 2001
From: Ulya Trofimovich <skvadrik@gmail.com>
Date: Wed, 16 Mar 2016 12:20:25 +0000
Subject: [PATCH] Use distinct type for path suffixes during skeleton data
 generation.

---
 re2c/src/ir/skeleton/generate_data.cc | 18 +++++++++---------
 re2c/src/ir/skeleton/path.h           | 22 +++++++++++++++++++---
 re2c/src/ir/skeleton/skeleton.cc      |  4 ++--
 re2c/src/ir/skeleton/skeleton.h       |  3 ++-
 4 files changed, 32 insertions(+), 15 deletions(-)

diff --git a/re2c/src/ir/skeleton/generate_data.cc b/re2c/src/ir/skeleton/generate_data.cc
index d4bb5947..7e1a582a 100644
--- a/re2c/src/ir/skeleton/generate_data.cc
+++ b/re2c/src/ir/skeleton/generate_data.cc
@@ -147,16 +147,17 @@ template <typename cunit_t, typename key_t> static void cover(
 {
 	const Node &node = skel.nodes[i];
 	uint8_t &loop = skel.loops[i];
-	path_t *&suffix = skel.suffixes[i];
+	suffix_t *&suffix = skel.suffixes[i];
 
 	if (node.end() && suffix == NULL) {
-		suffix = new path_t(i);
+		suffix = new suffix_t;
 	}
 
 	if (suffix != NULL)
 	{
-		prefix.append(suffix);
+		prefix.push_sfx(*suffix);
 		size = size + cover_one<cunit_t, key_t>(skel, input, keys, prefix);
+		prefix.pop_sfx(*suffix);
 	} else if (loop < 2) {
 		local_inc _(loop);
 		Node::arcs_t::const_iterator
@@ -165,15 +166,14 @@ template <typename cunit_t, typename key_t> static void cover(
 		for (; arc != end && !size.overflow(); ++arc) {
 			const size_t j = arc->first;
 
-			path_t new_prefix = prefix;
-			new_prefix.push(j);
-			cover<cunit_t, key_t>(skel, input, keys, new_prefix, size, j);
+			prefix.push(j);
+			cover<cunit_t, key_t>(skel, input, keys, prefix, size, j);
+			prefix.pop();
 
-			const path_t *sfx = skel.suffixes[j];
+			const suffix_t *sfx = skel.suffixes[j];
 			if (sfx != NULL && suffix == NULL) {
-				suffix = new path_t(i);
+				suffix = new suffix_t(*sfx);
 				suffix->push(j);
-				suffix->append(sfx);
 			}
 		}
 	}
diff --git a/re2c/src/ir/skeleton/path.h b/re2c/src/ir/skeleton/path.h
index a5865b22..f5709c5e 100644
--- a/re2c/src/ir/skeleton/path.h
+++ b/re2c/src/ir/skeleton/path.h
@@ -9,6 +9,19 @@
 namespace re2c
 {
 
+class suffix_t
+{
+	std::vector<size_t> arcs;
+
+public:
+	suffix_t() : arcs() {}
+	void push(size_t i)
+	{
+		arcs.push_back(i);
+	}
+	friend class path_t;
+};
+
 class path_t
 {
 	std::vector<size_t> arcs;
@@ -78,10 +91,13 @@ public:
 	{
 		arcs.pop_back();
 	}
-	void append(const path_t *p)
+	void push_sfx(const suffix_t &suffix)
+	{
+		arcs.insert(arcs.end(), suffix.arcs.rbegin(), suffix.arcs.rend());
+	}
+	void pop_sfx(const suffix_t &suffix)
 	{
-		assert(arcs.back() == p->arcs.front());
-		arcs.insert(arcs.end(), p->arcs.begin() + 1, p->arcs.end());
+		arcs.resize(arcs.size() - suffix.arcs.size());
 	}
 	bool operator<(const path_t &p) const
 	{
diff --git a/re2c/src/ir/skeleton/skeleton.cc b/re2c/src/ir/skeleton/skeleton.cc
index 7baa656a..0664b108 100644
--- a/re2c/src/ir/skeleton/skeleton.cc
+++ b/re2c/src/ir/skeleton/skeleton.cc
@@ -65,12 +65,12 @@ Skeleton::Skeleton(
 		nodes_count(dfa.states.size() + 1), // +1 for default state
 		nodes(new Node[nodes_count]),
 		loops(new uint8_t[nodes_count]),
-		suffixes(new path_t*[nodes_count]),
+		suffixes(new suffix_t*[nodes_count]),
 		sizeof_key(4),
 		rules(rs)
 {
 	memset(loops, 0, sizeof(uint8_t) * nodes_count);
-	memset(suffixes, 0, sizeof(path_t*) * nodes_count);
+	memset(suffixes, 0, sizeof(suffix_t*) * nodes_count);
 
 	const size_t nc = cs.size() - 1;
 
diff --git a/re2c/src/ir/skeleton/skeleton.h b/re2c/src/ir/skeleton/skeleton.h
index 93460ed8..856fd853 100644
--- a/re2c/src/ir/skeleton/skeleton.h
+++ b/re2c/src/ir/skeleton/skeleton.h
@@ -21,6 +21,7 @@ namespace re2c
 struct dfa_t;
 struct OutputFile;
 struct path_t;
+struct suffix_t;
 
 typedef local_increment_t<uint8_t> local_inc;
 
@@ -58,7 +59,7 @@ struct Skeleton
 	uint8_t *loops;
 
 	// paths to end node (for constructing path cover)
-	path_t **suffixes;
+	suffix_t **suffixes;
 
 	size_t sizeof_key;
 	rules_t rules;
-- 
2.40.0