{"thread":{"id":"4159","subject":"[PATCH] Update the documentation for git-merge-base","startedAt":"2006-05-16T05:58:15Z","lastAt":"2006-05-16T23:20:59Z","messageCount":7,"participants":["Fredrik Kuivinen","Junio C Hamano","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"20046","messageId":"20060516055815.GA4572@c165.ib.student.liu.se","threadId":"4159","inReplyTo":null,"subject":"[PATCH] Update the documentation for git-merge-base","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2006-05-16T05:58:15Z","receivedAt":"2006-05-16T05:58:15Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"\nSigned-off-by: Fredrik Kuivinen \n\n---\n\nIs the code guaranteed to return a least common ancestor? If that is\nthe case we should probably mention it in the documentation.\n\n\n Documentation/git-merge-base.txt | 18 ++++++++++++++----\n 1 files changed, 14 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt\nindex d1d56f1..6099be2 100644\n--- a/Documentation/git-merge-base.txt\n+++ b/Documentation/git-merge-base.txt\n@@ -8,16 +8,26 @@ git-merge-base - Finds as good a common \n \n SYNOPSIS\n --------\n-'git-merge-base' \n+'git-merge-base' [--all] \n \n DESCRIPTION\n -----------\n-\"git-merge-base\" finds as good a common ancestor as possible. Given a\n-selection of equally good common ancestors it should not be relied on\n-to decide in any particular way.\n+\n+\"git-merge-base\" finds as good a common ancestor as possible between\n+the two commits. That is, given two commits A and B 'git-merge-base A\n+B' will output a commit which is reachable from both A and B through\n+the parent relationship.\n+\n+Given a selection of equally good common ancestors it should not be\n+relied on to decide in any particular way.\n \n The \"git-merge-base\" algorithm is still in flux - use the source...\n \n+OPTIONS\n+-------\n+--all::\n+\tOutput all common ancestors for the two commits instead of\n+\tjust one.\n \n Author\n ------\n"},{"id":"20047","messageId":"7vhd3qebuv.fsf@assigned-by-dhcp.cox.net","threadId":"4159","inReplyTo":"20060516055815.GA4572@c165.ib.student.liu.se","subject":"Re: [PATCH] Update the documentation for git-merge-base","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-16T06:13:12Z","receivedAt":"2006-05-16T06:13:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> Is the code guaranteed to return a least common ancestor? If that is\n> the case we should probably mention it in the documentation.\n\nUnfortunately, no, if you mean by \"least common\" closest to the\ntips.\n\nSee the big illustration at the top of the source for how you\ncan construct pathological case to defeat an attempt to\nguarantee such. --all guarantees that the output contains all\ninteresting ones, but does not guarantee the output has no\nsuboptimal merge bases.\n"},{"id":"20051","messageId":"20060516065452.GA5540@c165.ib.student.liu.se","threadId":"4159","inReplyTo":"7vhd3qebuv.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Update the documentation for git-merge-base","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2006-05-16T06:54:52Z","receivedAt":"2006-05-16T06:54:52Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Mon, May 15, 2006 at 11:13:12PM -0700, Junio C Hamano wrote:\n> Fredrik Kuivinen writes:\n> \n> > Is the code guaranteed to return a least common ancestor? If that is\n> > the case we should probably mention it in the documentation.\n> \n> Unfortunately, no, if you mean by \"least common\" closest to the\n> tips.\n>\n\nBy \"least\" I mean the following:\n\nC is a least common ancestor of A and B if:\n\n* C is a common ancestor of A and B, and\n* for every other common ancestor D (different from C) of A and B, C\n is not reacheable from D.\n\n> See the big illustration at the top of the source for how you\n> can construct pathological case to defeat an attempt to\n> guarantee such. --all guarantees that the output contains all\n> interesting ones, but does not guarantee the output has no\n> suboptimal merge bases.\n\nThere are two examples at the top of the source. In the first one a\nleast common ancestor is returned. As I interpret the second one, it\nis an example of how the old algorithm without the postprocessing step\nproduced a common ancestor which is not least.\n\nAm I wrong? Do we have any cases where the current merge-base\nalgorithm gives us common ancestors which are not least?\n\n- Fredrik\n"},{"id":"20055","messageId":"7vu07qcsqk.fsf@assigned-by-dhcp.cox.net","threadId":"4159","inReplyTo":"20060516065452.GA5540@c165.ib.student.liu.se","subject":"Re: [PATCH] Update the documentation for git-merge-base","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-16T07:51:31Z","receivedAt":"2006-05-16T07:51:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n>> See the big illustration at the top of the source for how you\n>> can construct pathological case to defeat an attempt to\n>> guarantee such. --all guarantees that the output contains all\n>> interesting ones, but does not guarantee the output has no\n>> suboptimal merge bases.\n>\n> There are two examples at the top of the source. In the first one a\n> least common ancestor is returned. As I interpret the second one, it\n> is an example of how the old algorithm without the postprocessing step\n> produced a common ancestor which is not least.\n\nAh, yes, I remember now.\n\nThe drawing was done while we were working on the solution to\nthat pathological case; mark_reachable_commits() solves that\nhorizon effect.\n\n http://article.gmane.org/gmane.comp.version-control.git/11410\n http://article.gmane.org/gmane.comp.version-control.git/11429\n http://article.gmane.org/gmane.comp.version-control.git/11552\n http://article.gmane.org/gmane.comp.version-control.git/11613\n\nHowever, our inability to come up with one is not a nonexistence\nproof of cases the current algorithm can fail, so math minded\npeople _might_ want to prove the algorithm is optimal.\n\nNot me, though.\n"},{"id":"20068","messageId":"Pine.LNX.4.64.0605160821570.3866@g5.osdl.org","threadId":"4159","inReplyTo":"20060516065452.GA5540@c165.ib.student.liu.se","subject":"Re: [PATCH] Update the documentation for git-merge-base","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-16T15:32:42Z","receivedAt":"2006-05-16T15:32:42Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 16 May 2006, Fredrik Kuivinen wrote:\n> \n> By \"least\" I mean the following:\n> \n> C is a least common ancestor of A and B if:\n> \n> * C is a common ancestor of A and B, and\n> * for every other common ancestor D (different from C) of A and B, C\n> is not reacheable from D.\n\nYes, git-merge-base should always return a least common ancestor, never \nanything less. The only question is what happens when there are multiple \nLCA commits.\n\nIn fact, even in that case git-merge-base will have a pretty strong \nspecification:\n\n \"git-merge-base with the '--all' flag will return the complete set of\n least common ancestors, sorted by most recent (as defined purely by\n the commit date order, not any graph ordering) first.\n\n Without the '--all' flag, it will return just one LCA commit (the most \n recent one, by the same date-based definition).\n\n In the case two or more LCA commits have exactly the same committer \n date, the ordering between them is arbitrary\"\n\nI don't think you can be more specific, or do a better job. The definition \nof \"most recent\" is arbitrary, of course - and going by commit date is \njust _one_ way to order them, but it happens to be an easy one, and one \nthat is as good as any other choice.\n\nOf course, the defined ordering probably really matters only for the case \nwhere we return just one LCA out of many, but it's nice to be able to tell \nwhat the order will be even for the multi-commit case.\n\n> There are two examples at the top of the source. In the first one a\n> least common ancestor is returned. As I interpret the second one, it\n> is an example of how the old algorithm without the postprocessing step\n> produced a common ancestor which is not least.\n\nCorrect. We used to occasionally get it wrong, and return a common \nancestor that wasn't least.\n\n> Am I wrong? Do we have any cases where the current merge-base\n> algorithm gives us common ancestors which are not least?\n\nModulo bugs, no. And I don't think there are any bugs in that respect.\n\n\t\tLinus\n"},{"id":"20069","messageId":"Pine.LNX.4.64.0605160906150.3866@g5.osdl.org","threadId":"4159","inReplyTo":"Pine.LNX.4.64.0605160821570.3866@g5.osdl.org","subject":"Re: [PATCH] Update the documentation for git-merge-base","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-16T16:32:12Z","receivedAt":"2006-05-16T16:32:12Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 16 May 2006, Linus Torvalds wrote:\n> \n> I don't think you can be more specific, or do a better job. The definition \n> of \"most recent\" is arbitrary, of course - and going by commit date is \n> just _one_ way to order them, but it happens to be an easy one, and one \n> that is as good as any other choice.\n\nSide note: since LCA's are (by definition) never going to have a direct \ngraph relationship, there is obviously no ordering enforced by the graph \nitself. So they're all unordered in the graph sense, but you could use \nother measures of \"distance\" in the graph.\n\nExample other orderings that we _could_ do, and I considered (some purely \ngraph based, others based on content):\n\n - order by number of commits between the LCA and the two commits that we \n are trying to find the LCA for (the \"tips\").\n - order by diff size between the LCA and the tips\n - order by lack of conflicts between the LCA and the tips.\n\nhowever, none of the alternate orderings really seem to make a lot of \nsense.\n\nThe date-based one trumps them all by being straightforward and simple to \nboth implement and explain. And iirc, I actually verified that it happened \nto pick the \"better\" one for at least one of my tests when using the old \nstupid straigth three-way merge, so I think it was actually objectively a \ngood measure at least once.\n\nAnybody who cares can obviously always just do \"git-merge-base --all\" and \ndo their own sorting for the (relatively unlikely) case that you get more \nthan one parent.\n\nAnyway, just out of interest I just did some statistics using some shell \nscripts:\n\n - For the current kernel tree, of 1857 merges, only 17 had more than one \n merge base (and none had more than two):\n\n 1840 o\n 17 oo\n\n - In contrast, for git (current master branch), the numbers are 35 out of \n 540, and there are lots of merges with many LCA's:\n\n 505 o\n 15 oo\n 13 ooo\n 2 oooo\n 3 ooooo\n 2 ooooooo\n\nI think the difference is that Junio does a lot of these branches where he \nkeeps on pulling from them, and never syncs back (which is a great \nworkflow). In contrast, the kernel tends to try to avoid that because the \nhistory gets messy enough as it is ;)\n\nAnyway, the two commits that apparently have seven (!) LCA's in the git \ntree should probably be checked out. They are probably a good thing to see \nif git-merge-base really _really_ does the right thing, and whether they \nreally are true LCA's.\n\nThey are commits ad0b46bf.. and e6a933bd.. respectively.\n\n\t\tLinus\n"},{"id":"20091","messageId":"7vbqtx4kv8.fsf@assigned-by-dhcp.cox.net","threadId":"4159","inReplyTo":"Pine.LNX.4.64.0605160906150.3866@g5.osdl.org","subject":"Re: [PATCH] Update the documentation for git-merge-base","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-16T23:20:59Z","receivedAt":"2006-05-16T23:20:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> - In contrast, for git (current master branch), the numbers are 35 out of \n> 540, and there are lots of merges with many LCA's:\n>\n> 505 o\n> 15 oo\n> 13 ooo\n> 2 oooo\n> 3 ooooo\n> 2 ooooooo\n>\n> I think the difference is that Junio does a lot of these branches where he \n> keeps on pulling from them, and never syncs back (which is a great \n> workflow). In contrast, the kernel tends to try to avoid that because the \n> history gets messy enough as it is ;)\n>\n> Anyway, the two commits that apparently have seven (!) LCA's in the git \n> tree should probably be checked out. They are probably a good thing to see \n> if git-merge-base really _really_ does the right thing, and whether they \n> really are true LCA's.\n>\n> They are commits ad0b46bf.. and e6a933bd.. respectively.\n\nThe first one is because at 1.3.0 I pulled everything from\n\"next\" to \"master\".\n\nUsually \"next\" incorporates topic branches that stem from\ndifferent commits on \"master\", and when a new topic is merged to\n\"next\", it gets the updates to \"master\" up to that point along\nwith the new topic. When topics graduate (i.e. merged back) to\n\"master\", they do so at different pace.\n\n\n topic2 o---o---o---o---H---.\n / \\ \\\n next -----------o---o---E---o---I-------B\n / / / \\ \\\n topic1 / / o---D---. \\ \\\n / / / \\ \\ \\\n master ---G---o---C---o---o---F---o---o---A---X\n\nThe above illustration shows that two topics branched from\nmaster were cooked in next. Topic 1 branched from master at C,\nadded two commits (its tip is at D), merged to next at E and\nthen later merged to master at F. Similarly, topic 2 branched\nfrom master at G, added five commits (its tip is at H), merged\nto next at I and then later merged to master at A.\n\nWhen merging \"next\" into \"master\" by merging A and B to produce\nX, tips of topics 1 and 2 (D and H, respectively) become the\nmerge base.\n\nMerging \"next\" wholesale to \"master\" is hopefully a rare event,\nbut the seven bases you are seeing are the topic tips.\n\nThe other one is the other way around. From time to time,\n\"next\" itself gets updates from \"master\" to keep it in sync with\nfixes that occurred on \"master\" directly. Such a merge into\n\"next\" will have this picture but the principles are the same.\n\n topic2 o---o---o---o---H---.\n / \\ \\\n next -----------o---o---E---o---I-------B---Y\n / / / \\ /\n topic1 / / o---D---. \\ /\n / / / \\ \\ /\n master ---G---o---C---o---o---F---o---o---A\n"}]}