n-heads and patch dependency chains

n-heads and patch dependency chains

[Sam Vilain]

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.

Re: n-heads and patch dependency chains

[Linus Torvalds]

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

Re: n-heads and patch dependency chains

[Sam Vilain]

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.

Re: n-heads and patch dependency chains

[Junio C Hamano]

Sam Vilain <sam@vilain.net> 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

Re: n-heads and patch dependency chains

[linux]

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

Oh... I thought he explained that pretty well.

The problem is a long-lived out-of-tree patch, or anything else that's
going to undergo repeated test releases before merging.

Think about swsusp2 or resiser4 or gfs or user-mode linux (now merged)
or nommu linux (now merged) or some similar large patch that takes a
lot of review.

The challenge is to be able to maintain a "latest Linux release + patches"
distribution and still keep a clean patch to submit to Linus that
doesn't have a zillion cross-merges because he doesn't like that,
and they confuse the development history.

It happens with a single developer when you're working on several
independent features and want a "latest & greatest" tree while still
keeping the feature branches separate.

This is the sort of thing that git-rebase and pu branches are used for,
and jgarzik's libata-dev ALL branch is basically a manually operated
hydra.


Some combination of automatic rebasing and automatic generation of
a pu/ALL tree seems like what's being asked for here.  The former
adds new history "before" the branch development, and the latter
adds additional changes "after" it.  All this subterfuge is in
the name of keeping the feature development history clean.


But all of darcs' "patch calculus" ideas are just basically
rebase strategies.  If someone can come up with a good alternative
to diff-and-patch, perhaps git-rebase can develop a number of
underlying strategies like git-merge.

Re: n-heads and patch dependency chains

[Sam Vilain]

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.

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

Re: n-heads and patch dependency chains

[Jakub Narebski]

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

Re: n-heads and patch dependency chains

[Andreas Ericsson]

Sam Vilain wrote:
> Junio C Hamano wrote:
> 
>>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

Re: n-heads and patch dependency chains

[Junio C Hamano]

Andreas Ericsson <ae@op5.se> writes:

> Sam Vilain wrote:
>> Junio C Hamano wrote:
>>> [ made change on a test branch that bundles topic branches
>>>   -- now want to commit back to the component topic branch ]
>>>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.

It feels to me that the above set of flags encourage a workflow
that:

 (1) modify the source and run tests in "test" branch;
 (2) have tool automatically adjust the change to match the other
     branch (i.e. the topic to be checked in) automatically;
 (3) make a commit, without a chance to do the final sanity
     check in the context of the branch being committed.

An individual topic branch itself might not be even testable
standalone, but at least I'd prefer to have a chance to double
check if the "patch commuting" (or "cherry-pick stage") did a
sensible thing [*1*].

As I said on the list in the past, I am from a school that
believes in not committing anything that has not been
tested/reviewed as a whole, especially when it comes to
individual developers, so I am not sure it is a good idea
in general to make it easy to do so to begin with.

But that is just my personal preference, and it does not
necessarily have to stop people wishing to have that feature to
have it, especially when there are enough of them.

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

I take it that you are volunteering to come up with an initial
round of implementation of these flags?

[Footnote]

*1* ... that's where "git checkout -m that-topic", perhaps
 followed by "git diff HEAD", comes in.

Re: n-heads and patch dependency chains

[Andreas Ericsson]

Junio C Hamano wrote:
> Andreas Ericsson <ae@op5.se> writes:
> 
> 
>>Sam Vilain wrote:
>>
>>>Junio C Hamano wrote:
>>>
>>>>[ made change on a test branch that bundles topic branches
>>>>  -- now want to commit back to the component topic branch ]
>>>>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.
> 
> 
> It feels to me that the above set of flags encourage a workflow
> that:
> 
>  (1) modify the source and run tests in "test" branch;
>  (2) have tool automatically adjust the change to match the other
>      branch (i.e. the topic to be checked in) automatically;
>  (3) make a commit, without a chance to do the final sanity
>      check in the context of the branch being committed.
> 

