{"thread":{"id":"1477","subject":"[PATCH] merge-base.c: pathological case fix.","startedAt":"2005-08-12T01:14:50Z","lastAt":"2005-08-12T05:27:51Z","messageCount":2,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"7097","messageId":"7vk6isc5x1.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1477","inReplyTo":"Pine.LNX.4.58.0508111601000.3295@g5.osdl.org","subject":"[PATCH] merge-base.c: pathological case fix.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-08-12T01:14:50Z","receivedAt":"2005-08-12T01:14:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Also add some illustration requested by Linus.\n\nSigned-off-by: Junio C Hamano \n---\n\n merge-base.c | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++++-----\n 1 files changed, 68 insertions(+), 6 deletions(-)\n\n5cbb01b3bb1828759596bff71e16cfcee798491c\ndiff --git a/merge-base.c b/merge-base.c\n--- a/merge-base.c\n+++ b/merge-base.c\n@@ -6,18 +6,82 @@\n #define PARENT2 2\n #define UNINTERESTING 4\n \n-static int interesting(struct commit_list *list)\n+static struct commit *interesting(struct commit_list *list)\n {\n \twhile (list) {\n \t\tstruct commit *commit = list->item;\n \t\tlist = list->next;\n \t\tif (commit->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n-\t\treturn 1;\n+\t\treturn commit;\n \t}\n-\treturn 0;\n+\treturn NULL;\n }\n \n+/*\n+ * A pathological example of how this thing works.\n+ *\n+ * Suppose we had this commit graph, where chronologically\n+ * the timestamp on the commit are A <= B <= C <= D <= E <= F\n+ * and we are trying to figure out the merge base for E and F\n+ * commits.\n+ *\n+ * F\n+ * / \\\n+ * E A D\n+ * \\ / / \n+ * B /\n+ * \\ /\n+ * C\n+ *\n+ * First we push E and F to list to be processed. E gets bit 1\n+ * and F gets bit 2. The list becomes:\n+ *\n+ * list=F(2) E(1), result=empty\n+ *\n+ * Then we pop F, the newest commit, from the list. Its flag is 2.\n+ * We scan its parents, mark them reachable from the side that F is\n+ * reachable from, and push them to the list:\n+ *\n+ * list=E(1) D(2) A(2), result=empty\n+ *\n+ * Next pop E and do the same.\n+ *\n+ * list=D(2) B(1) A(2), result=empty\n+ *\n+ * Next pop D and do the same.\n+ *\n+ * list=C(2) B(1) A(2), result=empty\n+ *\n+ * Next pop C and do the same.\n+ *\n+ * list=B(1) A(2), result=empty\n+ *\n+ * Now it is B's turn. We mark its parent, C, reachable from B's side,\n+ * and push it to the list:\n+ *\n+ * list=C(3) A(2), result=empty\n+ *\n+ * Now pop C and notice it has flags==3. It is placed on the result list,\n+ * and the list now contains:\n+ *\n+ * list=A(2), result=C(3)\n+ *\n+ * We pop A and do the same.\n+ * \n+ * list=B(3), result=C(3)\n+ *\n+ * Next, we pop B and something very interesting happens. It has flags==3\n+ * so it is also placed on the result list, and its parents are marked\n+ * uninteresting, retroactively, and placed back on the list:\n+ *\n+ * list=C(7), result=C(7) B(3)\n+ * \n+ * Now, list does not have any interesting commit. So we find the newest\n+ * commit from the result list that is not marked uninteresting. Which is\n+ * commit B.\n+ */\n+\n static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)\n {\n \tstruct commit_list *list = NULL;\n@@ -58,9 +122,7 @@ static struct commit *common_ancestor(st\n \t\t\tinsert_by_date(p, &list);\n \t\t}\n \t}\n-\tif (!result)\n-\t\treturn NULL;\n-\treturn result->item;\n+\treturn interesting(result);\n }\n \n int main(int argc, char **argv)\n"},{"id":"7105","messageId":"7vwtmr912g.fsf@assigned-by-dhcp.cox.net","threadId":"1477","inReplyTo":"7vk6isc5x1.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] merge-base.c: pathological case fix.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-08-12T05:27:51Z","receivedAt":"2005-08-12T05:27:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I wrote:\n\n> + * F\n> + * / \\\n> + * E A D\n> + * \\ / / \n> + * B /\n> + * \\ /\n> + * C\n> + *\n> + * First we push E and F to list to be processed. E gets bit 1\n> + * and F gets bit 2. The list becomes:\n> + * ...\n> + * Next, we pop B and something very interesting happens. It has flags==3\n> + * so it is also placed on the result list, and its parents are marked\n> + * uninteresting, retroactively, and placed back on the list:\n> + *\n> + * list=C(7), result=C(7) B(3)\n> + * \n> + * Now, list does not have any interesting commit. So we find the newest\n> + * commit from the result list that is not marked uninteresting. Which is\n> + * commit B.\n\nI suspect we could have \"list\" where all commits on it is\nuninteresting, while \"result\" has an interesting commit that\nturns out to be reachable from one of the uninteresting commits\nthat is still on \"list\", and we miss it because we give up as\nsoon as \"list\" contains nothing but uninteresting ones.\n\nI have not come up with such a pathological example, but if that\nis indeed the case, we would still end up terminating the\nwell-contamination too early. I have a suspicion that no matter\nhow we cut it we would have this horizon effect anyway, and if\nwe want to really do the perfect job then we cannot avoid\ntraversing to the root.\n\nSince merge-base is aiming to be a heuristic that works well\nenough in practice, I think we should declare victory now and\nnot aim for perfection, which is an enemy of the good.\n"}]}