Re: [PATCH v5 2/4] format-patch: add '--base' option to record base tree info

Xiaolong Ye [off-list ref] writes:

+static struct commit *get_base_commit(const char *base_commit,
+				      struct commit **list,
+				      int total)
+{
+	struct commit *base = NULL;
+	struct commit **rev;
+	int i = 0, rev_nr = 0;
+
+	base = lookup_commit_reference_by_name(base_commit);
+	if (!base)
+		die(_("Unknown commit %s"), base_commit);
+
+	ALLOC_ARRAY(rev, total);
+	for (i = 0; i < total; i++)
+		rev[i] = list[i];
+
+	rev_nr = total;
+	/*
+	 * Get merge base through pair-wise computations
+	 * and store it in rev[0].
+	 */
+	while (rev_nr > 1) {
+		for (i = 0; i < rev_nr / 2; i++) {
+			struct commit_list *merge_base;
+			merge_base = get_merge_bases(rev[2 * i], rev[2 * i + 1]);
+			if (!merge_base || merge_base->next)
+				die(_("Failed to find exact merge base"));
+
+			rev[i] = merge_base->item;
+		}

So merge-base(0,1) is stored in rev[0], merge-base(2,3) is then
stored in rev[1], etc. and the last item, if rev_nr is odd, is left
in rev[rev_nr-1].  When the loop finishes, i is left as rev_nr/2
and...

+		if (rev_nr % 2)
+			rev[i] = rev[2 * i];

... when rev_nr is odd, that left-over thing moved down here.
E.g. if rev_nr == 5, the loop is left with i==2, rev[0] and rev[1]
are filled with pairwise merge bases, and this moves rev[4] to
rev[2], so that we can further process rev[0,1,2] with rev_nr set to
3 (i.e. (rev_nr + 1) / 2 below).

Sounds correct.

+		rev_nr = (rev_nr + 1) / 2;
+	}
+
+	if (!in_merge_bases(base, rev[0]))
+		die(_("base commit should be the ancestor of revision list"));
+
+	for (i = 0; i < total; i++) {
+		if (base == list[i])
+			die(_("base commit shouldn't be in revision list"));
+	}
+
+	free(rev);
+	return base;
+}