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

["Keller, Jacob E" <jacob.e.keller@intel.com>]

On 2/15/2022 6:48 AM, Derrick Stolee wrote:
> 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.
> 

Right. A closer look at the name-rev algorithm seems to be that it
starts looking at each tag and scanning down history to see if it can
find the given commit. It uses the commit timestamp as a heuristic to
decide whether or not to stop looking. This can speed up the search
because it prevents scanning the entire history.. but it breaks when
that heuristic is no longer true such as in the particular setup like
mine with a funky timestamp.


>> 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.
> 

Right. Using generation number would work for this I think.. The real
question being if it satisfies the other requirements.

I think it does, but I'm not 100% sure yet.

> 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