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

login
register
mail settings
Submitter Yuya Nishihara
Date May 26, 2015, 3 p.m.
Message ID <3c41bb6a51f96c0e4409.1432652419@mimosa>
Download mbox | patch
Permalink /patch/9276/
State Superseded
Commit c87b05925054c7c13e1085f8dc346d6262f17747
Headers show

Comments

Yuya Nishihara - May 26, 2015, 3 p.m.
# HG changeset patch
# User Yuya Nishihara <yuya@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.
Matt Mackall - May 26, 2015, 4:17 p.m.
On Wed, 2015-05-27 at 00:00 +0900, Yuya Nishihara wrote:
> # HG changeset patch
> # User Yuya Nishihara <yuya@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.
> +    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))

Seems to me this is still going to recurse to a depth equal to the
length of the expression? Have you tested this against a really big
expression?
Yuya Nishihara - May 26, 2015, 10:48 p.m.
On Tue, 26 May 2015 11:17:48 -0500, Matt Mackall wrote:
> On Wed, 2015-05-27 at 00:00 +0900, Yuya Nishihara wrote:
> > # HG changeset patch
> > # User Yuya Nishihara <yuya@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.
> > +    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))
> 
> Seems to me this is still going to recurse to a depth equal to the
> length of the expression? Have you tested this against a really big
> expression?

It recurses to right-hand side, but not to left-hand side. I've tested
it with "1 + 2 + ... + 10000".

Patch

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')