I don't fully understand 3 here. The workflow makes it easier to test 
how different topics work together, and make fixes to those that don't 
play well with others. Granted, it's not possible to test each topic by 
itself without checking it out, making the changes and re-compiling and 
so on, but since commits are so easy to undo I think it'd be nice to 
have the changes tracked. Another good thing is that fixes that apply on 
top of the "work-together" fixes, but that only make the topic branch 
build/work properly are completely rebase'able, and should result in a 
fast-forward merge since they share the same commit.


> An individual topic branch itself might not be even testable
> standalone, but at least I'd prefer to have a chance to double
> check if the "patch commuting" (or "cherry-pick stage") did a
> sensible thing [*1*].
> 

Understandable, and this workflow would still be available, but see below.


> As I said on the list in the past, I am from a school that
> believes in not committing anything that has not been
> tested/reviewed as a whole, especially when it comes to
> individual developers, so I am not sure it is a good idea
> in general to make it easy to do so to begin with.
> 

In short, you're from the school of centralized repositories. I used to 
be very careful about committing things too, but since I switched to git 
I happily commit smaller and more often, and regularly toss up a 
throw-away branch to make small commits that may or may not work and 
later apply the (tested) combined diff as a single commit or series of 
commits at points where I've tested one feature/fix to actually work as 
intended. This is nifty because people that help with testing can pull 
from my throw-away branch and get to work without me having to send them 
a tar-tree and a patch.

I believe in not *pushing* anything that hasn't been thoroughly tested, 
but the ability to track and commit possibly broken changes without it 
affecting the project as a whole is what makes git so great for me. In 
the CVS days distributed testing was a nuissance. With git it's smooth 
sailing.

> 
>>Those flags don't exist currently btw, in case someone's reading this
>>on the archives.
> 
> 
> I take it that you are volunteering to come up with an initial
> round of implementation of these flags?
> 

Unless someone can convince me I'm on the wrong track before I get off 
work, yes.

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

Re: n-heads and patch dependency chains

[Jakub Narebski]

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

Re: n-heads and patch dependency chains

[Catalin Marinas]

Sam Vilain <sam@vilain.net> 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.

As Linus pointed out, while darcs theory is interesting, it doesn't
work properly in practice. Dependency tracking can create problems
with merging. Darcs' patch commuting theory has (a big, IMHO) problem
since every time you pull a patch (or more) it needs to commute all
the patches back to the common ancestor. Over time, the merging
becomes slower and slower (i.e. even much slower than what darcs shows
in simple tests with the Linux kernel).

Inexact patch commuting can be achieved using diff3 (or merge) with 3
snapshots of the tree (the bottom of the patch, the top of the patch
and the current head on top of which the patch is being applied) which
GIT handles very well and fast since there is no need to commute
thousands of patches back to the common ancestor. The slight
disadvantage is that diff3 merging is not as exact as Darcs' patch
commuting but OK for 99% of the real cases.

StGIT is based on this inexact patch commuting "theory" and, with the
addition of upstream merging detection (based on reverse-applying), it
is seems to behave properly in almost all the cases (though you can
deliberately create some patches to break the algorithm).

I've been thinking about adding patch dependency tracking to StGIT but
only as a recommendation and not enforcement. The algorithm would be
similar to the upstream merging detection.

-- 
Catalin

Re: n-heads and patch dependency chains

[Andreas Ericsson]

Jakub Narebski wrote:
> 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?
> 

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

Re: n-heads and patch dependency chains

[Junio C Hamano]

I was re-reading the hydra stuff and realized I've seen the "a
cap that bundles independent tracks together" pattern somewhere
else in the history of git.

It is very similar to how "bind commit" would have worked.

With hydra, you keep independently mergeable tracks and bundle
their tips together:

    ---o--+
    ---o--+--*
    ---o--+

and advancement of each individual track is bundled together by
uncapping and recapping:

    ---o--o--+
    ---o--o--+--*
    ---o-----+

So a hydra cap would record:

 - the result "tree" of the (trivial) merge of the bundled tips;
 - the commit object name of the tips.

A "bind commit" proposal was made to support subprojects living
in their own subdirectories.  The picture to describe the commit
ancestry chain would be almost the same as the above picture,
except that it did not uncap and recap, but would have built its
own ancestry chain.

