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

So I'm back on the weird porcelain I mentioned months and months ago, the one which treats source trees as named collections of patches merged together in different ways, almost like stgit on steroids, only not.

It occurred to me recently that packed refs provide about 50% of what I need (efficient handling of lots and lots of refs); most of the other 50% consits of a new extremely weird git merge strategy, `git-merge-patched', which merges branches A and B by finding the most recent merge-base between branch B and any branch listed in .git/refs/trunks (`trunks' being a directory holding heads which are treated this way by this weird merge strategy; the porcelain will have to keep it up to date, which shouldn't be too terribly hard), and patch(1)ing the diff between that base and the tip of branch B into branch A. (A patch rejection, of course, means merge-by-hand and commit, as usual with merge conflicts.)

The idea being that if you have a tree like this:

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

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

then this merge strategy, when asked to merge heads/some-change-foo into trunks/old-and-grotty would spot that point B was the most recent merge point into anything in trunks/, generate a diff between point B and heads/some-change-foo, and patch it into trunks/old-and-grotty.

(I *know* this is really weird, but I've got a choice of doing this or continuing to use SCCS with the world's most horrible shell script wrapper as the source code repository for ~5Gb of source, with tens of thousands of files in a flat directory structure, expanded to 50Gb because we're storing binary files in there by the astonishingly inefficient means of uuencoding them and sccsing the result: you may be sick now. I know which I'd prefer. I may be distorting git into something unrecognisable to its own father but it's that or I go insane *and* run out of disk space.)

After all that setup, my question's simple. Does a `parent' in git terminology simply mean `this commit was derived in some way from the commit listed here'? If so, I suppose I can list heads/some-change-foo as one parent on these merge commits, even though the `merging' mechanism is so odd that I expect to be pelted with rotten vegetables as soon as I post this.

But it's that or SCCS.

(Of course this will go into a public git repository for people to laugh at. I don't expect anyone to actually *use* it.)

Nix wrote:

Yes, being parent means that this commit was derived in some way from the commit listed here. It needs not to be this commit is the result of merge of commits listed here... there was a discussion some time ago to use one of parents (first for example) instead of special header for "prev" link to previous value of the ref (which discussion was obsoleted by reflog).

It provies two things you have to think about if to use 'parenthood' for something a bit unexpected. First, parents are connectivity, so even if you delete trunks/some-name and then prune, averything that was merged in some branch or tag which lives still wouldn't get pruned. Second, the information about merges is used in merge strategies: consider if having this information would help your strange merge strategy.

And of course there is a question if the graph as visualized by for example gitk would have more sense or not with the "strange merges" marked as merges.

On Wed, 8 Nov 2006, Nix wrote:

Wow. You've got some strange setup there, Nix.

Well, strictly speaking, git doesn't itself assign much any real meaning to "parent" at all. It has the obvious meanings:

 - the parent pointers act as reachability graph edges (so fsck cares 
   about it a lot, of course)

 - listing the "log" of a commit will show everything reachable from that 
   commit and it's parents, of course (with the commit date-stamp being 
   used as a "ordering" when having multiple choices of commits to show)

 - it has the obvious meanings for the "revision arithmetic", ie revision 
   name parsing (ie "commit~3^2")

 - parenthood will be used to show the diff ("git show", "git log -p" and 
   friends)

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

so parenthood does obviously have a number of very specific technical meanings for different programs, but at the same time, no, git doesn't really "care". You can happily generate your own parenthood if you want to, and git will just continue to follow the above rules.

Yeah, git won't care. If you screw up parenthood, you have a few problems:

 - the diffs may look really strange. In particular, if you list multiple 
   parents, the git "diff" functions will all just assume that it's a 
   merge, and a "git show" will start showing the combined diff (which is 
   usually empty).

   So if you end up having multiple parents, not because it was "really" a 
   merge, but because you use the other parent pointer to point to some 
   "source" for the patch, things like "git log -p" won't give nice output 
   any more. You need to manually ask for the diff with something like

	# show diff from second parent
	git diff commit^2..commit

   instead.

 - listing too _few_ parents is potentially more serious, if you have 
   reachability issues (ie you wanted to keep the other source around, but 
   since you didn't list it as a parent, git won't know that it had 
   anything to do with your commit, so it may be pruned away unless you 
   have some other way to reach it)

but if you just have a really strange merge algorithm, and the _data_ associated with the parents is "surprising" from the standpoint of the default merge, git really won't care at all.

Your usage does sound a bit strange.

On 8 Nov 2006, Linus Torvalds uttered the following:

It's what happens when a version-control system gets implemented as an emergency hack when moving from VMS, by people who don't really grok Unix shell scripting... and then you let fifteen years pass, and nobody dares touch the hack because it's so damned delicate. It took months of agony to implement crude half-functional branching in this. Writing a git porcelain should be vastly simpler, even with the overhead of a conversion tool as well.

Writing that conversion tool will be fun :( e.g. I'm going to have to identify branches by diffing/xdeltaing each version of a file with every single previous version of that file, and if the diff is smallest against a version other than the immediate ancestor, it's assumed to be a branch against that version. (I'm going to have to fake up packed refs for these tiny branches so that they're at least accessible in emergencies, gah.)

It's all, well, nasty. But all will be so much happier in the shining world of git.

Oh *good*, that's what I thought.

[snip more things which match my understanding]

I'll list the patch-merged parent as the second parent, so that you'll only get the mostly-useless huge diff from that if you actually ask for it, and will get a more useful result with ^.

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

It is a merge, so that's right. It's just a rather odd merge.

(I don't envisage actual *changes* being made in these commits except to resolve conflicts.)

Well, I was envisaging that the other parent pointer would point to the tip of the changes tree. Going back to that graph again:

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

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

The idea is that the patch-merge of trunks/old-and-grotty and heads/some-change-foo would consist textually of the diff between B and heads/some-change-foo, applied to trunks/old-and-grotty, and would list as its parents trunks/old-and-grotty, *and heads/some-change-foo*.

(Perhaps this isn't really a merge after all? Should merge parents be treated as differently as this? It'll all be covered over by the porcelain in any case: it won't be possible to confuse a trunk/ with a normal head and accidentally patch-merge in the wrong direction.)

Yeah, that would be bad.

Good.

Agreed. But there are hundreds of people banging on my door asking for a proper version control system, quilt isn't a proper version control system in that sense, and stgit has... issues when you try to distribute it and when you have a lot of people working on one tree at once: plus it doesn't fit our weird workflow with multiple parallel release branches, at least one active development trunk, and all changes done under a carefully-controlled bug tracking system (it's as if *every* change has a bugzilla ticket associated, *always*, and we expect to be able to get from ticket to change efficiently).

(We do both distribution and working-copy-sharing: the trees are too large to have one tree per person, not least because each tree requires an entire Oracle instance of its own to play with and massive amounts of memory; and we have geographically distributed sites with trees of their own.)

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

Nix <nix@esperi.org.uk> writes:

This is a standard "cherry-picking" practice.

When you think about commit ancestry, think of it this way:

   These commits I list as its parents of this new commit, and
   everything that leads to them, are what I considered when
   derived this commit.  This new child commit of them suits the
   purpose of _my_ branch better than any of these parent
   commits I took into consideration because of such and such
   reasons that I stated in its commit log message.

If you mark the resulting commit on old-and-grotty to have some-change-foo as one of its parents, because some-change-foo has almost everything 'latest' has (up to point B), you are also saying "I have considered everything that happened between old-and-grotty and B when making this commit".

What's implied by that statement is this, even though you do not explicitly say:

   I reject everything that happened on the development line
   that led to 'latest' up to point B since old-and-grotty was
   forked.

This is not necessarily a bad thing, by the way. For somebody who is trying to maintain extremely-stable branch by cherry picking only changes in a few narrow areas from the mainline would _want_ to leave most of the "new good stuff" out from his branch. That's why I emphasized _my_ a few paragraphs above.

But it is _so_ different from the mindset of usual "every branch makes progress _forward_ perhaps with different pace". In this example, this branch is actively choosing to stay behind and refusing to take changes from the 'latest'. So your users need to really understand what they are doing. For example, if there is another topic forked off of B (or at a later commit from there that leads to 'latest'), after your "funny merge" took place, even the usual merge strategies would work as expected by you --- it would still ignore the changes up to B because you told git to do so.

Also, if you make a good change on top of the resulting merge that _should_ be applicable to some-change-foo which is based on the 'latest', you cannot merge that back in the usual way. Usual git merge will find your first "funny merge" as the merge base, and because it chooses to reject everything leading to B, the merge result would look very similar to the set of changes based on old-and-grotty. Actually, that would even fast forward to the version you made into a phony "merge" out of the cherry-picked result.

But that is at least consistent with the statement you made when you created that commit. Staying behind at old-and-grotty suited _your_ branch'es purpose better than being based on 'latest'. And a person who is merging _your_ branch into some-change-foo, by choosing to merge that branch into the latter, is choosing to share your branch'es purpose, so it is natural a lot of the "good things" that happened up to B is rewound by that merge.

So I think as long as you and your users understand what is going on, I do not see a problem at either the mechanical level or the philosophical level. But I am sure it would confuse a lot of people, so please do not come back complaining that you ended up getting your users heads explode ;-).

On 8 Nov 2006, Junio C. Hamano spake thusly:

Yes, pretty much, except that we do *everything* by cherry-picking, and we want to track the cherry-picks in the same way that all other changes are tracked (i.e., a small branch for each (numbered) change, patching madly in all directions into a variety of trunks and release branches, with all those patches tracked.)

Yeah. This is the merge-base tracking that Linus mentioned, and it's not quite what I'm looking for :/ it's a sort of step-parent, really...

(which is not necessarily true: we might want to backport an earlier change, also on another `small change branch', later on. Stuff on the trunks themselves will never want to get backported, but if the merge-base algorithm traverses patch-merge parent links, it might consider that a `small change branch' has been merged when it actually hasn't.)

That's exactly what we're doing, across-the-board.

*hahahaaaaa*... hang on, that *was* a joke, right? ;)

OK, I think I need to find a way to notate in the patch-merged commit that one or more parents should be disregarded when searching for merge bases (and *only* when searching for merge bases). I think that will do what's wanted in all areas: i.e., it'll act like a cherry-pick that shows up in the logs/revlist and so on, but doesn't affect the semantics of later merges of stuff from anywhere except for the same limited branch.

(obviously trying to patch-merge B to A twice is always going to fail, whether or not merge-base traversal jumps into B: I don't think there's any real need to protect against that.)