dagop: fix subsetparentswalker to set p1/p2 chains at merge revision

dagop: fix subsetparentswalker to set p1/p2 chains at merge revision

The previous implementation was wrong because the '1'/'2' key would be
appended at a fork revision. Since we traverse the graph from heads, a merge
revision is actually a branching point, where the sort key must be generated.

--- a/mercurial/dagop.py	Thu Mar 26 22:23:30 2020 +0900
+++ b/mercurial/dagop.py	Thu Mar 26 22:31:17 2020 +0900
@@ -391,7 +391,9 @@
         #
         # Once all pending paths have been resolved, 'pendingcnt[rev]' becomes
         # 0 and 'parents[rev]' contains the unsorted list of parent revisions
-        # and p1/p2 chains (excluding linear paths.)
+        # and p1/p2 chains (excluding linear paths.) The p1/p2 chains will be
+        # used as a sort key preferring p1. 'len(chain)' should be the number
+        # of merges between two revisions.
 
         subset = self._subset
         tovisit = self._tovisit  # heap queue of [-rev]
@@ -458,9 +460,12 @@
                         (unresolved.copy(), resolved.copy()),
                     ]
                     # 'rev' is a merge revision. increment the pending count
-                    # as the 'unresolved' dict will be duplicated.
+                    # as the 'unresolved' dict will be duplicated, and append
+                    # p1/p2 code to the existing chains.
                     for r in unresolved:
                         pendingcnt[r] += 1
+                        parentpointers[0][0][r] += b'1'
+                        parentpointers[1][0][r] += b'2'
                 for i, p in enumerate(parentrevs):
                     assert p < rev
                     heapq.heappush(tovisit, -p)
@@ -470,7 +475,6 @@
                         knownunresolved, knownresolved = pointers[p]
                         unresolved, resolved = parentpointers[i]
                         for r, c in unresolved.items():
-                            c += [b'1', b'2'][i]
                             if r in knownunresolved:
                                 # unresolved at both paths
                                 pendingcnt[r] -= 1
@@ -488,9 +492,10 @@
             # then, populate the active parents directly and add the current
             # 'rev' to the tracking pointers of the inactive parents.
             # 'pointers[p]' may be optimized out if both parents are active.
+            chaincodes = [b''] if len(parentrevs) <= 1 else [b'1', b'2']
             if curactive and bothparentsactive:
                 for i, p in enumerate(parentrevs):
-                    c = [b'1', b'2'][i]
+                    c = chaincodes[i]
                     parents[rev].append((c, p))
                     # no need to mark 'rev' as resolved since the 'rev' should
                     # be fully resolved (i.e. pendingcnt[rev] == 0)
@@ -499,7 +504,7 @@
                 for i, p in enumerate(parentrevs):
                     unresolved, resolved = pointers[p]
                     assert rev not in unresolved
-                    c = [b'1', b'2'][i]
+                    c = chaincodes[i]
                     if p in subset:
                         parents[rev].append((c, p))
                         # mark 'rev' as resolved through this path

--- a/tests/test-template-graph.t	Thu Mar 26 22:23:30 2020 +0900
+++ b/tests/test-template-graph.t	Thu Mar 26 22:31:17 2020 +0900
@@ -63,6 +63,61 @@
 
   $ cd ..
 
+Create repository containing merges of p1 > p2:
+
+  $ hg init named-branch-order
+  $ cd named-branch-order
+
+  $ hg branch -q b0
+  $ hg ci -m 0
+  $ hg up -q null
+  $ hg branch -q b1
+  $ hg ci -m 1
+  $ hg up -q null
+  $ hg branch -q b2
+  $ hg ci -m 2
+  $ hg merge -q 1
+  $ hg ci -m 3
+  $ hg ci -m 4 --config ui.allowemptycommit=true
+  $ hg merge -q 0
+  $ hg ci -m 5
+  $ hg ci -m 6 --config ui.allowemptycommit=true
+  $ hg up -q 1
+  $ hg branch -q b7
+  $ hg ci -m 7
+  $ hg ci -m 8 --config ui.allowemptycommit=true
+  $ hg up -q 6
+  $ hg ci -m 9 --config ui.allowemptycommit=true
+  $ hg up -q 8
+  $ hg merge -q 9
+  $ hg ci -m 10
+
+  $ hg log -Gq -T'{rev} {branch} -> {p1.rev} {p2.rev}\n'
+  @    10 b7 -> 8 9
+  |\
+  | o  9 b2 -> 6 -1
+  | |
+  o |  8 b7 -> 7 -1
+  | |
+  o |  7 b7 -> 1 -1
+  | |
+  | o  6 b2 -> 5 -1
+  | |
+  | o    5 b2 -> 4 0
+  | |\
+  | | o  4 b2 -> 3 -1
+  | | |
+  +---o  3 b2 -> 2 1
+  | | |
+  | | o  2 b2 -> -1 -1
+  | |
+  o |  1 b1 -> -1 -1
+   /
+  o  0 b0 -> -1 -1
+  
+
+  $ cd ..
+
 subsetparents
 -------------
 
@@ -335,3 +390,51 @@
   [255]
 
   $ cd ..
+
+subsetparents: p1/p2 order
+-------------------------
+
+  $ cd named-branch-order
+
+Parents should be sorted in p1/p2 order since p1 is likely to belong to
+the same named branch:
+
+  $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("0+1+2+6"))}\n' -r '0+1+2+6'
+  o    6 : 2 1 0
+  :\
+  : \
+  : :\
+  : : o  2 :
+  : :
+  : o  1 :
+  :
+  o  0 :
+  
+
+  $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("0+1+2+6+10"))}\n' -r '0+1+2+6+10'
+  @    10 tip: 6
+  :\
+  : o    6 : 2 1 0
+  :/:\
+  : : o  2 :
+  : :
+  o :  1 :
+   /
+  o  0 :
+  
+
+And p1 path should be selected if both p1/p2 paths exist:
+
+  $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("0+1+2+10"))}\n' -r '0+1+2+10'
+  @    10 tip: 1 2 0
+  :\
+  : \
+  : :\
+  : : o  2 :
+  : :
+  o :  1 :
+   /
+  o  0 :
+  
+
+  $ cd ..