It had two different kinds of commit relationships: parenthood
and directory structure binding.  The component subprojects
lived in their own subdirectories (so if you are maintaining an
embedded Linux along with matching toolchain, you would have linux/
subdirectory that has the kernel hierarchy, gcc/, libc/, ...),
and commit objects had "bind commit-sha1 subdirectory-name"
lines to express how the components are bundled together.  A
commit object would have looked like this:

	tree fc9957b0052df6a8248420395bc9febd66194252
        parent 052df6a8248420395bc9febd66194252fc9957b0
        bind f6a8248420395bc9febd66194252fc9957b0052d linux/
        bind 20395bc9febd66194252fc9957b0052df6a82484 gcc/
	author A U Thor <author@example.com> 1144111304 -0700
        ...

The "parent" line is the commit ancestry as usual, and each
"bind" line names a commit object of component project and where
in the directory hierarchy the tree for that commit object would
be checked out.  The "tree" line records the result of grafting
the subprojects together.  So, for example, ls-tree -d fc9957
linux in the above example would have shown the tree object
f6a824^{tree}.

The structure forbid you from binding two separate projects at
the same directory in order to enforce clean separation of
subprojects, but if you allow multiple commits to be bound at
the root level, that could be used as a hydra cap.

I've done changes to support this at the core level; I think I
still have the code around somewhere (and the net never forgets
;-), so if you are interested you might want to take a look.

The trickest part was to tell rev-list --objects to work
sensibly so that an ancestry chain that contains this kind of
commits can be fetched and pushed.  The code unfortunately was
done before recent rev-list renovation so merging it to the
current codebase needs some understanding of how rev-list is
supposed to work, though.

Re: n-heads and patch dependency chains

[Jakub Narebski]

Junio C Hamano wrote:

> I was re-reading the hydra stuff and realized I've seen the "a
> cap that bundles independent tracks together" pattern somewhere
> else in the history of git.
> 
> It is very similar to how "bind commit" would have worked.
[...] 
> A "bind commit" proposal was made to support subprojects living
> in their own subdirectories.  The picture to describe the commit
> ancestry chain would be almost the same as the above picture,
> except that it did not uncap and recap, but would have built its
> own ancestry chain.

One of versions of "hydra commit" proposals, in the mail which is yet to
appear on Gmane git mailing list archive, and Gmane NNTP interface to git
mailing list, was to define commit dependency (to which chain commit would
get) in the terms of affecting files in the same directory. Simple
generalization to subtree (directory and its subdirectories) gives "bind
commit for subprojects".

> It had two different kinds of commit relationships: parenthood
> and directory structure binding.

Great minds think alike :-P -- we (Sam and I) were talking on #git about
adding "depends-on" field to commit.

In the email to write I would propose that instead of adding "depends-on"
field (or "bind") one can at least in prototype stage make parallel
development, commiting simultaneously to the tree where history is history,
and to the tree where history is dependence, or bind. I hope I will make
myself clearer in upcoming message; see Sam post beginning this thread - we
want to make both pictures (on the left and on the right) simultaneously.

-- 
Jakub Narebski
Warsaw, Poland

Re: n-heads and patch dependency chains

[Sam Vilain]

Junio C Hamano wrote:

>A "bind commit" proposal was made to support subprojects living
>in their own subdirectories.  The picture to describe the commit
>ancestry chain would be almost the same as the above picture,
>except that it did not uncap and recap, but would have built its
>own ancestry chain.
>  
>

I had considered that this would make directory subprojects possible,
but didn't want to draw attention to it.

Actually I'm now of the thinking that the problem is that we are using
'parent' for two things;

1. the merge bases for this merge, if a merge
(or the base for this change for a patch)

2. the historical precedent(s) for this commit.

In the single line of history case these are always the same. For an
actual merge they are also the same. However, when you are superceding a
merge with a newer merge, or mucking with history they are different.

So, I think all we need to make this all work smashingly well is to have
a new field called "prior" or perhaps "previous".

As well as being mostly backwards compatible and supporting grouping
your commits into topics in a single checkout, this would also have the
side effect of:

