diff -r 0a853dc9b306 -r 8ec5478aa0d6 hgext/histedit.py
--- a/hgext/histedit.py	Wed Feb 24 18:42:59 2016 +0000
+++ b/hgext/histedit.py	Wed Feb 24 16:58:07 2016 +0100
@@ -1397,6 +1397,8 @@
         return oldreplacements
 
     unfi = repo.unfiltered()
+    nm = unfi.changelog.nodemap
+    obsstore = repo.obsstore
     newreplacements = list(oldreplacements)
     oldsuccs = [r[1] for r in oldreplacements]
     # successors that have already been added to succstocheck once
@@ -1404,15 +1406,13 @@
     succstocheck = list(seensuccs)
     while succstocheck:
         n = succstocheck.pop()
-        try:
-            ctx = unfi[n]
-        except error.RepoError:
-            # XXX node unknown locally, we should properly follow marker
+        missing = nm.get(n) is None
+        markers = obsstore.successors.get(n, ())
+        if missing and not markers:
+            # dead end, mark it as such
             newreplacements.append((n, ()))
-            continue
-
-        for marker in obsolete.successormarkers(ctx):
-            nsuccs = marker.succnodes()
+        for marker in markers:
+            nsuccs = marker[1]
             newreplacements.append((n, nsuccs))
             for nsucc in nsuccs:
                 if nsucc not in seensuccs: