Re: equal-tree-merges as way to make rebases fast-forward-able

From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Dec 1, 2009, 11:50 UTC
Message-ID: <4B1502F5.1060100@alum.mit.edu>
In-Reply-To: <cover.1259524136.git.brlink@debian.org>

Bernhard R. Link wrote:

Show 17 quoted lines

> Example 1:
> 
> Let's assume you maintain such a regularily-rebased branch that you
> want to be able to publish (or pull from other repositories for example
> on your laptop):
> 
> o=m=o=o=master
>    \
>     a=b=c=d=e=feature
> 
> with this patch you can do "git rebase -eqt master" and get:
> 
>               a'=b'=c'=d'=e'=feature'=eqt
>              /                       /
> o=m=o=o=master--------              /
>    \                  \            /
>     a=b=c=d=e=feature--merge-------

Actually, there is more information that can be retained about this rebase operation. Your scheme records the fact that (a+b+c+d+e+merge) == (o+o+a'+b'+c'+d'+e'), which is certainly true. But in the process of rebasing, the user has (implicitly or explicitly) resolved conflicts in transforming each of the patches a -> a', b -> b', etc. In fact, the patch a' is itself a merge between a and master; b' is a merge between b and a'; etc. If you record each of these merges individually, the result looks like this:

o=m=o=o=master
   \      \
    \      a'=b'=c'=d'=e'=feature'
     \    /  /  /  /  /
      ---a==b==c==d==e==feature

There are advantages to retaining all of this history:

* It faithfully represents intermediate steps of the rebase.

* There is no need for special "merge" and "eqt" merge commits affecting
an arbitrary group of feature patches; each of the rebased patches is
treated identically.

* There is a direct ancestry connection from the "new version" to the
"old version" of each patch; for example, it is easy to see that c' is a
new version of c and to compute the corresponding interdiffs.

* There are situations where the additional info can help git choose
better merge bases in the case of merge/rebases across three or more
repositories.  For example, somebody who is developing a subfeature
based on the feature branch can merge/rebase changes from both feature
and master without causing utter chaos.

The "historical" version of the feature branch should be omitted from most git output as you have suggested, but this would be best implemented by marking the "historical" ancestor with some extra flag in each merge commit.

Show 18 quoted lines

> Example 2:
> 
> Let's assume you have a feature branch like
> 
> o=master
>    \
>     a=b=c=d=e=f
> 
> Assume you just commited "f" which fixes a bug introduced by "b". [...]
> 
> So with this patches you can do "git rebase -i --eqt" and squash f into b
> and get:
> 
> o=master
>    \
>     a=b=c=d=e=f---
>      \            \
>       b+f=c'=d'=e'=eqt

This case can also record additional information:

o=master
   \
    a=b===c==d=e=f
       \   \  \   \
        b+f=c'=d'==e'

Here the new DAG cannot represent *all* ancestry information (namely, that b+f, c', and d' also include the original patch f), but it does accurately reflect useful information such as that c' includes c and that e' includes e and f.

I wrote some blog entries about rebasing-with-history that might be interesting [1-3].

Michael

[1] http://softwareswirl.blogspot.com/2009/04/truce-in-merge-vs-rebase-war.html [2] http://softwareswirl.blogspot.com/2009/08/upstream-rebase-just-works-if-history.html [3] http://softwareswirl.blogspot.com/2009/08/rebase-with-history-implementation.html