- directly supporting stgit / pg style patchset evolution, without
needing to use seperate branches for each release of your patchset. This
would not replace the need for stgit etc to wind the head - while
revising a patchset you really don't want the system to record
intermediate changes, just the ones you want to publish

- supporting tree subprojects (as it is a more specific use case)

- rewriting history! Without losing the old commits. Unless you wanted
to - say, for archiving old commits by rebasing the whole project off a
new revision.

It also does not suffer from the 'problem' in Andreas' "dual head
commit" approach that one commit will thenceforth be known by two commit
IDs.

>It had two different kinds of commit relationships: parenthood
>and directory structure binding.  The component subprojects
>lived in their own subdirectories (so if you are maintaining an
>embedded Linux along with matching toolchain, you would have linux/
>subdirectory that has the kernel hierarchy, gcc/, libc/, ...),
>and commit objects had "bind commit-sha1 subdirectory-name"
>lines to express how the components are bundled together.  A
>commit object would have looked like this:
>
>	tree fc9957b0052df6a8248420395bc9febd66194252
>        parent 052df6a8248420395bc9febd66194252fc9957b0
>        bind f6a8248420395bc9febd66194252fc9957b0052d linux/
>        bind 20395bc9febd66194252fc9957b0052df6a82484 gcc/
>	author A U Thor <author@example.com> 1144111304 -0700
>
>The "parent" line is the commit ancestry as usual, and each
>"bind" line names a commit object of component project and where
>in the directory hierarchy the tree for that commit object would
>be checked out.  The "tree" line records the result of grafting
>the subprojects together.  So, for example, ls-tree -d fc9957
>linux in the above example would have shown the tree object
>f6a824^{tree}.
>  
>

While the approach I outlined supports this in a way, it is subtly
different.

Firstly, the above approach makes it a hard requirement that the
independent series of commits are in seperate paths, you mention a fix
for this -

>The structure forbid you from binding two separate projects at
>the same directory in order to enforce clean separation of
>subprojects, but if you allow multiple commits to be bound at
>the root level, that could be used as a hydra cap.
>  
>

- but this means you are not storing the 'merged' tree in the commit,
which I think is a mistake. While we've been talking mostly about
dealing with managing changes simple enough to merge plainly for
simplicity of operations, this would *force* it to be so because you
need to allow anyone to check it out.

On the other hand - these bind commits enables tracking a sub-project in
a sub-directory whilst retaining the same commit IDs, to make tracking
easier.

Even this works using "prior", too - though you'd have to use surrogate
commits that link to the sub-project commit and wrapper tree object.

How does that sound?

Sam.

Re: n-heads and patch dependency chains

[Jakub Narebski]

First, hydras or n-head was invented to avoid capping and recapping, and
just advance it as a normal head (and to remember what are
subprojects/patch dependency chains/whatever to choose).

Second, we could generalize those extra commit references in commit
structure (be they "bind", "prior" or "previous", or "depends-on") and have
commit/merge pluggable helper manage them. And merge strategy may make use
of them.

Third, would using *directory* with for a N-HEAD (containing all the
subheads, subprojects, chains, branches, fibers, whatever) instead of an
ordinary file for HEAD be a good idea? For hydra if we want it to be easily
interweaved with ordinary commit I think we would also need the link for
bottom, hydra shoulder, hydra tail i.e. common commit being starting point
for all the chains, or subprojects (for subprojects it can be empty tree
commit).

-- 
Jakub Narebski
Warsaw, Poland

Re: n-heads and patch dependency chains

[Sam Vilain]

Jakub Narebski wrote:

>First, hydras or n-head was invented to avoid capping and recapping, and
>just advance it as a normal head (and to remember what are
>subprojects/patch dependency chains/whatever to choose).
>
>Second, we could generalize those extra commit references in commit
>structure (be they "bind", "prior" or "previous", or "depends-on") and have
>  
>

Note that these are all quite different types of references. "Bind"
implies an unmerged tree to be woven in on checkout, "prior and
"previous" a historical relationship, and "depends-on" the previous
commit that the change that this commit supplies was based on.

So, I think "parent" already means "depends-on" closely enough.

