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

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

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

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

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

> +	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);
> +	}

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

> +		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);