{"thread":{"id":"48538","subject":"commit-graph: change in \"best\" merge-base when ambiguous","startedAt":"2018-05-21T18:10:59Z","lastAt":"2018-05-25T06:03:52Z","messageCount":10,"participants":["Derrick Stolee","Elijah Newren","Jeff King","Jacob Keller","Stefan Beller","Michael Haggerty","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"348228","messageId":"e78a115a-a5ea-3c0a-5437-51ba0bcc56e1@gmail.com","threadId":"48538","inReplyTo":null,"subject":"commit-graph: change in \"best\" merge-base when ambiguous","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-05-21T18:10:54Z","receivedAt":"2018-05-21T18:10:59Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Hello all,\n\nWhile working on the commit-graph feature, I made a test commit that \nsets core.commitGraph and gc.commitGraph to true by default AND runs \n'git commit-graph write --reachable' after each 'git commit' command. \nThis helped me find instances in the test suite where the commit-graph \nfeature changes existing functionality. Most of these were in regards to \ngrafts, replace-objects, and shallow-clones (as expected) or when trying \nto find a corrupt or hidden commit (the commit-graph hides this \ncorrupt/missing data). However, there was one interesting case that I'd \nlike to mention on-list.\n\nIn t6024-recursive-merge.sh, we have the following commit structure:\n\n     # 1 - A - D - F\n     #   \\   X   /\n     #     B   X\n     #       X   \\\n     # 2 - C - E - G\n\nWhen merging F to G, there are two \"best\" merge-bases, A and C. With \ncore.commitGraph=false, 'git merge-base F G' returns A, while it returns \nC when core.commitGraph=true. This is due to the new walk order when \nusing generation numbers, although I have not dug deep into the code to \npoint out exactly where the choice between A and C is made. Likely it's \njust whatever order they are inserted into a list.\n\nIn the Discussion section of the `git merge-base` docs [1], we have the \nfollowing:\n\n     When the history involves criss-cross merges, there can be more \nthan one best common ancestor for two commits. For example, with this \ntopology:\n\n     ---1---o---A\n         \\ /\n          X\n         / \\\n     ---2---o---o---B\n\n     both 1 and 2 are merge-bases of A and B. Neither one is better than \nthe other (both are best merge bases). When the --all option is not \ngiven,     it is unspecified which best one is output.\n\nThis means our official documentation mentions that we do not have a \nconcrete way to differentiate between these choices. This makes me think \nthat this change in behavior is not a bug, but it _is_ a change in \nbehavior. It's worth mentioning, but I don't think there is any value in \nmaking sure `git merge-base` returns the same output.\n\nDoes anyone disagree? Is this something we should solidify so we always \nhave a \"definitive\" merge-base?\n\nThe biggest reason I think we should avoid sticking to the existing \nbehavior is that the current behavior depends on the walk order. That \nmeans we would not be able to concretely define a tie-breaker without \nchanging the existing behavior anyway.\n\nThanks,\n-Stolee\n\n[1] https://git-scm.com/docs/git-merge-base#_discussion\n\n"},{"id":"348235","messageId":"CABPp-BFEd+fK_i3qoYWudYS5mhWE1jsXR_xcSCZoJ=4Vd61LAQ@mail.gmail.com","threadId":"48538","inReplyTo":"e78a115a-a5ea-3c0a-5437-51ba0bcc56e1@gmail.com","subject":"Re: commit-graph: change in \"best\" merge-base when ambiguous","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2018-05-21T18:33:11Z","receivedAt":"2018-05-21T18:33:16Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi,\n\nOn Mon, May 21, 2018 at 11:10 AM, Derrick Stolee <stolee@gmail.com> wrote:\n> Hello all,\n>\n> While working on the commit-graph feature, I made a test commit that sets\n> core.commitGraph and gc.commitGraph to true by default AND runs 'git\n> commit-graph write --reachable' after each 'git commit' command. This helped\n> me find instances in the test suite where the commit-graph feature changes\n> existing functionality. Most of these were in regards to grafts,\n> replace-objects, and shallow-clones (as expected) or when trying to find a\n> corrupt or hidden commit (the commit-graph hides this corrupt/missing data).\n> However, there was one interesting case that I'd like to mention on-list.\n>\n> In t6024-recursive-merge.sh, we have the following commit structure:\n>\n>     # 1 - A - D - F\n>     #   \\   X   /\n>     #     B   X\n>     #       X   \\\n>     # 2 - C - E - G\n>\n> When merging F to G, there are two \"best\" merge-bases, A and C. With\n> core.commitGraph=false, 'git merge-base F G' returns A, while it returns C\n> when core.commitGraph=true. This is due to the new walk order when using\n> generation numbers, although I have not dug deep into the code to point out\n> exactly where the choice between A and C is made. Likely it's just whatever\n> order they are inserted into a list.\n\nOoh, interesting.\n\nJust a guess, but could it be related to relative ordering of\ncommitter timestamps?  Ordering of committer timestamps apparently\naffects order of merge-bases returned to merge-recursive, and although\nthat shouldn't have mattered, a few bugs meant that it did and the\norder ended up determining what contents a successful merge would\nhave.  See this recent post:\n\nhttps://public-inbox.org/git/CABPp-BFc1OLYKzS5rauOehvEugPc0oGMJp-NMEAmVMW7QR=4Eg@mail.gmail.com/\n\nThe fact that the merge was successful for both orderings of merge\nbases was the real bug, though; it should have detected and reported a\nconflict both ways.\n\n\nI'm not sure where else we have an accidental and incorrect dependence\non merge-base tie-breaker or ordering logic, but if it's like this\none, changing the tie-breaker should be okay.\n"},{"id":"348252","messageId":"20180521215046.GA16623@sigill.intra.peff.net","threadId":"48538","inReplyTo":"CABPp-BFEd+fK_i3qoYWudYS5mhWE1jsXR_xcSCZoJ=4Vd61LAQ@mail.gmail.com","subject":"Re: commit-graph: change in \"best\" merge-base when ambiguous","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-21T21:50:46Z","receivedAt":"2018-05-21T21:50:52Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 21, 2018 at 11:33:11AM -0700, Elijah Newren wrote:\n\n> > In t6024-recursive-merge.sh, we have the following commit structure:\n> >\n> >     # 1 - A - D - F\n> >     #   \\   X   /\n> >     #     B   X\n> >     #       X   \\\n> >     # 2 - C - E - G\n> >\n> > When merging F to G, there are two \"best\" merge-bases, A and C. With\n> > core.commitGraph=false, 'git merge-base F G' returns A, while it returns C\n> > when core.commitGraph=true. This is due to the new walk order when using\n> > generation numbers, although I have not dug deep into the code to point out\n> > exactly where the choice between A and C is made. Likely it's just whatever\n> > order they are inserted into a list.\n>\n> Ooh, interesting.\n> \n> Just a guess, but could it be related to relative ordering of\n> committer timestamps?  Ordering of committer timestamps apparently\n> affects order of merge-bases returned to merge-recursive, and although\n> that shouldn't have mattered, a few bugs meant that it did and the\n> order ended up determining what contents a successful merge would\n> have.  See this recent post:\n> \n> https://public-inbox.org/git/CABPp-BFc1OLYKzS5rauOehvEugPc0oGMJp-NMEAmVMW7QR=4Eg@mail.gmail.com/\n> \n> The fact that the merge was successful for both orderings of merge\n> bases was the real bug, though; it should have detected and reported a\n> conflict both ways.\n\nTraditionally we've inserted commits into the walk queue in commit-date\nordering, but with identical dates it may depend on the order in which\nyou reach the commits. Many of the tests are particularly bad for\nshowing this off because they do not use test_tick, and so you end up\nwith a bunch of commits with identical timestamps.\n\nIf we're just using generation numbers for queue ordering, we're even\nmore likely to hit these cases, since they're expected to increase along\nparallel branches at roughly the same rate. It's probably a good idea to\nhave some tie-breakers to make things more deterministic (walk order\nshouldn't matter, but it can be confusing if we sometimes use one order\nand sometimes the other).\n\nEven ordering by {generation, timestamp} isn't quite enough, since you\ncould still tie there. Perhaps {generation, timestamp, hash} would be a\nsensible ordering?\n\nAs for this specific case, even with the current code asking for `git\nmerge-base G F` will return the other answer. This is clearly a case\nwith multiple merge bases, and I'd expect \"merge-base --all\" to return\nboth (and actually it shows \"B\" as well, which makes sense). In the\nnon-all case, there is no \"best\", so we're free to show any.\n\n-Peff\n"},{"id":"348254","messageId":"20180521215443.GC16623@sigill.intra.peff.net","threadId":"48538","inReplyTo":"e78a115a-a5ea-3c0a-5437-51ba0bcc56e1@gmail.com","subject":"Re: commit-graph: change in \"best\" merge-base when ambiguous","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-21T21:54:43Z","receivedAt":"2018-05-21T21:54:54Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 21, 2018 at 02:10:54PM -0400, Derrick Stolee wrote:\n\n> In the Discussion section of the `git merge-base` docs [1], we have the\n> following:\n> \n>     When the history involves criss-cross merges, there can be more than one\n> best common ancestor for two commits. For example, with this topology:\n> \n>     ---1---o---A\n>         \\ /\n>          X\n>         / \\\n>     ---2---o---o---B\n> \n>     both 1 and 2 are merge-bases of A and B. Neither one is better than the\n> other (both are best merge bases). When the --all option is not given,    \n> it is unspecified which best one is output.\n> \n> This means our official documentation mentions that we do not have a\n> concrete way to differentiate between these choices. This makes me think\n> that this change in behavior is not a bug, but it _is_ a change in behavior.\n> It's worth mentioning, but I don't think there is any value in making sure\n> `git merge-base` returns the same output.\n> \n> Does anyone disagree? Is this something we should solidify so we always have\n> a \"definitive\" merge-base?\n\nHeh, I should have read your whole original message before responding,\nnot just the part that Elijah quoted.\n\nYes, I think this is clearly a case where all of the single merge-bases\nwe could show are equally good. And I don't think we should promise to\nshow a particular one, but I _do_ think it's friendly for us to have\ndeterministic tie-breakers (we certainly don't now).\n\n-Peff\n"},{"id":"348258","messageId":"CA+P7+xpC6bSy0wJhmgT=UMev2AdDz0LVG11Ok7Y5j0Fsr-s08Q@mail.gmail.com","threadId":"48538","inReplyTo":"20180521215443.GC16623@sigill.intra.peff.net","subject":"Re: commit-graph: change in \"best\" merge-base when ambiguous","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2018-05-21T22:25:40Z","receivedAt":"2018-05-21T22:26:22Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Mon, May 21, 2018 at 2:54 PM, Jeff King <peff@peff.net> wrote:\n> Yes, I think this is clearly a case where all of the single merge-bases\n> we could show are equally good. And I don't think we should promise to\n> show a particular one, but I _do_ think it's friendly for us to have\n> deterministic tie-breakers (we certainly don't now).\n>\n> -Peff\n\nRight. I think we should probably have some mechanism that will allow\nus to always give the same answer, even if it's somewhat arbitrary.\n\nRegards,\nJake\n"},{"id":"348259","messageId":"CAGZ79kb_eUas+7MtSm3KDyY=3sB4h=Z422nTyWaOoh4=UN72zA@mail.gmail.com","threadId":"48538","inReplyTo":"20180521215046.GA16623@sigill.intra.peff.net","subject":"Re: commit-graph: change in \"best\" merge-base when ambiguous","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-05-21T22:28:30Z","receivedAt":"2018-05-21T22:28:38Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, May 21, 2018 at 2:50 PM, Jeff King <peff@peff.net> wrote:\n> On Mon, May 21, 2018 at 11:33:11AM -0700, Elijah Newren wrote:\n>\n>> > In t6024-recursive-merge.sh, we have the following commit structure:\n>> >\n>> >     # 1 - A - D - F\n>> >     #   \\   X   /\n>> >     #     B   X\n>> >     #       X   \\\n>> >     # 2 - C - E - G\n>> >\n>> > When merging F to G, there are two \"best\" merge-bases, A and C. With\n>> > core.commitGraph=false, 'git merge-base F G' returns A, while it returns C\n>> > when core.commitGraph=true. This is due to the new walk order when using\n>> > generation numbers, although I have not dug deep into the code to point out\n>> > exactly where the choice between A and C is made. Likely it's just whatever\n>> > order they are inserted into a list.\n>>\n>> Ooh, interesting.\n>>\n>> Just a guess, but could it be related to relative ordering of\n>> committer timestamps?  Ordering of committer timestamps apparently\n>> affects order of merge-bases returned to merge-recursive, and although\n>> that shouldn't have mattered, a few bugs meant that it did and the\n>> order ended up determining what contents a successful merge would\n>> have.  See this recent post:\n>>\n>> https://public-inbox.org/git/CABPp-BFc1OLYKzS5rauOehvEugPc0oGMJp-NMEAmVMW7QR=4Eg@mail.gmail.com/\n>>\n>> The fact that the merge was successful for both orderings of merge\n>> bases was the real bug, though; it should have detected and reported a\n>> conflict both ways.\n>\n> Traditionally we've inserted commits into the walk queue in commit-date\n> ordering, but with identical dates it may depend on the order in which\n> you reach the commits. Many of the tests are particularly bad for\n> showing this off because they do not use test_tick, and so you end up\n> with a bunch of commits with identical timestamps.\n>\n> If we're just using generation numbers for queue ordering, we're even\n> more likely to hit these cases, since they're expected to increase along\n> parallel branches at roughly the same rate. It's probably a good idea to\n> have some tie-breakers to make things more deterministic (walk order\n> shouldn't matter, but it can be confusing if we sometimes use one order\n> and sometimes the other).\n>\n> Even ordering by {generation, timestamp} isn't quite enough, since you\n> could still tie there. Perhaps {generation, timestamp, hash} would be a\n> sensible ordering?\n\nThe hash sounds reasonable as the definite tie breaker.\n\ngit merge-base is documented as \"Find as good common ancestors\nas possible for a merge\", so in case we do not require the tie\nbreaking to be cheap, we could go by \"smallest diff output\"\nof the two diffs against the potential merge commit.\n\nThough I don't think this is really optimal for performance reasons.\n"},{"id":"348283","messageId":"3705af00-00b7-b620-cc77-eef8f0a73bc1@alum.mit.edu","threadId":"48538","inReplyTo":"e78a115a-a5ea-3c0a-5437-51ba0bcc56e1@gmail.com","subject":"Re: commit-graph: change in \"best\" merge-base when ambiguous","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-05-22T05:39:19Z","receivedAt":"2018-05-22T05:39:30Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/21/2018 08:10 PM, Derrick Stolee wrote:\n> [...]\n> In the Discussion section of the `git merge-base` docs [1], we have the\n> following:\n> \n>     When the history involves criss-cross merges, there can be more than\n> one best common ancestor for two commits. For example, with this topology:\n> \n>     ---1---o---A\n>         \\ /\n>          X\n>         / \\\n>     ---2---o---o---B\n> \n>     both 1 and 2 are merge-bases of A and B. Neither one is better than\n> the other (both are best merge bases). When the --all option is not\n> given,     it is unspecified which best one is output.\n> \n> This means our official documentation mentions that we do not have a\n> concrete way to differentiate between these choices. This makes me think\n> that this change in behavior is not a bug, but it _is_ a change in\n> behavior. It's worth mentioning, but I don't think there is any value in\n> making sure `git merge-base` returns the same output.\n> \n> Does anyone disagree? Is this something we should solidify so we always\n> have a \"definitive\" merge-base?\n> [...]\n\nThis may be beyond the scope of what you are working on, but there are\nsignificant advantages to selecting a \"best\" merge base from among the\ncandidates. Long ago [1] I proposed that the \"best\" merge base is the\nmerge base candidate that minimizes the number of non-merge commits that\nare in\n\n    git rev-list $candidate..$branch\n\nthat are already in master:\n\n    git rev-list $master\n\n(assuming merging branch into master), which is equivalent to choosing\nthe merge base that minimizes\n\n    git rev-list --count $candidate..$branch\n\nIn fact, this criterion is symmetric if you exchange branch ↔ master,\nwhich is a nice property, and indeed generalizes pretty simply to\ncomputing the merge base of more than two commits.\n\nIn that email I also included some data showing that the \"best\" merge\nbase almost always results in either the same or a shorter diff than the\nmore or less arbitrary algorithm that we currently use. Sometimes the\ndifference in diff length is dramatic.\n\nTo me it feels like the best *deterministic* merge base would be based\non the above criterion, maybe with first-parent reachability, commit\ntimes, and SHA-1s used (in that order) to break ties.\n\nI don't plan to work on the implementation of this idea myself (though\nwe've long used a script-based implementation of this algorithm\ninternally at GitHub).\n\nMichael\n\n[1] https://public-inbox.org/git/539A25BF.4060501@alum.mit.edu/\n    See the rest of the thread for more interesting discussion.\n[2]\nhttps://public-inbox.org/git/8a9b3f20-eed2-c59b-f7ea-3c68b3c30bf5@alum.mit.edu/\n    Higher in this thread, Junio proposes a different criterion.\n"},{"id":"348298","messageId":"8b480e9e-1fd3-35ff-2974-653fadd49fa7@gmail.com","threadId":"48538","inReplyTo":"3705af00-00b7-b620-cc77-eef8f0a73bc1@alum.mit.edu","subject":"Re: commit-graph: change in \"best\" merge-base when ambiguous","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-05-22T12:48:04Z","receivedAt":"2018-05-22T12:48:11Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/22/2018 1:39 AM, Michael Haggerty wrote:\n> On 05/21/2018 08:10 PM, Derrick Stolee wrote:\n>> [...]\n>> In the Discussion section of the `git merge-base` docs [1], we have the\n>> following:\n>>\n>>      When the history involves criss-cross merges, there can be more than\n>> one best common ancestor for two commits. For example, with this topology:\n>>\n>>      ---1---o---A\n>>          \\ /\n>>           X\n>>          / \\\n>>      ---2---o---o---B\n>>\n>>      both 1 and 2 are merge-bases of A and B. Neither one is better than\n>> the other (both are best merge bases). When the --all option is not\n>> given,     it is unspecified which best one is output.\n>>\n>> This means our official documentation mentions that we do not have a\n>> concrete way to differentiate between these choices. This makes me think\n>> that this change in behavior is not a bug, but it _is_ a change in\n>> behavior. It's worth mentioning, but I don't think there is any value in\n>> making sure `git merge-base` returns the same output.\n>>\n>> Does anyone disagree? Is this something we should solidify so we always\n>> have a \"definitive\" merge-base?\n>> [...]\n> This may be beyond the scope of what you are working on, but there are\n> significant advantages to selecting a \"best\" merge base from among the\n> candidates. Long ago [1] I proposed that the \"best\" merge base is the\n> merge base candidate that minimizes the number of non-merge commits that\n> are in\n>\n>      git rev-list $candidate..$branch\n>\n> that are already in master:\n>\n>      git rev-list $master\n>\n> (assuming merging branch into master), which is equivalent to choosing\n> the merge base that minimizes\n>\n>      git rev-list --count $candidate..$branch\n>\n> In fact, this criterion is symmetric if you exchange branch ↔ master,\n> which is a nice property, and indeed generalizes pretty simply to\n> computing the merge base of more than two commits.\n>\n> In that email I also included some data showing that the \"best\" merge\n> base almost always results in either the same or a shorter diff than the\n> more or less arbitrary algorithm that we currently use. Sometimes the\n> difference in diff length is dramatic.\n>\n> To me it feels like the best *deterministic* merge base would be based\n> on the above criterion, maybe with first-parent reachability, commit\n> times, and SHA-1s used (in that order) to break ties.\n\nThanks, everyone, for your perspective on this. I'm walking away with \nthese conclusions:\n\n1. While this is a change in behavior, it is not a regression. We do not \nneed to act immediately to preserve old behavior in these ambiguous cases.\n\n2. We should (eventually) define tie-breaking conditions. I like \nMichael's suggestion above.\n\nThanks,\n-Stolee\n"},{"id":"348493","messageId":"86o9h41zc3.fsf@gmail.com","threadId":"48538","inReplyTo":"8b480e9e-1fd3-35ff-2974-653fadd49fa7@gmail.com","subject":"Re: commit-graph: change in \"best\" merge-base when ambiguous","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-05-24T22:08:28Z","receivedAt":"2018-05-24T22:08:39Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n> On 5/22/2018 1:39 AM, Michael Haggerty wrote:\n>> On 05/21/2018 08:10 PM, Derrick Stolee wrote:\n>>> [...]\n>>> In the Discussion section of the `git merge-base` docs [1], we have the\n>>> following:\n>>>\n>>>      When the history involves criss-cross merges, there can be more than\n>>> one best common ancestor for two commits. For example, with this topology:\n>>>\n>>>      ---1---o---A\n>>>          \\ /\n>>>           X\n>>>          / \\\n>>>      ---2---o---o---B\n>>>\n>>>      both 1 and 2 are merge-bases of A and B. Neither one is better than\n>>> the other (both are best merge bases). When the --all option is not\n>>> given, it is unspecified which best one is output.\n>>>\n>>> This means our official documentation mentions that we do not have a\n>>> concrete way to differentiate between these choices. This makes me think\n>>> that this change in behavior is not a bug, but it _is_ a change in\n>>> behavior. It's worth mentioning, but I don't think there is any value in\n>>> making sure `git merge-base` returns the same output.\n>>>\n>>> Does anyone disagree? Is this something we should solidify so we always\n>>> have a \"definitive\" merge-base?\n>>> [...]\n>> This may be beyond the scope of what you are working on, but there are\n>> significant advantages to selecting a \"best\" merge base from among the\n>> candidates. Long ago [1] I proposed that the \"best\" merge base is the\n>> merge base candidate that minimizes the number of non-merge commits that\n>> are in\n>>\n>>      git rev-list $candidate..$branch\n>>\n>> that are already in master:\n>>\n>>      git rev-list $master\n>>\n>> (assuming merging branch into master), which is equivalent to choosing\n>> the merge base that minimizes\n>>\n>>      git rev-list --count $candidate..$branch\n\nIs the above correct...\n\n>> In fact, this criterion is symmetric if you exchange branch ↔ master,\n>> which is a nice property, and indeed generalizes pretty simply to\n>> computing the merge base of more than two commits.\n\n...as it doesn't seem to have the described symmetry.\n\n>>\n>> In that email I also included some data showing that the \"best\" merge\n>> base almost always results in either the same or a shorter diff than the\n>> more or less arbitrary algorithm that we currently use. Sometimes the\n>> difference in diff length is dramatic.\n>>\n>> To me it feels like the best *deterministic* merge base would be based\n>> on the above criterion, maybe with first-parent reachability, commit\n>> times, and SHA-1s used (in that order) to break ties.\n>\n> Thanks, everyone, for your perspective on this. I'm walking away with\n> these conclusions:\n>\n> 1. While this is a change in behavior, it is not a regression. We do\n> not need to act immediately to preserve old behavior in these\n> ambiguous cases.\n>\n> 2. We should (eventually) define tie-breaking conditions. I like\n> Michael's suggestion above.\n\nOne thing I'd like to point out is that when searching for some\nalgorithm to speed up merge-base calculation (which is called lowest\ncommon ancestor in graph theory, and for which I have currently found\nonly an algorithm with O(|V|*{E|) preparation time, and U(1) query)\nI have found instead attempts to rigorously define single representative\nlowest common ancestor.  It might be worth a look how it is done.\n\nAnother possible source to compare against is the algorithm used by\nMercurial (which as far as I know doesn't use recursive merge strategy,\nso it needs to chose one merge base).\n\nHTH,\n-- \nJakub Narębski\n"},{"id":"348517","messageId":"1fb58851-57bc-b787-fd38-474aa6afa8b3@alum.mit.edu","threadId":"48538","inReplyTo":"86o9h41zc3.fsf@gmail.com","subject":"Re: commit-graph: change in \"best\" merge-base when ambiguous","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-05-25T06:03:43Z","receivedAt":"2018-05-25T06:03:52Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/25/2018 12:08 AM, Jakub Narebski wrote:\n> Derrick Stolee <stolee@gmail.com> writes:\n>> On 5/22/2018 1:39 AM, Michael Haggerty wrote:\n>>> On 05/21/2018 08:10 PM, Derrick Stolee wrote:\n>>>> [...]\n>>> This may be beyond the scope of what you are working on, but there are\n>>> significant advantages to selecting a \"best\" merge base from among the\n>>> candidates. Long ago [1] I proposed that the \"best\" merge base is the\n>>> merge base candidate that minimizes the number of non-merge commits that\n>>> are in\n>>>\n>>>      git rev-list $candidate..$branch\n>>>\n>>> that are already in master:\n>>>\n>>>      git rev-list $master\n>>>\n>>> (assuming merging branch into master), which is equivalent to choosing\n>>> the merge base that minimizes\n>>>\n>>>      git rev-list --count $candidate..$branch\n> \n> Is the above correct...\n> \n>>> In fact, this criterion is symmetric if you exchange branch ↔ master,\n>>> which is a nice property, and indeed generalizes pretty simply to\n>>> computing the merge base of more than two commits.\n> \n> ...as it doesn't seem to have the described symmetry.\n\nThe first email that I referenced [1] demonstrates this in the section\n\"Symmetry; generalization to more than two branches\". The same thing is\ndemonstrated in a simpler way using set notation in a later email in\nthat thread [2].\n\nMichael\n\n[1] https://public-inbox.org/git/539A25BF.4060501@alum.mit.edu/\n[2] https://public-inbox.org/git/53A06264.9080205@alum.mit.edu/\n"}]}