name-rev: use generation numbers if available
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
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
@@ -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
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.
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
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
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.
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 fixNeither 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
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 fixNeither 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
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 fixNeither 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,
-StoleeWhat 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
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?
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 availableQuoted 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?
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.
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
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_GRAPHis 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
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 availableQuoted 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
62Quoted 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_GRAPHis 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
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 availableQuoted 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
62Quoted 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_GRAPHis 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,
-StoleeOk. 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
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
@@ -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.
PATCH v2 1/1 name-rev: use generation numbers if available
In reply to Jacob KellerFrom: 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
@@ -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