Skip to contentSkip to conversation

name-rev: use generation numbers if available

PATCH Superseded Jacob Keller 4 participants 18 messages Feb 28, 2022 – Mar 7, 2022

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v2 cover name-rev: use generation numbers if available

From: Jacob Keller <[email protected]>

Thanks for the review, Stolee!

Here's the range-diff since v1:

1: e7e302376dd6 ! 1: 8ab5d987bf93 name-rev: use generation numbers if available

    @@ Commit message
         This heuristic impacts git name-rev, and by extension git describe
         --contains which is built on top of name-rev.
     
    -    Further more, if --annotate-stdin is used, the heuristic is not enabled
    -    because the full history has to be analyzed anyways. This results in
    -    some confusion if a user sees that --annotate-stdin works but a normal
    -    name-rev does not.
    +    Further more, if --all or --annotate-stdin is used, the heuristic is not
    +    enabled because the full history has to be analyzed anyways. This
    +    results in some confusion if a user sees that --annotate-stdin works but
    +    a normal name-rev does not.
     
         If the repository has a commit graph, we can use the generation numbers
         instead of using the commit dates. This is essentially the same check
         except that generation numbers make it exact, where the commit date
         heuristic could be incorrect due to clock errors.
     
    -    Add a test case which covers this behavior and shows how the commit
    -    graph makes the name-rev process work.
    +    Since we're extending the notion of cutoff to more than one variable,
    +    create a series of functions for setting and checking the cutoff. This
    +    avoids duplication and moves access of the global cutoff and
    +    generation_cutoff to as few functions as possible.
    +
    +    Add several test cases including coverage of --all, --annotate-stdin,
    +    and the normal case with the cutoff heuristic, both with and without
    +    commit graphs enabled.
     
         Signed-off-by: Jacob Keller <[email protected]>
     
    @@ builtin/name-rev.c: struct rev_name {
      static timestamp_t cutoff = TIME_MAX;
      static struct commit_rev_name rev_names;
      
    ++/* Disable the cutoff checks entirely */
    ++static void disable_cutoff(void)
    ++{
    ++	generation_cutoff = 0;
    ++	cutoff = 0;
    ++}
    ++
    ++/* Cutoff searching any commits older than this one */
     +static void set_commit_cutoff(struct commit *commit)
     +{
    -+	timestamp_t generation;
     +
     +	if (cutoff > commit->date)
     +		cutoff = commit->date;
     +
    -+	generation = commit_graph_generation(commit);
    -+	if (generation_cutoff > generation)
    -+		generation_cutoff = generation;
    ++	if (generation_cutoff) {
    ++		timestamp_t generation = commit_graph_generation(commit);
    ++
    ++		if (generation_cutoff > generation)
    ++			generation_cutoff = generation;
    ++	}
    ++}
    ++
    ++/* adjust the commit date cutoff with a slop to allow for slightly incorrect
    ++ * commit timestamps in case of clock skew.
    ++ */
    ++static void adjust_cutoff_timestamp_for_slop(void)
    ++{
    ++	if (cutoff) {
    ++		/* check for undeflow */
    ++		if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)
    ++			cutoff = cutoff - CUTOFF_DATE_SLOP;
    ++		else
    ++			cutoff = TIME_MIN;
    ++	}
     +}
     +
     +/* Check if a commit is before the cutoff. Prioritize generation numbers
    @@ builtin/name-rev.c: struct rev_name {
     +static int commit_is_before_cutoff(struct commit *commit)
     +{
     +	if (generation_cutoff < GENERATION_NUMBER_INFINITY)
    -+		return commit_graph_generation(commit) < generation_cutoff;
    ++		return generation_cutoff &&
    ++			commit_graph_generation(commit) < generation_cutoff;
     +
     +	return commit->date < cutoff;
     +}
    @@ builtin/name-rev.c: static void name_rev(struct commit *start_commit,
      
      			if (parent_number > 1) {
     @@ builtin/name-rev.c: int cmd_name_rev(int argc, const char **argv, const char *prefix)
    - 		error("Specify either a list, or --all, not both!");
      		usage_with_options(name_rev_usage, opts);
      	}
    --	if (all || annotate_stdin)
    -+	if (all || annotate_stdin) {
    -+		generation_cutoff = 0;
    - 		cutoff = 0;
    -+	}
    + 	if (all || annotate_stdin)
    +-		cutoff = 0;
    ++		disable_cutoff();
      
      	for (; argc; argc--, argv++) {
      		struct object_id oid;
    @@ builtin/name-rev.c: int cmd_name_rev(int argc, const char **argv, const char *pr
      
      		if (peel_tag) {
      			if (!commit) {
    +@@ builtin/name-rev.c: int cmd_name_rev(int argc, const char **argv, const char *prefix)
    + 		add_object_array(object, *argv, &revs);
    + 	}
    + 
    +-	if (cutoff) {
    +-		/* check for undeflow */
    +-		if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)
    +-			cutoff = cutoff - CUTOFF_DATE_SLOP;
    +-		else
    +-			cutoff = TIME_MIN;
    +-	}
    ++	adjust_cutoff_timestamp_for_slop();
    ++
    + 	for_each_ref(name_ref, &data);
    + 	name_tips();
    + 
     
      ## t/t6120-describe.sh ##
     @@ t/t6120-describe.sh: test_expect_success 'name-rev covers all conditions while looking at parents' '
    @@ t/t6120-describe.sh: test_expect_success 'name-rev covers all conditions while l
     +	test_commit -C non-monotonic E
     +'
     +
    -+test_expect_success 'name-rev with commitGraph handles non-monotonic timestamps' '
    -+	test_config -C non-monotonic core.commitGraph true &&
    ++test_expect_success 'name-rev without commitGraph does not handle non-monotonic timestamps' '
    ++	test_config -C non-monotonic core.commitGraph false &&
     +	(
     +		cd non-monotonic &&
     +
    -+		# Ensure commit graph is up to date
    -+		git -c gc.writeCommitGraph=true gc &&
    ++		rm -rf .git/info/commit-graph* &&
     +
    -+		echo "main~3 tags/D~2" >expect &&
    ++		echo "main~3 undefined" >expect &&
     +		git name-rev --tags main~3 >actual &&
     +
     +		test_cmp expect actual
     +	)
     +'
     +
    -+test_expect_success 'name-rev --all works with non-monotonic' '
    ++test_expect_success 'name-rev --all works with non-monotonic timestamps' '
    ++	test_config -C non-monotonic core.commitGraph false &&
     +	(
     +		cd non-monotonic &&
     +
    ++		rm -rf .git/info/commit-graph* &&
    ++
    ++		cat >tags <<-\EOF &&
    ++		tags/E
    ++		tags/D
    ++		tags/D~1
    ++		tags/D~2
    ++		tags/A
    ++		EOF
    ++
    ++		git log --pretty=%H >revs &&
    ++
    ++		paste -d" " revs tags | sort >expect &&
    ++
    ++		git name-rev --tags --all | sort >actual &&
    ++		test_cmp expect actual
    ++	)
    ++'
    ++
    ++test_expect_success 'name-rev --annotate-stdin works with non-monotonic timestamps' '
    ++	test_config -C non-monotonic core.commitGraph false &&
    ++	(
    ++		cd non-monotonic &&
    ++
    ++		rm -rf .git/info/commit-graph* &&
    ++
     +		cat >expect <<-\EOF &&
     +		E
     +		D
    @@ t/t6120-describe.sh: test_expect_success 'name-rev covers all conditions while l
     +
     +		git log --pretty=%H >revs &&
     +		git name-rev --tags --annotate-stdin --name-only <revs >actual &&
    ++		test_cmp expect actual
    ++	)
    ++'
     +
    ++test_expect_success 'name-rev with commitGraph handles non-monotonic timestamps' '
    ++	test_config -C non-monotonic core.commitGraph true &&
    ++	(
    ++		cd non-monotonic &&
    ++
    ++		git commit-graph write --reachable &&
    ++
    ++		echo "main~3 tags/D~2" >expect &&
    ++		git name-rev --tags main~3 >actual &&
    ++
    ++		test_cmp expect actual
    ++	)
    ++'
    ++
    ++test_expect_success 'name-rev --all works with commitGraph' '
    ++	test_config -C non-monotonic core.commitGraph true &&
    ++	(
    ++		cd non-monotonic &&
    ++
    ++		git commit-graph write --reachable &&
    ++
    ++		cat >tags <<-\EOF &&
    ++		tags/E
    ++		tags/D
    ++		tags/D~1
    ++		tags/D~2
    ++		tags/A
    ++		EOF
    ++
    ++		git log --pretty=%H >revs &&
    ++
    ++		paste -d" " revs tags | sort >expect &&
    ++
    ++		git name-rev --tags --all | sort >actual &&
    ++		test_cmp expect actual
    ++	)
    ++'
    ++
    ++test_expect_success 'name-rev --annotate-stdin works with commitGraph' '
    ++	test_config -C non-monotonic core.commitGraph true &&
    ++	(
    ++		cd non-monotonic &&
    ++
    ++		git commit-graph write --reachable &&
    ++
    ++		cat >expect <<-\EOF &&
    ++		E
    ++		D
    ++		D~1
    ++		D~2
    ++		A
    ++		EOF
    ++
    ++		git log --pretty=%H >revs &&
    ++		git name-rev --tags --annotate-stdin --name-only <revs >actual &&
     +		test_cmp expect actual
     +	)
     +'

