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:

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:

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.

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 <sam@vilain.net> writes:

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.

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:

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.

And a good principle that is, too.

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.

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

That's a nice illustration of it, yes.

Sam.

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

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

Andreas Ericsson <ae@op5.se> writes:

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.

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.

Junio C Hamano wrote:

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.

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

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.

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

Andreas Ericsson wrote:

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

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

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

Jon Loeliger <jdl@freescale.com> writes:

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.

Likewise... ;-)

Junio C Hamano wrote:

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

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.

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.

Junio C Hamano wrote:

[...] 

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

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.

Junio C Hamano wrote:

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.

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 -

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

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 wrote:

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.

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.

Sam Vilain wrote:

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.

Sam Vilain wrote:

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

[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

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.

Sam Vilain <sam@vilain.net> wrote:

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.