{"thread":{"id":"56742","subject":"Unexpected conflict with ort merge strategy?","startedAt":"2021-10-19T22:41:02Z","lastAt":"2022-04-21T03:21:42Z","messageCount":5,"participants":["Tao Klerks","Elijah Newren","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"439048","messageId":"CAPMMpojsNQuHe9iSUGyu_q2M4VObjDPj4c0QrFPsHdYypQ3aog@mail.gmail.com","threadId":"56742","inReplyTo":null,"subject":"Unexpected conflict with ort merge strategy?","fromName":"Tao Klerks","fromEmail":"tao@klerks.biz","sentAt":"2021-10-19T22:40:48Z","receivedAt":"2021-10-19T22:41:02Z","isPatch":false,"sender":{"key":"tao@klerks.biz","avatar":"https://avatars.githubusercontent.com/u/531704?v=4"},"body":"Hi folks,\n\nI just came across a situation where the ort merge strategy chooses a\n\"worse\" rename mapping than the recursive strategy - worse in the\nsense of having a lower similarity score, worse in the sense of having\nbeen a change in another commit (but I guess this is just a limitation\nof git merge? It doesn't look for renames \"iteratively\" through\nhistory when merging?), and finally worse in the sense of causing a\nmerge conflict that, given the previous two points, is unnecessary and\ndoes not occur with recursive.\n\nI've prepared a reproduction script, attached. It's probably a little\nconvoluted because I didn't know exactly what to look out for. This is\nan extreme simplification of a real-life incident:\n\nOne file (folder1/firstfile.txt) is deleted independently in two\nbranches, and another somewhat-similar file (folder2/secondfile.txt)\nis renamed (to folder2/secondfile_renamed.txt) and slightly modified\nin one of them (in another commit).\n\nWhen the branch with the rename gets merged in to the branch that just\nhad the delete, \"ort\" sees the rename as having been of\n\"folder1/firstfile.txt\" to \"folder2/secondfile_renamed.txt\", despite\nthis being of a lower similarity than the real rename that happened,\nand a conflict ensues.\n\nIs ort supposed to choose the \"best\" rename choice, for a given set of\ntrees, and failing to do so here? Or is this a case of recursive\n*accidentally* doing a better thing?\n\nThanks,\nTao\n\n\ngit init\ngit config commit.gpgsign false\ngit config user.name Tao\ngit config user.email tao@klerks.biz\ntouch firstfile\ngit add firstfile\ngit commit -m \"First commit\"\nmkdir folder1\nmkdir folder2\n\ncat >> folder1/firstfile.txt << \"EOF\"\nFirstLine\nSecond Line\nLine Number 3\nFourth Line\nThere can Always be more Lines\n\nThat was an Empty Line\nSome Unique Stuff\nBut Not too Much\nEOF\n\ncat >> folder2/secondfile.txt << \"EOF\"\nFirstLine\nSecond Line\nLine Number 3\nThere can Always be more Lines\nBut not too many!\n\nThat was an Empty Line\nOtherwise Unique Stuff\nBut Not too Much\nEOF\n\ngit add .\ngit commit -m \"Starting State\"\n\ngit checkout -b featurebranch\ntouch newworkingfile\ngit add newworkingfile\ngit commit -m \"New working file\"\ngit rm folder1/firstfile.txt\ngit add .\ngit commit -m \"Deleted in working branch\"\ntouch anothernewworkingfile\ngit add anothernewworkingfile\ngit commit -m \"More regular history\"\n\n\ngit checkout master\nrm folder1/firstfile.txt\ngit add .\ngit commit -m \"also deleted here\"\n\nrm folder2/secondfile.txt\n\ncat >> folder2/secondfile_renamed.txt << \"EOF\"\nFirstLine\nSecond Line\nLine Number 3\nThere can Always be more Lines\nBut not too many!\n\nThat was an Empty Line\nOtherwise Almost Unique Stuff\nBut Not too Much\nEOF\n\ngit add .\ngit commit -m \"a high-percentage rename\"\n\ntouch amasterfile\ngit add amasterfile\ngit commit -m \"More regular history in master\"\n\ngit checkout -b regularmerge featurebranch\ngit merge master -s recursive\n\ngit checkout -b ortmerge featurebranch\ngit merge master -s ort\n"},{"id":"440923","messageId":"CABPp-BFAf+-ULwtd7WowsN2KSeJ0s1ucZZ1QSRYg8J+wM9MrZw@mail.gmail.com","threadId":"56742","inReplyTo":"CAPMMpojsNQuHe9iSUGyu_q2M4VObjDPj4c0QrFPsHdYypQ3aog@mail.gmail.com","subject":"Re: Unexpected conflict with ort merge strategy?","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-11-11T17:57:09Z","receivedAt":"2021-11-11T17:57:25Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Sorry for the late response...\n\nOn Tue, Oct 19, 2021 at 3:44 PM Tao Klerks <tao@klerks.biz> wrote:\n>\n> Hi folks,\n>\n> I just came across a situation where the ort merge strategy chooses a\n> \"worse\" rename mapping than the recursive strategy - worse in the\n> sense of having a lower similarity score, worse in the sense of having\n> been a change in another commit (but I guess this is just a limitation\n> of git merge? It doesn't look for renames \"iteratively\" through\n> history when merging?), and finally worse in the sense of causing a\n> merge conflict that, given the previous two points, is unnecessary and\n> does not occur with recursive.\n>\n>\n> I've prepared a reproduction script, attached. It's probably a little\n> convoluted because I didn't know exactly what to look out for. This is\n> an extreme simplification of a real-life incident:\n>\n> One file (folder1/firstfile.txt) is deleted independently in two\n> branches, and another somewhat-similar file (folder2/secondfile.txt)\n> is renamed (to folder2/secondfile_renamed.txt) and slightly modified\n> in one of them (in another commit).\n>\n> When the branch with the rename gets merged in to the branch that just\n> had the delete, \"ort\" sees the rename as having been of\n> \"folder1/firstfile.txt\" to \"folder2/secondfile_renamed.txt\", despite\n> this being of a lower similarity than the real rename that happened,\n> and a conflict ensues.\n\nVery interesting case; thanks for passing it along.  I thought Junio\nhad brought up this case while reviewing patches several months back\nand we discussed it, but I can't find it right now.  The short answer\nis that yes there's a difference in behavior, but no bug.  I'll\nsummarize and provide a 'TAKEAWAY' in the final paragraph, but there's\nlots of nuance here that probably deserves explaining for the curious.\n\nWARNING: lengthy details follow; skip to final paragraph of the whole\nemail if you want to skim\n\n\nSo, I'm assuming you're curious about why there's no bug despite a\ndifference in behavior.  So, let me explain (a) the crux of your\ntestcase -- what's happening and why, (b) similar-ish cases with\nbehavioral changes that were explicitly discussed and documented in\nthe past year (for BOTH merge-ort and merge-recursive), (c) some\nsimilar cases not discussed and documented, and for which the\nrecursive backend gives a \"worse\" answer according to what you\nsuggested \"worse\" meant, and (d) some warning/advice for folks dealing\nwith multiple files/directories whose contents are quite similar.\n\n=== (a) what's happening and why ===\n\nIn your testcase, you can drop all files other than\n  * folder1/firstfile.txt\n  * folder2/secondfile.txt\n  * folder2/secondfile_renamed.txt\nand any commits not touching those files can be dropped.  In simpler\nterms, your testcase is:\n  * Merge base: Has both folder1/firstfile.txt and folder2/secondfile.txt\n  * feature branch: delete folder1/firstfile.txt\n  * master branch: delete both folder1/firstfile.txt and\nfolder2/secondfile.txt, introduce folder2/secondfile_renamed.txt which\nis very similar to both deleted files, but more so to the latter\nIf you're thinking my description of the master branch is funny (as\nper your wording, you renamed folder2/secondfile.txt to\nfolder2/secondfile_renamed.txt), remember that git doesn't track\nrenames.\n\nSo, when git goes to merge, renames between the merge base say there\nhave been two files deleted and one new one added.  Since\nfolder2/secondfile.txt was unmodified in the feature branch, any\nrenames affecting it won't result in three-way content merges anyway,\nand thus was removed from rename detection.  That only leaves\nfolder1/firstfile.txt and folder2/secondfile_renamed.txt left to even\ncompare, and since it only compares those two, it matches them up as a\nrename.  That explains what is happening here, and why.\n\nNote that this particular change came from my \"Optimization batch 9\"\nin merge ort, and was the optimization that I think was more important\nthan all the others combined.\n\nBut some, seeing this case in isolation, might be thinking\n\"regression\", so let's dive into more nuance...\n\n\n=== (b) similar-ish cases discussed and documented explicitly in the\npast year ===\n\nWe decided in \"Optimization batch 7\" to actually relax the \"best\nmatch\" criteria.  Note that we changed the documentation in commit\n07c9a7fcb5 (\"gitdiffcore doc: mention new preliminary step for rename\ndetection\", 2021-02-14) to include the following:\n\n'''\nSo, for example, if a deleted\ndocs/ext.txt and an added docs/config/ext.txt are similar enough, they\nwill be marked as a rename and prevent an added docs/ext.md that may\nbe even more similar to the deleted docs/ext.txt from being considered\nas the rename destination in the later step.\n'''\n\nThis was related to some discussions we had around performance,\nincluding the following statement I made at the time:\n\n'''\nWe will give up \"optimal\" matches, but as long as what we provide are\n\"reasonable\" matches I think that should suffice.  I personally\nbelieve \"reasonable\" at O(N) cost trumps \"optimal\" at O(N^2).\n'''\n\n(It may also be worth noting that the optimization affecting your\ntestcase, from \"batch 9\", was one that often provides reasonable\nrenames at O(0) cost; O(0) is even more of an improvement over O(N^2)\nthan O(N) is.)\n\nSomewhat interesting here is that this \"Optimization batch 7\" isn't\njust new to merge-ort; it also affects merge-recursive.  So if we\nchanged your testcase as follows:\n  * feature branch: make a small tweak to both folder1/firstfile.txt\nand folder2/secondfile.txt\n  * master branch: delete both folder1/firstfile.txt and\nfolder2/secondfile.txt, and introduce newfolder/firstfile.txt that is\nmore similar to folder2/secondfile.txt\nthen both merge-ort and merge-recursive today will match up the\nfolder1/firstfile.txt -> newfolder/firstfile.txt.  (Whereas a year\nago, it would have matched up folder2/secondfile.txt ->\nnewfolder/firstfile.txt).\n\n\nBut the nuance goes a bit further...\n\n=== (c) some similar cases not discussed and documented, and for which\nthe recursive backend gives a \"worse\" answer by your explanation of\n\"worse\" as being that it gives conflicts ===\n\nIf you modified your testcase slightly:\n  * feature branch: modify folder1/firstfile.txt slightly\nand as a reminder, the other branches were:\n  * Merge base: Has both folder1/firstfile.txt and folder2/secondfile.txt\n  * master branch: delete both folder1/firstfile.txt and\nfolder2/secondfile.txt, introduce folder2/secondfile_renamed.txt which\nis very similar to both deleted files, but more so to the latter\n\nThen merge-recursive will fail with conflicts while merge-ort will\nsucceed without any.\n\nIs that better?  Worse?  For which backend?  Before you make your\ncall, let's consider the following slightly different case:\n  * Merge base: Has files A & B (very similar, but not exact)\n  * feature branch: Modify B, in an area where it differs from A\n  * master branch: Copy A to C (while modifying it slightly in the\narea it differs from B) in one commit, then delete B in another\ncommit.\n\nFrom the point of view of \"best matches\", we would have \"A was left\nalone, B is modified slightly on one side and deleted on the other,\nand C is a new file\" so the result should be \"the original A, the new\nC from master, and a modify/delete conflict on B\".  However,\nmerge-recursive and merge-ort will instead claim there was a B->C\nrename and since they have conflicting content changes in the same\narea, fill C with conflict markers from these \"unrelated\" files that\nthe user then has to separate.\n\nSo, should merge-ort and merge-recursive do copy detection in order to\nget the \"best\" matches?  Practically speaking, doing so means not only\ndropping the recent optimizations that sped up rename detection by a\nfew orders of magnitude, we're actually talking about taking the slow\nversion of merge-recursive from before this year and slowing it down a\nfew extra orders of magnitude in order to get copy detection -- making\nit overall several orders of magnitude slower than today's merge-ort.\n\nBut maybe you still think this is a correctness issue, and performance\nis irrelevant.  So let's go a little further in the nuance, so I can\ndemonstrate that \"best matches\" actually can give you demonstrably and\nlaughably wrong results:\n\n=== (d) some warning/advice for folks dealing with multiple files\nwhose contents are quite similar (or even multiple directories of\nfiles whose contents are quite similar) ===\n\nDuring the testing of merge-ort, I dug through many repositories and\nremerged all existing merges to see which might give different results\nwith merge-ort vs. Git v2.30's merge-recursive.  I did find some,\nthough they came from the basename-guided matching change (discussed\nin my section (b) above) rather than the unmodified-one-on-side change\n(the case you pointed out in your email).  However, every single one\nof the examples I found came from an interesting type of situation: it\nappears that a number of big projects sometimes make a complete copy\nof some directory (a library, a driver, whatever), and keep them both.\nMany times this might be to keep one stable, while making\nmodifications to the other copy to add new features or abilities.\nIt's also possible that there was an earlier rename involved before we\ngot the current two names as well.  So, with that in mind here's a\nquestion: what do you do when cherry-picking new features added to an\nolder version of the code?  If we use your \"highest percentage match\"\nas you mentioned earlier, we'll likely end up applying the\ncherry-picked changes to the _stable_ files rather than the new\nversion, because the copy meant to be stable is more similar to the\nolder version.  That's likely the wrong target.  But it gets worse...\n\nSome new feature is probably going to touch several files in the\nrelevant directory, not just one.  That raises the question of where\ndo the files each match individually?  I saw multiple examples where\nthe \"best\" match for individual files left half the files matching the\ncurrent stable version of the library/driver/whatever, and the other\nhalf of the files matched against the new version of the\nlibrary/driver/whatever.  That means that porting those patches using\nmerge/cherry-pick/rebase/etc. is going to apply half the patches to\none copy and the other half of the patches to the other copy.  That\njust cannot possibly be right.  merge-ort didn't fix this, it\nbasically just meant it'd sometimes choose a slightly different mix of\napplication targets, but still split them across the two copies.\nWell, technically merge-ort is marginally better here because the\ndirectory-rename-guided-optimizations in merge-ort means that it's\nslightly more likely to apply all the changes to one directory than\nmerge-recursive is.  But only slightly.  So these are situations where\nboth algorithms are likely to provide results that users will almost\ncertainly classify as wrong (and maybe even as \"extremely wrong\").\n\nIf your repository is one where each file is pretty unique, then\nrename detection seems to be a lot more reasonable and straightforward\nto just run automatically.  But if you have multiple near copies of\nthe same file, and especially if you have multiple near copies of the\nsame directory, then relying on git's automatic rename detection\nwithout double checking is a bad idea.  Git does a good job during a\nmerge of printing out which files it has detected as renames and\ndisplaying which files have three-way content merges performed on\nthem, so I'd recommend looking at those a lot closer if you've got\nmultiple near copies of the same file or directories.\n\n> Is ort supposed to choose the \"best\" rename choice, for a given set of\n> trees, and failing to do so here? Or is this a case of recursive\n> *accidentally* doing a better thing?\n\nAs noted above, neither the ort nor recursive strategies promise to\nchoose the \"best\" rename (by which I presume you mean closest match);\nthey both have situations where they'll pick a different one when\nthere are multiple choices.  Further, as shown above, finding the\noptimal rename choice is an ill-posed problem space when dealing with\nmultiple near-copies of the same files or directories.  I would not\nlabel either recursive's or ort's behavior as \"correct\" or \"better\"\nfor your testcase (nor as \"incorrect\" or \"worse\").  As to your last\nquestion, while there have been cases in the past of the recursive\nstrategy accidentally getting good results in some cases (e.g. due to\nserendipitous cancellation of different bugs for certain inputs),\nthere's no such accident in anything I've discussed here that I've\nfound; it's all a clear expected result of the algorithms in question.\nI hope that this all answers your particular questions, but I think\nthere's a deeper point here that is important for people to generally\nrealize for this situation or others like it:\n\n\nTAKEAWAY: Whenever you are dealing with multiple files or directories\nthat are near matches, the person doing merges/rebases/whatever really\ndoes need to be responsible to pay close attention to any such\nfiles/directories (and this is not new to merge-ort; it has always\nbeen an issue with merge-recursive as well).\n"},{"id":"440931","messageId":"xmqqfss2lbsv.fsf@gitster.g","threadId":"56742","inReplyTo":"CABPp-BFAf+-ULwtd7WowsN2KSeJ0s1ucZZ1QSRYg8J+wM9MrZw@mail.gmail.com","subject":"Re: Unexpected conflict with ort merge strategy?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-11-11T19:41:52Z","receivedAt":"2021-11-11T19:41:58Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren <newren@gmail.com> writes:\n\n> TAKEAWAY: Whenever you are dealing with multiple files or directories\n> that are near matches, the person doing merges/rebases/whatever really\n> does need to be responsible to pay close attention to any such\n> files/directories (and this is not new to merge-ort; it has always\n> been an issue with merge-recursive as well).\n\nOne difference is that merge-recursive has fewer magic heuristics\n(for example, it did not have \"my neighbours moved, so I should\").\n\nLess clever tools may burden the human users with more manual\nresolution in more cases, but when the heuristics work against the\nhuman user, it is easier to understand the situation (iow why/how\nthe tool made a wrong decision) because they are more predictable.\n\nIt is a balancing act.  We would prefer to see things more automated\nwhen there is no room for ambiguity, but a heuristics that works\ncorrectly 80% of the time would force human users to watch out for\nmistakes the tool may make in the 20% of the time, which means they\nneed to look for mistakes in _all_ merges made by the tool, which is\nnot something we would want.  That is the takeaway.\n\nThanks.\n"},{"id":"453971","messageId":"CAPMMpoj_aZTgiviv0OBYb-SwhgL9oecbBYkS9LQjcTf0cPmABg@mail.gmail.com","threadId":"56742","inReplyTo":"CABPp-BFAf+-ULwtd7WowsN2KSeJ0s1ucZZ1QSRYg8J+wM9MrZw@mail.gmail.com","subject":"Re: Unexpected conflict with ort merge strategy?","fromName":"Tao Klerks","fromEmail":"tao@klerks.biz","sentAt":"2022-04-20T11:10:26Z","receivedAt":"2022-04-20T11:10:45Z","isPatch":false,"sender":{"key":"tao@klerks.biz","avatar":"https://avatars.githubusercontent.com/u/531704?v=4"},"body":"Sorry for resurrecting such an old thread, and thanks again for your\ndetailed response last year.\n\nOn Thu, Nov 11, 2021 at 6:57 PM Elijah Newren <newren@gmail.com> wrote:\n>\n> Sorry for the late response...\n>\n> On Tue, Oct 19, 2021 at 3:44 PM Tao Klerks <tao@klerks.biz> wrote:\n> >\n> > Hi folks,\n> >\n> > I just came across a situation where the ort merge strategy chooses a\n> > \"worse\" rename mapping than the recursive strategy - worse in the\n> > sense of having a lower similarity score, worse in the sense of having\n> > been a change in another commit (but I guess this is just a limitation\n> > of git merge? It doesn't look for renames \"iteratively\" through\n> > history when merging?), and finally worse in the sense of causing a\n> > merge conflict that, given the previous two points, is unnecessary and\n> > does not occur with recursive.\n> >\n> >\n> > I've prepared a reproduction script, attached. It's probably a little\n> > convoluted because I didn't know exactly what to look out for. This is\n> > an extreme simplification of a real-life incident:\n> >\n> > One file (folder1/firstfile.txt) is deleted independently in two\n> > branches, and another somewhat-similar file (folder2/secondfile.txt)\n> > is renamed (to folder2/secondfile_renamed.txt) and slightly modified\n> > in one of them (in another commit).\n> >\n> > When the branch with the rename gets merged in to the branch that just\n> > had the delete, \"ort\" sees the rename as having been of\n> > \"folder1/firstfile.txt\" to \"folder2/secondfile_renamed.txt\", despite\n> > this being of a lower similarity than the real rename that happened,\n> > and a conflict ensues.\n>\n> Very interesting case; thanks for passing it along.  I thought Junio\n> had brought up this case while reviewing patches several months back\n> and we discussed it, but I can't find it right now.  The short answer\n> is that yes there's a difference in behavior, but no bug.  I'll\n> summarize and provide a 'TAKEAWAY' in the final paragraph, but there's\n> lots of nuance here that probably deserves explaining for the curious.\n>\n> WARNING: lengthy details follow; skip to final paragraph of the whole\n> email if you want to skim\n>\n>\n> So, I'm assuming you're curious about why there's no bug despite a\n> difference in behavior.  So, let me explain (a) the crux of your\n> testcase -- what's happening and why, (b) similar-ish cases with\n> behavioral changes that were explicitly discussed and documented in\n> the past year (for BOTH merge-ort and merge-recursive), (c) some\n> similar cases not discussed and documented, and for which the\n> recursive backend gives a \"worse\" answer according to what you\n> suggested \"worse\" meant, and (d) some warning/advice for folks dealing\n> with multiple files/directories whose contents are quite similar.\n>\n> === (a) what's happening and why ===\n>\n> In your testcase, you can drop all files other than\n>   * folder1/firstfile.txt\n>   * folder2/secondfile.txt\n>   * folder2/secondfile_renamed.txt\n> and any commits not touching those files can be dropped.  In simpler\n> terms, your testcase is:\n>   * Merge base: Has both folder1/firstfile.txt and folder2/secondfile.txt\n>   * feature branch: delete folder1/firstfile.txt\n>   * master branch: delete both folder1/firstfile.txt and\n> folder2/secondfile.txt, introduce folder2/secondfile_renamed.txt which\n> is very similar to both deleted files, but more so to the latter\n> If you're thinking my description of the master branch is funny (as\n> per your wording, you renamed folder2/secondfile.txt to\n> folder2/secondfile_renamed.txt), remember that git doesn't track\n> renames.\n\nI actually disagree with this as a simplification of my testcase. In\nmy testcase, the deletion of \"folder2/secondfile.txt\" and introduction\nof \"folder2/secondfile_renamed.txt\", the \"high-percentage rename\" as I\ncall it, is *separate* from the deletion of \"folder1/firstfile.txt\".\n\nI can understand how any given algorithm might choose to gloss over\nthat fact, but it has very clear significance in my testcase.\nObviously I'm not talking about the \"_renamed\" suffix, but rather the\nfact that in the *individual* commit, rename detection will 100%\ncorrectly/reliably detect this as a rename.\n\nWhen I provided the test case, I assumed this was something like\n\"Recursive uses the information of each commit individually, whereas\nort elides some stuff (and potentially introduces lots of other stuff)\nin the name of performance, hence there seems to be a correctness\nissue here\". I assumed that the \"recursive\" strategy was logically\nequivalent to iteratively merging all the changes, along some chosen\npath from the merge base (eg the shortest?), and ort was... something\nelse. Hence my assumption that in this case, where iteratively merging\nmaster into will get you the *right* result, regardless of whether you\nchoose \"recursive\" or \"ort\" to do it, there was a correctness\nregression in ort.\n\nIf I understand some of what you describe below correctly, this is an\nincorrect understanding of \"recursive\" - it does not, then, do the\nequivalent of iteratively merging all the commits along some selected\npath from the merge base.\n\nInsofar as a majority of my users (and, I suspect, a majority of git\nusers overall) typically deal with large merges in a context where\nsome upstream branch has had lots of changes, very iteratively, and\n*there is meaning* in those iterations, it scares me a bit to think\nthat users are at risk of getting painful or wrong merge outcomes\nbecause that upstream branch's history is actually being ignored, or\nnot used to its max potential. I would welcome some more-primitive and\nslow algorithm that could use the *knowledge* that\n\"folder2/secondfile_renamed.txt\" was in fact a rename of\n\"folder2/secondfile.txt\", as encoded in one of the individual commits\nin the path from the merge base to the tip being merged in. I would\nwant to be able to offer this \"slower, but more correct\" algorithm to\nmy users when a merge turned out to be more conflictive than they\nmight have expected, as here.\n\n(of course, I may have misread chunks of what you are saying here - my\nconclusion here is strongly focused on your, in my opinion\ncorrectness-damaging, simplification of my test case)\n\n>\n> So, when git goes to merge, renames between the merge base say there\n> have been two files deleted and one new one added.  Since\n> folder2/secondfile.txt was unmodified in the feature branch, any\n> renames affecting it won't result in three-way content merges anyway,\n> and thus was removed from rename detection.  That only leaves\n> folder1/firstfile.txt and folder2/secondfile_renamed.txt left to even\n> compare, and since it only compares those two, it matches them up as a\n> rename.  That explains what is happening here, and why.\n>\n> Note that this particular change came from my \"Optimization batch 9\"\n> in merge ort, and was the optimization that I think was more important\n> than all the others combined.\n>\n> But some, seeing this case in isolation, might be thinking\n> \"regression\", so let's dive into more nuance...\n>\n>\n> === (b) similar-ish cases discussed and documented explicitly in the\n> past year ===\n>\n> We decided in \"Optimization batch 7\" to actually relax the \"best\n> match\" criteria.  Note that we changed the documentation in commit\n> 07c9a7fcb5 (\"gitdiffcore doc: mention new preliminary step for rename\n> detection\", 2021-02-14) to include the following:\n>\n> '''\n> So, for example, if a deleted\n> docs/ext.txt and an added docs/config/ext.txt are similar enough, they\n> will be marked as a rename and prevent an added docs/ext.md that may\n> be even more similar to the deleted docs/ext.txt from being considered\n> as the rename destination in the later step.\n> '''\n>\n> This was related to some discussions we had around performance,\n> including the following statement I made at the time:\n>\n> '''\n> We will give up \"optimal\" matches, but as long as what we provide are\n> \"reasonable\" matches I think that should suffice.  I personally\n> believe \"reasonable\" at O(N) cost trumps \"optimal\" at O(N^2).\n> '''\n>\n> (It may also be worth noting that the optimization affecting your\n> testcase, from \"batch 9\", was one that often provides reasonable\n> renames at O(0) cost; O(0) is even more of an improvement over O(N^2)\n> than O(N) is.)\n>\n> Somewhat interesting here is that this \"Optimization batch 7\" isn't\n> just new to merge-ort; it also affects merge-recursive.  So if we\n> changed your testcase as follows:\n>   * feature branch: make a small tweak to both folder1/firstfile.txt\n> and folder2/secondfile.txt\n>   * master branch: delete both folder1/firstfile.txt and\n> folder2/secondfile.txt, and introduce newfolder/firstfile.txt that is\n> more similar to folder2/secondfile.txt\n> then both merge-ort and merge-recursive today will match up the\n> folder1/firstfile.txt -> newfolder/firstfile.txt.  (Whereas a year\n> ago, it would have matched up folder2/secondfile.txt ->\n> newfolder/firstfile.txt).\n>\n>\n> But the nuance goes a bit further...\n>\n> === (c) some similar cases not discussed and documented, and for which\n> the recursive backend gives a \"worse\" answer by your explanation of\n> \"worse\" as being that it gives conflicts ===\n>\n> If you modified your testcase slightly:\n>   * feature branch: modify folder1/firstfile.txt slightly\n> and as a reminder, the other branches were:\n>   * Merge base: Has both folder1/firstfile.txt and folder2/secondfile.txt\n>   * master branch: delete both folder1/firstfile.txt and\n> folder2/secondfile.txt, introduce folder2/secondfile_renamed.txt which\n> is very similar to both deleted files, but more so to the latter\n>\n> Then merge-recursive will fail with conflicts while merge-ort will\n> succeed without any.\n>\n> Is that better?  Worse?  For which backend?  Before you make your\n> call, let's consider the following slightly different case:\n>   * Merge base: Has files A & B (very similar, but not exact)\n>   * feature branch: Modify B, in an area where it differs from A\n>   * master branch: Copy A to C (while modifying it slightly in the\n> area it differs from B) in one commit, then delete B in another\n> commit.\n>\n> From the point of view of \"best matches\", we would have \"A was left\n> alone, B is modified slightly on one side and deleted on the other,\n> and C is a new file\" so the result should be \"the original A, the new\n> C from master, and a modify/delete conflict on B\".  However,\n> merge-recursive and merge-ort will instead claim there was a B->C\n> rename and since they have conflicting content changes in the same\n> area, fill C with conflict markers from these \"unrelated\" files that\n> the user then has to separate.\n\nMy knowledge of copy-detection is very limited - I don't know what\npurpose it serves, when it is used, etc. I've always assumed that from\na \"file destiny\" perspective, creating a copy, without removing/moving\nthe original, should have no impact on where later changes to the\noriginal are considered to go - they stay with the original, even if\nit drastically changes. I would only ever expect rename detection to\nkick in if one thing was added, and another removed, in the *same*\ncommit.\n\nIf I were to apply an \"iterative-ort\" algorithm (that is, first merge\nin the \"Copy A to C\" commit, then merge in the \"delete B\" commit,\nusing ort both times), I would get the \"best match\" outcome you\ndescribe, right?\n\n>\n> So, should merge-ort and merge-recursive do copy detection in order to\n> get the \"best\" matches?  Practically speaking, doing so means not only\n> dropping the recent optimizations that sped up rename detection by a\n> few orders of magnitude, we're actually talking about taking the slow\n> version of merge-recursive from before this year and slowing it down a\n> few extra orders of magnitude in order to get copy detection -- making\n> it overall several orders of magnitude slower than today's merge-ort.\n\nI'm not sure I understand what copy-detection has to do with it - is\nyour point here that by identifying a copy and carrying that knowledge\nforward, you can avoid a later deletion of the original being\n*mistaken* for a rename? That sounds... very reasonable, but given\nyour description of impact on performance, maybe sub-optimal.\n\nI assume adding this copy-detection would still, in practice, perform\nbetter than my imaginary \"iterative-ort\" algorithm?\n\n>\n> But maybe you still think this is a correctness issue, and performance\n> is irrelevant.  So let's go a little further in the nuance, so I can\n> demonstrate that \"best matches\" actually can give you demonstrably and\n> laughably wrong results:\n>\n> === (d) some warning/advice for folks dealing with multiple files\n> whose contents are quite similar (or even multiple directories of\n> files whose contents are quite similar) ===\n>\n> During the testing of merge-ort, I dug through many repositories and\n> remerged all existing merges to see which might give different results\n> with merge-ort vs. Git v2.30's merge-recursive.  I did find some,\n> though they came from the basename-guided matching change (discussed\n> in my section (b) above) rather than the unmodified-one-on-side change\n> (the case you pointed out in your email).  However, every single one\n> of the examples I found came from an interesting type of situation: it\n> appears that a number of big projects sometimes make a complete copy\n> of some directory (a library, a driver, whatever), and keep them both.\n> Many times this might be to keep one stable, while making\n> modifications to the other copy to add new features or abilities.\n> It's also possible that there was an earlier rename involved before we\n> got the current two names as well.  So, with that in mind here's a\n> question: what do you do when cherry-picking new features added to an\n> older version of the code?  If we use your \"highest percentage match\"\n> as you mentioned earlier, we'll likely end up applying the\n> cherry-picked changes to the _stable_ files rather than the new\n> version, because the copy meant to be stable is more similar to the\n> older version.  That's likely the wrong target.  But it gets worse...\n>\n> Some new feature is probably going to touch several files in the\n> relevant directory, not just one.  That raises the question of where\n> do the files each match individually?  I saw multiple examples where\n> the \"best\" match for individual files left half the files matching the\n> current stable version of the library/driver/whatever, and the other\n> half of the files matched against the new version of the\n> library/driver/whatever.  That means that porting those patches using\n> merge/cherry-pick/rebase/etc. is going to apply half the patches to\n> one copy and the other half of the patches to the other copy.\n\nIf I understand you correctly, this is a problem that both \"recursive\"\nand \"ort\" share, but my imaginary \"iterative-ort\" does not. Is that\nright?\n\n> That\n> just cannot possibly be right.  merge-ort didn't fix this, it\n> basically just meant it'd sometimes choose a slightly different mix of\n> application targets, but still split them across the two copies.\n> Well, technically merge-ort is marginally better here because the\n> directory-rename-guided-optimizations in merge-ort means that it's\n> slightly more likely to apply all the changes to one directory than\n> merge-recursive is.  But only slightly.  So these are situations where\n> both algorithms are likely to provide results that users will almost\n> certainly classify as wrong (and maybe even as \"extremely wrong\").\n>\n> If your repository is one where each file is pretty unique, then\n> rename detection seems to be a lot more reasonable and straightforward\n> to just run automatically.  But if you have multiple near copies of\n> the same file, and especially if you have multiple near copies of the\n> same directory, then relying on git's automatic rename detection\n> without double checking is a bad idea.  Git does a good job during a\n> merge of printing out which files it has detected as renames and\n> displaying which files have three-way content merges performed on\n> them, so I'd recommend looking at those a lot closer if you've got\n> multiple near copies of the same file or directories.\n>\n> > Is ort supposed to choose the \"best\" rename choice, for a given set of\n> > trees, and failing to do so here? Or is this a case of recursive\n> > *accidentally* doing a better thing?\n>\n> As noted above, neither the ort nor recursive strategies promise to\n> choose the \"best\" rename (by which I presume you mean closest match);\n> they both have situations where they'll pick a different one when\n> there are multiple choices.  Further, as shown above, finding the\n> optimal rename choice is an ill-posed problem space when dealing with\n> multiple near-copies of the same files or directories.  I would not\n> label either recursive's or ort's behavior as \"correct\" or \"better\"\n> for your testcase (nor as \"incorrect\" or \"worse\").  As to your last\n> question, while there have been cases in the past of the recursive\n> strategy accidentally getting good results in some cases (e.g. due to\n> serendipitous cancellation of different bugs for certain inputs),\n> there's no such accident in anything I've discussed here that I've\n> found; it's all a clear expected result of the algorithms in question.\n> I hope that this all answers your particular questions, but I think\n> there's a deeper point here that is important for people to generally\n> realize for this situation or others like it:\n>\n>\n> TAKEAWAY: Whenever you are dealing with multiple files or directories\n> that are near matches, the person doing merges/rebases/whatever really\n> does need to be responsible to pay close attention to any such\n> files/directories (and this is not new to merge-ort; it has always\n> been an issue with merge-recursive as well).\n\nThis conclusion I find deeply scary and problematic. If I have 1000\nusers of a repo, and there are 3 sections of the folder structure that\nhave been split off / duplicated, and many of these users might change\nthe original ones or the copies, you're saying *all* of these users\nmerging \"upstream\" changes down into their feature branches need to be\n*aware* of the \"there are multiple similar directories\" problem, and\nneed to *actively* recheck that git is not doing anything \"wrong\" by\neliding commit history when merging, even in the absence of warning or\nconflicts from the tool???\n\nSorry if I'm misunderstanding and mischaracterizing... but this\nseems... bad. It seems very much in violation of the general principle\nthat Junio outlined that \"[users needing] to look for mistakes in\n_all_ merges made by the tool, [...] is\nnot something we would want.\"\n\nUnderstanding that the default choice of merge strategy needs to make\ncompromises, and apparently recursive *already* made these particular\ncompromises, is there in fact an \"iterative along the shortest merge\npath\", or \"iterative-ort\" strategy or that I could try / play with, in\nterms of performance testing? In practice, I think the *process* of\nfaking/prototyping this would actually be a kind of \"reverse-rebase\":\n* Assuming I have a series of commits on \"master\" that, taken together\nwithout copy-detection, can be \"misinterpreted\", and that I want to\nmerge master into a feature branch:\n* Checkout a new branch from master, creating temporary branch\n\"merge-outcome-candidate\"\n* Rebase onto feature (resolving any conflicts along the way,\npotentially over several/many steps, and *without* --rebase-merges),\nresulting in an iterately-merged / resolved tree\n* Check out feature\n* Merge in master with --no-commit\n* \"git add  .\" to fake-resolve any conflicts\n* \"git restore merge-outcome-candidate -- *\" to reuse the\niteratively-merged tree as the merge outcome\n* \"git commit\", pretending this was a regular merge\n\nDoes anything logically equivalent to this exist?\n\nDo you agree that it would in principle address the correctness issues\ndiscussed here, no matter how poorly it might perform?\n\nThanks,\nTao\n"},{"id":"454048","messageId":"CABPp-BHF5j9XTrJOreHMaQ+TrZB1VgZvs-Bq2vFD1yhLBdkV3A@mail.gmail.com","threadId":"56742","inReplyTo":"CAPMMpoj_aZTgiviv0OBYb-SwhgL9oecbBYkS9LQjcTf0cPmABg@mail.gmail.com","subject":"Re: Unexpected conflict with ort merge strategy?","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-04-21T03:21:25Z","receivedAt":"2022-04-21T03:21:42Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Apr 20, 2022 at 4:10 AM Tao Klerks <tao@klerks.biz> wrote:\n>\n> Sorry for resurrecting such an old thread, and thanks again for your\n> detailed response last year.\n>\n> On Thu, Nov 11, 2021 at 6:57 PM Elijah Newren <newren@gmail.com> wrote:\n> >\n> > Sorry for the late response...\n> >\n> > On Tue, Oct 19, 2021 at 3:44 PM Tao Klerks <tao@klerks.biz> wrote:\n> > >\n[...]\n> > === (a) what's happening and why ===\n> >\n> > In your testcase, you can drop all files other than\n> >   * folder1/firstfile.txt\n> >   * folder2/secondfile.txt\n> >   * folder2/secondfile_renamed.txt\n> > and any commits not touching those files can be dropped.  In simpler\n> > terms, your testcase is:\n> >   * Merge base: Has both folder1/firstfile.txt and folder2/secondfile.txt\n> >   * feature branch: delete folder1/firstfile.txt\n> >   * master branch: delete both folder1/firstfile.txt and\n> > folder2/secondfile.txt, introduce folder2/secondfile_renamed.txt which\n> > is very similar to both deleted files, but more so to the latter\n> > If you're thinking my description of the master branch is funny (as\n> > per your wording, you renamed folder2/secondfile.txt to\n> > folder2/secondfile_renamed.txt), remember that git doesn't track\n> > renames.\n>\n> I actually disagree with this as a simplification of my testcase. In\n> my testcase, the deletion of \"folder2/secondfile.txt\" and introduction\n> of \"folder2/secondfile_renamed.txt\", the \"high-percentage rename\" as I\n> call it, is *separate* from the deletion of \"folder1/firstfile.txt\".\n>\n> I can understand how any given algorithm might choose to gloss over\n> that fact, but it has very clear significance in my testcase.\n> Obviously I'm not talking about the \"_renamed\" suffix, but rather the\n> fact that in the *individual* commit, rename detection will 100%\n> correctly/reliably detect this as a rename.\n>\n> When I provided the test case, I assumed this was something like\n> \"Recursive uses the information of each commit individually, whereas\n> ort elides some stuff (and potentially introduces lots of other stuff)\n> in the name of performance, hence there seems to be a correctness\n> issue here\". I assumed that the \"recursive\" strategy was logically\n> equivalent to iteratively merging all the changes, along some chosen\n> path from the merge base (eg the shortest?), and ort was... something\n> else. Hence my assumption that in this case, where iteratively merging\n> master into will get you the *right* result, regardless of whether you\n> choose \"recursive\" or \"ort\" to do it, there was a correctness\n> regression in ort.\n>\n> If I understand some of what you describe below correctly, this is an\n> incorrect understanding of \"recursive\" - it does not, then, do the\n> equivalent of iteratively merging all the commits along some selected\n> path from the merge base.\n\nYes, recursive looks at exactly 3 commits -- the merge base, HEAD, and\nthe tip of the other branch being merged.  The history of how it got\nthere is ignored.\n\nThis is documented explicitly, and the manuals even provide an example\nfor users who mistakenly assume that the merge algorithm looks at\nindividual commits.  The particular example in the manual shows that\nthe merge algorithm handles that case in a way that could negatively\nsurprise such users.  Look for \"if a change is made on both branches,\nbut later reverted on one of the branches\" in either the git-merge or\ngit-rebase manpages.\n\n> Insofar as a majority of my users (and, I suspect, a majority of git\n> users overall) typically deal with large merges in a context where\n> some upstream branch has had lots of changes, very iteratively, and\n> *there is meaning* in those iterations, it scares me a bit to think\n> that users are at risk of getting painful or wrong merge outcomes\n> because that upstream branch's history is actually being ignored, or\n> not used to its max potential.\n\nIgnored is correct; the history is only used to find the merge base\n(or merge bases).\n\n> I would welcome some more-primitive and\n> slow algorithm that could use the *knowledge* that\n> \"folder2/secondfile_renamed.txt\" was in fact a rename of\n> \"folder2/secondfile.txt\", as encoded in one of the individual commits\n> in the path from the merge base to the tip being merged in. I would\n> want to be able to offer this \"slower, but more correct\" algorithm to\n> my users when a merge turned out to be more conflictive than they\n> might have expected, as here.\n\nSuch an idea was suggested early on when git was introduced (and I\nthink other version control systems did something along those lines\nfor different reasons).  IIRC, Linus flatly rejected it saying the\nthree commit handling is better.  However, we didn't have pluggable\nmerge backends back then.  We do now.  So, if you want to write a new\nmerge algorithm that folks could use which inspects each individual\ncommit between the merge base and the two branches being merged, feel\nfree.\n\n[...]\n> > Is that better?  Worse?  For which backend?  Before you make your\n> > call, let's consider the following slightly different case:\n> >   * Merge base: Has files A & B (very similar, but not exact)\n> >   * feature branch: Modify B, in an area where it differs from A\n> >   * master branch: Copy A to C (while modifying it slightly in the\n> > area it differs from B) in one commit, then delete B in another\n> > commit.\n> >\n> > From the point of view of \"best matches\", we would have \"A was left\n> > alone, B is modified slightly on one side and deleted on the other,\n> > and C is a new file\" so the result should be \"the original A, the new\n> > C from master, and a modify/delete conflict on B\".  However,\n> > merge-recursive and merge-ort will instead claim there was a B->C\n> > rename and since they have conflicting content changes in the same\n> > area, fill C with conflict markers from these \"unrelated\" files that\n> > the user then has to separate.\n>\n> My knowledge of copy-detection is very limited - I don't know what\n> purpose it serves, when it is used, etc. I've always assumed that from\n> a \"file destiny\" perspective, creating a copy, without removing/moving\n> the original, should have no impact on where later changes to the\n> original are considered to go - they stay with the original, even if\n> it drastically changes. I would only ever expect rename detection to\n> kick in if one thing was added, and another removed, in the *same*\n> commit.\n\nIf there's a copy and the original is later renamed (or deleted), how\ndoes the merge algorithm tell which filename is the original one?\nEspecially given that recursive/ort only look at the endpoints and not\nthe individual intermediate commits?\n\n> If I were to apply an \"iterative-ort\" algorithm (that is, first merge\n> in the \"Copy A to C\" commit, then merge in the \"delete B\" commit,\n> using ort both times), I would get the \"best match\" outcome you\n> describe, right?\n\nAn iterative merge algorithm that handles commits individually has all\nkinds of research issues (including questions about either extremely\nheavily nested conflicts or else N+M separate conflict resolution\nsteps for users to wade through for each merge).  I don't assume I\nknow how such an algorithm would work or behave.\n\nI'm sure you'd probably code it to give you the \"most similar within a\nsingle commit\" match since that's what's important to you, but I don't\nknow how that pans out in the wider scheme of things.\n\n[...]\n> > === (d) some warning/advice for folks dealing with multiple files\n> > whose contents are quite similar (or even multiple directories of\n> > files whose contents are quite similar) ===\n> >\n> > During the testing of merge-ort, I dug through many repositories and\n> > remerged all existing merges to see which might give different results\n> > with merge-ort vs. Git v2.30's merge-recursive.  I did find some,\n> > though they came from the basename-guided matching change (discussed\n> > in my section (b) above) rather than the unmodified-one-on-side change\n> > (the case you pointed out in your email).  However, every single one\n> > of the examples I found came from an interesting type of situation: it\n> > appears that a number of big projects sometimes make a complete copy\n> > of some directory (a library, a driver, whatever), and keep them both.\n> > Many times this might be to keep one stable, while making\n> > modifications to the other copy to add new features or abilities.\n> > It's also possible that there was an earlier rename involved before we\n> > got the current two names as well.  So, with that in mind here's a\n> > question: what do you do when cherry-picking new features added to an\n> > older version of the code?  If we use your \"highest percentage match\"\n> > as you mentioned earlier, we'll likely end up applying the\n> > cherry-picked changes to the _stable_ files rather than the new\n> > version, because the copy meant to be stable is more similar to the\n> > older version.  That's likely the wrong target.  But it gets worse...\n> >\n> > Some new feature is probably going to touch several files in the\n> > relevant directory, not just one.  That raises the question of where\n> > do the files each match individually?  I saw multiple examples where\n> > the \"best\" match for individual files left half the files matching the\n> > current stable version of the library/driver/whatever, and the other\n> > half of the files matched against the new version of the\n> > library/driver/whatever.  That means that porting those patches using\n> > merge/cherry-pick/rebase/etc. is going to apply half the patches to\n> > one copy and the other half of the patches to the other copy.\n>\n> If I understand you correctly, this is a problem that both \"recursive\"\n> and \"ort\" share, but my imaginary \"iterative-ort\" does not. Is that\n> right?\n\n\"recursive\" and \"ort\" both share this quality, yes.  It's hard to\nopine on an imaginary algorithm, though since it seems to be the\nmotivating factor for your new algorithm I would assume you'd either\nsolve that case or find it too hard and give up.  (Note that I have no\nidea if achieving this goal of yours is easy or hard.)\n\n> > That\n> > just cannot possibly be right.  merge-ort didn't fix this, it\n> > basically just meant it'd sometimes choose a slightly different mix of\n> > application targets, but still split them across the two copies.\n> > Well, technically merge-ort is marginally better here because the\n> > directory-rename-guided-optimizations in merge-ort means that it's\n> > slightly more likely to apply all the changes to one directory than\n> > merge-recursive is.  But only slightly.  So these are situations where\n> > both algorithms are likely to provide results that users will almost\n> > certainly classify as wrong (and maybe even as \"extremely wrong\").\n> >\n> > If your repository is one where each file is pretty unique, then\n> > rename detection seems to be a lot more reasonable and straightforward\n> > to just run automatically.  But if you have multiple near copies of\n> > the same file, and especially if you have multiple near copies of the\n> > same directory, then relying on git's automatic rename detection\n> > without double checking is a bad idea.  Git does a good job during a\n> > merge of printing out which files it has detected as renames and\n> > displaying which files have three-way content merges performed on\n> > them, so I'd recommend looking at those a lot closer if you've got\n> > multiple near copies of the same file or directories.\n> >\n> > > Is ort supposed to choose the \"best\" rename choice, for a given set of\n> > > trees, and failing to do so here? Or is this a case of recursive\n> > > *accidentally* doing a better thing?\n> >\n> > As noted above, neither the ort nor recursive strategies promise to\n> > choose the \"best\" rename (by which I presume you mean closest match);\n> > they both have situations where they'll pick a different one when\n> > there are multiple choices.  Further, as shown above, finding the\n> > optimal rename choice is an ill-posed problem space when dealing with\n> > multiple near-copies of the same files or directories.  I would not\n> > label either recursive's or ort's behavior as \"correct\" or \"better\"\n> > for your testcase (nor as \"incorrect\" or \"worse\").  As to your last\n> > question, while there have been cases in the past of the recursive\n> > strategy accidentally getting good results in some cases (e.g. due to\n> > serendipitous cancellation of different bugs for certain inputs),\n> > there's no such accident in anything I've discussed here that I've\n> > found; it's all a clear expected result of the algorithms in question.\n> > I hope that this all answers your particular questions, but I think\n> > there's a deeper point here that is important for people to generally\n> > realize for this situation or others like it:\n> >\n> >\n> > TAKEAWAY: Whenever you are dealing with multiple files or directories\n> > that are near matches, the person doing merges/rebases/whatever really\n> > does need to be responsible to pay close attention to any such\n> > files/directories (and this is not new to merge-ort; it has always\n> > been an issue with merge-recursive as well).\n>\n> This conclusion I find deeply scary and problematic. If I have 1000\n> users of a repo, and there are 3 sections of the folder structure that\n> have been split off / duplicated, and many of these users might change\n> the original ones or the copies, you're saying *all* of these users\n> merging \"upstream\" changes down into their feature branches need to be\n> *aware* of the \"there are multiple similar directories\" problem, and\n> need to *actively* recheck that git is not doing anything \"wrong\" by\n> eliding commit history when merging, even in the absence of warning or\n> conflicts from the tool???\n>\n> Sorry if I'm misunderstanding and mischaracterizing... but this\n> seems... bad. It seems very much in violation of the general principle\n> that Junio outlined that \"[users needing] to look for mistakes in\n> _all_ merges made by the tool, [...] is\n> not something we would want.\"\n>\n> Understanding that the default choice of merge strategy needs to make\n> compromises, and apparently recursive *already* made these particular\n> compromises, is there in fact an \"iterative along the shortest merge\n> path\", or \"iterative-ort\" strategy or that I could try / play with, in\n> terms of performance testing?\n\nNo such thing exists to my knowledge.  Michael Haggerty's git-imerge\n(imerge == incremental merge) is similar-ish, but it avoids doing each\nstep by trying to bisect through to find where you first hit\nconflicts; if it doesn't hit conflicts, it skips over a large range of\ncommits.  That might be problematic for you, since handling multiple\ncommits at once might result in the \"best match\" for a rename picking\nthe most similar match over the range of commits rather than most\nsimilar within individual commits.  But perhaps the git-imerge code is\nuseful to you and you can modify it in some fashion to actually run\nthrough each individual commit.\n"}]}