Re: What's the meaning of `parenthood' in git commits?

[Nix <nix@esperi.org.uk>]

On 8 Nov 2006, nix@esperi.org.uk spake thusly:
> On 8 Nov 2006, Linus Torvalds uttered the following:
>>  - the "merge-base" algorithms obviously use it to find the most recent 
>>    common ancestor, and that in turn impacts the normal merge strategies, 
>>    of course.
>
> Hm, yeah, if merging iterates down patch-merged branches it might have
> interesting consequences, because the trees on one side of patch- merges
> are likely to be very different to trees on the other side (years of
> development separate them). I'd like a way to specify that those parents
> are *not* to be traversed by the merge-base algorithms, really.
>
> A series of
>
> not-merge-base: <sha1 id>
>
> headers, perhaps? (I think that's likely to involve much less code churn
> than introducing a new `not-merge-base-parent' tag).

Wrong. Sort of.

When doing normal merges you don't want to consider patch-merged parents
as real merges: but there is one situation when you *do* want merge-base
checking to traverse such links.

Say you have the tree just described:

     B
------------- ref trunks/latest
     \
      ------ ref heads/some-change-foo

 ... -------- ref trunks/old-and-grotty

and you want to patch-merge heads/some-change-foo with
trunks/old-and-grotty.

It doesn't quite apply, so you end up with a conflict-resolution. This
will normally be in the merge commit, but there's no guarantee of that:
perhaps you knew the source tree would conflict in advance and fixed it
up so that it wouldn't, leaving the old heads/some-change-foo pointing
before that fixup:

     B
------------- ref trunks/latest
     \
      ------- ref heads/some-change-foo
          D \
            c
            |
 ... -------------- ref trunks/old-and-grotty

Later on, you find a bug in that change. It's still the same conceptual
change, so you fix it, and you want to patch-merge the fix across:

     B
------------- ref trunks/latest
     \
      -----------\ ref heads/some-change-foo
          C \    .
            c    . (link under construction)
            |    .
 ... -------------- ref trunks/old-and-grotty
            E    F

What patch-merge must do in order to produce a diff-merge at point F is
therefore rather more involved than I'd hoped:

 - determine B as above (most recent merge-base of heads/some-change-foo
   with anything in trunks/).

 - determine the merge-base of trunks/old-and-grotty with
   heads/some-change-foo, *traversing patch-merge parents*. Call this
   base C. (This is the only circumstance in which merge-base
   determination should traverse patch-merged parents.)

 - Iff that base C is topologically a child of B, then we have already
   merged part of this change in the past. In that case, instead of the
   merge consisting of the diff between B and F, it consists of the diff
   between C and the head, minus the set of changes c. So it remains to
   determine c.

 - scan backwards along F with git-rev-list, searching specifically for
   the most recent patch-merge naming any commit which has C as a
   transitive parent: that is point E. (Such a point must exist as long
   as only patch-merges have been used to merge heads/some-change-foo
   with trunks/old-and-grotty: if other sorts of merge have been used,
   all bets are off and I think we can legitimately fail the merge.)
   (This requires the ability to distinguish patch-merges from normal
   merges, but that's easy if we have any tag at all to distinguish
   them, which we must for merge- base traversal to avoid such parents
   normally.)

 - Reverse out the diff between C and E (if the two are not the same
   commit) and remember it temporarily as c.

 - Apply the forwards diff between point C and heads/some-change-foo,
   and then apply c in the forwards direction (if c is already present,
   this is not an error: it just means that whatever conflict-
   resolution was necessary as a one-off was later needed on the change
   trunk).

I think that should cope with just about everything. I've tried to mock
up all sorts of contrived trees and I can't find anything that doesn't
reduce to that case or a simplification of it. (And no, this case is not
contrived: we test on trunks, so we deal with it whenever anything fails
testing and has to be fixed...)

(Now all I have to do is write it... enough words, time for action.
Actually time for sleep, it's three in the morning here. Action
tomorrow.)

-- 
Rich industrial heritage: lifeless wasteland. `The land