{"thread":{"id":"61511","subject":"Replaying merges","startedAt":"2024-05-18T00:35:10Z","lastAt":"2024-05-18T17:50:14Z","messageCount":3,"participants":["Johannes Schindelin","Elijah Newren","Martin von Zweigbergk"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"495021","messageId":"ee35f3b2-bf20-6fcc-2c71-38499aa592fe@gmx.de","threadId":"61511","inReplyTo":null,"subject":"Replaying merges","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2024-05-18T00:35:07Z","receivedAt":"2024-05-18T00:35:10Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Elijah,\n\nI took the suggestion to heart that you explained a couple of times to me:\nTo replay merge commits (including their merge conflict resolutions) by\nusing the _remerged_ commit as merge base, the original merge commit as\nmerge head, and the newly-created merge (with conflicts and all) as HEAD.\n\nI noodled on this idea a bit until I got it into a usable shape that I\napplied to great effect when working on the recent embargoed releases.\n\nHere it is, the script [*1*] that I used (basically replacing all the\n`merge -C` instances in the rebase script with `replay-merge.sh`):\n\n-- snip --\n#!/bin/sh\n\ndie () {\n\techo \"$*\" >&2\n\texit 1\n}\n\ntest $# = 2 ||\ndie \"Usage: $0 <original-merge> <rewritten-merge-head>\"\n\noriginal_merge=\"$(git rev-parse --verify \"$1\")\" ||\ndie \"Not a revision? $1\"\ntest ' ' = \"$(git show -s --format=%P \"$original_merge\" | tr -dc ' ')\" ||\ndie \"Not a merge? $1\"\nrewritten_merge_head=\"$(git rev-parse --verify \"$2\" 2>/dev/null)\" ||\nrewritten_merge_head=\"$(git rev-parse --verify \"refs/rewritten/$2\")\" ||\ndie \"Not a revision? $2\"\n\n# Already merged?\nif test 0 -eq $(git rev-list --count HEAD..$rewritten_merge_head)\nthen\n\techo \"Already merged: $2\" >&2\n\texit 0\nfi\n\n# Can we fast-forward instead?\nif test \"$(git rev-parse HEAD $rewritten_merge_head)\" = \"$(git rev-parse $original_merge^ $original_merge^2)\"\nthen\n\techo \"Fast-forwarding to $1\" >&2\n\texec git merge --no-stat --ff-only $original_merge\n\tdie \"Could not fast-forward to $original_merge\"\nfi\n\n# Only Git v2.45 and newer can handle the `--merge-base=<tree>` invocation\nvalidate_git_version () {\n\tempty_tree=4b825dc642cb6eb9a060e54bf8d69288fbee4904\n\tgit merge-tree --merge-base=$empty_tree $empty_tree $empty_tree >/dev/null 2>&1 ||\n\tdie \"Need a Git version that understands --merge-base=<tree-ish>\"\n}\nvalidate_git_version\n\ndo_merge () {\n\tgit update-ref refs/tmp/head $1 &&\n\tgit update-ref refs/tmp/merge_head $2 &&\n\t{ result=\"$(git merge-tree refs/tmp/head refs/tmp/merge_head)\"; res=$?; } &&\n\techo \"$result\" | head -n 1 &&\n\treturn $res\n}\n\nremerge_original=$(do_merge $original_merge^ $original_merge^2)\ntest -n \"$remerge_original\" || die \"Could not remerge $original_merge\"\nmerge_new=$(do_merge HEAD $rewritten_merge_head)\ntest -n \"$merge_new\" || die \"Could not merge $rewritten_merge_head\"\nnew_tree=$(git merge-tree --merge-base=$remerge_original $original_merge $merge_new | head -n 1)\ntest -n \"$new_tree\" || die \"Could not create new merge\"\n\n# Even though there might be merge conflicts, the `merge-tree` command might\n# succeed with exit code 0! The reason is that the merge conflict may originate\n# from one of the previous two merges.\n\nfiles_with_conflicts=\"$(git diff $original_merge..$new_tree |\n\tsed -ne '/^diff --git /{\n\t\t# store the first file name in the hold area\n\t\ts/^diff --git a\\/\\(.*\\) b\\/.*$/\\1/\n\t\tx\n\t}' -e '/^+<<<<<<< refs\\/tmp\\/head$/{\n\t\t# found a merge conflict\n                :1\n                # read all lines until the ==== line\n                n\n\t\t/^+=======$/b2\n                b1\n                :2\n                # read all lines until the >>>> line\n                /+>>>>>>> refs\\/tmp\\/merge_head$/{\n\t\t\t# print file name\n\t\t\tx\n\t\t\tp\n\t\t\t# skip to next file\n\t\t\t:3\n\t\t\tn\n\t\t\t/^diff --git/{\n\t\t\t\t# store the first file name in the hold area\n\t\t\t\ts/^diff --git a\\/\\(.*\\) b\\/.*$/\\1/\n\t\t\t\tx\n\t\t\t\tb\n\t\t\t}\n\t\t\tb3\n\t\t}\n\t\tn\n\t\tb2\n\t}')\"\n\n# Is it a \"Sync with <version>\" merge? Then regenerate the log\nsync_info=\"$(git cat-file commit $original_merge |\n\tsed -n '/^$/{N;s/^\\n//;/^Sync with 2\\./{N;N;s/^\\(.*\\)\\n\\n\\* \\([^:]*\\).*/\\1,\\2/p};q}')\"\nmerge_msg=\nif test -n \"$sync_info\"\nthen\n\tmerge_msg=\"$(printf '%s\\t\\t%s\\n' $rewritten_merge_head \"${sync_info#*,}\" |\n\t\tgit fmt-merge-msg --log -m \"${sync_info%,*}\" |\n\t\tgrep -v '^#')\"\nfi\n\nif test -z \"$files_with_conflicts\"\nthen\n\t# No conflicts\n\tcommitter=\"$(git var GIT_COMMITTER_IDENT)\" ||\n\tdie \"Could not get committer ident\"\n\tnew_commit=\"$(git cat-file commit \"$original_merge\")\" ||\n\tdie \"Could not get commit message of $original_merge\"\n\tnew_commit=\"$(echo \"$new_commit\" |\n\t\tsed '1,/^$/{\n\t\t\ts/^tree .*/tree '\"$new_tree\"'/\n\t\t\ts/^committer .*/committer '\"$committer\"'/\n\t\t\t/^parent /{\n\t\t\t\t:1\n\t\t\t\tN\n\t\t\t\ts/.*\\n//\n\t\t\t\t/^parent /b1\n\t\t\t\ti\\\nparent '\"$(git rev-parse HEAD)\"'\\\nparent '\"$(git rev-parse $rewritten_merge_head)\"'\n\t\t\t}\n\t\t}')\"\n\tif test -n \"$merge_msg\"\n\tthen\n\t\tnew_commit=\"$(printf '%s\\n\\n%s\\n' \\\n\t\t\t\"$(echo \"$new_commit\" | sed '/^$/q')\" \\\n\t\t\t\"$merge_msg\")\"\n\tfi\n\tnew_commit=\"$(echo \"$new_commit\" | git hash-object -t commit -w --stdin)\" ||\n\tdie \"Could not transmogrify commit object\"\n\tgit merge --no-stat -q --ff-only \"$new_commit\"\nelse\n\techo \"no-ff\" >\"$(git rev-parse --git-path MERGE_MODE)\"\n\tgit rev-parse \"$rewritten_merge_head\" >\"$(git rev-parse --git-path MERGE_HEAD)\"\n\tif test -n \"$merge_msg\"\n\tthen\n\t\techo \"$merge_msg\"\n\telse\n\t\tgit cat-file commit \"$original_merge\" |\n\t\tsed '1,/^$/d'\n\tfi >\"$(git rev-parse --git-path MERGE_MSG)\"\n\n\tgit read-tree -u --reset \"$new_tree\" ||\n\tdie \"Could not update to $new_tree\"\n\n\techo \"$files_with_conflicts\" |\n\twhile read file\n\tdo\n\t\techo \"Needs merge: $file\"\n\t\tmode=\"$(git ls-tree $new_tree \"$file\" | sed 's/ .*//')\" &&\n\t\ta=$(git show \"$new_tree:$file\" |\n\t\t\tsed -e '/^<<<<<<< refs\\/tmp\\/head$/d' \\\n\t\t\t    -e '/^=======$/,/>>>>>>> refs\\/tmp\\/merge_head$/d' |\n\t\t\tgit hash-object -w --stdin) &&\n\t\tb=$(git show \"$new_tree:$file\" |\n\t\t\tsed -e '/^<<<<<<< refs\\/tmp\\/head$/,/^=======$/d' \\\n\t\t\t    -e '/>>>>>>> refs\\/tmp\\/merge_head$/d' |\n\t\t\tgit hash-object -w --stdin) &&\n\t\tprintf \"%s %s %s\\t%s\\n\" \\\n\t\t\t0 $a 0 \"$file\" \\\n\t\t\t$mode $(git rev-parse HEAD:\"$file\") 1 \"$file\" \\\n\t\t\t$mode $a 2 \"$file\" \\\n\t\t\t$mode $b 3 \"$file\" |\n\t\tgit update-index --index-info ||\n\t\tdie \"Could not update the index with '$file'\"\n\tdone\n\tdie \"There were merge conflicts\"\nfi\n-- snap --\n\nFor the most part, this worked beautifully.\n\nHowever. The devil lies in the detail. You will see that the majority of\nthe script is concerned with recreating the stages that need to be put\ninto the index. The reason is that the merge conflicts are already part of\nthe merge base and hence the `merge-tree` arguments do not reflect the\nstages.\n\nBut it gets even worse. The biggest complication is not even addressed in\nthis script, when I realized what was going on, I understood immediately\nthat it was time to abandon the shell script and start implementing this\nlogic in C (which I can currently only do on my own time, which is\nscarce). The biggest complication being the scenario... when a merge\nconflict had been addressed in the original merge commit, but in the\nreplayed merge there is no conflict. In such a scenario, this script _will\ncreate not one, but two merge conflicts, nested ones_!\n\nI still do think that your idea has merit, but I fear that it won't ever\nbe as easy as performing multiple three-way merges in succession. To\naddress the observed problem, the code will always have to be aware of\nunresolved conflicts in the provided merge base, so that it can handle\nthem appropriately, and not treat them as plain text, so that no nested\nconflicts need to be created.\n\nUnfortunately, I did not document properly in what precise circumstances\nthose nested conflicts were generated (I was kind of busy trying to\ncoordinate everything around the security bug-fix releases), but I hope to\nfind some time soon to do so, and to turn them into a set of test cases\nthat we can play with.\n\nCiao,\nJohannes\n\nFootnote *1*: You'd think that I'd learn from past experiences _not_ to\nprototype in Bash when I want to eventually implement it in C. Honestly, I\nthought I could get away with it because I failed to anticipate the many\ncomplications, not the least of which being that there is currently no\n_actually_ correct way to generate the stages. So basically I thought that\nthe script would consist of the part before the code comment starting with\n\"Even though there might be merge conflicts\"...\n"},{"id":"495022","messageId":"CABPp-BHv7K3gQ4+ZgOTFHUyhNm7dVa4wtzy_gtNHKNcyFYqr_g@mail.gmail.com","threadId":"61511","inReplyTo":"ee35f3b2-bf20-6fcc-2c71-38499aa592fe@gmx.de","subject":"Re: Replaying merges","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-05-18T01:45:32Z","receivedAt":"2024-05-18T01:45:44Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi Johannes!\n\nOn Fri, May 17, 2024 at 5:35 PM Johannes Schindelin\n<Johannes.Schindelin@gmx.de> wrote:\n>\n> Hi Elijah,\n>\n> I took the suggestion to heart that you explained a couple of times to me:\n> To replay merge commits (including their merge conflict resolutions) by\n> using the _remerged_ commit as merge base, the original merge commit as\n> merge head, and the newly-created merge (with conflicts and all) as HEAD.\n>\n> I noodled on this idea a bit until I got it into a usable shape that I\n> applied to great effect when working on the recent embargoed releases.\n>\n> Here it is, the script [*1*] that I used (basically replacing all the\n> `merge -C` instances in the rebase script with `replay-merge.sh`):\n>\n<snip>\n> For the most part, this worked beautifully.\n\nCool to see someone try it out.\n\n> However. The devil lies in the detail.\n\nYup, but details rather than detail.  ;-)\n\n<snip>\n> The biggest complication being the scenario... when a merge\n> conflict had been addressed in the original merge commit, but in the\n> replayed merge there is no conflict. In such a scenario, this script _will\n> create not one, but two merge conflicts, nested ones_!\n\nOnly if merge.conflictStyle=\"diff3\"; if merge.conflictStyle=\"merge\",\nthen there will be no nested conflict (since the nested conflict comes\nfrom the fact that the base version had a conflict itself).\n\nThis is one of the issues I noted in my write up a couple years ago:\nhttps://github.com/newren/git/blob/replay/replay-design-notes.txt#L315-L316\n\nFurther, it can get worse, since in the current code the inner\nconflict from the base merge could be an already arbitrarily nested\nmerge conflict with N levels (due to recursive merging allowing\narbitrary nested of merge conflicts), giving us an overall nesting of\nN+1 merge conflicts rather than just the 2 you assumed.  That's ugly\nenough, but we also need to worry about ensuring the conflict markers\nfrom different merges get different conflict marker lengths, which\npresents an extra challenge since the outer merge here is not part of\nthe original recursive merge.\n\nIn addition to these challenges, there's some other ones:\n  * What about when the remerged commit and the newly-created merge\nhave the \"same\" conflict.  Does it actually look the \"same\" to the\ndiff machinery so that it can resolve the conflict away to how the\noriginal merge resolved?  (Answer: not with a naive merge of these\nthree commits; we need to do some extra tweaking.  I'm actually\nsuprised you said this basic idea worked given this particular\nproblem.)\n  * What about conflicts with binary files?  Or non-textual conflicts\nof other types like modify/delete or rename/rename?\n\n> I still do think that your idea has merit, but I fear that it won't ever\n> be as easy as performing multiple three-way merges in succession.\n\nI totally agree we need to do more than the simple merge of those\nthree \"commits\"; I have ideas for this that address some of the\nchallenges over at\nhttps://github.com/newren/git/blob/replay/replay-design-notes.txt#L264-L341\n\n> To address the observed problem, the code will always have to be aware of\n> unresolved conflicts in the provided merge base, so that it can handle\n> them appropriately, and not treat them as plain text, so that no nested\n> conflicts need to be created.\n\nI agree we need to handle conflicts specially -- not only in the\nprovided merge base ('R' in my document) but also in the new merge of\nthe two parents (what you labelled HEAD and I labelled 'N').\n\n> Unfortunately, I did not document properly in what precise circumstances\n> those nested conflicts were generated (I was kind of busy trying to\n> coordinate everything around the security bug-fix releases), but I hope to\n> find some time soon to do so, and to turn them into a set of test cases\n> that we can play with.\n\nYeah, we'll also need to add testcases for some of the other issues I\npoint out in that document.\n\nI'm looking forward to my situation changing soon and hopefully\ngetting more time to work on things like this...\n"},{"id":"495036","messageId":"CANiSa6hU6r-7K_GAyNtO4-_VUHBDfByd6ws3VdZEj4KKrSmryg@mail.gmail.com","threadId":"61511","inReplyTo":"CANiSa6gyNpJ3cUNLD1hFnBYeDFm6aFYv8k41MGvX+C90G8oaaw@mail.gmail.com","subject":"Re: Replaying merges","fromName":"Martin von Zweigbergk","fromEmail":"martinvonz@gmail.com","sentAt":"2024-05-18T17:50:02Z","receivedAt":"2024-05-18T17:50:14Z","isPatch":false,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"Now HTML-free\n\nOn Sat, May 18, 2024 at 9:33 AM Martin von Zweigbergk\n<martinvonz@gmail.com> wrote:\n>\n>\n>\n> On Fri, May 17, 2024, 18:45 Elijah Newren <newren@gmail.com> wrote:\n>>\n>> Hi Johannes!\n>>\n>> On Fri, May 17, 2024 at 5:35 PM Johannes Schindelin\n>> <Johannes.Schindelin@gmx.de> wrote:\n>> >\n>> > Hi Elijah,\n>> >\n>> > I took the suggestion to heart that you explained a couple of times to me:\n>> > To replay merge commits (including their merge conflict resolutions) by\n>> > using the _remerged_ commit as merge base, the original merge commit as\n>> > merge head, and the newly-created merge (with conflicts and all) as HEAD.\n>> >\n>> > I noodled on this idea a bit until I got it into a usable shape that I\n>> > applied to great effect when working on the recent embargoed releases.\n>> >\n>> > Here it is, the script [*1*] that I used (basically replacing all the\n>> > `merge -C` instances in the rebase script with `replay-merge.sh`):\n>> >\n>> <snip>\n>> > For the most part, this worked beautifully.\n>>\n>> Cool to see someone try it out.\n>>\n>> > However. The devil lies in the detail.\n>>\n>> Yup, but details rather than detail.  ;-)\n>>\n>> <snip>\n>> > The biggest complication being the scenario... when a merge\n>> > conflict had been addressed in the original merge commit, but in the\n>> > replayed merge there is no conflict. In such a scenario, this script _will\n>> > create not one, but two merge conflicts, nested ones_!\n>>\n>> Only if merge.conflictStyle=\"diff3\"; if merge.conflictStyle=\"merge\",\n>> then there will be no nested conflict (since the nested conflict comes\n>> from the fact that the base version had a conflict itself).\n>>\n>> This is one of the issues I noted in my write up a couple years ago:\n>> https://github.com/newren/git/blob/replay/replay-design-notes.txt#L315-L316\n>>\n>> Further, it can get worse, since in the current code the inner\n>> conflict from the base merge could be an already arbitrarily nested\n>> merge conflict with N levels (due to recursive merging allowing\n>> arbitrary nested of merge conflicts), giving us an overall nesting of\n>> N+1 merge conflicts rather than just the 2 you assumed.  That's ugly\n>> enough, but we also need to worry about ensuring the conflict markers\n>> from different merges get different conflict marker lengths, which\n>> presents an extra challenge since the outer merge here is not part of\n>> the original recursive merge.\n>>\n>> In addition to these challenges, there's some other ones:\n>>   * What about when the remerged commit and the newly-created merge\n>> have the \"same\" conflict.  Does it actually look the \"same\" to the\n>> diff machinery so that it can resolve the conflict away to how the\n>> original merge resolved?  (Answer: not with a naive merge of these\n>> three commits; we need to do some extra tweaking.  I'm actually\n>> suprised you said this basic idea worked given this particular\n>> problem.)\n>>   * What about conflicts with binary files?  Or non-textual conflicts\n>> of other types like modify/delete or rename/rename?\n>>\n>> > I still do think that your idea has merit, but I fear that it won't ever\n>> > be as easy as performing multiple three-way merges in succession.\n>>\n>> I totally agree we need to do more than the simple merge of those\n>> three \"commits\"; I have ideas for this that address some of the\n>> challenges over at\n>> https://github.com/newren/git/blob/replay/replay-design-notes.txt#L264-L341\n>\n>\n> Another approach is to not eagerly evaluate the auto-merged parent tree and instead do some algebra on the trees. For example, if the parents of the merge commit is calculated by merging tree B and tree C with tree A as base, then you can consider the result as tree B+C-A. If the merge commit itself has tree D and you're rebasing it onto tree E, then the result is E+(D-(B+C-A)). You can then evaluate that by recursively merging the trees as usual. This is effectively what jj does and it works very well.\n>\n> I don't think Git has support for merging more than 3 trees (or tree entries, etc.) at once yet, but that's not very hard. Here's how jj does it: https://github.com/martinvonz/jj/blob/main/lib%2Fsrc%2Fmerge.rs. I think the tests at the end there are quite easy to read and they explain well how it works.\n>\n>\n>\n>\n"}]}