[PATCH 12/15] name-rev: eliminate recursion in name_rev()

["SZEDER Gábor" <szeder.dev@gmail.com>]

The name_rev() function calls itself recursively for each interesting
parent of the commit it got as parameter, and, consequently, it can
segfault when processing a deep history if it exhausts the available
stack space.  E.g. running 'git name-rev --all' and 'git name-rev
HEAD~100000' in the gcc, gecko-dev, llvm, and WebKit repositories
results in segfaults on my machine.

Eliminate the recursion by inserting the interesting parents into a
'commit_list' and iteratating until the list becomes empty.

Note that the order in which the parent commits are added to that list
is important: they must be inserted at the beginning of the list, and
their relative order must be kept as well, because otherwise
performance suffers.

The stacksize-limited test 'name-rev works in a deep repo' in
't6120-describe.sh' demonstrated this issue and expected failure.  Now
the recursion is gone, so flip it to expect success.

Also gone are the dmesg entries logging the segfault of the git
process on every execution of the test suite.

Unfortunately, eliminating the recursion comes with a performance
penaly: 'git name-rev --all' tends to be between 15-20% slower than
before.

Note that this slightly changes the order of lines in the output of
'git name-rev --all', usually swapping two lines every 35 lines in
git.git or every 150 lines in linux.git.  This shouldn't matter in
practice, because the output has always been unordered anyway.

This patch is best viewed with '--ignore-all-space'.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 builtin/name-rev.c  | 85 ++++++++++++++++++++++++++-------------------
 t/t6120-describe.sh |  2 +-
 2 files changed, 51 insertions(+), 36 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index f2198a8bc3..b6fa495340 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -100,48 +100,63 @@ static struct rev_name *create_or_update_name(struct commit *commit,
 		return NULL;
 }
 
-static void name_rev(struct commit *commit,
+static void name_rev(struct commit *start_commit,
 		const char *tip_name, timestamp_t taggerdate,
 		int from_tag)
 {
-	struct rev_name *name = get_commit_rev_name(commit);
-	struct commit_list *parents;
-	int parent_number = 1;
-
-	for (parents = commit->parents;
-			parents;
-			parents = parents->next, parent_number++) {
-		struct commit *parent = parents->item;
-		const char *new_name;
-		int generation, distance;
-
-		parse_commit(parent);
-		if (parent->date < cutoff)
-			continue;
+	struct commit_list *list = NULL;
+
+	commit_list_insert(start_commit, &list);
+
+	while (list) {
+		struct commit *commit = pop_commit(&list);
+		struct rev_name *name = get_commit_rev_name(commit);
+		struct commit_list *parents, *new_parents = NULL;
+		struct commit_list **last_new_parent = &new_parents;
+		int parent_number = 1;
+
+		for (parents = commit->parents;
+				parents;
+				parents = parents->next, parent_number++) {
+			struct commit *parent = parents->item;
+			const char *new_name;
+			int generation, distance;
+
+			parse_commit(parent);
+			if (parent->date < cutoff)
+				continue;
 
-		if (parent_number > 1) {
-			size_t len;
+			if (parent_number > 1) {
+				size_t len;
+
+				strip_suffix(name->tip_name, "^0", &len);
+				if (name->generation > 0)
+					new_name = xstrfmt("%.*s~%d^%d",
+							   (int)len,
+							   name->tip_name,
+							   name->generation,
+							   parent_number);
+				else
+					new_name = xstrfmt("%.*s^%d", (int)len,
+							   name->tip_name,
+							   parent_number);
+				generation = 0;
+				distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
+			} else {
+				new_name = name->tip_name;
+				generation = name->generation + 1;
+				distance = name->distance + 1;
+			}
 
-			strip_suffix(tip_name, "^0", &len);
-			if (name->generation > 0)
-				new_name = xstrfmt("%.*s~%d^%d", (int)len, tip_name,
-						   name->generation,
-						   parent_number);
-			else
-				new_name = xstrfmt("%.*s^%d", (int)len, tip_name,
-						   parent_number);
-			generation = 0;
-			distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
-		} else {
-			new_name = tip_name;
-			generation = name->generation + 1;
-			distance = name->distance + 1;
+			if (create_or_update_name(parent, new_name, taggerdate,
+						  generation, distance,
+						  from_tag))
+				last_new_parent = commit_list_append(parent,
+						  last_new_parent);
 		}
 
-		if (create_or_update_name(parent, new_name, taggerdate,
-					  generation, distance,
-					  from_tag))
-			name_rev(parent, new_name, taggerdate, from_tag);
+		*last_new_parent = list;
+		list = new_parents;
 	}
 }
 
diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
index 2a0f2204c4..e37f02d21c 100755
--- a/t/t6120-describe.sh
+++ b/t/t6120-describe.sh
@@ -379,7 +379,7 @@ test_expect_success 'describe tag object' '
 	test_i18ngrep "fatal: test-blob-1 is neither a commit nor blob" actual
 '
 
-test_expect_failure ULIMIT_STACK_SIZE 'name-rev works in a deep repo' '
+test_expect_success ULIMIT_STACK_SIZE 'name-rev works in a deep repo' '
 	i=1 &&
 	while test $i -lt 8000
 	do
-- 
2.23.0.331.g4e51dcdf11