diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -128,8 +128,7 @@ def rebase(ui, repo, **opts):
 
         if not keepf:
             # Remove no more useful revisions
-            if (set(repo.changelog.descendants(min(state)))
-                                                    - set(state.keys())):
+            if set(repo.changelog.descendants(min(state))) - set(state):
                 ui.warn(_("warning: new changesets detected on source branch, "
                                                         "not stripping\n"))
             else:
diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -678,7 +678,7 @@ class revlog(object):
             # find from roots.
             heads = dict.fromkeys(heads, 0)
             # Start at the top and keep marking parents until we're done.
-            nodestotag = set(heads.keys())
+            nodestotag = set(heads)
             # Remember where the top was so we can use it as a limit later.
             highestrev = max([self.rev(n) for n in nodestotag])
             while nodestotag: