Patchwork rebase: rebase changesets with branch grouped

# HG changeset patch
# User Xidorn Quan <me@upsuper.org>
# Date 1474095776 -36000
#      Sat Sep 17 17:02:56 2016 +1000
# Node ID 88184dc23ccacfc8ae450abc5d574b8b028bca79
# Parent  285a8c3e53f2183438f0cdbc238e4ab851d0d110
rebase: rebase changesets with branch grouped

There's a topoiter or topoorder somewhere that is used by "hg log". Can
that be used here? Sorry, on mobile and too lazy to find the exact function.

On Sat, Sep 17, 2016, 08:18 Xidorn Quan <me@upsuper.org> wrote:

> # HG changeset patch
> # User Xidorn Quan <me@upsuper.org>
> # Date 1474095776 -36000
> #      Sat Sep 17 17:02:56 2016 +1000
> # Node ID 88184dc23ccacfc8ae450abc5d574b8b028bca79
> # Parent  285a8c3e53f2183438f0cdbc238e4ab851d0d110
> rebase: rebase changesets with branch grouped
>
> diff --git a/hgext/rebase.py b/hgext/rebase.py
> --- a/hgext/rebase.py
> +++ b/hgext/rebase.py
> @@ -330,18 +330,38 @@ class rebaseruntime(object):
>
> inclusive=True)
>
>          # Keep track of the current bookmarks in order to reset them later
>          self.currentbookmarks = repo._bookmarks.copy()
>          self.activebookmark = self.activebookmark or repo._activebookmark
>          if self.activebookmark:
>              bookmarks.deactivate(repo)
>
> -        sortedrevs = sorted(self.state)
> +        # Sort revisions with branches grouped
>          cands = [k for k, v in self.state.iteritems() if v == revtodo]
> +        remainrevs = set(self.state.iterkeys())
> +        sortedrevs = []
> +        # Sort based on candidates and put their ancestors with them
> +        for cand in util.branchsorted(repo, cands):
> +            ancestors = [cand]
> +            remainrevs.remove(cand)
> +            i = 0
> +            while i < len(ancestors):
> +                ctx = repo[ancestors[i]]
> +                for p in ctx.parents():
> +                    prev = p.rev()
> +                    if prev in remainrevs:
> +                        remainrevs.remove(prev)
> +                        ancestors.append(prev)
> +                i += 1
> +            ancestors.reverse()
> +            sortedrevs.extend(ancestors)
> +        # Finally, descendents which are not rebased
> +        sortedrevs.extend(sorted(remainrevs))
> +
>          total = len(cands)
>          pos = 0
>          for rev in sortedrevs:
>              ctx = repo[rev]
>              desc = '%d:%s "%s"' % (ctx.rev(), ctx,
>                                     ctx.description().split('\n', 1)[0])
>              names = repo.nodetags(ctx.node()) +
> repo.nodebookmarks(ctx.node())
>              if names:
> diff --git a/mercurial/util.py b/mercurial/util.py
> --- a/mercurial/util.py
> +++ b/mercurial/util.py
> @@ -2897,8 +2897,33 @@ decompressors = {None: lambda fh: fh,
>                   'BZ': _makedecompressor(lambda: bz2.BZ2Decompressor()),
>                   'GZ': _makedecompressor(lambda: zlib.decompressobj()),
>                   }
>  # also support the old form by courtesies
>  decompressors['UN'] = decompressors[None]
>
>  # convenient shortcut
>  dst = debugstacktrace
> +
> +def branchsorted(repo, revs, sortrevs=None):
> +    '''Returns a sorted list of revisions in a order that branches are
> +    grouped together.'''
> +    remainrevs = set(revs)
> +    stack = [sorted(revs, reverse=True)]
> +    result = []
> +    while stack:
> +        stacktop = stack[-1]
> +        if not stacktop:
> +            stack.pop()
> +            continue
> +        nextrev = stacktop.pop()
> +        if nextrev not in remainrevs:
> +            continue
> +        ctx = repo[nextrev]
> +        # If any of its parents is still in remainrevs, we can not put
> +        # the changeset into result. We would traverse to it again when
> +        # we resolve all its parents.
> +        if any(p.rev() in remainrevs for p in ctx.parents()):
> +            continue
> +        remainrevs.remove(nextrev)
> +        result.append(nextrev)
> +        stack.append(sorted((c.rev() for c in ctx.children()),
> reverse=True))
> +    return result
> diff --git a/tests/test-rebase-branch-order.t
> b/tests/test-rebase-branch-order.t
> new file mode 100644
> --- /dev/null
> +++ b/tests/test-rebase-branch-order.t
> @@ -0,0 +1,89 @@
> +  $ cat >> $HGRCPATH <<EOF
> +  > [extensions]
> +  > rebase=
> +  > [alias]
> +  > tglog=log -G --template "{rev}:{node|short} {desc}"
> +  > EOF
> +
> +  $ hg init repo
> +  $ cd repo
> +
> +  $ touch a
> +  $ hg ci -Am A
> +  adding a
> +
> +  $ touch b
> +  $ hg ci -Am B
> +  adding b
> +
> +  $ touch c
> +  $ hg ci -Am C
> +  adding c
> +
> +  $ hg up 1
> +  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
> +  $ touch d
> +  $ hg ci -Am D
> +  adding d
> +  created new head
> +
> +  $ hg up 2
> +  1 files updated, 0 files merged, 1 files removed, 0 files unresolved
> +  $ touch e
> +  $ hg ci -Am E
> +  adding e
> +
> +  $ hg up 3
> +  1 files updated, 0 files merged, 2 files removed, 0 files unresolved
> +  $ touch f
> +  $ hg ci -Am F
> +  adding f
> +
> +  $ hg up 0
> +  0 files updated, 0 files merged, 3 files removed, 0 files unresolved
> +  $ touch g
> +  $ hg ci -Am G
> +  adding g
> +  created new head
> +
> +  $ hg tglog
> +  @  6:124bb27b6f28 G
> +  |
> +  | o  5:412b391de760 F
> +  | |
> +  | | o  4:82ae8dc7a9b7 E
> +  | | |
> +  | o |  3:ab709c9f7171 D
> +  | | |
> +  | | o  2:d84f5cfaaf14 C
> +  | |/
> +  | o  1:76035bbd54bd B
> +  |/
> +  o  0:216878401574 A
> +
> +
> +Test rebasing is done with commits in branch grouped together.
> +
> +  $ hg rebase -s 1 -d 6
> +  rebasing 1:76035bbd54bd "B"
> +  rebasing 2:d84f5cfaaf14 "C"
> +  rebasing 4:82ae8dc7a9b7 "E"
> +  rebasing 3:ab709c9f7171 "D"
> +  rebasing 5:412b391de760 "F"
> +  saved backup bundle to
> $TESTTMP/repo/.hg/strip-backup/76035bbd54bd-e341bc99-backup.hg (glob)
> +
> +  $ hg tglog
> +  o  6:31884cfb735e F
> +  |
> +  o  5:6d89fa5b0909 D
> +  |
> +  | o  4:de64d97c697b E
> +  | |
> +  | o  3:b18e4d2d0aa1 C
> +  |/
> +  o  2:0983daf9ff6a B
> +  |
> +  @  1:124bb27b6f28 G
> +  |
> +  o  0:216878401574 A
> +
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>

