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

From: Jakub Narebski <[email-masked]>
Date: Mon, 03 Apr 2006 06:10:33 +0200

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