Patchwork [2,of,4] rebase: initial support for multiple destinations

login
register
mail settings
Submitter Jun Wu
Date June 24, 2017, 5:04 a.m.
Message ID <79f7ce082ec2fc97d5bd.1498280681@x1c>
Download mbox | patch
Permalink /patch/21660/
State Changes Requested
Headers show

Comments

Jun Wu - June 24, 2017, 5:04 a.m.
# HG changeset patch
# User Jun Wu <quark@fb.com>
# Date 1498279696 25200
#      Fri Jun 23 21:48:16 2017 -0700
# Node ID 79f7ce082ec2fc97d5bd67e3fcffb66daf6e7d4e
# Parent  a8a42cc07de6538e92bae498882144f9b8296c98
# Available At https://bitbucket.org/quark-zju/hg-draft
#              hg pull https://bitbucket.org/quark-zju/hg-draft -r 79f7ce082ec2
rebase: initial support for multiple destinations

This patch defines "SRC" and "ALLSRC" to "--dest" revset so destination
could be different for different source revisions.

This is useful, for example, "-s 'unstable()' -d 'calc-the-dest(SRC)'" to
solve instability, which is a highly wanted feature. Ideally rebase and
revset takes care of it and there is no need for separate commands or flags.
Moreover, power users can read the revset so the behavior is less magical,
sysadmins can ship comprehensive default revset in configs so it's also
friendly to newbie users.

This patch is long but I don't have a good way to split it - things are
tightly coupled and split means undesirable temporary untested changes.
Rebase tests seem to be solid, so I guess we might just rely on tests.

Changes:

  - Replace "dest" with "destmap" everywhere.
  - Update the state file format to store the destination map.
    Add a test for old state file support.
  - Completely rewrite "defineparents" and its dependence "nearestrebased".
    The old code has too many tech debts and is very error-prone (I have
    tried) to add correct destmap support. The new code should be much more
    maintainable.
  - Partially rewrite "_computeobsoletenotrebased" to support destmap. Drop
    a comment saying split is problematic due to API limitation.
  - Remove "self.destancestors", use changelog index to test ancestors.
    This simplifies the code and makes it less error-prone (impossible to
    have inconsistent dest and destancestors). The fact that index is C code
    and "ancestors" is Python means the new code might be even faster.
  - Resolve dest revset using "SRC" and "ALLSRC".

The feature is not completed yet. Namely, it's problematic if source and
destination overlaps. So it requires an experimental config
"experimental.rebasemultidest" and is disabled by default for now.

Patch

diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -22,5 +22,4 @@  import os
 from mercurial.i18n import _
 from mercurial.node import (
-    hex,
     nullid,
     nullrev,
@@ -47,4 +46,5 @@  from mercurial import (
     repoview,
     revset,
+    revsetlang,
     scmutil,
     smartset,
@@ -140,7 +140,6 @@  class rebaseruntime(object):
         self.activebookmark = None
         self.currentbookmarks = None
-        self.dest = None
+        self.destmap = {}
         self.skipped = set()
-        self.destancestors = set()
 
         self.collapsef = opts.get('collapse', False)
@@ -172,5 +171,6 @@  class rebaseruntime(object):
         repo = self.repo.unfiltered()
         f.write(repo[self.originalwd].hex() + '\n')
-        f.write(repo[self.dest].hex() + '\n')
+        # was "dest". we now write dest per src root below.
+        f.write('\n')
         f.write(repo[self.external].hex() + '\n')
         f.write('%d\n' % int(self.collapsef))
@@ -178,15 +178,13 @@  class rebaseruntime(object):
         f.write('%d\n' % int(self.keepbranchesf))
         f.write('%s\n' % (self.activebookmark or ''))
+        destmap = self.destmap
         for d, v in self.state.iteritems():
             oldrev = repo[d].hex()
             if v >= 0:
                 newrev = repo[v].hex()
-            elif v == revtodo:
-                # To maintain format compatibility, we have to use nullid.
-                # Please do remove this special case when upgrading the format.
-                newrev = hex(nullid)
             else:
                 newrev = v
-            f.write("%s:%s\n" % (oldrev, newrev))
+            destnode = repo[destmap[d]].hex()
+            f.write("%s:%s:%s\n" % (oldrev, newrev, destnode))
         repo.ui.debug('rebase status stored\n')
 
@@ -195,9 +193,10 @@  class rebaseruntime(object):
         repo = self.repo
         keepbranches = None
-        dest = None
+        legacydest = None
         collapse = False
         external = nullrev
         activebookmark = None
         state = {}
+        destmap = {}
 
         try:
@@ -207,5 +206,8 @@  class rebaseruntime(object):
                     originalwd = repo[l].rev()
                 elif i == 1:
-                    dest = repo[l].rev()
+                    # this line should be empty in newer version. but legacy
+                    # clients may still use it
+                    if l:
+                        legacydest = repo[l].rev()
                 elif i == 2:
                     external = repo[l].rev()
@@ -222,7 +224,13 @@  class rebaseruntime(object):
                     activebookmark = l
                 else:
-                    oldrev, newrev = l.split(':')
-                    if newrev in (str(nullmerge), str(revignored),
-                                  str(revprecursor), str(revpruned)):
+                    args = l.split(':')
+                    oldrev = args[0]
+                    newrev = args[1]
+                    if len(args) > 2:
+                        destnode = args[2]
+                    else:
+                        destnode = legacydest
+                    destmap[repo[oldrev].rev()] = repo[destnode].rev()
+                    if newrev.startswith('-'):
                         state[repo[oldrev].rev()] = int(newrev)
                     elif newrev == nullid:
@@ -243,5 +251,5 @@  class rebaseruntime(object):
         # recompute the set of skipped revs
         if not collapse:
-            seen = {dest}
+            seen = set(destmap.values())
             for old, new in sorted(state.items()):
                 if new != revtodo and new in seen:
@@ -254,5 +262,5 @@  class rebaseruntime(object):
 
         self.originalwd = originalwd
-        self.dest = dest
+        self.destmap = destmap
         self.state = state
         self.skipped = skipped
@@ -263,10 +271,10 @@  class rebaseruntime(object):
         self.activebookmark = activebookmark
 
-    def _handleskippingobsolete(self, rebaserevs, obsoleterevs, dest):
+    def _handleskippingobsolete(self, rebaserevs, obsoleterevs, destmap):
         """Compute structures necessary for skipping obsolete revisions
 
         rebaserevs:     iterable of all revisions that are to be rebased
         obsoleterevs:   iterable of all obsolete revisions in rebaseset
-        dest:           a destination revision for the rebase operation
+        destmap:        {srcrev: destrev} destination revisions
         """
         self.obsoletenotrebased = {}
@@ -277,5 +285,5 @@  class rebaseruntime(object):
         obsoleteset = set(obsoleterevs)
         self.obsoletenotrebased = _computeobsoletenotrebased(self.repo,
-                                    obsoleteset, dest)
+                                    obsoleteset, destmap)
         skippedset = set(self.obsoletenotrebased)
         _checkobsrebase(self.repo, self.ui, obsoleteset, rebaseset, skippedset)
@@ -297,12 +305,12 @@  class rebaseruntime(object):
                 raise error.Abort(msg, hint=hint)
         if isabort:
-            return abort(self.repo, self.originalwd, self.dest,
+            return abort(self.repo, self.originalwd, self.destmap,
                          self.state, activebookmark=self.activebookmark)
 
         obsrevs = (r for r, st in self.state.items() if st == revprecursor)
-        self._handleskippingobsolete(self.state.keys(), obsrevs, self.dest)
+        self._handleskippingobsolete(self.state.keys(), obsrevs, self.destmap)
 
-    def _preparenewrebase(self, dest, rebaseset):
-        if dest is None:
+    def _preparenewrebase(self, destmap, rebaseset):
+        if not destmap:
             return _nothingtorebase()
 
@@ -317,7 +325,7 @@  class rebaseruntime(object):
 
         obsrevs = _filterobsoleterevs(self.repo, set(rebaseset))
-        self._handleskippingobsolete(rebaseset, obsrevs, dest)
+        self._handleskippingobsolete(rebaseset, obsrevs, destmap)
 
-        result = buildstate(self.repo, dest, rebaseset, self.collapsef,
+        result = buildstate(self.repo, destmap, rebaseset, self.collapsef,
                             self.obsoletenotrebased)
 
@@ -333,14 +341,19 @@  class rebaseruntime(object):
                                   hint=_("see 'hg help phases' for details"))
 
-        (self.originalwd, self.dest, self.state) = result
+        (self.originalwd, self.destmap, self.state) = result
         if self.collapsef:
-            self.destancestors = self.repo.changelog.ancestors(
-                                        [self.dest],
-                                        inclusive=True)
-            self.external = externalparent(self.repo, self.state,
-                                              self.destancestors)
+            dests = set(self.destmap.values())
+            if len(dests) != 1:
+                raise error.Abort(
+                    _('--collapse does not work with multiple destinations'))
+            destrev = next(iter(dests))
+            destancestors = self.repo.changelog.ancestors([destrev],
+                                                          inclusive=True)
+            self.external = externalparent(self.repo, self.state, destancestors)
 
-        if dest.closesbranch() and not self.keepbranchesf:
-            self.ui.status(_('reopening closed branch head %s\n') % dest)
+        for destrev in sorted(set(destmap.values())):
+            dest = self.repo[destrev]
+            if dest.closesbranch() and not self.keepbranchesf:
+                self.ui.status(_('reopening closed branch head %s\n') % dest)
 
     def _performrebase(self, tr):
@@ -359,9 +372,4 @@  class rebaseruntime(object):
                             'branches'))
 
-        # Rebase
-        if not self.destancestors:
-            self.destancestors = repo.changelog.ancestors([self.dest],
-                                                          inclusive=True)
-
         # Keep track of the current bookmarks in order to reset them later
         self.currentbookmarks = repo._bookmarks.copy()
@@ -379,4 +387,5 @@  class rebaseruntime(object):
         pos = 0
         for rev in sortedrevs:
