git@vger.kernel.org mailing list mirror (one of many)
 help / Atom feed
From: Sergey Organov <sorganov@gmail.com>
To: git@vger.kernel.org
Cc: Johannes Sixt <j6t@kdbg.org>, Junio C Hamano <gitster@pobox.com>,
	Jacob Keller <jacob.keller@gmail.com>,
	Johannes Schindelin <johannes.schindelin@gmx.de>
Subject: [RFC] Rebasing merges: a jorney to the ultimate solution (Road Clear)
Date: Fri, 16 Feb 2018 16:08:39 +0300
Message-ID: <87y3jtqdyg.fsf@javad.com> (raw)

Hi,

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: a "Trivial Merge (TM)", see below.]

Let me begin by outlining the method in git terms, and special thanks
here must go to "Johannes Sixt" <j6t@kdbg.org> for his original bright
idea to use "cherry-pick -m1" to rebase merge commits.

End of preface -- here we go.

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. Merge --no-ff new b2' to current new b1', to produce 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 see why and how the method actually works.

Firs off, let me introduce you to my new friend, the Trivial Merge, or
(TM) for short. By definition, (TM) is a merge that introduces
absolutely no differences to the sides of the merge. (I also like to
sometimes call him "Angel Merge", both as the most beautiful of all
merges, and as direct antithesis to "evil merge".)

One very nice thing about (TM) is that to safely rebase it, it suffices
to merge its (rebased) parents. It is safe in this case, as (TM) itself
doesn't posses any content changes, and thus none could be missed by
replacing it with another merge commit.

I bet most of us have never seen (TM) in practice though, so let's see
how (TM) can help us handle general case of some random merge. What I'm
going to do is to create a virtual (TM) and see how it goes from there.

Let's start with this history:

  M
 / \
B1  B2

And let's transform it to the following one, contextually equivalent to
the original, by introducing 2 simple utility commits U1 and U2, and a
new utility merge commit UM:

  UM
 /  \
U1   U2
|    |
B1   B2

Here content of any of the created UM, U1, and U2 is the same, and is
exact copy of 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]), and how U1 an U2 represent content
changes due to merge on either side[*], and how neither preceding nor
subsequent commits content would be 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 "Trivial Merge (TM)" his true self,
introducing zero changes to content.

Next we rebase our new representation of the history and we get:

  UM'
 /  \
U1'  U2'
|    |
B1'  B2'

Here UM' is bare merge of U1' and U2', in exact accordance with the
method of rebasing a (TM) we've already discussed above, and U1' and U2'
are rebased versions of U1 and U2, obtained by usual rebasing methods
for non-merge commits.

(Note, however, that at this point UM' is not necessarily a (TM)
anymore, so in real implementation it may make sense to check if UM' is
not a (TM) and stop for possible user amendment.)

Finally, to get to our required merge commit M', we get the content of
UM' and record two actual parents of the merge:

  M'
 / \
B1' B2'

Where [M'] = [UM'].

That's it. Mission complete.

I expect the method to have the following nice features:

- it carefully preserves user changes by rebasing the merge commit
itself, in a way that is semantically similar to rebasing simple
(non-merge) commits, yet it allows changes made to branches during
history editing to propagate over corresponding merge commit that joins
the branches, even automatically when the changes don't conflict, as
expected.

