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