threads / discuss / 12059

Re: new stacked git feature

Subject: Re: new stacked git feature

## tl;dr

8 messages between Feb 12, 2008 and Feb 22, 2008.

replies: 7people: 3as markdown or json

Catalin Marinas· Feb 12, 2008, 16:42 UTC · lore

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:

Show 11 quoted lines

> 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

Karl Hasselström· Feb 13, 2008, 00:08 UTC · re: Catalin Marinas · lore

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

Show 9 quoted lines

> 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

Catalin Marinas· Feb 13, 2008, 22:29 UTC · re: Karl Hasselström · lore

On 13/02/2008, Karl Hasselström <kha@treskal.com> wrote:

Show 17 quoted lines

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

Show 10 quoted lines

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

Show 10 quoted lines

>   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

Karl Hasselström· Feb 13, 2008, 23:52 UTC · re: Catalin Marinas · lore

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

Show 9 quoted lines

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

Show 6 quoted lines

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

Show 17 quoted lines

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

Catalin Marinas· Feb 20, 2008, 23:06 UTC · re: Karl Hasselström · lore

On 13/02/2008, Karl Hasselström <kha@treskal.com> wrote:

Show 16 quoted lines

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

Show 8 quoted lines

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

Show 10 quoted lines

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

Show 22 quoted lines

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

Show 8 quoted lines

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

Karl Hasselström· Feb 21, 2008, 07:45 UTC · re: Catalin Marinas · lore

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

Show 13 quoted lines

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

Show 7 quoted lines

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

Show 10 quoted lines

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

Show 13 quoted lines

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

Show 5 quoted lines

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

Show 7 quoted lines

> 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

Catalin Marinas· Feb 22, 2008, 13:54 UTC · re: Karl Hasselström · lore

On 21/02/2008, Karl Hasselström <kha@treskal.com> wrote:

Show 17 quoted lines

> 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

Karl Hasselström· Feb 22, 2008, 15:19 UTC · re: Catalin Marinas · lore

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.

Show 8 quoted lines

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

Show 7 quoted lines

> 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