Deferring Conflict Resolution To Later Parents In Octopus Merges

pbranch supports conceptual octopus merges (merges with more than two parents) at the branch level. This gives rise to novel situations for Mercurial, which we look at here.

Problem And Solution

In a patch graph like (where A = default):

A -> (B, C -> D, E) -> .O -> O

we have an octopus merge branch .O with parents B, D, and E. Assume this is fully pmerged. Now we pull a change A1 in A that conflicts with files b in B, c in C, and e in E. Let’s say in change A0 in A we had files bA0, cA0, eA0 in A0 before the pull. These were changed to bB0, cC0 → cD0, eE0 in their respective branches. This is also how they ended up in .O via pmerge.

The pull of cset A1 introduces bA1, cA1, dA1, which all conflict with their current versions in A, B, C. When we first pmerge into B, C → D, E, we need to resolve these conflicts by hand (denoted by ->!):

(bB0, bA1) ->! bB1
(cC0, cA1) ->! cC1; (cD0, cC1) -> cD1
(eE0, eA1) ->! eE1

Now we want to do the octopus merge. So we attempt to merge B into .O, meaning change B1 and .O0E, where the latter denotes the final merge of E into .O from our initial pmerge. Since B1 already contains A1, this merge will fail with conflicts (denoted by -!):

(bB0, bB1) -> bB1
(cD0, cA1) -!
(eE0, eA1) -!

