name-rev: change ULONG_MAX to TIME_MAX

Earlier, dddbad728c ("timestamp_t: a new data type for timestamps", 2017-04-26) changed several types to timestamp_t.

5589e87fd8 ("name-rev: change a "long" variable to timestamp_t", 2017-05-20) cleaned up a missed variable, but both missed a _MAX constant.

Change the remaining constant to the one appropriate for the current type

---
 builtin/name-rev.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index c41ea7c2a6..598da6c8bc 100644
@@ -253,7 +253,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
 		struct commit *commit = (struct commit *)o;
 		int from_tag = starts_with(path, "refs/tags/");
 
-		if (taggerdate == ULONG_MAX)
+		if (taggerdate == TIME_MAX)
 			taggerdate = ((struct commit *)o)->date;
 		path = name_ref_abbrev(path, can_abbreviate_output);
 		name_rev(commit, xstrdup(path), taggerdate, 0, 0,

2.14.1.603.gf58147c36e

Hi Michael,

Good catch!

ACK,
Dscho

Thanks.

I think this (and the earlier 5589e8) was caused by an unnoticed semantic conflict at 78089b71 ("Merge branch 'jc/name-rev-lw-tag'", 2017-05-30). Merging is sometimes hard ;-)

Will queue.

Junio C Hamano venit, vidit, dixit 06.09.2017 05:35:

Simple merges and semi-simple merges...

BTW, there's more fallout from those name-rev changes: In connection with that other thread about surprising describe results for emacs.git I noticed that I can easily get "git name-rev --stdin" to segfault there. As easy as

echo bc5d96a0b2a1dccf7eeeec459e40d21b54c977f4 | git name-rev --stdin

for example.

That's unfortunate for the use-case of name-rev to amend git log output.

The reason seems to be that with "--stdin" or "--all", "name-rev" walks and names all commits before beginning to use that those names for even a single commit as above.

That segfault bisects to the logic changing commit in jc/name-rev-lw-tag, but I think the changed logic simply leads to more xmallocs() the segfault sooner now. Or something that I dind't spot even after a few hours.

On the other hand, nearly every time that I try to understand describe or name-rev I want get rid of insert_commit_by_date() and the like and replace this by generations, and maybe a simple rev-walk (per ref)...

The segfault seems to be due to running out of stack space. The problem is that name_rev() is recursive over the history graph. That topic added a parameter to the function, which increased the memory used for each level of the recursion. But the fundamental problem has always been there. The right solution is to switch to iteration (with our own stack structure if necessary).

We had similar problems with the recursive --contains traversal in tag, and ended up with cbc60b6720 (git tag --contains: avoid stack overflow, 2014-04-24).

-Peff

Jeff King venit, vidit, dixit 06.09.2017 15:35:

Cool, thanks for the pointer. ulimit -s is a great way to test this.

Michael

The lazy prerequisite ULIMIT_STACK_SIZE is used only in t7004 so far.

Move it to test-lib.sh so that it can be used in other tests (which it will be in a follow-up commit).

---
 t/t7004-tag.sh | 6 ------
 t/test-lib.sh  | 6 ++++++
 2 files changed, 6 insertions(+), 6 deletions(-)

index dbcd6f623c..5bf5ace56b 100755
@@ -1863,12 +1863,6 @@ test_expect_success 'version sort with very long prerelease suffix' '
 	git tag -l --sort=version:refname
 '
 
-run_with_limited_stack () {
-	(ulimit -s 128 && "$@")
-}
-
-test_lazy_prereq ULIMIT_STACK_SIZE 'run_with_limited_stack true'
-
 # we require ulimit, this excludes Windows
 test_expect_success ULIMIT_STACK_SIZE '--contains and --no-contains work in a deep repo' '
 	>expect &&