Jacob Keller (1):
name-rev: use generation numbers if available

 builtin/name-rev.c  |  71 +++++++++++++++++++-----
 t/t6120-describe.sh | 132 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 189 insertions(+), 14 deletions(-)
Signature · 1 line
2.35.1.355.ge7e302376dd6
#1 lore raw

PATCH 1/1 name-rev: use generation numbers if available

From: Jacob Keller <[email protected]>

If a commit in a sequence of linear history has a non-monotonically increasing commit timestamp, git name-rev might not properly name the commit.

This occurs because name-rev uses a heuristic of the commit date to avoid searching down tags which lead to commits that are older than the named commit. This is intended to avoid work on larger repositories.

This heuristic impacts git name-rev, and by extension git describe --contains which is built on top of name-rev.

Further more, if --all or --annotate-stdin is used, the heuristic is not enabled because the full history has to be analyzed anyways. This results in some confusion if a user sees that --annotate-stdin works but a normal name-rev does not.

If the repository has a commit graph, we can use the generation numbers instead of using the commit dates. This is essentially the same check except that generation numbers make it exact, where the commit date heuristic could be incorrect due to clock errors.

Since we're extending the notion of cutoff to more than one variable, create a series of functions for setting and checking the cutoff. This avoids duplication and moves access of the global cutoff and generation_cutoff to as few functions as possible.

Add several test cases including coverage of --all, --annotate-stdin, and the normal case with the cutoff heuristic, both with and without commit graphs enabled.

