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

[Sergey Organov]

Hi Johannes,

Johannes Schindelin  writes:

> Hi Sergey,
>
> On Mon, 12 Mar 2018, Sergey Organov wrote:
>
>> [...]
>> 
>> Yet another consequence is that my approach will likely result in better
>> code reuse.
>
> This is a purely academic speculation. At least until somebody implements
> Phillip's method. Oh wait, I already started to implement it, and it was
> not exactly hard to implement:
>
> https://github.com/dscho/git/commit/26d2858800a4e0d3cc6313ddb54dd4d2ce516f31

Nice! Please see [1] for some recent relevant discussion.

[1] https://public-inbox.org/git/87efkn6s1h@javad.com/

-- Sergey

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

[Sergey Organov]

Dear Johannes,

Johannes Schindelin  writes:

> Hi Sergey,
>
> On Mon, 12 Mar 2018, Sergey Organov wrote:
>
>> Johannes Schindelin  writes:
>> 
>> > [...]
>> >
>> > Where "easy" meant that I had to spend 1h still to figure out why
>> > using the unrebased merge parents as merge bases.
>> 
>> That's because you try to figure out something that is not there in the
>> [RFC v2]. I suggest to forget everything you've already imagined and
>> just read the [RFC v2] proposal afresh. It should take about 10 minutes
>> or less to get it. Really.
>> 
>> > The same amount of time did not allow me to wrap my head around
>> > Sergey's verbose explanations.
>> 
>> Honestly, I don't believe it, sorry, but I'm willing to explain anything
>> you wish to be explained in _[RFC v2]_.
>
> No, really. If you cannot bring yourself to believe my words, then I hate
> to break it to you: I am not lying.
>
> As to "I'm willing to explain anything you wish to be explained in RFC
> v2": I was asking, and asking, and asking again, for a simple summary of
> the idea behind your proposal. Nothing. That was the answer.

No. The answer rather was this simple explanation that I gave you
multiple times already "rebase each side of the merge, then merge the
results back using original merge commit as the merge base". Yet you say
there was none. I'm confused.

Well, as it seems you grok Phillip's notation just fine, here is RFC
algorithm in this notation [1]:

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')

> I had to figure it out myself: the idea is to *create* fake commits,
> non-merge ones, for every single merge commit parent. Those fake commits
> combine the changes of *all* merge commit parents *but one*. And then
> those commits are rebased, individually, with tons of opportunities for
> merge conflicts. Repeated ones. And then that result is merged.

Wrong. See above.

Anyway, it doesn't matter anymore, see [1].

References:

[1] https://public-inbox.org/git/87efkn6s1h@javad.com

-- Sergey

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

[Johannes Schindelin]

Hi Buga,

On Tue, 13 Mar 2018, Igor Djordjevic wrote:

> On 12/03/2018 11:20, Johannes Schindelin wrote:
> > 
> > > > [...] and cannot introduce ambiguities when rebasing the
> > > > changes introduced by M (i.e. the "amendmendts" we talked about).
> > >
> > > Hmm, not following here, which ambiguities are we talking about?
> > 
> > U1' vs U2' of course. Those are two things that can be different, even if
> > they ideally would have identical trees.
> > 
> > Phillip's strategy does not leave that room for ambiguity.
> 
> Ehm, in Sergey`s approach, this is not an issue, but a feature :)

Well, in my use cases, this would not be a good feature. It would be
highly annoying, confusing, and cost me tons of time.

> If U1' != U2', it just means a more complex rebase happened, but it 
> doesn`t compromise the result (rebased merge) in any way.

No, it just means that your strategy failed to give a consistent answer to
the question "what would the rebased merge commit's tree look like".

> On the other hand, if U1' == U2', we can be pretty sure that merge
> rebasing went as clean as possible.

With the backsplanation I gave for Phillip's strategy, I can be as sure
that rebasing went as clean as possible if it does not produce merge
conflicts: it reconciles the changes introduced by 1) rebasing the merge
tips with the changes introduced by 2) the original merge commit relative
to its parents.

And even if it produces merge conflicts, I know at least that those are
conflicts between those two sets of changes.

Ciao,
Dscho

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

[Johannes Schindelin]

Hi Sergey,

On Mon, 12 Mar 2018, Sergey Organov wrote:

> Johannes Schindelin  writes:
> 
> > [...]
> >
> > Where "easy" meant that I had to spend 1h still to figure out why
> > using the unrebased merge parents as merge bases.
> 
> That's because you try to figure out something that is not there in the
> [RFC v2]. I suggest to forget everything you've already imagined and
> just read the [RFC v2] proposal afresh. It should take about 10 minutes
> or less to get it. Really.
> 
> > The same amount of time did not allow me to wrap my head around
> > Sergey's verbose explanations.
> 
> Honestly, I don't believe it, sorry, but I'm willing to explain anything
> you wish to be explained in _[RFC v2]_.

No, really. If you cannot bring yourself to believe my words, then I hate
to break it to you: I am not lying.

As to "I'm willing to explain anything you wish to be explained in RFC
v2": I was asking, and asking, and asking again, for a simple summary of
the idea behind your proposal. Nothing. That was the answer.

I had to figure it out myself: the idea is to *create* fake commits,
non-merge ones, for every single merge commit parent. Those fake commits
combine the changes of *all* merge commit parents *but one*. And then
those commits are rebased, individually, with tons of opportunities for
merge conflicts. Repeated ones. And then that result is merged.

Except that there is something more convoluted going on because of that
dumb, annoying requirement that this also has to work interactively. Where
somebody like myself might have done something really annoying such as
dropping commits, or even amending them with changes that had not been in
the previous version of the merge commit parents.

So then, after doing a ton of work to rebase the original merge commit's
changes, we perform three-way merges with the already-rebased parents (or
actually, the new tips, because as I pointed out, the parent commit may
have been dropped or reordered) to *undo* those painfully rebased changes.

No matter how much you are married to RFC v2: it *does* do unnecessary
work, it *does* result in a *lot* more opportunity for merge conflicts,
and as a bonus: it even introduces the opportunity to come up with
two versions of the rebased merge commit that disagree with one another.

> > But I'll take your word for it that the strategies are equivalent, and
> > go with the one that has both a simpler explanation (in my mind, at
> > least), and an more robust implementation.
> 
> It's up to you, and it'd still be much better than what we have now, but
> you will need to face the (I think unfortunate) consequences I just
> summarized elsewhere in the thread.

No, it was not up to me. It was up to you to convince me (or for that
matter, anybody else on the Git mailing list), that your approaches are
essentially the same.

But they are not, as your RFC v2 includes a detour of unnecessary work.
Even if the end result is theoretically the same, *practically* your
approach forces a lot of work on the user, work that is often just thrown
away!

Let's take a concrete example. Like, an example that really came up. On
the Git mailing list. A tangible example that shapes my experience, and
more importantly: other Git users' experience as well.

I introduced a change to the funny construct `void *data = data;` that was
meant to fool GCC versions that could not figure out that data would not
be used uninitialized. While that shut up GCC, it upset other compilers
that now said that this new construct does not make sense. My approach was
to introduce the macro `FAKE_INIT(type, name, value)` which would be
expanded to `type name = name;` for GCC, and to `type name = (type)value`
for all other compilers.

This was a change I wanted to cook in Git for Windows for a couple of
iterations until I am sure it works as expected, also on non-Windows
platforms, and with other compilers than MSVC, GCC and Clang.

Recently Ramsay Jones spent the time to research this issue a lot deeper
than it was done before, and found out *which* GCC versions are affected,
and introduced a patch series that fixes this problem for real, *undoing*
the `void *data = data;` mess.

Obviously, this fix conflicts with my work-around.

Okay, good, so what would happen, hypothetically, if the Git garden shears
I use (and which you probably still haven't studied, even if I pointed you
to it several times, but expecting me to read RFC v2 at the same time
instead of answering my questions about it) were adjusted to use RFC v2 to
rebase merges?

To answer that, I first have to tell you that Git for Windows' branch
thicket consists of roughly 70 topic branches that are partially
criss-cross-merged. There are roughly 40 merge commits (44 if I counted
correctly) on the commit graph between HEAD and that work-around that
conflicts with Ramsay's fix.

So the first thing that would happen when rebasing the branch thicket is
this: I would encounter the merge conflict 

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

[Johannes Schindelin]

Hi Sergey,

On Mon, 12 Mar 2018, Sergey Organov wrote:

