Skip to contentSkip to conversation

new stacked git feature

DISCUSSION Catalin Marinas 3 participants 8 messages Jun 15, 2016 1 message not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw

Hi Jason,

Quoted 4 lines · Jason Baron

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.

Quoted 11 lines · Catalin Marinas
Quoted 6 lines · Jason Baron

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.

Signature · 1 line
Catalin
#2 lore raw
Quoted 9 lines · Catalin Marinas

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.

Signature · 2 lines
Karl Hasselström, [email protected]
      www.treskal.com/kalle
#3 lore raw
Quoted 11 lines · Karl Hasselström
Quoted 9 lines · Catalin Marinas

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.

Quoted 6 lines

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.

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

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

Signature · 1 line
Catalin
#4 lore raw
Quoted 9 lines · Catalin Marinas
Quoted 3 lines · Karl Hasselström

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

Quoted 2 lines

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

Quoted 2 lines

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.

Quoted 6 lines
Quoted 2 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.

Quoted 11 lines
Quoted 10 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.

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

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

Signature · 2 lines
Karl Hasselström, [email protected]
      www.treskal.com/kalle
#5 lore raw
Quoted 9 lines · Karl Hasselström
Quoted 7 lines · Catalin Marinas
Quoted 3 lines · Karl Hasselström

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

Quoted 7 lines
Quoted 3 lines

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.

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

Quoted 3 lines

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

Quoted 10 lines
Quoted 6 lines
Quoted 2 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)?

Quoted 19 lines
Quoted 11 lines
Quoted 10 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.

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

Quoted 3 lines

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

Quoted 8 lines
Quoted 3 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.

Signature · 1 line
Catalin
#6 lore raw
Quoted 6 lines · Catalin Marinas
Quoted 4 lines · Karl Hasselström
Quoted 1 line · Catalin Marinas

On 13/02/2008, Karl Hasselström <[email protected]> wrote:

Quoted 7 lines
Quoted 2 lines

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.

Quoted 7 lines
Quoted 4 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.

Quoted 10 lines
Quoted 7 lines
Quoted 4 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.

Quoted 7 lines
Quoted 7 lines
Quoted 6 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).

Quoted 6 lines
Quoted 3 lines

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.

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

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

Signature · 2 lines
Karl Hasselström, [email protected]
      www.treskal.com/kalle
#7 lore raw
Quoted 11 lines · Karl Hasselström
Quoted 5 lines · Catalin Marinas

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.

Quoted 6 lines

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

Quoted 2 lines

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.

Signature · 1 line
Catalin
#8 lore raw
Quoted 4 lines · Catalin Marinas

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

Quoted 8 lines · Karl Hasselström
Quoted 3 lines

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.

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

Signature · 2 lines
Karl Hasselström, [email protected]
      www.treskal.com/kalle