diff --git a/mercurial/branchmap.py b/mercurial/branchmap.py
--- a/mercurial/branchmap.py
+++ b/mercurial/branchmap.py
@@ -77,8 +77,7 @@ def updatecache(repo):
                 revs.extend(r for  r in extrarevs if r <= partial.tiprev)
     revs.extend(cl.revs(start=partial.tiprev + 1))
     if revs:
-        ctxgen = (repo[r] for r in revs)
-        partial.update(repo, ctxgen)
+        partial.update(repo, revs)
         partial.write(repo)
     assert partial.validfor(repo)
     repo._branchcaches[repo.filtername] = partial
@@ -144,12 +143,13 @@ class branchcache(dict):
             # Abort may be raise by read only opener
             pass
 
-    def update(self, repo, ctxgen):
+    def update(self, repo, revgen):
         """Given a branchhead cache, self, that may have extra nodes or be
         missing heads, and a generator of nodes that are at least a superset of
         heads missing, this function updates self to be correct.
         """
         cl = repo.changelog
+        ctxgen = (repo[r] for r in revgen)
         # collect new branch entries
         newbranches = {}
         for c in ctxgen:
diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -196,7 +196,7 @@ def _headssummary(repo, remote, outgoing
     newmap = branchmap.branchcache((branch, heads[1])
                                  for branch, heads in headssum.iteritems()
                                  if heads[0] is not None)
-    newmap.update(repo, missingctx)
+    newmap.update(repo, (ctx.rev() for ctx in missingctx))
     for branch, newheads in newmap.iteritems():
         headssum[branch][1][:] = newheads
     return headssum
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -1406,10 +1406,11 @@ class localrepository(object):
         # it, Otherwise, since nodes were destroyed, the cache is stale and this
         # will be caught the next time it is read.
         if newheadnodes:
-            ctxgen = (self[node] for node in newheadnodes
-                      if self.changelog.hasnode(node))
+            cl = self.changelog
+            revgen = (cl.rev(node) for node in newheadnodes
+                      if cl.hasnode(node))
             cache = self._branchcaches[None]
-            cache.update(self, ctxgen)
+            cache.update(self, revgen)
             cache.write(self)
 
         # Ensure the persistent tag cache is updated.  Doing it now