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

The itch this idea is supposed to scratch is the problem that a rebase or a amended commit is no longer a fast-forward, so cannot be easily pulled. While this is not a problem in most workflows, as one can either merge or keep everything private and rebase until published, it would be nice to have a way for cases in between, where both a clean presentable commit order is to be maintained and people (or yourself from different repositories) should be able to easily upgrade to newer versions without an error-prone not-fast-forward.

My idea to solve this is combining both histories, the rebased/revised history and the actualy history, marking with some "equal-tree-merge" the point where they have the same result. The following mails show some patches to implement this by means of a merge where all parents have the same tree and some special casing when encountering such a thing. This has the advantage that older git version will just see strange merges and may present both histories, but otherwise just work.

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

i.e: the new feature branch has both histories:
  - "feature'" where everything is cleanly rebased and in a form where
               format-patch is suitable to send it upstream
  - "merge" which is both a descendant from feature (so one can see what
    changed since that time and can just pull when one had had cloned feature)

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". Now you of course do not want to send it that way upstream (as it will make reviewing harder, may force people bisecting to skip some versions every time they hit this region and so on), so you want to bisect -i and squash "f" into "b".

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

But if you had already cloned at state "d" to your laptop (or made a backup of that branch at some server, or published it for use of some collegues) it will not be a fast-forward, so you have to be very carefull to not accidentially lose a commit that is already there.

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

which means that you can just pull from your laptop and get the new head as fast-forward, but still have a proper history ready for submitting.

The only downsize of this approach is that an unpatched/old git of course does not know about that it can just choose one of both histories but think it has to look at both, so git-format-patch will return patches multiple times and git-rebase will also try to apply both branches, which the patched version no longer does, only showing the 'presentable' in this case.

Those patches are a bit rough and mostly intended to show how it could work and to allow experimenting with it. I think the biggest thing still missing (apart from documentation, error handling, better commit messages) is making git bisect take advantage of this and only looking at the nice branch.

Bernhard R. Link (7):
  add new command git equal-tree-marker
  add option to only visit the first parent of a equal tree merge
  format-patch defaults to --first-equal-tree-only
  support equal tree merges in interactive rebase
  make rebase -m equal tree marker aware
  add support for creating equal tree markers after rebase
  add support for creating equal tree markers to rebase -i

 .gitignore                 |    1 +
 Makefile                   |    1 +
 builtin-log.c              |    1 +
 git-equal-tree-marker.sh   |   50 ++++++++++++++++++++++++++++++++++++++
 git-rebase--interactive.sh |   33 +++++++++++++++++++++++++
 git-rebase.sh              |   35 ++++++++++++++++++++++++--
 revision.c                 |   57 +++++++++++++++++++++++++++++++++++++-------
 revision.h                 |    1 +
 8 files changed, 167 insertions(+), 12 deletions(-)
 create mode 100644 git-equal-tree-marker.sh

Hochachtungsvoll,
	Bernhard R. Link

This adds a new commit denoting tha current branch has the same tree as another branch, thus allowing fast-forward from the named commits to this one.

TODO: manpage, rewrite as builtin once the semantics are accepted?
---
 .gitignore               |    1 +
 Makefile                 |    1 +
 git-equal-tree-marker.sh |   50 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 52 insertions(+), 0 deletions(-)
 create mode 100644 git-equal-tree-marker.sh

Bernhard R. Link venit, vidit, dixit 30.11.2009 15:43:

You mean there should be something really simple, such as:

git rev-parse "$1"^{tree}

Michael

rev_info gets a new flag first_equal_tree_only that causes revision walks to ignore all but the first parent of equal tree merges. The default is off and there are options --first-equal-tree-only and --all-equal-trees to switch it on/off respectively.

TODO:
 - manpage updates
 - check interaction with some of the other options
---
 revision.c |   57 ++++++++++++++++++++++++++++++++++++++++++++++++---------
 revision.h |    1 +
 2 files changed, 49 insertions(+), 9 deletions(-)

TODO: manpage update to hint to --all-equal-trees?
---
 builtin-log.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

---
 git-rebase--interactive.sh |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