On 09/17/2016 09:11 AM, Xidorn Quan wrote:
> # HG changeset patch
> # User Xidorn Quan <me@upsuper.org>
> # Date 1474095776 -36000
> #      Sat Sep 17 17:02:56 2016 +1000
> # Node ID 88184dc23ccacfc8ae450abc5d574b8b028bca79
> # Parent  285a8c3e53f2183438f0cdbc238e4ab851d0d110
> rebase: rebase changesets with branch grouped

This description good get a bit better

- reference the issue you create on the tacker by adding "(issue###)" to 
the first line,
- add a "(BC)" flag, even if this is small and useful change, this is a 
change to backward compatibility.
- explain why this change is a good idea. Your rational in the bug 
report was good, just include them there.

>
> diff --git a/hgext/rebase.py b/hgext/rebase.py
> --- a/hgext/rebase.py
> +++ b/hgext/rebase.py
> @@ -330,18 +330,38 @@ class rebaseruntime(object):
>                                                                 inclusive=True)
>
>          # Keep track of the current bookmarks in order to reset them later
>          self.currentbookmarks = repo._bookmarks.copy()
>          self.activebookmark = self.activebookmark or repo._activebookmark
>          if self.activebookmark:
>              bookmarks.deactivate(repo)
>
> -        sortedrevs = sorted(self.state)
> +        # Sort revisions with branches grouped
>          cands = [k for k, v in self.state.iteritems() if v == revtodo]
> +        remainrevs = set(self.state.iterkeys())
> +        sortedrevs = []
> +        # Sort based on candidates and put their ancestors with them
> +        for cand in util.branchsorted(repo, cands):
> +            ancestors = [cand]
> +            remainrevs.remove(cand)
> +            i = 0
> +            while i < len(ancestors):
> +                ctx = repo[ancestors[i]]
> +                for p in ctx.parents():
> +                    prev = p.rev()
> +                    if prev in remainrevs:
> +                        remainrevs.remove(prev)
> +                        ancestors.append(prev)
> +                i += 1
> +            ancestors.reverse()
> +            sortedrevs.extend(ancestors)
> +        # Finally, descendents which are not rebased
> +        sortedrevs.extend(sorted(remainrevs))
> +

