Separate the tree expander outHEADmaster

4 files changed, 170 insertions, 115 deletions

diff --git a/cmd/main.c b/cmd/main.c
index 5e72fea..dd95024 100644
--- a/cmd/main.c
+++ b/cmd/main.c
@@ -11,23 +11,11 @@
 #include "leven.h"
 #include "parse.h"
 #include "log.h"
+#include "tree.h"
 
-#define ACTIONS(X) \
-        X(ACTION_MATCH) \
-        X(ACTION_DEL_A) \
-        X(ACTION_ADD_B) \
-        X(ACTION_ET) \
-
-#define ENUM_VALUE(NAME) NAME,
-#define STRING_ARRAY_VALUE(NAME) #NAME,
-
-enum Action {
-    ACTIONS(ENUM_VALUE)
-};
-
-static const char *ActionNames[] = {
-    ACTIONS(STRING_ARRAY_VALUE)
-};
+size_t max(size_t a, size_t b) {
+	return a > b ? a : b;
+}
 
 int main(int argc, char **argv) {
 	int rc;
@@ -74,18 +62,41 @@ int main(int argc, char **argv) {
 	size_t *b_opens = malloc(b_tree.len * sizeof(size_t));
 
 	{
-		size_t *a_cursor = a_opens;
-		for(size_t i = 0; i < a_tree.len*2; i++) {
-			if(a_chunks[i] >= 0) {
-				*(a_cursor++) = a_chunks[i];
+		size_t *stack_base = malloc(max(a_tree.len, b_tree.len) * sizeof(size_t));
+		{
+			size_t *stack = stack_base;
+			size_t *write_cursor = a_opens;
+			ssize_t *read_cursor = a_chunks;
+			struct Tree tree = a_tree;
+
+			for(size_t i = 0; i < tree.len; i++) {
+				*(write_cursor++) = *(read_cursor++);
+
+				while(*stack < tree.adj.stride && *imat_nid(tree.adj, *stack, i) != 0) (*stack)++;
+				stack++;
+				// @CLEANUP: Maybe it would be nicer if we just added a fake
+				// element to the start of the array to abosrb the read
+				while(stack > stack_base && stack[-1] == 0) {
+					(stack--);
+					(*stack)--;
+				}
 			}
 		}
-	}
-	{
-		size_t *b_cursor = b_opens;
-		for(size_t i = 0; i < b_tree.len*2; i++) {
-			if(b_chunks[i] >= 0) {
-				*(b_cursor++) = b_chunks[i];
+		{
+			size_t *stack = stack_base;
+			size_t *write_cursor = b_opens;
+			ssize_t *read_cursor = b_chunks;
+			struct Tree tree = b_tree;
+
+			for(size_t i = 0; i < tree.len; i++) {
+				*(write_cursor++) = *(read_cursor++);
+
+				while(*stack < tree.adj.stride && *imat_nid(tree.adj, *stack, i) != 0) (*stack)++;
+				stack++;
+				while(stack > stack_base && stack[-1] == 0) {
+					(stack--);
+					(*stack)--;
+				}
 			}
 		}
 	}
@@ -97,13 +108,13 @@ int main(int argc, char **argv) {
 		*imat_uint32_t(cost, i+1, 0) = a_len;
 	}
 	for(size_t j = 0; j < 4; j++) {
-		size_t b_tag_end = b_chunks[j];
+		size_t b_tag_end = b_opens[j];
 		while(b[b_tag_end] != '>') b_tag_end++;
-		size_t b_len = b_tag_end - b_chunks[j];
+		size_t b_len = b_tag_end - b_opens[j];
 		*imat_uint32_t(cost, 0, j+1) = b_len;
 	}
 	for(size_t j = 0; j < 4; j++) {
-		size_t b_tag_end = b_chunks[j];
+		size_t b_tag_end = b_opens[j];
 		while(b[b_tag_end] != '>') b_tag_end++;
 		for(size_t i = 0; i < 4; i++) {
 			size_t a_tag_end = a_opens[i];
@@ -111,11 +122,11 @@ int main(int argc, char **argv) {
 			log("%ld, %ld", i, j);
 			
 			size_t a_len = a_tag_end - a_opens[i];
-			size_t b_len = b_tag_end - b_chunks[j];
+			size_t b_len = b_tag_end - b_opens[j];
 			log("B: %ld, A: %ld", b_len, a_len);
-			log("A: %.*s, B: %.*s", (int)a_len, a + a_opens[i], (int)b_len, b + b_chunks[j]);
+			log("A: %.*s, B: %.*s", (int)a_len, a + a_opens[i], (int)b_len, b + b_opens[j]);
 
-			*imat_uint32_t(cost, i+1, j+1) = !(a_len == b_len && memcmp(a + a_opens[i], b + b_chunks[j], a_len) == 0) * 1;
+			*imat_uint32_t(cost, i+1, j+1) = !(a_len == b_len && memcmp(a + a_opens[i], b + b_opens[j], a_len) == 0) * 1;
 		}
 	}
 	printf("\n");
@@ -188,88 +199,20 @@ int main(int argc, char **argv) {
 	// going to solve right now. I think we may have to lookup what decision
 	// we made for the open tag
 	// The worst case would be that we remove the whole A tree and the whole B tree
-	enum Action *emit_actions = malloc((a_tree.len + b_tree.len) * 2 * sizeof(*emit_actions));
-	size_t current_action = 0;
-	size_t a_cursor = 0;
-	size_t b_cursor = 0;
-	size_t alignment_cursor = 0;
-
-	size_t *a_close = malloc(a_tree.len * sizeof(size_t));
-	size_t a_close_top = 0;
-	size_t *b_close = malloc(b_tree.len * sizeof(size_t));
-	size_t b_close_top = 0;
-
-	while(a_cursor < a_tree.len && b_cursor < b_tree.len) {
-		if(alignment[alignment_cursor] == 0) {
-			alignment_cursor++;
-			emit_actions[current_action++] = ACTION_ADD_B;
-
-			b_close[b_close_top] = 0;
-			while(b_close[b_close_top] < b_tree.adj.stride && *imat_nid(b_tree.adj, b_close[b_close_top], b_cursor) != 0)
-				b_close[b_close_top]++;
-			b_close_top++;
-
-			b_cursor++;
-		} else if(a_cursor + 1 < alignment[alignment_cursor]) {
-			emit_actions[current_action++] = ACTION_DEL_A;
-
-			a_close[a_close_top] = 0;
-			while(a_close[a_close_top] < a_tree.adj.stride && *imat_nid(a_tree.adj, a_close[a_close_top], a_cursor) != 0)
-				a_close[a_close_top]++;
-			a_close_top++;
-
-			a_cursor++;
-		} else {
-			alignment_cursor++;
-			emit_actions[current_action++] = ACTION_MATCH;
-
-			b_close[b_close_top] = 0;
-			while(b_close[b_close_top] < b_tree.adj.stride && *imat_nid(b_tree.adj, b_close[b_close_top], b_cursor) != 0)
-				b_close[b_close_top]++;
-			b_close_top++;
-
-			a_close[a_close_top] = 0;
-			while(a_close[a_close_top] < a_tree.adj.stride && *imat_nid(a_tree.adj, a_close[a_close_top], a_cursor) != 0)
-				a_close[a_close_top]++;
-			a_close_top++;
-
-			a_cursor++;
-			b_cursor++;
-		}
-
-		while(a_close[a_close_top-1] == 0 || b_close[b_close_top-1] == 0) {
-			if(a_close[a_close_top-1] == 0 && b_close[b_close_top-1] == 0) {
-				a_close_top--;
-				a_close[a_close_top-1]--;
-				b_close_top--;
-				b_close[b_close_top-1]--;
-
-				emit_actions[current_action++] = ACTION_MATCH;
-			} else if(a_close[a_close_top-1] == 0) {
-				a_close_top--;
-				a_close[a_close_top-1]--;
-
-				emit_actions[current_action++] = ACTION_DEL_A;
-			} else if(b_close[b_close_top-1] == 0) {
-				b_close_top--;
-				b_close[b_close_top-1]--;
-
-				emit_actions[current_action++] = ACTION_ADD_B;
-			}
-		}
-	}
+	enum Action *emit_actions = malloc((a_tree.len + b_tree.len) * 2 * sizeof(*emit_actions) + 1);
+	expand_alignment(a_tree, b_tree, alignment, emit_actions);
 
 	logb("Actions: ");
-	for(size_t i = 0; i < current_action; i++) {
+	for(size_t i = 0; emit_actions[i] != ACTION_END; i++) {
 		lognl();
 		logc("    %s", ActionNames[emit_actions[i]]);
 	}
 	loge();
 	
-	b_cursor = 0;
-	a_cursor = 0;
+	size_t a_cursor = 0;
+	size_t b_cursor = 0;
 
-	for(size_t i = 0; i < current_action; i++) {
+	for(size_t i = 0; emit_actions[i] != ACTION_END; i++) {
 		size_t bc_len = (b_cursor+1 >= b_tree.len*2 ? strlen(b) : b_chunks[b_cursor+1]) - b_chunks[b_cursor];
 		size_t ac_len = (a_cursor+1 >= a_tree.len*2 ? strlen(a) : a_chunks[a_cursor+1]) - a_chunks[a_cursor];
 		if(emit_actions[i] == ACTION_MATCH) {
diff --git a/src/tree.c b/src/tree.c
new file mode 100644
index 0000000..3bb2737
--- /dev/null
+++ b/src/tree.c
@@ -0,0 +1,77 @@
+#include "tree.h"
+
+#include <stdlib.h>
+
+void expand_alignment(struct Tree a_tree, struct Tree b_tree, uint32_t *alignment, enum Action *emit_actions) {
+	size_t current_action = 0;
+	size_t a_cursor = 0;
+	size_t b_cursor = 0;
+	size_t alignment_cursor = 0;
+
+	size_t *a_close = malloc(a_tree.len * sizeof(size_t));
+	size_t a_close_top = 0;
+	size_t *b_close = malloc(b_tree.len * sizeof(size_t));
+	size_t b_close_top = 0;
+
+	while(a_cursor < a_tree.len && b_cursor < b_tree.len) {
+		if(alignment[alignment_cursor] == 0) {
+			alignment_cursor++;
+			emit_actions[current_action++] = ACTION_ADD_B;
+
+			b_close[b_close_top] = 0;
+			while(b_close[b_close_top] < b_tree.adj.stride && *imat_nid(b_tree.adj, b_close[b_close_top], b_cursor) != 0)
+				b_close[b_close_top]++;
+			b_close_top++;
+
+			b_cursor++;
+		} else if(a_cursor + 1 < alignment[alignment_cursor]) {
+			emit_actions[current_action++] = ACTION_DEL_A;
+
+			a_close[a_close_top] = 0;
+			while(a_close[a_close_top] < a_tree.adj.stride && *imat_nid(a_tree.adj, a_close[a_close_top], a_cursor) != 0)
+				a_close[a_close_top]++;
+			a_close_top++;
+
+			a_cursor++;
+		} else {
+			alignment_cursor++;
+			emit_actions[current_action++] = ACTION_MATCH;
+
+			b_close[b_close_top] = 0;
+			while(b_close[b_close_top] < b_tree.adj.stride && *imat_nid(b_tree.adj, b_close[b_close_top], b_cursor) != 0)
+				b_close[b_close_top]++;
+			b_close_top++;
+
+			a_close[a_close_top] = 0;
+			while(a_close[a_close_top] < a_tree.adj.stride && *imat_nid(a_tree.adj, a_close[a_close_top], a_cursor) != 0)
+				a_close[a_close_top]++;
+			a_close_top++;
+
+			a_cursor++;
+			b_cursor++;
+		}
+
+		while(a_close[a_close_top-1] == 0 || b_close[b_close_top-1] == 0) {
+			if(a_close[a_close_top-1] == 0 && b_close[b_close_top-1] == 0) {
+				a_close_top--;
+				a_close[a_close_top-1]--;
+				b_close_top--;
+				b_close[b_close_top-1]--;
+
+				emit_actions[current_action++] = ACTION_MATCH;
+			} else if(a_close[a_close_top-1] == 0) {
+				a_close_top--;
+				a_close[a_close_top-1]--;
+
+				emit_actions[current_action++] = ACTION_DEL_A;
+			} else if(b_close[b_close_top-1] == 0) {
+				b_close_top--;
+				b_close[b_close_top-1]--;
+
+				emit_actions[current_action++] = ACTION_ADD_B;
+			}
+		}
+	}
+
+	emit_actions[current_action] = ACTION_END;
+}
diff --git a/src/tree.h b/src/tree.h
new file mode 100644
index 0000000..e1dd424
--- /dev/null
+++ b/src/tree.h
@@ -0,0 +1,23 @@
+#pragma once
+
+#include "parse.h"
+#include <stddef.h>
+
+#define ACTIONS(X) \
+        X(ACTION_MATCH) \
+        X(ACTION_DEL_A) \
+        X(ACTION_ADD_B) \
+        X(ACTION_END) \
+
+#define ENUM_VALUE(NAME) NAME,
+#define STRING_ARRAY_VALUE(NAME) #NAME,
+
+enum Action {
+    ACTIONS(ENUM_VALUE)
+};
+
+static const char *ActionNames[] = {
+    ACTIONS(STRING_ARRAY_VALUE)
+};
+
+void expand_alignment(struct Tree a_tree, struct Tree b_tree, uint32_t *alignment, enum Action *emit_actions);
diff --git a/test/parse.c b/test/parse.c
index 328bfd3..e1474cd 100644
--- a/test/parse.c
+++ b/test/parse.c
@@ -17,7 +17,7 @@ int main(int argc, char **argv) {
 
 	{
 		struct Tree a;
-		size_t *chunks = NULL;
+		ssize_t *chunks = NULL;
 		if(parse_string("<root></root>", &a, &chunks) != 0) return fail();
 		if(a.adj.stride != 1) return fail();
 		if(a.len != 1) return fail();
@@ -28,6 +28,7 @@ int main(int argc, char **argv) {
 		
 		// Verify chunk offsets
 		if(chunks[0] != 0) return fail();
+		if(chunks[1] != 6) return fail();
 		
 		free(chunks);
 		free(a.adj.data);
@@ -35,7 +36,7 @@ int main(int argc, char **argv) {
 
 	{
 		struct Tree a;
-		size_t *chunks = NULL;
+		ssize_t *chunks = NULL;
 		if(parse_string("<root> </root>", &a, &chunks) != 0) return fail();
 		if(a.adj.stride != 1) return fail();
 		if(a.len != 1) return fail();
@@ -46,6 +47,7 @@ int main(int argc, char **argv) {
 		
 		// Verify chunk offsets
 		if(chunks[0] != 0) return fail();
+		if(chunks[1] != 7) return fail();
 		
 		free(chunks);
 		free(a.adj.data);
@@ -53,7 +55,7 @@ int main(int argc, char **argv) {
 
 	{
 		struct Tree a;
-		size_t *chunks = NULL;
+		ssize_t *chunks = NULL;
 		if(parse_string("<root>\n</root>", &a, &chunks) != 0) return fail();
 		if(a.adj.stride != 1) return fail();
 		if(a.len != 1) return fail();
@@ -64,6 +66,7 @@ int main(int argc, char **argv) {
 		
 		// Verify chunk offsets
 		if(chunks[0] != 0) return fail();
+		if(chunks[1] != 7) return fail();
 		
 		free(chunks);
 		free(a.adj.data);
@@ -71,7 +74,7 @@ int main(int argc, char **argv) {
 
 	{
 		struct Tree a;
-		size_t *chunks = NULL;
+		ssize_t *chunks = NULL;
 		if(parse_string("<root><a></a><b></b></root>", &a, &chunks) != 0) return fail();
 		if(a.adj.stride != 2) return fail();
 		if(a.len != 3) return fail();
@@ -85,7 +88,10 @@ int main(int argc, char **argv) {
 		// Verify chunk offsets
 		if(chunks[0] != 0) return fail();
 		if(chunks[1] != 6) return fail();
-		if(chunks[2] != 13) return fail();
+		if(chunks[2] != 9) return fail();
+		if(chunks[3] != 13) return fail();
+		if(chunks[4] != 16) return fail();
+		if(chunks[5] != 20) return fail();
 		
 		free(chunks);
 		free(a.adj.data);
@@ -93,7 +99,7 @@ int main(int argc, char **argv) {
 
 	{
 		struct Tree a;
-		size_t *chunks = NULL;
+		ssize_t *chunks = NULL;
 		if(parse_string("<root><a><c></c></a><b></b></root>", &a, &chunks) != 0) return fail();
 		if(a.adj.stride != 2) return fail();
 		if(a.len != 4) return fail();
@@ -109,7 +115,11 @@ int main(int argc, char **argv) {
 		if(chunks[0] != 0) return fail();
 		if(chunks[1] != 6) return fail();
 		if(chunks[2] != 9) return fail();
-		if(chunks[3] != 20) return fail();
+		if(chunks[3] != 12) return fail();
+		if(chunks[4] != 16) return fail();
+		if(chunks[5] != 20) return fail();
+		if(chunks[6] != 23) return fail();
+		if(chunks[7] != 27) return fail();
 		
 		free(chunks);
 		free(a.adj.data);
@@ -118,7 +128,7 @@ int main(int argc, char **argv) {
 	// We forgot to close the open tag
 	{
 		struct Tree a;
-		size_t *chunks = NULL;
+		ssize_t *chunks = NULL;
 		fflush(stdout);
 		if(parse_string("<root</root>", &a, &chunks) != 1) return fail();
 		fflush(stdout);
@@ -127,7 +137,7 @@ int main(int argc, char **argv) {
 	// Test self-closing tag
 	{
 		struct Tree a;
-		size_t *chunks = NULL;
+		ssize_t *chunks = NULL;
 		fflush(stdout);
 		if(parse_string("<root><a /></root>", &a, &chunks) != 0) return fail();
 		if(a.adj.stride != 1) return fail();
@@ -141,6 +151,8 @@ int main(int argc, char **argv) {
 		// Verify chunk offsets
 		if(chunks[0] != 0) return fail();
 		if(chunks[1] != 6) return fail();
+		if(chunks[2] != 9) return fail();
+		if(chunks[3] != 11) return fail();
 
 		free(chunks);
 		free(a.adj.data);