---
 git-rebase.sh |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

With the new --eqt option, git rebase adds an equal tree marker, so that the old branch can be fast-forwarded to the new one. If the trees are not equal, a fake merge of the new base and the old branch is created first.

TODO:
 - manpage update,
 - should --eqt have a better (longer more descriptive) name?
 - the commit message of the merge should have a better default
   and presented to the user for editing
---
 git-rebase.sh |   33 +++++++++++++++++++++++++++++++--
 1 files changed, 31 insertions(+), 2 deletions(-)

With the new --eqt option, git rebase -i adds an equal tree marker, so that the old branch can be fast-forwarded to the new one. If the trees are not equal, a fake merge of the new base and the old branch is created first.

TODO:
- manpage update,
- should --eqt have a better (longer more descriptive) name?
- the commit message of the merge should have a better default
  and presented to the user for editing
---
 git-rebase--interactive.sh |   32 ++++++++++++++++++++++++++++++++
 1 files changed, 32 insertions(+), 0 deletions(-)

Heya,

On Mon, Nov 30, 2009 at 15:43, Bernhard R. Link <brlink@debian.org> wrote:

Given the experimental nature of your patches it would probably have been appropriate to mark them "RFC" (request for comment). You can do so by running: `git format-patch --subject-prefix="RFC PATCH"` instead of "git format-patch".

On 11/30/2009 03:43 PM, Bernhard R. Link wrote:

How does this compare with topgit?

Paolo

* Paolo Bonzini <bonzini@gnu.org> [091130 16:32]:

It's not easily compareable as having different aims, but I think there are some use-cases where this allows native usage of git where previously the best bet was topgit.

Assume for example you want to maintain a set of patches of some upstream, which you want to have in some form relative to upstream and in patches easily reviewable and pickable by other people.

You could do that with topgit by making each change a topgit branch. But to clone that repository then you would need topgit to get all the information and cherry picking one of your changes (that perhaps grow with the time, was adapted to new upstreams and had bugs fixed) needs telling topgit to combine the changes of that branch and use that instead of a simple cherry pick.

With this equal-tree-marker you can just do a git rebase --eqt or git rebase -i --eqt and both have a history with your changes as single commits which are easy to look at (and you can just pushing head^1 somewhere for upstream to pull from) while still having all the history in your git archive so someone else can look what actually happened or just clone your current head and repeatenly pull from it.

Hochachtungsvoll,
	Bernhard R. Link

Bernhard R. Link venit, vidit, dixit 30.11.2009 15:43:

Do you mean pushed? For pull, the state of the branch on the receiving side play a role, of course.

Without having the time to go through the detailed setup you described below (sorry), I'm wondering how this differs from what Git calls a trivial merge? Is it merely about asserting that you merge coinciding (heads with) trees?

Michael

Bernhard R. Link venit, vidit, dixit 30.11.2009 15:43: [...]

Ok, I couldn't resist looking at your examples. Actually, before anything else: Thanking for describing *what* you want to achieve, not only how.

git checkout -b featureprime feature git rebase master git merge feature # should be trivial git branch -M featureprime feature

If that side branch is named "feature": git checkout -b fixup feature git rebase -i a # squash f into b; creates b+f c# d' e' git merge feature # should be trivial git branch -M fixup feature

You can also go crazy with rebase --onto here, or use cherry-pick repeatedly.

Note that I always use a temporary branch for rewriting, before renaming it to the proper branch name. I haven't checked, but I assume the "first-parents" are the way you want them (you want log --first-parent --no-merges to show the rewritten commits, right?); otherwise you would have to do the merges the other way round.

Cheers, Michael

* Michael J Gruber <git@drmicha.warpmail.net> [091130 17:00]:

My problem with that is that --first-parent-only makes no difference between this and other merges.

Assume the example2

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

would continue with some paralel commits and a merge:

o=master
   \
    a=b=c=d=e=f---       y
     \            \     / \
      b+f=c'=d'=e'=eqt-x   m
                        \ /
                         z

now if you rebase that tree (or want to send it with format-patch), you either get the old commits multiple times in format-patch (and possibly causing already resolved conflicts when doing the am step in rebase), or you use --first-parent-only and might miss z.

