Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/parser.py @ 25801:272ff3680bf3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
parser: fill invalid infix and suffix actions by None This can simplify the expansion of (prefix, infix, suffix) actions.
author Yuya Nishihara <yuya@tcha.org>
date Sun, 05 Jul 2015 11:17:22 +0900
parents 48919d246a47
children cc741c76b26a
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
1 # parser.py - simple top-down operator precedence parser for mercurial
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
2 #
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
3 # Copyright 2010 Matt Mackall <mpm@selenic.com>
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
4 #
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
5 # This software may be used and distributed according to the terms of the
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
6 # GNU General Public License version 2 or any later version.
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
7
11449
05af334bac05 parser: fix URL to effbot
Julian Cowley <julian@lava.net>
parents: 11412
diff changeset
8 # see http://effbot.org/zone/simple-top-down-parsing.htm and
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
9 # http://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
10 # for background
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
11
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
12 # takes a tokenizer and elements
25655
b8b73652c1c9 parser: update documentation about tokenizer and elements
Yuya Nishihara <yuya@tcha.org>
parents: 25654
diff changeset
13 # tokenizer is an iterator that returns (type, value, pos) tuples
b8b73652c1c9 parser: update documentation about tokenizer and elements
Yuya Nishihara <yuya@tcha.org>
parents: 25654
diff changeset
14 # elements is a mapping of types to binding strength, prefix, infix and
25801
272ff3680bf3 parser: fill invalid infix and suffix actions by None
Yuya Nishihara <yuya@tcha.org>
parents: 25705
diff changeset
15 # suffix actions
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
16 # an action is a tree node name, a tree label, and an optional match
17500
8ac8db8dc346 en-us: labeled
timeless@mozdev.org
parents: 14701
diff changeset
17 # __call__(program) parses program into a labeled tree
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
18
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11278
diff changeset
19 import error
14701
4b93bd041772 parsers: fix localization markup of parser errors
Mads Kiilerich <mads@kiilerich.com>
parents: 13665
diff changeset
20 from i18n import _
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11278
diff changeset
21
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
22 class parser(object):
25654
af329a84310c parser: accept iterator of tokens instead of tokenizer function and program
Yuya Nishihara <yuya@tcha.org>
parents: 25306
diff changeset
23 def __init__(self, elements, methods=None):
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
24 self._elements = elements
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
25 self._methods = methods
13176
895f54a79c6e templater: use the parser.py parser to extend the templater syntax
Matt Mackall <mpm@selenic.com>
parents: 11449
diff changeset
26 self.current = None
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
27 def _advance(self):
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
28 'advance the tokenizer'
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
29 t = self.current
25171
d647f97f88dd parsers: use 'next' instead of try/except
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20778
diff changeset
30 self.current = next(self._iter, None)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
31 return t
11319
9d1cf337a78d parser: fix missing param in _match
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 11305
diff changeset
32 def _match(self, m, pos):
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
33 'make sure the tokenizer matches an end condition'
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
34 if self.current[0] != m:
14701
4b93bd041772 parsers: fix localization markup of parser errors
Mads Kiilerich <mads@kiilerich.com>
parents: 13665
diff changeset
35 raise error.ParseError(_("unexpected token: %s") % self.current[0],
11305
d4cafcb63f77 cleanups: undefined variables
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 11289
diff changeset
36 self.current[2])
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
37 self._advance()
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
38 def _parse(self, bind=0):
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11278
diff changeset
39 token, value, pos = self._advance()
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
40 # handle prefix rules on current token
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
41 prefix = self._elements[token][1]
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
42 if not prefix:
14701
4b93bd041772 parsers: fix localization markup of parser errors
Mads Kiilerich <mads@kiilerich.com>
parents: 13665
diff changeset
43 raise error.ParseError(_("not a prefix: %s") % token, pos)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
44 if len(prefix) == 1:
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
45 expr = (prefix[0], value)
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
46 else:
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
47 if len(prefix) > 2 and prefix[2] == self.current[0]:
11319
9d1cf337a78d parser: fix missing param in _match
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 11305
diff changeset
48 self._match(prefix[2], pos)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
49 expr = (prefix[0], None)
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
50 else:
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
51 expr = (prefix[0], self._parse(prefix[1]))
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
52 if len(prefix) > 2:
11319
9d1cf337a78d parser: fix missing param in _match
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 11305
diff changeset
53 self._match(prefix[2], pos)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
54 # gather tokens until we meet a lower binding strength
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
55 while bind < self._elements[self.current[0]][0]:
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11278
diff changeset
56 token, value, pos = self._advance()
25801
272ff3680bf3 parser: fill invalid infix and suffix actions by None
Yuya Nishihara <yuya@tcha.org>
parents: 25705
diff changeset
57 infix, suffix = self._elements[token][2:]
11278
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
58 # check for suffix - next token isn't a valid prefix
25801
272ff3680bf3 parser: fill invalid infix and suffix actions by None
Yuya Nishihara <yuya@tcha.org>
parents: 25705
diff changeset
59 if suffix and not self._elements[self.current[0]][1]:
11278
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
60 expr = (suffix[0], expr)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
61 else:
11278
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
62 # handle infix rules
25801
272ff3680bf3 parser: fill invalid infix and suffix actions by None
Yuya Nishihara <yuya@tcha.org>
parents: 25705
diff changeset
63 if not infix:
14701
4b93bd041772 parsers: fix localization markup of parser errors
Mads Kiilerich <mads@kiilerich.com>
parents: 13665
diff changeset
64 raise error.ParseError(_("not an infix: %s") % token, pos)
11278
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
65 if len(infix) == 3 and infix[2] == self.current[0]:
11319
9d1cf337a78d parser: fix missing param in _match
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 11305
diff changeset
66 self._match(infix[2], pos)
11278
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
67 expr = (infix[0], expr, (None))
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
68 else:
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
69 expr = (infix[0], expr, self._parse(infix[1]))
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
70 if len(infix) == 3:
11319
9d1cf337a78d parser: fix missing param in _match
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 11305
diff changeset
71 self._match(infix[2], pos)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
72 return expr
25654
af329a84310c parser: accept iterator of tokens instead of tokenizer function and program
Yuya Nishihara <yuya@tcha.org>
parents: 25306
diff changeset
73 def parse(self, tokeniter):
af329a84310c parser: accept iterator of tokens instead of tokenizer function and program
Yuya Nishihara <yuya@tcha.org>
parents: 25306
diff changeset
74 'generate a parse tree from tokens'
af329a84310c parser: accept iterator of tokens instead of tokenizer function and program
Yuya Nishihara <yuya@tcha.org>
parents: 25306
diff changeset
75 self._iter = tokeniter
13176
895f54a79c6e templater: use the parser.py parser to extend the templater syntax
Matt Mackall <mpm@selenic.com>
parents: 11449
diff changeset
76 self._advance()
13665
e798e430c5e5 revset: report a parse error if a revset is not parsed completely (issue2654)
Bernhard Leiner <bleiner@gmail.com>
parents: 13176
diff changeset
77 res = self._parse()
e798e430c5e5 revset: report a parse error if a revset is not parsed completely (issue2654)
Bernhard Leiner <bleiner@gmail.com>
parents: 13176
diff changeset
78 token, value, pos = self.current
e798e430c5e5 revset: report a parse error if a revset is not parsed completely (issue2654)
Bernhard Leiner <bleiner@gmail.com>
parents: 13176
diff changeset
79 return res, pos
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
80 def eval(self, tree):
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
81 'recursively evaluate a parse tree using node methods'
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
82 if not isinstance(tree, tuple):
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
83 return tree
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
84 return self._methods[tree[0]](*[self.eval(t) for t in tree[1:]])
25654
af329a84310c parser: accept iterator of tokens instead of tokenizer function and program
Yuya Nishihara <yuya@tcha.org>
parents: 25306
diff changeset
85 def __call__(self, tokeniter):
af329a84310c parser: accept iterator of tokens instead of tokenizer function and program
Yuya Nishihara <yuya@tcha.org>
parents: 25306
diff changeset
86 'parse tokens into a parse tree and evaluate if methods given'
af329a84310c parser: accept iterator of tokens instead of tokenizer function and program
Yuya Nishihara <yuya@tcha.org>
parents: 25306
diff changeset
87 t = self.parse(tokeniter)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
88 if self._methods:
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
89 return self.eval(t)
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
90 return t
25253
3f1a9b44b8c2 parser: move prettyformat() function from revset module
Yuya Nishihara <yuya@tcha.org>
parents: 25171
diff changeset
91
25705
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
92 def buildargsdict(trees, funcname, keys, keyvaluenode, keynode):
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
93 """Build dict from list containing positional and keyword arguments
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
94
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
95 Invalid keywords or too many positional arguments are rejected, but
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
96 missing arguments are just omitted.
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
97 """
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
98 if len(trees) > len(keys):
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
99 raise error.ParseError(_("%(func)s takes at most %(nargs)d arguments")
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
100 % {'func': funcname, 'nargs': len(keys)})
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
101 args = {}
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
102 # consume positional arguments
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
103 for k, x in zip(keys, trees):
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
104 if x[0] == keyvaluenode:
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
105 break
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
106 args[k] = x
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
107 # remainder should be keyword arguments
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
108 for x in trees[len(args):]:
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
109 if x[0] != keyvaluenode or x[1][0] != keynode:
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
110 raise error.ParseError(_("%(func)s got an invalid argument")
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
111 % {'func': funcname})
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
112 k = x[1][1]
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
113 if k not in keys:
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
114 raise error.ParseError(_("%(func)s got an unexpected keyword "
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
115 "argument '%(key)s'")
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
116 % {'func': funcname, 'key': k})
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
117 if k in args:
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
118 raise error.ParseError(_("%(func)s got multiple values for keyword "
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
119 "argument '%(key)s'")
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
120 % {'func': funcname, 'key': k})
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
121 args[k] = x[2]
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
122 return args
48919d246a47 revset: add function to build dict of positional and keyword arguments
Yuya Nishihara <yuya@tcha.org>
parents: 25655
diff changeset
123
25254
060bdfef2517 parser: extract closure of prettyformat() to a top-level function
Yuya Nishihara <yuya@tcha.org>
parents: 25253
diff changeset
124 def _prettyformat(tree, leafnodes, level, lines):
060bdfef2517 parser: extract closure of prettyformat() to a top-level function
Yuya Nishihara <yuya@tcha.org>
parents: 25253
diff changeset
125 if not isinstance(tree, tuple) or tree[0] in leafnodes:
060bdfef2517 parser: extract closure of prettyformat() to a top-level function
Yuya Nishihara <yuya@tcha.org>
parents: 25253
diff changeset
126 lines.append((level, str(tree)))
060bdfef2517 parser: extract closure of prettyformat() to a top-level function
Yuya Nishihara <yuya@tcha.org>
parents: 25253
diff changeset
127 else:
060bdfef2517 parser: extract closure of prettyformat() to a top-level function
Yuya Nishihara <yuya@tcha.org>
parents: 25253
diff changeset
128 lines.append((level, '(%s' % tree[0]))
060bdfef2517 parser: extract closure of prettyformat() to a top-level function
Yuya Nishihara <yuya@tcha.org>
parents: 25253
diff changeset
129 for s in tree[1:]:
060bdfef2517 parser: extract closure of prettyformat() to a top-level function
Yuya Nishihara <yuya@tcha.org>
parents: 25253
diff changeset
130 _prettyformat(s, leafnodes, level + 1, lines)
060bdfef2517 parser: extract closure of prettyformat() to a top-level function
Yuya Nishihara <yuya@tcha.org>
parents: 25253
diff changeset
131 lines[-1:] = [(lines[-1][0], lines[-1][1] + ')')]
060bdfef2517 parser: extract closure of prettyformat() to a top-level function
Yuya Nishihara <yuya@tcha.org>
parents: 25253
diff changeset
132
25253
3f1a9b44b8c2 parser: move prettyformat() function from revset module
Yuya Nishihara <yuya@tcha.org>
parents: 25171
diff changeset
133 def prettyformat(tree, leafnodes):
3f1a9b44b8c2 parser: move prettyformat() function from revset module
Yuya Nishihara <yuya@tcha.org>
parents: 25171
diff changeset
134 lines = []
25254
060bdfef2517 parser: extract closure of prettyformat() to a top-level function
Yuya Nishihara <yuya@tcha.org>
parents: 25253
diff changeset
135 _prettyformat(tree, leafnodes, 0, lines)
25253
3f1a9b44b8c2 parser: move prettyformat() function from revset module
Yuya Nishihara <yuya@tcha.org>
parents: 25171
diff changeset
136 output = '\n'.join((' ' * l + s) for l, s in lines)
3f1a9b44b8c2 parser: move prettyformat() function from revset module
Yuya Nishihara <yuya@tcha.org>
parents: 25171
diff changeset
137 return output
25306
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
138
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
139 def simplifyinfixops(tree, targetnodes):
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
140 """Flatten chained infix operations to reduce usage of Python stack
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
141
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
142 >>> def f(tree):
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
143 ... print prettyformat(simplifyinfixops(tree, ('or',)), ('symbol',))
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
144 >>> f(('or',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
145 ... ('or',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
146 ... ('symbol', '1'),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
147 ... ('symbol', '2')),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
148 ... ('symbol', '3')))
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
149 (or
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
150 ('symbol', '1')
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
151 ('symbol', '2')
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
152 ('symbol', '3'))
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
153 >>> f(('func',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
154 ... ('symbol', 'p1'),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
155 ... ('or',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
156 ... ('or',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
157 ... ('func',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
158 ... ('symbol', 'sort'),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
159 ... ('list',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
160 ... ('or',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
161 ... ('or',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
162 ... ('symbol', '1'),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
163 ... ('symbol', '2')),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
164 ... ('symbol', '3')),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
165 ... ('negate',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
166 ... ('symbol', 'rev')))),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
167 ... ('and',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
168 ... ('symbol', '4'),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
169 ... ('group',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
170 ... ('or',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
171 ... ('or',
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
172 ... ('symbol', '5'),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
173 ... ('symbol', '6')),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
174 ... ('symbol', '7'))))),
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
175 ... ('symbol', '8'))))
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
176 (func
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
177 ('symbol', 'p1')
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
178 (or
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
179 (func
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
180 ('symbol', 'sort')
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
181 (list
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
182 (or
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
183 ('symbol', '1')
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
184 ('symbol', '2')
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
185 ('symbol', '3'))
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
186 (negate
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
187 ('symbol', 'rev'))))
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
188 (and
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
189 ('symbol', '4')
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
190 (group
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
191 (or
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
192 ('symbol', '5')
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
193 ('symbol', '6')
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
194 ('symbol', '7'))))
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
195 ('symbol', '8')))
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
196 """
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
197 if not isinstance(tree, tuple):
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
198 return tree
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
199 op = tree[0]
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
200 if op not in targetnodes:
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
201 return (op,) + tuple(simplifyinfixops(x, targetnodes) for x in tree[1:])
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
202
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
203 # walk down left nodes taking each right node. no recursion to left nodes
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
204 # because infix operators are left-associative, i.e. left tree is deep.
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
205 # e.g. '1 + 2 + 3' -> (+ (+ 1 2) 3) -> (+ 1 2 3)
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
206 simplified = []
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
207 x = tree
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
208 while x[0] == op:
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
209 l, r = x[1:]
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
210 simplified.append(simplifyinfixops(r, targetnodes))
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
211 x = l
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
212 simplified.append(simplifyinfixops(x, targetnodes))
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
213 simplified.append(op)
c87b05925054 parser: add helper to reduce nesting of chained infix operations
Yuya Nishihara <yuya@tcha.org>
parents: 25254
diff changeset
214 return tuple(reversed(simplified))