---
 builtin/name-rev.c  |  71 +++++++++++++++++++-----
 t/t6120-describe.sh | 132 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 189 insertions(+), 14 deletions(-)
builtin/name-rev.c +57 -14
index 929591269ddf..c59b5699fe80 100644
@@ -9,6 +9,7 @@
 #include "prio-queue.h"
 #include "hash-lookup.h"
 #include "commit-slab.h"
+#include "commit-graph.h"
 
 /*
  * One day.  See the 'name a rev shortly after epoch' test in t6120 when
@@ -26,9 +27,58 @@ struct rev_name {
 
 define_commit_slab(commit_rev_name, struct rev_name);
 
+static timestamp_t generation_cutoff = GENERATION_NUMBER_INFINITY;
 static timestamp_t cutoff = TIME_MAX;
 static struct commit_rev_name rev_names;
 
+/* Disable the cutoff checks entirely */
+static void disable_cutoff(void)
+{
+	generation_cutoff = 0;
+	cutoff = 0;
+}
+
+/* Cutoff searching any commits older than this one */
+static void set_commit_cutoff(struct commit *commit)
+{
+
+	if (cutoff > commit->date)
+		cutoff = commit->date;
+
+	if (generation_cutoff) {
+		timestamp_t generation = commit_graph_generation(commit);
+
+		if (generation_cutoff > generation)
+			generation_cutoff = generation;
+	}
+}
+
+/* adjust the commit date cutoff with a slop to allow for slightly incorrect
+ * commit timestamps in case of clock skew.
+ */
+static void adjust_cutoff_timestamp_for_slop(void)
+{
+	if (cutoff) {
+		/* check for undeflow */
+		if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)
+			cutoff = cutoff - CUTOFF_DATE_SLOP;
+		else
+			cutoff = TIME_MIN;
+	}
+}
+
+/* Check if a commit is before the cutoff. Prioritize generation numbers
+ * first, but use the commit timestamp if we lack generation data.
+ */
+static int commit_is_before_cutoff(struct commit *commit)
+{
+	if (generation_cutoff < GENERATION_NUMBER_INFINITY)
+		return generation_cutoff &&
+			commit_graph_generation(commit) < generation_cutoff;
+
+	return commit->date < cutoff;
+}
+
 /* How many generations are maximally preferred over _one_ merge traversal? */
 #define MERGE_TRAVERSAL_WEIGHT 65535
 
