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

On 8 Nov 2006, nix@esperi.org.uk spake thusly:

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