Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/lark/parse_tree_builder.py: 52%

226 statements  

« prev     ^ index     » next       coverage.py v7.3.1, created at 2023-09-25 06:30 +0000

1"""Provides functions for the automatic building and shaping of the parse-tree.""" 

2 

3from typing import List 

4 

5from .exceptions import GrammarError, ConfigurationError 

6from .lexer import Token 

7from .tree import Tree 

8from .visitors import Transformer_InPlace 

9from .visitors import _vargs_meta, _vargs_meta_inline 

10 

11###{standalone 

12from functools import partial, wraps 

13from itertools import product 

14 

15 

16class ExpandSingleChild: 

17 def __init__(self, node_builder): 

18 self.node_builder = node_builder 

19 

20 def __call__(self, children): 

21 if len(children) == 1: 

22 return children[0] 

23 else: 

24 return self.node_builder(children) 

25 

26 

27 

28class PropagatePositions: 

29 def __init__(self, node_builder, node_filter=None): 

30 self.node_builder = node_builder 

31 self.node_filter = node_filter 

32 

33 def __call__(self, children): 

34 res = self.node_builder(children) 

35 

36 if isinstance(res, Tree): 

37 # Calculate positions while the tree is streaming, according to the rule: 

38 # - nodes start at the start of their first child's container, 

39 # and end at the end of their last child's container. 

40 # Containers are nodes that take up space in text, but have been inlined in the tree. 

41 

42 res_meta = res.meta 

43 

44 first_meta = self._pp_get_meta(children) 

45 if first_meta is not None: 

46 if not hasattr(res_meta, 'line'): 

47 # meta was already set, probably because the rule has been inlined (e.g. `?rule`) 

48 res_meta.line = getattr(first_meta, 'container_line', first_meta.line) 

49 res_meta.column = getattr(first_meta, 'container_column', first_meta.column) 

50 res_meta.start_pos = getattr(first_meta, 'container_start_pos', first_meta.start_pos) 

51 res_meta.empty = False 

52 

53 res_meta.container_line = getattr(first_meta, 'container_line', first_meta.line) 

54 res_meta.container_column = getattr(first_meta, 'container_column', first_meta.column) 

55 res_meta.container_start_pos = getattr(first_meta, 'container_start_pos', first_meta.start_pos) 

56 

57 last_meta = self._pp_get_meta(reversed(children)) 

58 if last_meta is not None: 

59 if not hasattr(res_meta, 'end_line'): 

60 res_meta.end_line = getattr(last_meta, 'container_end_line', last_meta.end_line) 

61 res_meta.end_column = getattr(last_meta, 'container_end_column', last_meta.end_column) 

62 res_meta.end_pos = getattr(last_meta, 'container_end_pos', last_meta.end_pos) 

63 res_meta.empty = False 

64 

65 res_meta.container_end_line = getattr(last_meta, 'container_end_line', last_meta.end_line) 

66 res_meta.container_end_column = getattr(last_meta, 'container_end_column', last_meta.end_column) 

67 res_meta.container_end_pos = getattr(last_meta, 'container_end_pos', last_meta.end_pos) 

68 

69 return res 

70 

71 def _pp_get_meta(self, children): 

72 for c in children: 

73 if self.node_filter is not None and not self.node_filter(c): 

74 continue 

75 if isinstance(c, Tree): 

76 if not c.meta.empty: 

77 return c.meta 

78 elif isinstance(c, Token): 

79 return c 

80 elif hasattr(c, '__lark_meta__'): 

81 return c.__lark_meta__() 

82 

83def make_propagate_positions(option): 

84 if callable(option): 

85 return partial(PropagatePositions, node_filter=option) 

86 elif option is True: 

87 return PropagatePositions 

88 elif option is False: 

89 return None 

90 

91 raise ConfigurationError('Invalid option for propagate_positions: %r' % option) 

92 

93 

94class ChildFilter: 

95 def __init__(self, to_include, append_none, node_builder): 

96 self.node_builder = node_builder 

97 self.to_include = to_include 

98 self.append_none = append_none 

99 

100 def __call__(self, children): 

101 filtered = [] 

102 

103 for i, to_expand, add_none in self.to_include: 

104 if add_none: 

105 filtered += [None] * add_none 

106 if to_expand: 

107 filtered += children[i].children 

108 else: 

109 filtered.append(children[i]) 

110 

111 if self.append_none: 

112 filtered += [None] * self.append_none 

113 

114 return self.node_builder(filtered) 

115 

116 

117class ChildFilterLALR(ChildFilter): 

118 """Optimized childfilter for LALR (assumes no duplication in parse tree, so it's safe to change it)""" 

119 

120 def __call__(self, children): 

121 filtered = [] 

122 for i, to_expand, add_none in self.to_include: 

123 if add_none: 

124 filtered += [None] * add_none 

125 if to_expand: 

126 if filtered: 

127 filtered += children[i].children 