@@ -151,7 +201,7 @@ static void name_rev(struct commit *start_commit,
 	struct rev_name *start_name;
 
 	parse_commit(start_commit);
-	if (start_commit->date < cutoff)
+	if (commit_is_before_cutoff(start_commit))
 		return;
 
 	start_name = create_or_update_name(start_commit, taggerdate, 0, 0,
@@ -181,7 +231,7 @@ static void name_rev(struct commit *start_commit,
 			int generation, distance;
 
 			parse_commit(parent);
-			if (parent->date < cutoff)
+			if (commit_is_before_cutoff(parent))
 				continue;
 
 			if (parent_number > 1) {
@@ -568,7 +618,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 		usage_with_options(name_rev_usage, opts);
 	}
 	if (all || annotate_stdin)
-		cutoff = 0;
+		disable_cutoff();
 
 	for (; argc; argc--, argv++) {
 		struct object_id oid;
@@ -596,10 +646,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 			continue;
 		}
 
-		if (commit) {
-			if (cutoff > commit->date)
-				cutoff = commit->date;
-		}
+		if (commit)
+			set_commit_cutoff(commit);
 
 		if (peel_tag) {
 			if (!commit) {
@@ -612,13 +660,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 		add_object_array(object, *argv, &revs);
 	}
 
-	if (cutoff) {
-		/* check for undeflow */
-		if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)
-			cutoff = cutoff - CUTOFF_DATE_SLOP;
-		else
-			cutoff = TIME_MIN;
-	}
+	adjust_cutoff_timestamp_for_slop();
+
 	for_each_ref(name_ref, &data);
 	name_tips();
 
t/t6120-describe.sh +132 -0

138 lines not on this page · raw message

Signature · 1 line
2.35.1.355.ge7e302376dd6
#2 lore raw

t/t6120-describe.sh test_expect_success 'name-rev covers all conditions while looking at parents' ' · line 517

Quoted 13 lines · Jacob Keller
t/t6120-describe.sh +13 -0
+test_expect_success 'name-rev without commitGraph does not handle non-monotonic timestamps' '
+	test_config -C non-monotonic core.commitGraph false &&
+	(
+		cd non-monotonic &&
+
+		rm -rf .git/info/commit-graph* &&
+
+		echo "main~3 undefined" >expect &&
+		git name-rev --tags main~3 >actual &&
+
+		test_cmp expect actual
+	)
+'

I doubt it is wise to "test" that a program does _not_ produce a correct output, or even worse, it produces a particular wrong output. This test, for example, casts in stone that any future optimization that does not depend on the commit-graph is forever prohibited.

Just dropping the test would be fine, I would think.

#3 lore raw
Quoted 23 lines · Junio C Hamano

t/t6120-describe.sh test_expect_success 'name-rev covers all conditions while looking at parents' ' · line 517

Quoted 13 lines · Jacob Keller
t/t6120-describe.sh +13 -0
+test_expect_success 'name-rev without commitGraph does not handle non-monotonic timestamps' '
+     test_config -C non-monotonic core.commitGraph false &&
+     (
+             cd non-monotonic &&
+
+             rm -rf .git/info/commit-graph* &&
+
+             echo "main~3 undefined" >expect &&
+             git name-rev --tags main~3 >actual &&
+
+             test_cmp expect actual
+     )
+'

I doubt it is wise to "test" that a program does _not_ produce a correct output, or even worse, it produces a particular wrong output. This test, for example, casts in stone that any future optimization that does not depend on the commit-graph is forever prohibited.

Quoted 1 line

Just dropping the test would be fine, I would think.

Stolee mentioned it. We could also convert it to a "test_expect_failure" with the expected output too... But that makes it look like something we'll fix

#4 lore raw
Quoted 25 lines · Jacob Keller
Quoted 23 lines · Junio C Hamano

t/t6120-describe.sh test_expect_success 'name-rev covers all conditions while looking at parents' ' · line 517

Quoted 13 lines · Jacob Keller
t/t6120-describe.sh +13 -0
+test_expect_success 'name-rev without commitGraph does not handle non-monotonic timestamps' '
+     test_config -C non-monotonic core.commitGraph false &&
+     (
+             cd non-monotonic &&
+
+             rm -rf .git/info/commit-graph* &&
+
+             echo "main~3 undefined" >expect &&
+             git name-rev --tags main~3 >actual &&
+
+             test_cmp expect actual
+     )
+'

I doubt it is wise to "test" that a program does _not_ produce a correct output, or even worse, it produces a particular wrong output. This test, for example, casts in stone that any future optimization that does not depend on the commit-graph is forever prohibited.

Quoted 5 lines
Quoted 1 line

Just dropping the test would be fine, I would think.

Stolee mentioned it. We could also convert it to a "test_expect_failure" with the expected output too... But that makes it look like something we'll fix

I'm happy to drop this test though

Thanks,
Jake

#5 lore raw
In reply to Jacob Keller
Quoted 24 lines · Jacob Keller
Quoted 23 lines · Junio C Hamano

t/t6120-describe.sh test_expect_success 'name-rev covers all conditions while looking at parents' ' · line 517

Quoted 13 lines · Jacob Keller
t/t6120-describe.sh +13 -0
+test_expect_success 'name-rev without commitGraph does not handle non-monotonic timestamps' '
+     test_config -C non-monotonic core.commitGraph false &&
+     (
+             cd non-monotonic &&
+
+             rm -rf .git/info/commit-graph* &&
+
+             echo "main~3 undefined" >expect &&
+             git name-rev --tags main~3 >actual &&
+
+             test_cmp expect actual
+     )
+'

I doubt it is wise to "test" that a program does _not_ produce a correct output, or even worse, it produces a particular wrong output. This test, for example, casts in stone that any future optimization that does not depend on the commit-graph is forever prohibited.

Quoted 5 lines
Quoted 1 line

Just dropping the test would be fine, I would think.

Stolee mentioned it. We could also convert it to a "test_expect_failure" with the expected output too... But that makes it look like something we'll fix

Neither sounds like a good idea anyway. What we care most is with commit graph, the algorithm will not be fooled by skewed timestamps.

#6 lore raw
Quoted 26 lines · Junio C Hamano
Quoted 24 lines · Jacob Keller
Quoted 23 lines · Junio C Hamano

t/t6120-describe.sh test_expect_success 'name-rev covers all conditions while looking at parents' ' · line 517

Quoted 13 lines · Jacob Keller
t/t6120-describe.sh +13 -0
+test_expect_success 'name-rev without commitGraph does not handle non-monotonic timestamps' '
+     test_config -C non-monotonic core.commitGraph false &&
+     (
+             cd non-monotonic &&
+
+             rm -rf .git/info/commit-graph* &&
+
+             echo "main~3 undefined" >expect &&
+             git name-rev --tags main~3 >actual &&
+
+             test_cmp expect actual
+     )
+'

I doubt it is wise to "test" that a program does _not_ produce a correct output, or even worse, it produces a particular wrong output. This test, for example, casts in stone that any future optimization that does not depend on the commit-graph is forever prohibited.

Quoted 8 lines
Quoted 5 lines
Quoted 1 line

Just dropping the test would be fine, I would think.

Stolee mentioned it. We could also convert it to a "test_expect_failure" with the expected output too... But that makes it look like something we'll fix

Neither sounds like a good idea anyway. What we care most is with commit graph, the algorithm will not be fooled by skewed timestamps.

I'm fine with losing this test.

I perhaps lean too hard on "tests should document current behavior" so we know when we are changing behavior, and the commit can justify that change. For this one, we are really documenting that we have an optimization that doesn't walk all commits based on the date of the target commit. If we dropped that optimization accidentally, then we have no test so far that verifies that we don't walk the entire commit history with these name-rev queries.

If there is value in documenting that optimization, then a comment before the test could describe that the output is not desirable, but it's due to an optimization that we want to keep in place.

Thanks,
-Stolee

#7 lore raw
Quoted 38 lines · Derrick Stolee
Quoted 26 lines · Junio C Hamano
Quoted 24 lines · Jacob Keller
Quoted 23 lines · Junio C Hamano

t/t6120-describe.sh test_expect_success 'name-rev covers all conditions while looking at parents' ' · line 517

Quoted 13 lines · Jacob Keller
t/t6120-describe.sh +13 -0
+test_expect_success 'name-rev without commitGraph does not handle non-monotonic timestamps' '
+     test_config -C non-monotonic core.commitGraph false &&
+     (
+             cd non-monotonic &&
+
+             rm -rf .git/info/commit-graph* &&
+
+             echo "main~3 undefined" >expect &&
+             git name-rev --tags main~3 >actual &&
+
+             test_cmp expect actual
+     )
+'

I doubt it is wise to "test" that a program does _not_ produce a correct output, or even worse, it produces a particular wrong output. This test, for example, casts in stone that any future optimization that does not depend on the commit-graph is forever prohibited.

Quoted 8 lines
Quoted 5 lines
Quoted 1 line

Just dropping the test would be fine, I would think.

Stolee mentioned it. We could also convert it to a "test_expect_failure" with the expected output too... But that makes it look like something we'll fix

Neither sounds like a good idea anyway. What we care most is with commit graph, the algorithm will not be fooled by skewed timestamps.

I'm fine with losing this test.

Quoted 8 lines

I perhaps lean too hard on "tests should document current behavior" so we know when we are changing behavior, and the commit can justify that change. For this one, we are really documenting that we have an optimization that doesn't walk all commits based on the date of the target commit. If we dropped that optimization accidentally, then we have no test so far that verifies that we don't walk the entire commit history with these name-rev queries.

I think the "tests should document current behavior" is handled by the fact that this specific test fails if you revert the name-rev changes but keep the test.

Quoted 7 lines

If there is value in documenting that optimization, then a comment before the test could describe that the output is not desirable, but it's due to an optimization that we want to keep in place.

Thanks,
-Stolee

What about a test which uses something like the trace system to list all the commits it checked? I guess that might get a bit messy but that could be used to cover the "this optimization is important" and that applies to the commit graph implementation rather than keeping a negative test of the other implementation.

Thanks,
Jake

#8 lore raw
Quoted 48 lines · Jacob E
Quoted 38 lines · Derrick Stolee
Quoted 26 lines · Junio C Hamano
Quoted 24 lines · Jacob Keller
Quoted 23 lines · Junio C Hamano

t/t6120-describe.sh test_expect_success 'name-rev covers all conditions while looking at parents' ' · line 517

Quoted 13 lines · Jacob Keller
t/t6120-describe.sh +13 -0
+test_expect_success 'name-rev without commitGraph does not handle non-monotonic timestamps' '
+     test_config -C non-monotonic core.commitGraph false &&
+     (
+             cd non-monotonic &&
+
+             rm -rf .git/info/commit-graph* &&
+
+             echo "main~3 undefined" >expect &&
+             git name-rev --tags main~3 >actual &&
+
+             test_cmp expect actual
+     )
+'

I doubt it is wise to "test" that a program does _not_ produce a correct output, or even worse, it produces a particular wrong output. This test, for example, casts in stone that any future optimization that does not depend on the commit-graph is forever prohibited.

Quoted 8 lines
Quoted 5 lines
Quoted 1 line

Just dropping the test would be fine, I would think.

Stolee mentioned it. We could also convert it to a "test_expect_failure" with the expected output too... But that makes it look like something we'll fix

Neither sounds like a good idea anyway. What we care most is with commit graph, the algorithm will not be fooled by skewed timestamps.

I'm fine with losing this test.

Quoted 8 lines

I perhaps lean too hard on "tests should document current behavior" so we know when we are changing behavior, and the commit can justify that change. For this one, we are really documenting that we have an optimization that doesn't walk all commits based on the date of the target commit. If we dropped that optimization accidentally, then we have no test so far that verifies that we don't walk the entire commit history with these name-rev queries.

Quoted 3 lines

I think the "tests should document current behavior" is handled by the fact that this specific test fails if you revert the name-rev changes but keep the test.

Ah, so this _is_ documenting a new behavior that didn't exist before the series. That is good to include, then. If it was "just" testing the behavior before this series, then it would have less reason to exist.

Quoted 5 lines
Quoted 5 lines

If there is value in documenting that optimization, then a comment before the test could describe that the output is not desirable, but it's due to an optimization that we want to keep in place.

Quoted 8 lines
Quoted 2 lines

Thanks,
-Stolee

What about a test which uses something like the trace system to list all the commits it checked? I guess that might get a bit messy but that could be used to cover the "this optimization is important" and that applies to the commit graph implementation rather than keeping a negative test of the other implementation.

A trace of the _count_ of visited commits might be effective, without being too noisy in the trace logs or too fragile to future updates (only need to change a number if the optimization changes).

Thanks,
-Stolee

#9 lore raw
Quoted 8 lines · Derrick Stolee
Quoted 3 lines

I think the "tests should document current behavior" is handled by the fact that this specific test fails if you revert the name-rev changes but keep the test.

Ah, so this _is_ documenting a new behavior that didn't exist before the series. That is good to include, then. If it was "just" testing the behavior before this series, then it would have less reason to exist.

With of without the additional codepath to handle the case where commit graph is available, the original heuristics that is based on commit timestamps are fooled by a history with skewed timestamps.

So I thought this "without commit graph, the algorithm must fail this way" test would be testing the current behaviour *and* the behaviour of the new code, no?

#10 lore raw
Quoted 16 lines

-----Original Message-----
From: Junio C Hamano <[email protected]>
Sent: Tuesday, March 01, 2022 12:23 PM
To: Derrick Stolee <[email protected]>
Cc: Keller, Jacob E <[email protected]>; Jacob Keller <[email protected]>; Git mailing list <[email protected]>
Subject: Re: [PATCH] name-rev: use generation numbers if available

Quoted 4 lines · Derrick Stolee
Quoted 3 lines

I think the "tests should document current behavior" is handled by the fact that this specific test fails if you revert the name-rev changes but keep the test.

Quoted 9 lines
Quoted 4 lines

Ah, so this _is_ documenting a new behavior that didn't exist before the series. That is good to include, then. If it was "just" testing the behavior before this series, then it would have less reason to exist.

With of without the additional codepath to handle the case where commit graph is available, the original heuristics that is based on commit timestamps are fooled by a history with skewed timestamps.

Let's clarify. There are two versions of the test in this version:

1) test which enables commit graph and tests that it does the right behavior.

2) test which removes commit graph and tests that it behaves the old way.

test (1) checks the flow with the commit graph enabled, and verifies that with a commit graph the new behavior is used. This test will fail if you revert the name-rev commit-graph support.

test (2) always performs the way we don't like. (since we disable the commit graph and the new flow doesn't kick in) This is the test I think I will eliminate in the next revision.

