Re: n-heads and patch dependency chains

Sam Vilain wrote:

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

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

  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