[PATCH 3 of 5] parser: add helper function to test if pattern matches parsed tree

[Yuya Nishihara]

# HG changeset patch
# User Yuya Nishihara <yuya at tcha.org>
# Date 1455712269 -32400
#      Wed Feb 17 21:31:09 2016 +0900
# Node ID af0821ec50deb2b65db7e0fecef6b0d379256533
# Parent  937f5edf91058c63fafd981a59feaaaa98d21068
parser: add helper function to test if pattern matches parsed tree

This function will be used as follows:

  match('ancestors(_) and not ancestors(_)', x)

See the next patch for details.

diff --git a/mercurial/parser.py b/mercurial/parser.py
--- a/mercurial/parser.py
+++ b/mercurial/parser.py
@@ -312,6 +312,59 @@ def buildtree(template, placeholder, *re
         raise error.ProgrammingError('too many replacements')
     return r
 
+def _matchtree(pattern, tree, placeholder, incompletenodes, matches):
+    if pattern == tree:
+        return True
+    if not isinstance(pattern, tuple) or not isinstance(tree, tuple):
+        return False
+    if pattern == placeholder and tree[0] not in incompletenodes:
+        matches.append(tree)
+        return True
+    if len(pattern) != len(tree):
+        return False
+    return all(_matchtree(p, x, placeholder, incompletenodes, matches)
+               for p, x in zip(pattern, tree))
+
+def matchtree(pattern, tree, placeholder=None, incompletenodes=()):
+    """If a tree matches the pattern, return a list of the tree and nodes
+    matched with the placeholder; Otherwise None
+
+    >>> def f(pattern, tree):
+    ...     m = matchtree(pattern, tree, _, {'keyvalue', 'list'})
+    ...     if m:
+    ...         return m[1:]
+
+    >>> _ = ('symbol', '_')
+    >>> f(('func', ('symbol', 'ancestors'), _),
+    ...   ('func', ('symbol', 'ancestors'), ('symbol', '1')))
+    [('symbol', '1')]
+    >>> f(('func', ('symbol', 'ancestors'), _),
+    ...   ('func', ('symbol', 'ancestors'), None))
+    >>> f(('range', ('dagrange', _, _), _),
+    ...   ('range',
+    ...     ('dagrange', ('symbol', '1'), ('symbol', '2')),
+    ...     ('symbol', '3')))
+    [('symbol', '1'), ('symbol', '2'), ('symbol', '3')]
+
+    The placeholder does not match the specified incomplete nodes because
+    an incomplete node (e.g. argument list) cannot construct an expression.
+
+    >>> f(('func', ('symbol', 'ancestors'), _),
+    ...   ('func', ('symbol', 'ancestors'),
+    ...     ('list', ('symbol', '1'), ('symbol', '2'))))
+
+    The placeholder may be omitted, but which shouldn't match a None node.
+
+    >>> _ = None
+    >>> f(('func', ('symbol', 'ancestors'), None),
+    ...   ('func', ('symbol', 'ancestors'), ('symbol', '0')))
+    """
+    if placeholder is not None and not isinstance(placeholder, tuple):
+        raise error.ProgrammingError('placeholder must be a node tuple')
+    matches = [tree]
+    if _matchtree(pattern, tree, placeholder, incompletenodes, matches):
+        return matches
+
 def parseerrordetail(inst):
     """Compose error message from specified ParseError object
     """