- it has provision for detection of even slightest chances of ending up
with surprising merge (just check if UM' is still (TM)), so that
implementation could stop for user inspection and amendment when
appropriate, yet it is capable of handling trivial cases smoothly and
automatically.

- it never falls back to simple invocation of merge operation on rebased
original branches themselves, thus avoiding the problem of lack of
knowledge of how the merge at hand has been performed in the first
place. It doesn't prevent implementation from letting user to manually
perform whatever merge she wishes when suspect result is automatically
detected though.

- it extends trivially to octopus merges.

- it appears shiny to the point that it will likely be able to handle
even darkest evil merges nicely, no special treatment required.

Footnote:

[*] We may as well consider the (UM,U1,U2) trio to be semantically split
representation of git merge commit, where U1 and U2 represent content
changes to the sides, and UM represents pure history joint. Or, the
other way around, we may consider git merge commit to be optimized
representation of this trio. I think this split representation could
help to simplify reasoning about git merges in general.

-- Sergey

             reply index

Thread overview: 80+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-02-16 13:08 Sergey Organov [this message]
2018-02-18  4:16 ` Jacob Keller
2018-02-19  5:28   ` Sergey Organov
2018-02-19 23:44 ` Igor Djordjevic
2018-02-20 12:42   ` Sergey Organov
2018-02-27  0:07   ` Johannes Schindelin
2018-02-27  5:01     ` Sergey Organov
2018-02-27  5:30     ` Jacob Keller
2018-02-27 16:21       ` Johannes Schindelin
2018-02-27 18:55         ` Igor Djordjevic
2018-02-27 19:59           ` Igor Djordjevic
2018-02-27 23:27             ` Johannes Schindelin
2018-02-28  2:12               ` Igor Djordjevic
2018-02-28  4:35                 ` Igor Djordjevic
2018-02-28  6:14                   ` Sergey Organov
2018-02-28 20:53                     ` Igor Djordjevic
2018-02-28  5:44               ` Sergey Organov
2018-02-28 19:42                 ` Igor Djordjevic
2018-02-27 23:40             ` Igor Djordjevic
2018-02-28  0:10               ` Junio C Hamano
2018-02-28  2:35                 ` Igor Djordjevic
2018-02-28  5:27                 ` Sergey Organov
2018-02-28  0:36               ` Jacob Keller
2018-02-28  1:33                 ` Igor Djordjevic
2018-02-28  1:43                   ` Igor Djordjevic
2018-02-28  5:21                   ` Sergey Organov
2018-02-28 19:09                     ` Igor Djordjevic
2018-03-01  5:27                       ` Sergey Organov
2018-02-28  5:19               ` Sergey Organov
2018-02-28 20:25                 ` Igor Djordjevic
2018-02-28 22:17                   ` Igor Djordjevic
2018-03-01  5:19                     ` Sergey Organov
2018-03-01  5:39                   ` Sergey Organov
2018-03-02  1:16                     ` Igor Djordjevic
2018-03-02  5:40                       ` Sergey Organov
2018-03-02 17:45                         ` Igor Djordjevic
2018-03-02 11:31                     ` Phillip Wood
2018-03-03  0:29                       ` Igor Djordjevic
2018-03-05  5:00                         ` Sergey Organov
2018-03-06 10:52                           ` Phillip Wood
2018-03-06 16:56                             ` Junio C Hamano
2018-03-08  7:05                               ` Johannes Schindelin
2018-03-08  8:18                                 ` Junio C Hamano
2018-03-11 11:56                                   ` Johannes Schindelin
2018-03-13 18:24                                     ` Junio C Hamano
2018-03-26 13:17                                       ` Johannes Schindelin
2018-03-05 17:29                         ` Johannes Schindelin
2018-03-06 23:21                           ` Igor Djordjevic
2018-03-07  7:04                             ` Johannes Schindelin
2018-03-06 10:45                         ` Phillip Wood
2018-03-06 11:45                           ` Sergey Organov
2018-03-08 16:30                             ` Igor Djordjevic
2018-03-06 18:12                           ` Johannes Schindelin
2018-03-07  5:08                             ` Sergey Organov
2018-03-07  6:58                               ` Johannes Schindelin
2018-03-07 14:34                                 ` Sergey Organov
2018-03-08  6:45                                   ` Johannes Schindelin
2018-03-12 12:31                                     ` Sergey Organov
2018-03-26 11:37                                       ` Johannes Schindelin
2018-03-27  5:11                                         ` Sergey Organov
2018-03-27 12:55                                           ` Johannes Schindelin
2018-03-28  4:32                                             ` Sergey Organov
2018-03-08 11:08                             ` Phillip Wood
2018-03-05 17:52                       ` Johannes Schindelin
2018-03-13 16:10                       ` Sergey Organov
2018-03-14  1:12                         ` Igor Djordjevic
2018-03-14  7:21                           ` Sergey Organov
2018-03-15  0:09                             ` Igor Djordjevic
2018-03-15  7:52                               ` Sergey Organov
2018-03-15 23:08                                 ` Igor Djordjevic
2018-03-16  7:31                                   ` Sergey Organov
2018-03-17  3:04                                     ` Igor Djordjevic
2018-03-19  6:01                                       ` Sergey Organov
2018-03-26 14:11                                   ` Johannes Schindelin
2018-02-28  0:29         ` Jacob Keller
2018-02-27 11:57     ` Sergey Organov
2018-02-27 18:14       ` Junio C Hamano
2018-02-28  0:30         ` Jacob Keller
2018-02-28  5:54           ` Sergey Organov
2018-02-28  4:53         ` Sergey Organov

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=87y3jtqdyg.fsf@javad.com \
    --to=sorganov@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=j6t@kdbg.org \
    --cc=jacob.keller@gmail.com \
    --cc=johannes.schindelin@gmx.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

git@vger.kernel.org mailing list mirror (one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/
       or Tor2web: https://www.tor2web.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox