Patchwork [2,of,2] dagop: fix subsetparentswalker to set p1/p2 chains at merge revision

login
register
mail settings
Submitter Yuya Nishihara
Date March 29, 2020, 1:51 p.m.
Message ID <81235b66321d2e3b2ccf.1585489865@mimosa>
Download mbox | patch
Permalink /patch/45937/
State Accepted
Headers show

Comments

Yuya Nishihara - March 29, 2020, 1:51 p.m.
# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1585229477 -32400
#      Thu Mar 26 22:31:17 2020 +0900
# Node ID 81235b66321d2e3b2ccf7f591720b9ef21c9bc63
# Parent  d5aa217ada517aa9d141fbf869aeef8737531ac4
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.
Augie Fackler - April 1, 2020, 7:23 p.m.
queued, thanks

> On Mar 29, 2020, at 09:51, Yuya Nishihara <yuya@tcha.org> wrote:
> 
> # HG changeset patch
> # User Yuya Nishihara <yuya@tcha.org>
> # Date 1585229477 -32400
> #      Thu Mar 26 22:31:17 2020 +0900
> # Node ID 81235b66321d2e3b2ccf7f591720b9ef21c9bc63
> # Parent  d5aa217ada517aa9d141fbf869aeef8737531ac4
> 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.
> 
> diff --git a/mercurial/dagop.py b/mercurial/dagop.py
> --- a/mercurial/dagop.py
> +++ b/mercurial/dagop.py
> @@ -391,7 +391,9 @@ class subsetparentswalker(object):
>         #
>         # 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 @@ class subsetparentswalker(object):
>                         (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 @@ class subsetparentswalker(object):
>                         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 @@ class subsetparentswalker(object):
>             # 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 @@ class subsetparentswalker(object):
>                 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
> diff --git a/tests/test-template-graph.t b/tests/test-template-graph.t
> --- a/tests/test-template-graph.t
> +++ b/tests/test-template-graph.t
> @@ -63,6 +63,61 @@ Test graph-related template functions
> 
>   $ 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 @@ Invalid arguments:
>   [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 ..
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel

Patch

diff --git a/mercurial/dagop.py b/mercurial/dagop.py
--- a/mercurial/dagop.py
+++ b/mercurial/dagop.py
@@ -391,7 +391,9 @@  class subsetparentswalker(object):
         #
         # 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 @@  class subsetparentswalker(object):
                         (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 @@  class subsetparentswalker(object):
                         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 @@  class subsetparentswalker(object):
             # 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 @@  class subsetparentswalker(object):
                 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
diff --git a/tests/test-template-graph.t b/tests/test-template-graph.t
--- a/tests/test-template-graph.t
+++ b/tests/test-template-graph.t
@@ -63,6 +63,61 @@  Test graph-related template functions
 
   $ 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 @@  Invalid arguments:
   [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 ..