Re: [PATCH v2 1/3] commit-reach: add get_branch_base_for_tip

> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
>> Repositories that use pull requests (or merge requests) to advance one or
>> more "protected" branches, the history of that reference can be recovered by
>> following the first-parent history in most cases.
> 
> I cannot quite parse it, but perhaps "Repositories that" -> "In
> repositories that"?

>> Most are completed using
>> no-fast-forward merges, though squash merges are quite common. Less common
>> is rebase-and-merge, which still validates this assumption. Finally, the
>> case that breaks this assumption is the fast-forward update (with potential
>> rebasing).  Even in this case, the previous commit commonly appears in the
>> first-parent history of the branch.
> 
>> Given current command-line interface options, this optimization criteria is
>> not easy to detect directly. Even using the command
>>
>>    git rev-list --count --first-parent <base>..<source>
>>
>> does not measure this count, as it uses full reachability from <base> to
>> determine which commits to remove from the range '<base>..<source>'.
> 
> Makes me wonder if "--ancestry-path" would help.

>> The trickiest part of the integer slab is what happens when reaching a
>> collision among the histories of the bases and the history of the source.
>> This is noticed when viewing the first parent and seeing that it has a slab
>> value that differs in sign (negative or positive). In this case, the
>> collision commit is stored in the method variable 'branch_point' and its
>> slab value is set to -1. The index of the best base (so far) is stored in
>> the method variable 'best_index'. It is possible that there are multiple
>> commits that have the branch_point as its first parent, leading to multiple
>> updates of best_index.  The result is determined when 'branch_point' is
>> visited in the commit walk, giving the guarantee that all commits that could
>> reach 'branch_point' were visited.
> 
> OK.
> 
>> +/*
>> + * This slab initializes integers to zero, so use "-1" for "tip is best" and
>> + * "i + 1" for "bases[i] is best".
>> + */
>> +define_commit_slab(best_branch_base, int);
>> +static struct best_branch_base best_branch_base;
>> +#define get_best(c) (*best_branch_base_at(&best_branch_base, c))
>> +#define set_best(c,v) (*best_branch_base_at(&best_branch_base, c) = v)
> 
> Micronit.  Prepare for macro arguments to be expressions, even if
> current callers don't use anything more complex, i.e., something
> like
> 
> 	(*best_branch_base_at(&best_branch_base, (c)))
> 	(*best_branch_base_at(&best_branch_base, (c)) = (v))

>> +
>> +	/* Initialize queue and slab now that generations are guaranteed. */
>> +	init_best_branch_base(&best_branch_base);
>> +	set_best(tip, -1);
>> +	prio_queue_put(&queue, tip);
>> +
>> +	for (size_t i = 0; i < bases_nr; i++) {
>> +		struct commit *c = bases[i];
>> +
>> +		/* Has this already been marked as best by another commit? */
>> +		if (get_best(c))
>> +			continue;
> 
> Oh, so this defines the tie-breaking behaviour, but simply removing
> it is a wrong solution if we wanted our tie-breaking to work as
> "last one wins", as we still do not want to put it in the queue, so
> this "if best is already found, skip the rest" is serving dual
> purposes.  Good.