>commit/merge pluggable helper manage them. And merge strategy may make use
>of them.
>
>Third, would using *directory* with for a N-HEAD (containing all the
>subheads, subprojects, chains, branches, fibers, whatever) instead of an
>ordinary file for HEAD be a good idea? For hydra if we want it to be easily
>interweaved with ordinary commit I think we would also need the link for
>bottom, hydra shoulder, hydra tail i.e. common commit being starting point
>for all the chains, or subprojects (for subprojects it can be empty tree
>commit).
>  
>

This was similar to the original suggestion, of heads that have multiple
heads, or hydra. I think the basic rejection for this is that nothing is
then tracking the progression of the merged tree - unless you keep a
"cherry picked" tree for the combined work. And of course it is a
backwards incompatible change.

Sam.

Re: n-heads and patch dependency chains

[Jakub Narebski]

Sam Vilain wrote:

> Jakub Narebski wrote:

>>Third, would using *directory* with for a N-HEAD (containing all the
>>subheads, subprojects, chains, branches, fibers, whatever) instead of an
>>ordinary file for HEAD be a good idea? For hydra if we want it to be
>>easily interweaved with ordinary commit I think we would also need the
>>link for bottom, hydra shoulder, hydra tail i.e. common commit being
>>starting point for all the chains, or subprojects (for subprojects it can
>>be empty tree commit).
> 
> This was similar to the original suggestion, of heads that have multiple
> heads, or hydra. I think the basic rejection for this is that nothing is
> then tracking the progression of the merged tree - unless you keep a
> "cherry picked" tree for the combined work. And of course it is a
> backwards incompatible change.

I thought about keeping N-HEAD and HEAD and updating them simultaneously.
With extra fields in commit (however they would be named) use them, without
extra fields use ordinary branches, creating histories like in your example
in first post in the thread.

I.e. when doing [hydra] commit, add commit to ordinary history (recording
the time sequence of changes inside branch) advancing HEAD, and add commit
to appropriate chain/subhead/fiber in the N-HEAD and "advance N-HEAD". This
would make change backwards compatibile.

The problem would be to keep N-HEAD and HEAD to get out of sync, e.g. when
somebody updates only HEAD with an older git... well, we can always advance
N-HEAD to HEAD using commits from the time they were in sync to the current
head state.

-- 
Jakub Narebski
ShadeHawk on #git
Warsaw, Poland

Re: n-heads and patch dependency chains

[Jon Loeliger]

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

Re: n-heads and patch dependency chains

[Junio C Hamano]

Jon Loeliger <jdl@freescale.com> writes:

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

To be consistent, I think the result should be "as if the change
was commited only to the topic-branch and then the topic-branch
was *merged* into the testing-branch", since you start your
testing branch as "being the result of several merged topic-branches".

I do that (manually) all the time, with:

	$ git checkout next
        $ hack hack hack

        $ git checkout -m one/topic
        $ git commit -o this-path that-path
        $ git checkout next
        $ git pull . one/topic

Giving a short-hand for the last four-command sequence would
certainly be nice.

> 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? :-)

Likewise... ;-)

Re: n-heads and patch dependency chains

[Andreas Ericsson]

Junio C Hamano wrote:
> Jon Loeliger <jdl@freescale.com> writes:
> 
> 
>>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.
> 
> 
> To be consistent, I think the result should be "as if the change
> was commited only to the topic-branch and then the topic-branch
> was *merged* into the testing-branch", since you start your
> testing branch as "being the result of several merged topic-branches".
> 
> I do that (manually) all the time, with:
> 
> 	$ git checkout next
>         $ hack hack hack
> 
>         $ git checkout -m one/topic
>         $ git commit -o this-path that-path
>         $ git checkout next
>         $ git pull . one/topic
> 
> Giving a short-hand for the last four-command sequence would
> certainly be nice.
> 

Ah. That's easier than what I originally looked at doing.

> 
>>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? :-)
> 
> 
> Likewise... ;-)
> 

Sorry to disappoint you so far. I'll see if I can turn up my 
shell-skills a notch or two and get the hang of the commit-script enough 
to implement it.

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