diff --git a/hgext/patchbomb.py b/hgext/patchbomb.py
--- a/hgext/patchbomb.py
+++ b/hgext/patchbomb.py
@@ -238,15 +238,14 @@ def patchbomb(ui, repo, *revs, **opts):
         dest = ui.expandpath(dest or 'default-push', dest or 'default')
         dest, branches = hg.parseurl(dest)
         revs, checkout = hg.addbranchrevs(repo, repo, branches, revs)
-        if revs:
-            revs = [repo.lookup(rev) for rev in revs]
         other = hg.repository(hg.remoteui(repo, opts), dest)
         ui.status(_('comparing with %s\n') % url.hidepassword(dest))
-        o = discovery.findoutgoing(repo, other)
+        common, _anyinc, _heads = discovery.findcommonincoming(repo, other)
+        nodes = revs and map(repo.lookup, revs) or revs
+        o = repo.changelog.findmissing(common, heads=nodes)
         if not o:
             ui.status(_("no changes found\n"))
             return []
-        o = repo.changelog.nodesbetween(o, revs)[0]
         return [str(repo.changelog.rev(r)) for r in o]
 
     def getpatches(revs):
diff --git a/hgext/transplant.py b/hgext/transplant.py
--- a/hgext/transplant.py
+++ b/hgext/transplant.py
@@ -494,10 +494,10 @@ def transplant(ui, repo, *revs, **opts):
     and then resume where you left off by calling :hg:`transplant
     --continue/-c`.
     '''
-    def incwalk(repo, incoming, branches, match=util.always):
+    def incwalk(repo, commmon, branches, match=util.always):
         if not branches:
             branches = None
-        for node in repo.changelog.nodesbetween(incoming, branches)[0]:
+        for node in repo.changelog.findmissing(common, branches):
             if match(node):
                 yield node
 
@@ -552,8 +552,8 @@ def transplant(ui, repo, *revs, **opts):
     if source:
         sourcerepo = ui.expandpath(source)
         source = hg.repository(ui, sourcerepo)
-        source, common, incoming, bundle = bundlerepo.getremotechanges(ui, repo,
-                                            source, force=True)
+        source, common, anyinc, bundle = bundlerepo.getremotechanges(ui, repo,
+                                          source, force=True)
     else:
         source = repo
 
@@ -577,7 +577,7 @@ def transplant(ui, repo, *revs, **opts):
                 revmap[int(r)] = source.lookup(r)
         elif opts.get('all') or not merges:
             if source != repo:
-                alltransplants = incwalk(source, incoming, branches,
+                alltransplants = incwalk(source, common, branches,
                                          match=matchfn)
             else:
                 alltransplants = transplantwalk(source, p1, branches,
diff --git a/mercurial/bundlerepo.py b/mercurial/bundlerepo.py
--- a/mercurial/bundlerepo.py
+++ b/mercurial/bundlerepo.py
@@ -287,9 +287,8 @@ def instance(ui, path, create):
     return bundlerepository(ui, repopath, bundlename)
 
 def getremotechanges(ui, repo, other, revs=None, bundlename=None,
-                     force=False, usecommon=False):
-    tmp = discovery.findcommonincoming(repo, other, heads=revs, force=force,
-                                       commononly=usecommon)
+                     force=False):
+    tmp = discovery.findcommonincoming(repo, other, heads=revs, force=force)
     common, incoming, rheads = tmp
     if not incoming:
         try:
@@ -305,7 +304,7 @@ def getremotechanges(ui, repo, other, re
         if revs is None and other.capable('changegroupsubset'):
             revs = rheads
 
-        if usecommon:
+        if other.capable('getbundle'):
             cg = other.getbundle('incoming', common=common, heads=revs)
         elif revs is None:
             cg = other.changegroup(incoming, "incoming")
diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -696,49 +696,21 @@ def bundle(ui, repo, fname, dest=None, *
         if dest:
             raise util.Abort(_("--base is incompatible with specifying "
                                "a destination"))
-        base = [repo.lookup(rev) for rev in base]
-        # create the right base
-        # XXX: nodesbetween / changegroup* should be "fixed" instead
-        o = []
-        has = set((nullid,))
-        for n in base:
-            has.update(repo.changelog.reachable(n))
-        if revs:
-            revs = [repo.lookup(rev) for rev in revs]
-            visit = revs[:]
-            has.difference_update(visit)
-        else:
-            visit = repo.changelog.heads()
-        seen = {}
-        while visit:
-            n = visit.pop(0)
-            parents = [p for p in repo.changelog.parents(n) if p not in has]
-            if len(parents) == 0:
-                if n not in has:
-                    o.append(n)
-            else:
-                for p in parents:
-                    if p not in seen:
-                        seen[p] = 1
-                        visit.append(p)
+        common = [repo.lookup(rev) for rev in base]
     else:
         dest = ui.expandpath(dest or 'default-push', dest or 'default')
         dest, branches = hg.parseurl(dest, opts.get('branch'))
         other = hg.repository(hg.remoteui(repo, opts), dest)
         revs, checkout = hg.addbranchrevs(repo, other, branches, revs)
-        if revs:
-            revs = [repo.lookup(rev) for rev in revs]
-        o = discovery.findoutgoing(repo, other, force=opts.get('force'))
-
-    if not o:
+        inc = discovery.findcommonincoming(repo, other, force=opts.get('force'))
+        common, _anyinc, _heads = inc
+
+    nodes = revs and map(repo.lookup, revs) or revs
+    cg = repo.getbundle('bundle', common=common, heads=nodes)
+    if not cg:
         ui.status(_("no changes found\n"))
         return 1
 
-    if revs:
-        cg = repo.changegroupsubset(o, revs, 'bundle')
-    else:
-        cg = repo.changegroup(o, 'bundle')
-
     bundletype = opts.get('type', 'bzip2').lower()
     btypes = {'none': 'HG10UN', 'bzip2': 'HG10BZ', 'gzip': 'HG10GZ'}
     bundletype = btypes.get(bundletype)
@@ -3959,9 +3931,9 @@ def summary(ui, repo, **opts):
         other = hg.repository(hg.remoteui(repo, {}), dest)
         ui.debug('comparing with %s\n' % url.hidepassword(dest))
         repo.ui.pushbuffer()
-        o = discovery.findoutgoing(repo, other)
+        common, _anyinc, _heads = discovery.findcommonincoming(repo, other)
         repo.ui.popbuffer()
-        o = repo.changelog.nodesbetween(o, None)[0]
+        o = repo.changelog.findmissing(common=common)
         if o:
             t.append(_('%d outgoing') % len(o))
         if 'bookmarks' in other.listkeys('namespaces'):
diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -9,14 +9,19 @@ from node import nullid, short
 from i18n import _
 import util, error
 
-def findcommonincoming(repo, remote, heads=None, force=False, commononly=False):
-    """Return a tuple (common, missing, heads) used to identify missing nodes
-    from remote. "missing" is either a boolean indicating if any nodes are missing
-    (when commononly=True), or else a list of the root nodes of the missing set.
+def findcommonincoming(repo, remote, heads=None, force=False):
+    """Return a tuple (common, anyincoming, heads) used to identify the common
+    subset of nodes between repo and remote.
 
-    If a list of heads is specified, return only nodes which are heads
-    or ancestors of these heads.
+    "common" is a list of (at least) the heads of the common subset.
+    "anyincoming" is testable as a boolean indicating if any nodes are missing
+      locally. If remote does not support getbundle, this actually is a list of
+      roots of the nodes that would be incoming, to be supplied to
+      changegroupsubset. No code except for pull should be relying on this fact
+      any longer.
+    "heads" is either the supplied heads, or else the remote's heads.
     """
+
     m = repo.changelog.nodemap
     search = []
     fetch = set()
@@ -37,7 +42,7 @@ def findcommonincoming(repo, remote, hea
     # and start by examining the heads
     repo.ui.status(_("searching for changes\n"))
 
-    if commononly:
+    if remote.capable('getbundle'):
         myheads = repo.heads()
         known = remote.known(myheads)
         if util.all(known):
@@ -155,45 +160,6 @@ def findcommonincoming(repo, remote, hea
 
     return base, list(fetch), heads
 
-def findoutgoing(repo, remote, base=None, remoteheads=None, force=False):
-    """Return list of nodes that are roots of subsets not in remote
-
-    If base dict is specified, assume that these nodes and their parents
-    exist on the remote side.
-    If remotehead is specified, assume it is the list of the heads from
-    the remote repository.
-    """
-    if base is None:
-        base = findcommonincoming(repo, remote, heads=remoteheads,
-                                  force=force)[0]
-    else:
-        base = list(base)
-
-    repo.ui.debug("common changesets up to "
-                  + " ".join(map(short, base)) + "\n")
-
-    remain = set(repo.changelog.nodemap)
-
-    # prune everything remote has from the tree
-    remain.remove(nullid)
-    remove = base
-    while remove:
-        n = remove.pop(0)
-        if n in remain:
-            remain.remove(n)
-            for p in repo.changelog.parents(n):
-                remove.append(p)
-
-    # find every node whose parents have been pruned
-    subset = []
-    # find every remote head that will get new children
-    for n in remain:
-        p1, p2 = repo.changelog.parents(n)
-        if p1 not in remain and p2 not in remain:
-            subset.append(n)
-
-    return subset
-
 def prepush(repo, remote, force, revs, newbranch):
     '''Analyze the local and remote repositories and determine which
     changesets need to be pushed to the remote. Return value depends