> Johannes Schindelin  writes:
> > Hi Sergey,
> 
> [...]
> 
> > That is misrepresenting what happened.
> 
> No, it's you who are spreading misinformation, probably unintentional,
> but still.

Way to go, Sergey. Way to go.

> [... more of the same...]
>
> > Let's focus on that strategy rather than going back to the strategy
> > which has known flaws and only an unsatisfyingly complex explanation.
> 
> Not that fast, as it now has no known flaws and still has surprisingly
> simple explanation. It also has its own niceties that are currently
> being discussed elsewhere in the thread.

I find it surprisingly complicated. Of course, that may be just me, but I
am not exactly a noob when it comes to interactive rebases.

Ciao,
Johannes

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

[Johannes Schindelin]

Hi Sergey,

On Mon, 12 Mar 2018, Sergey Organov wrote:

> [...]
> 
> Yet another consequence is that my approach will likely result in better
> code reuse.

This is a purely academic speculation. At least until somebody implements
Phillip's method. Oh wait, I already started to implement it, and it was
not exactly hard to implement:

https://github.com/dscho/git/commit/26d2858800a4e0d3cc6313ddb54dd4d2ce516f31

Ciao,
Johannes

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

[Igor Djordjevic]

Hi Dscho,

On 12/03/2018 11:20, Johannes Schindelin wrote:
> 
> > > [...] and cannot introduce ambiguities when rebasing the
> > > changes introduced by M (i.e. the "amendmendts" we talked about).
> >
> > Hmm, not following here, which ambiguities are we talking about?
> 
> U1' vs U2' of course. Those are two things that can be different, even if
> they ideally would have identical trees.
> 
> Phillip's strategy does not leave that room for ambiguity.

Ehm, in Sergey`s approach, this is not an issue, but a feature :)

If U1' != U2', it just means a more complex rebase happened, but it 
doesn`t compromise the result (rebased merge) in any way.

On the other hand, if U1' == U2', we can be pretty sure that merge 
rebasing went as clean as possible.

That`s the idea, at least.

Regards, Buga

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

[Igor Djordjevic]

Hi Dscho,

On 11/03/2018 23:04, Igor Djordjevic wrote:
> 
> I`m yet to read (and reason about) your whole (very informative) 
> reply, but I just wanted to address this part first, as it might be a 
> clear end-game situation already, due to a mutual agreement, all the 
> rest being purely academic, interesting, but not any more (that) 
> important to discuss.

Ok, here`s the follow-up.

It`s "for discussion sake only", nothing really groundbreaking in 
here, I would think.

On 11/03/2018 16:40, Johannes Schindelin wrote:
> 
> > > > The main problem with this decision is that we still don't see how
> > > > and when to stop for user amendment using this method. OTOH, the
> > > > original has this issue carefully discussed.
> > >
> > > Why would we want to stop, unless there are merge conflicts?
> >
> > Because we can reliably know that something "unusual" happened - and by
> > that I don`t necessarily mean "wrong", but just might be worth user
> > inspection.
> 
> We have a similar conundrum in recursive merges. Remember how multiple
> merge bases are merged recursively? There can be merge conflicts, too, in
> *any* of the individual merges involved, and indeed, there are (under
> relatively rare circumstances).
> 
> Since we already faced that problem, and we already answered it by
> presenting possibly nested merge conflicts, I am in strong favor of
> keeping our new scenario consistent: present possibly-nested merge
> conflicts.

This is something I didn`t really know (possibly-nested merge 
conflicts already being a regular part of Git user experience), 
thanks for explaining it.

In the light of this, I can only agree, let`s keep it consistent.

If anyone ever decides / finds out there`s a better approach in 
regards to user experience, this might get revised, but it`s a 
different beast altogether, yes.

> As far as I understand, one of the arguments in favor of the current
> approach was: there is no good way to tell the user where they are, and
> how to continue from there. So better just to continue and present the
> user with the entire set of conflicts, and have an obvious way out.

Yes, I see this as the main concern, too. I would have expected that 
being in a kind of a "limbo" for a while shouldn`t be too bad, but I 
guess that`s too academic (and inexperienced) thought, and from a 
practical point of view one may not really know how to approach the 
(iterative) conflicts in the first place, not knowing his exact 
position (nor what`s to come)...?

Or, might be we _can_ provide enough clues on where we currently are 
(even if still inside some intermediate state)...? But, this still 
might be a topic for the future, indeed, and unrelated to rebasing 
merges alone (as you pointed out already).

> > For example, situation like this (M is made on A3 with `-s ours`, 
> > obsoleting Bx commits):
> >
> > (1) ---X8--X9 (master)
> >|\
> >| A1---A2---A3
> >| \
> >|  M (topic)
> >| /
> >\-B1---B2---B3
> >
> > ... where we want to rebase M onto X9 is what I would call "usual 
> > stuff", but this situation (M is still made on A3 with `-s ours`, 
> > obsoleting Bx commits, but note cherry-picked B2'):
> >
> > (2) ---X8--B2'--X9 (master)
> >|\
> >| A1---A2---A3
> >| \
> >|  M (topic)
> >| /
> >\-B1---B2---B3
> >
> > ... where we still want to rebase M onto X9 is what we might consider 
> > "unusual", because we noticed that something that shouldn`t be part 
> > of the rebased merge commit (due to previous `-s ours`) actually got 
> > in there (due to later cherry-pick), and just wanting the user to 
> > check and confirm.
> 
> We already have those scenarios when performing a regular interactive
> rebase, where a patch was already applied upstream. In the normal case,
> the user is not even shown B2, thanks to the --cherry-pick option used in
> generating the todo list.
> 
> Granted, in some cases --cherry-pick does not detect that, and then we
> generate a todo list including B2, and when that patch is applied, the
> interactive rebase stops, saying that there are no changes to be
> committed.
> 
> And this behavior is exactly the same with --recreate-merges!
> 
> So I do not think that it would make sense to bother the user *again* when
> rebasing the merge commit.

This seems fair enough. Phillip also pointed out it might be more 
annoyance then help, but as no one was really sure of the possibilities 
we`re discussing here, I thought being better to play it a bit on the 
safe side, for the first time, at least.

I would still like to see more examples of where this U1' == U2' 
check actually helps, and counter ones, where it only serves to annoy. 
Might be we only discover them in the future, though, once the new 
functionality is in use.

