Re: [PATCH] name-rev: test showing failure with non-monotonic commit dates

[Derrick Stolee <derrickstolee@github.com>]

On 2/14/2022 5:07 PM, Jacob Keller wrote:
> On Mon, Feb 14, 2022 at 1:50 PM Junio C Hamano <gitster@pobox.com> wrote:
>>
>> Jacob Keller <jacob.e.keller@intel.com> writes:
>>
>>> From: Jacob Keller <jacob.keller@gmail.com>
>>>
>>> If a commit in a sequence of linear history has a non-monotonically
>>> increasing commit timestamp, git name-rev will not properly name the
>>> commit.
>>>
>>> However, if you use --annotate-stdin then the commit does actually get
>>> picked up and named properly.
>>
>> IIRC, this is to be expected.
>>
> 
> Right. I figured this is somehow expected behavior...
> 
>> When preparing to answer --annotate-stdin request, the command has
>> to dig down to the root of the history, which would be too expensive
>> in some repositories and wants to stop traversal early when it knows
>> particular commits it needs to describe.
>>
> 
> And this method of cutting the search relies on monotonic commit times right?
> 
> Is there any other method we could use (commit graph?) or perhaps to
> add an option so that you could go "git name-rev --no-cutoff <commid
> id>"? That would potentially allow working around this particular
> problem on repositories where its known to be problematic.

I initially thought that generation numbers could help. The usual way
is to use a priority queue that explores by generation, not commit
date. This approach was immediately stifled by these lines:

	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
	prio_queue_put(&queue, start_commit);

So the queue is really a stack.
 
> Alternatively is there some other way to apply the cutoff heuristic
> only in some cases? I get the sense this is intended to allow cutting
> off merged branches? i.e. not applying it when history is linear? I'd
> have to study it further but the existing algorithm seems to break
> because as it goes up the history it has found an "older" commit, so
> it stops trying to blame that line...?

It is still possible that the cutoff could be altered to use generation
numbers instead of commit dates, but I haven't looked closely enough to
be sure.

Here is a very basic attempt. With GIT_TEST_COMMIT_GRAPH=1, your
test_expect_failure turns into a success.

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 138e3c30a2b..f7ad1dd8b4d 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -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
@@ -27,6 +28,7 @@ struct rev_name {
 define_commit_slab(commit_rev_name, struct rev_name);
 
 static timestamp_t cutoff = TIME_MAX;
+static timestamp_t generation_cutoff = 0;
 static struct commit_rev_name rev_names;
 
 /* How many generations are maximally preferred over _one_ merge traversal? */
@@ -151,7 +153,10 @@ static void name_rev(struct commit *start_commit,
 	struct rev_name *start_name;
 
 	parse_commit(start_commit);
-	if (start_commit->date < cutoff)
+	if (generation_cutoff && generation_cutoff < GENERATION_NUMBER_INFINITY) {
+		if (commit_graph_generation(start_commit) < generation_cutoff)
+			return;
+	} else if (start_commit->date < cutoff)
 		return;
 
 	start_name = create_or_update_name(start_commit, taggerdate, 0, 0,
@@ -599,6 +604,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 		if (commit) {
 			if (cutoff > commit->date)
 				cutoff = commit->date;
+			if (generation_cutoff > commit_graph_generation(commit))
+				generation_cutoff = commit_graph_generation(commit);
 		}
 
 		if (peel_tag) {

Thanks,
-Stolee