Mercurial > hg
comparison mercurial/parser.py @ 25306:c87b05925054
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.
author | Yuya Nishihara <yuya@tcha.org> |
---|---|
date | Sun, 26 Apr 2015 18:05:23 +0900 |
parents | 060bdfef2517 |
children | af329a84310c |
comparison
equal
deleted
inserted
replaced
25304:9bc11716bc86 | 25306:c87b05925054 |
---|---|
106 def prettyformat(tree, leafnodes): | 106 def prettyformat(tree, leafnodes): |
107 lines = [] | 107 lines = [] |
108 _prettyformat(tree, leafnodes, 0, lines) | 108 _prettyformat(tree, leafnodes, 0, lines) |
109 output = '\n'.join((' ' * l + s) for l, s in lines) | 109 output = '\n'.join((' ' * l + s) for l, s in lines) |
110 return output | 110 return output |
111 | |
112 def simplifyinfixops(tree, targetnodes): | |
113 """Flatten chained infix operations to reduce usage of Python stack | |
114 | |
115 >>> def f(tree): | |
116 ... print prettyformat(simplifyinfixops(tree, ('or',)), ('symbol',)) | |
117 >>> f(('or', | |
118 ... ('or', | |
119 ... ('symbol', '1'), | |
120 ... ('symbol', '2')), | |
121 ... ('symbol', '3'))) | |
122 (or | |
123 ('symbol', '1') | |
124 ('symbol', '2') | |
125 ('symbol', '3')) | |
126 >>> f(('func', | |
127 ... ('symbol', 'p1'), | |
128 ... ('or', | |
129 ... ('or', | |
130 ... ('func', | |
131 ... ('symbol', 'sort'), | |
132 ... ('list', | |
133 ... ('or', | |
134 ... ('or', | |
135 ... ('symbol', '1'), | |
136 ... ('symbol', '2')), | |
137 ... ('symbol', '3')), | |
138 ... ('negate', | |
139 ... ('symbol', 'rev')))), | |
140 ... ('and', | |
141 ... ('symbol', '4'), | |
142 ... ('group', | |
143 ... ('or', | |
144 ... ('or', | |
145 ... ('symbol', '5'), | |
146 ... ('symbol', '6')), | |
147 ... ('symbol', '7'))))), | |
148 ... ('symbol', '8')))) | |
149 (func | |
150 ('symbol', 'p1') | |
151 (or | |
152 (func | |
153 ('symbol', 'sort') | |
154 (list | |
155 (or | |
156 ('symbol', '1') | |
157 ('symbol', '2') | |
158 ('symbol', '3')) | |
159 (negate | |
160 ('symbol', 'rev')))) | |
161 (and | |
162 ('symbol', '4') | |
163 (group | |
164 (or | |
165 ('symbol', '5') | |
166 ('symbol', '6') | |
167 ('symbol', '7')))) | |
168 ('symbol', '8'))) | |
169 """ | |
170 if not isinstance(tree, tuple): | |
171 return tree | |
172 op = tree[0] | |
173 if op not in targetnodes: | |
174 return (op,) + tuple(simplifyinfixops(x, targetnodes) for x in tree[1:]) | |
175 | |
176 # walk down left nodes taking each right node. no recursion to left nodes | |
177 # because infix operators are left-associative, i.e. left tree is deep. | |
178 # e.g. '1 + 2 + 3' -> (+ (+ 1 2) 3) -> (+ 1 2 3) | |
179 simplified = [] | |
180 x = tree | |
181 while x[0] == op: | |
182 l, r = x[1:] | |
183 simplified.append(simplifyinfixops(r, targetnodes)) | |
184 x = l | |
185 simplified.append(simplifyinfixops(x, targetnodes)) | |
186 simplified.append(op) | |
187 return tuple(reversed(simplified)) |