Thus the idea to have some way to destinguish this merge from a normal merge and thus the extra pseudo-merge in example 1 to get the following merge to merge things with equal tree.

Hochachtungsvoll,
	Bernhard R. Link

Hi,

On Mon, 30 Nov 2009, Bernhard R. Link wrote:

Actually, I did something like this without any new tool:

	git rebase origin/master
	git merge -s ours master@{1}

The effect is that there is a merge commit which really merges the old state.

OTOH I can see that there is merit in trying to avoid to _require_ the whole history of the rebased branch. But then, would it not be more in line with Git's ideas if there was a tool trying to identify, say, from the commit message which commits in HEAD...MERGE_HEAD are supposed to be identical?

Ciao, Dscho

"Bernhard R. Link" <brlink@debian.org> writes:

If you rewrite a series twice, your RFC will work like this, IIUC:

 * You have commit 1 and rewrite it to 2.  You record the difference
   between 1 and 2 on top of 1 as commit X and record a same-tree merge as
   A.  Here, A^1 == 2, A^2 == X, and 2^{tree} == A^{tree}.

       2-------A
      /       /
     0---1---X

 * You then rewrite it to 3.  You record the difference between A and 3
   (which is the same as between 2 and 3, because 2^{tree} == A^{tree})
   as commit Y, and record a same-tree merge as B.  B^1 == 3, B^2 == Y and
   3^{tree} == B^{tree}.

         Y---------------B
        /               /
       2-------A-------3
      /       /
     0---1---X

It however might be easier to review what happened if you create a history this way upon the second rewrite (forget the second picture above):

       3-------.
      /         \
     0---2---W---B
      \         /
       1-------Z

That is, Z and W records the interdifff between 1 to 3 and 2 to 3 respectively, and B is a same-tree merge of 3, W and Z.

As you are giving some specific meaning to the order of merge parents of a marker commit, namely, the first parent is the latest version of this series (i.e. B^1 == 3), you can extend it to declare that the second parent is the next to the latest incarnation (i.e. B^2 == W) and the third one is one version older than the second one (i.e. B^3 == Z).

Doing it this way allows you to publish the final result "3" without any cruft in the history.

In your code you have comment wondering if there is a better wording for the fix-up commit you create during rebase when the trees do not match. I would suggest calling it "interdiff". That is exactly what "git show W" would show.

While I find the primary idea (i.e. keeping the old and new equivalents by recording a merge of it, and using the first-parent to traverse when you find such a special merge) reasonable (and as Dscho has pointed out, this technique is widely used, I suspect---it is an obvious thing to do), I think we need something stronger than just "this commit merges commits that happen to have the same trees" as the marker.

Git is designed to work well in an environment where multiple people produces identical result. A 3-way merge resolves cleanly when both branches modified a path to the same result (at contents level as well at path level). If you take this principle to the extreme, you should be able to merge two branches that were developed independently but still reached the same conclusion at the end, without marking such a merge as anything funny. With your RFC code, one branch will be mistakenly treated as "old cruft that was improved by the other branch by rewriting".

To avoid that, I think (1) the marker has to be more reliable than just "happens to have the same tree", and (2) the traversal done by Porcelains (your patches 3 thru 5) by default should be unaware of eqt.

I don't know what a suitable marker should look like, though. The marker must be easily identifiable by the lowest level rev-list machinery, so it needs to be a sign left somewhere in the commit object. Perhaps making it require to have the same tree as all its parents _and_ a well-known marker string in the log message (and nothing else) would be a good start.

In the longer term, if the line of this direction turns out to be a good one, I do not mind adding a special header to the commit object separate from the log message, but we should start without one until this proves to be a useful ingredient in people's workflows. With a reliable marker, we can obviously drop the "same-tree" ness from the definition of the marker commit, which in turn means that you do not need "interdiff" commits while rebasing.

The command to build such a merge could be an option to "git merge -s ours" (perhaps something like "git merge -s ours -Xeqt").

* Junio C Hamano <gitster@pobox.com> [091130 19:19]:

I think it rather looks like this:

     3---------------B
     |              /
     | 2-------A---Y
     |/       /
     0---1---X

I think changing it to get this would be easy (though only in the case where the very last commit was such an equal tree merge), but I do not think it would be actually better:

- it is no longer possible to see the history of changes by just walking
  right on every equal-tree-merge.
- commit a no longer exists. If some downstream already has
  cloned/pulled, no fast-forward is possible any more.

I've considered adding a new header or only a magic description text for those commits, but I think it is not necessary. Because the actual programs making it useful to treat this special (format-patch producing too many patches, rebases possibly showing conflicts already resolved and bisect walking too many branches) will be the same when two branches only resulting in the same tree by pure chance show up.

I think for patch 3 (format-patch) and 4 (rebase -i) it is always better to have the new behaviour even when only hitting equal trees by chance. I'm unsure about 5 (rebase -m), but guess it still is.

It already does always create a unique log message. So one could also have one more strict and one less strict mode (and some option to decide on the default).

Hochachtungsvoll,
	Bernhard R. Link

"Bernhard R. Link" <brlink@debian.org> writes:

Oh, I wasn't suggesting you to change it to use an octopus. I however did want to know if you considered pros-and-cons with such an alternative (there perhaps are other approaches as well), and I agree recording one iteration at a time like you do is better.

On Montag, 30. November 2009, Junio C Hamano wrote:

Wouldn't the pathspec . be the marker:

    git rev-list HEAD -- .

follows only one of the branches that have identical trees.

-- Hannes

Johannes Sixt <j6t@kdbg.org> writes:

Because I am saying that "this commit has two parents and they record the identical trees" is a condition that is too weak to mark a special-purpose merge to bind the latest and an earlier version of a series, your rev-list example command line should not be the way to identify such a mark commit and act differently upon seeing one.

Actually your command line is even weaker, I think, although it would not make much difference in real-life. The marker as currently Bernhard implements not only has parents with identical trees, but the tree it has also matches those of its parents.

You can make a commit that merges two branches that independently reached the same conclusion (which git is designed to handle as an ordinary event in real life), and amend that commit into an evil merge that has different contents from its parents (which, I suspect, does not have much use in practice), and your rev-list will drop one of the branches for even such a commit, mistaking it as a marker when it is clearly not one.

My "it would not make much difference in real-life" in the two paragraphs above comes purely from "such an evil merge would not have much use in practice". We should make sure that "two branches that reached the same conclusion" is not mistaken with a marker this series introduces.

Quoting Junio C Hamano <gitster@pobox.com>

I think you can record a merge commit that has an unusual list of parents for this. For example, you can record the latest version twice, as the first and the second parents, and make the previous version the third parent. Because such a merge can't be created with git-merge command, you can reliably tell that it is an unusual 'marker' merge.

No matter what techinique is used to mark the special 'marker', if it happens in real life for two or more people who worked independantly to arrive at the same conclusion, I don't think dismissing it as 'by chance' and discarding the contribution from the second branch is a good solution. If git is meant to work smoothly in projects where more than one person see and accept patches from the same origin, the condition is not met 'by chance'; the tool is by design supposed to handle it as a regular situation.

On the other hand, if you made the marker reliable, I think you don't have to disable this feature by default like you said in your (2).

As a side note, I have a bug to report. I tried this sequence of commands to make sure git-merge doesn't record the same parent twice (the last git-merge is made on the slave branch and tries to have slave, master and slave as its three parents).

 % git init
 % echo hello >world
 % git add . ; git commit -m first
 % echo again >world
 % git commit -a -m master
 % git checkout -b slave master^
 % echo again >world
 % git commit -a -m slave
 % git merge master slave

But I got the "usage: ..." error message from git-merge.

Nanako Shiraishi <nanako3@lavabit.com> writes:

That's too ugly a hack, and hints an undesirable attitude that this will be the last feature that needs such cleverness, without leaving the door open for others who need similar "magic marker" capability added to commit objects. The approach will not scale, unless you consider "first and second parents being the same means it is 'rebased branches magic', and first, second and third parents being the same means some other matic, etc." as scalable.