> If there are merge conflicts, yes, we will have to. If there are none
> (even if your U1' != 

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

[Sergey Organov]

Hi Johannes,

Johannes Schindelin  writes:

[...]

> The biggest difference is that it is easy for me to see the motivation
> behind Phillip's strategy, whereas I am still puzzled why one would come
> up with a complicated strategy that splits merge commits and re-merges
> them later, and why it should work in general (I still suspect that this
> is not the case).

Because I believe that rebasing simple commit (1 parent) should be
nothing else but reduced version of rebasing any commit (N parents) at
N=1. The [RFC v2] being discussed provides exactly such a method.

OTOH, check what Phillip's version does at N=1. Is it the same as
"rebase simple commit" strategy you already happily use? If not, please
explain why it must be different.

> Where "easy" meant that I had to spend 1h still to figure out why using
> the unrebased merge parents as merge bases.

That's because you try to figure out something that is not there in the
[RFC v2]. I suggest to forget everything you've already imagined and
just read the [RFC v2] proposal afresh. It should take about 10 minutes
or less to get it. Really.

> The same amount of time did not allow me to wrap my head around
> Sergey's verbose explanations.

Honestly, I don't believe it, sorry, but I'm willing to explain anything
you wish to be explained in _[RFC v2]_.

> But I'll take your word for it that the strategies are equivalent, and go
> with the one that has both a simpler explanation (in my mind, at least),
> and an more robust implementation.

It's up to you, and it'd still be much better than what we have now, but
you will need to face the (I think unfortunate) consequences I just
summarized elsewhere in the thread.

-- Sergey

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

[Sergey Organov]

Hi Buga,

Igor Djordjevic  writes:

> Hi Dscho,

[...]

> I think the root of misunderstanding might be coming from the fact
> that Sergey was mainly describing a general concept (without a
> strictly defined implementation strategy, not being restricted to a
> specific one), where Phillip came up with a solution that eventually
> seems to use the same concept (as those transformations above should
> show), but simplifying it further inside a concrete implementation.

As a side-note, starting from sound general concept leaves a hope to
end-up with something like Git, while starting from an implementation,
however nice it is, gives a danger of ending-up with something like Bzr.

-- Sergey

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

[Sergey Organov]

Hi Johannes,

Johannes Schindelin  writes:
> Hi Sergey,

[...]

> That is misrepresenting what happened.

No, it's you who are spreading misinformation, probably unintentional,
but still.

> First, you came up with a strategy. I pointed out shortcomings that
> implied that we cannot use it unchanged. Then, Buga fixed your strategy by
> using additional steps (making the process more complicated than before,
> still without a simple-enough explanation for my liking, fixing the
> shortcomings). Then, Phillip presented a super-simple strategy and Buga
> confirmed that it also fixes the shortcomings I pointed out.

Except that you've missed very essential thing: even before Phillip
presented his method, the original has been fixed and simultaneously
became even simpler. It's now entirely described in [RFC v2] that you
apparently still refuse to read.

> I am very excited that we finally found something that works *and* is easy
> to reason about.

You have chances to be even more exited as we in fact have 2 of them
that both work and are both easy to reason about.

> Let's focus on that strategy rather than going back to the strategy which
> has known flaws and only an unsatisfyingly complex explanation.

Not that fast, as it now has no known flaws and still has surprisingly
simple explanation. It also has its own niceties that are currently
being discussed elsewhere in the thread.

-- Sergey

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

[Sergey Organov]

Hi Buga,

Igor Djordjevic  writes:

[...]

> That said, *if* we decide we like temporary commit U1' == U2' consistency 
> check (especially for non-interactive rebase, maybe), we can produce 
> these after the fact for the sake of the check only.

I don't believe interactive vs. non-interactive split is actually
helpful. I'd consider non-interactive just a special case of interactive
when user didn't edit the todo list, nothing more. No special treatment
should be required.

For one, consistency checks in both modes has similar importance, even
if only because there could be parts of history being interactively
rebased which the user didn't intend to edit, nor actually edited during
given session.

Now let me get back to pros and cons of the two approaches to rebasing
merges we have. Below I still advocate my approach by further discussing
the differences, but simultaneously I'd like to emphasize that whatever
particular way of rebasing merges will finally be used, it will be a
huge step forward and I'm glad I've raised the issue in the first place.

First, please consider the fact that my "rebase sides" method has yet
another nice property: it reduces back to original "rebase the commit"
operation when you apply it to a non-merge commit. In other words, it's
true generalization on top of rebasing of simple commit.

OTOH, Phillip's approach, when reduced to non-merge commit, still does a
version of rebase, but very specific one, and in inverse manner. I.e.,
rather than merging changes of the commit to be rebased into the new
base, it merges changes introduced by the new base into the commit being
rebased.

One consequence is that when conflict occurs, Phillip's approach will
give surprising order of ours vs theirs changes, inverted with respect
to those of the usual rebase of non-merge commit, while my approach will
give exact non-merge commit semantics. It could likely be fixed by
slightly modifying Phillip's approach, but it will make its
implementation more complex.

Another consequence is that, provided my version is used, all options
that tune "simple commit rebase" behavior will automagically work for
rebasing merge commits, in exactly the same manner. OTOH, Phillip's
approach, without special attention in implementation, will do the same
thing no matter what -m -s, or -X options say.

Yet another consequence is that my approach will likely result in better
code reuse. Even though mine seems to be harder to implement stand-alone
than Phillip's one, it should be actually easier to implement inside the
"git rebase", as it will use exactly the same machinery that "git
rebase" already uses to rebase simple commits, adding only final "git
merge-recursive" (or "git merge-resolve", or "git merge-octopus", -- any
of them  will do the job), which current implementation already performs
as well, for re-creating merges from scratch.

Second thought, unrelated to the above. To me it seems that my "rebasing
sides" approach, being entirely symmetric, is cleaner than incremental
merging suggested by Phillip, as with my approach one will still deal
with branches independently, in the same way as for simple commits,
until the single final merge operation. This comes with drawback of 1
additional step in my approach when compared to the Phillip's one
though, but then mine has definitely no issues with the exact order of
merges.

Overall, to me it seems that unmodified Phillip's approach will bring
unnecessarily wide set of new user experiences, and fixing it will
require some tricks in implementation, for no apparent reason.

-- Sergey

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

[Johannes Schindelin]

Hi Buga,

On Sun, 11 Mar 2018, Igor Djordjevic wrote:

> On 11/03/2018 16:47, Johannes Schindelin wrote:
> > 
> > > Having explained all this, I realized this is the same "essentially
> > > merging the new tips into the original pretending that the new tips
> > > were not rebased but merged into upstream" as Phillip`s one, just
> > > that we have additional temporary commits U1 and U2 (as per
> > > mentioned "patch theory") :)
> > 
> > But if the old tips had been merged into upstream (resulting in the
> > new tips), then the merge bases would be *the old tips*.
> 
> Exactly, and that is what part you`ve cut out of the quote was 
> showing :) By Phillip`s implementation, we would start with *old tips* 
> as merge bases, indeed (old tips being U1 and U2 in this case),

I really do not see how it would make sense to take the original merge
commit as merge base in this scenario. It makes no *logical* sense: in
which interpretation did you develop changes in two divergent directions
from that merge commit?

Whereas if you use the old tips as merge bases, you can say very easily
what those two directions were: one merged with other merge parents, the
other direction rebased on top of upstream. There. Two divergent sets of
changes that we want to reconcile ("merge"). Easy as apple pie.

> where it further gets transformed as previously written:
> 
> > git merge-recursive U1 -- M U1'
> > tree="$(git write-tree)"
> > git merge-recursive U2 -- $tree U2'
> > tree="$(git write-tree)"
> > 
> > ..., where we know U1 = U2 = M (in regards to trees), so this is the 
> > same as:
> > 
> > git merge-recursive M -- M U1'
> > tree="$(git write-tree)"
> > git merge-recursive M -- $tree U2'
> > tree="$(git write-tree)"
> 
> Here, `git merge-recursive M -- M U1'` simply equals to U1' tree 
> (being a fast-forward merge), so we can write the two merges above as
> a single merge, too:
> 
> > git merge-recursive M -- U1' U2'
> > tree="$(git write-tree)"
> > 
> > ... which is exactly what Sergey`s (updated) approach suggests, 
> > merging U1' and U2' with M as merge-base (and shown inside that 
> > sample implementation script I provided[1]) :)
> 
> So from *old tips* being the rebased merge base (Phillip), we got to 
> *old merge commit* being the rebased merge base (Sergey), or vice 
> versa. Does this shed a bit more light on it now? Or you wanted to 
> point out something else in the first place...?

Okay, I'll trust you that these stunts show that the two strategies are
equivalent as to what their results are.

The biggest difference is that it is easy for me to see the motivation
behind Phillip's strategy, whereas I am still puzzled why one would come
up with a complicated strategy that splits merge commits and re-merges
them later, and why it should work in general (I still suspect that this
is not the case).

Where "easy" meant that I had to spend 1h still to figure out why using
the unrebased merge parents as merge bases. The same amount of time did
not allow me to wrap my head around Sergey's verbose explanations.

But I'll take your word for it that the strategies are equivalent, and go
with the one that has both a simpler explanation (in my mind, at least),
and an more robust implementation.

> > I am still not sure for what scenarios Phillip's strategy is the same as
> > Sergey's (updated) one, as the former strategy can do completely without
> > temporary commits [...]
> 
> I think the root of misunderstanding might be coming from the fact 
> that Sergey was mainly describing a general concept (without a 
> strictly defined implementation strategy, not being restricted to a 
> specific one), where Phillip came up with a solution that eventually 
> seems to use the same concept (as those transformations above should 
> show), but simplifying it further inside a concrete implementation.

Well, Sergey started off by suggesting the "rebase the patch relatively to
the first parent always" strategy, then came up with a long-ish email
describing a different approach (which I slowly realize is related to the
first strategy, and it would have been *much* appreciated if it was not
left to the reader to figure that one out), then incorporated what I
called your hack (again, no clear and concise description what changed,
just throwing a bunch of big bones to the dogs with the next long-ish
document).

So I will not apologize for stopping to pay so much attention to that
sub-thread at some point.

> By saying that Phillip "simplified it", even though transformations
> shown above might show different, I mean he managed to further decompose
> what Sergey was aiming for, abstracting temporary commits U1 and U2 out
> of the equation, thus making them optional, but not required.

That is not how I read Phillip's mail. It was more like "how about this
instead". And it was simple enough, with clear example how to implement
it, that I thought about that single mail for an hour, until I was

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

[Igor Djordjevic]

Hi Dscho,

I`m yet to read (and reason about) your whole (very informative) 
reply, but I just wanted to address this part first, as it might be a 
clear end-game situation already, due to a mutual agreement, all the 
rest being purely academic, interesting, but not any more (that) 
important to discuss.

On 11/03/2018 16:40, Johannes Schindelin wrote:
> 
> > For myself, I do actually favor Sergey`s approach in general, but 
> > _implemented_ through what Phillip described (or a mixture of both, to 
> > be precise). But, let me explain... :)
> 
> So as you explained later in this sub-thread, Sergey's approach is
> essentially the same as Phillip's.
> 
> I still do not understand Sergey's approach on a fundamental level. I
> mean, I can follow his instructions how to implement his algorithm, but it
> is as if I had a blindfold on and somebody guided me through a maze: I
> understand *what* I am supposed to do, but I have no clue *why*.
> 
> And admittedly, I got very frustrated when a document was thrown my way
> that is too long to read in one sitting, and all of my attempts at getting
> clear and comprehensible answers to specific questions were met with "go
> and read that document, I am sure you will understand then".
> 
> For something as fundamental to my daily workflow as an interactive rebase
> (*especially* when trying to maintain the branch topology), this is no
> good at all.
> 
> Since you already confirmed that there is essentially no difference
> between the two approaches, I will simply go with the one I understand, in
> particular I understand *why* it works.
> 
> But let's read on, maybe I will change my mind based on your explanations
> (which do answer my questions, thank you so much for that)...

No problem, I learned much myself trying to write those explanations 
in the first place, and I still need to read on yet myself, seeing 
how well my explanations actually fared :) Thank you for still 
holding on, though.

But I just wanted to point out that you can really just go with what 
Phillip described if you find that easier to reason about (and/or 
implement), there`s even no need for mind changing, as essentially, 
and in my opinion, it seems to be just a bit different implementation 
of the same concept (but not requiring temporary commits).

That said, *if* we decide we like temporary commit U1' == U2' consistency 
check (especially for non-interactive rebase, maybe), we can produce 
these after the fact for the sake of the check only.

I will come with a follow-up, but all the rest might be less important.

Regards, Buga

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

[Igor Djordjevic]

Hi Dscho,

On 11/03/2018 16:47, Johannes Schindelin wrote:
> 
> > > > Phillip's method is essentially merging the new tips into the original
> > > > merge, pretending that the new tips were not rebased but merged into
> > > > upstream.
> > >
> > > [...]
> > >
> > > Here`s a starting point, two commits A and B, merged into M:
> > >
> > > (3) ---A
> > > \
> > >  M
> > > /
> > > ---B
> > >
> > >
> > > According the "patch theory"[1] (which might not be too popular 
> > > around here, but should serve the purpose for what I`m trying to 
> > > explain), each merge commit can be "transformed" to two non-merge 
> > > commits, one on top of each of the merge parents, where new commit 
> > > brings its original merge parent commit tree to the state of the 
> > > merge commit tree:
> > >
> > > (4) ---A---U1
> > >
> > >
> > >
> > > ---B---U2
> > >
> > >
> > > Now, we have two new commits, U1 and U2, each having the same tree as 
> > > previous merge commit M, but representing changes in regards to 
> > > specific parents - and this is essentially what Sergey`s original 
> > > approach was using (whether he knew it, or not).
> > >
> > > When it comes to rebasing, it`s pretty simple, too. As this:
> > >
> > > (5) ---X1---o---o---o---o---o---X2 (master)
> > >|\
> > >| A1---A2---A3
> > >| \
> > >|  M
> > >| /
> > >\-B1---B2---B3
> > >
> > > ... actually equals this:
> > >
> > > (6) ---X1---o---o---o---o---o---X2 (master)
> > >|\
> > >| A1---A2---A3---U1
> > >|
> > >|
> > >|
> > >\-B1---B2---B3---U2
> > >
> > > ... where trees of M, U1 and U2 are same, and we can use the regular 
> > > rebase semantics and rebase it to this:
> > >
> > > (7) ---X1---o---o---o---o---o---X2 (master)
> > > |\
> > > | A1'--A2'--A3'--U1'
> > > |
> > > |
> > > |
> > > \-B1'--B2'--B3'--U2'
> > >
> > > ... which is essentially this again:
> > >
> > > (8) ---X1---o---o---o---o---o---X2 (master)
> > > |\
> > > | A1'--A2'--A3'
> > > |\
> > > | M'
> > > |/
> > > \-B1'--B2'--B3'
> > >
> >
> > Having explained all this, I realized this is the same "essentially 
> > merging the new tips into the original pretending that the new tips 
> > were not rebased but merged into upstream" as Phillip`s one, just 
> > that we have additional temporary commits U1 and U2 (as per mentioned 
> > "patch theory") :)
> 
> But if the old tips had been merged into upstream (resulting in the new
> tips), then the merge bases would be *the old tips*.

Exactly, and that is what part you`ve cut out of the quote was 
showing :) By Phillip`s implementation, we would start with *old tips* 
as merge bases, indeed (old tips being U1 and U2 in this case), where 
it further gets transformed as previously written:

>   git merge-recursive U1 -- M U1'
>   tree="$(git write-tree)"
>   git merge-recursive U2 -- $tree U2'
>   tree="$(git write-tree)"
> 
> ..., where we know U1 = U2 = M (in regards to trees), so this is the 
> same as:
> 
>   git merge-recursive M -- M U1'
>   tree="$(git write-tree)"
>   git merge-recursive M -- $tree U2'
>   tree="$(git write-tree)"

Here, `git merge-recursive M -- M U1'` simply equals to U1' tree 
(being a fast-forward merge), so we can write the two merges above as
a single merge, too:

>   git merge-recursive M -- U1' U2'
>   tree="$(git write-tree)"
> 
> ... which is exactly what Sergey`s (updated) approach suggests, 
> merging U1' and U2' with M as merge-base (and shown inside that 
> sample implementation script I provided[1]) :)

So from *old tips* being the rebased merge base (Phillip), we got to 
*old merge commit* being the rebased merge base (Sergey), or vice 
versa. Does this shed a bit more light on it now? Or you wanted to 
point out something else in the first place...?

> I am still not sure for what scenarios Phillip's strategy is the same as
> Sergey's (updated) one, as the former strategy can do completely without
> temporary commits [...]

I think the root of misunderstanding might be coming from the fact 
that Sergey was mainly describing a general concept (without a 
strictly defined implementation strategy, not being restricted to a 
specific one), where Phillip came up with a solution that eventually 
seems to use the same concept (as those transformations above should 
show), but simplifying it further inside a concrete implementation.

By saying that Phillip "simplified it", even though transformations 
shown above 

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

[Johannes Schindelin]

Hi Buga,

On Fri, 9 Mar 2018, Igor Djordjevic wrote:

> On 08/03/2018 20:58, Igor Djordjevic wrote:
> > 
> > > Phillip's method is essentially merging the new tips into the original
> > > merge, pretending that the new tips were not rebased but merged into
> > > upstream.
> > 
> > [...]
> > 
> > Here`s a starting point, two commits A and B, merged into M:
> > 
> > (3) ---A
> > \
> >  M
> > /
> > ---B
> > 
> > 
> > According the "patch theory"[1] (which might not be too popular 
> > around here, but should serve the purpose for what I`m trying to 
> > explain), each merge commit can be "transformed" to two non-merge 
> > commits, one on top of each of the merge parents, where new commit 
> > brings its original merge parent commit tree to the state of the 
> > merge commit tree:
> > 
> > (4) ---A---U1
> > 
> > 
> > 
> > ---B---U2
> > 
> > 
> > Now, we have two new commits, U1 and U2, each having the same tree as 
> > previous merge commit M, but representing changes in regards to 
> > specific parents - and this is essentially what Sergey`s original 
> > approach was using (whether he knew it, or not).
> > 
> > When it comes to rebasing, it`s pretty simple, too. As this:
> > 
> > (5) ---X1---o---o---o---o---o---X2 (master)
> >|\
> >| A1---A2---A3
> >| \
> >|  M
> >| /
> >\-B1---B2---B3
> > 
> > ... actually equals this:
> > 
> > (6) ---X1---o---o---o---o---o---X2 (master)
> >|\
> >| A1---A2---A3---U1
> >|
> >|
> >|
> >\-B1---B2---B3---U2
> > 
> > ... where trees of M, U1 and U2 are same, and we can use the regular 
> > rebase semantics and rebase it to this:
> > 
> > (7) ---X1---o---o---o---o---o---X2 (master)
> > |\
> > | A1'--A2'--A3'--U1'
> > |
> > |
> > |
> > \-B1'--B2'--B3'--U2'
> > 
> > ... which is essentially this again:
> > 
> > (8) ---X1---o---o---o---o---o---X2 (master)
> > |\
> > | A1'--A2'--A3'
> > |\
> > | M'
> > |/
> > \-B1'--B2'--B3'
> > 
> 
> Having explained all this, I realized this is the same "essentially 
> merging the new tips into the original pretending that the new tips 
> were not rebased but merged into upstream" as Phillip`s one, just 
> that we have additional temporary commits U1 and U2 (as per mentioned 
> "patch theory") :)

