git@vger.kernel.org mailing list mirror (one of many)
 help / Atom feed
From: Jacob Keller <jacob.keller@gmail.com>
To: Sergey Organov <sorganov@gmail.com>
Cc: Git mailing list <git@vger.kernel.org>,
	Johannes Sixt <j6t@kdbg.org>, Junio C Hamano <gitster@pobox.com>,
	Johannes Schindelin <johannes.schindelin@gmx.de>
Subject: Re: [RFC] Rebasing merges: a jorney to the ultimate solution (Road Clear)
Date: Sat, 17 Feb 2018 20:16:34 -0800
Message-ID: <CA+P7+xrgmSHv-coOdUAmBm31Sd0DzYdoez=tVO8drew9q7DExw@mail.gmail.com> (raw)
In-Reply-To: <87y3jtqdyg.fsf@javad.com>

On Fri, Feb 16, 2018 at 5:08 AM, Sergey Organov <sorganov@gmail.com> wrote:
> 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.
>

I hope to take a more detailed look at this, also possibly with some
attempts at re-creating the process by hand to see it in practice.

> 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.
>

Seems pretty straight forward, go to each branch and cherry-pick the
merge respective to its relative parent, and then finally re-merge
everything, and consume the intermittent commits.

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

This might be a bit tricky for a user to understand what the process
is, especially if they don't understand how it's creating special U1'
and U2' commits. However, it *is* the cleanest method I've either seen
or thought of for presenting the conflict to the user.

> 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.
>

Right.

> - 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.

Nice!

>
> - 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.
>

Right, since we're re-creating the intermittent commits U1' and U2'
first based on the original merge, that's how we manage to maintain
the result of the merge. I like it.

> - 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.
>

Yep, and I like that it has a pretty reasonable way of presenting
conflicts for resolution. It may be a bit tricky to explain the use of
the intermittent commits U1' and U2' though.

> 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.

Yes, I think this concept is pretty useful. I think it could be useful
as a way of showing how the merge worked.

Thanks,
Jake

>
> -- Sergey

  reply index

Thread overview: 173+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-02-16 13:08 Sergey Organov
2018-02-18  4:16 ` Jacob Keller [this message]
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:17                       ` [RFC] Rebasing merges: a jorney to the ultimate solution(RoadClear) Phillip Wood
2018-03-02 12:36                         ` Phillip Wood
2018-03-02 16:02                           ` Jacob Keller
2018-03-02 23:33                             ` Igor Djordjevic
2018-03-06 10:36                               ` Phillip Wood
2018-03-06 18:12                                 ` Johannes Schindelin
2018-03-06 19:43                                   ` Igor Djordjevic
2018-03-07  7:26                                     ` Johannes Schindelin
2018-03-08 11:20                                       ` Phillip Wood
2018-03-08 12:16                                         ` Phillip Wood
2018-03-08 16:05                                           ` Igor Djordjevic
2018-03-11 12:00                                             ` Johannes Schindelin
2018-03-11 16:33                                               ` Igor Djordjevic
2018-03-12 10:37                                                 ` Johannes Schindelin
2018-03-12 12:56                                                   ` Sergey Organov
2018-03-13  0:01                                                     ` Igor Djordjevic
2018-03-26 12:03                                                       ` Johannes Schindelin
2018-03-27  5:08                                                         ` Sergey Organov
2018-03-27 13:35                                                           ` Johannes Schindelin
2018-04-02  6:07                                                             ` Sergey Organov
2018-03-12 23:54                                                   ` Igor Djordjevic
2018-03-13  6:25                                                     ` Sergey Organov
2018-03-08 15:56                                         ` Igor Djordjevic
2018-03-11 12:08                                           ` Johannes Schindelin
2018-03-11 17:34                                             ` Igor Djordjevic
2018-03-12 10:46                                               ` Johannes Schindelin
2018-03-13  0:16                                                 ` Igor Djordjevic
2018-03-26 13:07                                                   ` Johannes Schindelin
2018-03-27  5:51                                                     ` Sergey Organov
2018-03-27 13:49                                                       ` Johannes Schindelin
2018-03-28  5:57                                                         ` Sergey Organov
2018-03-30 13:41                                                           ` Johannes Schindelin
2018-03-30 16:36                                                             ` Sergey Organov
2018-03-28  5:57                                                         ` Sergey Organov
     [not found]                                                           ` <CA+P7+xoDQ2mzhxeZPFhaY+TaSoKkQm=5AtoduHH06-VggOJ2jg@mail.gmail.com>
