Patchwork [4,of,4,V3] revsets: add new topographical sort

login
register
mail settings
Submitter Martijn Pieters
Date June 8, 2016, 4:20 p.m.
Message ID <9f8ec1d987d7e20e1b31.1465402841@mjpieters-mbp>
Download mbox | patch
Permalink /patch/15442/
State Changes Requested
Delegated to: Augie Fackler
Headers show

Comments

Martijn Pieters - June 8, 2016, 4:20 p.m.
# HG changeset patch
# User Martijn Pieters <mjpieters@fb.com>
# Date 1465399954 -3600
#      Wed Jun 08 16:32:34 2016 +0100
# Node ID 9f8ec1d987d7e20e1b31b598041e98ac2e16628a
# Parent  b573c3858edcd746dd0868a6b243dd73ddb8105a
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)"
Augie Fackler - June 10, 2016, 3:47 a.m.
On Wed, Jun 08, 2016 at 05:20:41PM +0100, Martijn Pieters wrote:
> # HG changeset patch
> # User Martijn Pieters <mjpieters@fb.com>
> # Date 1465399954 -3600
> #      Wed Jun 08 16:32:34 2016 +0100
> # Node ID 9f8ec1d987d7e20e1b31b598041e98ac2e16628a
> # Parent  b573c3858edcd746dd0868a6b243dd73ddb8105a
> revsets: add new topographical sort

At quick skim, the rest of the series looks good here.

>
> 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/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
> @@ -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 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'))
> @@ -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(_(
> +            '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),
> +                       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
> 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
> @@ -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: 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]
> +
>    $ cd ..
>    $ cd repo
>
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel

Patch

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
@@ -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 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'))
@@ -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(_(
+            '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),
+                       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
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
@@ -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: 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]
+
   $ cd ..
   $ cd repo