But if the old tips had been merged into upstream (resulting in the new
tips), then the merge bases would be *the old tips*.

I am still not sure for what scenarios Phillip's strategy is the same as
Sergey's (updated) one, as the former strategy can do completely without
temporary commits, and cannot introduce ambiguities when rebasing the
changes introduced by M (i.e. the "amendmendts" we talked about).

Ciao,
Dscho

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

[Johannes Schindelin]

Hi Buga,

On Thu, 8 Mar 2018, Igor Djordjevic wrote:

> On 07/03/2018 15:08, Johannes Schindelin wrote:
> > 
> > > > Didn't we settle on Phillip's "perform successive three-way merges
> > > > between the original merge commit and the new tips with the old tips
> > > > as base" strategy?
> > >
> > > It seems you did, dunno exactly why.
> > 
> > That is not true. You make it sound like I was the only one who liked
> > this, and not Phillip and Buga, too.
> 
> For myself, I do actually favor Sergey`s approach in general, but 
> _implemented_ through what Phillip described (or a mixture of both, to 
> be precise). But, let me explain... :)

So as you explained later in this sub-thread, Sergey's approach is
essentially the same as Phillip's.

I still do not understand Sergey's approach on a fundamental level. I
mean, I can follow his instructions how to implement his algorithm, but it
is as if I had a blindfold on and somebody guided me through a maze: I
understand *what* I am supposed to do, but I have no clue *why*.

And admittedly, I got very frustrated when a document was thrown my way
that is too long to read in one sitting, and all of my attempts at getting
clear and comprehensible answers to specific questions were met with "go
and read that document, I am sure you will understand then".

For something as fundamental to my daily workflow as an interactive rebase
(*especially* when trying to maintain the branch topology), this is no
good at all.

Since you already confirmed that there is essentially no difference
between the two approaches, I will simply go with the one I understand, in
particular I understand *why* it works.

But let's read on, maybe I will change my mind based on your explanations
(which do answer my questions, thank you so much for that)...

> > > The main problem with this decision is that we still don't see how
> > > and when to stop for user amendment using this method. OTOH, the
> > > original has this issue carefully discussed.
> > 
> > Why would we want to stop, unless there are merge conflicts?
> 
> Because we can reliably know that something "unusual" happened - and by
> that I don`t necessarily mean "wrong", but just might be worth user
> inspection.

We have a similar conundrum in recursive merges. Remember how multiple
merge bases are merged recursively? There can be merge conflicts, too, in
*any* of the individual merges involved, and indeed, there are (under
relatively rare circumstances).

Since we already faced that problem, and we already answered it by
presenting possibly nested merge conflicts, I am in strong favor of
keeping our new scenario consistent: present possibly-nested merge
conflicts.

As far as I understand, one of the arguments in favor of the current
approach was: there is no good way to tell the user where they are, and
how to continue from there. So better just to continue and present the
user with the entire set of conflicts, and have an obvious way out.

> For example, situation like this (M is made on A3 with `-s ours`, 
> obsoleting Bx commits):
> 
> (1) ---X8--X9 (master)
>|\
>| A1---A2---A3
>| \
>|  M (topic)
>| /
>\-B1---B2---B3
> 
> ... where we want to rebase M onto X9 is what I would call "usual 
> stuff", but this situation (M is still made on A3 with `-s ours`, 
> obsoleting Bx commits, but note cherry-picked B2'):
> 
> (2) ---X8--B2'--X9 (master)
>|\
>| A1---A2---A3
>| \
>|  M (topic)
>| /
>\-B1---B2---B3
> 
> ... where we still want to rebase M onto X9 is what we might consider 
> "unusual", because we noticed that something that shouldn`t be part 
> of the rebased merge commit (due to previous `-s ours`) actually got 
> in there (due to later cherry-pick), and just wanting the user to 
> check and confirm.

We already have those scenarios when performing a regular interactive
rebase, where a patch was already applied upstream. In the normal case,
the user is not even shown B2, thanks to the --cherry-pick option used in
generating the todo list.

Granted, in some cases --cherry-pick does not detect that, and then we
generate a todo list including B2, and when that patch is applied, the
interactive rebase stops, saying that there are no changes to be
committed.

And this behavior is exactly the same with --recreate-merges!

So I do not think that it would make sense to bother the user *again* when
rebasing the merge commit.

If there are merge conflicts, yes, we will have to. If there are none
(even if your U1' != U2'), it would be outright annoying to stop.

> > > "rebase sides of the merge commit and then three-way merge them back
> > > using original merge commit as base"
> > 
> > And that is also wrong, as I had proved already! Only Buga's addition
> > made it robust against dropping/modifying commits, and that addition
> > also makes it more complicated.
> 
> No, this 

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

[Igor Djordjevic]

On 08/03/2018 20:58, Igor Djordjevic wrote:
> 
> > Phillip's method is essentially merging the new tips into the original
> > merge, pretending that the new tips were not rebased but merged into
> > upstream.
> 
> [...]
> 
> Here`s a starting point, two commits A and B, merged into M:
> 
> (3) ---A
> \
>  M
> /
> ---B
> 
> 
> According the "patch theory"[1] (which might not be too popular 
> around here, but should serve the purpose for what I`m trying to 
> explain), each merge commit can be "transformed" to two non-merge 
> commits, one on top of each of the merge parents, where new commit 
> brings its original merge parent commit tree to the state of the 
> merge commit tree:
> 
> (4) ---A---U1
> 
> 
> 
> ---B---U2
> 
> 
> Now, we have two new commits, U1 and U2, each having the same tree as 
> previous merge commit M, but representing changes in regards to 
> specific parents - and this is essentially what Sergey`s original 
> approach was using (whether he knew it, or not).
> 
> When it comes to rebasing, it`s pretty simple, too. As this:
> 
> (5) ---X1---o---o---o---o---o---X2 (master)
>|\
>| A1---A2---A3
>| \
>|  M
>| /
>\-B1---B2---B3
> 
> ... actually equals this:
> 
> (6) ---X1---o---o---o---o---o---X2 (master)
>|\
>| A1---A2---A3---U1
>|
>|
>|
>\-B1---B2---B3---U2
> 
> ... where trees of M, U1 and U2 are same, and we can use the regular 
> rebase semantics and rebase it to this:
> 
> (7) ---X1---o---o---o---o---o---X2 (master)
> |\
> | A1'--A2'--A3'--U1'
> |
> |
> |
> \-B1'--B2'--B3'--U2'
> 
> ... which is essentially this again:
> 
> (8) ---X1---o---o---o---o---o---X2 (master)
> |\
> | A1'--A2'--A3'
> |\
> | M'
> |/
> \-B1'--B2'--B3'
> 

Having explained all this, I realized this is the same "essentially 
merging the new tips into the original pretending that the new tips 
were not rebased but merged into upstream" as Phillip`s one, just 
that we have additional temporary commits U1 and U2 (as per mentioned 
"patch theory") :)

Merging U1' and U2' with M as a base can initially be presented like 
this as well (what Phillip`s approach would yield):

git merge-recursive U1 -- M U1'
tree="$(git write-tree)"
git merge-recursive U2 -- $tree U2'
tree="$(git write-tree)"

..., where we know U1 = U2 = M (in regards to trees), so this is the 
same as:

git merge-recursive M -- M U1'
tree="$(git write-tree)"
git merge-recursive M -- $tree U2'
tree="$(git write-tree)"

..., which can be further simplified, being the same as:

git merge-recursive M -- U1' U2'
tree="$(git write-tree)"

... which is exactly what Sergey`s (updated) approach suggests, 
merging U1' and U2' with M as merge-base (and shown inside that 
sample implementation script I provided[1]) :)

With all this said, I think it`s safe to say these two approaches are 
exactly the same, just Sergey`s being simplified (thus harder to 
initially understand), and the only actual question is whether we 
value U1' and U2' enough, as possible "something suspicious happened" 
indicators, to use them, or not.