As Martin pointed, we have already have topological function in core. 
The "official" way to access it is through revset. Something like the 
following line should do (might need adjustment)

	sortedrevs = repo.revs("reverse(sort( %ld, "topo"))", revs)

>          total = len(cands)
>          pos = 0
>          for rev in sortedrevs:
>              ctx = repo[rev]
>              desc = '%d:%s "%s"' % (ctx.rev(), ctx,
>                                     ctx.description().split('\n', 1)[0])
>              names = repo.nodetags(ctx.node()) + repo.nodebookmarks(ctx.node())
>              if names:
> diff --git a/mercurial/util.py b/mercurial/util.py
> --- a/mercurial/util.py
> +++ b/mercurial/util.py
> @@ -2897,8 +2897,33 @@ decompressors = {None: lambda fh: fh,
>                   'BZ': _makedecompressor(lambda: bz2.BZ2Decompressor()),
>                   'GZ': _makedecompressor(lambda: zlib.decompressobj()),
>                   }
>  # also support the old form by courtesies
>  decompressors['UN'] = decompressors[None]
>
>  # convenient shortcut
>  dst = debugstacktrace
> +
> +def branchsorted(repo, revs, sortrevs=None):
> +    '''Returns a sorted list of revisions in a order that branches are
> +    grouped together.'''
> +    remainrevs = set(revs)
> +    stack = [sorted(revs, reverse=True)]
> +    result = []
> +    while stack:
> +        stacktop = stack[-1]
> +        if not stacktop:
> +            stack.pop()
> +            continue
> +        nextrev = stacktop.pop()
> +        if nextrev not in remainrevs:
> +            continue
> +        ctx = repo[nextrev]
> +        # If any of its parents is still in remainrevs, we can not put
> +        # the changeset into result. We would traverse to it again when
> +        # we resolve all its parents.
> +        if any(p.rev() in remainrevs for p in ctx.parents()):
> +            continue
> +        remainrevs.remove(nextrev)
> +        result.append(nextrev)
> +        stack.append(sorted((c.rev() for c in ctx.children()), reverse=True))
> +    return result
> diff --git a/tests/test-rebase-branch-order.t b/tests/test-rebase-branch-order.t
> new file mode 100644
> --- /dev/null
> +++ b/tests/test-rebase-branch-order.t

Please do not introduce a new test file for such a small extra test 
(each test file have a slight overhead). Find and existing rebase test 
file where it would make sense to add the extra bits to tests this.

Cheers,