[PATCH 5 of 5 V2] revsets: add new topographical sort

Martijn Pieters mj at zopatista.com
Tue May 24 01:12:02 EDT 2016


# HG changeset patch
# User Martijn Pieters <mjpieters at fb.com>
# Date 1464066656 25200
#      Mon May 23 22:10:56 2016 -0700
# Node ID 179780aa5f762751ea2f9c4f052f8e390e227d40
# Parent  6530acadb949fd5006fd3ce763857d2014aa9743
revsets: add new topographical sort

Sort revisions in reverse revision order but grouped by topographical branches.
Visualised as a graph, instead of:

  o  4
  |
  | o  3
  | |
  | o  2
  | |
  o |  1
  |/
  o  0

revisions on a 'main' branch are emitted before 'side' branches:

  o  4
  |
  o  1
  |
  | o  3
  | |
  | o  2
  |/
  o  0

where what constitutes a 'main' branch is configurable, so the sort could also
result in:

  o  3
  |
  o  2
  |
  | o  4
  | |
  | o  1
  |/
  o  0

This sort was already available as an experimental option in the graphmod
module, from which it is now removed.

This sort is best used with hg log -G:

  $ hg log -G "sort(all(), topo)"

diff --git a/mercurial/cmdutil.py b/mercurial/cmdutil.py
--- a/mercurial/cmdutil.py
+++ b/mercurial/cmdutil.py
@@ -2147,7 +2147,7 @@
     if opts.get('rev'):
         # User-specified revs might be unsorted, but don't sort before
         # _makelogrevset because it might depend on the order of revs
-        if revs.sortorder != ('-rev',):
+        if revs.sortorder not in (('-rev',), ('topo',)):
             revs.sort(reverse=True)
     if expr:
         # Revset matchers often operate faster on revisions in changelog
diff --git a/mercurial/graphmod.py b/mercurial/graphmod.py
--- a/mercurial/graphmod.py
+++ b/mercurial/graphmod.py
@@ -52,16 +52,6 @@
 
     gpcache = {}
 
-    if repo.ui.configbool('experimental', 'graph-group-branches', False):
-        firstbranch = ()
-        firstbranchrevset = repo.ui.config(
-            'experimental', 'graph-group-branches.firstbranch', '')
-        if firstbranchrevset:
-            firstbranch = repo.revs(firstbranchrevset)
-        parentrevs = repo.changelog.parentrevs
-        revs = revset.groupbranchiter(revs, parentrevs, firstbranch)
-        revs = revset.baseset(revs)
-
     for rev in revs:
         ctx = repo[rev]
         # partition into parents in the rev set and missing parents, then
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -1834,7 +1834,7 @@
         return True
     return subset & s.filter(filter, condrepr='<roots>')
 
- at predicate('sort(set[, [-]key...])', safe=True)
+ at predicate('sort(set[, [-]key... [, ...]])', safe=True)
 def sort(repo, subset, x):
     """Sort set by keys. The default sort order is ascending, specify a key
     as ``-key`` to sort in descending order.
@@ -1846,8 +1846,14 @@
     - ``desc`` for the commit message (description),
     - ``user`` for user name (``author`` can be used as an alias),
     - ``date`` for the commit date
+    - ``topo`` for a reverse topographical sort
+
+    The ``topo`` sort order cannot be combined with other sort keys. This sort
+    takes one optional argument, ``topo.firstbranch``, which takes a revset tha
+    specifies what topographical branches to prioritize in the sort.
+
     """
-    args = getargsdict(x, 'sort', 'set keys')
+    args = getargsdict(x, 'sort', 'set keys topo.firstbranch')
     if 'set' not in args:
         # i18n: "sort" is a keyword
         raise error.ParseError(_('sort requires one or two arguments'))
@@ -1859,12 +1865,35 @@
     s = args['set']
     keys = keys.split()
     revs = getset(repo, subset, s)
+
+    if len(keys) > 1 and any(k.lstrip('-') == 'topo' for k in keys):
+            # i18n: "topo" is a keyword
+            raise error.ParseError(_(
+                'The topo sort order cannot be combined with other sort keys'))
+
+    firstbranch = ()
+    if 'topo.firstbranch' in args:
+        if any(k.lstrip('-') == 'topo' for k in keys):
+            firstbranch = getset(repo, subset, args['topo.firstbranch'])
+        else:
+            # i18n: "topo" and "topo.firstbranch" are keywords
+            raise error.ParseError(_(
+                'topo.firstbranch can only be used when using the topo sort '
+                'key'))
+
     if keys == ["rev"]:
         revs.sort()
         return revs
     elif keys == ["-rev"]:
         revs.sort(reverse=True)
         return revs
