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

> 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