diff --git a/hgext/transplant.py b/hgext/transplant.py
--- a/hgext/transplant.py
+++ b/hgext/transplant.py
@@ -91,14 +91,22 @@ class transplanter(object):
         '''returns True if a node is already an ancestor of parent
         or has already been transplanted'''
         if hasnode(repo, node):
-            if node in repo.changelog.reachable(parent, stop=node):
+            reachablerevs = repo.changelog.incancestors(
+                [repo.changelog.rev(parent)],
+                stoprev=repo.changelog.rev(node))
+            reachable = (repo.changelog.node(rev) for rev in reachablerevs)
+            if node in reachable:
                 return True
         for t in self.transplants.get(node):
             # it might have been stripped
             if not hasnode(repo, t.lnode):
                 self.transplants.remove(t)
                 return False
-            if t.lnode in repo.changelog.reachable(parent, stop=t.lnode):
+            reachablerevs = repo.changelog.incancestors(
+                [repo.changelog.rev(parent)],
+                stoprev=repo.changelog.rev(t.lnode))
+            reachable = (repo.changelog.node(rev) for rev in reachablerevs)
+            if t.lnode in reachable:
                 return True
         return False
 
diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -214,8 +214,8 @@ def checkheads(repo, remote, outgoing, r
                 if latest not in newheads:
                     continue
                 minhrev = min(cl.rev(h) for h in newheads)
-                reachable = cl.reachable(latest, cl.node(minhrev))
-                reachable.remove(latest)
+                reachable = [cl.node(rev) for rev in
+                             cl.ancestors([cl.rev(latest)], minhrev)]
                 newheads.difference_update(reachable)
         branches = set([None])
         newmap = {None: newheads}
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -590,8 +590,10 @@ class localrepository(repo.repository):
                 if latest not in bheads:
                     continue
                 minbhnode = self[bheads[0]].node()
-                reachable = self.changelog.reachable(latest, minbhnode)
-                reachable.remove(latest)
+                cl = self.changelog
+                ancestors = cl.ancestors([cl.rev(latest)],
+                                          cl.rev(minbhnode))
+                reachable = [cl.node(rev) for rev in ancestors]
                 if reachable:
                     bheads = [b for b in bheads if b not in reachable]
             partial[branch] = bheads
diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -361,29 +361,6 @@ class revlog(object):
         return len(t)
     size = rawsize
 
-    def reachable(self, node, stop=None):
-        """return the set of all nodes ancestral to a given node, including
-         the node itself, stopping when stop is matched"""
-        reachable = set((node,))
-        visit = util.deque([node])
-        if stop:
-            stopn = self.rev(stop)
-        else:
-            stopn = 0
-        while visit:
-            n = visit.popleft()
-            if n == stop:
-                continue
-            if n == nullid:
-                continue
-            for p in self.parents(n):
-                if self.rev(p) < stopn:
-                    continue
-                if p not in reachable:
-                    reachable.add(p)
-                    visit.append(p)
-        return reachable
-
     def ancestors(self, revs, stoprev=0):
         """Generate the ancestors of 'revs' in reverse topological order.
         Does not generate revs lower than stoprev.