+    elif keys[0] in ("topo", "-topo"):
+        revs = baseset(_toposort(revs, repo.changelog.parentrevs, firstbranch),
+                       sortorder=('topo',))
+        if keys[0][0] == '-':
+            revs.reverse()
+        return revs
+
     # sort() is guaranteed to be stable
     ctxs = [repo[r] for r in revs]
     for k in reversed(keys):
@@ -1892,7 +1921,7 @@
             raise error.ParseError(_("unknown sort key %r") % k)
     return baseset([c.rev() for c in ctxs], sortorder=keys)
 
-def groupbranchiter(revs, parentsfunc, firstbranch=()):
+def _toposort(revs, parentsfunc, firstbranch=()):
     """Yield revisions from heads to roots one (topo) branch at a time.
 
     This function aims to be used by a graph generator that wishes to minimize
diff --git a/tests/test-glog-topological.t b/tests/test-glog-topological.t
--- a/tests/test-glog-topological.t
+++ b/tests/test-glog-topological.t
@@ -40,7 +40,7 @@
 
 (display all nodes)
 
-  $ hg --config experimental.graph-group-branches=1 log -G
+  $ hg log -G -r 'sort(all(), topo)'
   o  8
   |
   o  3
@@ -62,7 +62,7 @@
 
 (revset skipping nodes)
 
-  $ hg --config experimental.graph-group-branches=1 log -G --rev 'not (2+6)'
+  $ hg log -G --rev 'sort(not (2+6), topo)'
   o  8
   |
   o  3
@@ -80,7 +80,7 @@
 
 (begin) from the other branch
 
-  $ hg --config experimental.graph-group-branches=1 --config experimental.graph-group-branches.firstbranch=5 log -G
+  $ hg log -G -r 'sort(all(), topo, topo.firstbranch=5)'
   o  7
   |
   o  6
diff --git a/tests/test-revset.t b/tests/test-revset.t
--- a/tests/test-revset.t
+++ b/tests/test-revset.t
@@ -1100,6 +1100,67 @@
   0 b12  m111 u112 111 10800
   2 b111 m11  u12  111 3600
 
+ toposort prioritises graph branches
+
+  $ hg up 2
+  0 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  $ touch a
+  $ hg addremove
+  adding a
+  $ hg ci -m 't1' -u 'tu' -d '130 0'
+  created new head
+  $ echo 'a' >> a
+  $ hg ci -m 't2' -u 'tu' -d '130 0'
+  $ hg book book1
+  $ hg up 4
+  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  (leaving bookmark book1)
+  $ touch a
+  $ hg addremove
+  adding a
+  $ hg ci -m 't3' -u 'tu' -d '130 0'
+
+  $ hg log -r 'sort(all(), topo)'
+  7 b111 t3   tu   130 0
+  4 b111 m112 u111 110 14400
+  3 b112 m111 u11  120 0
+  6 b111 t2   tu   130 0
+  5 b111 t1   tu   130 0
+  2 b111 m11  u12  111 3600
+  1 b11  m12  u111 112 7200
+  0 b12  m111 u112 111 10800
+
+  $ hg log -r 'sort(all(), -topo)'
+  0 b12  m111 u112 111 10800
+  1 b11  m12  u111 112 7200
+  2 b111 m11  u12  111 3600
+  5 b111 t1   tu   130 0
+  6 b111 t2   tu   130 0
+  3 b112 m111 u11  120 0
+  4 b111 m112 u111 110 14400
+  7 b111 t3   tu   130 0
+
+  $ hg log -r 'sort(all(), topo, topo.firstbranch=book1)'
+  6 b111 t2   tu   130 0
+  5 b111 t1   tu   130 0
+  7 b111 t3   tu   130 0
+  4 b111 m112 u111 110 14400
+  3 b112 m111 u11  120 0
+  2 b111 m11  u12  111 3600
+  1 b11  m12  u111 112 7200
+  0 b12  m111 u112 111 10800
+
+topographical sorting can't be combined with other sort keys, and you can't
+use the topo.firstbranch option when topo sort is not active:
+
+  $ hg log -r 'sort(all(), "topo user")'
+  hg: parse error: The topo sort order cannot be combined with other sort keys
+  [255]
+
+  $ hg log -r 'sort(all(), user, topo.firstbranch=book1)'
+  hg: parse error: topo.firstbranch can only be used when using the topo sort key
+  [255]
+
 verify that revsets retain sort order keys
 
   $ cat <<EOF > $TESTTMP/echosortorder.py
@@ -1133,6 +1194,12 @@
   $ hg echosortorder 'reverse(sort(all(), "user -branch date rev"))'
   Sort order: ('-user', 'branch', '-date', '-rev')
 
+  $ hg echosortorder 'sort(all(), topo)'
+  Sort order: ('topo',)
+
+  $ hg echosortorder 'sort(all(), -topo)'
+  Sort order: ('-topo',)
+
   $ cd ..
   $ cd repo
 


More information about the Mercurial-devel mailing list