threads / patch / 1477

patchmerge-base.c: pathological case fix.

Subject: [PATCH] merge-base.c: pathological case fix.

## tl;dr

2 messages between Aug 12, 2005 and Aug 12, 2005. Diffs are folded; open one to read it.

replies: 1people: 1as markdown or json

Junio C Hamano· Aug 12, 2005, 01:14 UTC · lore
Also add some illustration requested by Linus.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 merge-base.c |   74 +++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 68 insertions(+), 6 deletions(-)
5cbb01b3bb1828759596bff71e16cfcee798491c
Show changes to merge-base.c +68 −6
diff --git a/merge-base.c b/merge-base.c
--- a/merge-base.c
+++ b/merge-base.c
@@ -6,18 +6,82 @@
 #define PARENT2 2
 #define UNINTERESTING 4
 
-static int interesting(struct commit_list *list)
+static struct commit *interesting(struct commit_list *list)
 {
 	while (list) {
 		struct commit *commit = list->item;
 		list = list->next;
 		if (commit->object.flags & UNINTERESTING)
 			continue;
-		return 1;
+		return commit;
 	}
-	return 0;
+	return NULL;
 }
 
+/*
+ * A pathological example of how this thing works.
+ *
+ * Suppose we had this commit graph, where chronologically
+ * the timestamp on the commit are A <= B <= C <= D <= E <= F
+ * and we are trying to figure out the merge base for E and F
+ * commits.
+ *
+ *                  F
+ *                 / \
+ *            E   A   D
+ *             \ /   /  
+ *              B   /
+ *               \ /
+ *                C
+ *
+ * First we push E and F to list to be processed.  E gets bit 1
+ * and F gets bit 2.  The list becomes:
+ *
+ *     list=F(2) E(1), result=empty
+ *
+ * Then we pop F, the newest commit, from the list.  Its flag is 2.
+ * We scan its parents, mark them reachable from the side that F is
+ * reachable from, and push them to the list:
+ *
+ *     list=E(1) D(2) A(2), result=empty
+ *
+ * Next pop E and do the same.
+ *
+ *     list=D(2) B(1) A(2), result=empty
+ *
+ * Next pop D and do the same.
+ *
+ *     list=C(2) B(1) A(2), result=empty
+ *
+ * Next pop C and do the same.
+ *
+ *     list=B(1) A(2), result=empty
+ *
+ * Now it is B's turn.  We mark its parent, C, reachable from B's side,
+ * and push it to the list:
+ *
+ *     list=C(3) A(2), result=empty
+ *
+ * Now pop C and notice it has flags==3.  It is placed on the result list,
+ * and the list now contains:
+ *
+ *     list=A(2), result=C(3)
+ *
+ * We pop A and do the same.
+ * 
+ *     list=B(3), result=C(3)
+ *
+ * Next, we pop B and something very interesting happens.  It has flags==3
+ * so it is also placed on the result list, and its parents are marked
+ * uninteresting, retroactively, and placed back on the list:
+ *
+ *    list=C(7), result=C(7) B(3)
+ * 
+ * Now, list does not have any interesting commit.  So we find the newest
+ * commit from the result list that is not marked uninteresting.  Which is
+ * commit B.
+ */
+
 static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
 {
 	struct commit_list *list = NULL;
@@ -58,9 +122,7 @@ static struct commit *common_ancestor(st
 			insert_by_date(p, &list);
 		}
 	}
-	if (!result)
-		return NULL;
-	return result->item;
+	return interesting(result);
 }
 
 int main(int argc, char **argv)
Junio C Hamano· Aug 12, 2005, 05:27 UTC · re: Junio C Hamano · lore

Re: [PATCH] merge-base.c: pathological case fix.

I wrote:
Show 20 quoted lines
> + *                  F
> + *                 / \
> + *            E   A   D
> + *             \ /   /  
> + *              B   /
> + *               \ /
> + *                C
> + *
> + * First we push E and F to list to be processed.  E gets bit 1
> + * and F gets bit 2.  The list becomes:
> + * ...
> + * Next, we pop B and something very interesting happens.  It has flags==3
> + * so it is also placed on the result list, and its parents are marked
> + * uninteresting, retroactively, and placed back on the list:
> + *
> + *    list=C(7), result=C(7) B(3)
> + * 
> + * Now, list does not have any interesting commit.  So we find the newest
> + * commit from the result list that is not marked uninteresting.  Which is
> + * commit B.

I suspect we could have "list" where all commits on it is uninteresting, while "result" has an interesting commit that turns out to be reachable from one of the uninteresting commits that is still on "list", and we miss it because we give up as soon as "list" contains nothing but uninteresting ones.

I have not come up with such a pathological example, but if that is indeed the case, we would still end up terminating the well-contamination too early. I have a suspicion that no matter how we cut it we would have this horizon effect anyway, and if we want to really do the perfect job then we cannot avoid traversing to the root.

Since merge-base is aiming to be a heuristic that works well enough in practice, I think we should declare victory now and not aim for perfection, which is an enemy of the good.

← back to recent threads