128 else: # Optimize for left-recursion 

129 filtered = children[i].children 

130 else: 

131 filtered.append(children[i]) 

132 

133 if self.append_none: 

134 filtered += [None] * self.append_none 

135 

136 return self.node_builder(filtered) 

137 

138 

139class ChildFilterLALR_NoPlaceholders(ChildFilter): 

140 "Optimized childfilter for LALR (assumes no duplication in parse tree, so it's safe to change it)" 

141 def __init__(self, to_include, node_builder): 

142 self.node_builder = node_builder 

143 self.to_include = to_include 

144 

145 def __call__(self, children): 

146 filtered = [] 

147 for i, to_expand in self.to_include: 

148 if to_expand: 

149 if filtered: 

150 filtered += children[i].children 

151 else: # Optimize for left-recursion 

152 filtered = children[i].children 

153 else: 

154 filtered.append(children[i]) 

155 return self.node_builder(filtered) 

156 

157 

158def _should_expand(sym): 

159 return not sym.is_term and sym.name.startswith('_') 

160 

161 

162def maybe_create_child_filter(expansion, keep_all_tokens, ambiguous, _empty_indices: List[bool]): 

163 # Prepare empty_indices as: How many Nones to insert at each index? 

164 if _empty_indices: 

165 assert _empty_indices.count(False) == len(expansion) 

166 s = ''.join(str(int(b)) for b in _empty_indices) 

167 empty_indices = [len(ones) for ones in s.split('0')] 

168 assert len(empty_indices) == len(expansion)+1, (empty_indices, len(expansion)) 

169 else: 

170 empty_indices = [0] * (len(expansion)+1) 

171 

172 to_include = [] 

173 nones_to_add = 0 

174 for i, sym in enumerate(expansion): 

175 nones_to_add += empty_indices[i] 

176 if keep_all_tokens or not (sym.is_term and sym.filter_out): 

177 to_include.append((i, _should_expand(sym), nones_to_add)) 

178 nones_to_add = 0 

179 

180 nones_to_add += empty_indices[len(expansion)] 

181 

182 if _empty_indices or len(to_include) < len(expansion) or any(to_expand for i, to_expand,_ in to_include): 

183 if _empty_indices or ambiguous: 

184 return partial(ChildFilter if ambiguous else ChildFilterLALR, to_include, nones_to_add) 

185 else: 

186 # LALR without placeholders 

187 return partial(ChildFilterLALR_NoPlaceholders, [(i, x) for i,x,_ in to_include]) 

188 

189 

190class AmbiguousExpander: 

191 """Deal with the case where we're expanding children ('_rule') into a parent but the children 

192 are ambiguous. i.e. (parent->_ambig->_expand_this_rule). In this case, make the parent itself 

193 ambiguous with as many copies as there are ambiguous children, and then copy the ambiguous children 

194 into the right parents in the right places, essentially shifting the ambiguity up the tree.""" 

195 def __init__(self, to_expand, tree_class, node_builder): 

196 self.node_builder = node_builder 

197 self.tree_class = tree_class 

198 self.to_expand = to_expand 

199 

200 def __call__(self, children): 

201 def _is_ambig_tree(t): 

202 return hasattr(t, 'data') and t.data == '_ambig' 

203 

204 # -- When we're repeatedly expanding ambiguities we can end up with nested ambiguities. 

205 # All children of an _ambig node should be a derivation of that ambig node, hence 

206 # it is safe to assume that if we see an _ambig node nested within an ambig node 

207 # it is safe to simply expand it into the parent _ambig node as an alternative derivation. 

208 ambiguous = [] 

209 for i, child in enumerate(children): 

210 if _is_ambig_tree(child): 

211 if i in self.to_expand: 

212 ambiguous.append(i) 

213 

214 child.expand_kids_by_data('_ambig') 

215 

216 if not ambiguous: 

217 return self.node_builder(children) 

218 

219 expand = [child.children if i in ambiguous else (child,) for i, child in enumerate(children)] 

220 return self.tree_class('_ambig', [self.node_builder(list(f)) for f in product(*expand)]) 

221 

222 

223def maybe_create_ambiguous_expander(tree_class, expansion, keep_all_tokens): 

224 to_expand = [i for i, sym in enumerate(expansion) 

225 if keep_all_tokens or ((not (sym.is_term and sym.filter_out)) and _should_expand(sym))] 

226 if to_expand: 

227 return partial(AmbiguousExpander, to_expand, tree_class) 

228 

229 

230class AmbiguousIntermediateExpander: 

