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

[Michael Haggerty <mhagger@alum.mit.edu>]

Bernhard R. Link wrote:
> 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.

> 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