+            dest = self.destmap[rev]
             ctx = repo[rev]
             desc = '%d:%s "%s"' % (ctx.rev(), ctx,
@@ -392,8 +401,6 @@  class rebaseruntime(object):
                 ui.progress(_("rebasing"), pos, ("%d:%s" % (rev, ctx)),
                             _('changesets'), total)
-                p1, p2, base = defineparents(repo, rev, self.dest,
-                                             self.state,
-                                             self.destancestors,
-                                             self.obsoletenotrebased)
+                p1, p2, base = defineparents(repo, rev, self.destmap,
+                                             self.state)
                 self.storestatus(tr=tr)
                 storecollapsemsg(repo, self.collapsemsg)
@@ -405,5 +412,5 @@  class rebaseruntime(object):
                                      'rebase')
                         stats = rebasenode(repo, rev, p1, base, self.state,
-                                           self.collapsef, self.dest)
+                                           self.collapsef, dest)
                         if stats and stats[3] > 0:
                             raise error.InterventionRequired(
@@ -464,8 +471,6 @@  class rebaseruntime(object):
         repo, ui, opts = self.repo, self.ui, self.opts
         if self.collapsef and not self.keepopen:
-            p1, p2, _base = defineparents(repo, min(self.state),
-                                          self.dest, self.state,
-                                          self.destancestors,
-                                          self.obsoletenotrebased)
+            src = min(self.state)
+            p1, p2, _base = defineparents(repo, src, self.destmap, self.state)
             editopt = opts.get('edit')
             editform = 'rebase.collapse'
@@ -519,7 +524,4 @@  class rebaseruntime(object):
                     succ = self.obsoletenotrebased[k]
                     nstate[repo[k].node()] = repo[succ].node()
-            # XXX this is the same as dest.node() for the non-continue path --
-            # this should probably be cleaned up
-            destnode = repo[self.dest].node()
 
         # restore original working directory
@@ -537,5 +539,5 @@  class rebaseruntime(object):
         if self.currentbookmarks:
             with repo.transaction('bookmark') as tr:
-                updatebookmarks(repo, destnode, nstate,
+                updatebookmarks(repo, self.destmap, nstate,
                                 self.currentbookmarks, tr)
                 if self.activebookmark not in repo._bookmarks:
@@ -729,7 +731,7 @@  def rebase(ui, repo, **opts):
                 return retcode
         else:
-            dest, rebaseset = _definesets(ui, repo, destf, srcf, basef, revf,
-                                          destspace=destspace)
-            retcode = rbsrt._preparenewrebase(dest, rebaseset)
+            destmap, rebaseset = _definesets(ui, repo, destf, srcf, basef, revf,
+                                             destspace=destspace)
+            retcode = rbsrt._preparenewrebase(destmap, rebaseset)
             if retcode is not None:
                 return retcode
@@ -774,6 +776,5 @@  def _definesets(ui, repo, destf=None, sr
                           hint=_('use: hg rebase -d REV'))
 
-    if destf:
-        dest = scmutil.revsingle(repo, destf)
+    dest = None
 
     if revf:
@@ -795,5 +796,7 @@  def _definesets(ui, repo, destf=None, sr
                         "can't compute rebase set\n"))
             return None, None
-        if not destf:
+        if destf:
+            dest = scmutil.revsingle(repo, destf)
+        else:
             dest = repo[_destrebase(repo, base, destspace=destspace)]
             destf = str(dest)
@@ -844,5 +847,41 @@  def _definesets(ui, repo, destf=None, sr
         destf = str(dest)
 
-    return dest, rebaseset
+    # fast path: try to resolve dest without local revsets
+    if dest is None:
+        try:
+            dest = scmutil.revsingle(repo, destf)
+        except error.RepoLookupError:
+            # might have used "SRC" or "ALLSRC", raise if multidest feature is
+            # not enabled
+            if not ui.configbool('experimental', 'rebasemultidest', False):
+                raise
+
+    if dest is not None:
+        # assign dest to each rev in rebaseset
+        destrev = dest.rev()
+        destmap = {r: destrev for r in rebaseset} # {srcrev: destrev}
+    else:
+        # resolve dest for each src rev separately
+        destmap = {}
+        allsrc = revsetlang.formatspec('%ld', rebaseset)
+        ignored = set() # ignored revs in rebaseset
+        for r in rebaseset:
+            local = {'ALLSRC': allsrc, 'SRC': revsetlang.formatspec('%d', r)}
+            destset = repo.anyrevs([destf], user=True, local=local)
+            size = len(destset)
+            if size == 1:
+                destmap[r] = destset.first()
+            elif size == 0:
+                # no destination, remove from src (rebaseset)
+                ignored.add(r)
+            else:
+                raise error.Abort(_('rebase destination for %s is not unique')
+                                  % repo[r])
+        if ignored:
+            rebaseset -= ignored
+            if not rebaseset:
+                ui.status(_('nothing to rebase - empty destination\n'))
+
+    return destmap, rebaseset
 
 def externalparent(repo, state, destancestors):
@@ -926,12 +965,38 @@  def rebasenode(repo, rev, p1, base, stat
     return stats
 
-def nearestrebased(repo, rev, state):
-    """return the nearest ancestors of rev in the rebase result"""
-    rebased = [r for r in state if state[r] > nullmerge]
-    candidates = repo.revs('max(%ld  and (::%d))', rebased, rev)
-    if candidates:
-        return state[candidates.first()]
-    else:
-        return None
+def adjusteddest(repo, rev, prev, destmap, state):
+    """adjust rebase destination given the current rebase state
+
+    rev is being rebased, prev is one of its parent.
+
+    For example, when rebasing E to F:
+
+        B' <- written during the rebase
+        |
+        F <- original destination of B, E
+        |
+        | E <- rev, which is being rebased
+        | |
+        | D <- prev, one parent of rev being checked
+        | |
+        | x <- skipped
+        | |
+        | C <- rebased as C'       C' <- written during the rebase
+        | |                        |
+        | B <- rebased as B'       G <- destination of C, separate subgraph
+        |/
+        A
+
+    The destination will be adjusted from F to B'.
+    """
+    dest = destmap[rev]
+    if prev == nullrev:
+        return dest
+    # interesting rebase source - having a same dest and is rebased
+    source = [s for s, d in state.items() if d > 0 and destmap[s] == dest]
+    candidate = repo.revs('max(%ld and (::%d))', source, prev).first()
+    if candidate is not None:
+        return state[candidate]
+    return dest
 
 def _checkobsrebase(repo, ui, rebaseobsrevs, rebasesetrevs, rebaseobsskipped):
@@ -958,105 +1023,93 @@  def _checkobsrebase(repo, ui, rebaseobsr
         raise error.Abort(msg % (",".join(divhashes),), hint=h)
 
-def defineparents(repo, rev, dest, state, destancestors,
-                  obsoletenotrebased):
+def defineparents(repo, rev, destmap, state):
     'Return the new parent relationship of the revision that will be rebased'
-    parents = repo[rev].parents()
-    p1 = p2 = nullrev
-    rp1 = None
+    cl = repo.changelog
+    def ancestor(rev1, rev2):
+        # take revision numbers instead of nodes
+        return cl.rev(cl.ancestor(cl.node(rev1), cl.node(rev2)))
 
-    p1n = parents[0].rev()
-    if p1n in destancestors:
-        p1 = dest
-    elif p1n in state:
-        if state[p1n] == nullmerge:
-            p1 = dest
-        elif state[p1n] in revskipped:
-            p1 = nearestrebased(repo, p1n, state)
-            if p1 is None:
-                p1 = dest
-        else:
-            p1 = state[p1n]
-    else: # p1n external
-        p1 = dest
-        p2 = p1n
+    oldps = repo.changelog.parentrevs(rev) # old parents
+    newps = list(oldps) # new parents
+    bases = set() # merge base candidates
+    dests = [adjusteddest(repo, rev, p, destmap, state) for p in oldps]
+
+    for i, p in enumerate(oldps):
+        # Do not skip nullrev for p1. Otherwise root node cannot be rebased.
+        if p == nullrev and i != 0:
+            continue
+
+        # For non-merge changeset, just move p to adjusted dest as requested.
+        if oldps[1] == nullrev:
+            newps[i] = dests[i]
 
-    if len(parents) == 2 and parents[1].rev() not in destancestors:
-        p2n = parents[1].rev()
-        # interesting second parent
-        if p2n in state:
-            if p1 == dest: # p1n in destancestors or external
-                p1 = state[p2n]
-                if p1 == revprecursor:
-                    rp1 = obsoletenotrebased[p2n]
-            elif state[p2n] in revskipped:
-                p2 = nearestrebased(repo, p2n, state)
-                if p2 is None:
-                    # no ancestors rebased yet, detach
-                    p2 = dest
-            else:
-                p2 = state[p2n]
-        else: # p2n external
-            if p2 != nullrev: # p1n external too => rev is a merged revision
-                raise error.Abort(_('cannot use revision %d as base, result '
-                        'would have 3 parents') % rev)
-            p2 = p2n
-    repo.ui.debug(" future parents are %d and %d\n" %
-                            (repo[rp1 or p1].rev(), repo[p2].rev()))
+        # For merge changeset, if we move p to dests[i] unconditionally, both
+        # parents may change and the end result looks like "the merge loses a
+        # parent", which is a surprise. This is a limit because "--dest" only
+        # accepts one dest per src.
+        #
+        # Therefore, only move p with reasonable conditions (in this order):
+        #   - use dest, if dest is a descendent of (p or one of p's successors)
+        #   - use p's rebased result, if p is rebased (state[p] > 0)
+        #
+        # That also means, we might ignore user's dest for a merge sometimes.
+        elif ancestor(p, dests[i]) == p or state.get(p) == revprecursor:
+            newps[i] = dests[i]
+        elif p in state and state[p] > 0:
+            newps[i] = state[p]
+
+        # The old parent is a merge base candidate
+        if newps[i] != oldps[i]:
+            bases.add(p)
+
+    # Remove duplicated parent
+    if newps[1] == newps[0]:
+        newps[1] = nullrev
 
-    if not any(p.rev() in state for p in parents):
-        # Case (1) root changeset of a non-detaching rebase set.
-        # Let the merge mechanism find the base itself.
-        base = None
-    elif not repo[rev].p2():
-        # Case (2) detaching the node with a single parent, use this parent
-        base = repo[rev].p1().rev()
+    # Extra checks for merge changesets
+    if newps[1] != nullrev:
+        # If one parent becomes an ancestor of the other, drop the ancestor
+        anc = ancestor(*newps)
+        newps = [p for p in newps if p != anc]
+        assert newps
+        if len(newps) == 1:
+            newps.append(nullrev)
+        elif oldps[0] == newps[0]:
+            # Since we update to p1, swap parents if only p2 gets changed
+            newps.reverse()
+
+    # No parent change might be an error because we fail to make rev a
+    # descendent of requested dest. This can happen, for example:
+    #
+    #   C          rebase -s C -d D
+    #   |\         None of A and B will be changed to D and rebase fails.
+    #   A B   D
+    if set(newps) == set(oldps) and destmap[rev] not in newps:
+        # The error message is for compatibility. It's a bit misleading since
+        # rebase is not supposed to add new parents.
+        raise error.Abort(_('cannot use revision %d as base, '
+                            'result would have 3 parents') % rev)
+
+    repo.ui.debug(" future parents are %d and %d\n" % tuple(newps))
+
+    # Merge base
+    base = None
+    if len(bases) == 1:
+        base = next(iter(bases))
     else:
-        # Assuming there is a p1, this is the case where there also is a p2.
-        # We are thus rebasing a merge and need to pick the right merge base.
-        #
-        # Imagine we have:
-        # - M: current rebase revision in this step
-        # - A: one parent of M
-        # - B: other parent of M
-        # - D: destination of this merge step (p1 var)
-        #
-        # Consider the case where D is a descendant of A or B and the other is
-        # 'outside'. In this case, the right merge base is the D ancestor.
-        #
-        # An informal proof, assuming A is 'outside' and B is the D ancestor:
-        #
-        # If we pick B as the base, the merge involves:
-        # - changes from B to M (actual changeset payload)
-        # - changes from B to D (induced by rebase) as D is a rebased
-        #   version of B)
-        # Which exactly represent the rebase operation.
+        # Prefer merge base candidates in (ALLSRC::). Because they are usually
+        # not calculable from changelog DAG alone. For example,
         #
-        # If we pick A as the base, the merge involves:
-        # - changes from A to M (actual changeset payload)
-        # - changes from A to D (with include changes between unrelated A and B
-        #   plus changes induced by rebase)
-        # Which does not represent anything sensible and creates a lot of
-        # conflicts. A is thus not the right choice - B is.
-        #
-        # Note: The base found in this 'proof' is only correct in the specified
-        # case. This base does not make sense if is not D a descendant of A or B
-        # or if the other is not parent 'outside' (especially not if the other
-        # parent has been rebased). The current implementation does not
-        # make it feasible to consider different cases separately. In these
-        # other cases we currently just leave it to the user to correctly
-        # resolve an impossible merge using a wrong ancestor.
-        #
-        # xx, p1 could be -4, and both parents could probably be -4...
-        for p in repo[rev].parents():
-            if state.get(p.rev()) == p1:
-                base = p.rev()
-                break
-        else: # fallback when base not found
-            base = None
+        #   B'     rebase -s B -d D, when B was rebased to B'. dest for C
+        #   | C    is B', but merge base for C is B, instead of
+        #   D |    changelog.ancestor(C, B') == A. If changelog DAG and "state"
+        #   | B    edges are merged (so there will be an edge from B to B'),
+        #   |/     the merge base is still ancestor(C, B') in the merged graph.
+        #   A
+        subsetbases = bases & set(state)
+        if len(subsetbases) == 1:
+            base = sorted(subsetbases)[0]
 
-            # Raise because this function is called wrong (see issue 4106)
-            raise AssertionError('no base found to rebase on '
-                                 '(defineparents called wrong)')
-    return rp1 or p1, p2, base
+    return newps[0], newps[1], base
 
 def isagitpatch(repo, patchname):
@@ -1109,6 +1162,8 @@  def updatemq(repo, state, skipped, **opt
         mq.savedirty()
 
-def updatebookmarks(repo, destnode, nstate, originalbookmarks, tr):
+def updatebookmarks(repo, destmap, nstate, originalbookmarks, tr):
     'Move bookmarks to their correct changesets, and delete divergent ones'
+    torev = repo.changelog.rev
+    tonode = repo.changelog.node
     marks = repo._bookmarks
     for k, v in originalbookmarks.iteritems():
@@ -1116,4 +1171,5 @@  def updatebookmarks(repo, destnode, nsta
             # update the bookmarks for revs that have moved
             marks[k] = nstate[v]
+            destnode = tonode(destmap[torev(v)])
             bookmarks.deletedivergent(repo, [destnode], k)
     marks.recordchange(tr)
@@ -1168,5 +1224,5 @@  def needupdate(repo, state):
     return False
 
-def abort(repo, originalwd, dest, state, activebookmark=None):
+def abort(repo, originalwd, destmap, state, activebookmark=None):
     '''Restore the repository to its original state.  Additional args:
 
@@ -1178,5 +1234,5 @@  def abort(repo, originalwd, dest, state,
         # their values within the state mapping will be the dest rev id. The
         # dstates list must must not contain the dest rev (issue4896)
-        dstates = [s for s in state.values() if s >= 0 and s != dest]
+        dstates = [s for r, s in state.items() if s >= 0 and s != destmap[r]]
         immutable = [d for d in dstates if not repo[d].mutable()]
         cleanup = True
@@ -1197,5 +1253,6 @@  def abort(repo, originalwd, dest, state,
         if cleanup:
             shouldupdate = False
-            rebased = filter(lambda x: x >= 0 and x != dest, state.values())
+            rebased = [s for r, s in state.items()
+                       if s >= 0 and s != destmap[r]]
             if rebased:
                 strippoints = [
@@ -1203,5 +1260,5 @@  def abort(repo, originalwd, dest, state,
 
             updateifonnodes = set(rebased)
-            updateifonnodes.add(dest)
+            updateifonnodes.update(destmap.values())
             updateifonnodes.add(originalwd)
             shouldupdate = repo['.'].rev() in updateifonnodes
@@ -1225,9 +1282,9 @@  def abort(repo, originalwd, dest, state,
     return 0
 
-def buildstate(repo, dest, rebaseset, collapse, obsoletenotrebased):
+def buildstate(repo, destmap, rebaseset, collapse, obsoletenotrebased):
     '''Define which revisions are going to be rebased and where
 
     repo: repo
-    dest: context
+    destmap: {srcrev: destrev}
     rebaseset: set of rev
     '''
@@ -1238,7 +1295,8 @@  def buildstate(repo, dest, rebaseset, co
     # applied patch. But it prevents messing up the working directory when
     # a partially completed rebase is blocked by mq.
-    if 'qtip' in repo.tags() and (dest.node() in
-                            [s.node for s in repo.mq.applied]):
-        raise error.Abort(_('cannot rebase onto an applied mq patch'))
+    if 'qtip' in repo.tags():
+        mqapplied = set(repo[s.node].rev() for s in repo.mq.applied)
+        if set(destmap.values()) & mqapplied:
+            raise error.Abort(_('cannot rebase onto an applied mq patch'))
 
     roots = list(repo.set('roots(%ld)', rebaseset))
@@ -1247,7 +1305,7 @@  def buildstate(repo, dest, rebaseset, co
     roots.sort()
     state = dict.fromkeys(rebaseset, revtodo)
-    detachset = set()
     emptyrebase = True
     for root in roots:
+        dest = repo[destmap[root.rev()]]
         commonbase = root.ancestor(dest)
         if commonbase == root:
@@ -1308,16 +1366,20 @@  def buildstate(repo, dest, rebaseset, co
         if len(root.parents()) <= 1:
             # ancestors of <root> not ancestors of <dest>
-            detachset.update(repo.changelog.findmissingrevs([commonbase.rev()],
-                                                            [root.rev()]))
+            destrev = destmap[root.rev()]
+            detachset = repo.changelog.findmissingrevs([commonbase.rev()],
+                                                       [root.rev()])
+            for r in detachset:
+                if r not in state:
+                    state[r] = nullmerge
+                    destmap[r] = destrev
     if emptyrebase:
         return None
     for rev in sorted(state):
+        if state[rev] == nullmerge:
+            continue
         parents = [p for p in repo.changelog.parentrevs(rev) if p != nullrev]
         # if all parents of this revision are done, then so is this revision
         if parents and all((state.get(p) == p for p in parents)):
             state[rev] = rev
-    for r in detachset:
-        if r not in state:
-            state[r] = nullmerge
     if len(roots) > 1:
         # If we have multiple roots, we may have "hole" in the rebase set.
@@ -1334,5 +1396,6 @@  def buildstate(repo, dest, rebaseset, co
         else:
             state[r] = revprecursor
-    return originalwd, dest.rev(), state
+    assert all(r in destmap for r in state)
+    return originalwd, destmap, state
 
 def clearrebased(ui, repo, state, skipped, collapsedas=None):
@@ -1458,5 +1521,5 @@  def _filterobsoleterevs(repo, revs):
     return set(r for r in revs if repo[r].obsolete())
 
-def _computeobsoletenotrebased(repo, rebaseobsrevs, dest):
+def _computeobsoletenotrebased(repo, rebaseobsrevs, destmap):
     """return a mapping obsolete => successor for all obsolete nodes to be
     rebased that have a successors in the destination
@@ -1465,29 +1528,22 @@  def _computeobsoletenotrebased(repo, reb
     obsoletenotrebased = {}
 
-    # Build a mapping successor => obsolete nodes for the obsolete
-    # nodes to be rebased
-    allsuccessors = {}
-    cl = repo.changelog
-    for r in rebaseobsrevs:
-        node = cl.node(r)
-        for s in obsolete.allsuccessors(repo.obsstore, [node]):
-            try:
-                allsuccessors[cl.rev(s)] = cl.rev(node)
-            except LookupError:
-                pass
-
-    if allsuccessors:
-        # Look for successors of obsolete nodes to be rebased among
-        # the ancestors of dest
-        ancs = cl.ancestors([repo[dest].rev()],
-                            stoprev=min(allsuccessors),
-                            inclusive=True)
-        for s in allsuccessors:
-            if s in ancs:
-                obsoletenotrebased[allsuccessors[s]] = s
-            elif (s == allsuccessors[s] and
-                  allsuccessors.values().count(s) == 1):
-                # plain prune
-                obsoletenotrebased[s] = None
+    cl = repo.unfiltered().changelog
+    nodemap = cl.nodemap
+    for srcrev in rebaseobsrevs:
+        srcnode = cl.node(srcrev)
+        destrev = destmap[srcrev]
+        destnode = cl.node(destrev)
+        # XXX: more advanced APIs are required to handle split correctly
+        successors = list(obsolete.allsuccessors(repo.obsstore, [srcnode]))
+        if len(successors) == 1:
+            # prune
+            obsoletenotrebased[srcrev] = None
+        else:
+            for succnode in successors:
+                if succnode == srcnode or succnode not in nodemap:
+                    continue
+                if cl.isancestor(succnode, destnode):
+                    obsoletenotrebased[srcrev] = nodemap[succnode]
+                    break
 
     return obsoletenotrebased
diff --git a/tests/test-rebase-dest.t b/tests/test-rebase-dest.t
--- a/tests/test-rebase-dest.t
+++ b/tests/test-rebase-dest.t
@@ -77,2 +77,232 @@  Check rebase.requiredest interaction wit
   [255]
 
+Setup rebase with multiple destinations
+
+  $ cat >> $TESTTMP/maprevset.py <<EOF
+  > from mercurial import registrar, revset, revsetlang, smartset
+  > revsetpredicate = registrar.revsetpredicate()
+  > cache = {}
+  > @revsetpredicate('map')
+  > def map(repo, subset, x):
+  >     """(set, mapping)"""
+  >     setarg, maparg = revsetlang.getargs(x, 2, 2, '')
+  >     rset = revset.getset(repo, smartset.fullreposet(repo), setarg)
+  >     mapstr = revsetlang.getstring(maparg, '')
+  >     map = dict(a.split(':') for a in mapstr.split(','))
+  >     rev = rset.first()
+  >     desc = repo[rev].description()
+  >     newdesc = map.get(desc)
+  >     if newdesc == 'null':
+  >         revs = [-1]
+  >     else:
+  >         query = revsetlang.formatspec('desc(%s)', newdesc)
+  >         revs = repo.revs(query)
+  >     return smartset.baseset(revs)
+  > EOF
+
+  $ cat >> $HGRCPATH <<EOF
+  > [ui]
+  > allowemptycommit=1
+  > [extensions]
+  > drawdag=$TESTDIR/drawdag.py
+  > [phases]
+  > publish=False
+  > [alias]
+  > tglog = log -G --template "{rev}: {desc} {troubles}" -r 'sort(all(), topo)'
+  > [extensions]
+  > maprevset=$TESTTMP/maprevset.py
+  > [experimental]
+  > evolution=all
+  > rebasemultidest=1
+  > EOF
+
+  $ rebasewithdag() {
+  >   N=`$PYTHON -c "print($N+1)"`
+  >   hg init repo$N && cd repo$N
+  >   hg debugdrawdag
+  >   hg rebase "$@" > _rebasetmp
+  >   r=$?
+  >   grep -v 'saved backup bundle' _rebasetmp
+  >   [ $r -eq 0 ] && rm -f .hg/localtags && hg tglog
+  >   cd ..
+  >   return $r
+  > }
+
+Destination resolves to an empty set:
+
+  $ rebasewithdag -s B -d 'SRC - SRC' <<'EOS'
+  > C
+  > |
+  > B
+  > |
+  > A
+  > EOS
+  nothing to rebase - empty destination
+  [1]
+
+Multiple destinations and --collapse are not compatible:
+
+  $ rebasewithdag -s C+E -d 'SRC^^' --collapse <<'EOS'
+  > C F
+  > | |
+  > B E
+  > | |
+  > A D
+  > EOS
+  abort: --collapse does not work with multiple destinations
+  [255]
+
+Multiple destinations cannot be used with --base:
+
+  $ rebasewithdag -b B+E -d 'SRC^^' --collapse <<'EOS'
+  > B E
+  > | |
+  > A D
+  > EOS
+  abort: unknown revision 'SRC'!
+  [255]
+
+Rebase to null should work:
+
+  $ rebasewithdag -r B+E -d 'null' <<'EOS'
+  > B E
+  > | |
+  > A D
+  > EOS
+  rebasing 2:112478962961 "B" (B)
+  rebasing 3:cd488e83d208 "E" (E tip)
+  o  5: E
+  
+  o  4: B
+  
+  o  1: D
+  
+  o  0: A
+  
+Destination resolves to multiple changesets:
+
+  $ rebasewithdag -s B -d 'ALLSRC' <<'EOS'
+  > C
+  > |
+  > B
+  > |
+  > Z
+  > EOS
+  abort: rebase destination for f0a671a46792 is not unique
+  [255]
+
+Destination is an ancestor of source:
+
+  $ rebasewithdag -s B -d 'SRC' <<'EOS'
+  > C
+  > |
+  > B
+  > |
+  > Z
+  > EOS
+  abort: source is ancestor of destination
+  [255]
+
+Switch roots:
+
+  $ rebasewithdag -s 'all() - roots(all())' -d 'roots(all()) - ::SRC' <<'EOS'
+  > C  F
+  > |  |
+  > B  E
+  > |  |
+  > A  D
+  > EOS
+  rebasing 2:112478962961 "B" (B)
+  rebasing 4:26805aba1e60 "C" (C)
+  rebasing 3:cd488e83d208 "E" (E)
+  rebasing 5:0069ba24938a "F" (F tip)
+  o  9: F
+  |
+  o  8: E
+  |
+  | o  7: C
+  | |
+  | o  6: B
+  | |
+  | o  1: D
+  |
+  o  0: A
+  
+Different destinations for merge changesets with a same root:
+
+  $ rebasewithdag -s B -d '((parents(SRC)-B-A)::) - (::ALLSRC)' <<'EOS'
+  > C G
+  > |\|
+  > | F
+  > |
+  > B E
+  > |\|
+  > A D
+  > EOS
+  rebasing 3:102ab7219146 "B" (B)
+  rebasing 6:35e5af6dc4ff "C" (C tip)
+  o    8: C
+  |\
+  | o    7: B
+  | |\
+  o | |  5: G
+  | | |
+  | | o  4: E
+  | | |
+  o | |  2: F
+   / /
+  | o  1: D
+  |
+  o  0: A
+  
+Move to a previous parent:
+
+  $ rebasewithdag -s E+F+G -d 'SRC^^' <<'EOS'
+  >     H
+  >     |
+  >   D G
+  >   |/
+  >   C F
+  >   |/
+  >   B E  # E will be ignored, since E^^ is empty
+  >   |/
+  >   A
+  > EOS
+  rebasing 4:33441538d4aa "F" (F)
+  rebasing 6:cf43ad9da869 "G" (G)
+  rebasing 7:eef94f3b5f03 "H" (H tip)
+  o  10: H
+  |
+  | o  5: D
+  |/
+  o  3: C
+  |
+  | o  9: G
+  |/
+  o  1: B
+  |
+  | o  8: F
+  |/
+  | o  2: E
+  |/
+  o  0: A
+  
+Source overlaps with destination (not handled well currently):
+
+  $ rebasewithdag -s 'B+C+D' -d 'map(SRC, "B:C,C:D")' <<'EOS'
+  > B C D
+  >  \|/
+  >   A
+  > EOS
+  rebasing 1:112478962961 "B" (B)
+  rebasing 2:dc0947a82db8 "C" (C)
+  o  5: C
+  |
+  o  3: D
+  |
+  | o  4: B unstable
+  | |
+  | x  2: C
+  |/
+  o  0: A
+  
diff --git a/tests/test-rebase-legacy.t b/tests/test-rebase-legacy.t
new file mode 100644
--- /dev/null
+++ b/tests/test-rebase-legacy.t
@@ -0,0 +1,69 @@ 
+Test rebase --continue with rebasestate written by legacy client
+
+  $ cat >> $HGRCPATH <<EOF
+  > [extensions]
+  > rebase=
+  > drawdag=$TESTDIR/drawdag.py
+  > EOF
+
+  $ hg init
+  $ hg debugdrawdag <<'EOF'
+  >    D H
+  >    | |
+  >    C G
+  >    | |
+  >    B F
+  >    | |
+  >  Z A E
+  >   \|/
+  >    R
+  > EOF
+
+rebasestate generated by a legacy client running "hg rebase -r B+D+E+G+H -d Z"
+
+  $ touch .hg/last-message.txt
+  $ cat > .hg/rebasestate <<EOF
+  > 0000000000000000000000000000000000000000
+  > f424eb6a8c01c4a0c0fba9f863f79b3eb5b4b69f
+  > 0000000000000000000000000000000000000000
+  > 0
+  > 0
+  > 0
+  > 
+  > 21a6c45028857f500f56ae84fbf40689c429305b:-2
+  > de008c61a447fcfd93f808ef527d933a84048ce7:0000000000000000000000000000000000000000
+  > c1e6b162678d07d0b204e5c8267d51b4e03b633c:0000000000000000000000000000000000000000
+  > aeba276fcb7df8e10153a07ee728d5540693f5aa:-3
+  > bd5548558fcf354d37613005737a143871bf3723:-3
+  > d2fa1c02b2401b0e32867f26cce50818a4bd796a:0000000000000000000000000000000000000000
+  > 6f7a236de6852570cd54649ab62b1012bb78abc8:0000000000000000000000000000000000000000
+  > 6582e6951a9c48c236f746f186378e36f59f4928:0000000000000000000000000000000000000000
+  > EOF
+
+  $ hg rebase --continue
+  rebasing 4:c1e6b162678d "B" (B)
+  not rebasing ignored 6:bd5548558fcf "C" (C)
+  rebasing 8:6f7a236de685 "D" (D)
+  rebasing 2:de008c61a447 "E" (E)
+  not rebasing ignored 5:aeba276fcb7d "F" (F)
+  rebasing 7:d2fa1c02b240 "G" (G)
+  rebasing 9:6582e6951a9c "H" (H tip)
+  saved backup bundle to $TESTTMP/.hg/strip-backup/6f7a236de685-f3834b91-backup.hg (glob)
+
+  $ hg log -G -T '{rev}:{node|short} {desc}\n'
+  o  7:721b8da0a708 H
+  |
+  o  6:9d65695ec3c2 G
+  |
+  o  5:21c8397a5d68 E
+  |
+  | o  4:fc52970345e8 D
+  | |
+  | o  3:eac96551b107 B
+  |/
+  o  2:f424eb6a8c01 Z
+  |
+  | o  1:21a6c4502885 A
+  |/
+  o  0:b41ce7760717 R
+