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

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