@@ -1222,3 +1222,129 @@ done:
free(commits);
repo_clear_commit_marks(r, SEEN);
}
+
+/*
+ * 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))
+
+int get_branch_base_for_tip(struct repository *r,
+ struct commit *tip,
+ struct commit **bases,
+ size_t bases_nr)
+{
+ int best_index = -1;
+ struct commit *branch_point = NULL;
+ struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
+ int found_missing_gen = 0;
+
+ if (!bases_nr)
+ return -1;
+
+ repo_parse_commit(r, tip);
+ if (commit_graph_generation(tip) == GENERATION_NUMBER_INFINITY)
+ found_missing_gen = 1;
+
+ /* Check for missing generation numbers. */
+ for (size_t i = 0; i < bases_nr; i++) {
+ struct commit *c = bases[i];
+ repo_parse_commit(r, c);
+ if (commit_graph_generation(c) == GENERATION_NUMBER_INFINITY)
+ found_missing_gen = 1;
+ }
+
+ 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];
+ int best = get_best(c);
+
+ /* Has this already been marked as best by another commit? */
+ if (best) {
+ if (best == -1) {
+ /* We agree at this position. Stop now. */
+ best_index = i + 1;
+ goto cleanup;
+ }
+ 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;
+ }
+
+cleanup:
+ clear_best_branch_base(&best_branch_base);
+ clear_prio_queue(&queue);
+ return best_index > 0 ? best_index - 1 : -1;
+}
@@ -139,4 +139,21 @@ void tips_reachable_from_bases(struct repository *r,
struct commit **tips, size_t tips_nr,
int mark);
+/*
+ * Given a 'tip' commit and a list potential 'bases', return the index 'i' that
+ * minimizes the number of commits in the first-parent history of 'tip' and not
+ * in the first-parent history of 'bases[i]'.
+ *
+ * Among a list of long-lived branches that are updated only by merges (with the
+ * first parent being the previous position of the branch), this would inform
+ * which branch was used to create the tip reference.
+ *
+ * Returns -1 if no common point is found in first-parent histories, which is
+ * rare, but possible with multiple root commits.
+ */
+int get_branch_base_for_tip(struct repository *r,
+ struct commit *tip,
+ struct commit **bases,
+ size_t bases_nr);
+
#endif
@@ -114,6 +114,8 @@ int cmd__reach(int ac, const char **av)
repo_in_merge_bases_many(the_repository, A, X_nr, X_array, 0));
else if (!strcmp(av[1], "is_descendant_of"))
printf("%s(A,X):%d\n", av[1], repo_is_descendant_of(r, A, X));
+ else if (!strcmp(av[1], "get_branch_base_for_tip"))
+ printf("%s(A,X):%d\n", av[1], get_branch_base_for_tip(r, A, X_array, X_nr));
else if (!strcmp(av[1], "get_merge_bases_many")) {
struct commit_list *list = NULL;
if (repo_get_merge_bases_many(the_repository,
@@ -612,4 +612,65 @@ test_expect_success 'for-each-ref merged:none' '
--format="%(refname)" --stdin
'
+# For get_branch_base_for_tip, we only care about
+# first-parent history. Here is the test graph with
+# second parents removed:
+#
+# (10,10)
+# /
+# (10,9) (9,10)
+# / /
+# (10,8) (9,9) (8,10)
+# / / /
+# ( continued...)
+# \ / / /
+# (3,1) (2,2) (1,3)
+# \ / /
+# (2,1) (1,2)
+# \ /
+# (1,1)
+#
+# In short, for a commit (i,j), the first-parent history
+# walks all commits (i, k) with k from j to 1, then the
+# commits (l, 1) with l from i to 1.
+
+test_expect_success 'get_branch_base_for_tip: none reach' '
+ # (2,3) branched from the first tip (i,4) in X with i > 2
+ cat >input <<-\EOF &&
+ A:commit-2-3
+ X:commit-1-2
+ X:commit-1-4
+ X:commit-4-4
+ X:commit-8-4
+ X:commit-10-4
+ EOF
+ echo "get_branch_base_for_tip(A,X):2" >expect &&
+ test_all_modes get_branch_base_for_tip
+'
+
+test_expect_success 'get_branch_base_for_tip: equal to tip' '
+ # (2,3) branched from the first tip (i,4) in X with i > 2
+ cat >input <<-\EOF &&
+ A:commit-8-4
+ X:commit-1-2
+ X:commit-1-4
+ X:commit-4-4
+ X:commit-8-4
+ X:commit-10-4
+ EOF
+ echo "get_branch_base_for_tip(A,X):3" >expect &&
+ test_all_modes get_branch_base_for_tip
+'
+
+test_expect_success 'get_branch_base_for_tip: all reach tip' '
+ # (2,3) branched from the first tip (i,4) in X with i > 2
+ cat >input <<-\EOF &&
+ A:commit-4-1
+ X:commit-4-2
+ X:commit-5-1
+ EOF
+ echo "get_branch_base_for_tip(A,X):0" >expect &&
+ test_all_modes get_branch_base_for_tip
+'
+
test_done