diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -66,7 +66,6 @@
 revprecursor = -4
 # plain prune (no successor)
 revpruned = -5
-revskipped = (revignored, revprecursor, revpruned)
 
 cmdtable = {}
 command = registrar.command(cmdtable)
@@ -390,10 +389,7 @@
                 ui.status(_('rebasing %s\n') % desc)
                 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.dest, self.state)
                 self.storestatus(tr=tr)
                 storecollapsemsg(repo, self.collapsemsg)
                 if len(repo[None].parents()) == 2:
@@ -463,9 +459,7 @@
         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)
+                                          self.dest, self.state)
             editopt = opts.get('edit')
             editform = 'rebase.collapse'
             if self.collapsemsg:
@@ -960,15 +954,6 @@
         result.append(adjusted)
     return result
 
-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 _checkobsrebase(repo, ui, rebaseobsrevs, rebasesetrevs, rebaseobsskipped):
     """
     Abort if rebase will create divergence or rebase is noop because of markers
@@ -992,107 +977,131 @@
               "experimental.allowdivergence=True")
         raise error.Abort(msg % (",".join(divhashes),), hint=h)
 
-def defineparents(repo, rev, dest, state, destancestors,
-                  obsoletenotrebased):
-    'Return the new parent relationship of the revision that will be rebased'
-    parents = repo[rev].parents()
-    p1 = p2 = nullrev
-    rp1 = None
+def successorrevs(repo, rev):
+    """yield revision numbers for successors of rev"""
+    unfi = repo.unfiltered()
+    nodemap = unfi.changelog.nodemap
+    for s in obsutil.allsuccessors(unfi.obsstore, [unfi[rev].node()]):
+        if s in nodemap:
+            yield nodemap[s]
+
+def defineparents(repo, rev, dest, state):
+    """Return new parents and optionally a merge base for rev being rebased
+
+    The destination specified by "dest" cannot always be used directly because
+    previously rebase result could affect destination. For example,
 
