[PATCH 3 of 6] revset: implement precomputed revset functions

[Patrick Mezard]

# HG changeset patch
# User Patrick Mezard <patrick at mezard.eu>
# Date 1336509824 -7200
# Node ID dbeeb20515c9b9225f74fc8491d516a7b6b2f48a
# Parent  53db775e252c0f4f7add32b62e08096814d3ab7e
revset: implement precomputed revset functions

Calling revset matchers more than once works correctly but could be
inefficient when the revset functions have to generate expensive data
structures before starting to filter input revisions, the structures
being recreated at each call. A precomputed() decorator is introduced,
marking functions as returning filtering closures rather than filtering
directly. Unfortunately, the expression tree is made of tuples which
cannot be extended to preserve state. The preparetree() function
traverses the expression tree and replaces ('func', fname, ...) tuples
with funcobj objects, extending tuple, and able to handle the
@precomputed functions. All this is applied to _ancestors() as an
example.

The goal is to turn all functions used by graphlog.getlogrevs() into
precomputed ones.

On mozilla repository:

                         first line    total
  * hg log --follow -r 90000:80000
  2.2                        0.127s   1.667s
  before                     0.366s   6.139s
  after                      0.375s   1.783s

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -47,6 +47,40 @@
                 yield i
                 break
 
+def precomputed(func):
+    """Decorator marking a revset function as precomputed
+
+    Instead of returning a list of revisions, the function returns a
+    closure doing so, usually to preserve expensive state between
+    calls. This is useful when revset matchers are being called
+    repeatedly instead of once.
+    """
+    func.precomputed = True
+    return func
+
+class funcobj(tuple):
+    """Replace ('func', 'name', ...) tuples in the expression tree.
+
+    funcobj preserves state between calls to an existing revset tree,
+    like revset function precomputed data.
+    """
+    iscallable = True
+
+    def __init__(self, *args, **kwargs):
+        super(funcobj, self).__init__(*args, **kwargs)
+        self.fn = None
+
+    def __call__(self, repo, subset, a, b):
+        if a[0] == 'symbol' and a[1] in symbols:
+            fn = symbols[a[1]]
+            if self.fn is None:
+                if getattr(fn, 'precomputed', False):
+                    self.fn = fn(repo, subset, b)
+                else:
+                    self.fn = fn
+            return self.fn(repo, subset, b)
+        raise error.ParseError(_("not a function: %s") % a[1])
+
 elements = {
     "(": (20, ("group", 1, ")"), ("func", 1, ")")),
     "~": (18, None, ("ancestor", 18)),
@@ -153,6 +187,8 @@
 def getset(repo, subset, x):
     if not x:
         raise error.ParseError(_("missing argument"))
+    if getattr(x, 'iscallable', False):
+        return x(repo, subset, *x[1:])
     return methods[x[0]](repo, subset, *x[1:])
 
 # operator methods
@@ -237,19 +273,27 @@
 
     return [r for r in an if r in subset]
 
+ at precomputed
 def _ancestors(repo, subset, x, followfirst=False):
     args = getset(repo, range(len(repo)), x)
-    if not args:
-        return []
-    s = set(_revancestors(repo, args, followfirst)) | set(args)
-    return [r for r in subset if r in s]
+    s = set()
+    if args:
+        s = set(_revancestors(repo, args, followfirst)) | set(args)
 
+    def fn(repo, subset, x):
+        if not s:
+            return []
+        return [r for r in subset if r in s]
+    return fn
+
+ at precomputed
 def ancestors(repo, subset, x):
     """``ancestors(set)``
     Changesets that are ancestors of a changeset in set.
     """
     return _ancestors(repo, subset, x)
 
+ at precomputed
 def _firstancestors(repo, subset, x):
     # ``_firstancestors(set)``
     # Like ``ancestors(set)`` but follows only the first parents.
@@ -1369,6 +1413,14 @@
 
 parse = parser.parser(tokenize, elements).parse
 
+def preparetree(tree):
+    if isinstance(tree, tuple):
+        kind = tuple
+        if tree and tree[0] == 'func':
+            kind = funcobj
+        return kind(preparetree(e) for e in tree)
+    return tree
+
 def match(ui, spec):
     if not spec:
         raise error.ParseError(_("empty query"))
@@ -1378,6 +1430,7 @@
     if ui:
         tree = findaliases(ui, tree)
     weight, tree = optimize(tree, True)
+    tree = preparetree(tree)
     def mfunc(repo, subset):
         return getset(repo, subset, tree)
     return mfunc