Re: new stacked git feature

Re: new stacked git feature

[Catalin Marinas]

Hi Jason,

On Fri, 2008-01-11 at 14:49 -0500, Jason Baron wrote:
> I was just wondering if there was any progress on the feature, mentioned 
> below that we were discussing...I'd be more than happy to help explain
> it further or help out with it...maybe there a mailing i should be sending
> this to?

Sorry for the loooooong delay. I've been pretty busy and not able to do
much work on StGIT (though the other contributors did a lot of changes).
Now I'm trying to get up to speed with the latest StGIT structure :-).

I cc'ed the other StGIT people and the GIT mailing list.

Catalin Marinas wrote:
> Jason Baron wrote:
> > I also want to be able to go back to a git tag and reproduce a state of
> > the tree...i'm not sure i can do this with two git repositories...i almost
> > want an stgit mode where changes to the patches directory resulst in git
> > commits. IE if i refresh and patch or remove a patch i get a commit to the
> > patches directory. Maybe this can be a 'commit' mode or something that is
> > set when we do 'stgit init'? thoughts?
> 
> This could be made to work but I usually run refresh really often. Maybe
> the commits to the patches directory should have an additional log
> describing what it does (like the 'refresh --annotate').

The background of this discussion is to have two or more StGIT
repositories and keep them in sync. An idea is to share the exported
patches directory and automatically synchronise them between various
repositories (we already have a 'stg sync' command which I use for this
kind of things but it's not automated).

Yet another idea is to add some metadata to each commit log, something
like a unique id so that one can recreate the stack with only a GIT
revision id, without knowing the base.

-- 
Catalin

Re: new stacked git feature

[Karl Hasselström]

On 2008-02-12 16:42:46 +0000, Catalin Marinas wrote:

> The background of this discussion is to have two or more StGIT
> repositories and keep them in sync. An idea is to share the exported
> patches directory and automatically synchronise them between various
> repositories (we already have a 'stg sync' command which I use for
> this kind of things but it's not automated).
>
> Yet another idea is to add some metadata to each commit log,
> something like a unique id so that one can recreate the stack with
> only a GIT revision id, without knowing the base.

I've been trying to come up with a good way to represent undo
information, and my current plan is this:

  * Every time the patch stack is modified (that is, any time an StGit
    command modifies anything at all), a new commit is made to a log
    branch. Each StGit branch has one such log branch.

  * The tree of a log commit contains:

      - A "patches" subtree, with one subtree per patch, named after
        the patch.

          + Each patch tree contains an "a" and a "b" tree, and a blob
            with the commit details including the sha1 of the commit
            object we use to represent the patch.

      - "applied" and "unapplied" blobs.

      - A version stamp blob, to make it easier to extend the log
        format in the future if we ever need to.

  * The log commit has one or more parents: zero or more log commits,
    and the current branch head commit.

This has a couple of features:

  * The log contains all the information necessary for resetting back
    to any given prior state. We might lose the commit objects of
    unapplied patches since they aren't reachable from the branch
    head, but we can recreate equivalent commit objects.

      - This means that one could pull a log branch from another
        repository and continue working on it.

      - It also means that all the other StGit metadata becomes
        redundant.

  * The log is able to represent any state, even "broken" states. This
    means that it's possible to undo "stg repair".

  * The log can represent nonlinear history -- that is, forks and
    merges in the state of the patch stack -- but, like git, says
    nothing about how the result of a merge is to be computed.

I've started to build this, but haven't gotten very far yet.

I wasn't planning to try to build patch stack merging until later, but
here's how I imagine it would work:

  1. All patches are popped, and set to a special "conflicting" state
     with three or more "a" trees: a.ours, a.theirs, a.base0, a.base1,
     a.base2, .... Similarly for the "b" tree and the commit details.
     (Of course, trivial conflicts could be sorted out automatically
     at this point.)

  2. The merged stack base is created with a normal recursive merge.

  3. When a conflicting patch is pushed, we do the following:

       1. For each of .ours, .theirs, .base0, ..., create a new "b"
          tree just like we do when we normally push a patch. If there
          are conflicts, autoresolve them like merge-recursive does
          internally.

       2. Create the single new "b" tree by making a recursive merge
          of all these updated "b" trees. Represent any conflicts like
          we usually do when pushing patches.

I haven't even gotten far enough to test if this kind of merging gives
sane results, but I think it might.

Feedback welcome on all of this, obviously.

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

Re: new stacked git feature

[Catalin Marinas]

On 13/02/2008, Karl Hasselström <kha@treskal.com> wrote:
> On 2008-02-12 16:42:46 +0000, Catalin Marinas wrote:
> > The background of this discussion is to have two or more StGIT
> > repositories and keep them in sync. An idea is to share the exported
> > patches directory and automatically synchronise them between various
> > repositories (we already have a 'stg sync' command which I use for
> > this kind of things but it's not automated).
> >
> > Yet another idea is to add some metadata to each commit log,
> > something like a unique id so that one can recreate the stack with
> > only a GIT revision id, without knowing the base.
>
> I've been trying to come up with a good way to represent undo
> information, and my current plan is this:
>
>   * Every time the patch stack is modified (that is, any time an StGit
>     command modifies anything at all), a new commit is made to a log
>     branch. Each StGit branch has one such log branch.

We already have another commit for the patch history. If we add this,
we end up with 3 commit for each patch command. People already
complained that StGIT is slow, I wouldn't go this route. I even think
we should drop the patch history log and maybe use some git features
like reflog.

For undo, can we not keep the HEAD of the old stacks in a simple text
file? Or maybe use reflogs and only allow as many undos as information
available in reflog.

> I wasn't planning to try to build patch stack merging until later, but
> here's how I imagine it would work:
>
>   1. All patches are popped, and set to a special "conflicting" state
>      with three or more "a" trees: a.ours, a.theirs, a.base0, a.base1,
>      a.base2, .... Similarly for the "b" tree and the commit details.
>      (Of course, trivial conflicts could be sorted out automatically
>      at this point.)
>
>   2. The merged stack base is created with a normal recursive merge.

A recursive merge with the HEAD of another stack containing similar
patches? If yes, when pushing it is likely that the patches already in
the base will be emptied during a three-way merge.

>   3. When a conflicting patch is pushed, we do the following:
>
>        1. For each of .ours, .theirs, .base0, ..., create a new "b"
>           tree just like we do when we normally push a patch. If there
>           are conflicts, autoresolve them like merge-recursive does
>           internally.
>
>        2. Create the single new "b" tree by making a recursive merge
>           of all these updated "b" trees. Represent any conflicts like
>           we usually do when pushing patches.

My idea is to merge each patch with the corresponding commit in the
other branch and leave the base unchanged (like "stg sync"). The
difficulty is in identifying which commit from the other branch has to
be used. We could try guessing by the number of changes or just using
the subject line, assuming that it won't change (or an extra id field
in the commit text).

I find this workflow pretty difficult to implement since the StGIT
patches are pretty volatile. It might be better to use topic branches
instead.

-- 
Catalin

Re: new stacked git feature

[Karl Hasselström]

On 2008-02-13 22:29:34 +0000, Catalin Marinas wrote:

> On 13/02/2008, Karl Hasselström <kha@treskal.com> wrote:
>
> >   * Every time the patch stack is modified (that is, any time an
> >     StGit command modifies anything at all), a new commit is made
> >     to a log branch. Each StGit branch has one such log branch.
>
> We already have another commit for the patch history. If we add
> this, we end up with 3 commit for each patch command. People already
> complained that StGIT is slow, I wouldn't go this route.

I intend to get rid of the current per-patch log. It doesn't save
enough information to be useful anyway.

As for the speed: we'll have to write one blob and one tree per
modified patch, plus one top-level tree and a small constant number of
blobs. (Caveat: my current implementation is too stupid to realize
that not all patches were modified all the time.) These simple
create-an-object-from-data-on-stdin commands should be fast enough
that this won't be a problem (and if a dozen extra calls to git is too
expensive, we'll just have to build a git command that can take them
all in one go).

> For undo, can we not keep the HEAD of the old stacks in a simple
> text file?

We could. (We'd have to keep the sha1s of all the patches there,
though, and not just HEAD. And the applied/unapplied files.)

> Or maybe use reflogs and only allow as many undos as information
> available in reflog.

Yes, complemented by some extra files (see above). That's certainly a
reasonable choice.

I'd like to try my scheme out first, however. It's potentially more
powerful, since it can be pulled between repositories and maybe even
merged.

> >   2. The merged stack base is created with a normal recursive
> >      merge.
>
> A recursive merge with the HEAD of another stack containing similar
> patches? If yes, when pushing it is likely that the patches already
> in the base will be emptied during a three-way merge.

No, a merge of the stack _bases_, with all patches popped off. And
this would be a regular git merge, so no emptying of patches.

> >   3. When a conflicting patch is pushed, we do the following:
> >
> >        1. For each of .ours, .theirs, .base0, ..., create a new
> >           "b" tree just like we do when we normally push a patch.
> >           If there are conflicts, autoresolve them like
> >           merge-recursive does internally.
> >
> >        2. Create the single new "b" tree by making a recursive
> >           merge of all these updated "b" trees. Represent any
> >           conflicts like we usually do when pushing patches.
>
> My idea is to merge each patch with the corresponding commit in the
> other branch and leave the base unchanged (like "stg sync"). The
> difficulty is in identifying which commit from the other branch has
> to be used. We could try guessing by the number of changes or just
> using the subject line, assuming that it won't change (or an extra
> id field in the commit text).

I was thinking about the same thing: just match up the patches with
the same name. If the user has renamed a patch, she can coalesce the
two manually.

> I find this workflow pretty difficult to implement since the StGIT
> patches are pretty volatile. It might be better to use topic
> branches instead.

I agree that it's far from certain that this will be a very useful
workflow. But I'm willing to bet a couple of day's work that it is, so
I'll build a prototype and see.

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

Re: new stacked git feature

[Catalin Marinas]

On 13/02/2008, Karl Hasselström <kha@treskal.com> wrote:
> On 2008-02-13 22:29:34 +0000, Catalin Marinas wrote:
>
>  > On 13/02/2008, Karl Hasselström <kha@treskal.com> wrote:
>  >
>
> > >   * Every time the patch stack is modified (that is, any time an
>  > >     StGit command modifies anything at all), a new commit is made
>  > >     to a log branch. Each StGit branch has one such log branch.
>  >
>  > We already have another commit for the patch history. If we add
>  > this, we end up with 3 commit for each patch command. People already
>  > complained that StGIT is slow, I wouldn't go this route.
>
>
> I intend to get rid of the current per-patch log. It doesn't save
>  enough information to be useful anyway.

I use it from time to time. The commit message gives you the commit id
of the patch at that time and the commit diff gives you the changes
made by a refresh. It's mainly useful if you ran refresh and don't
remember what changes you've added.

>  As for the speed: we'll have to write one blob and one tree per
>  modified patch, plus one top-level tree and a small constant number of
>  blobs. (Caveat: my current implementation is too stupid to realize
>  that not all patches were modified all the time.) These simple
>  create-an-object-from-data-on-stdin commands should be fast enough
>  that this won't be a problem (and if a dozen extra calls to git is too
>  expensive, we'll just have to build a git command that can take them
>  all in one go).

As I said in the other e-mail, it needs a run through stg-prof to see
what the impact is with large number of patches.

>  I'd like to try my scheme out first, however. It's potentially more
>  powerful, since it can be pulled between repositories and maybe even
>  merged.

That's interesting indeed (though I don't fully understand all of this).

>  > >   2. The merged stack base is created with a normal recursive
>  > >      merge.
>  >
>  > A recursive merge with the HEAD of another stack containing similar
>  > patches? If yes, when pushing it is likely that the patches already
>  > in the base will be emptied during a three-way merge.
>
>
> No, a merge of the stack _bases_, with all patches popped off. And
>  this would be a regular git merge, so no emptying of patches.

OK, but we would need the StGIT information about stack bases to be
passed between repositories. And, after this merge, how do you merge
common patches (but maybe slightly modified)?

>  > >   3. When a conflicting patch is pushed, we do the following:
>  > >
>  > >        1. For each of .ours, .theirs, .base0, ..., create a new
>  > >           "b" tree just like we do when we normally push a patch.
>  > >           If there are conflicts, autoresolve them like
>  > >           merge-recursive does internally.
>  > >
>  > >        2. Create the single new "b" tree by making a recursive
>  > >           merge of all these updated "b" trees. Represent any
>  > >           conflicts like we usually do when pushing patches.
>  >
>  > My idea is to merge each patch with the corresponding commit in the
>  > other branch and leave the base unchanged (like "stg sync"). The
>  > difficulty is in identifying which commit from the other branch has
>  > to be used. We could try guessing by the number of changes or just
>  > using the subject line, assuming that it won't change (or an extra
>  > id field in the commit text).
>
>
> I was thinking about the same thing: just match up the patches with
>  the same name. If the user has renamed a patch, she can coalesce the
>  two manually.

Ah, OK. But how do we pass the patch name information? I think the
commit log wouldn't be enough as it can be easily modified. There is
also a situation when patches on the remote stack were reordered and
with some conflicts fixed. In this case, merging gets even more
complicated (I think darcs solves this by making all the patches
immutable but the base feature of StGIT is that patches are easily
modifiable).

>  > I find this workflow pretty difficult to implement since the StGIT
>  > patches are pretty volatile. It might be better to use topic
>  > branches instead.
>
>
> I agree that it's far from certain that this will be a very useful
>  workflow. But I'm willing to bet a couple of day's work that it is, so
>  I'll build a prototype and see.

It would be nice to allow an easy workflow for people trying to share
the same repository and benefit from StGIT. There was a recent thread
on the Linux kernel lists about a new branch, linux-next, which
included some discussions on GIT, patch management, rebasing etc. Some
people mentioned that they ended up using classic patch management
(quilt) and storing the patches in a repository which can be shared
between developers.

-- 
Catalin

Re: new stacked git feature

[Karl Hasselström]

On 2008-02-20 23:06:07 +0000, Catalin Marinas wrote:

> On 13/02/2008, Karl Hasselström <kha@treskal.com> wrote:
>
> > On 2008-02-13 22:29:34 +0000, Catalin Marinas wrote:
> >
> > > On 13/02/2008, Karl Hasselström <kha@treskal.com> wrote:
> >
> > I intend to get rid of the current per-patch log. It doesn't save
> > enough information to be useful anyway.
>
> I use it from time to time. The commit message gives you the commit
> id of the patch at that time and the commit diff gives you the
> changes made by a refresh. It's mainly useful if you ran refresh and
> don't remember what changes you've added.

Ah, OK. Well, the per-branch log will be able to give you all of that.

> > These simple create-an-object-from-data-on-stdin commands should
> > be fast enough that this won't be a problem (and if a dozen extra
> > calls to git is too expensive, we'll just have to build a git
> > command that can take them all in one go).
>
> As I said in the other e-mail, it needs a run through stg-prof to
> see what the impact is with large number of patches.

Agreed.

> > > A recursive merge with the HEAD of another stack containing
> > > similar patches? If yes, when pushing it is likely that the
> > > patches already in the base will be emptied during a three-way
> > > merge.
> >
> > No, a merge of the stack _bases_, with all patches popped off. And
> > this would be a regular git merge, so no emptying of patches.
>
> OK, but we would need the StGIT information about stack bases to be
> passed between repositories.

Yes.

> > > My idea is to merge each patch with the corresponding commit in
> > > the other branch and leave the base unchanged (like "stg sync").
> > > The difficulty is in identifying which commit from the other
> > > branch has to be used. We could try guessing by the number of
> > > changes or just using the subject line, assuming that it won't
> > > change (or an extra id field in the commit text).
> >
> > I was thinking about the same thing: just match up the patches
> > with the same name. If the user has renamed a patch, she can
> > coalesce the two manually.
>
> Ah, OK. But how do we pass the patch name information? I think the
> commit log wouldn't be enough as it can be easily modified.

The per-branch log will contain this information.

> There is also a situation when patches on the remote stack were
> reordered and with some conflicts fixed. In this case, merging gets
> even more complicated (I think darcs solves this by making all the
> patches immutable but the base feature of StGIT is that patches are
> easily modifiable).

The scheme I described should be able to handle this. When a patch is
pushed, its base is set, and we can just make a normal 3-way merge.

Consider a stack with two patches, a:A->B and b:B->C (A, B, and C are
commits). In one branch, this is modified to a:A->B1 and b:B1->C1; and
in the other, the patch order is changed so we get b:A->X and a:X->C.

When we merge these, the base is unchanged (so still A), and the patch
order is b, a (since it was changed in one branch but not the other).

  1. First we push b. The A->X variant applies trivially, but the
     B1->C1 variant needs the standard 3-way merge. The merge is
     force-resolved (that is, any conflicts are ignored, and just
     stored in the result tree); call the result Y. Then we make a
     3-way merge with C as ancestor and X and Y as ours and theirs;
     the result (possibly fixed up manually by the user) is stored as
     the new patch top -- call it Z. So now we have pushed b:A->Z.

  2. Then we push a. Both the A->B1 and the X->C variants need 3-way
     merging, since we apply the patch on top of Z; call the resulting
     (possibly force-resolved) trees P and Q. Then we make a 3-way
     merge with B as ancestor and P and Q as ours and theirs; the
     result (possibly fixed up manually by the user) is stored as the
     new patch top -- call it R. So now we have pushed a:Z->R.

> It would be nice to allow an easy workflow for people trying to
> share the same repository and benefit from StGIT. There was a recent
> thread on the Linux kernel lists about a new branch, linux-next,
> which included some discussions on GIT, patch management, rebasing
> etc. Some people mentioned that they ended up using classic patch
> management (quilt) and storing the patches in a repository which can
> be shared between developers.

Yes, absolutely. And this is precisely what we'll get out of this if
it pans out. But if it doesn't, the _same_ per-branch log format can
be used with a different conflict resolution scheme -- for example, we
could compute the diff text for each of the patches and just merge
those, which gives the same result as if the user had stored patches
in the repository.

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

Re: new stacked git feature

[Catalin Marinas]

On 21/02/2008, Karl Hasselström <kha@treskal.com> wrote:
> On 2008-02-20 23:06:07 +0000, Catalin Marinas wrote:
>  > There is also a situation when patches on the remote stack were
>  > reordered and with some conflicts fixed. In this case, merging gets
>  > even more complicated (I think darcs solves this by making all the
>  > patches immutable but the base feature of StGIT is that patches are
>  > easily modifiable).
>
>
> The scheme I described should be able to handle this. When a patch is
>  pushed, its base is set, and we can just make a normal 3-way merge.
>
>  Consider a stack with two patches, a:A->B and b:B->C (A, B, and C are
>  commits). In one branch, this is modified to a:A->B1 and b:B1->C1; and
>  in the other, the patch order is changed so we get b:A->X and a:X->C.
>
>  When we merge these, the base is unchanged (so still A), and the patch
>  order is b, a (since it was changed in one branch but not the other).

"stg sync" does pretty much the same now but in a more manual way. I
don't really like the way the conflicts are presented - i.e. you don't
know which patch was modified afterwards because the patches lose this
information (they are not topic branches).

>   1. First we push b. The A->X variant applies trivially, but the
>      B1->C1 variant needs the standard 3-way merge.

3-way merge with X and B1 as base? This leads to the current "sync"
issue, you can't tell which patch was original and which was modified.

Just a thought (not that I'd like this feature in StGIT). Someone
tried a project some time ago, similar to StGIT, but using topic
branches rather than individual commits per patch. The GIT history
looked very ugly, especially after re-ordering, but the advantage was
that you can avoid rebasing patches and simply merging changes from
bottom patches into top ones. This would make synchronisation of
patches between branches much easier.

-- 
Catalin

Re: new stacked git feature

[Karl Hasselström]

On 2008-02-22 13:54:12 +0000, Catalin Marinas wrote:

> "stg sync" does pretty much the same now but in a more manual way. I
> don't really like the way the conflicts are presented - i.e. you
> don't know which patch was modified afterwards because the patches
> lose this information (they are not topic branches).

This shouldn't be a problem with a per-branch log -- it would have the
state of both ancestors before the merge, and the merged state
afterwards, so nothing should be lost.

> On 21/02/2008, Karl Hasselström <kha@treskal.com> wrote:
>
> >   1. First we push b. The A->X variant applies trivially, but the
> >      B1->C1 variant needs the standard 3-way merge.
>
> 3-way merge with X and B1 as base? This leads to the current "sync"
> issue, you can't tell which patch was original and which was
> modified.

No. First a 3-way merge (A (base), A, X) with result X, and then a
3-way merge (A (base), B1, C1) with a result that has to be computed
by the merge algorithm. Just as if you were pushing both versions of
the patch separately.

The basic algorithm is:

  1. You want to merge patches A->B and C->D. Their closest common
     ancestors are X0->Y0, X1->Y1, ...

  2. Select the base tree K you want to push the patch on. This is
     either another patch, or the bottom of the stack.

  3. For each of A->B, C->D, X0->Y0, X1->Y1, ..., push them separately
     onto K (in parallel, not on top of each other). If there are
     conflicts, just commit the conflict markers. The patches are now
     K->B', K->D', K->Y0', K->Y1', ...

  4. Merge B' and D' with Y0', Y1', ... as bases. In case of
     conflicts, ask the user to resolve them.

Obviously, K may be the same as one or more of A, C, X0, X1, ..., so
that some or all of the pushes are trivial.

> Just a thought (not that I'd like this feature in StGIT). Someone
> tried a project some time ago, similar to StGIT, but using topic
> branches rather than individual commits per patch. The GIT history
> looked very ugly, especially after re-ordering, but the advantage
> was that you can avoid rebasing patches and simply merging changes
> from bottom patches into top ones. This would make synchronisation
> of patches between branches much easier.

I never really liked that approach; it kind of treats patches as
trees, when they are in fact the diff between two trees. It only works
because the boundary between two applied patches is a tree. But the
user thinks she's manipulating patches and not patch boundaries, which
is why the history looks strange.

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle