Patchwork [1,of,4,V2] parser: add helper to reduce nesting of chained infix operations

login
register
mail settings
Submitter Yuya Nishihara
Date May 27, 2015, 3:14 p.m.
Message ID <ba1e7a39338b162c2f36.1432739662@mimosa>
Download mbox | patch
Permalink /patch/9294/
State Accepted
Headers show

Comments

Yuya Nishihara - May 27, 2015, 3:14 p.m.
# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1430039123 -32400
#      Sun Apr 26 18:05:23 2015 +0900
# Node ID ba1e7a39338b162c2f36f8a2a6be05a9c80fdde6
# Parent  6ac860f700b5cfeda232d5305963047696b869ca
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.

Patch

diff --git a/mercurial/parser.py b/mercurial/parser.py
--- a/mercurial/parser.py
+++ b/mercurial/parser.py
@@ -108,3 +108,80 @@  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. no recursion to left nodes
+    # because infix operators are left-associative, i.e. left tree is deep.
+    # 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')