Re: n-heads and patch dependency chains

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 [off-list ref] 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:

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

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 [off-list ref] 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.

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

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.

Sam Vilain wrote:

Jakub Narebski wrote:

quoted

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