changeset 29348:2188f170f5b6

revset: 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)"

--- a/mercurial/graphmod.py	Mon Jun 13 18:20:00 2016 +0100
+++ b/mercurial/graphmod.py	Mon Jun 13 18:20:00 2016 +0100
@@ -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

--- a/mercurial/revset.py	Mon Jun 13 18:20:00 2016 +0100
+++ b/mercurial/revset.py	Mon Jun 13 18:20:00 2016 +0100
@@ -1843,7 +1843,7 @@
     'date': lambda c: c.date()[0],
 }
 
-@predicate('sort(set[, [-]key...])', safe=True)
+@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.
@@ -1855,8 +1855,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 that
+    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'))
@@ -1868,12 +1874,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(_(
+            '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),
+                       istopo=True)
+        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):
@@ -1887,7 +1916,7 @@
             raise error.ParseError(_("unknown sort key %r") % fk)
     return baseset([c.rev() for c in ctxs])
 
-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

--- a/tests/test-glog-topological.t	Mon Jun 13 18:20:00 2016 +0100
+++ b/tests/test-glog-topological.t	Mon Jun 13 18:20:00 2016 +0100
@@ -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

--- a/tests/test-revset.t	Mon Jun 13 18:20:00 2016 +0100
+++ b/tests/test-revset.t	Mon Jun 13 18:20:00 2016 +0100
@@ -1106,6 +1106,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: 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]
+
   $ cd ..
   $ cd repo