[PATCH 1 of 4] parser: add helper to reduce nesting of chained infix operations

[Yuya Nishihara]

# HG changeset patch
# User Yuya Nishihara <yuya at tcha.org>
# Date 1430039123 -32400
#      Sun Apr 26 18:05:23 2015 +0900
# Node ID 3c41bb6a51f96c0e4409f6b21689f61c16e149b2
# Parent  e43162c556830f24e7de564786bded96fecdc947
parser: add helper to reduce nesting of chained infix operations

This will be used to avoid stack overflow caused by chained 'or' operations
in revset.

diff --git a/mercurial/parser.py b/mercurial/parser.py
--- a/mercurial/parser.py
+++ b/mercurial/parser.py
@@ -108,3 +108,79 @@ def prettyformat(tree, leafnodes):
     _prettyformat(tree, leafnodes, 0, lines)
     output = '\n'.join(('  ' * l + s) for l, s in lines)
     return output
+
+def simplifyinfixops(tree, targetnodes):
+    """Flatten chained infix operations to reduce usage of Python stack
+
+    >>> def f(tree):
+    ...     print prettyformat(simplifyinfixops(tree, ('or',)), ('symbol',))
+    >>> f(('or',
+    ...     ('or',
+    ...       ('symbol', '1'),
+    ...       ('symbol', '2')),
+    ...     ('symbol', '3')))
+    (or
+      ('symbol', '1')
+      ('symbol', '2')
+      ('symbol', '3'))
+    >>> f(('func',
+    ...     ('symbol', 'p1'),
+    ...     ('or',
+    ...       ('or',
+    ...         ('func',
+    ...           ('symbol', 'sort'),
+    ...           ('list',
+    ...             ('or',
+    ...               ('or',
+    ...                 ('symbol', '1'),
+    ...                 ('symbol', '2')),
+    ...               ('symbol', '3')),
+    ...             ('negate',
+    ...               ('symbol', 'rev')))),
+    ...         ('and',
+    ...           ('symbol', '4'),
+    ...           ('group',
+    ...             ('or',
+    ...               ('or',
+    ...                 ('symbol', '5'),
+    ...                 ('symbol', '6')),
+    ...               ('symbol', '7'))))),
+    ...       ('symbol', '8'))))
+    (func
+      ('symbol', 'p1')
+      (or
+        (func
+          ('symbol', 'sort')
+          (list
+            (or
+              ('symbol', '1')
+              ('symbol', '2')
+              ('symbol', '3'))
+            (negate
+              ('symbol', 'rev'))))
+        (and
+          ('symbol', '4')
+          (group
+            (or
+              ('symbol', '5')
+              ('symbol', '6')
+              ('symbol', '7'))))
+        ('symbol', '8')))
+    """
+    if not isinstance(tree, tuple):
+        return tree
+    op = tree[0]
+    if op not in targetnodes:
+        return (op,) + tuple(simplifyinfixops(x, targetnodes) for x in tree[1:])
+
+    # walk down left nodes taking each right node
+    # e.g. '1 + 2 + 3' -> (+ (+ 1 2) 3) -> (+ 1 2 3)
+    simplified = []
+    x = tree
+    while x[0] == op:
+        l, r = x[1:]
+        simplified.append(simplifyinfixops(r, targetnodes))
+        x = l
+    simplified.append(simplifyinfixops(x, targetnodes))
+    simplified.append(op)
+    return tuple(reversed(simplified))
diff --git a/tests/test-doctest.py b/tests/test-doctest.py
--- a/tests/test-doctest.py
+++ b/tests/test-doctest.py
@@ -21,6 +21,7 @@ testmod('mercurial.match')
 testmod('mercurial.minirst')
 testmod('mercurial.patch')
 testmod('mercurial.pathutil')
+testmod('mercurial.parser')
 testmod('mercurial.revset')
 testmod('mercurial.store')
 testmod('mercurial.subrepo')