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

[Junio C Hamano <gitster@pobox.com>]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Derrick Stolee <stolee@gmail.com>
>
> Add a new reachability algorithm that intends to discover (from a heuristic)
> which branch was used as the starting point for a given commit. Add focused
> tests using the 'test-tool reach' command.
>
> 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))

> +	if (found_missing_gen) {
> +		struct commit **commits;
> +		size_t commits_nr = bases_nr + 1;
> +
> +		CALLOC_ARRAY(commits, commits_nr);
> +		COPY_ARRAY(commits, bases, bases_nr);
> +		commits[bases_nr] = tip;
> +		ensure_generations_valid(r, commits, commits_nr);
> +		free(commits);
> +	}

It would have been very unfortunate if this copying were done only
because commits and tip are not in the same array, but the called
function mutates the given array of commits so we cannot avoid
passing a copy anyway.  Given these constraints, this is the
cleanest implementation, probably.

> +
> +	/* 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.

> +		set_best(c, i + 1);
> +		prio_queue_put(&queue, c);
> +	}
> +
> +	while (queue.nr) {
> +		struct commit *c = prio_queue_get(&queue);
> +		int best_for_c = get_best(c);
> +		int best_for_p, positive;
> +		struct commit *parent;
> +
> +		/* Have we reached a known branch point? It's optimal. */
> +		if (c == branch_point)
> +			break;
> +
> +		repo_parse_commit(r, c);
> +		if (!c->parents)
> +			continue;
> +
> +		parent = c->parents->item;
> +		repo_parse_commit(r, parent);
> +		best_for_p = get_best(parent);
> +
> +		if (!best_for_p) {
> +			/* 'parent' is new, so pass along best_for_c. */
> +			set_best(parent, best_for_c);
> +			prio_queue_put(&queue, parent);
> +			continue;
> +		}
> +
> +		if (best_for_p > 0 && best_for_c > 0) {
> +			/* Collision among bases. Minimize. */
> +			if (best_for_c < best_for_p)
> +				set_best(parent, best_for_c);
> +			continue;
> +		}
> +
> +		/*
> +		 * At this point, we have reached a commit that is reachable
> +		 * from the tip, either from 'c' or from an earlier commit to
> +		 * have 'parent' as its first parent.
> +		 *
> +		 * Update 'best_index' to match the minimum of all base indices
> +		 * to reach 'parent'.
> +		 */
> +
> +		/* Exactly one is positive due to initial conditions. */
> +		positive = (best_for_c < 0) ? best_for_p : best_for_c;
> +
> +		if (best_index < 0 || positive < best_index)
> +			best_index = positive;
> +
> +		/* No matter what, track that the parent is reachable from tip. */
> +		set_best(parent, -1);
> +		branch_point = parent;
> +	}
> +
> +	clear_best_branch_base(&best_branch_base);
> +	clear_prio_queue(&queue);

OK.  We get rid of the slab and prio-queue once we are done.
Nice.

Thanks.