@@ -209,14 +175,13 @@ def prepush(repo, remote, force, revs, n
     successive changegroup chunks ready to be sent over the wire and
     remoteheads is the list of remote heads.'''
     remoteheads = remote.heads()
-    common, inc, rheads = findcommonincoming(repo, remote, heads=remoteheads,
-                                             force=force)
+    common, inc, _rheads = findcommonincoming(repo, remote, heads=remoteheads,
+                                              force=force)
 
     cl = repo.changelog
-    update = findoutgoing(repo, remote, common, remoteheads)
-    outg, bases, heads = cl.nodesbetween(update, revs)
+    outg = cl.findmissing(common, revs)
 
-    if not bases:
+    if not outg:
         repo.ui.status(_("no changes found\n"))
         return None, 1
 
@@ -317,8 +282,7 @@ def prepush(repo, remote, force, revs, n
 
     if revs is None:
         # use the fast path, no race possible on push
-        nodes = repo.changelog.findmissing(common)
-        cg = repo._changegroup(nodes, 'push')
+        cg = repo._changegroup(outg, 'push')
     else:
-        cg = repo.changegroupsubset(update, revs, 'push')
+        cg = repo.getbundle('push', heads=revs, common=common)
     return cg, remoteheads
diff --git a/mercurial/hg.py b/mercurial/hg.py
--- a/mercurial/hg.py
+++ b/mercurial/hg.py
@@ -426,19 +426,14 @@ def _incoming(displaychlist, subreporecu
 
     if revs:
         revs = [other.lookup(rev) for rev in revs]
-    usecommon = other.capable('getbundle')
-    other, common, incoming, bundle = bundlerepo.getremotechanges(ui, repo, other,
-                                       revs, opts["bundle"], opts["force"],
-                                       usecommon=usecommon)
-    if not incoming:
+    other, common, anyinc, bundle = bundlerepo.getremotechanges(ui, repo, other,
+                                     revs, opts["bundle"], opts["force"])
+    if not anyinc:
         ui.status(_("no changes found\n"))
         return subreporecurse()
 
     try:
-        if usecommon:
-            chlist = other.changelog.findmissing(common, revs)
-        else:
-            chlist = other.changelog.nodesbetween(incoming, revs)[0]
+        chlist = other.changelog.findmissing(common, revs)
         displayer = cmdutil.show_changeset(ui, other, opts, buffered)
 
         # XXX once graphlog extension makes it into core,
@@ -488,12 +483,13 @@ def _outgoing(ui, repo, dest, opts):
         revs = [repo.lookup(rev) for rev in revs]
 
     other = repository(remoteui(repo, opts), dest)
-    o = discovery.findoutgoing(repo, other, force=opts.get('force'))
+    inc = discovery.findcommonincoming(repo, other, force=opts.get('force'))
+    common, _anyinc, _heads = inc
+    o = repo.changelog.findmissing(common, revs)
     if not o:
         ui.status(_("no changes found\n"))
         return None
-
-    return repo.changelog.nodesbetween(o, revs)[0]
+    return o
 
 def outgoing(ui, repo, dest, opts):
     def recurse():
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -1327,9 +1327,8 @@ class localrepository(repo.repository):
     def pull(self, remote, heads=None, force=False):
         lock = self.lock()
         try:
-            usecommon = remote.capable('getbundle')
             tmp = discovery.findcommonincoming(self, remote, heads=heads,
-                                               force=force, commononly=usecommon)
+                                               force=force)
             common, fetch, rheads = tmp
             if not fetch:
                 self.ui.status(_("no changes found\n"))
@@ -1341,7 +1340,7 @@ class localrepository(repo.repository):
                     # issue1320, avoid a race if remote changed after discovery
                     heads = rheads
 
-                if usecommon:
+                if remote.capable('getbundle'):
                     cg = remote.getbundle('pull', common=common,
                                           heads=heads or rheads)
                 elif heads is None:
@@ -1475,6 +1474,8 @@ class localrepository(repo.repository):
         if not heads:
             heads = cl.heads()
         common, missing = cl.findcommonmissing(common, heads)
+        if not missing:
+            return None
         return self._changegroupsubset(common, missing, heads, source)
 
     def _changegroupsubset(self, commonrevs, csets, heads, source):
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -554,10 +554,10 @@ def outgoing(repo, subset, x):
         revs = [repo.lookup(rev) for rev in revs]
     other = hg.repository(hg.remoteui(repo, {}), dest)
     repo.ui.pushbuffer()
-    o = discovery.findoutgoing(repo, other)
+    common, _anyinc, _heads = discovery.findcommonincoming(repo, other)
     repo.ui.popbuffer()
     cl = repo.changelog
-    o = set([cl.rev(r) for r in repo.changelog.nodesbetween(o, revs)[0]])
+    o = set([cl.rev(r) for r in repo.changelog.findmissing(common, revs)])
     return [r for r in subset if r in o]
 
 def p1(repo, subset, x):
diff --git a/tests/test-acl.t b/tests/test-acl.t
--- a/tests/test-acl.t
+++ b/tests/test-acl.t
@@ -83,7 +83,6 @@ Extension disabled for lack of a hook
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -137,7 +136,6 @@ Extension disabled for lack of acl.sourc
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   invalidating branch cache (tip differs)
   3 changesets found
   list of changesets:
@@ -195,7 +193,6 @@ No [acl.allow]/[acl.deny]
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   invalidating branch cache (tip differs)
   3 changesets found
   list of changesets:
@@ -262,7 +259,6 @@ Empty [acl.allow]
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   invalidating branch cache (tip differs)
   3 changesets found
   list of changesets:
@@ -327,7 +323,6 @@ fred is allowed inside foo/
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -396,7 +391,6 @@ Empty [acl.deny]
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -462,7 +456,6 @@ fred is allowed inside foo/, but not foo
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -533,7 +526,6 @@ fred is allowed inside foo/, but not foo
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -601,7 +593,6 @@ fred is allowed inside foo/, but not foo
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -671,7 +662,6 @@ barney is allowed everywhere
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -744,7 +734,6 @@ wilma can change files with a .txt exten
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   invalidating branch cache (tip differs)
   3 changesets found
   list of changesets:
@@ -822,7 +811,6 @@ file specified by acl.config does not ex
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -893,7 +881,6 @@ betty is allowed inside foo/ by a acl.co
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -976,7 +963,6 @@ acl.config can set only [acl.allow]/[acl
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -1050,7 +1036,6 @@ fred is always allowed
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   invalidating branch cache (tip differs)
   3 changesets found
   list of changesets:
@@ -1121,7 +1106,6 @@ no one is allowed inside foo/Bar/
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   invalidating branch cache (tip differs)
   3 changesets found
   list of changesets:
@@ -1195,7 +1179,6 @@ OS-level groups
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   3 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -1266,7 +1249,6 @@ OS-level groups
   """
   pushing to ../b
   searching for changes
-  common changesets up to 6675d58eff77
   invalidating branch cache (tip differs)
   3 changesets found
   list of changesets:
@@ -1378,7 +1360,6 @@ No branch acls specified
   """
   pushing to ../b
   searching for changes
-  common changesets up to 07e028174695
   4 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -1456,7 +1437,6 @@ Branch acl deny test
   """
   pushing to ../b
   searching for changes
-  common changesets up to 07e028174695
   invalidating branch cache (tip differs)
   4 changesets found
   list of changesets:
@@ -1533,7 +1513,6 @@ Branch acl empty allow test
   """
   pushing to ../b
   searching for changes
-  common changesets up to 07e028174695
   4 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -1605,7 +1584,6 @@ Branch acl allow other
   """
   pushing to ../b
   searching for changes
-  common changesets up to 07e028174695
   4 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -1671,7 +1649,6 @@ Branch acl allow other
   """
   pushing to ../b
   searching for changes
-  common changesets up to 07e028174695
   4 changesets found
   list of changesets:
   ef1ea85a6374b77d6da9dcda9541f498f2d17df7
@@ -1754,7 +1731,6 @@ push foobar into the remote
   """
   pushing to ../b
   searching for changes
-  common changesets up to 07e028174695
   invalidating branch cache (tip differs)
   4 changesets found
   list of changesets:
@@ -1837,7 +1813,6 @@ Branch acl conflicting deny
   """
   pushing to ../b
   searching for changes
-  common changesets up to 07e028174695
   invalidating branch cache (tip differs)
   4 changesets found
   list of changesets:
diff --git a/tests/test-bundle-r.t b/tests/test-bundle-r.t
--- a/tests/test-bundle-r.t
+++ b/tests/test-bundle-r.t
@@ -231,7 +231,8 @@ empty bundle
 issue76 msg2163
 
   $ hg -R test bundle --base 3 -r 3 -r 3 test-bundle-cset-3.hg
-  1 changesets found
+  no changes found
+  [1]
 
 Issue1910: 'hg bundle --base $head' does not exclude $head from
 result
diff --git a/tests/test-bundle.t b/tests/test-bundle.t
--- a/tests/test-bundle.t
+++ b/tests/test-bundle.t
@@ -562,7 +562,6 @@ bundle single branch
 
   $ hg bundle bundle.hg part --debug
   searching for changes
-  common changesets up to c0025332f9ed
   2 changesets found
   list of changesets:
   d2ae7f538514cd87c17547b0de4cea71fe1af9fb
diff --git a/tests/test-push-warn.t b/tests/test-push-warn.t
--- a/tests/test-push-warn.t
+++ b/tests/test-push-warn.t
@@ -39,7 +39,6 @@
   found new branch changeset 1c9246a22a0a
   found new changesets starting at 1c9246a22a0a
   1 total queries
-  common changesets up to d8d565842d04
   new remote heads on branch 'default'
   new remote head 1e108cc5548c
   abort: push creates new remote heads on branch 'default'!