Re: n-heads and patch dependency chains

From: Jakub Narebski <jnareb@gmail.com>
Date: Apr 4, 2006, 00:51 UTC
Message-ID: <e0sfti$1nb$1@sea.gmane.org>
In-Reply-To: <4430D352.4010707@vilain.net>

Sam Vilain wrote:

Show 7 quoted lines

> The IRC log:
> 
> 17:45 < mugwump> the other suggestions look quite good.  I don't know
>                  how I got roped into spending a whole day on this :)
> 17:46 < mugwump> oh yeah, I remember now.  somebody asked for a
>                  comparison between darcs and git
> 17:46  * ShadeHawk whistles innocently

Let me describe in my own words results of IRC discussion and posts on Git
Mailing List, both in this thread and in "Multi-headed branches (hydra? :))
for basic patch calculus" one
  http://permalink.gmane.org/gmane.comp.version-control.git/18258
and Sam Vilain work (prototype). It might help with understanding Sam's
work; and I hope Sam would correct me if I'm wrong.

It started I think as a way to describe (represent, save) in core GIT the partial ordering of patches (commits) by dependence Darcs uses in it's patch algebra theory {i.e. patch1 <- patch2 if patch2 depends on patch1 (patches does not commute)} at *commit time*.

Show 16 quoted lines

> Say you've got a sequence of changes like this:
> 
> 1. add foo.c
> 2. add bar.c
> 3. modify foo.c
> 4. modify bar.c
> 
> The darcs-like operation of this would be to have two sequences of
> ordered patches that combine to a final result.  ie:
> 
>   1 <- 3
>   2 <- 4
> 
> Unless you jump through hoops, git will represent it as:
> 
>   1 <- 2 <- 3 <- 4.

[the direction of arrows has changed in this quote]

First part of the idea is to represent the partial ordering of patches by their interdependence (the sequences, chains of ordered patches) using "parent" relation. (There was also idea of adding another field(s) "depends-on" to represent only commit dependency in addition to "parent(s)" relations defining history.)

Second part of the idea is to avoid creating, then recreating the final something (commit) which combines commit chains to a final result

Show 7 quoted lines

>
>   1 -> 3  \
>            >- head
>   2 -> 4  /
> 
> Where "head" is a merge commit that just combines the trees of 3 and 4.
>

So an idea of "hydra", or "n-head" was born, which is just virtual trivial merge commit which gives us final result, HEAD of chains. (It is trivial because trees 3 and 4 are independent, merge without conflicts.) And also related idea of "hydra commit", which automatically adds commit to correct chain (places commit in correct place of partial ordering by dependence) and advances n-head (virtual trival merge commit which is HEAD).

The side effects (perhaps more important than making use of Darcs patch algebra theory, and Darcs merge algorithm) is that we have automatical topic branches, or to be more exact automatical dependency (sub)branches (commit/patch dependency chains).

Does it make sense?

To be continued...

In next installment we will see how "hydra commits" or "n-heads" might work: simplifications in defining commit dependency, "coarse" ordering i.e. no branching dependency chains, updating n-head during commit and during merge. Sam Vilain wrote some scripts for "proving of concept"; I would present my idea on that matter, untested.

-- 
Jakub Narębski
ShadeHawk on #git
Poland