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

From: Sergey Organov <[email-masked]>
Date: Wed, 14 Mar 2018 10:21:46 +0300

Hi Buga,

Igor Djordjevic <[email-masked]> writes:

> Hi Sergey,
>
> On 13/03/2018 17:10, Sergey Organov wrote:
>> 
>> > 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')
>> 
>> I wonder if it's OK to exchange the order of heads in the first merge
>> (also dropped C for brevity):
>
> It should be, being "left" or "right" hand side ("theirs" or "ours") 
> of the three-way merge shouldn`t matter, they`re still both equally 
> compared to the merge-base.
>
>> git checkout --detach A'
>> git merge-recursive A -- A' M
>> tree=$(git write-tree)
>> git merge-recursive B -- $tree B'
>> tree=$(git write-tree)
>> M'=$(git log --pretty=%B -1 M | git commit-tree -pA' -pB')
>> 
>> If so, don't the first 2 lines now read: "rebase (first parent of) M on
>> top of A'"?
>
> Hmm, lol, yes...? :) So basically, this:
>
> (1)	git checkout --detach M
> 	git merge-recursive A -- M A'
> 	tree=$(git write-tree)
> 	...
>
> ... is equivalent to this:
>
> (2)	git checkout --detach A'
> 	git merge-recursive A -- A' M
> 	tree=$(git write-tree)
> 	...
>
> ..., being equivalent to this:
>
> (3)	git checkout --detach A'
> 	git cherry-pick -m 1 M
> 	tree=$(git write-tree)
> 	...
>
> ..., where in all three cases that `$tree` is equivalent to U1' we 
> discussed about so much already :)

Exactly, and thanks for noticing that it's actually U1', that happens to
soon become rather handy, see below.

> I tested it like this as well, slightly modifying previously sent out 
> script (like this one[1]), and it still seems to be working ;) Nice!

Very nice of you, thanks!

Yet another outcome of this transformation is that the fist step is now
free to (and probably should) utilize all the options (-s, -X, etc.)
that usual rebase has:

git-rebase-first-parent --onto A' M
tree=$(git write-tree)

where 'git-rebase-first-parent' is whatever machinery is currently being
used to rebase simple non-merge commit.

[

Moreover, Phillip's method could further be transformed to what is in
RFC, not that I think it should, see below. Just for the sake of
completeness though, here is the essential missing transformation that
makes Phillip's method symmetric, after which it becomes true special
case of the RFC with particular rebase-first-parent implementation:

git checkout --detach A'
git merge-recursive A -- A' M
tree_U1'=$(git write-tree)
git checkout --detach B'
git merge-recursive B -- B' M
tree_U2'=$(git write-tree)
git merge-recursive M -- $tree_U1' $tree_U2'
tree=$(git write-tree)
M'=$(git log --pretty=%B -1 M | git commit-tree -pA' -pB')

]

>
>> If so, then it could be implemented so that it reduces back to regular
>> rebase of non-merges when applied to a single-parent commit, similar to
>> the method in the RFC, striking out one of advantages of the RFC.
>
> I guess so, but I think it now boils down only to what one finds 
> easier to reason about even more.

I actually think there is more to it. It's incremental asymmetric nature
of the Phillip's approach that I now find rather appealing and worth to
be used in practice.

While the RFC approach, being entirely symmetric, is nice from the POV
of theory and reasoning, yet simple to implement, the actual user
interface of Git is inherently asymmetric with respect to merges (one
merges side-branch(es) to mainline), so asymmetric approach of the
Phillip's method should give smoother user experience, even if only
because of 1 less merge.

There are still 2 issues about the implementation that need to be
discussed though:

1. Still inverted order of the second merge compared to RFC.

It'd be simple to "fix" again, except I'm not sure it'd be better, and
as there is no existing experiences with this step to follow, it
probably should be left as in the original, where it means "merge the
changes made in B' (w.r.t B) into our intermediate version of the
resulting merge".

The original Phillip's version seems to better fit the asymmetry between
mainline and side-branch handling.

The actual difference will be only in the order of ours vs theirs in
conflicts though, and thus it's not that critical.

2. The U1' == U2' consistency check in RFC that I still think is worth
to be implemented.

In application to the method being discussed, we only need the check if
the final merge went without conflicts, so the user was not already
involved, and the check itself is then pretty simple:

 "proceed without stop only if $tree = $tree_U1'"

Its equivalence to the U1' == U2' test in the RFC follows from the fact
that if M' is non-conflicting merge of U1' and U2', then M' == U1' if
and only if U2' == U1'.

Finally, here is a sketch of the implementation that I'd suggest to
use:

git-rebase-first-parent --onto A' M
tree_U1'=$(git write-tree)
git merge-recursive B -- $tree_U1' B'
tree=$(git write-tree)
M'=$(git log --pretty=%B -1 M | git commit-tree -pA' -pB')
[ $conflicted_last_merge = "yes" ] ||
  trees-match $tree_U1' $tree || 
  stop-for-user-amendment

where 'git-rebase-first-parent' denotes whatever machinery is currently
being used to rebase simple non-merge commit. Handy approximation of
which for stand-alone scripting is:

git checkout --detach A' && git cherry-pick -m 1 M

[As an interesting note, observe how, after all, that original Johannes
Sixt's idea of rebasing of merge commit by cherry-picking its first
parent is back there.]

-- Sergey