n-heads and patch dependency chains

Hi all,

"Patch dependency chains", the best plain-English term we could find for
the scary sounding darcs term "patch calculus", are said by some to be a
very good reason to use a system like darcs, even to some its
fundamental advantage over systems such as git.

The question is, to what extent is this point true?

To get a feel for the issues involved, I tried applying an example
n-head and patch dependency logic to a "real" project that had a small
enough number of commits to make it feasible to construct everything
manually.

A side-by-side comparison of the commit history with n-head commits
(left pane) and without (right pane) is here:

  http://utsl.gen.nz/git/hydra-vs-regular.png

Some important points to note:

  0. gitk is re-ordering the commits to try to make the graph tidy,
     so don't worry that the commits are in a different order

  1. commits were considered dependent on the last commit(s) that
     delivered the file(s) they modified.  As in, the user specified
     that extra heads be created wherever possible, including
     splitting heads.

  2. the "rolling" n-head was continually discarded.  "n-head" is
     misspelt :) as "hydra-head" in the diagrams.

  3. patches that just added new files were performed by first
     making a new repository, adding those files and committing.
     this is why there are a lot of "starting points" on the tree

I think we can conclude from this:

  - this is not impossible using the current model, and some extra
    useful information can be seen in the tree that shows more real
    dependency information and relationships between individual commits

  - doing automatic n-head creation would probably be madness, as
    far too many useless heads are created (though it is almost
    guaranteed that supporting 'patch commuting' a la darcs would
    make this *even worse* as it would mean that you could potentially
    have even more heads)

  - the current tools make this style of development difficult.

The bugs:

  - git-merge-octopus isn't capable of merging commits where there is
    no common commit, but none was needed as the commits' trees don't
    overlap.

    That is, with "git-pull -s octopus . head1 head2 head3 ..."
    you get the error:

      Unable to find common commit with 42f49cc...

    But pulling the branches individually works fine;

      Merging HEAD with 42f49cc...
      Merging:
        c0805...
        42f49...
      found 1 common ancestor(s):
      1 virtual commit

    That 'branch' was created by setting up a new git repo in another
    path, then using 'git-fetch' to pull it into the local one.

  - for some reason I had to list "-s ours" twice to git-pull when
    manually making the octopus merge nodes

  - `git-pull --no-commit -a' suffers from the same problem

  - some tools (such as the diff window in gitk) produce *very*
    strange output if you try to merge the heads and apply the next
    patch in the same go.

The open questions:

  - would it make a difference if this automatic patch dependency
    information was stored using a different type of relationship?

  - would this be more useful if the initial n-head creation was more
    manual, like topic branches?  And if it did work like this, would
    an n-head pull feature enable the 'pu' development model to work
    seamlessly?

  - how useful are the other benefits of dependent commits?

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

So there we go, anyway.  If some form of patch dependency system is to
be included in git, then I hope this message helps to explain the
practical problems and give the would-be author a good head start :)

Hot potato into the aether, anyone?

Sam.

On Mon, 3 Apr 2006, Sam Vilain wrote:

"Patch dependency chains", the best plain-English term we could find for
the scary sounding darcs term "patch calculus", are said by some to be a
very good reason to use a system like darcs, even to some its
fundamental advantage over systems such as git.

I really think that darcs is just "nice theory", and has nothing to do 
with real life.

Terms like "patch calculus" may sound cool and useful, but let's face it, 
the proof is in the pudding, and quite frankly, I would bet that trying to 
do something like that on a real project would just be a total disaster.

I want my merges simple. I want them to take a couple of seconds. I don't 
want to see strange patch dependencies that nobody cares about. And I very 
much don't want to see theory over practice.

		Linus

On Mon, 2006-04-03 at 07:29 -0700, Linus Torvalds wrote:

I really think that darcs is just "nice theory", and has nothing to do 
with real life.

Terms like "patch calculus" may sound cool and useful, but let's face it, 
the proof is in the pudding, and quite frankly, I would bet that trying to 
do something like that on a real project would just be a total disaster.

I want my merges simple. I want them to take a couple of seconds. I 
don't want to see strange patch dependencies that nobody cares about.

Dave really was right with his keynote comment about nomenclature in
Dunedin.  I shouldn't even have put the term "patch calculus" in the
e-mail body at all :-P

Seriously, though, the rest of the report basically agrees with your
position.  Sorry if it was rambling and that key message wasn't clear.

We did kind of work out along the way that the best bits of patch
calculus were probably obtained with good use of topic branches.  Likely
if there are any key advances to be made, they will be found in the form
of clever ways to manage topic branches.

 And I very much don't want to see theory over practice.

Theory?  Do I *look* like a theorist?

(looks around sheepishly)

This was valuable cross-culture field research!

(looks around at rather non-plussed eyes)

Hey, I found it quite enlightening, and at least a few other people were
amused by the ordeal.  And I learned a little bit more about git along
the way.

(waits for a 'hear', 'hear'!  silence.)

I'll get me coat.

Sam.

Sam Vilain [off-list ref] writes:

I think we can conclude from this:

  - this is not impossible using the current model, and some extra
    useful information can be seen in the tree that shows more real
    dependency information and relationships between individual commits

  - doing automatic n-head creation would probably be madness, as
    far too many useless heads are created (though it is almost
    guaranteed that supporting 'patch commuting' a la darcs would
    make this *even worse* as it would mean that you could potentially
    have even more heads)

I suspect people have hard time grasping _why_ you are jumping
through hoops.  At least I do.  What problem are you trying to
solve?  You perhaps described your mechanism well enough, but it
is not quite clear to me what kind of operations are made easier
with this exercise, against which possible downside of it, if
any, would be judged.

  - the current tools make this style of development difficult.

Git was born from necessity, and we have been aiming to have
tools to do what are commonly needed.  It is not surprising to
see existing tools do not support modes of operations that are
"unusual" (meaning, things we have not done with git so far).
Also we do not tend to do things only because we can.

Now admittably I am guilty of having done a few things only
because we can.  Octopus is an example.  Making an Octopus only
because you can does not buy you much, other than its coolness
value, and it would make exporting the history to other SCMs
somewhat harder I suspect, and it makes bisecting more
expensive [*1*].

For example, the point jdl raised during the discussion is far
easier to understand.  When working on multiple topics, he often
needs to test them as a whole, so he pulls them into a test
branch (can be a throwaway branch).  When he needs to do fixups,
it is most efficient to do compile/run test while still in the
test branch, but after things test out, in order to keep
logically different things separate, he needs to go back to
relevant topic branches and make a commit.  This is painful --
are there ways to make this easier [*2*]?

Would patch commutation calculus help with his problem?

I suspect patch commutation could be used to solve his problem,
but if it does not, it does not mean what you are trying to do
with hydra is not interesting.  It just means from your
descriptions it is not clear what real problems hydra is trying
to solve, and I misunderstood that it is related to his problem
(just like jdl did, I suspect).

So can you step back a bit and start from describing what
problem you are trying to solve, before describing the
mechanisms you think would help?

One thing I can think of that could potentially come out of your
approach would be an alternative implementation of what StGIT
does.  Inside a local developer repository, being able to
reorder patches and rewrite them flexibly is very useful.

While I agree with Linus's reaction "I want my merges fast", I
am not necessarily so negative about the approach.  For example,
if you use it only as a tool to reorder and clean-up local
development history to a presentable form (IOW, using hydra to
manage your development, but the result exposed to the outside
world is exported from that hydra into a more linear form, that
does not give other people a heart attach when they look at the
ancestry graph in gitk), you would not negatively affect other
people who work with you.


[Footnote]

*1* Do not get me wrong.  Octopus is sometimes the most natural
way to express what happened, but the case it applies to is
quite narrowly defined -- to merge in independent branches that
happened to mature at the same time together.  So the tool
discourages you from making an Octopus that is not trivial,
deliberately.

*2* I see two approaches, the more obvious being "git checkout
-m that-topic".  Just edit (but not update-index) on top of
test, have "checkout -m" adjust your changes to the topic branch
you want to commit to, make a commit there, and then come back
to the test branch, and merge the topic branch again.

Another obvious strategy would be to make commits on top of
"test" and then cherry-pick them back on top of the relevant
topics later.
    
        topicA                  You have three topics
         o---o                  you need to test together...
        /
    ---o---o topicB
        \ 
         o---o
        topicC

 ==>
    
        topicA                  So merge them up and start testing.
         o---o
        /     \      
    ---o---o---T
        \     /
         o---o
        topicB

 ==>
     
        topicA                  But you find problems, and fix them
         o---o                  up as you go along...
        /     \      
    ---o---o---T---1---2
        \     /
         o---o
        topicB

 ==>
    
        topicA                  Later you cherry-pick them into
         o---o---1'             relevant topics.
        /
    ---o---o topicB
        \ 
         o---o---2'
        topicC

 ==>

        topicA                  Next round of test will continue
         o---o---1'             by rebuilding the test branch
        /         \
    ---o---o-------T
        \         /
         o---o---2'
        topicC

Junio C Hamano wrote:

I suspect people have hard time grasping _why_ you are jumping
through hoops.  At least I do.  What problem are you trying to
solve?  You perhaps described your mechanism well enough, but it
is not quite clear to me what kind of operations are made easier
with this exercise, against which possible downside of it, if
any, would be judged.
[...]
So can you step back a bit and start from describing what
problem you are trying to solve, before describing the
mechanisms you think would help?
 

As a research exercise the principle purpose was first to see if there
is a natural fit with git's data model, and secondly to investigate what
benefits were possible from it. In a sense it was "bottom-up" investigation.

quoted

 - the current tools make this style of development difficult.
   

Git was born from necessity, and we have been aiming to have
tools to do what are commonly needed.  It is not surprising to
see existing tools do not support modes of operations that are
"unusual" (meaning, things we have not done with git so far).
Also we do not tend to do things only because we can.
 

And a good principle that is, too.

For example, the point jdl raised during the discussion is far
easier to understand.  When working on multiple topics, he often
needs to test them as a whole, so he pulls them into a test
branch (can be a throwaway branch).  When he needs to do fixups,
it is most efficient to do compile/run test while still in the
test branch, but after things test out, in order to keep
logically different things separate, he needs to go back to
relevant topic branches and make a commit.  This is painful --
are there ways to make this easier [*2*]?

Would patch commutation calculus help with his problem?
 

I'd provisionally say "yes, that's the fit". It's just like having
multiple topic branches all checked out at once, with commits going to
the appropriate branch as necessary.

In my experiment, when a commit touched files on more than one head,
then the heads would be collapsed to a single one, like a merge. As the
nature of the setup was such that you didn't explicitly name heads, this
was a natural thing to do. But if you're naming them, you probably would
want some way to choose between applying the commit to just one head,
both heads, or collapsing the two heads into one.

That approach actually offers the most flexibility - a porcelain could
do full darcs-like patch calculus if it wanted, or saner explicit topic
branching.

One thing I can think of that could potentially come out of your
approach would be an alternative implementation of what StGIT
does.  Inside a local developer repository, being able to
reorder patches and rewrite them flexibly is very useful.
 

Oh, I didn't think of that. Were you thinking of an extra head for each
"uncommitted" chain of related patches? That's an interesting idea.

I think it might really help use cases like the -mm Linux tree, where
bunches of related commits are typically applied in a series, but you
especially want to track inter-set dependencies. Currently stgit takes a
very long time to import the split -mm series :-)

Another obvious strategy would be to make commits on top of
"test" and then cherry-pick them back on top of the relevant
topics later.
   
       topicA                  You have three topics
        o---o                  you need to test together...
       /
 [...]
       \         /
        o---o---2'
       topicC
 

That's a nice illustration of it, yes.

Sam.

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

Sam Vilain wrote:

Junio C Hamano wrote:

quoted

For example, the point jdl raised during the discussion is far
easier to understand.  When working on multiple topics, he often
needs to test them as a whole, so he pulls them into a test
branch (can be a throwaway branch).  When he needs to do fixups,
it is most efficient to do compile/run test while still in the
test branch, but after things test out, in order to keep
logically different things separate, he needs to go back to
relevant topic branches and make a commit.  This is painful --
are there ways to make this easier [*2*]?

Would patch commutation calculus help with his problem?

I'd provisionally say "yes, that's the fit". It's just like having
multiple topic branches all checked out at once, with commits going to
the appropriate branch as necessary.

Wouldn't "git commit -M -b topic", for committing to a different branch 
than what is checked out (-b) and also to the checked out branch (-M) 
have the same beneficial effects, but without the complexity of hydras 
and patch dependency theory? It would only remove the cherry-pick stage 
though, but perhaps it's good enough. Although when I think about it, -b 
<branch> for committing to another branch and -B <branch> for doing the 
above probably makes more sense.

Those flags don't exist currently btw, in case someone's reading this on 
the archives.

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

Andreas Ericsson wrote:

Wouldn't "git commit -M -b topic", for committing to a different branch
than what is checked out (-b) and also to the checked out branch (-M)
have the same beneficial effects, but without the complexity of hydras
and patch dependency theory? It would only remove the cherry-pick stage
though, but perhaps it's good enough. Although when I think about it, -b
<branch> for committing to another branch and -B <branch> for doing the
above probably makes more sense.

Do you mean that you commit current state to the checked out (working)
branch, and commit *changes* (i.e. apply patch) to a different branch?

-- 
Jakub Narebski
Warsaw, Poland

Jakub Narebski wrote:

Andreas Ericsson wrote:

quoted

Wouldn't "git commit -M -b topic", for committing to a different branch
than what is checked out (-b) and also to the checked out branch (-M)
have the same beneficial effects, but without the complexity of hydras
and patch dependency theory? It would only remove the cherry-pick stage
though, but perhaps it's good enough. Although when I think about it, -b
<branch> for committing to another branch and -B <branch> for doing the
above probably makes more sense.

Do you mean that you commit current state to the checked out (working)
branch, and commit *changes* (i.e. apply patch) to a different branch?

No, I mean that this would commit both to the testing branch (being the 
result of several merged topic-branches) and to the topic-branch merged 
in. Commit as in regular commit, with a commit-message and a patch. The 
resulting repository would be the exact same as if the change was 
committed only to the topic-branch and then cherry-picked on to the 
testing-branch.

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

On Tue, 2006-04-04 at 06:47, Andreas Ericsson wrote:

No, I mean that this would commit both to the testing branch (being the 
result of several merged topic-branches) and to the topic-branch merged 
in. Commit as in regular commit, with a commit-message and a patch. The 
resulting repository would be the exact same as if the change was 
committed only to the topic-branch and then cherry-picked on to the 
testing-branch.

I am your number one fan!  If I finish reading these 600+
messages, will I find out you have already implemented it,
it's committed, and you just need me to test it now? :-)

jdl