I would think yes, but I would be open for more samples of where do 
they become useful for reporting "suspicious activity", too.

Regards, Buga

[1] https://public-inbox.org/git/b11785bd-5c96-43c1-95d8-b28eccfd1...@gmail.com/

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

[Igor Djordjevic]

On 08/03/2018 21:27, Igor Djordjevic wrote:
> 
> > git merge-recursive U1' -- M U2'
> > tree="$(git write-tree)"
> > # in case of original merge being octopus, we would continue like:
> > # git merge-recursive $tree -- M U3'
> > # tree="$(git write-tree)"
> > # git merge-recursive $tree -- M U4'
> > # ... and so on, then finally:
> > git merge-recursive $tree -- "$(git merge-base U1' U2' B1')" B1'
> > # in more general case, it would be:
> > # git merge-recursive $tree -- "$(git merge-base 
> > )" B1'
> > tree="$(git write-tree)"
> > git tag M' "$(git log --pretty=%B -1 M | git commit-tree $tree -p B3' 
> > -p B4 -p B1')"
> 
> That last line should obviously read just:
> 
>   git log --pretty=%B -1 M | git commit-tree $tree -p B3' -p B4 -p B1'
> 
> ..., above mentioned `git tag M'` part being a leftover from my other test 
> script.

Eh, pardon me, I managed to mess up all the merge-recursive lines, 
too, in regards to where the merge-base commit goes... Here`s a 
complete (and corrected) sample:

git merge-recursive M -- U1' U2'
tree="$(git write-tree)"
# in case of original merge being octopus, we would continue like:
# git merge-recursive M -- $tree U3'
# tree="$(git write-tree)"
# git merge-recursive M -- $tree U4'
# ... and so on, then finally:
git merge-recursive "$(git merge-base U1' U2' B1')" -- $tree B1'
# ... or even:
# git merge-recursive "$(git merge-base B3' B4 B1')" -- $tree B1'
# as in more general case, it would be:
# git merge-recursive "$(git merge-base 
)" -- $tree B1'
tree="$(git write-tree)"
git log --pretty=%B -1 M | git commit-tree $tree -p B3' -p B4 -p B1'

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

[Igor Djordjevic]

On 08/03/2018 20:58, Igor Djordjevic wrote:
> 
>   git merge-recursive U1' -- M U2'
>   tree="$(git write-tree)"
>   # in case of original merge being octopus, we would continue like:
>   # git merge-recursive $tree -- M U3'
>   # tree="$(git write-tree)"
>   # git merge-recursive $tree -- M U4'
>   # ... and so on, then finally:
>   git merge-recursive $tree -- "$(git merge-base U1' U2' B1')" B1'
>   # in more general case, it would be:
>   # git merge-recursive $tree -- "$(git merge-base 
> )" B1'
>   tree="$(git write-tree)"
>   git tag M' "$(git log --pretty=%B -1 M | git commit-tree $tree -p B3' 
> -p B4 -p B1')"

That last line should obviously read just:

git log --pretty=%B -1 M | git commit-tree $tree -p B3' -p B4 -p B1'

..., above mentioned `git tag M'` part being a leftover from my other test 
script.

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

[Igor Djordjevic]

Hi Johannes,

On 07/03/2018 15:08, Johannes Schindelin wrote:
> 
> > > Didn't we settle on Phillip's "perform successive three-way merges
> > > between the original merge commit and the new tips with the old tips
> > > as base" strategy?
> >
> > It seems you did, dunno exactly why.
> 
> That is not true. You make it sound like I was the only one who liked
> this, and not Phillip and Buga, too.

For myself, I do actually favor Sergey`s approach in general, but 
_implemented_ through what Phillip described (or a mixture of both, to 
be precise). But, let me explain... :)

> > The main problem with this decision is that we still don't see how and
> > when to stop for user amendment using this method. OTOH, the original
> > has this issue carefully discussed.
> 
> Why would we want to stop, unless there are merge conflicts?

Because we can reliably know that something "unusual" happened - and 
by that I don`t necessarily mean "wrong", but just might be worth 
user inspection.

For example, situation like this (M is made on A3 with `-s ours`, 
obsoleting Bx commits):

(1) ---X8--X9 (master)
   |\
   | A1---A2---A3
   | \
   |  M (topic)
   | /
   \-B1---B2---B3

... where we want to rebase M onto X9 is what I would call "usual 
stuff", but this situation (M is still made on A3 with `-s ours`, 
obsoleting Bx commits, but note cherry-picked B2'):

(2) ---X8--B2'--X9 (master)
   |\
   | A1---A2---A3
   | \
   |  M (topic)
   | /
   \-B1---B2---B3

... where we still want to rebase M onto X9 is what we might consider 
"unusual", because we noticed that something that shouldn`t be part 
of the rebased merge commit (due to previous `-s ours`) actually got 
in there (due to later cherry-pick), and just wanting the user to 
check and confirm.

This is the major reason why I would prefer Sergey`s approach in 
general... and might be I also have a good explanation on *why* it 
works, but let`s get there ;)

(p.s. This is only one, but certainly not the only case)

> > "rebase sides of the merge commit and then three-way merge them back
> > using original merge commit as base"
> 
> And that is also wrong, as I had proved already! Only Buga's addition made
> it robust against dropping/modifying commits, and that addition also makes
> it more complicated.

No, this is actually right, that sentence nicely describing _how_ it 
works. That addition of mine was just including the correct merge 
base (being the original merge commit that we are "rebasing"), and 
that`s what Sergey is talking about.

> And it still has no satisfactory simple explanation why it works.

Getting there... :)

> > > - it is *very easy* to reason about, once it is pointed out that
> > > rebases and merges result in the same trees.
> >
> > The original is as easy to reason about, if not easier, especially as
> > recursive merge strategy is not being used there in new ways.
> 
> So do it. I still have to hear a single-sentence, clear and obvious
> explanation why it works.
> 
> And please do not describe why your original version works, because it
> does not work. Describe why the one amended with Buga's hack works.
> 
> > I honestly don't see any advantages of Phillip's method over the
> > original, except personal preferences. At the same time, I have no
> > objection of using it either, provided consistency check problem is
> > solved there as well.
> 
> Okay, let me reiterate then, because I do not want this point to be
> missed:
> 
> Phillip's method is essentially merging the new tips into the original
> merge, pretending that the new tips were not rebased but merged into
> upstream.
> 
> So it exploits the duality of the rebase and merge operation, which both
> result in identical trees (potentially after resolving merge conflicts).
> 
> I cannot think of any such interpretation for your proposal augmented by
> Buga's fix-ups. And I haven't heard any such interpretation from your
> side, either.

Ok here it goes (I might be still wrong, but please bare with me).

What Sergey originally described also uses the "duality of the rebase 
and merge operation", too ;) Just in a bit different way (and might 
be a more straightforward one?).

Here`s a starting point, two commits A and B, merged into M:

(3) ---A
\
 M
/
---B


According the "patch theory"[1] (which might not be too popular 
around here, but should serve the purpose for what I`m trying to 
explain), each merge commit can be "transformed" to two non-merge 
commits, one on top of each of the merge parents, where new commit 
brings its original merge parent commit tree to the state of the 
merge commit tree:

(4) ---A---U1



---B---U2


