On Tue, 23 Aug 2005, Junio C Hamano wrote:
>
> Only lightly tested, in the sense that I did only this one case
> and nothing else. For a large repository and with complex
> merges, "merge-base -a" _might_ end up reporting many
> candidates, in which case the pre-merge step to figure out the
> best merge base may turn out to be disastrously slow. I dunno.
Ok, I think your approach is the correct one. Just list all the commits,
and let the merge logic figure out which one is the best one.
Here, in case anybody cares, is an alternate approach, which sucks. It
_happens_ to pick the right parent in this case, but when I look at why it
picks it, it's pretty much just pure luck again. The distance function is
not good.
Just returning several entries is the correct thing to do, because then
you can make the distance function be based on the tree diffs, like you
do. That's _much_ better than trying to make the distance be based on some
topology.
So I append this patch just as a historical curiosity. Junio's patch is
clearly superior.
Linus
---
diff --git a/merge-base.c b/merge-base.c
--- a/merge-base.c
+++ b/merge-base.c
@@ -82,10 +82,84 @@ static struct commit *interesting(struct
* commit B.
*/
+/*
+ * Count the distance from one commit to the base, using a very
+ * stupid recursive algorithm. We only avoid recursion when seeing
+ * a single parent.
+ */
+static unsigned long count_distance(struct commit *head, struct commit *base)
+{
+ struct commit_list *parents;
+ unsigned long distance = ULONG_MAX;
+ unsigned long chain = 1;
+
+ /* Walk the chain of direct parents */
+ for (;;) {
+ parents = head->parents;
+ if (!parents)
+ goto no_parent;
+ /* Multiple parents? */
+ if (parents->next)
+ break;
+ head = parents->item;
+ if (head == base)
+ return chain;
+ chain++;
+ }
+
+ while (parents) {
+ struct commit *c = parents->item;
+ unsigned long d;
+
+ parents = parents->next;
+ if (c == base)
+ return chain;
+ if (c->object.flags & UNINTERESTING)
+ continue;
+ d = count_distance(c, base);
+ if (d < distance)
+ distance = d;
+ }
+ if (distance != ULONG_MAX)
+ return distance + chain;
+no_parent:
+ return ULONG_MAX;
+}
+
+/*
+ * There are some really nasty cases where we get multiple apparently
+ * equally valid parents, and we need to disambiguate them.
+ *
+ * We aim for the one whose total distance to the two revisions is the
+ * smallest, where distance is "x**2 + y**2" (we _much_ prefer a nice
+ * balanced equidistant one over one that is near to one but far from
+ * the other)
+ */
+static struct commit *pick_best_commit(struct commit_list *list, struct commit
*rev1, struct commit *rev2)
+{
+ unsigned long distance = ULONG_MAX;
+ struct commit *best = NULL;
+
+ do {
+ struct commit *base = list->item;
+ unsigned long d1 = count_distance(rev1, base);
+ unsigned long d2 = count_distance(rev2, base);
+ unsigned long d = d1*d1 + d2*d2;
+
+fprintf(stderr, "distance analysis: %s: %lu %lu %lu\n",
sha1_to_hex(base->object.sha1), d1, d2, d);
+ if (d < distance) {
+ distance = d;
+ best = base;
+ }
+ } while ((list = list->next) != NULL);
+ return best;
+}
+
static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
{
struct commit_list *list = NULL;
struct commit_list *result = NULL;
+ struct commit_list *final = NULL;
if (rev1 == rev2)
return rev1;
@@ -122,7 +196,32 @@ static struct commit *common_ancestor(st
insert_by_date(p, &list);
}
}
- return interesting(result);
+
+ /*
+ * Go through the result list, and pick out unique
+ * members to put on the final list.
+ */
+ while (result) {
+ struct commit_list *entry = result;
+ struct commit *c = result->item;
+ result = result->next;
+ if (c->object.flags & UNINTERESTING)
+ continue;
+ if (c == rev1 || c == rev2)
+ return c;
+ entry->next = final;
+ final = entry;
+ c->object.flags |= UNINTERESTING;
+ }
+
+ if (!final)
+ return NULL;
+
+ /* Just one entry? */
+ if (!final->next)
+ return final->item;
+
+ return pick_best_commit(final, rev1, rev2);
}
int main(int argc, char **argv)
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