index 5fbd8d4a90..f22c1b260a 100644
@@ -1167,6 +1167,12 @@ run_with_limited_cmdline () {
 
 test_lazy_prereq CMDLINE_LIMIT 'run_with_limited_cmdline true'
 
+run_with_limited_stack () {
+	(ulimit -s 128 && "$@")
+}
+
+test_lazy_prereq ULIMIT_STACK_SIZE 'run_with_limited_stack true'
+
 build_option () {
 	git version --build-options |
 	sed -ne "s/^$1: //p"

2.14.1.603.gf58147c36e

name-rev is used in a few tests, but tested only in t6120 along with describe so far.

Add tests for name-rev with --all and --stdin.

---
 t/t6120-describe.sh | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

index aa74eb8f0d..7c5728ebd5 100755
@@ -198,6 +198,31 @@ test_expect_success 'name-rev with exact tags' '
 	test_cmp expect actual
 '
 
+test_expect_success 'name-rev --all' '
+	>expect.unsorted &&
+	for rev in $(git rev-list --all)
+	do
+		git name-rev $rev >>expect.unsorted
+	done &&
+	sort <expect.unsorted >expect &&
+	git name-rev --all >actual.unsorted &&
+	sort <actual.unsorted >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'name-rev --stdin' '
+	>expect.unsorted &&
+	for rev in $(git rev-list --all)
+	do
+		name=$(git name-rev --name-only $rev) &&
+		echo "$rev ($name)" >>expect.unsorted
+	done &&
+	sort <expect.unsorted >expect &&
+	git rev-list --all | git name-rev --stdin >actual.unsorted &&
+	sort <actual.unsorted >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success 'describe --contains with the exact tags' '
 	echo "A^0" >expect &&
 	tag_object=$(git rev-parse refs/tags/A) &&

2.14.1.603.gf58147c36e

t6120 breaks the repo state intentionally in the last tests.

Clean up the breakage afterwards (and before adding more tests).

---
 t/t6120-describe.sh | 1 +
 1 file changed, 1 insertion(+)

index 7c5728ebd5..1997ccde56 100755
@@ -275,6 +275,7 @@ test_expect_success 'describe chokes on severely broken submodules' '
 '
 test_expect_success 'describe ignoring a borken submodule' '
 	git describe --broken >out &&
+	test_when_finished "mv .git/modules/sub_moved .git/modules/sub1" &&
 	grep broken out
 '
 

2.14.1.603.gf58147c36e

Depending on the implementation of walks, limitted stack size may lead to problems (for recursion).

Test name-rev and describe with deep repos and limitted stack size and mark the former with known failure.

We add these tests (which add gazillions of commits) last so as to keep the runtime of other subtests the same.

---
 t/t6120-describe.sh | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

index 1997ccde56..dd6dd9df9b 100755
@@ -279,4 +279,35 @@ test_expect_success 'describe ignoring a borken submodule' '
 	grep broken out
 '
 
+# we require ulimit, this excludes Windows
+test_expect_failure ULIMIT_STACK_SIZE 'name-rev works in a deep repo' '
+	i=1 &&
+	while test $i -lt 8000
+	do
+		echo "commit refs/heads/master
+committer A U Thor <[email protected]> $((1000000000 + $i * 100)) +0200
+data <<EOF
+commit #$i
+EOF"
+		test $i = 1 && echo "from refs/heads/master^0"
+		i=$(($i + 1))
+	done | git fast-import &&
+	git checkout master &&
+	git tag far-far-away HEAD^ &&
+	echo "HEAD~4000 tags/far-far-away~3999" >expect &&
+	git name-rev HEAD~4000 >actual &&
+	test_cmp expect actual &&
+	run_with_limited_stack git name-rev HEAD~4000 >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success ULIMIT_STACK_SIZE 'describe works in a deep repo' '
+	git tag -f far-far-away HEAD~7999 &&
+	echo "far-far-away" >expect &&
+	git describe --tags --abbrev=0 HEAD~4000 >actual &&
+	test_cmp expect actual &&
+	run_with_limited_stack git describe --tags --abbrev=0 HEAD~4000 >actual &&
+	test_cmp expect actual
+'
+
 test_done

2.14.1.603.gf58147c36e

name-rev segfaults for me in emacs.git with the typical 8102 stack size. The reason is the recursive walk that name-rev uses.

This series adds a test to mark this as known failure, after some clean-ups.

Michael J Gruber (4):
t7004: move limited stack prereq to test-lib
t6120: test name-rev --all and --stdin
t6120: clean up state after breaking repo
t6120: test describe and name-rev with deep repos

 t/t6120-describe.sh | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 t/t7004-tag.sh      |  6 ------
 t/test-lib.sh       |  6 ++++++
 3 files changed, 63 insertions(+), 6 deletions(-)

2.14.1.603.gf58147c36e

These all look reasonable to me. The size of the test case in the final one is presumably arbitrary and just copied from t7004. I don't know if it's worth trying to shrink it. It could shorten a rather expensive test. OTOH, if we shorten it too much then we might get a false pass (e.g., if the algorithm remains recursive but has a smaller stack footprint).

Now comes the hard part: rewriting the C code. :)

-Peff

Jeff King venit, vidit, dixit 07.09.2017 16:54:

Looking at it more closely, the solution in cbc60b6720 ("git tag --contains: avoid stack overflow", 2014-04-24) seems to be a bit "ad hoc" to me:

First of all, there is more than "tag --contains" that may exceed the stack by recursion. So I would expect the solution to be more general, and not localised and specialised to builtin/tag.c

Second, this is a walk, so I'm wondering whether our revision walk machinery should be the place to add missing functionality (if any). That way, everything would benefit from possible or existing improvements there. For example, I think some of our "extra walkers" don't heed object replacements. (I need to test more.)

Michael

At the time, tag was the only one using this depth-first contains algorithm. It's since been adapted to ref-filter.c, but of course the stack handling went with it.

Most traversals have a date-sorted queue, so are effectively doing a breadth-first iteration with no recursion.

It's possible that name-rev could make better use of the existing traversal machinery. It's often tough to do so, though, because that machinery gives you a linearized ordering of the commits. Whereas something like name-rev really cares about the order that it visits the commits, because it's building up the names.

It's the same for this "tag --contains" traversal. It _used_ to be a series of merge-base computations. But by doing a custom traversal, we can cache incremental results through the graph and avoid walking over the same bits multiple times. There actually is a way to do it with the regular breadth-first traversal, but you have to store one bit per ref you're checking for each commit.

I played around with that a bit a while ago, and it did seem to work. I can dig up the patches if you're interested. But one downside is that one bit per ref per commit adds up if you have a lot of refs. A large number of those bitfields will be the same, so you could probably get by with a copy-on-write scheme, but I never implemented that.

Of course somebody may have a more clever algorithm, too. I don't claim the above is a proof. ;)

-Peff