Now, we have two new commits, U1 and U2, each having the same tree as 
previous merge commit M, but representing changes in regards to 
specific parents - and this is essentially what Sergey`s original 

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

[Johannes Schindelin]

Hi Sergey,

On Wed, 7 Mar 2018, Sergey Organov wrote:

> Johannes Schindelin  writes:
> >
> > On Wed, 7 Mar 2018, Sergey Organov wrote:
> >
> >> Johannes Schindelin  writes:
> >> 
> >> > On Tue, 6 Mar 2018, Sergey Organov wrote:
> >> >
> >> >> This is v2 of my "Rebasing merges" proposal.
> >> >
> >> > Didn't we settle on Phillip's "perform successive three-way merges
> >> > between the original merge commit and the new tips with the old
> >> > tips as base" strategy?
> >> 
> >> It seems you did, dunno exactly why.
> >
> > That is not true. You make it sound like I was the only one who liked
> > this, and not Phillip and Buga, too.
> >
> > Are you interested in the best solution, or in your solution :-)
> 
> I'm interested in any that works, and only you say that those suggested
> by Phillip is somehow superior. I still believe it's mine that superior,
> even if slightly.

That is misrepresenting what happened.

First, you came up with a strategy. I pointed out shortcomings that
implied that we cannot use it unchanged. Then, Buga fixed your strategy by
using additional steps (making the process more complicated than before,
still without a simple-enough explanation for my liking, fixing the
shortcomings). Then, Phillip presented a super-simple strategy and Buga
confirmed that it also fixes the shortcomings I pointed out.

I am very excited that we finally found something that works *and* is easy
to reason about.

Let's focus on that strategy rather than going back to the strategy which
has known flaws and only an unsatisfyingly complex explanation.

> >> The main problem with this decision is that we still don't see how
> >> and when to stop for user amendment using this method. OTOH, the
> >> original has this issue carefully discussed.
> >
> > Why would we want to stop, unless there are merge conflicts?
> 
> There is somewhat lengthy discussion about it that you probably missed.
> Not to repeat it, just see how 'rerere' works when it fires during
> rebase, even with no conflicts.

I did not miss that discussion. My question was a follow-up: Why would we
want to stop, unless there are merge conflicts?

> >> > It has the following advantages:
> >> >
> >> > - it is *very simple* to describe
> >> 
> >> The original is as simple if not simpler:
> >> 
> >> "rebase sides of the merge commit and then three-way merge them back
> >> using original merge commit as base"
> >
> > And that is also wrong, as I had proved already! Only Buga's addition made
> > it robust against dropping/modifying commits, and that addition also makes
> > it more complicated.
> 
> No. Get your facts straight. The [RFC v2] already fixed that original
> mistake. Could you please finally read it?

I do not see Buga's additions, and it is still a lengthy document that is
hard to understand.

Phillip's alternative, in contrast, fit in at most two 80x25 pages and was
intuitive (at least after seeing that the tree resulting from a merge is
identical to the tree resulting from a rebase, once all merge conflicts
are handled appropriately).

> > And it still has no satisfactory simple explanation why it works.
> 
> It has. It's there in the [RFC v2]. You seem to be the only one who
> doesn't get it. I suppose you just didn't bother to read.

I tried to read it, and got lost in all those figures that really do not
do anything to make this strategy obvious to me.

Granted, I now know *how* it works.

I gave up understanding *why* it is supposed to work.

With Phillip's mail, it only took me 5 minutes to get a rudimentary
understanding why it works.

> >> No problems with octopuses, and no virtual merge bases of recursive
> >> merges to reason about.
> >
> > But those are no problems for Phillip's strategy, either!
> 
> I thought it was you who started to discuss virtual merge bases and
> related problems, as well as how it's difficult to support octopus
> merges, but it's fine with me if there are none of these problems.

Yes, I started explaining virtual merge bases, and how they are used in
the recursive merge. Because I was asked how the recursive merge works,
and I happen to know how it works very intimately.

> > So your point is...?
> 
> Still the same -- use what's better, the [RFC v2].

I strongly disagree that your approach is superior. It is more complex,
and still has no simple answer to the question "why is this supposed to do
what I want it to do?"

It does a lot of criss-crossing, and when I see that, I immediately
suspect that it would lose information e.g. when commits were amended
during the rebase. There are just way too many paths for obsolete changes
to creep in again.

> >> > - it is *very easy* to reason about, once it is pointed out that
> >> > rebases and merges result in the same trees.
> >> 
> >> The original is as easy to reason about, if not easier, especially as
> >> recursive merge strategy is not being used there in new ways.
> >
> > So do it. I still have to hear 

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

[Sergey Organov]

Hi Johannes,

Johannes Schindelin  writes:
> Hi Sergey,
>
> On Wed, 7 Mar 2018, Sergey Organov wrote:
>
>> Johannes Schindelin  writes:
>> 
>> > On Tue, 6 Mar 2018, Sergey Organov wrote:
>> >
>> >> This is v2 of my "Rebasing merges" proposal.
>> >
>> > Didn't we settle on Phillip's "perform successive three-way merges
>> > between the original merge commit and the new tips with the old tips
>> > as base" strategy?
>> 
>> It seems you did, dunno exactly why.
>
> That is not true. You make it sound like I was the only one who liked
> this, and not Phillip and Buga, too.
>
> Are you interested in the best solution, or in your solution :-)

I'm interested in any that works, and only you say that those suggested
by Phillip is somehow superior. I still believe it's mine that superior,
even if slightly.

>
>> The main problem with this decision is that we still don't see how and
>> when to stop for user amendment using this method. OTOH, the original
>> has this issue carefully discussed.
>
> Why would we want to stop, unless there are merge conflicts?

There is somewhat lengthy discussion about it that you probably missed.
Not to repeat it, just see how 'rerere' works when it fires during
rebase, even with no conflicts.

>
>> > It has the following advantages:
>> >
>> > - it is *very simple* to describe
>> 
>> The original is as simple if not simpler:
>> 
>> "rebase sides of the merge commit and then three-way merge them back
>> using original merge commit as base"
>
> And that is also wrong, as I had proved already! Only Buga's addition made
> it robust against dropping/modifying commits, and that addition also makes
> it more complicated.

No. Get your facts straight. The [RFC v2] already fixed that original
mistake. Could you please finally read it?

> And it still has no satisfactory simple explanation why it works.

It has. It's there in the [RFC v2]. You seem to be the only one who
doesn't get it. I suppose you just didn't bother to read.

>> No problems with octopuses, and no virtual merge bases of recursive
>> merges to reason about.
>
> But those are no problems for Phillip's strategy, either!

I thought it was you who started to discuss virtual merge bases and
related problems, as well as how it's difficult to support octopus
merges, but it's fine with me if there are none of these problems.

>
> So your point is...?

Still the same -- use what's better, the [RFC v2].

>
>> > - it is *very easy* to reason about, once it is pointed out that
>> > rebases and merges result in the same trees.
>> 
>> The original is as easy to reason about, if not easier, especially as
>> recursive merge strategy is not being used there in new ways.
>
> So do it. I still have to hear a single-sentence, clear and obvious
> explanation why it works.
>
> And please do not describe why your original version works, because it
> does not work.

Original [RFC] didn't work because of rather simple mistake that I've
already admitted and fixed. [RFC v2] has got the fix. Read [RFC v2] and
get your facts straight.

> Describe why the one amended with Buga's hack works.

It doesn't matter as these hacks are not needed anymore.

>
>> I honestly don't see any advantages of Phillip's method over the
>> original, except personal preferences. At the same time, I have no
>> objection of using it either, provided consistency check problem is
>> solved there as well.
>
> Okay, let me reiterate then, because I do not want this point to be
> missed:
>
> Phillip's method is essentially merging the new tips into the original
> merge, pretending that the new tips were not rebased but merged into
> upstream.
>
> So it exploits the duality of the rebase and merge operation, which both
> result in identical trees (potentially after resolving merge
> conflicts).
>
> I cannot think of any such interpretation for your proposal augmented by
> Buga's fix-ups. And I haven't heard any such interpretation from your
> side, either.

No fix-ups or augmentations are needed. It was a mistake that has been
fixed in [RFC v2]. You've missed essential part of the discussion.

Read the [RFC v2], please:

Significant changes are:

1. Fixed mistake in the final merge step in the original proposal: wrong
   merge base was used.

-- Sergey

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

[Johannes Schindelin]

Hi Sergey,

On Wed, 7 Mar 2018, Sergey Organov wrote:

> Johannes Schindelin  writes:
> 
> > On Tue, 6 Mar 2018, Sergey Organov wrote:
> >
> >> This is v2 of my "Rebasing merges" proposal.
> >
> > Didn't we settle on Phillip's "perform successive three-way merges
> > between the original merge commit and the new tips with the old tips
> > as base" strategy?
> 
> It seems you did, dunno exactly why.

That is not true. You make it sound like I was the only one who liked
this, and not Phillip and Buga, too.

Are you interested in the best solution, or in your solution :-)

> The main problem with this decision is that we still don't see how and
> when to stop for user amendment using this method. OTOH, the original
> has this issue carefully discussed.

Why would we want to stop, unless there are merge conflicts?

> > It has the following advantages:
> >
> > - it is *very simple* to describe
> 
> The original is as simple if not simpler:
> 
> "rebase sides of the merge commit and then three-way merge them back
> using original merge commit as base"

And that is also wrong, as I had proved already! Only Buga's addition made
it robust against dropping/modifying commits, and that addition also makes
it more complicated.

And it still has no satisfactory simple explanation why it works.

> No problems with octopuses, and no virtual merge bases of recursive
> merges to reason about.

But those are no problems for Phillip's strategy, either!

So your point is...?

> > - it is *very easy* to reason about, once it is pointed out that
> > rebases and merges result in the same trees.
> 
> The original is as easy to reason about, if not easier, especially as
> recursive merge strategy is not being used there in new ways.

So do it. I still have to hear a single-sentence, clear and obvious
explanation why it works.

And please do not describe why your original version works, because it
does not work. Describe why the one amended with Buga's hack works.

> I honestly don't see any advantages of Phillip's method over the
> original, except personal preferences. At the same time, I have no
> objection of using it either, provided consistency check problem is
> solved there as well.

Okay, let me reiterate then, because I do not want this point to be
missed:

Phillip's method is essentially merging the new tips into the original
merge, pretending that the new tips were not rebased but merged into
upstream.

So it exploits the duality of the rebase and merge operation, which both
result in identical trees (potentially after resolving merge conflicts).

I cannot think of any such interpretation for your proposal augmented by
Buga's fix-ups. And I haven't heard any such interpretation from your
side, either.

> >> 3. I now use "True Merge" name instead of former "Trivial Merge", to
> >>avoid confusion with what Git documentation calls "trivial merge",
> >>thanks to Junio C Hamano  for pointing this out.
> >
> > "True Merge" is probably also a candidate for improvement. If what you
> > refer to is a "true" merge, that means all others are "untrue"
> > merges???
> 
> [d]evil merges, obviously.
> 
> Seriously, it's pure history joint. Just "joint' will do.

You might want to try harder to stick with the existing nomenclature. That
would make it a lot easier to discuss.

Ciao,
Johannes

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

[Sergey Organov]

Hi Johannes,

Johannes Schindelin  writes:

> Hi Sergey,
>
> On Tue, 6 Mar 2018, Sergey Organov wrote:
>
>> This is v2 of my "Rebasing merges" proposal.
>
> Didn't we settle on Phillip's "perform successive three-way merges between
> the original merge commit and the new tips with the old tips as base"
> strategy?

It seems you did, dunno exactly why.

The main problem with this decision is that we still don't see how and
when to stop for user amendment using this method. OTOH, the original
has this issue carefully discussed.

> It has the following advantages:
>
> - it is *very simple* to describe

The original is as simple if not simpler:

"rebase sides of the merge commit and then three-way merge them back
using original merge commit as base"

No problems with octopuses, and no virtual merge bases of recursive
merges to reason about.

> - it is *very easy* to reason about, once it is pointed out that rebases
>   and merges result in the same trees.

The original is as easy to reason about, if not easier, especially
as recursive merge strategy is not being used there in new ways.

I honestly don't see any advantages of Phillip's method over the
original, except personal preferences. At the same time, I have no
objection of using it either, provided consistency check problem is
solved there as well.

>
> ... and BTW...
>
>> 3. I now use "True Merge" name instead of former "Trivial Merge", to
>>avoid confusion with what Git documentation calls "trivial merge",
>>thanks to Junio C Hamano  for pointing this out.
>
> "True Merge" is probably also a candidate for improvement. If what you
> refer to is a "true" merge, that means all others are "untrue"
> merges???

[d]evil merges, obviously.

Seriously, it's pure history joint. Just "joint' will do.

-- Sergey

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

[Johannes Schindelin]

Hi Sergey,

On Tue, 6 Mar 2018, Sergey Organov wrote:

> This is v2 of my "Rebasing merges" proposal.

Didn't we settle on Phillip's "perform successive three-way merges between
the original merge commit and the new tips with the old tips as base"
strategy? It has the following advantages:

- it is *very simple* to describe

- it is *very easy* to reason about, once it is pointed out that rebases
  and merges result in the same trees.

... and BTW...

> 3. I now use "True Merge" name instead of former "Trivial Merge", to
>avoid confusion with what Git documentation calls "trivial merge",
>thanks to Junio C Hamano  for pointing this out.

"True Merge" is probably also a candidate for improvement. If what you
refer to is a "true" merge, that means all others are "untrue" merges???

Ciao,
Johannes

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

[Sergey Organov]

Hi,

This is v2 of my "Rebasing merges" proposal.

Significant changes are:

1. Fixed mistake in the final merge step in the original proposal: wrong
   merge base was used. Thanks everybody who provided test-cases, and
   special thanks to Igor Djordjevic  for
   implementing and testing a few variants of the method.

2. Added discussion of the exact place where handling of special
   frequent cases such as "git merge -ours", if any, should go.

3. I now use "True Merge" name instead of former "Trivial Merge", to
   avoid confusion with what Git documentation calls "trivial merge",
   thanks to Junio C Hamano  for pointing this out.

During discussion of the original proposal, yet another way of
implementing a true rebase of a merge commit has been suggested by
Phillip Wood [1]. His method also gathers
the changes on both sides of the merge and then merges them back to the
original merge, so both methods have similar concept and differ in
implementation. It looks like both implementations bring the same
result, at least it was so in the limited testing that Igor performed.

[1] 
https://public-inbox.org/git/6c8749ca-ec5d-b4b7-f1a0-50d9ad294...@talktalk.net/


---8<-8<--

By accepting the challenges raised in recent discussion of advanced
support for history rebasing and editing in Git, I hopefully figured out
a clean and elegant method of rebasing merges that I think is "The Right
Way (TM)" to perform this so far troublesome operation. ["(TM)" here has
second meaning: "True Merge" (TM), see below.]

Let me begin with quick outline of the method, to illustrate the
simplicity of the approach, and special thanks here must go to "Johannes
Sixt"  for his original bright idea to use "cherry-pick
-m1" to rebase merge commits.

Given 2 original branches, b1 and b2, and a merge commit M that joins
them, suppose we've already rebased b1 to b1', and b2 to b2'. Suppose
also that B1' and B2' happen to be the tip commits on b1' and b2',
respectively.

To produce merge commit M' that joins b1' and b2', the following
operations will suffice:

1. Checkout b2' and cherry-pick -m2 M, to produce U2' (and new b2').
2. Checkout b1' and cherry-pick -m1 M, to produce U1' (and new b1').
3. Perform 3-way merge of U1' and U2' using original M as merge base,
   to get UM'.
4. Get rid of U1' and U2' by re-writing parent references of UM' from
   U1' and U2' to  B1' and B2', respectively, to produce M'.
5. Mission complete.

Let's now turn to the method itself and see why and how it actually
works.

First off, let me introduce you to my new friend, the True Merge, or
(TM) for short. By definition, (TM) is a merge that brings absolutely
no differences to the sides of the merge. (I also like to call him
"Angel Merge" (AM), both as being the most beautiful of all merges, and
as direct antithesis to "[d]evil merge"; or even "Perfect Merge" (PM),
but the latter goes after lunch time.)

Being trivial history joint and nothing else, (TM)/(AM)/(PM) is safe and
easy to be rebased (see below). However, since most of us have never met
(TM) in practice, you probably wonder how (TM) can actually help us
handle general case of rebasing of some random merge.

Let's start with this history:

M
   / \
  B1  B2

where B1 and B2 are tip commits of 2 branches, and M is the merge commit
that joins them. Let's transform this history to the following one,
contextually equivalent to the original, by introducing 2 non-merge
utility commits U1 and U2, and a new utility merge commit UM:

UM
   /  \
  U1   U2
  ||
  B1   B2

were contents of all the created commits match, and are exact copies of
the original content of M. I.e., provided [A] denotes "content of commit
A", we have:

  [UM] = [U1] = [U2] = [M]

Stress again how these changes to the history preserve the exact content
of the original merge ([UM] = [M]), how U1 an U2 represent content
changes due to the merge on either side[*], and how content of neither
preceding nor subsequent commits is affected by the change of
representation.

Now observe that as [U1] = [UM], and [U2] = [UM], the UM happens to be
exactly our new friend -- the "True Merge (TM)" his true self,
introducing exactly zero changes to content. Pure history joint.

Next, we separately rebase both branches of our new representation of
the history to whatever new base we need, and we get:

  U1'  U2'
  ||
  B1'  B2'

where U1' and U2' are rebased versions of U1 and U2, obtained by usual
rebasing methods for non-merge commits.

Finally, let's merge back our branches.

To perform the right kind of merge, notice that U1' and U2' have
diverged from U1 and U2, respectively. Further, provided [U1] = [U2] =
[UM] = [M], they have both diverged from the original merge commit
M. Therefore, to merge U1' and U2' into UM', it suffices to use 3-way
merge using original M as the merge base:

UM'
   /  \
  U1'  U2'
   \  /