Multi-headed branches (hydra? :)) for basic patch calculus

Multi-headed branches (hydra? :)) for basic patch calculus

[Sam Vilain]

>From a discussion on #git, the idea was raised of "multi-headed
branches"

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.

However, you *could* represent it as:

  1 -> 3  \
           >- head
  2 -> 4  /

Where "head" is a merge commit that just combines the trees of 3 and 4.

If somebody adds a commit (5) that changes "foo.c" again, the darcs
history would change to:

  1 -> 3 -> 5
  2 -> 4

To represent this in git you could just roll back the head merge commit,
push commit 5 on that branch, then make a new head:

  1 -> 3 -> 5 \
               >- head
  2 -> 4 -----/

However, if there was support for "hydra", or heads that are multiple
commit IDs (and necessarily, no blobs in corresponding paths in their
trees that are not identical), then you would not need to destroy and
recreate this dummy merge head commit to model your patch history in
this manner.

If the plumbing or a porcelain could be smart enough to automatically
create hydra when patches are not dependent, then many of the benefits
of patch calculus might come for free, without having to create these
complicated sounding entities manually.

Of course this doesn't give you the symbolic labelling of patches that
can allow darcs to detect already applied, but "mutated" patches, but
that might not matter in practice.

Sam.

Re: Multi-headed branches (hydra? :)) for basic patch calculus

[Jakub Narebski]

Sam Vilain wrote:

> From a discussion on #git, the idea was raised of "multi-headed
> branches"
[...] 
> If somebody adds a commit (5) that changes "foo.c" again, the darcs
> history would change to:
> 
>   1 -> 3 -> 5
>   2 -> 4
> 
> To represent this in git you could just roll back the head merge commit,
> push commit 5 on that branch, then make a new head:
>
>   1 -> 3 -> 5 \
>                >- head
>   2 -> 4 -----/
> 
> However, if there was support for "hydra", or heads that are multiple
> commit IDs (and necessarily, no blobs in corresponding paths in their
> trees that are not identical), then you would not need to destroy and
> recreate this dummy merge head commit to model your patch history in
> this manner.
[...]

I'm not sure if "hydras", i.e. multi-commit 'heads' are what would make
GIT able to use some of Darcs patches calculus ideas. If I understand
correctly in GIT 'head' (and 'tag') not only identifies commit (commits
in hydra[1]) but also tree (in hydra it is result of trivial (?) merge).
Wouldn't it be better to somehow represent rather partial ordering between
commits in history, to have something from Darcs in GIT? Although I'm not
sure about efficiency, and if we should do detect commits dependency -- or
in other words partial ordering of commits/patches -- at commit or at
merge. And if we should remember (or cache) partial ordering/dependency
info...

[1] I've detected some confusion in this terminology. "Hydra" is
multi-headed moster, yet in your ptoposal it is one head that has multiple
bodies... and "octopus" is taken. I guess the terminology should be
switched (octopus <-> hydra).

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: Multi-headed branches (hydra? :)) for basic patch calculus

[Sam Vilain]

Jakub Narebski wrote:

>>However, if there was support for "hydra", or heads that are multiple
>>commit IDs (and necessarily, no blobs in corresponding paths in their
>>trees that are not identical), then you would not need to destroy and
>>recreate this dummy merge head commit to model your patch history in
>>this manner.
>>    
>>
>[...]
>
>I'm not sure if "hydras", i.e. multi-commit 'heads' are what would make
>GIT able to use some of Darcs patches calculus ideas. If I understand
>correctly in GIT 'head' (and 'tag') not only identifies commit (commits
>in hydra[1]) but also tree (in hydra it is result of trivial (?) merge).
>  
>

Whether it is stored as a procession of trees or as a sequence of
patches does not actually make a difference to a mathematician.

This might not sound right at first, but think that it does not matter
whether you have the number "4" which came after "3" that you store it
as "4 (3 was prior)" or "1+1+1+1".  ℕ (the set of natural numbers) is
itself defined by induction, yet this is not important for functions
that deal with natural number elements.

>Wouldn't it be better to somehow represent rather partial ordering between
>commits in history, to have something from Darcs in GIT?  Although I'm not
>sure about efficiency, and if we should do detect commits dependency -- or
>in other words partial ordering of commits/patches -- at commit or at
>merge.
>

That is more or less what I proposed, except that the ordering is built
at commit time to pick a best head rather than when you try to pull the
patch, which seems a trivial difference at best.

I think git-commit --hydra is called for.

First we define a "hydra leash", I can think of two definitions:

 - a hydra leash is a specially marked commit
 - a hydra leash is a commit that has multiple parents, and is
   the result of just an index merge of its parents