So pmerge goes looking in the other octopus merge candidates D, E for whether these branches already contain resolutions of the conflicting pairs. (Note that we look for corresponding pairs via changeset nodes, not file nodes, to avoid the problem that http://mercurial.selenic.com/bts/issue1327 addresses). To handle cases as in C → D, we scan ancestors too.

If we find an existing resolution, we drop the file from the merge (by reverting it to the first merge parent’s version and flagging it as clean). Thus the later merge of the branch containing the existing resolution will apply it to .O. So for the merge of B we get:

(bB0, bB1) -> bB1
(cD0, cA1) -? cD0
(eE0, eA1) -? eE0

For the subsequent merge of D we get:

(bB1, bA1) -> bB1
(cD0, cD1) -> cD1
(eE0, eA1) -? eE0

And finally for E we get:

(bB1, bA1) -> bB1
(cD1, cA1) -> cD1
(eE0, eE1) -> eE1

This is acceptable because we are not interested in the semantic validity of the interim merges within the hidden branch .O. Only its final state that is then merged forward into O is of interest.

Currently, pbranch can only handle this at the file level, not the hunk level.

Test Case With File-Level Resolution

Base Branch Graph

We build the initial branch-join graph A → (B, C → D, E) → .O → O:

$ hg init octopus-file
$ cd octopus-file

Base branch A:

$ hg branch A
marked working directory as branch A
(branches are permanent and global, did you want a bookmark?)
$ echo a >a
$ echo b >b
$ echo c >c
$ echo d >d
$ echo e >e
$ hg ci -qAm base

Fork A → B:

$ echo B >b
$ hg pnew B
marked working directory as branch B
(branches are permanent and global, did you want a bookmark?)

Fork A → C → D:

$ hg up A
1 files updated, 0 files merged, 1 files removed, 0 files unresolved

$ echo C >c
$ hg pnew C
marked working directory as branch C
(branches are permanent and global, did you want a bookmark?)
created new head

$ echo D >d
$ hg pnew D
marked working directory as branch D
(branches are permanent and global, did you want a bookmark?)

Fork A → E:

$ hg up A
2 files updated, 0 files merged, 2 files removed, 0 files unresolved

$ echo E >e
$ hg pnew E
marked working directory as branch E
(branches are permanent and global, did you want a bookmark?)
created new head

Join (B, D, E) → O:

$ hg pnew O
marked working directory as branch O
(branches are permanent and global, did you want a bookmark?)
$ sed -i .hg/pgraph -e 's/O: E/O: B, D, E/'
$ hg pmerge
updating to B
3 files updated, 0 files merged, 2 files removed, 0 files unresolved
marked working directory as branch .O
(branches are permanent and global, did you want a bookmark?)
updating to D
5 files updated, 0 files merged, 2 files removed, 0 files unresolved
.O: merging from D
marked working directory as branch .O
(branches are permanent and global, did you want a bookmark?)
3 files updated, 0 files merged, 0 files removed, 0 files unresolved
updating to E
5 files updated, 0 files merged, 4 files removed, 0 files unresolved
.O: merging from E
marked working directory as branch .O
(branches are permanent and global, did you want a bookmark?)
7 files updated, 0 files merged, 0 files removed, 0 files unresolved
O: merging from .O
marked working directory as branch O
(branches are permanent and global, did you want a bookmark?)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved

Result:

$ hg pgraph -s
@    O
|\
| \
| |\
o | |  B
| | |
| o |  D
| | |
+---o  E
| |
| o  C
|/
o  A

Conflicting Change

Now we introduce the change that conflicts with all three forks:

$ hg up A
4 files updated, 0 files merged, 6 files removed, 0 files unresolved
$ echo b1 >b
$ echo c1 >c
$ echo e1 >e
$ hg ci -m A1

and merge it into the three forks, resolving conflicts. First A → B:

$ hg up B
4 files updated, 0 files merged, 0 files removed, 0 files unresolved
needs merge with A
needs update of diff base to tip of A
use 'hg pmerge'
$ hg pmerge
updating to A
3 files updated, 0 files merged, 1 files removed, 0 files unresolved
B: merging from A
marked working directory as branch B
(branches are permanent and global, did you want a bookmark?)
merging b
warning: conflicts during merge.
merging b incomplete! (edit conflicts, then use 'hg resolve --mark')
1 files updated, 0 files merged, 0 files removed, 1 files unresolved
abort: use 'hg resolve' to handle unresolved file merges, then do 'hg pmerge' again
$ echo B1 >b
$ hg resolve -m b
$ hg ci -m B1
$ hg pmerge
B: updating dependencies

Then A → C → D:

$ hg up D
6 files updated, 0 files merged, 1 files removed, 0 files unresolved
needs merge with A (through C)
use 'hg pmerge'
$ hg pmerge
updating to A
4 files updated, 0 files merged, 2 files removed, 0 files unresolved
C: merging from A
marked working directory as branch C
(branches are permanent and global, did you want a bookmark?)
merging c
warning: conflicts during merge.
merging c incomplete! (edit conflicts, then use 'hg resolve --mark')
1 files updated, 0 files merged, 0 files removed, 1 files unresolved
abort: use 'hg resolve' to handle unresolved file merges, then do 'hg pmerge' again
$ echo C1 >c
$ hg resolve -m c
$ hg ci -m C1
$ hg pmerge D
C: updating dependencies
D: merging from C
marked working directory as branch D
(branches are permanent and global, did you want a bookmark?)
2 files updated, 0 files merged, 0 files removed, 0 files unresolved

And A → E:

$ hg up E
5 files updated, 0 files merged, 2 files removed, 0 files unresolved
needs merge with A
needs update of diff base to tip of A
use 'hg pmerge'
$ hg pmerge
updating to A
3 files updated, 0 files merged, 1 files removed, 0 files unresolved
E: merging from A
marked working directory as branch E
(branches are permanent and global, did you want a bookmark?)
merging e
warning: conflicts during merge.
merging e incomplete! (edit conflicts, then use 'hg resolve --mark')
1 files updated, 0 files merged, 0 files removed, 1 files unresolved
abort: use 'hg resolve' to handle unresolved file merges, then do 'hg pmerge' again
$ echo E1 >e
$ hg resolve -m e
$ hg ci -m E1
$ hg pmerge
E: updating dependencies

Clean up .orig files:

$ find . -name '*.orig' | xargs rm

Here’s the current situation:

$ hg pgraph -s
o    O
|\    * needs merge with B (through .O)
| |   * needs merge with D (through .O)
| |   * needs merge with E (through .O)
| \
| |\
o | |  B
| | |
| o |  D
| | |
+---@  E
| |
| o  C
|/
o  A

$ hg glog
@  17    E: update patch dependencies - john
|
o    16    E: E1 - john
|\
| | o    15    D: merge of C - john
| | |\
| | | o  14    C: update patch dependencies - john
| | | |
| +---o  13    C: C1 - john
| | | |
| | | | o  12    B: update patch dependencies - john
| | | | |
| +-----o  11    B: B1 - john
| | | | |
| o | | |  10    A: A1 - john
| | | | |
| | | | | o    9    O: merge of .O - john
| | | | | |\
+-----------o  8    .O: merge of E - john
| | | | | | |
| | +-------o  7    .O: merge of D - john
| | | | | | |
| | | | +---o  6    .O: update patch dependencies - john
| | | | | |
+---------o  5    O: start new patch on E - john
| | | | |
o | | | |  4    E: start new patch on A - john
|/ / / /
| o / /  3    D: start new patch on C - john
| |/ /
| o /  2    C: start new patch on A - john
|/ /
| o  1    B: start new patch on A - john
|/
o  0    A: base - john

Octopus Merge With Successful Resolution

And now we pmerge:

$ hg pmerge O
updating to B
3 files updated, 0 files merged, 1 files removed, 0 files unresolved
.O: merging from B
marked working directory as branch .O
(branches are permanent and global, did you want a bookmark?)
merging c
warning: conflicts during merge.
merging c incomplete! (edit conflicts, then use 'hg resolve --mark')
merging e
warning: conflicts during merge.
merging e incomplete! (edit conflicts, then use 'hg resolve --mark')
5 files updated, 0 files merged, 0 files removed, 2 files unresolved
deferring c; pending resolution in rev 13
deferring e; pending resolution in rev 16
updating to D
4 files updated, 0 files merged, 3 files removed, 0 files unresolved
.O: merging from D
marked working directory as branch .O
(branches are permanent and global, did you want a bookmark?)
merging b
warning: conflicts during merge.
merging b incomplete! (edit conflicts, then use 'hg resolve --mark')
merging c
warning: conflicts during merge.
merging c incomplete! (edit conflicts, then use 'hg resolve --mark')
3 files updated, 0 files merged, 0 files removed, 2 files unresolved
resolving b; already merged in rev 18
resolving c; already merged in rev 15
updating to E
5 files updated, 0 files merged, 4 files removed, 0 files unresolved
.O: merging from E
marked working directory as branch .O
(branches are permanent and global, did you want a bookmark?)
merging .hgpatchinfo/E.dep
7 files updated, 1 files merged, 0 files removed, 0 files unresolved
O: merging from .O
marked working directory as branch O
(branches are permanent and global, did you want a bookmark?)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved

and review:

$ hg cat a b c d e
a
B1
C1
D
E1

$ cd ..

Test Case With Hunk-Level Resolution

Base Branch Graph

We again build the initial branch-join graph A → (B, C → D, E) → .O → O:

$ hg init octopus-hunk
$ cd octopus-hunk

Base branch A, this time with multiple lines in file a:

$ hg branch A
marked working directory as branch A
(branches are permanent and global, did you want a bookmark?)
$ echo a >a
$ for i in 1 2 3 4 5 6 7 8 9; do echo $i >>a; done
$ echo b >b
$ echo c >c
$ echo d >d
$ echo e >e
$ hg ci -qAm base

Fork A → B, changes file a:

$ sed -i a -e s/2/B/
$ echo B >b
$ hg pnew B
marked working directory as branch B
(branches are permanent and global, did you want a bookmark?)

Fork A → C → D, changes file a in D in a different hunk:

$ hg up A
2 files updated, 0 files merged, 1 files removed, 0 files unresolved

$ echo C >c
$ hg pnew C
marked working directory as branch C
(branches are permanent and global, did you want a bookmark?)
created new head

$ sed -i a -e s/8/D/
$ echo D >d
$ hg pnew D
marked working directory as branch D
(branches are permanent and global, did you want a bookmark?)

Fork A → E:

$ hg up A
3 files updated, 0 files merged, 2 files removed, 0 files unresolved

$ echo E >e
$ hg pnew E
marked working directory as branch E
(branches are permanent and global, did you want a bookmark?)
created new head

Join (B, D, E) → O:

$ hg pnew O
marked working directory as branch O
(branches are permanent and global, did you want a bookmark?)
$ sed -i .hg/pgraph -e 's/O: E/O: B, D, E/'
$ hg pmerge
updating to B
4 files updated, 0 files merged, 2 files removed, 0 files unresolved
marked working directory as branch .O
(branches are permanent and global, did you want a bookmark?)
updating to D
6 files updated, 0 files merged, 2 files removed, 0 files unresolved
.O: merging from D
marked working directory as branch .O
(branches are permanent and global, did you want a bookmark?)
merging a
3 files updated, 1 files merged, 0 files removed, 0 files unresolved
updating to E
6 files updated, 0 files merged, 4 files removed, 0 files unresolved
.O: merging from E
marked working directory as branch .O
(branches are permanent and global, did you want a bookmark?)
8 files updated, 0 files merged, 0 files removed, 0 files unresolved
O: merging from .O
marked working directory as branch O
(branches are permanent and global, did you want a bookmark?)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved

Result:

$ hg pgraph -s
@    O
|\
| \
| |\
o | |  B
| | |
| o |  D
| | |
+---o  E
| |
| o  C
|/
o  A

Conflicting Change

Now we introduce the change that conflicts with all three forks. In particular, it conflicts within file a for B and D, but in different hunks:

$ hg up A
5 files updated, 0 files merged, 6 files removed, 0 files unresolved
$ echo b1 >b
$ echo c1 >c
$ echo e1 >e
$ sed -i a -e s/2/22/ -e s/8/88/
$ hg ci -m A1

and merge it into the three forks, resolving conflicts. First A → B:

$ hg up B
5 files updated, 0 files merged, 0 files removed, 0 files unresolved
needs merge with A
needs update of diff base to tip of A
use 'hg pmerge'
$ hg pmerge
updating to A
4 files updated, 0 files merged, 1 files removed, 0 files unresolved
B: merging from A
marked working directory as branch B
(branches are permanent and global, did you want a bookmark?)
merging a
warning: conflicts during merge.
merging a incomplete! (edit conflicts, then use 'hg resolve --mark')
merging b
warning: conflicts during merge.
merging b incomplete! (edit conflicts, then use 'hg resolve --mark')
1 files updated, 0 files merged, 0 files removed, 2 files unresolved
abort: use 'hg resolve' to handle unresolved file merges, then do 'hg pmerge' again
$ cp a.orig a
$ sed -i a -e s/B/BB/
$ hg resolve -m a
$ echo B1 >b
$ hg resolve -m b
$ hg ci -m B1
$ hg pmerge
B: updating dependencies

Then A → C → D:

$ hg up D
7 files updated, 0 files merged, 1 files removed, 0 files unresolved
needs merge with A (through C)
use 'hg pmerge'
$ hg pmerge
updating to A
5 files updated, 0 files merged, 2 files removed, 0 files unresolved
C: merging from A
marked working directory as branch C
(branches are permanent and global, did you want a bookmark?)
merging c
warning: conflicts during merge.
merging c incomplete! (edit conflicts, then use 'hg resolve --mark')
1 files updated, 0 files merged, 0 files removed, 1 files unresolved
abort: use 'hg resolve' to handle unresolved file merges, then do 'hg pmerge' again
$ echo C1 >c
$ hg resolve -m c
$ hg ci -m C1
$ hg pmerge D
C: updating dependencies
D: merging from C
marked working directory as branch D
(branches are permanent and global, did you want a bookmark?)
merging a
warning: conflicts during merge.
merging a incomplete! (edit conflicts, then use 'hg resolve --mark')
2 files updated, 0 files merged, 0 files removed, 1 files unresolved
abort: use 'hg resolve' to handle unresolved file merges, then do 'hg pmerge' again
$ cp a.orig a
$ sed -i a -e s/D/DD/
$ hg resolve -m a
$ hg pmerge D
D: committing current merge from C

And A → E:

$ hg up E
6 files updated, 0 files merged, 2 files removed, 0 files unresolved
needs merge with A
needs update of diff base to tip of A
use 'hg pmerge'
$ hg pmerge
updating to A
4 files updated, 0 files merged, 1 files removed, 0 files unresolved
E: merging from A
marked working directory as branch E
(branches are permanent and global, did you want a bookmark?)
merging e
warning: conflicts during merge.
merging e incomplete! (edit conflicts, then use 'hg resolve --mark')
1 files updated, 0 files merged, 0 files removed, 1 files unresolved
abort: use 'hg resolve' to handle unresolved file merges, then do 'hg pmerge' again
$ echo E1 >e
$ hg resolve -m e
$ hg ci -m E1
$ hg pmerge
E: updating dependencies

Clean up .orig files:

$ find . -name '*.orig' | xargs rm

Octopus Merge With Unresolved Conflicts

Again, we pmerge:

$ hg up .O
10 files updated, 0 files merged, 0 files removed, 0 files unresolved
needs merge with B
needs merge with D
needs merge with E
needs update of diff base to tip of B
needs update of diff base to tip of D
needs update of diff base to tip of E
use 'hg pmerge'
$ hg merge B
merging a
warning: conflicts during merge.
merging a incomplete! (edit conflicts, then use 'hg resolve --mark')
merging c
warning: conflicts during merge.
merging c incomplete! (edit conflicts, then use 'hg resolve --mark')
merging e
warning: conflicts during merge.
merging e incomplete! (edit conflicts, then use 'hg resolve --mark')
2 files updated, 0 files merged, 0 files removed, 3 files unresolved
use 'hg resolve' to retry unresolved file merges or 'hg update -C .' to abandon
$ hg debugoctopusresolve D E
deferring c; pending resolution in rev 13
deferring e; pending resolution in rev 16
$ hg stat
M .hgpatchinfo/B.dep
M a
M b
? a.orig
$ hg ci -m M1
abort: unresolved merge conflicts (see hg help resolve)

Current pbranch fails to detect octopus resolutions at the hunk level.

$ cd ..