[PATCH 2 of 2 v5] revlog: remove revlog.reachable()

Joshua Redstone joshua.redstone at fb.com
Tue Jun 5 15:38:50 CDT 2012


# HG changeset patch
# User Joshua Redstone <joshua.redstone at fb.com>
# Date 1338566177 25200
# Node ID 2054d1d0bae3374010c4280d3abb1184c86d793a
# Parent  d566aa319d5f7c58c69b985b53ff7498f08e53c6
revlog: remove revlog.reachable()

Replace few remaining uses of revlog.reachable with revlog.ancestors.
One subtlety is that reachable(n) includes n while ancestors(n) does not.

This also fixes a small performance bug in localrepo._updatebranchcache.  That
function would iterate over new candidate heads in order from oldest to newest,
in contrast to the comment that observes that iterating from newest to oldest
results in fewer pases over the set of reachable nodes.

diff -r d566aa319d5f -r 2054d1d0bae3 hgext/transplant.py
--- a/hgext/transplant.py	Mon Jun 04 17:57:57 2012 -0500
+++ b/hgext/transplant.py	Fri Jun 01 08:56:17 2012 -0700
@@ -88,17 +88,23 @@
         self.editor = None
 
     def applied(self, repo, node, parent):
-        '''returns True if a node is already an ancestor of parent
-        or has already been transplanted'''
+        '''returns True if a node is already an ancestor of parent,
+        including parent, or has already been transplanted'''
+        if hasnode(repo, parent):
+            parentrev = repo.changelog.rev(parent)
         if hasnode(repo, node):
-            if node in repo.changelog.reachable(parent, stop=node):
+            stoprev = repo.changelog.rev(node)
+            if stoprev == parentrev or \
+                    stoprev in repo.changelog.ancestors([parentrev], stoprev):
                 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):
+            lnoderev = repo.changelog.rev(t.lnode)
+            if lnoderev == parentrev or \
+                    lnoderev in repo.changelog.ancestors([parentrev], lnoderev):
                 return True
         return False
 
diff -r d566aa319d5f -r 2054d1d0bae3 mercurial/discovery.py
--- a/mercurial/discovery.py	Mon Jun 04 17:57:57 2012 -0500
+++ b/mercurial/discovery.py	Fri Jun 01 08:56:17 2012 -0700
@@ -208,17 +208,19 @@
         # Construct {old,new}map with branch = None (topological branch).
         # (code based on _updatebranchcache)
         oldheads = set(h for h in remoteheads if h in cl.nodemap)
-        newheads = oldheads.union(outgoing.missing)
-        if len(newheads) > 1:
-            for latest in reversed(outgoing.missing):
-                if latest not in newheads:
+        oldheadrevs = set([cl.rev(node) for node in oldheads])
+        missingrevs = [cl.rev(node) for node in outgoing.missing]
+        newheadrevs = oldheadrevs.union(missingrevs)
+        if len(newheadrevs) > 1:
+            missingrevs.sort(reverse=True)
+            for latest in missingrevs:
+                if latest not in newheadrevs:
                     continue
-                minhrev = min(cl.rev(h) for h in newheads)
-                reachable = cl.reachable(latest, cl.node(minhrev))
-                reachable.remove(latest)
-                newheads.difference_update(reachable)
+                minhrev = min(newheadsrevs)
+                reachable = set(cl.ancestors([latest], minhrev))
+                newheadrevs.difference_update(reachable)
         branches = set([None])
-        newmap = {None: newheads}
+        newmap = {None: [cl.node(rev) for rev in newheadrevs]}
         oldmap = {None: oldheads}
         unsynced = inc and branches or set()
 
diff -r d566aa319d5f -r 2054d1d0bae3 mercurial/localrepo.py
--- a/mercurial/localrepo.py	Mon Jun 04 17:57:57 2012 -0500
+++ b/mercurial/localrepo.py	Fri Jun 01 08:56:17 2012 -0700
@@ -574,27 +574,26 @@
         # collect new branch entries
         newbranches = {}
         for c in ctxgen:
-            newbranches.setdefault(c.branch(), []).append(c.node())
+            newbranches.setdefault(c.branch(), []).append(c.rev())
         # if older branchheads are reachable from new ones, they aren't
         # really branchheads. Note checking parents is insufficient:
         # 1 (branch a) -> 2 (branch b) -> 3 (branch a)
-        for branch, newnodes in newbranches.iteritems():
-            bheads = partial.setdefault(branch, [])
-            bheads.extend(newnodes)
-            if len(bheads) <= 1:
-                continue
-            bheads = sorted(bheads, key=lambda x: self[x].rev())
+        for branch, newrevs in newbranches.iteritems():
+            bheadrevs = [self.changelog.rev(node) for node in
+                         partial.setdefault(branch, [])]
+            bheadrevs.extend(newrevs)
+            bheadrevs.sort()
             # starting from tip means fewer passes over reachable
-            while newnodes:
-                latest = newnodes.pop()
-                if latest not in bheads:
+            newrevs.sort(reverse=True)
+            while newrevs:
+                latest = newrevs.pop()
+                if latest not in bheadrevs:
                     continue
-                minbhnode = self[bheads[0]].node()
-                reachable = self.changelog.reachable(latest, minbhnode)
-                reachable.remove(latest)
-                if reachable:
-                    bheads = [b for b in bheads if b not in reachable]
-            partial[branch] = bheads
+                ancestors = set(self.changelog.ancestors([latest],
+                                                         bheadrevs[0]))
+                if ancestors:
+                    bheadrevs = [b for b in bheadrevs if b not in ancestors]
+            partial[branch] = [self.changelog.node(rev) for rev in bheadrevs]
 
     def lookup(self, key):
         return self[key].node()
diff -r d566aa319d5f -r 2054d1d0bae3 mercurial/revlog.py
--- a/mercurial/revlog.py	Mon Jun 04 17:57:57 2012 -0500
+++ b/mercurial/revlog.py	Fri Jun 01 08:56:17 2012 -0700
@@ -358,29 +358,6 @@
         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.


More information about the Mercurial-devel mailing list