rebase: introduce support for automatically rebasing orphan changes

_destautorebase(SRC) is based on the _destrestack(SRC) revset from
fbamend. The supporting _possibledestination function is extracted
from evolve, with minor cleanups.

We've considered some alternatives here:
 * This change, but with --auto as the flag name. We're hedging our bets
   on this a little in this change so that if this ends up being the wrong
   direction we haven't burned the valauble --auto name on rebase.
 * --destination auto: I've got reservations about the discoverability of this,
   and we don't currently have a good story for a revset alias of sorts that
   changes behavior depending on the context in which it's used.
 * A "rebase presets" feature, where we could use the currently-an-error
   positional argument space for the rebase command to define presets, so that
   users could define a 'linearize' preset that specifies
   --revision='orphan()-obsolete()' and --dest=_destautoorphanrebase(SRC).

Personally, I find the third option somewhat appealing, but am
hesitant to "spend" the functionality space of positional arguments to
the rebase command. We should revisit the way we expose this
functionality sometime in the 4.7 cycle once we've had a chance to vet
the implementation of the functionality.

Differential Revision: https://phab.mercurial-scm.org/D2668

hgext/rebase.py

@@ -108,6 +108,25 b' def _revsetdestrebase(repo, subset, x):'
         sourceset = revset.getset(repo, smartset.fullreposet(repo), x)
     return subset & smartset.baseset([_destrebase(repo, sourceset)])
 
+@revsetpredicate('_destautoorphanrebase')
+def _revsetdestautoorphanrebase(repo, subset, x):
+    """automatic rebase destination for a single orphan revision"""
+    unfi = repo.unfiltered()
+    obsoleted = unfi.revs('obsolete()')
+
+    src = revset.getset(repo, subset, x).first()
+
+    # Empty src or already obsoleted - Do not return a destination
+    if not src or src in obsoleted:
+        return smartset.baseset()
+    dests = destutil.orphanpossibledestination(repo, src)
+    if len(dests) > 1:
+        raise error.Abort(
+            _("ambiguous automatic rebase: %r could end up on any of %r") % (
+                src, dests))
+    # We have zero or one destination, so we can just return here.
+    return smartset.baseset(dests)
+
 def _ctxdesc(ctx):
     """short description for a context"""
     desc = '%d:%s "%s"' % (ctx.rev(), ctx,
@@ -651,7 +670,10 b' class rebaseruntime(object):'
     ('i', 'interactive', False, _('(DEPRECATED)')),
     ('t', 'tool', '', _('specify merge tool')),
     ('c', 'continue', False, _('continue an interrupted rebase')),
-    ('a', 'abort', False, _('abort an interrupted rebase'))] +
+    ('a', 'abort', False, _('abort an interrupted rebase')),
+    ('', 'auto-orphans', '', _('automatically rebase orphan revisions '
+                               'in the specified revset (EXPERIMENTAL)')),
+     ] +
     cmdutil.formatteropts,
     _('[-s REV | -b REV] [-d REV] [OPTION]'))
 def rebase(ui, repo, **opts):
@@ -783,6 +805,15 b' def rebase(ui, repo, **opts):'
         # fail the entire transaction.)
         inmemory = False
 
+    if opts.get('auto_orphans'):
+        for key in opts:
+            if key != 'auto_orphans' and opts.get(key):
+                raise error.Abort(_('--auto-orphans is incompatible with %s') %
+                                  ('--' + key))
+        userrevs = list(repo.revs(opts.get('auto_orphans')))
+        opts['rev'] = [revsetlang.formatspec('%ld and orphan()', userrevs)]
+        opts['dest'] = '_destautoorphanrebase(SRC)'
+
     if inmemory:
         try:
             # in-memory merge doesn't support conflicts, so if we hit any, abort

mercurial/destutil.py

@@ -16,6 +16,39 b' from . import ('
     stack
 )
 
+def orphanpossibledestination(repo, rev):
+    """Return all changesets that may be a new parent for orphan `rev`.
+
+    This function works fine on non-orphan revisions, it's just silly
+    because there's no destination implied by obsolete markers, so
+    it'll return nothing.
+    """
+    tonode = repo.changelog.node
+    parents = repo.changelog.parentrevs
+    torev = repo.changelog.rev
+    dest = set()
+    tovisit = list(parents(rev))
+    while tovisit:
+        r = tovisit.pop()
+        succsets = obsutil.successorssets(repo, tonode(r))
+        if not succsets:
+            # if there are no successors for r, r was probably pruned
+            # and we should walk up to r's parents to try and find
+            # some successors.
+            tovisit.extend(parents(r))
+        else:
+            # We should probably pick only one destination from split
+            # (case where '1 < len(ss)'), This could be the currently
+            # tipmost, but the correct result is less clear when
+            # results of the split have been moved such that they
+            # reside on multiple branches.
+            for ss in succsets:
+                for n in ss:
+                    dr = torev(n)
+                    if dr != -1:
+                        dest.add(dr)
+    return dest
+
 def _destupdateobs(repo, clean):
     """decide of an update destination from obsolescence markers"""
     node = None

tests/test-rebase-obsolete.t

@@ -482,7 +482,34 b' Test that rewriting leaving instability '
   |/
   o  0:cd010b8cd998 A
   
+  $ cd ..
+  $ cp -R hidden stabilize
+  $ cd stabilize
+  $ hg rebase --auto-orphans '0::' -d 10
+  abort: --auto-orphans is incompatible with --dest
+  [255]
+  $ hg rebase --auto-orphans '0::'
+  rebasing 9:cf44d2f5a9f4 "D"
+  $ hg log -G
+  o  12:7e3935feaa68 D
+  |
+  o  11:0d8f238b634c C
+  |
+  o  10:7c6027df6a99 B
+  |
+  @  7:02de42196ebe H
+  |
+  | o  6:eea13746799a G
+  |/|
+  o |  5:24b6387c8c8c F
+  | |
+  | o  4:9520eea781bc E
+  |/
+  o  0:cd010b8cd998 A
+  
 
+  $ cd ../hidden
+  $ rm -r ../stabilize
 
 Test multiple root handling
 ------------------------------------