I will remove the 2nd test, since the first test covers the change in behavior just fine, and I think I agree we don't need to set in-stone the implementation without commit graph.

I will also look at adding a test which performs a count of which revisions get inspected and makes sure that we actually are doing the optimization.

Quoted 3 lines

So I thought this "without commit graph, the algorithm must fail this way" test would be testing the current behaviour *and* the behaviour of the new code, no?

#11 lore raw
Quoted 12 lines · Jacob E

Let's clarify. There are two versions of the test in this version:

1) test which enables commit graph and tests that it does the right behavior.

2) test which removes commit graph and tests that it behaves the old way.

test (1) checks the flow with the commit graph enabled, and verifies that with a commit graph the new behavior is used. This test will fail if you revert the name-rev commit-graph support.

test (2) always performs the way we don't like. (since we disable the commit graph and the new flow doesn't kick in) This is the test I think I will eliminate in the next revision.

Quoted 7 lines

I will remove the 2nd test, since the first test covers the change in behavior just fine, and I think I agree we don't need to set in-stone the implementation without commit graph.

I will also look at adding a test which performs a count of which revisions get inspected and makes sure that we actually are doing the optimization.

Sounds like a sensible thing to do.

In any case, in the current patch, #2 is not working in linux-TEST-vars job at CI. You can visit this URL

