{"thread":{"id":"58233","subject":"Lost file after git merge","startedAt":"2022-07-28T08:23:33Z","lastAt":"2022-07-31T01:46:31Z","messageCount":9,"participants":["Laďa Tesařík","Ævar Arnfjörð Bjarmason","Junio C Hamano","brian m. carlson","René Scharfe","Elijah Newren"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"460066","messageId":"HE1PR0501MB24096E2FBDB66318A2FDADAAF8969@HE1PR0501MB2409.eurprd05.prod.outlook.com","threadId":"58233","inReplyTo":null,"subject":"Lost file after git merge","fromName":"Laďa Tesařík","fromEmail":"lada.tesarik@olc.cz","sentAt":"2022-07-28T08:23:24Z","receivedAt":"2022-07-28T08:23:33Z","isPatch":false,"sender":{"key":"lada.tesarik@olc.cz","avatar":null},"body":"Dear all,\n\nrecently we experienced strange behavior of git merge after deleting file in two branches and introducing it again in one of them (revision graph: https://i.stack.imgur.com/jNUZB.png):\n\n1. I added a file called 'new_file' to a master branch.\n2. Then I created branch feature/2 and deleted the file in master\n3. Then I deleted the file in branch feature/2 as well.\n4. I created 'new_file' on branch feature/2 again.\n5. I merged feature/2 into master, merge introduced no changes, file 'new_file' is not present in master.\n\nThis could cause problems to our team in the future, fortunately we noticed it this time.\nPlease, does anybody have any explanation for this behavior?\n\nOr is anybody aware of any Git or Source option that changes this behaviour?\n\nThank you very much,\n\nLada Tesarik\n\nP. S.\nIn the picture the steps were done with git revert command, but result is the same if I delete file manually and perform git commit.\nTested with git versions 2.26 and 2.37"},{"id":"460068","messageId":"220728.865yjhl8wk.gmgdl@evledraar.gmail.com","threadId":"58233","inReplyTo":"HE1PR0501MB24096E2FBDB66318A2FDADAAF8969@HE1PR0501MB2409.eurprd05.prod.outlook.com","subject":"Re: Lost file after git merge","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-07-28T12:17:51Z","receivedAt":"2022-07-28T12:27:32Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Jul 28 2022, Laďa Tesařík wrote:\n\n> 1. I added a file called 'new_file' to a master branch.\n> 2. Then I created branch feature/2 and deleted the file in master\n> 3. Then I deleted the file in branch feature/2 as well.\n> 4. I created 'new_file' on branch feature/2 again.\n> 5. I merged feature/2 into master, merge introduced no changes, file 'new_file' is not present in master.\n>\n> This could cause problems to our team in the future, fortunately we noticed it this time.\n> Please, does anybody have any explanation for this behavior?\n>\n> Or is anybody aware of any Git or Source option that changes this behaviour?\n>\n> Thank you very much,\n>\n> Lada Tesarik\n>\n> P. S.\n> In the picture the steps were done with git revert command, but result is the same if I delete file manually and perform git commit.\n> Tested with git versions 2.26 and 2.37\n\nThose who know \"merge\" better will chime in, but I believe this is known\nbehavior, and you can see why if your \"topic\" branch doesn't\n(re)introduce the file as it was on master, but adds a small change to\nit.\n\nI quickly experimented with this (with the fast-export stream at the\nend). If you had a \"hello\" as the content on \"master\" and introduced\n\"hello2\" on the topic you'd get:\n\n\t$ git merge topic\n\tCONFLICT (modify/delete): file.txt deleted in HEAD and modified in topic.  Version topic of file.txt left in tree.\n\tAutomatic merge failed; fix conflicts and then commit the result.\n\nSo others will know better, but I vaguely recall this having to do with\nthis being the same in your version (not the below hello2 version, but\nif you s/hello2/hello/):\n\n\tgit rev-parse $(git merge-base topic master):\n\tgit rev-parse topic:\n\nI.e. the topic is the TREESAME as its divergence point with \"master\",\nwhich IIRC is a shortcut the merge takes when deciding what changes to\nkeep, and whether they conflict.\n\n--\nblob\nmark :1\ndata 6\nhello\n\nreset refs/heads/master\ncommit refs/heads/master\nmark :2\nauthor Ævar Arnfjörð Bjarmason <avarab@gmail.com> 1659010359 +0200\ncommitter Ævar Arnfjörð Bjarmason <avarab@gmail.com> 1659010359 +0200\ndata 9\nAdd file\nM 100644 :1 file.txt\n\ncommit refs/heads/master\nmark :3\nauthor Ævar Arnfjörð Bjarmason <avarab@gmail.com> 1659010437 +0200\ncommitter Ævar Arnfjörð Bjarmason <avarab@gmail.com> 1659010437 +0200\ndata 81\nRevert \"Add file\"\n\nThis reverts commit 75aa73c55b19219d47dfc7ec3883c88466678718.\nfrom :2\nD file.txt\n\ncommit refs/heads/topic\nmark :4\nauthor Ævar Arnfjörð Bjarmason <avarab@gmail.com> 1659010369 +0200\ncommitter Ævar Arnfjörð Bjarmason <avarab@gmail.com> 1659010369 +0200\ndata 81\nRevert \"Add file\"\n\nThis reverts commit 75aa73c55b19219d47dfc7ec3883c88466678718.\nfrom :2\nD file.txt\n\nblob\nmark :5\ndata 7\nhello2\n\ncommit refs/heads/topic\nmark :6\nauthor Ævar Arnfjörð Bjarmason <avarab@gmail.com> 1659010359 +0200\ncommitter Ævar Arnfjörð Bjarmason <avarab@gmail.com> 1659010644 +0200\ndata 9\nAdd file\nfrom :4\nM 100644 :5 file.txt\n\n"},{"id":"460130","messageId":"xmqqilnhcgd7.fsf@gitster.g","threadId":"58233","inReplyTo":"220728.865yjhl8wk.gmgdl@evledraar.gmail.com","subject":"Re: Lost file after git merge","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-07-28T17:11:00Z","receivedAt":"2022-07-28T17:11:09Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n\n> On Thu, Jul 28 2022, Laďa Tesařík wrote:\n>\n>> 1. I added a file called 'new_file' to a master branch.\n>> 2. Then I created branch feature/2 and deleted the file in master\n>> 3. Then I deleted the file in branch feature/2 as well.\n>> 4. I created 'new_file' on branch feature/2 again.\n\nIt heavily depends on how this creation is done, i.e. what went into\nthe created file.  Imagine that a file existed with content A at\ncommit 0, both commits 1 and 2 removed it on their forked history,\nand then commit 3 added exactly the same content A to the same path:\n\n          1---3\n         /     \\\n    ----0---2---4---->\n\nWhen you are about to merge 2 and 3 to create 4, what would a\nthree-way merge see?\n\n    0 had content A at path P\n    2 said \"no we do not want content A at path P\"\n    3 said \"we are happy with content A at path P\"\n\nSo the net result is that 0-->3 \"one side did not touch A at P\" and\n0-->2 \"one side removed A at P\".  \n\nThree-way merge between X and Y is all about taking what X did if Y\ndidn't have any opinion on what X touched.  This is exactly that\ncase.  The history 0--->3 didn't have any opinion on what should be\nin P or whether P should exist, and that is why there is no change\nbetween these two endpoints.  The history 0--->2 does care---it feels\nthat it is detrimental to the project to have P hence it removed.\n\nSo the end result will remove P, if 3 added identical content as\nexisted at 0 and removed at 1.\n\nIf 3 added something different, then the picture becomes entirely\ndifferent.  The history 0--->3 no longer has \"no opinion\".  It\nstrongly believes that P having content A at 0 was wrong, and it\nshould have content B, hence it changed it.  Now when that opinion\ncollides with the opinion of the history 0--->2 that says it is\nwrong to have content A at path P, the person who is creating the\nmerge at 4 needs to think and resolve.\n"},{"id":"460153","messageId":"YuL+btk2MYmnphRs@tapette.crustytoothpaste.net","threadId":"58233","inReplyTo":"HE1PR0501MB24096E2FBDB66318A2FDADAAF8969@HE1PR0501MB2409.eurprd05.prod.outlook.com","subject":"Re: Lost file after git merge","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2022-07-28T21:23:58Z","receivedAt":"2022-07-28T21:24:04Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2022-07-28 at 08:23:24, Laďa Tesařík wrote:\n> Dear all,\n> \n> recently we experienced strange behavior of git merge after deleting file in two branches and introducing it again in one of them (revision graph: https://i.stack.imgur.com/jNUZB.png):\n> \n> 1. I added a file called 'new_file' to a master branch.\n> 2. Then I created branch feature/2 and deleted the file in master\n> 3. Then I deleted the file in branch feature/2 as well.\n> 4. I created 'new_file' on branch feature/2 again.\n> 5. I merged feature/2 into master, merge introduced no changes, file 'new_file' is not present in master.\n> \n> This could cause problems to our team in the future, fortunately we noticed it this time.\n> Please, does anybody have any explanation for this behavior?\n> \n> Or is anybody aware of any Git or Source option that changes this behaviour?\n\nI think this is covered in the Git FAQ:\n\nIf I make a change on two branches but revert it on one, why does the merge of those branches include the change?\n\tBy default, when Git does a merge, it uses a strategy called the `ort`\n\tstrategy, which does a fancy three-way merge.  In such a case, when Git\n\tperforms the merge, it considers exactly three points: the two heads and a\n\tthird point, called the _merge base_, which is usually the common ancestor of\n\tthose commits.  Git does not consider the history or the individual commits\n\tthat have happened on those branches at all.\n\n  As a result, if both sides have a change and one side has reverted that change,\n  the result is to include the change.  This is because the code has changed on\n  one side and there is no net change on the other, and in this scenario, Git\n  adopts the change.\n\n  If this is a problem for you, you can do a rebase instead, rebasing the branch\n  with the revert onto the other branch.  A rebase in this scenario will revert\n  the change, because a rebase applies each individual commit, including the\n  revert.  Note that rebases rewrite history, so you should avoid rebasing\n  published branches unless you're sure you're comfortable with that.  See the\n  NOTES section in git-rebase(1) for more details.\n\nIn this case, your change is to delete the file and the revert is to\nre-add it, which is why this is happening.\n\nI realize this is tricky, which is why I added this FAQ entry, and,\nbefore that, the mention in git-merge(1) in the sentence starting with\n\"With the strategies\".  It is, however, the correct behaviour, since a\nthree-way merge must necessarily adopt a change, whatever that is, when\nthe other side is unchanged, and as a result, there's no configuration\noption for this.\n-- \nbrian m. carlson (he/him or they/them)\nToronto, Ontario, CA\n"},{"id":"460267","messageId":"701c318c-1a1b-1793-90e8-807cf97dc948@web.de","threadId":"58233","inReplyTo":"xmqqilnhcgd7.fsf@gitster.g","subject":"Re: Lost file after git merge","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-29T20:23:18Z","receivedAt":"2022-07-29T20:23:37Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 28.07.22 um 19:11 schrieb Junio C Hamano:\n> Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n>\n>> On Thu, Jul 28 2022, Laďa Tesařík wrote:\n>>\n>>> 1. I added a file called 'new_file' to a master branch.\n>>> 2. Then I created branch feature/2 and deleted the file in master\n>>> 3. Then I deleted the file in branch feature/2 as well.\n>>> 4. I created 'new_file' on branch feature/2 again.\n>\n> It heavily depends on how this creation is done, i.e. what went into\n> the created file.  Imagine that a file existed with content A at\n> commit 0, both commits 1 and 2 removed it on their forked history,\n> and then commit 3 added exactly the same content A to the same path:\n>\n>           1---3\n>          /     \\\n>     ----0---2---4---->\n>\n> When you are about to merge 2 and 3 to create 4, what would a\n> three-way merge see?\n>\n>     0 had content A at path P\n>     2 said \"no we do not want content A at path P\"\n>     3 said \"we are happy with content A at path P\"\n>\n> So the net result is that 0-->3 \"one side did not touch A at P\" and\n> 0-->2 \"one side removed A at P\".\n>\n> Three-way merge between X and Y is all about taking what X did if Y\n> didn't have any opinion on what X touched.  This is exactly that\n> case.  The history 0--->3 didn't have any opinion on what should be\n> in P or whether P should exist, and that is why there is no change\n> between these two endpoints.\n\nThe last sentence is not necessarily true.  You could also say that\n0--->3 cared so much about path P having content A that it brought it\nback from the void.  Determining whether a de-facto revert\n- intended to return to an uncaring state of \"take whatever main has\" or\n- meant to choose *that* specific content which incidentally is on main\nis not possible from the snapshots at the merge point alone, I think.\n\nChecking if 0...3 touched P and leaving that path unmerged out of\ncaution shouldn't be terribly expensive.\n\n> The history 0--->2 does care---it feels\n> that it is detrimental to the project to have P hence it removed.\n>\n> So the end result will remove P, if 3 added identical content as\n> existed at 0 and removed at 1.\n>\n> If 3 added something different, then the picture becomes entirely\n> different.  The history 0--->3 no longer has \"no opinion\".  It\n> strongly believes that P having content A at 0 was wrong, and it\n> should have content B, hence it changed it.  Now when that opinion\n> collides with the opinion of the history 0--->2 that says it is\n> wrong to have content A at path P, the person who is creating the\n> merge at 4 needs to think and resolve.\n\n"},{"id":"460284","messageId":"xmqqh72z4lu6.fsf@gitster.g","threadId":"58233","inReplyTo":"701c318c-1a1b-1793-90e8-807cf97dc948@web.de","subject":"Re: Lost file after git merge","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-07-29T22:04:33Z","receivedAt":"2022-07-29T22:04:41Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n>> Three-way merge between X and Y is all about taking what X did if Y\n>> didn't have any opinion on what X touched.  This is exactly that\n>> case.  The history 0--->3 didn't have any opinion on what should be\n>> in P or whether P should exist, and that is why there is no change\n>> between these two endpoints.\n>\n> The last sentence is not necessarily true.  You could also say that\n> 0--->3 cared so much about path P having content A that it brought it\n> back from the void.  Determining whether a de-facto revert\n> - intended to return to an uncaring state of \"take whatever main has\" or\n> - meant to choose *that* specific content which incidentally is on main\n> is not possible from the snapshots at the merge point alone, I think.\n\nYes, it is doable.  It no longer is a three-way merge if we did so,\nthough ;-)\n"},{"id":"460298","messageId":"CABPp-BE4saKAboS=SPQmQe6n2=Fnhv7pL4_JfF2Zwg5Zhp7Vjw@mail.gmail.com","threadId":"58233","inReplyTo":"701c318c-1a1b-1793-90e8-807cf97dc948@web.de","subject":"Re: Lost file after git merge","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-30T02:16:08Z","receivedAt":"2022-07-30T02:16:26Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Jul 29, 2022 at 1:34 PM René Scharfe <l.s.r@web.de> wrote:\n>\n> Am 28.07.22 um 19:11 schrieb Junio C Hamano:\n> > Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n> >\n> >> On Thu, Jul 28 2022, Laďa Tesařík wrote:\n> >>\n> >>> 1. I added a file called 'new_file' to a master branch.\n> >>> 2. Then I created branch feature/2 and deleted the file in master\n> >>> 3. Then I deleted the file in branch feature/2 as well.\n> >>> 4. I created 'new_file' on branch feature/2 again.\n> >\n> > It heavily depends on how this creation is done, i.e. what went into\n> > the created file.  Imagine that a file existed with content A at\n> > commit 0, both commits 1 and 2 removed it on their forked history,\n> > and then commit 3 added exactly the same content A to the same path:\n> >\n> >           1---3\n> >          /     \\\n> >     ----0---2---4---->\n> >\n> > When you are about to merge 2 and 3 to create 4, what would a\n> > three-way merge see?\n> >\n> >     0 had content A at path P\n> >     2 said \"no we do not want content A at path P\"\n> >     3 said \"we are happy with content A at path P\"\n> >\n> > So the net result is that 0-->3 \"one side did not touch A at P\" and\n> > 0-->2 \"one side removed A at P\".\n> >\n> > Three-way merge between X and Y is all about taking what X did if Y\n> > didn't have any opinion on what X touched.  This is exactly that\n> > case.  The history 0--->3 didn't have any opinion on what should be\n> > in P or whether P should exist, and that is why there is no change\n> > between these two endpoints.\n>\n> The last sentence is not necessarily true.  You could also say that\n> 0--->3 cared so much about path P having content A that it brought it\n> back from the void.  Determining whether a de-facto revert\n> - intended to return to an uncaring state of \"take whatever main has\" or\n> - meant to choose *that* specific content which incidentally is on main\n> is not possible from the snapshots at the merge point alone, I think.\n>\n> Checking if 0...3 touched P and leaving that path unmerged out of\n> caution shouldn't be terribly expensive.\n\nI think it might be terribly expensive.\n\nWalking history can easily be the slow part of such an operation, e.g.\ncan_fast_forward() taking roughly 100 times as long as doing the\nmerge_incore_recursive() portion that creates the new merged toplevel\ntree[1].  (And can_fast_forward() is a form of history walk that\ndoesn't involve traversing into any trees, so I suspect it's a cheaper\nhistory traversal than what is being suggested).\n\nFocusing on the tree traversal side, this suggested change would\nessentially disable the trivial directory resolution optimizations in\nmerge-ort[2].  (Note that the trivial directory resolution sped up a\nrebase that didn't involve very many renames by a factor of 25).  The\nwhole point of that optimization was to avoid walking into trees that\nwere only changed on one side, where possible.  Your proposed change\nwould be saying we always have to walk into trees that either side\nmodified...and do so for every intermediate commit as well so that we\ncan fully enumerate all (temporarily) changed files.\n\n\n[1] https://lore.kernel.org/git/CABPp-BE48=97k_3tnNqXPjSEfA163F8hoE+HY0Zvz1SWB2B8EA@mail.gmail.com/\n[2] https://lore.kernel.org/git/pull.988.v4.git.1626841444.gitgitgadget@gmail.com/\n"},{"id":"460307","messageId":"d461718f-cc72-96e2-4de6-4cc67e3b95a5@web.de","threadId":"58233","inReplyTo":"CABPp-BE4saKAboS=SPQmQe6n2=Fnhv7pL4_JfF2Zwg5Zhp7Vjw@mail.gmail.com","subject":"Re: Lost file after git merge","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-30T14:44:50Z","receivedAt":"2022-07-30T14:45:09Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 30.07.22 um 04:16 schrieb Elijah Newren:\n> On Fri, Jul 29, 2022 at 1:34 PM René Scharfe <l.s.r@web.de> wrote:\n>>\n>> Am 28.07.22 um 19:11 schrieb Junio C Hamano:\n>>> Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n>>>\n>>>> On Thu, Jul 28 2022, Laďa Tesařík wrote:\n>>>>\n>>>>> 1. I added a file called 'new_file' to a master branch.\n>>>>> 2. Then I created branch feature/2 and deleted the file in master\n>>>>> 3. Then I deleted the file in branch feature/2 as well.\n>>>>> 4. I created 'new_file' on branch feature/2 again.\n>>>\n>>> It heavily depends on how this creation is done, i.e. what went into\n>>> the created file.  Imagine that a file existed with content A at\n>>> commit 0, both commits 1 and 2 removed it on their forked history,\n>>> and then commit 3 added exactly the same content A to the same path:\n>>>\n>>>           1---3\n>>>          /     \\\n>>>     ----0---2---4---->\n>>>\n>>> When you are about to merge 2 and 3 to create 4, what would a\n>>> three-way merge see?\n>>>\n>>>     0 had content A at path P\n>>>     2 said \"no we do not want content A at path P\"\n>>>     3 said \"we are happy with content A at path P\"\n>>>\n>>> So the net result is that 0-->3 \"one side did not touch A at P\" and\n>>> 0-->2 \"one side removed A at P\".\n>>>\n>>> Three-way merge between X and Y is all about taking what X did if Y\n>>> didn't have any opinion on what X touched.  This is exactly that\n>>> case.  The history 0--->3 didn't have any opinion on what should be\n>>> in P or whether P should exist, and that is why there is no change\n>>> between these two endpoints.\n>>\n>> The last sentence is not necessarily true.  You could also say that\n>> 0--->3 cared so much about path P having content A that it brought it\n>> back from the void.  Determining whether a de-facto revert\n>> - intended to return to an uncaring state of \"take whatever main has\" or\n>> - meant to choose *that* specific content which incidentally is on main\n>> is not possible from the snapshots at the merge point alone, I think.\n>>\n>> Checking if 0...3 touched P and leaving that path unmerged out of\n>> caution shouldn't be terribly expensive.\n>\n> I think it might be terribly expensive.\n>\n> Walking history can easily be the slow part of such an operation, e.g.\n> can_fast_forward() taking roughly 100 times as long as doing the\n> merge_incore_recursive() portion that creates the new merged toplevel\n> tree[1].  (And can_fast_forward() is a form of history walk that\n> doesn't involve traversing into any trees, so I suspect it's a cheaper\n> history traversal than what is being suggested).\n>\n> Focusing on the tree traversal side, this suggested change would\n> essentially disable the trivial directory resolution optimizations in\n> merge-ort[2].  (Note that the trivial directory resolution sped up a\n> rebase that didn't involve very many renames by a factor of 25).  The\n> whole point of that optimization was to avoid walking into trees that\n> were only changed on one side, where possible.  Your proposed change\n> would be saying we always have to walk into trees that either side\n> modified...and do so for every intermediate commit as well so that we\n> can fully enumerate all (temporarily) changed files.\n\nTrue: Compared to just checking if a path was touched by 3, a history\ntraversal can take arbitrarily long.  At least it's bounded by the merge\nbase and a specific path.  And renames complicate the picture, but only\nfull renames (same blob or tree ID) need to be considered.  That feels\ndoable in a reasonable amount of time, but it's not as cheap as ignoring\nthe history.\n\nAssuming that one side doesn't care about a path because it has the same\ncontent as the merge base is tempting.  And reverts that break this\nassumption are probably quite rare.  Still it led to an unintended\noutcome here.  Reminds me of a recent chess robot incident [3].  Speed\nis nice and safety has a cost, but do we already make the best possible\ntradeoff here?\n\n> [1] https://lore.kernel.org/git/CABPp-BE48=97k_3tnNqXPjSEfA163F8hoE+HY0Zvz1SWB2B8EA@mail.gmail.com/\n> [2] https://lore.kernel.org/git/pull.988.v4.git.1626841444.gitgitgadget@gmail.com/\n\n[3] https://www.theguardian.com/sport/2022/jul/24/chess-robot-grabs-and-breaks-finger-of-seven-year-old-opponent-moscow\n"},{"id":"460322","messageId":"CABPp-BF5S6QT6Hn-1wf6w67-ayWfX5WZLZqueNMMeqp1jtXirg@mail.gmail.com","threadId":"58233","inReplyTo":"d461718f-cc72-96e2-4de6-4cc67e3b95a5@web.de","subject":"Re: Lost file after git merge","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-31T01:45:57Z","receivedAt":"2022-07-31T01:46:31Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Okay, you nerd-sniped me into responding why I'm super skeptical of this path...\n\nOn Sat, Jul 30, 2022 at 7:44 AM René Scharfe <l.s.r@web.de> wrote:\n>\n> Am 30.07.22 um 04:16 schrieb Elijah Newren:\n> > On Fri, Jul 29, 2022 at 1:34 PM René Scharfe <l.s.r@web.de> wrote:\n> >>\n> >> Am 28.07.22 um 19:11 schrieb Junio C Hamano:\n> >>> Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n> >>>\n> >>>> On Thu, Jul 28 2022, Laďa Tesařík wrote:\n> >>>>\n> >>>>> 1. I added a file called 'new_file' to a master branch.\n> >>>>> 2. Then I created branch feature/2 and deleted the file in master\n> >>>>> 3. Then I deleted the file in branch feature/2 as well.\n> >>>>> 4. I created 'new_file' on branch feature/2 again.\n> >>>\n> >>> It heavily depends on how this creation is done, i.e. what went into\n> >>> the created file.  Imagine that a file existed with content A at\n> >>> commit 0, both commits 1 and 2 removed it on their forked history,\n> >>> and then commit 3 added exactly the same content A to the same path:\n> >>>\n> >>>           1---3\n> >>>          /     \\\n> >>>     ----0---2---4---->\n> >>>\n> >>> When you are about to merge 2 and 3 to create 4, what would a\n> >>> three-way merge see?\n> >>>\n> >>>     0 had content A at path P\n> >>>     2 said \"no we do not want content A at path P\"\n> >>>     3 said \"we are happy with content A at path P\"\n> >>>\n> >>> So the net result is that 0-->3 \"one side did not touch A at P\" and\n> >>> 0-->2 \"one side removed A at P\".\n> >>>\n> >>> Three-way merge between X and Y is all about taking what X did if Y\n> >>> didn't have any opinion on what X touched.  This is exactly that\n> >>> case.  The history 0--->3 didn't have any opinion on what should be\n> >>> in P or whether P should exist, and that is why there is no change\n> >>> between these two endpoints.\n> >>\n> >> The last sentence is not necessarily true.  You could also say that\n> >> 0--->3 cared so much about path P having content A that it brought it\n> >> back from the void.  Determining whether a de-facto revert\n> >> - intended to return to an uncaring state of \"take whatever main has\" or\n> >> - meant to choose *that* specific content which incidentally is on main\n> >> is not possible from the snapshots at the merge point alone, I think.\n> >>\n> >> Checking if 0...3 touched P and leaving that path unmerged out of\n> >> caution shouldn't be terribly expensive.\n> >\n> > I think it might be terribly expensive.\n> >\n> > Walking history can easily be the slow part of such an operation, e.g.\n> > can_fast_forward() taking roughly 100 times as long as doing the\n> > merge_incore_recursive() portion that creates the new merged toplevel\n> > tree[1].  (And can_fast_forward() is a form of history walk that\n> > doesn't involve traversing into any trees, so I suspect it's a cheaper\n> > history traversal than what is being suggested).\n> >\n> > Focusing on the tree traversal side, this suggested change would\n> > essentially disable the trivial directory resolution optimizations in\n> > merge-ort[2].  (Note that the trivial directory resolution sped up a\n> > rebase that didn't involve very many renames by a factor of 25).  The\n> > whole point of that optimization was to avoid walking into trees that\n> > were only changed on one side, where possible.  Your proposed change\n> > would be saying we always have to walk into trees that either side\n> > modified...and do so for every intermediate commit as well so that we\n> > can fully enumerate all (temporarily) changed files.\n>\n> True: Compared to just checking if a path was touched by 3, a history\n> traversal can take arbitrarily long.  At least it's bounded by the merge\n> base and a specific path.\n\nHow is it bounded by a specific path?  How do you know which path to\ncheck?  Can't this affect many paths?  I think to fix this issue, you\neither have to walk all paths for all intermediate commits, OR:\n  * get the list of paths modified between the merge base and one side\nof history (just an endpoint diff, not a view of history along the\nway)\n  * get the list of paths modified between the merge base and the\nother side of history (again, just an endpoint diff)\n  * take the symmetric difference of those two lists above (let's name\nthe resulting set SD so we can refer to it later).\n  * Walk all intermediate commits between the merge base and the two\nendpoints being merged, and for each one investigate every path in it\ncorresponding to one of the paths in SD.\n  * As we do the above walk into trees of all intermediate commits,\nlook for a sequence of commits that does some change and then later\nreverts it\n\nAlso, I think using the phrase \"the merge base\" points out some\nill-posedness in this problem.  For actual merges, I think it's well\nposed.  But...\n\nWhat about cherry-picks, rebases, and reverts?  Those pass a funny\nmerge-base to the merge machinery.  Using that merge-base does allow\nus to construct a valid commit range, but in that context, is that\nrange still correct to use with your rule?  Perhaps it does make sense\nto use that range and apply your same rule, but...\n\nWhat if we instead cherry-pick a different way -- using format-patch\nand `git am -3`?  At the time git-am runs, it only has one commit\navailable to it.  It cannot determine any merge-base.  So what range\nof commits should it walk to see if the upstream side has both made a\nchange to some file and then undone that change?  Do we walk all of\nhistory?  Do we attempt to find some point in history that appears to\nhave the same versions of the files in the \"from\" versions of the\npatch being applied?  What if such a commit does not exist?  What if\nmany such commits exist?  If many such commits exist, what if using\none of those commits would give us a different answer than using\nanother commit (meaning, what if we do see a change-and-then-unchange\nif one of them is used as the merge-base, but do not see such a\nsequence if the other one is)?  I'm certain I could construct examples\nof each of those \"What if\" scenarios for git-am.\n\n>  And renames complicate the picture, but only\n> full renames (same blob or tree ID) need to be considered.  That feels\n> doable in a reasonable amount of time, but it's not as cheap as ignoring\n> the history.\n\nMaking things 25x slower and calling it \"not as cheap\"?  That's some\nliterary jiu-jitsu there.\n\nAlso, I think the 25x figure may well undercount the expense, perhaps\neven dramatically, since I'm not sure things can be limited in the\nform you envision...\n\n> Assuming that one side doesn't care about a path because it has the same\n> content as the merge base is tempting.  And reverts that break this\n> assumption are probably quite rare.  Still it led to an unintended\n> outcome here.  Reminds me of a recent chess robot incident [3].  Speed\n> is nice and safety has a cost, but do we already make the best possible\n> tradeoff here?\n\nI mean, if you want to make an alternative merge strategy that isn't\nbased on a three-way merge, by all means go ahead.  We have pluggable\nbackends, after all.\n\nIt's not clear to me that your suggestion actually leads to a\nsituation with fewer unintended outcomes, though it is clear that\nperformance could be dramatically worse.  Let's explore this for a bit\n(more than I already have above)...\n\nLet's say you aim to fix this \"unintended outcome\" via paying\nattention to the changes from individual commits along the way.  This\nisn't the only such issue users report that is intrinsic to how\nthree-way content merges work.  Do you decide to also address the\nothers?  From the top of my head, others include:\n\nA) generalize your logic here -- apply it to individual hunks rather\nthan only to whole files.  Using your exact same rationale would\nsuggest that if someone modifies a hunk on one side of history and\nundid it later, then that region of code should not cleanly resolve to\nwhat the other side of history has but should instead be marked as\nconflicted.\nB) handle commits cherry-picked to both sides \"better\".  If someone\napplies the same cherry-pick to both sides, and they then further\nmodify the same lines on one side, there should be no \"useless\"\nconflict, because both sides \"built on top of\" the same cherry-picked\nstate.\nC) make rename detection match files based on changes in individual\ncommits rather than on the overall diff since the merge base\n\nIt turns out that others have explored part of this space before, e.g.\nBram Cohen's \"Precise Codeville Merge\"[4], which had names for\nbehaviors (A) and (B) (see [5] and [6], respectively; also note that\nit points out that requirements (A) and (B) can come into conflict).\nPerhaps if you are interested, you can port his code over and use his\nalgorithm?  However, it might be worth noting that he later gave up on\nit and recommended that people use three-way merges instead[7].\n\nSince Git seems to be the only system that does rename detection, (C)\nis new territory.  But it's also relevant in that a user requested\nthat the merge algorithm incorporate information from changes in\nindividual commits along the history in order to solve a \"bug\" they\nran into[8].\n\nAlso, besides implementing Bram's \"Precise Codeville Merge\" in Git,\nthere may be another pre-existing solution available: using Michael\nHaggerty's git-imerge[9] and making sure it fully fills out its matrix\nof merges instead of opportunistically attempting to skip some.  That\nwould certainly make sure that changes from each individual commit was\nconsidered.\n\nBut let's say you don't want to use either Precise Codeville Merge or\ngit-imerge, and want to make a copy of our default strategy\n(merge-ort) and modify it.  Once you implement your new strategy, I'm\nsure the other cases in (A), (B), and (C) will be brought up by people\nand it's hard to see based on your rationale so far why your new\nalgorithm shouldn't attempt to solve those issues as well.  If you do,\nyour performance will really tank.  Not only did you kill the trivial\ndirectory resolution optimization, you also kill the irrelevant\nrenames optimization (which, IMO, was the crowning jewel of the ort\noptimizations).  But it's also worse than that because (A) and likely\n(B) force you to compute pairwise diffs of every sequence of commits\nsince the merge base, and (C) forces those all to include rename\ndetection (both for full and partial renames).  But it gets worse.\nSome of those commits in the history back to the merge base will be\nmerge commits, for which we have to be careful with the diff\ncomputation.  We can't just ignore merge commits, because\nchange-and-then-unchanged code might have been done in merge commits\nas part of an attempt to fix semantic conflicts.  So, to address merge\ncommits, we have to see the changes made by users in those merges\nrelative to the auto-merge state.  If we do that, the upshot is that\nhandling (A)-(C) implies that to merge two branches, we have to look\nat all merge commits in the history of the two branches back to the\nmerge base, and remerge every one of them.\n\nMaybe you're okay with all of the above, even with others giving up on\nmerge strategies other than three-way merge.  Maybe individually\nmerging all commits since the merge base doesn't phase you.  Maybe you\ncan make some kind of distinction where some of (A)-(C) don't matter.\nMaybe you just capitulate and say you only care about the problem that\nstarted this thread and ignore all three of those requests.  Maybe you\ndon't care about git-am and exclude it, overlooking the extra\ndifference we've added between it and the other commands (a bit sad\nsince merge-ort had removed one of those differences and I like\ncommands being more consistent).  Maybe the resulting \"mere\" 25x\nslowdown is good enough for you for your repository sizes.  Or maybe\nyou'd be hiding this behind some non-default option that people could\nselect, allowing them to make the tradeoff.  Whether any or all of\nthat is true, I just don't see how to maintain it with the rationale\nand description given, so I'm not comfortable with it affecting the\ncode I have to maintain.\n\nSo, I'm skeptical.  But feel free to create a new merge strategy and\nprove me wrong.\n\n\n[4] https://tonyg.github.io/revctrl.org/PreciseCodevilleMerge.html\n[5] https://tonyg.github.io/revctrl.org/ImplicitUndo.html\n[6] https://tonyg.github.io/revctrl.org/Convergence.html\n[7] https://bramcohen.livejournal.com/52148.html\n[8] https://lore.kernel.org/git/CABPp-BHF5j9XTrJOreHMaQ+TrZB1VgZvs-Bq2vFD1yhLBdkV3A@mail.gmail.com/\n[9] https://github.com/mhagger/git-imerge\n"}]}