231 """ 

232 Propagate ambiguous intermediate nodes and their derivations up to the 

233 current rule. 

234 

235 In general, converts 

236 

237 rule 

238 _iambig 

239 _inter 

240 someChildren1 

241 ... 

242 _inter 

243 someChildren2 

244 ... 

245 someChildren3 

246 ... 

247 

248 to 

249 

250 _ambig 

251 rule 

252 someChildren1 

253 ... 

254 someChildren3 

255 ... 

256 rule 

257 someChildren2 

258 ... 

259 someChildren3 

260 ... 

261 rule 

262 childrenFromNestedIambigs 

263 ... 

264 someChildren3 

265 ... 

266 ... 

267 

268 propagating up any nested '_iambig' nodes along the way. 

269 """ 

270 

271 def __init__(self, tree_class, node_builder): 

272 self.node_builder = node_builder 

273 self.tree_class = tree_class 

274 

275 def __call__(self, children): 

276 def _is_iambig_tree(child): 

277 return hasattr(child, 'data') and child.data == '_iambig' 

278 

279 def _collapse_iambig(children): 

280 """ 

281 Recursively flatten the derivations of the parent of an '_iambig' 

282 node. Returns a list of '_inter' nodes guaranteed not 

283 to contain any nested '_iambig' nodes, or None if children does 

284 not contain an '_iambig' node. 

285 """ 

286 

287 # Due to the structure of the SPPF, 

288 # an '_iambig' node can only appear as the first child 

289 if children and _is_iambig_tree(children[0]): 

290 iambig_node = children[0] 

291 result = [] 

292 for grandchild in iambig_node.children: 

293 collapsed = _collapse_iambig(grandchild.children) 

294 if collapsed: 

295 for child in collapsed: 

296 child.children += children[1:] 

297 result += collapsed 

298 else: 

299 new_tree = self.tree_class('_inter', grandchild.children + children[1:]) 

300 result.append(new_tree) 

301 return result 

302 

303 collapsed = _collapse_iambig(children) 

304 if collapsed: 

305 processed_nodes = [self.node_builder(c.children) for c in collapsed] 

306 return self.tree_class('_ambig', processed_nodes) 

307 

308 return self.node_builder(children) 

309 

310 

311 

312def inplace_transformer(func): 

313 @wraps(func) 

314 def f(children): 

315 # function name in a Transformer is a rule name. 

316 tree = Tree(func.__name__, children) 

317 return func(tree) 

318 return f 

319 

320 

321def apply_visit_wrapper(func, name, wrapper): 

322 if wrapper is _vargs_meta or wrapper is _vargs_meta_inline: 

323 raise NotImplementedError("Meta args not supported for internal transformer") 

324 

325 @wraps(func) 

326 def f(children): 

327 return wrapper(func, name, children, None) 

328 return f 

329 

330 

331class ParseTreeBuilder: 

332 def __init__(self, rules, tree_class, propagate_positions=False, ambiguous=False, maybe_placeholders=False): 

333 self.tree_class = tree_class 

334 self.propagate_positions = propagate_positions 

335 self.ambiguous = ambiguous 

336 self.maybe_placeholders = maybe_placeholders 

337 

338 self.rule_builders = list(self._init_builders(rules)) 

339 

340 def _init_builders(self, rules): 

341 propagate_positions = make_propagate_positions(self.propagate_positions) 

342 

343 for rule in rules: 

344 options = rule.options 

345 keep_all_tokens = options.keep_all_tokens 

346 expand_single_child = options.expand1 

347 

348 wrapper_chain = list(filter(None, [ 

349 (expand_single_child and not rule.alias) and ExpandSingleChild, 

350 maybe_create_child_filter(rule.expansion, keep_all_tokens, self.ambiguous, options.empty_indices if self.maybe_placeholders else None), 

351 propagate_positions, 

352 self.ambiguous and maybe_create_ambiguous_expander(self.tree_class, rule.expansion, keep_all_tokens), 

353 self.ambiguous and partial(AmbiguousIntermediateExpander, self.tree_class) 

354 ])) 

355 

356 yield rule, wrapper_chain 

357 

358 def create_callback(self, transformer=None): 

359 callbacks = {} 

360 

361 default_handler = getattr(transformer, '__default__', None) 

362 if default_handler: 

363 def default_callback(data, children): 

364 return default_handler(data, children, None) 

365 else: 

366 default_callback = self.tree_class 

367 

368 for rule, wrapper_chain in self.rule_builders: 

369 

370 user_callback_name = rule.alias or rule.options.template_source or rule.origin.name 

371 try: 

372 f = getattr(transformer, user_callback_name) 

373 wrapper = getattr(f, 'visit_wrapper', None) 

374 if wrapper is not None: 

375 f = apply_visit_wrapper(f, user_callback_name, wrapper) 

376 elif isinstance(transformer, Transformer_InPlace): 

377 f = inplace_transformer(f) 

378 except AttributeError: 

379 f = partial(default_callback, user_callback_name) 

380 

381 for w in wrapper_chain: 

382 f = w(f) 

383 

384 if rule in callbacks: 

385 raise GrammarError("Rule '%s' already exists" % (rule,)) 

386 

387 callbacks[rule] = f 

388 

389 return callbacks 

390 

391###}