[PATCH] describe: rewrite name_rev() iteratively

[Dragos Foianu <dragos.foianu@gmail.com>]

The "git describe --contains" command uses the name_rev() function which
is currently a recursive function. This causes a Stack Overflow when the
history is large enough.

Rewrite name_rev iteratively using a stack on the heap. This slightly
reduces performance due to the extra operations on the heap, but the
function no longer overflows the stack.

Reported-by: Sylvestre Ledru <sylvestre@mozilla.com>
Signed-off-by: Dragos Foianu <dragos.foianu@gmail.com>
---
 builtin/name-rev.c |  176 ++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 128 insertions(+), 48 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index c824d4e..5848d81 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -19,66 +19,146 @@ static long cutoff = LONG_MAX;
 /* How many generations are maximally preferred over _one_ merge traversal? */
 #define MERGE_TRAVERSAL_WEIGHT 65535
 
+typedef struct rev_data {
+	struct commit *commit;
+	const char *tip_name;
+	int generation;
+	int distance;
+	int deref;
+} *rev_data;
+
+typedef struct rev_stack {
+	struct rev_data *rev;
+	struct rev_stack *next;
+} *rev_stack;
+
+static void stack_push(rev_stack *stack, rev_data data) {
+	rev_stack new_node = xmalloc(sizeof(*new_node));
+
+	new_node->rev = data;
+	new_node->next = *stack;
+	*stack = new_node;
+}
+
+static void stack_push_end(rev_stack *stack, rev_data data) {
+	rev_stack new_node = xmalloc(sizeof(*new_node));
+
+	while (*stack != NULL)
+		stack = &(*stack)->next;
+	new_node->rev = data;
+	new_node->next = *stack;
+	*stack = new_node;
+}
+
+static rev_data stack_pop(rev_stack *stack) {
+	rev_stack next = (*stack)->next;
+	rev_data rev = (*stack)->rev;
+	free(*stack);
+
+	*stack = next;
+	return rev;
+}
+
+static rev_data make_rev_data(struct commit *commit,
+		const char* tip_name, int generation, int distance,
+		int deref)
+{
+	rev_data data = xmalloc(sizeof(*data));
+
+	data->commit = commit;
+	data->tip_name = tip_name;
+	data->generation = generation;
+	data->distance = distance;
+	data->deref = deref;
+
+	return data;
+}
+
 static void name_rev(struct commit *commit,
 		const char *tip_name, int generation, int distance,
 		int deref)
 {
-	struct rev_name *name = (struct rev_name *)commit->util;
-	struct commit_list *parents;
-	int parent_number = 1;
+	rev_stack stack = NULL;
+	rev_data data, next_rev;
 
-	parse_commit(commit);
+	data = make_rev_data(commit, tip_name, generation, distance, deref);
+	stack_push(&stack, data);
 
-	if (commit->date < cutoff)
-		return;
+	while (stack != NULL) {
+		rev_data rev = stack_pop(&stack);
 
-	if (deref) {
-		char *new_name = xmalloc(strlen(tip_name)+3);
-		strcpy(new_name, tip_name);
-		strcat(new_name, "^0");
-		tip_name = new_name;
+		struct rev_name *name = (struct rev_name *) rev->commit->util;
+		struct commit_list *parents;
+		int parent_number = 1;
 
-		if (generation)
-			die("generation: %d, but deref?", generation);
-	}
+		parse_commit(rev->commit);
+
+		if (rev->commit->date < cutoff)
+			continue;
+
+		if (rev->deref) {
+			char *new_name = xmalloc(strlen(rev->tip_name) + 3);
+			strcpy(new_name, rev->tip_name);
+			strcat(new_name, "^0");
+			rev->tip_name = new_name;
 
-	if (name == NULL) {
-		name = xmalloc(sizeof(rev_name));
-		commit->util = name;
-		goto copy_data;
-	} else if (name->distance > distance) {
+			if (rev->generation)
+				die("generation: %d, but deref?",
+					rev->generation);
+		}
+
+		if (name == NULL) {
+			name = xmalloc(sizeof(rev_name));
+			rev->commit->util = name;
+			goto copy_data;
+		} else if (name->distance > rev->distance) {
 copy_data:
-		name->tip_name = tip_name;
-		name->generation = generation;
-		name->distance = distance;
-	} else
-		return;
-
-	for (parents = commit->parents;
-			parents;
-			parents = parents->next, parent_number++) {
-		if (parent_number > 1) {
-			int len = strlen(tip_name);
-			char *new_name = xmalloc(len +
-				1 + decimal_length(generation) +  /* ~<n> */
-				1 + 2 +				  /* ^NN */
-				1);
-
-			if (len > 2 && !strcmp(tip_name + len - 2, "^0"))
-				len -= 2;
-			if (generation > 0)
-				sprintf(new_name, "%.*s~%d^%d", len, tip_name,
-						generation, parent_number);
-			else
-				sprintf(new_name, "%.*s^%d", len, tip_name,
-						parent_number);
+			name->tip_name = rev->tip_name;
+			name->generation = rev->generation;
+			name->distance = rev->distance;
+		} else
+			continue;
 
-			name_rev(parents->item, new_name, 0,
-				distance + MERGE_TRAVERSAL_WEIGHT, 0);
-		} else {
-			name_rev(parents->item, tip_name, generation + 1,
-				distance + 1, 0);
+		for (parents = rev->commit->parents;
+				parents;
+				parents = parents->next, parent_number++) {
+			if (parent_number > 1) {
+				int len = strlen(rev->tip_name);
+				char *new_name = xmalloc(len +
+					/* ~<n> */
+					1 + decimal_length(rev->generation) +
+					/* ^NN */
+					1 + 2 +
+					1);
+
+				if (len > 2 &&
+					!strcmp(rev->tip_name + len - 2, "^0"))
+					len -= 2;
+
+				if (rev->generation > 0)
+					sprintf(new_name, "%.*s~%d^%d", len,
+						rev->tip_name, rev->generation,
+						parent_number);
+				else
+					sprintf(new_name, "%.*s^%d", len,
+						rev->tip_name, parent_number);
+
+				next_rev = make_rev_data(parents->item,
+					new_name, 0,
+					rev->distance + MERGE_TRAVERSAL_WEIGHT,
+					0);
+
+				stack_push_end(&stack, next_rev);
+			} else {
+				next_rev = make_rev_data(parents->item,
+					rev->tip_name, rev->generation + 1,
+					rev->distance + 1, 0);
+
+				stack_push(&stack, next_rev);
+			}
 		}
+
+		free(rev);
 	}
 }
 
-- 
1.7.10.4