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

# 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)"

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