[PATCH 2 of 3 V2] revlog: switch findmissing to use ancestor.missingancestors, and add a revs variant

[Siddharth Agarwal]

# HG changeset patch
# User Siddharth Agarwal <sid0 at fb.com>
# Date 1353547305 28800
# Node ID 09b23b668aac8fa8a45e60a0c6dd0f9563ca1700
# Parent  562ed7c273988f91645be6189b51ab3119752c09
revlog: switch findmissing to use ancestor.missingancestors, and add a revs variant

This also speeds up other commands that use findmissing, like incoming and
merge --preview. With a large linear repository (>400000 commits) and with one
incoming changeset, incoming is sped up from around 4-4.5 seconds to under 3.

diff -r 562ed7c27398 -r 09b23b668aac mercurial/revlog.py
--- a/mercurial/revlog.py	Wed Nov 21 17:16:02 2012 -0800
+++ b/mercurial/revlog.py	Wed Nov 21 17:21:45 2012 -0800
@@ -430,6 +430,29 @@
         missing.sort()
         return has, [self.node(r) for r in missing]
 
+    def findmissingrevs(self, common=None, heads=None):
+        """Return the revision numbers of the ancestors of heads that
+        are not ancestors of common.
+
+        More specifically, return a list of revision numbers corresponding to
+        nodes N such that every N satisfies the following constraints:
+
+          1. N is an ancestor of some node in 'heads'
+          2. N is not an ancestor of any node in 'common'
+
+        The list is sorted by revision number, meaning it is
+        topologically sorted.
+
+        'heads' and 'common' are both lists of revision numbers.  If heads is
+        not supplied, uses all of the revlog's heads.  If common is not
+        supplied, uses nullid."""
+        if common is None:
+            common = [nullrev]
+        if heads is None:
+            heads = self.headrevs()
+
+        return ancestor.missingancestors(heads, common, self.parentrevs)
+
     def findmissing(self, common=None, heads=None):
         """Return the ancestors of heads that are not ancestors of common.
 
@@ -445,8 +468,15 @@
         'heads' and 'common' are both lists of node IDs.  If heads is
         not supplied, uses all of the revlog's heads.  If common is not
         supplied, uses nullid."""
-        _common, missing = self.findcommonmissing(common, heads)
-        return missing
+        if common is None:
+            common = [nullid]
+        if heads is None:
+            heads = self.heads()
+
+        common = [self.rev(n) for n in common]
+        heads = [self.rev(n) for n in heads]
+
+        return [self.node(r) for r in self.findmissingrevs(common, heads)]
 
     def nodesbetween(self, roots=None, heads=None):
         """Return a topological path from 'roots' to 'heads'.