We must also define the concept of a commit being "against" the head(s)
of a hydra.

With that term in mind, we can make "--hydra" do as follows:

 a) find the head(s) of the hydra that the commit is against;
 b) apply the commit, and set its parents to those head(s)
 c) put the hydra leash back on.

Ideally the leash should not have the previous leash as one of its
parents; that leash was always transient and keeping its history is
perhaps not required, and would break the latter leash detection method
described above.

Instead, git-pull et al should know what to do.

> And if we should remember (or cache) partial ordering/dependency
>info...
>
>[1] I've detected some confusion in this terminology. "Hydra" is
>multi-headed moster, yet in your ptoposal it is one head that has multiple
>bodies... and "octopus" is taken. I guess the terminology should be
>switched (octopus <-> hydra).
>  
>

A head is a head because there is only one of it, and it's at the top. 
If the leash is transient then it doesn't really exist, and therefore
can't be called a head.  So, you look instead at the heads remaining,
and where you expected to see an entity with a single head you see many
heads.

Sam.

Re: Multi-headed branches (hydra? :)) for basic patch calculus

[Jakub Narebski]

Sam Vilain wrote:

> Jakub Narebski wrote:

>>Wouldn't it be better to somehow represent rather partial ordering between
>>commits in history, to have something from Darcs in GIT?  Although I'm not
>>sure about efficiency, and if we should do detect commits dependency -- or
>>in other words partial ordering of commits/patches -- at commit or at
>>merge.
>>
> 
> That is more or less what I proposed, except that the ordering is built
> at commit time to pick a best head rather than when you try to pull the
> patch, which seems a trivial difference at best.
> 
> I think git-commit --hydra is called for.
> 
> First we define a "hydra leash", I can think of two definitions:
> 
>  - a hydra leash is a specially marked commit
>  - a hydra leash is a commit that has multiple parents, and is
>    the result of just an index merge of its parents
> 
> We must also define the concept of a commit being "against" the head(s)
> of a hydra.
> 
> With that term in mind, we can make "git commit --hydra" do as follows:
> 
>  a) find the head(s) of the hydra that the commit is against;
>  b) apply the commit, and set its parents to those head(s)
>  c) put the hydra leash back on.

Let's reiterate to check if I understand that:

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
5. modify foo.c again

You want patch/commit dependency, which is partial ordering of
patches/commits/trees:

  1 -> 3 -> 5
  2 -> 4

be represented as

  1 -> 3 -> 5 \
               >- head
  2 -> 4 -----/


First, to clean up my error, head is not a commit. Head is floating pointer
to the top commit (something like "last" pointer in the list, except we
don't have list but directed acyclic graph). Getting head means getting the
tree corresponding to that commit.

Your hydra is a set of pointers to top commit. Getting hydra means getting
the tree which is trivial merge of top commits (no conflicts!). Ordinary
head is just hydra with one top commit.

Do I understand that hydra is constructed *at commit*?


Second, to repeat my patches vs. trees arguments. In GIT now if one gets
(4), one would get tree with files foo.c and bar.c added, both modified.
With hydra, and with the arrows meaning that one commit is parent of the
other (unless you modify commit structure too), one would get tree with
only file bar.c added, and modified.

BTW, the arrows should be in other direction to show how commits refers to
toher commits.


Third, let us consider different possible "git-commit --hydra" in above
hydra [head] sitiation:

a.) 6. modify bar.c dependent on 4

  1 -> 3 -> 5 \
               >- head/hydra
  2 -> 4 -> 6 /

b.) 6. modify foo.c independently of 5, depends on changes in 3: 
it is getting complicated.

  1 -> 3 -> 5 --\
        \        \
         -> 6 ---->- head
                 /
  2 -> 4 -------/

c.) 6. moves some content from foo.c to bar.c, thus depending (at least) on
both 3 (let's assume that independently 5) and on 4. How to represent that
without modyfying commit structure (and not only head structure)? If we use
multiple commits as parents for 6, how do we distinguish between 6 being
merge commit of commits 3 and 4, and 6 depending on commits 3 and 4?

  1 -> 3 -> 5 --\
        \        \
     (?) -> 6 ---->- head
        /        /
  2 -> 4 -------/


Fourth, the fact that commits do not generate conflicts doesn't mean that
they are independent. Let's assume that we are introducing new function for
example. If we change first header file foo.h, *commit* that change (not
the best practice/workflow, I know) resulting in commit (1), then change
file foo.c resulting in commit (2), then commits (1) and (2) are
independent in the sense of commits, and so would say the tool which
detects dependencies (partial ordering). But actually commits (1) and (2)
depends on each other, and commiting both one after another to the same
branch says so now.


For more comments I would need to read theory of patches in more detail
first.

I hope that all the above makes sense...
-- 
Jakub Narebski
Warsaw, Poland

Re: Multi-headed branches (hydra? :)) for basic patch calculus

[J. Bruce Fields]

On Sun, Apr 02, 2006 at 04:07:32PM +1200, Sam Vilain wrote:
> To represent this in git you could just roll back the head merge commit,
> push commit 5 on that branch, then make a new head:
> 
>   1 -> 3 -> 5 \
>                >- head
>   2 -> 4 -----/
> 
> However, if there was support for "hydra", or heads that are multiple
> commit IDs (and necessarily, no blobs in corresponding paths in their
> trees that are not identical), then you would not need to destroy and
> recreate this dummy merge head commit to model your patch history in
> this manner.

What's the advantage to doing this?

> If the plumbing or a porcelain could be smart enough to automatically
> create hydra when patches are not dependent, then many of the benefits
> of patch calculus might come for free, without having to create these
> complicated sounding entities manually.

What are the benefits of patch calculus?  (What is it?  The only
explanation I've seen is at
http://abridgegame.org/darcs/manual/node8.html, but I don't find it very
helpful.)

--b.

Re: Patch calculus

[Jakub Narebski]

J. Bruce Fields wrote:

> What are the benefits of patch calculus?  (What is it?  The only
> explanation I've seen is at
>   http://abridgegame.org/darcs/manual/node8.html, 
> but I don't find it very helpful.)

See also http://www.darcs.net/DarcsWiki/PatchTheory
particularly http://www.darcs.net/DarcsWiki/WhyYouWantPatchTheory

P.S. I'm not a Darcs advocate.
-- 
Jakub Narebski
Warsaw, Poland

Re: Patch calculus

[Jakub Narebski]

J. Bruce Fields wrote:
 
> What are the benefits of patch calculus?  (What is it?  The only
> explanation I've seen is at
>   http://abridgegame.org/darcs/manual/node8.html,
> but I don't find it very helpful.)

See also http://www.darcs.net/DarcsWiki/PatchTheory
particularly http://www.darcs.net/DarcsWiki/WhyYouWantPatchTheory

and http://en.wikibooks.org/wiki/Understanding_darcs

-- 
Jakub Narebski
Warsaw, Poland

Re: Multi-headed branches (hydra? :)) for basic patch calculus

[Martin Langhoff]

On 4/2/06, Sam Vilain <sam@vilain.net> wrote:
> If the plumbing or a porcelain could be smart enough to automatically
> create hydra when patches are not dependent, then many of the benefits
> of patch calculus might come for free, without having to create these
> complicated sounding entities manually.

I'm not too excited about the benefits of patch calculus -- it seems
to break  many general usage scenarios(*) and I haven't seen many
examples of those benefits that aren't a bit contrived.

* - For instance: the common practice of having a patch series where
you create a new function and later add calls to it breaks quite
seriously under patch calculus.

Are there common usage scenarios where patch calculus helps more than
it hurts? Preferrably without involving manual recording of
dependencies or full language parsers that guess them.

cheers,


m

Re: Multi-headed branches (hydra? :)) for basic patch calculus

[Sam Vilain]

Martin Langhoff wrote:

>On 4/2/06, Sam Vilain <sam@vilain.net> wrote:
>  
>
>>If the plumbing or a porcelain could be smart enough to automatically
>>create hydra when patches are not dependent, then many of the benefits
>>of patch calculus might come for free, without having to create these
>>complicated sounding entities manually.
>>    
>>
>
>I'm not too excited about the benefits of patch calculus -- it seems
>to break  many general usage scenarios(*) and I haven't seen many
>examples of those benefits that aren't a bit contrived.
>
>* - For instance: the common practice of having a patch series where
>you create a new function and later add calls to it breaks quite
>seriously under patch calculus.
>  
>

Perhaps.  But forget the darcs implementation for a moment.

When you make a commit, you're labelling it with the previous dependent
commit for this commit to apply.

So, git-commit-hydra would do this calculation based on the files
changed.  git-commit would assume the prior commit.  You still have both
options available.

>Are there common usage scenarios where patch calculus helps more than
>it hurts? Preferrably without involving manual recording of
>dependencies or full language parsers that guess them.
>  
>

I am in the process of converting a live repository as if it had been
committed to in this manner.  I'll post results shortly.

Sam.