{"thread":{"id":"32048","subject":"git merge commits are non-deterministic? what changed?","startedAt":"2012-11-09T13:31:32Z","lastAt":"2012-11-20T20:39:13Z","messageCount":9,"participants":["Ulrich Spörlein","Andreas Schwab","Matthieu Moy","Jeff King","Michael J Gruber","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"202696","messageId":"20121109133132.GK69724@acme.spoerlein.net","threadId":"32048","inReplyTo":null,"subject":"git merge commits are non-deterministic? what changed?","fromName":"Ulrich Spörlein","fromEmail":"uqs@spoerlein.net","sentAt":"2012-11-09T13:31:32Z","receivedAt":"2012-11-09T13:31:32Z","isPatch":false,"sender":{"key":"uqs@spoerlein.net","avatar":null},"body":"Hi all,\n\nI'm running a couple of conversions from SVN to git, using a slightly\nhacked version of svn2git (because it can cope with multiple branches\nand is several orders of magnitude faster than git-svn).\n\nAnyway, when doing some verification runs, using the same version of\nsvn2git, but different versions of git, I get different commit hashes,\nand I tracked it down to the ordering of the parents inside a merge\ncommit.\n\nversion 1.7.9.2\n% git show --format=raw e209a83|head\ncommit e209a83c1e0a387c88a44f3a8f2be2670ed85eae\ntree de2d7c6726a45428d4a310da2acd8839daf9f85f\nparent 5fba0401c23a594e4ad5e807bf14a5439645a358\nparent 25062ba061871945759b3baa833fe64969383e40\nparent 89bebeef185ed08424fc548f8569081c6add2439\nparent c7d5f60d3a7e2e3c4da23b157c62504667344438\nparent e7bc108f0d6a394050818a4af64a59094d3c793e\nparent 48231afadc40013e6bfda56b04a11ee3a602598f\nauthor rgrimes <rgrimes@FreeBSD.org> 739897097 +0000\ncommitter rgrimes <rgrimes@FreeBSD.org> 739897097 +0000\n\nvs\n\ngit version 1.8.0\n% git show --format=raw 42f0fad|head\ncommit 42f0fadccab6eefc7ffdc1012345b42ad45e36c2\ntree de2d7c6726a45428d4a310da2acd8839daf9f85f\nparent 5fba0401c23a594e4ad5e807bf14a5439645a358\nparent 25062ba061871945759b3baa833fe64969383e40\nparent 89bebeef185ed08424fc548f8569081c6add2439\nparent 48231afadc40013e6bfda56b04a11ee3a602598f\nparent c7d5f60d3a7e2e3c4da23b157c62504667344438\nparent e7bc108f0d6a394050818a4af64a59094d3c793e\nauthor rgrimes <rgrimes@FreeBSD.org> 739897097 +0000\ncommitter rgrimes <rgrimes@FreeBSD.org> 739897097 +0000\n\nI haven't verified to see if that ordering is stable within a git\nversion, but the fact that it changed across versions clearly means that\nI cannot depend on this currently (I have never seen this problem in two\nyears, so I blame git 1.8.0 ...)\n\nTwo questions:\n1. Can we impose a stable ordering of the commits being recorded in a\nmerge commit? Listing parents in chronological order or something like\nthat.\n\n2. Why the hell is the commit hash dependent on the ordering of the\nparent commits? IMHO it should sort the set of parents before\ncalculating the hash ...\n\nHelp?\nUli\n"},{"id":"202699","messageId":"m2y5iarf5s.fsf@igel.home","threadId":"32048","inReplyTo":"20121109133132.GK69724@acme.spoerlein.net","subject":"Re: git merge commits are non-deterministic? what changed?","fromName":"Andreas Schwab","fromEmail":"schwab@linux-m68k.org","sentAt":"2012-11-09T15:04:31Z","receivedAt":"2012-11-09T15:04:31Z","isPatch":false,"sender":{"key":"schwab@linux-m68k.org","avatar":"https://avatars.githubusercontent.com/u/2175493?v=4"},"body":"Ulrich Spörlein <uqs@spoerlein.net> writes:\n\n> Two questions:\n> 1. Can we impose a stable ordering of the commits being recorded in a\n> merge commit? Listing parents in chronological order or something like\n> that.\n\nThe order is determined by the order the refs are given to git merge (or\ngit commit-tree when using the plumbing).\n\n> 2. Why the hell is the commit hash dependent on the ordering of the\n> parent commits? IMHO it should sort the set of parents before\n> calculating the hash ...\n\nWhat would be the sort key?\n\nAndreas.\n\n-- \nAndreas Schwab, schwab@linux-m68k.org\nGPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5\n\"And now for something completely different.\"\n"},{"id":"202700","messageId":"20121109154245.GP69724@acme.spoerlein.net","threadId":"32048","inReplyTo":"m2y5iarf5s.fsf@igel.home","subject":"Re: git merge commits are non-deterministic? what changed?","fromName":"Ulrich Spörlein","fromEmail":"uqs@spoerlein.net","sentAt":"2012-11-09T15:42:45Z","receivedAt":"2012-11-09T15:42:45Z","isPatch":false,"sender":{"key":"uqs@spoerlein.net","avatar":null},"body":"On Fri, 2012-11-09 at 16:04:31 +0100, Andreas Schwab wrote:\n> Ulrich Spörlein <uqs@spoerlein.net> writes:\n> \n> > Two questions:\n> > 1. Can we impose a stable ordering of the commits being recorded in a\n> > merge commit? Listing parents in chronological order or something like\n> > that.\n> \n> The order is determined by the order the refs are given to git merge (or\n> git commit-tree when using the plumbing).\n> \n> > 2. Why the hell is the commit hash dependent on the ordering of the\n> > parent commits? IMHO it should sort the set of parents before\n> > calculating the hash ...\n> \n> What would be the sort key?\n\nTrivially, the hash of the parents itself. So you'd always get\n\n...\nparent 0000\nparent 1111\nparent aaaa\nparent ffff\n\nhth\nUli\n"},{"id":"202701","messageId":"vpq390idb8v.fsf@grenoble-inp.fr","threadId":"32048","inReplyTo":"20121109154245.GP69724@acme.spoerlein.net","subject":"Re: git merge commits are non-deterministic? what changed?","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2012-11-09T15:52:48Z","receivedAt":"2012-11-09T15:52:48Z","isPatch":false,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Ulrich Spörlein <uqs@spoerlein.net> writes:\n\n>> > 2. Why the hell is the commit hash dependent on the ordering of the\n>> > parent commits? IMHO it should sort the set of parents before\n>> > calculating the hash ...\n>> \n>> What would be the sort key?\n>\n> Trivially, the hash of the parents itself. So you'd always get\n>\n> ...\n> parent 0000\n> parent 1111\n> parent aaaa\n> parent ffff\n\nThat would change the behavior of --first-parent. Or you'd need to\ncompute the sha1 of the sorted list, but keep the unsorted one in the\ncommit. Possible, but weird ;-).\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"202703","messageId":"20121109161647.GB19725@sigill.intra.peff.net","threadId":"32048","inReplyTo":"vpq390idb8v.fsf@grenoble-inp.fr","subject":"Re: git merge commits are non-deterministic? what changed?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-09T16:16:47Z","receivedAt":"2012-11-09T16:16:47Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 09, 2012 at 04:52:48PM +0100, Matthieu Moy wrote:\n\n> Ulrich Spörlein <uqs@spoerlein.net> writes:\n> \n> >> > 2. Why the hell is the commit hash dependent on the ordering of the\n> >> > parent commits? IMHO it should sort the set of parents before\n> >> > calculating the hash ...\n> >> \n> >> What would be the sort key?\n> >\n> > Trivially, the hash of the parents itself. So you'd always get\n> >\n> > ...\n> > parent 0000\n> > parent 1111\n> > parent aaaa\n> > parent ffff\n> \n> That would change the behavior of --first-parent. Or you'd need to\n> compute the sha1 of the sorted list, but keep the unsorted one in the\n> commit. Possible, but weird ;-).\n\nRight. The reason that merge parents are stored in the order given on\nthe command line is not random or because it was not considered. It\nencodes a valuable piece of information: did the user merge \"foo\" into\n\"bar\", or did they merge \"bar\" into \"foo\"?\n\nSo I think this discussion is going in the wrong direction; git should\nnever sort the parents, because the order is meaningful. The original\ncomplaint was that a run of svn2git produced different results on two\ndifferent git versions. The important question to me is: did svn2git\nfeed the parents to git in the same order?\n\nIf it did, and git produced different results, then that is a serious\nbug.\n\nIf it did not, then the issue needs to be resolved in svn2git (which\n_may_ want to sort the parents that it feeds to git, but it would depend\non whether the order it is currently presenting is meaningful).\n\n-Peff\n"},{"id":"202710","messageId":"20121109182753.GQ69724@acme.spoerlein.net","threadId":"32048","inReplyTo":"20121109161647.GB19725@sigill.intra.peff.net","subject":"Re: git merge commits are non-deterministic? what changed?","fromName":"Ulrich Spörlein","fromEmail":"uqs@spoerlein.net","sentAt":"2012-11-09T18:27:53Z","receivedAt":"2012-11-09T18:27:53Z","isPatch":false,"sender":{"key":"uqs@spoerlein.net","avatar":null},"body":"On Fri, 2012-11-09 at 11:16:47 -0500, Jeff King wrote:\n> On Fri, Nov 09, 2012 at 04:52:48PM +0100, Matthieu Moy wrote:\n> \n> > Ulrich Spörlein <uqs@spoerlein.net> writes:\n> > \n> > >> > 2. Why the hell is the commit hash dependent on the ordering of the\n> > >> > parent commits? IMHO it should sort the set of parents before\n> > >> > calculating the hash ...\n> > >> \n> > >> What would be the sort key?\n> > >\n> > > Trivially, the hash of the parents itself. So you'd always get\n> > >\n> > > ...\n> > > parent 0000\n> > > parent 1111\n> > > parent aaaa\n> > > parent ffff\n> > \n> > That would change the behavior of --first-parent. Or you'd need to\n> > compute the sha1 of the sorted list, but keep the unsorted one in the\n> > commit. Possible, but weird ;-).\n> \n> Right. The reason that merge parents are stored in the order given on\n> the command line is not random or because it was not considered. It\n> encodes a valuable piece of information: did the user merge \"foo\" into\n> \"bar\", or did they merge \"bar\" into \"foo\"?\n> \n> So I think this discussion is going in the wrong direction; git should\n> never sort the parents, because the order is meaningful. The original\n> complaint was that a run of svn2git produced different results on two\n> different git versions. The important question to me is: did svn2git\n> feed the parents to git in the same order?\n> \n> If it did, and git produced different results, then that is a serious\n> bug.\n> \n> If it did not, then the issue needs to be resolved in svn2git (which\n> _may_ want to sort the parents that it feeds to git, but it would depend\n> on whether the order it is currently presenting is meaningful).\n\nYeah, thanks, looks like I have some more work to do. I don't quite get\nhow it could come up with a different order, seeing that it is using svn\nas the base.\n\nWill run some more experiments, thanks for the info so far.\n\nCheers,\nUli\n"},{"id":"202950","messageId":"50A0DD23.4040800@drmicha.warpmail.net","threadId":"32048","inReplyTo":"20121109182753.GQ69724@acme.spoerlein.net","subject":"Re: git merge commits are non-deterministic? what changed?","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2012-11-12T11:27:31Z","receivedAt":"2012-11-12T11:27:31Z","isPatch":false,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Ulrich Spörlein venit, vidit, dixit 09.11.2012 19:27:\n> On Fri, 2012-11-09 at 11:16:47 -0500, Jeff King wrote:\n>> On Fri, Nov 09, 2012 at 04:52:48PM +0100, Matthieu Moy wrote:\n>>\n>>> Ulrich Spörlein <uqs@spoerlein.net> writes:\n>>>\n>>>>>> 2. Why the hell is the commit hash dependent on the ordering of the\n>>>>>> parent commits? IMHO it should sort the set of parents before\n>>>>>> calculating the hash ...\n>>>>>\n>>>>> What would be the sort key?\n>>>>\n>>>> Trivially, the hash of the parents itself. So you'd always get\n>>>>\n>>>> ...\n>>>> parent 0000\n>>>> parent 1111\n>>>> parent aaaa\n>>>> parent ffff\n>>>\n>>> That would change the behavior of --first-parent. Or you'd need to\n>>> compute the sha1 of the sorted list, but keep the unsorted one in the\n>>> commit. Possible, but weird ;-).\n>>\n>> Right. The reason that merge parents are stored in the order given on\n>> the command line is not random or because it was not considered. It\n>> encodes a valuable piece of information: did the user merge \"foo\" into\n>> \"bar\", or did they merge \"bar\" into \"foo\"?\n>>\n>> So I think this discussion is going in the wrong direction; git should\n>> never sort the parents, because the order is meaningful. The original\n>> complaint was that a run of svn2git produced different results on two\n>> different git versions. The important question to me is: did svn2git\n>> feed the parents to git in the same order?\n>>\n>> If it did, and git produced different results, then that is a serious\n>> bug.\n>>\n>> If it did not, then the issue needs to be resolved in svn2git (which\n>> _may_ want to sort the parents that it feeds to git, but it would depend\n>> on whether the order it is currently presenting is meaningful).\n> \n> Yeah, thanks, looks like I have some more work to do. I don't quite get\n> how it could come up with a different order, seeing that it is using svn\n> as the base.\n> \n> Will run some more experiments, thanks for the info so far.\n\nThere was a change in the order in which \"git cherry-pick A B C\" applies\nthe commits. It's the only odering affecting change in 1.8.0 that I can\nthink of right now.\n\nMichael\n"},{"id":"203562","messageId":"20121120162226.GK69724@acme.spoerlein.net","threadId":"32048","inReplyTo":"50A0DD23.4040800@drmicha.warpmail.net","subject":"Re: git merge commits are non-deterministic? what changed?","fromName":"Ulrich Spörlein","fromEmail":"uqs@spoerlein.net","sentAt":"2012-11-20T16:22:26Z","receivedAt":"2012-11-20T16:22:26Z","isPatch":false,"sender":{"key":"uqs@spoerlein.net","avatar":null},"body":"On Mon, 2012-11-12 at 12:27:31 +0100, Michael J Gruber wrote:\n> Ulrich Spörlein venit, vidit, dixit 09.11.2012 19:27:\n> > On Fri, 2012-11-09 at 11:16:47 -0500, Jeff King wrote:\n> >> On Fri, Nov 09, 2012 at 04:52:48PM +0100, Matthieu Moy wrote:\n> >>\n> >>> Ulrich Spörlein <uqs@spoerlein.net> writes:\n> >>>\n> >>>>>> 2. Why the hell is the commit hash dependent on the ordering of the\n> >>>>>> parent commits? IMHO it should sort the set of parents before\n> >>>>>> calculating the hash ...\n> >>>>>\n> >>>>> What would be the sort key?\n> >>>>\n> >>>> Trivially, the hash of the parents itself. So you'd always get\n> >>>>\n> >>>> ...\n> >>>> parent 0000\n> >>>> parent 1111\n> >>>> parent aaaa\n> >>>> parent ffff\n> >>>\n> >>> That would change the behavior of --first-parent. Or you'd need to\n> >>> compute the sha1 of the sorted list, but keep the unsorted one in the\n> >>> commit. Possible, but weird ;-).\n> >>\n> >> Right. The reason that merge parents are stored in the order given on\n> >> the command line is not random or because it was not considered. It\n> >> encodes a valuable piece of information: did the user merge \"foo\" into\n> >> \"bar\", or did they merge \"bar\" into \"foo\"?\n> >>\n> >> So I think this discussion is going in the wrong direction; git should\n> >> never sort the parents, because the order is meaningful. The original\n> >> complaint was that a run of svn2git produced different results on two\n> >> different git versions. The important question to me is: did svn2git\n> >> feed the parents to git in the same order?\n> >>\n> >> If it did, and git produced different results, then that is a serious\n> >> bug.\n> >>\n> >> If it did not, then the issue needs to be resolved in svn2git (which\n> >> _may_ want to sort the parents that it feeds to git, but it would depend\n> >> on whether the order it is currently presenting is meaningful).\n> > \n> > Yeah, thanks, looks like I have some more work to do. I don't quite get\n> > how it could come up with a different order, seeing that it is using svn\n> > as the base.\n> > \n> > Will run some more experiments, thanks for the info so far.\n> \n> There was a change in the order in which \"git cherry-pick A B C\" applies\n> the commits. It's the only odering affecting change in 1.8.0 that I can\n> think of right now.\n\nJust to wrap this up, it was of course a \"feature\" of the converter,\nthat resulted in this unrepeatable behavior. The SVN API makes use of\napr_hashes, which were traversed in arbitrary order, hence SVN commits\nspanning multiple git-branches would be handled in a non-deterministic\norder, leading to randomly ordered parent objects for later git merge\ncommits.\n\nIt it still debatable, whether a merge commit should have a\nlist-of-parents or a set-of-parents. Changing it to a set-of-parents\n(with a well-defined hash function), would have made this problem go\naway.\n\nBut this will never be changed, it would break the fundamental git\nstorage model as it is in place now.\n\nCheers,\nUli\n"},{"id":"203570","messageId":"7v4nkkroum.fsf@alter.siamese.dyndns.org","threadId":"32048","inReplyTo":"20121120162226.GK69724@acme.spoerlein.net","subject":"Re: git merge commits are non-deterministic? what changed?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-11-20T20:39:13Z","receivedAt":"2012-11-20T20:39:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ulrich Spörlein <uqs@spoerlein.net> writes:\n\n> But this will never be changed, it would break the fundamental git\n> storage model as it is in place now.\n\nIt doesn't just break \"storage model\", but more importantly, it\nbreaks the semantics.\n\nImagine that things started breaking after merging your topic branch\n'foo' to the integration branch 'master', and how people would\nperceive the situation.  Everybody would say your topic 'foo' broke\nthe build.  Nobody except you would say, even if the tip of your\ntopic 'foo' alone works perfectly, merging the 'master' to your\ntopic 'foo' broke that topic.  The topic should have been adjusted\nto the updated baseline, that is the 'master' branch before this\nmerge since your topic 'foo' forked off of it, before or during the\nmerge.\n\nTo express what was merged into what, the order of parents in the\ncommit is fundamentally a part of what a commit is.\n"}]}