2018-03-28 11:29                                                             ` Sergey Organov
     [not found]                                                               ` <CA+P7+xo19mHrWz9Fy-ifgCcVJM2xwzcLj7F2NvFe2LwGbaJiDQ@mail.gmail.com>
2018-03-29  5:53                                                                 ` Sergey Organov
2018-03-30 10:38                                                                   ` Johannes Schindelin
2018-03-30 12:36                                                                     ` Sergey Organov
2018-03-30 13:33                                                                       ` Johannes Schindelin
2018-03-30 15:13                                                                         ` Sergey Organov
2018-03-28 12:10                                                             ` Sergey Organov
2018-03-08 16:07                                         ` Jacob Keller
2018-03-11 12:11                                           ` Johannes Schindelin
2018-03-11 17:46                                             ` Igor Djordjevic
2018-03-08 15:16                                       ` Igor Djordjevic
2018-03-08 16:21                                         ` Igor Djordjevic
2018-03-11 12:22                                           ` Johannes Schindelin
2018-03-14 14:24                                         ` Sergey Organov
2018-03-14 23:11                                           ` Igor Djordjevic
2018-03-15  6:00                                             ` Sergey Organov
2018-03-15 21:51                                               ` Igor Djordjevic
2018-03-17  2:08                                             ` Igor Djordjevic
2018-03-19  5:44                                               ` Sergey Organov
2018-03-19 21:35                                                 ` Igor Djordjevic
2018-03-20 14:43                                                   ` Sergey Organov
2018-03-26 13:47                                           ` Johannes Schindelin
2018-03-06 23:24                                   ` Junio C Hamano
2018-03-07  7:09                                     ` Johannes Schindelin
2018-03-07 18:20                                       ` Junio C Hamano
2018-03-08  7:03                                         ` Johannes Schindelin
2018-03-08  8:11                                           ` Junio C Hamano
2018-03-09 17:09                                             ` Johannes Schindelin
2018-03-02 16:00                         ` Jacob Keller
2018-03-02 18:14                           ` Igor Djordjevic
2018-03-03 17:29                             ` Igor Djordjevic
2018-03-05  5:35                               ` Sergey Organov
2018-03-02 11:31                     ` [RFC] Rebasing merges: a jorney to the ultimate solution (Road Clear) 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
2018-03-06 13:26 ` [RFC v2] " Sergey Organov
2018-03-07  6:46   ` Johannes Schindelin
2018-03-07 13:27     ` Sergey Organov
2018-03-07 14:08       ` Johannes Schindelin
2018-03-07 15:16         ` Sergey Organov
2018-03-08  7:01           ` Johannes Schindelin
2018-03-12 12:42             ` Sergey Organov
2018-03-26 11:50               ` Johannes Schindelin
2018-03-08 19:58         ` Igor Djordjevic
2018-03-08 20:27           ` Igor Djordjevic
2018-03-08 22:05             ` Igor Djordjevic
2018-03-08 23:31               ` Igor Djordjevic
2018-03-11 15:47                 ` Johannes Schindelin
2018-03-11 20:53                   ` Igor Djordjevic
2018-03-12 10:20                     ` Johannes Schindelin
2018-03-12 13:49                       ` Sergey Organov
2018-03-26 12:44                         ` Johannes Schindelin
2018-03-27  5:32                           ` Sergey Organov
2018-03-13  0:29                       ` Igor Djordjevic
2018-03-26 13:58                         ` Johannes Schindelin
2018-03-12 13:07                     ` Sergey Organov
2018-03-11 15:40           ` Johannes Schindelin
2018-03-11 22:04             ` Igor Djordjevic
2018-03-12 12:05               ` Sergey Organov
2018-03-26 11:33                 ` Johannes Schindelin
2018-03-27  5:34                   ` Sergey Organov
2018-03-12 22:41               ` Igor Djordjevic

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='CA+P7+xrgmSHv-coOdUAmBm31Sd0DzYdoez=tVO8drew9q7DExw@mail.gmail.com' \
    --to=jacob.keller@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=j6t@kdbg.org \
    --cc=johannes.schindelin@gmx.de \
    --cc=sorganov@gmail.com \
    /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