https://github.com/git/git/runs/5400048732?check_suite_focus=true#step:4:68062

while logged into your GitHub account for details.

Thanks.

#12 lore raw
Quoted 23 lines · Junio C Hamano
Quoted 12 lines · Jacob E

Let's clarify. There are two versions of the test in this version:

1) test which enables commit graph and tests that it does the right behavior.

2) test which removes commit graph and tests that it behaves the old way.

test (1) checks the flow with the commit graph enabled, and verifies that with a commit graph the new behavior is used. This test will fail if you revert the name-rev commit-graph support.

test (2) always performs the way we don't like. (since we disable the commit graph and the new flow doesn't kick in) This is the test I think I will eliminate in the next revision.

Quoted 7 lines

I will remove the 2nd test, since the first test covers the change in behavior just fine, and I think I agree we don't need to set in-stone the implementation without commit graph.

I will also look at adding a test which performs a count of which revisions get inspected and makes sure that we actually are doing the optimization.

Quoted 8 lines

Sounds like a sensible thing to do.

In any case, in the current patch, #2 is not working in linux-TEST-vars job at CI. You can visit this URL

https://github.com/git/git/runs/5400048732?check_suite_focus=true#step:4:68062

while logged into your GitHub account for details.

Looks like this job sets all the TEST variables including GIT_TEST_COMMIT_GRAPH=1? The negative test passes because the commit graph is enforced on and we then succeed even though we were trying to test the negative case.

I'm going to remove that test in v3 anyways, so I don't think it is a big deal. However, I wonder is there some way to mark a test as explicitely "don't run if GIT_TEST_COMMIT_GRAPH is set"?

Thanks,
Jake

#13 lore raw
Quoted 33 lines · Jacob Keller
Quoted 23 lines · Junio C Hamano
Quoted 12 lines · Jacob E

Let's clarify. There are two versions of the test in this version:

1) test which enables commit graph and tests that it does the right behavior.

2) test which removes commit graph and tests that it behaves the old way.

test (1) checks the flow with the commit graph enabled, and verifies that with a commit graph the new behavior is used. This test will fail if you revert the name-rev commit-graph support.

test (2) always performs the way we don't like. (since we disable the commit graph and the new flow doesn't kick in) This is the test I think I will eliminate in the next revision.

Quoted 7 lines

I will remove the 2nd test, since the first test covers the change in behavior just fine, and I think I agree we don't need to set in-stone the implementation without commit graph.

I will also look at adding a test which performs a count of which revisions get inspected and makes sure that we actually are doing the optimization.

Quoted 8 lines

Sounds like a sensible thing to do.

In any case, in the current patch, #2 is not working in linux-TEST-vars job at CI. You can visit this URL

https://github.com/git/git/runs/5400048732?check_suite_focus=true#step:4:68062

while logged into your GitHub account for details.

Quoted 8 lines

Looks like this job sets all the TEST variables including GIT_TEST_COMMIT_GRAPH=1? The negative test passes because the commit graph is enforced on and we then succeed even though we were trying to test the negative case.

I'm going to remove that test in v3 anyways, so I don't think it is a big deal. However, I wonder is there some way to mark a test as explicitely "don't run if GIT_TEST_COMMIT_GRAPH is set"?

Typically, we try to keep them compatible in both cases. However, you can set GIT_TEST_COMMIT_GRAPH=0 for the test, if you want. Be careful to only change it locally to the single test, not "globally" to the full test script.

Thanks,
-Stolee

#14 lore raw
Quoted 60 lines

-----Original Message-----
From: Derrick Stolee <[email protected]>
Sent: Monday, March 07, 2022 12:27 PM
To: Jacob Keller <[email protected]>; Junio C Hamano <[email protected]>
Cc: Keller, Jacob E <[email protected]>; Git mailing list <[email protected]>
Subject: Re: [PATCH] name-rev: use generation numbers if available

Quoted 4 lines · Jacob Keller
Quoted 3 lines · Junio C Hamano

"Keller, Jacob E" <[email protected]> writes:

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

Let's clarify. There are two versions of the test in this version:

1) test which enables commit graph and tests that it does the right behavior.

2) test which removes commit graph and tests that it behaves the old way.

test (1) checks the flow with the commit graph enabled, and verifies that with

a commit graph the new behavior is used. This test will fail if you revert the name-rev commit-graph support.

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

test (2) always performs the way we don't like. (since we disable the commit

graph and the new flow doesn't kick in) This is the test I think I will eliminate in the next revision.

Quoted 10 lines
Quoted 10 lines
Quoted 9 lines

I will remove the 2nd test, since the first test covers the change in behavior just fine, and I think I agree we don't need to set in-stone the implementation without commit graph.

I will also look at adding a test which performs a count of which revisions get inspected and makes sure that we actually are doing the optimization.

Quoted 6 lines
Quoted 6 lines

Sounds like a sensible thing to do.

In any case, in the current patch, #2 is not working in linux-TEST-vars job at CI. You can visit this URL

https://github.com/git/git/runs/5400048732?check_suite_focus=true#step:4:680
62

Quoted 11 lines
Quoted 2 lines

while logged into your GitHub account for details.

Looks like this job sets all the TEST variables including GIT_TEST_COMMIT_GRAPH=1? The negative test passes because the commit graph is enforced on and we then succeed even though we were trying to test the negative case.

I'm going to remove that test in v3 anyways, so I don't think it is a big deal. However, I wonder is there some way to mark a test as explicitely "don't run if GIT_TEST_COMMIT_GRAPH is set"?

Quoted 7 lines

Typically, we try to keep them compatible in both cases. However, you can set GIT_TEST_COMMIT_GRAPH=0 for the test, if you want. Be careful to only change it locally to the single test, not "globally" to the full test script.

Thanks,
-Stolee

Ok. The problem is that specific test does not behave the same. In fact it *cannot* behave the same because we're trying to test the non-commit-graph flow there. Since i'm dropping it in v3 I won't worry too much about it.

Thanks,
Jake

#15 lore raw
Quoted 44 lines · Jacob E
Quoted 44 lines

-----Original Message-----
From: Derrick Stolee <[email protected]>
Sent: Monday, March 07, 2022 12:27 PM
To: Jacob Keller <[email protected]>; Junio C Hamano <[email protected]>
Cc: Keller, Jacob E <[email protected]>; Git mailing list <[email protected]>
Subject: Re: [PATCH] name-rev: use generation numbers if available

Quoted 7 lines · Jacob Keller
Quoted 6 lines · Junio C Hamano
Quoted 3 lines · Jacob E

I will also look at adding a test which performs a count of which revisions get inspected and makes sure that we actually are doing the optimization.

Quoted 6 lines
Quoted 6 lines

Sounds like a sensible thing to do.

In any case, in the current patch, #2 is not working in linux-TEST-vars job at CI. You can visit this URL

https://github.com/git/git/runs/5400048732?check_suite_focus=true#step:4:680
62

Quoted 11 lines
Quoted 2 lines

while logged into your GitHub account for details.

Looks like this job sets all the TEST variables including GIT_TEST_COMMIT_GRAPH=1? The negative test passes because the commit graph is enforced on and we then succeed even though we were trying to test the negative case.

I'm going to remove that test in v3 anyways, so I don't think it is a big deal. However, I wonder is there some way to mark a test as explicitely "don't run if GIT_TEST_COMMIT_GRAPH is set"?

Typically, we try to keep them compatible in both cases. However, you can set GIT_TEST_COMMIT_GRAPH=0 for the test, if you want. Be careful to only change it locally to the single test, not "globally" to the full test script.

Quoted 4 lines
Quoted 2 lines

Thanks,
-Stolee

Ok. The problem is that specific test does not behave the same. In fact it *cannot* behave the same because we're trying to test the non-commit-graph flow there. Since i'm dropping it in v3 I won't worry too much about it.

You could disable _parsing_ the commit-graph in the necessary Git command with "-c core.commitGraph=false".

Thanks,
-Stolee

#16 lore raw
In reply to Keller, Jacob E
Quoted 1 line · Jacob E

Ok. The problem is that specific test does not behave the same. In fact it *cannot* behave the same because we're trying to test the non-commit-graph flow there. Since i'm dropping it in v3 I won't worry too much about it.

As you said, if you are removing the test, it is a moot point, but I think what Derrick suggests is to do something like this:

t/t6120-describe.sh +1 -0
index c353c21cc8..871bdbbec9 100755
@@ -508,6 +508,7 @@ test_expect_success 'name-rev without commitGraph does not handle non-monotonic
 		cd non-monotonic &&
 
 		rm -rf .git/info/commit-graph* &&
+		sane_unset GIT_TEST_COMMIT_GRAPH &&
 
 		echo "main~3 undefined" >expect &&
 		git name-rev --tags main~3 >actual &&

where you want to decline using the commit-graph feature. As this test piece is already in its own subshell, the unsetting will affect only this one.

#17 lore raw

PATCH v2 1/1 name-rev: use generation numbers if available

In reply to Jacob Keller

From: Jacob Keller <[email protected]>

If a commit in a sequence of linear history has a non-monotonically increasing commit timestamp, git name-rev might not properly name the commit.

This occurs because name-rev uses a heuristic of the commit date to avoid searching down tags which lead to commits that are older than the named commit. This is intended to avoid work on larger repositories.

This heuristic impacts git name-rev, and by extension git describe --contains which is built on top of name-rev.

Further more, if --all or --annotate-stdin is used, the heuristic is not enabled because the full history has to be analyzed anyways. This results in some confusion if a user sees that --annotate-stdin works but a normal name-rev does not.

If the repository has a commit graph, we can use the generation numbers instead of using the commit dates. This is essentially the same check except that generation numbers make it exact, where the commit date heuristic could be incorrect due to clock errors.

Since we're extending the notion of cutoff to more than one variable, create a series of functions for setting and checking the cutoff. This avoids duplication and moves access of the global cutoff and generation_cutoff to as few functions as possible.

Add several test cases including coverage of --all, --annotate-stdin, and the normal case with the cutoff heuristic, both with and without commit graphs enabled.

---
Changes since v1:
* Extract all accesses to generation_cutoff and cutoff into helper functions. This way only the helper functions access the global variables

* Add several tests to cover all the behavior with and without commit graphs

* Apply Stolee's suggestion of checking generation_cutoff is zero so that we can avoid unnecessarily accessing the commit graph data.

 builtin/name-rev.c  |  71 +++++++++++++++++++-----
 t/t6120-describe.sh | 132 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 189 insertions(+), 14 deletions(-)
builtin/name-rev.c +57 -14
index 929591269ddf..c59b5699fe80 100644
@@ -9,6 +9,7 @@
 #include "prio-queue.h"
 #include "hash-lookup.h"
 #include "commit-slab.h"
+#include "commit-graph.h"
 
 /*
  * One day.  See the 'name a rev shortly after epoch' test in t6120 when
@@ -26,9 +27,58 @@ struct rev_name {
 
 define_commit_slab(commit_rev_name, struct rev_name);
 
+static timestamp_t generation_cutoff = GENERATION_NUMBER_INFINITY;
 static timestamp_t cutoff = TIME_MAX;
 static struct commit_rev_name rev_names;
 
+/* Disable the cutoff checks entirely */
+static void disable_cutoff(void)
+{
+	generation_cutoff = 0;
+	cutoff = 0;
+}
+
+/* Cutoff searching any commits older than this one */
+static void set_commit_cutoff(struct commit *commit)
+{
+
+	if (cutoff > commit->date)
+		cutoff = commit->date;
+
+	if (generation_cutoff) {
+		timestamp_t generation = commit_graph_generation(commit);
+
+		if (generation_cutoff > generation)
+			generation_cutoff = generation;
+	}
+}
+
+/* adjust the commit date cutoff with a slop to allow for slightly incorrect
+ * commit timestamps in case of clock skew.
+ */
+static void adjust_cutoff_timestamp_for_slop(void)
+{
+	if (cutoff) {
+		/* check for undeflow */
+		if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)
+			cutoff = cutoff - CUTOFF_DATE_SLOP;
+		else
+			cutoff = TIME_MIN;
+	}
+}
+
+/* Check if a commit is before the cutoff. Prioritize generation numbers
+ * first, but use the commit timestamp if we lack generation data.
+ */
+static int commit_is_before_cutoff(struct commit *commit)
+{
+	if (generation_cutoff < GENERATION_NUMBER_INFINITY)
+		return generation_cutoff &&
+			commit_graph_generation(commit) < generation_cutoff;
+
+	return commit->date < cutoff;
+}
+
 /* How many generations are maximally preferred over _one_ merge traversal? */
 #define MERGE_TRAVERSAL_WEIGHT 65535
 
@@ -151,7 +201,7 @@ static void name_rev(struct commit *start_commit,
 	struct rev_name *start_name;
 
 	parse_commit(start_commit);
-	if (start_commit->date < cutoff)
+	if (commit_is_before_cutoff(start_commit))
 		return;
 
 	start_name = create_or_update_name(start_commit, taggerdate, 0, 0,
@@ -181,7 +231,7 @@ static void name_rev(struct commit *start_commit,
 			int generation, distance;
 
 			parse_commit(parent);
-			if (parent->date < cutoff)
+			if (commit_is_before_cutoff(parent))
 				continue;
 
 			if (parent_number > 1) {
@@ -568,7 +618,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 		usage_with_options(name_rev_usage, opts);
 	}
 	if (all || annotate_stdin)
-		cutoff = 0;
+		disable_cutoff();
 
 	for (; argc; argc--, argv++) {
 		struct object_id oid;
@@ -596,10 +646,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 			continue;
 		}
 
-		if (commit) {
-			if (cutoff > commit->date)
-				cutoff = commit->date;
-		}
+		if (commit)
+			set_commit_cutoff(commit);
 
 		if (peel_tag) {
 			if (!commit) {
@@ -612,13 +660,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 		add_object_array(object, *argv, &revs);
 	}
 
-	if (cutoff) {
-		/* check for undeflow */
-		if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)
-			cutoff = cutoff - CUTOFF_DATE_SLOP;
-		else
-			cutoff = TIME_MIN;
-	}
+	adjust_cutoff_timestamp_for_slop();
+
 	for_each_ref(name_ref, &data);
 	name_tips();
 
t/t6120-describe.sh +132 -0

138 lines not on this page · raw message

Signature · 1 line
2.35.1.355.ge7e302376dd6