As I said, if the approach this series takes turns out to be useful, it is Ok to implement it as a new header in the commit object if necessary.

We try very hard to avoid adding random headers to commits because a commit that records the same history should be named the same way in the object store namespace and adding random headers will make it easier to create the same commit with different names, but what we are discussing is a special purpose pseudo commit and it _is_ a feature that the object name of a commit, after SHA-1 hashing, is different with and without the special header in this case.

I said the same thing, and I agree that two (or more) people creating the same state should be treated as a normal event. But I am not so sure about a merge that binds two such histories together. The person who makes such a merge can go on without making one as far as tree-state is concerned (i.e. such a merge will result in the same tree with both parents), and the _only_ reason a merge between the two branches is created is to cauterize one (or both) of the branches, declare that everything that happened in the branch is now part of this branch. In other words, such a merge is an operation to purely affect the history and not contents.

As J6t pointed out, when we tell the revision walking machinery to limit by path, we already simplify the history we show to the user, and if path happens to name the whole tree, such a history is already simplified to show only one side of the story. So perhaps it is not as grave an offence to ignore contribution from one side when both of the parents of a merge record the same tree as I originally thought. It also justifies not introducing a new header in commits. The implementation of Bernhard's series might become simpler if it used the trick to use "." pathspec internally instead of introducing a new traversal option to the revision machinery.

That is true, but as you may be able to tell, I am undecided if the marker should be _that_ explicit, or should be implicit and the fact that a merge that whose all parents have the same tree should make it automatically a marker (iow, I earlier said "misidentify" but now I am wondering if it makes sense to define any merge with the property an "alternative history binding marker", no matter how it was created).

Well, you did not quote the usage string you got, but it should have began like this:

    usage: git merge [options] <remote>...
       or: git merge [options] <msg> HEAD <remote>

The parser misinterpreted your request as the latter form (which is ancient and probably predates your involvement with the git project), noticed that you did not give any <remote> commit, and then gave the usage message.

I think we really should start deprecating the ancient form, but the original sample script using this syntax from Linus was copied by many people and are still found everywhere, I think, and people may still use their scripts that were written with the ancient syntax.

In any case, at least this patch will make it start behaving a bit more sanely.

-- >8 --
Subject: Do not misidentify "git merge foo HEAD" as an old-style invocation

This was misinterpreted as an ancient style "git merge <message> HEAD <commit> <commit>..." that merges one (or more) <commit> into the current branch and record the resulting commit with the given message. Then a later sanity check found that there is no <commit> specified and gave a usage message.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

The ancient form of git merge command used in the original sample script has been copied from Linus and are still found everywhere, I think, and people may still have it in their scripts, but on the other hand, it is so unintuitive that even people reasonably familiar with git is surprised by accidentally triggering the support to parse this ancient form.

Gently nudge people to upgrade their script to more recent and readable style for eventual removal of the original syntax.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

    And this is the first step of such a deprecation.  Perhaps we start
    warning in 1.7.0 and remove it in 1.8.0, or something like that.

 builtin-merge.c |    5 +++++
 1 files changed, 5 insertions(+), 0 deletions(-)

On Mon, 30 Nov 2009, Junio C Hamano wrote:

If this is going to be removed in the future, then it is already deprecated. Therefore it is much better to start warning now and not wait for 1.7.0. There is just no point delaying the advice.

Nicolas

Nicolas Pitre <nico@fluxnic.net> writes:

Very true.

What I am not absolutely sure about is if the presense of the support for ancient usage hurts people in real life so much that it is better to remove it than keep it. At least we saw one example of a user (who is not a novice) getting puzzled by it, but that may not be enough datapoint to decide with.

Quoting Junio C Hamano <gitster@pobox.com> writes:

Thank you; it fixes the bug for me. Do I have to say 

    Tested-by: Nanako Shiraishi <nanako3@lavabit.com>

to ask you to include it in the new release?

Nanako Shiraishi <nanako3@lavabit.com> writes:

Thanks for reminding me.  I almost forgot that I did that patch.

Bernhard R. Link wrote:

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.

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