Subject: Re: Multi-headed branches (hydra? :)) for basic patch calculus

From: Sam Vilain <[email-masked]>
Date: Mon, 03 Apr 2006 11:15:43 +1200

Jakub Narebski wrote:

>>However, if there was support for "hydra", or heads that are multiple
>>commit IDs (and necessarily, no blobs in corresponding paths in their
>>trees that are not identical), then you would not need to destroy and
>>recreate this dummy merge head commit to model your patch history in
>>this manner.
>>    
>>
>[...]
>
>I'm not sure if "hydras", i.e. multi-commit 'heads' are what would make
>GIT able to use some of Darcs patches calculus ideas. If I understand
>correctly in GIT 'head' (and 'tag') not only identifies commit (commits
>in hydra[1]) but also tree (in hydra it is result of trivial (?) merge).
>  
>

Whether it is stored as a procession of trees or as a sequence of
patches does not actually make a difference to a mathematician.

This might not sound right at first, but think that it does not matter
whether you have the number "4" which came after "3" that you store it
as "4 (3 was prior)" or "1+1+1+1".  ℕ (the set of natural numbers) is
itself defined by induction, yet this is not important for functions
that deal with natural number elements.

>Wouldn't it be better to somehow represent rather partial ordering between
>commits in history, to have something from Darcs in GIT?  Although I'm not
>sure about efficiency, and if we should do detect commits dependency -- or
>in other words partial ordering of commits/patches -- at commit or at
>merge.
>

That is more or less what I proposed, except that the ordering is built
at commit time to pick a best head rather than when you try to pull the
patch, which seems a trivial difference at best.

I think git-commit --hydra is called for.

First we define a "hydra leash", I can think of two definitions:

 - a hydra leash is a specially marked commit
 - a hydra leash is a commit that has multiple parents, and is
   the result of just an index merge of its parents

We must also define the concept of a commit being "against" the head(s)
of a hydra.

With that term in mind, we can make "--hydra" do as follows:

 a) find the head(s) of the hydra that the commit is against;
 b) apply the commit, and set its parents to those head(s)
 c) put the hydra leash back on.

Ideally the leash should not have the previous leash as one of its
parents; that leash was always transient and keeping its history is
perhaps not required, and would break the latter leash detection method
described above.

Instead, git-pull et al should know what to do.

> And if we should remember (or cache) partial ordering/dependency
>info...
>
>[1] I've detected some confusion in this terminology. "Hydra" is
>multi-headed moster, yet in your ptoposal it is one head that has multiple
>bodies... and "octopus" is taken. I guess the terminology should be
>switched (octopus <-> hydra).
>  
>

A head is a head because there is only one of it, and it's at the top. 
If the leash is transient then it doesn't really exist, and therefore
can't be called a head.  So, you look instead at the heads remaining,
and where you expected to see an entity with a single head you see many
heads.

Sam.