Skip to contentSkip to conversation

name-rev: use generation numbers if available

PATCH Superseded Jacob Keller 2 participants 4 messages Mar 10, 2022

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

PATCH v3 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 a test that covers the new commitGraph behavior, as well as tests for --all and --annotate-stdin with and without commitGraphs.

---
Changes since v2:
* Removed negative test with commit graph disabled

I wanted to add a test that counted number of revisions walked, but I couldn't figure out if we had a method to get this data out using GIT_TRACE or GIT_TRACE2...

 builtin/name-rev.c  |  71 +++++++++++++++++++++------
 t/t6120-describe.sh | 116 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 173 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 +116 -0

122 lines not on this page · raw message

base-commit: c2162907e9aa884bdb70208389cb99b181620d51

Signature · 1 line
2.35.1.355.ge7e302376dd6
#1 lore raw
Quoted 6 lines · Jacob Keller
t/t6120-describe.sh +6 -0
+# A-B-C-D-E-main
+#
+# Where C has a non-monotonically increasing commit timestamp w.r.t. other
+# commits
+test_expect_success 'non-monotonic commit dates setup' '
+	UNIX_EPOCH_ZERO="@0 +0000" &&

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

Quoted 10 lines
t/t6120-describe.sh +10 -0
+	git init non-monotonic &&
+	test_commit -C non-monotonic A &&
+	test_commit -C non-monotonic --no-tag B &&
+	test_commit -C non-monotonic --no-tag --date "$UNIX_EPOCH_ZERO" C &&
+	test_commit -C non-monotonic D &&
+	test_commit -C non-monotonic E
+'
+
+test_expect_success 'name-rev with commitGraph handles non-monotonic timestamps' '
+	test_config -C non-monotonic core.commitGraph false &&

Don't you mean "true" here?

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

Quoted 9 lines
t/t6120-describe.sh +9 -0
+	(
+		cd non-monotonic &&
+
+		echo "main~3 tags/D~2" >expect &&
+		git name-rev --tags main~3 >actual &&
+
+		test_cmp expect actual
+	)
+'

Other than that there wasn't anything unexpected in this iteration.

Thanks.

#2 lore raw
Quoted 28 lines

-----Original Message-----
From: Junio C Hamano <[email protected]>
Sent: Wednesday, March 09, 2022 4:33 PM
To: Keller, Jacob E <[email protected]>
Cc: [email protected]; Jacob Keller <[email protected]>
Subject: Re: [PATCH v3] name-rev: use generation numbers if available

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

Quoted 10 lines · Jacob Keller
t/t6120-describe.sh +10 -0
+# A-B-C-D-E-main
+#
+# Where C has a non-monotonically increasing commit timestamp w.r.t. other
+# commits
+test_expect_success 'non-monotonic commit dates setup' '
+	UNIX_EPOCH_ZERO="@0 +0000" &&
+	git init non-monotonic &&
+	test_commit -C non-monotonic A &&
+	test_commit -C non-monotonic --no-tag B &&
+	test_commit -C non-monotonic --no-tag --date "$UNIX_EPOCH_ZERO" C

&&

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

Quoted 5 lines
t/t6120-describe.sh +5 -0
+	test_commit -C non-monotonic D &&
+	test_commit -C non-monotonic E
+'
+
+test_expect_success 'name-rev with commitGraph handles non-monotonic

timestamps' '

Quoted 4 lines

Review

Quoted 1 line
(quoted diff) +1 -0
+	test_config -C non-monotonic core.commitGraph false &&

Don't you mean "true" here?

Yep. Will fix.

Quoted 13 lines

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

Quoted 9 lines
t/t6120-describe.sh +9 -0
+	(
+		cd non-monotonic &&
+
+		echo "main~3 tags/D~2" >expect &&
+		git name-rev --tags main~3 >actual &&
+
+		test_cmp expect actual
+	)
+'

Other than that there wasn't anything unexpected in this iteration.

Thanks.

#3 lore raw
In reply to Junio C Hamano
Quoted 5 lines · Junio C Hamano

Review

Quoted 2 lines
(quoted diff) +2 -0
+test_expect_success 'name-rev with commitGraph handles non-monotonic timestamps' '
+	test_config -C non-monotonic core.commitGraph false &&

Don't you mean "true" here?

Quoted 9 lines

Review

Quoted 9 lines
(quoted diff) +9 -0
+	(
+		cd non-monotonic &&
+
+		echo "main~3 tags/D~2" >expect &&
+		git name-rev --tags main~3 >actual &&
+
+		test_cmp expect actual
+	)
+'

And I am not sure if there is anybody _writing_ the graph file in the first place, so perhaps squash this in?

 t/t6120-describe.sh | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
t/t6120-describe.sh +3 -1
index 0b18f73779..9a35e783a7 100755
@@ -503,10 +503,12 @@ test_expect_success 'non-monotonic commit dates setup' '
 '
 
 test_expect_success 'name-rev with commitGraph handles non-monotonic timestamps' '
-	test_config -C non-monotonic core.commitGraph false &&
+	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 &&
 
Signature · 1 line
2.35.1-744-g1f8f0331bc