Re: [RFC] Rebasing merges: a jorney to the ultimate solution (Road Clear)

[Johannes Schindelin <Johannes.Schindelin@gmx.de>]

Hi Phillip,

On Fri, 2 Mar 2018, Phillip Wood wrote:

> On 01/03/18 05:39, Sergey Organov wrote:
> > 
> > Igor Djordjevic <igor.d.djordjevic@gmail.com> writes:
> > 
> >> On 28/02/2018 06:19, Sergey Organov wrote:
> >>>
> >>>>> (3) ---X1---o---o---o---o---o---X2
> >>>>>        |\                       |\
> >>>>>        | A1---A2---A3---U1      | A1'--A2'--A3'--U1'
> >>>>>        |             \          |
> >>>>>        |              M         |
> >>>>>        |             /          |
> >>>>>        \-B1---B2---B3---U2      \-B1'--B2'--B3'--U2'
> >>>>>
> >>>>
> >>>> Meh, I hope I`m rushing it now, but for example, if we had decided to 
> >>>> drop commit A2 during an interactive rebase (so losing A2' from 
> >>>> diagram above), wouldn`t U2' still introduce those changes back, once 
> >>>> U1' and U2' are merged, being incorrect/unwanted behavior...? :/
> >>>
> >>> I think the method will handle this nicely.
> >>
> >> That`s what I thought as well. And then I made a test. And then the 
> >> test broke... Now, might be the test was flawed in the first place, 
> >> but thinking about it a bit more, it does seem to make sense not to 
> >> handle this case nicely :/
> > 
> > Yeah, I now see it myself. I'm sorry for being lazy and not inspecting
> > this more carefully in the first place.
> > 
> > [...]
> > 
> >> So while your original proposal currently seems like it could be 
> >> working nicely for non-interactive rebase (and might be some simpler 
> >> interactive ones), now hitting/acknowledging its first real use 
> >> limit, my additional quick attempt[1] just tries to aid pretty 
> >> interesting case of complicated interactive rebase, too, where we 
> >> might be able to do better as well, still using you original proposal 
> >> as a base idea :)
> > 
> > Yes, thank you for pushing me back to reality! :-) The work and thoughts
> > you are putting into solving the puzzle are greatly appreciated!
> > 
> > Thinking about it overnight, I now suspect that original proposal had a
> > mistake in the final merge step. I think that what you did is a way to
> > fix it, and I want to try to figure what exactly was wrong in the
> > original proposal and to find simpler way of doing it right.
> > 
> > The likely solution is to use original UM as a merge-base for final
> > 3-way merge of U1' and U2', but I'm not sure yet. Sounds pretty natural
> > though, as that's exactly UM from which both U1' and U2' have diverged
> > due to rebasing and other history editing.
> 
> Hi Sergey, I've been following this discussion from the sidelines,
> though I haven't had time to study all the posts in this thread in
> detail. I wonder if it would be helpful to think of rebasing a merge as
> merging the changes in the parents due to the rebase back into the
> original merge. So for a merge M with parents A B C that are rebased to
> A' B' C' the rebased merge M' would be constructed by (ignoring shell
> quoting issues)
> 
> git checkout --detach M
> git merge-recursive A -- M A'
> tree=$(git write-tree)
> git merge-recursive B -- $tree B'
> tree=$(git write-tree)
> git merge-recursive C -- $tree C'
> tree=$(git write-tree)
> M'=$(git log --pretty=%B -1 M | git commit-tree -pA' -pB' -pC')

(The $tree obviously wants to be passed as parameter to commit-tree, but
it's easy to get the idea.)

> This should pull in all the changes from the parents while preserving
> any evil conflict resolution in the original merge. It superficially
> reminds me of incremental merging [1] but it's so long since I looked at
> that I'm not sure if there are any significant similarities.

Interesting.

Basically, this is pretending that A'/B'/C' were not the result of
rebases, but of merges between A/B/C and upstream, and then performing an
octopus merge of M, A', B' and C'.

It is a beautiful application of the duality between merges and rebases:
ideally, they both result in the same tree [*1*].

That is a pretty clean and simple-to-describe paradigm to work off of, and
to reason about.

Ciao,
Dscho

Footnote *1*: I frequently use that duality in work to rebase "clean"
patches on top of upstream, and use that rebased branch to figure out how
to resolve merge conflicts when merging upstream into a long-running
branch (whose tree is identical to the pre-rebase version of the clean
patches). And yes, I *think* that this is essentially Michael Haggerty's
`git-imerge` idea.