-    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
+          D E    rebase -r C+D+E -d B
+          |/     C will be rebased to C'
+        B C      D's new destination will be C' instead of B
+        |/       E's new destination will be C' instead of B
+        A
+
+    The new parents of a merge is slightly more complicated. See the comment
+    block below.
+    """
+    cl = repo.changelog
+    def ancestor(rev1, rev2):
+        # take revision numbers instead of nodes
+        return cl.rev(cl.ancestor(cl.node(rev1), cl.node(rev2)))
 
-    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()))
+    oldps = repo.changelog.parentrevs(rev) # old parents
+    newps = list(oldps) # new parents
+    bases = set() # merge base candidates
+    dests = adjustdest(repo, rev, dest, state)
+
+    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]
+
+        # 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 any(ancestor(x, dests[i]) == x for x in successorrevs(repo, p)):
+            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 parent changes)
+        if newps[i] != oldps[i]:
+            bases.add(p)
 
-    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()
+    # Remove duplicated parent
+    if newps[1] == newps[0]:
+        newps[1] = nullrev
+
+    # 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]:
+            # The update code prefers updating to p1 blindly. If p1 is not
+            # changed, swap parents so update will be more likely to do the
+            # right thing.
+            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 dest 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)
+
+    # Source should not be ancestor of dest. The check here guarantees it's
+    # impossible. Checks in other places might catch some cases. But this is a
+    # double check that guarantees it's strictly impossible.
+    if any(p != nullrev and ancestor(p, rev) == rev for p in newps):
+        raise error.Abort(_('source is ancestor of destination'))
+
+    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 which are not a changelog ancestor of
+        # rev and its destination. 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.
+        #   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
         #
-        # 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
+        # Also see https://bz.mercurial-scm.org/show_bug.cgi?id=1950#c8 which
+        # uses "virtual null merge" to explain this situation in another way.
+        bases.difference_update(ancestor(rev, d) for d in set(dests))
+        if len(bases) >= 1:
+            if len(bases) > 1:
+                repo.ui.debug(
+                    'warning: cannot decide best merge base for %d '
+                    '(candidates: %r)\n' % (rev, sorted(bases)))
+            base = max(bases)
 
-            # 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):
     'Return true if the given patch is in git format'
diff --git a/tests/test-rebase-brute-force.t b/tests/test-rebase-brute-force.t
--- a/tests/test-rebase-brute-force.t
+++ b/tests/test-rebase-brute-force.t
@@ -31,8 +31,8 @@
     AD: A':Z D':Z
     BD: B':Z D':B'
    ABD: A':Z B':Z D':B'
-    CD: CRASH: revlog index out of range
-   ACD: A':Z C':A'A' D':Z
+    CD: ABORT: cannot use revision 3 as base, result would have 3 parents
+   ACD: A':Z C':A'B D':Z
    BCD: B':Z C':B'A D':B'
   ABCD: A':Z B':Z C':A'B' D':B'
 
@@ -52,4 +52,4 @@
     C: ABORT: cannot use revision 3 as base, result would have 3 parents
    BC: B':Z C':B'A
    AC: 
-  BAC: ABORT: nothing to merge
+  BAC: B':Z C':B'A
diff --git a/tests/test-rebase-newancestor.t b/tests/test-rebase-newancestor.t
--- a/tests/test-rebase-newancestor.t
+++ b/tests/test-rebase-newancestor.t
@@ -284,18 +284,7 @@
   rebasing 6:4c5f12f25ebe "merge rebase ancestors" (tip)
   resolving manifests
   removing other
-  note: merging f9daf77ffe76+ and 4c5f12f25ebe using bids from ancestors a60552eb93fb and f59da8fc0fcf
-  
-  calculating bids for ancestor a60552eb93fb
   resolving manifests
-  
-  calculating bids for ancestor f59da8fc0fcf
-  resolving manifests
-  
-  auction for merging merge bids
-   other: consensus for g
-  end of auction
-  
   getting other
   committing files:
   other
diff --git a/tests/test-rebase-obsolete.t b/tests/test-rebase-obsolete.t
--- a/tests/test-rebase-obsolete.t
+++ b/tests/test-rebase-obsolete.t
@@ -488,9 +488,33 @@
   >   A
   > EOF
 
-BROKEN: This raises an exception
-  $ hg rebase -d G -r 'B + D + F' 2>&1 | grep '^AssertionError'
-  AssertionError: no base found to rebase on (defineparents called wrong)
+  $ hg rebase -d G -r 'B + D + F'
+  rebasing 1:112478962961 "B" (B)
+  rebasing 2:b18e25de2cf5 "D" (D)
+  not rebasing ignored 4:26805aba1e60 "C" (C)
+  not rebasing ignored 5:4b61ff5c62e2 "E" (E)
+  rebasing 6:f15c3adaf214 "F" (F tip)
+  abort: cannot use revision 6 as base, result would have 3 parents
+  [255]
+  $ hg log -G
+  @  8:1971b36cbe4e D
+  |
+  | o  7:f7e03ec6c148 B
+  |/
+  | o    6:f15c3adaf214 F
+  | |\
+  | | o  5:4b61ff5c62e2 E
+  | | |
+  | o |  4:26805aba1e60 C
+  | | |
+  o | |  3:6fa3874a3b67 G
+  | | |
+  +---o  2:b18e25de2cf5 D
+  | |
+  | o  1:112478962961 B
+  |/
+  o  0:426bada5c675 A
+  
 
   $ cd ..
 
@@ -962,17 +986,19 @@
   >   A
   > EOF
 
-BROKEN: Raises an exception
-  $ hg rebase -d B -s E 2>&1 | grep AssertionError:
-  AssertionError: no base found to rebase on (defineparents called wrong)
+  $ hg rebase -d B -s E
+  note: not rebasing 3:7fb047a69f22 "E" (E), already in destination as 1:112478962961 "B"
+  rebasing 4:66f1a38021c9 "F" (F tip)
   $ hg log -G
-  o    4:66f1a38021c9 F
+  o    5:aae1787dacee F
   |\
-  | x  3:7fb047a69f22 E
-  | |
-  o |  2:b18e25de2cf5 D
-  |/
-  | o  1:112478962961 B
+  | | x  4:66f1a38021c9 F
+  | |/|
+  | | x  3:7fb047a69f22 E
+  | | |
+  | o |  2:b18e25de2cf5 D
+  | |/
+  o /  1:112478962961 B
   |/
   o  0:426bada5c675 A
   
@@ -994,19 +1020,19 @@
   $ hg rebase -d C -s D
   note: not rebasing 2:b18e25de2cf5 "D" (D), already in destination as 1:112478962961 "B"
   rebasing 5:66f1a38021c9 "F" (F tip)
-BROKEN: not rebased on top of requested destination (C)
+
   $ hg log -G
-  o    6:50e9d60b99c6 F
+  o    6:0913febf6439 F
   |\
-  | | x  5:66f1a38021c9 F
-  | |/|
-  +-----o  4:26805aba1e60 C
+  +---x  5:66f1a38021c9 F
+  | | |
+  | o |  4:26805aba1e60 C
   | | |
-  | o |  3:7fb047a69f22 E
+  o | |  3:7fb047a69f22 E
   | | |
-  | | x  2:b18e25de2cf5 D
-  | |/
-  o |  1:112478962961 B
+  +---x  2:b18e25de2cf5 D
+  | |
+  | o  1:112478962961 B
   |/
   o  0:426bada5c675 A
   
@@ -1025,19 +1051,21 @@
   >   A
   > EOF
 
-BROKEN: Raises an exception
-  $ hg rebase -d C -s E 2>&1 | grep AssertionError:
-  AssertionError: no base found to rebase on (defineparents called wrong)
+  $ hg rebase -d C -s E
+  note: not rebasing 3:7fb047a69f22 "E" (E), already in destination as 1:112478962961 "B"
+  rebasing 5:66f1a38021c9 "F" (F tip)
   $ hg log -G
-  o    5:66f1a38021c9 F
+  o    6:c6ab0cc6d220 F
   |\
-  | | o  4:26805aba1e60 C
+  +---x  5:66f1a38021c9 F
   | | |
-  | x |  3:7fb047a69f22 E
+  | o |  4:26805aba1e60 C
   | | |
-  o | |  2:b18e25de2cf5 D
-  |/ /
-  | o  1:112478962961 B
+  | | x  3:7fb047a69f22 E
+  | | |
+  o---+  2:b18e25de2cf5 D
+   / /
+  o /  1:112478962961 B
   |/
   o  0:426bada5c675 A
   
@@ -1060,9 +1088,8 @@
   rebasing 2:b18e25de2cf5 "D" (D)
   note: not rebasing 3:7fb047a69f22 "E" (E), already in destination as 1:112478962961 "B"
   rebasing 5:66f1a38021c9 "F" (F tip)
+  note: rebase of 5:66f1a38021c9 created no changes to commit
   $ hg log -G
-  o  7:9ed45af61fa0 F
-  |
   o  6:8f47515dda15 D
   |
   | x    5:66f1a38021c9 F
@@ -1096,13 +1123,14 @@
   note: not rebasing 2:b18e25de2cf5 "D" (D), already in destination as 1:112478962961 "B"
   rebasing 3:7fb047a69f22 "E" (E)
   rebasing 5:66f1a38021c9 "F" (F tip)
-BROKEN: This should have resulted in a rebased F with one parent, just like in
-the test case above
+
+Rebased F should have one parent, just like in the test case above
+
   $ hg log -G
-  o    7:c1e6f26e339d F
-  |\
-  | o  6:533690786a86 E
-  |/
+  o  7:502540f44880 F
+  |
+  o  6:533690786a86 E
+  |
   | x    5:66f1a38021c9 F
   | |\
   o | |  4:26805aba1e60 C