Coverage for /pythoncovmergedfiles/medio/medio/src/black/src/blib2to3/pytree.py: 37%
Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# Copyright 2006 Google, Inc. All Rights Reserved.
2# Licensed to PSF under a Contributor Agreement.
4"""
5Python parse tree definitions.
7This is a very concrete parse tree; we need to keep every token and
8even the comments and whitespace between tokens.
10There's also a pattern matching implementation here.
11"""
13# mypy: allow-untyped-defs, allow-incomplete-defs
15from collections.abc import Iterator
16from typing import Any, Optional, TypeVar, Union
18from blib2to3.pgen2.grammar import Grammar
20__author__ = "Guido van Rossum <guido@python.org>"
23_type_reprs: dict[int, str | int] = {}
26def type_repr(type_num: int) -> str | int:
27 global _type_reprs
28 if not _type_reprs:
29 from . import pygram
31 if not hasattr(pygram, "python_symbols"):
32 pygram.initialize(cache_dir=None)
34 # printing tokens is possible but not as useful
35 # from .pgen2 import token // token.__dict__.items():
36 for name in dir(pygram.python_symbols):
37 val = getattr(pygram.python_symbols, name)
38 if type(val) == int:
39 _type_reprs[val] = name
40 return _type_reprs.setdefault(type_num, type_num)
43_P = TypeVar("_P", bound="Base")
45NL = Union["Node", "Leaf"]
46Context = tuple[str, tuple[int, int]]
47RawNode = tuple[int, Optional[str], Optional[Context], Optional[list[NL]]]
50class Base:
51 """
52 Abstract base class for Node and Leaf.
54 This provides some default functionality and boilerplate using the
55 template pattern.
57 A node may be a subnode of at most one parent.
58 """
60 # Default values for instance variables
61 type: int # int: token number (< 256) or symbol number (>= 256)
62 parent: Optional["Node"] = None # Parent node pointer, or None
63 children: list[NL] # List of subnodes
65 def __new__(cls, *args, **kwds):
66 """Constructor that prevents Base from being instantiated."""
67 assert cls is not Base, "Cannot instantiate Base"
68 return object.__new__(cls)
70 def __eq__(self, other: Any) -> bool:
71 """
72 Compare two nodes for equality.
74 This calls the method _eq().
75 """
76 if self.__class__ is not other.__class__:
77 return NotImplemented
78 return self._eq(other)
80 @property
81 def prefix(self) -> str:
82 raise NotImplementedError
84 def _eq(self: _P, other: _P) -> bool:
85 """
86 Compare two nodes for equality.
88 This is called by __eq__ and __ne__. It is only called if the two nodes
89 have the same type. This must be implemented by the concrete subclass.
90 Nodes should be considered equal if they have the same structure,
91 ignoring the prefix string and other context information.
92 """
93 raise NotImplementedError
95 def __deepcopy__(self: _P) -> _P:
96 return self.clone()
98 def clone(self: _P) -> _P:
99 """
100 Return a cloned (deep) copy of self.
102 This must be implemented by the concrete subclass.
103 """
104 raise NotImplementedError
106 def pre_order(self) -> Iterator[NL]:
107 """
108 Return a pre-order iterator for the tree.
110 This must be implemented by the concrete subclass.
111 """
112 raise NotImplementedError
114 def replace(self, new: NL | list[NL]) -> None:
115 """Replace this node with a new one in the parent."""
116 assert self.parent is not None, str(self)
117 assert new is not None
118 if not isinstance(new, list):
119 new = [new]
120 parent = self.parent
121 for i, ch in enumerate(parent.children):
122 if ch is self:
123 break
124 else:
125 raise AssertionError((parent.children, self, new))
126 # Splice the new children in place of `self` and keep the cached sibling
127 # maps valid without rebuilding them, which would be O(len(children)) per
128 # call and quadratic when many children are replaced while siblings are
129 # read in between (e.g. merging implicitly concatenated strings).
130 parent._replace_child_in_sibling_maps(self, new)
131 parent.children[i : i + 1] = new
132 for x in new:
133 x.parent = parent
134 self.parent = None
136 def get_lineno(self) -> int | None:
137 """Return the line number which generated the invocant node."""
138 node = self
139 while not isinstance(node, Leaf):
140 if not node.children:
141 return None
142 node = node.children[0]
143 return node.lineno
145 def remove(self, search_start: int = 0) -> int | None:
146 """
147 Remove the node from the tree. Returns the position of the node in its
148 parent's children before it was removed.
150 ``search_start`` hints where to begin looking in the parent's children.
151 A caller that removes many siblings of the same parent in left-to-right
152 order can pass the last returned position to avoid rescanning the whole
153 list from index 0 every time, which is quadratic over the parent. The
154 entire list is still searched (starting at the hint and wrapping around),
155 so an inaccurate hint only costs a little extra scanning.
156 """
157 if self.parent:
158 children = self.parent.children
159 count = len(children)
160 for offset in range(count):
161 i = (search_start + offset) % count
162 if children[i] is self:
163 del children[i]
164 self.parent._remove_from_sibling_maps(self)
165 self.parent = None
166 return i
167 return None
169 @property
170 def next_sibling(self) -> NL | None:
171 """
172 The node immediately following the invocant in their parent's children
173 list. If the invocant does not have a next sibling, it is None
174 """
175 if self.parent is None:
176 return None
178 if self.parent.next_sibling_map is None:
179 self.parent.update_sibling_maps()
180 assert self.parent.next_sibling_map is not None
181 return self.parent.next_sibling_map[id(self)]
183 @property
184 def prev_sibling(self) -> NL | None:
185 """
186 The node immediately preceding the invocant in their parent's children
187 list. If the invocant does not have a previous sibling, it is None.
188 """
189 if self.parent is None:
190 return None
192 if self.parent.prev_sibling_map is None:
193 self.parent.update_sibling_maps()
194 assert self.parent.prev_sibling_map is not None
195 return self.parent.prev_sibling_map[id(self)]
197 def leaves(self) -> Iterator["Leaf"]:
198 # Walk iteratively rather than recursing with `yield from`, whose per-node
199 # generator delegation is O(depth) and makes a full traversal quadratic on
200 # deeply nested trees (e.g. a long `a ** b ** c ** ...` chain).
201 stack: list[NL] = list(reversed(self.children))
202 while stack:
203 node = stack.pop()
204 if isinstance(node, Leaf):
205 yield node
206 else:
207 stack.extend(reversed(node.children))
209 def depth(self) -> int:
210 if self.parent is None:
211 return 0
212 return 1 + self.parent.depth()
215class Node(Base):
216 """Concrete implementation for interior nodes."""
218 def __init__(
219 self,
220 type: int,
221 children: list[NL],
222 prefix: str | None = None,
223 ) -> None:
224 """
225 Initializer.
227 Takes a type constant (a symbol number >= 256), a sequence of
228 child nodes, and an optional prefix argument.
230 As a side effect, the parent pointers of the children are updated.
231 """
232 assert type >= 256, type
233 self.type = type
234 self.children = list(children)
235 for ch in self.children:
236 assert ch.parent is None, repr(ch)
237 ch.parent = self
238 self.invalidate_sibling_maps()
239 if prefix is not None:
240 self.prefix = prefix
242 def __repr__(self) -> str:
243 """Return a canonical string representation."""
244 assert self.type is not None
245 return f"{self.__class__.__name__}({type_repr(self.type)}, {self.children!r})"
247 def __str__(self) -> str:
248 """
249 Return a pretty string representation.
251 This reproduces the input source exactly.
252 """
253 return "".join(map(str, self.children))
255 def _eq(self, other: Base) -> bool:
256 """Compare two nodes for equality."""
257 return (self.type, self.children) == (other.type, other.children)
259 def clone(self) -> "Node":
260 assert self.type is not None
261 """Return a cloned (deep) copy of self."""
262 return Node(
263 self.type,
264 [ch.clone() for ch in self.children],
265 self.prefix,
266 )
268 def pre_order(self) -> Iterator[NL]:
269 """Return a pre-order iterator for the tree."""
270 # Walk iteratively rather than recursing with `yield from`. The recursive
271 # form resumes one delegating generator per level on every step, so a full
272 # traversal costs O(depth) per node and is quadratic on deeply nested trees.
273 stack: list[NL] = [self]
274 while stack:
275 node = stack.pop()
276 yield node
277 stack.extend(reversed(node.children))
279 @property
280 def prefix(self) -> str:
281 """
282 The whitespace and comments preceding this node in the input.
283 """
284 if not self.children:
285 return ""
286 return self.children[0].prefix
288 @prefix.setter
289 def prefix(self, prefix: str) -> None:
290 if self.children:
291 self.children[0].prefix = prefix
293 def set_child(self, i: int, child: NL) -> None:
294 """
295 Equivalent to 'node.children[i] = child'. This method also sets the
296 child's parent attribute appropriately.
297 """
298 child.parent = self
299 old = self.children[i]
300 old.parent = None
301 self.children[i] = child
302 self._replace_in_sibling_maps(old, child)
304 def insert_child(self, i: int, child: NL) -> None:
305 """
306 Equivalent to 'node.children.insert(i, child)'. This method also sets
307 the child's parent attribute appropriately.
308 """
309 child.parent = self
310 self.children.insert(i, child)
311 if 0 <= i < len(self.children) and self.children[i] is child:
312 self._insert_into_sibling_maps(i, child)
313 else:
314 self.invalidate_sibling_maps()
316 def append_child(self, child: NL) -> None:
317 """
318 Equivalent to 'node.children.append(child)'. This method also sets the
319 child's parent attribute appropriately.
320 """
321 child.parent = self
322 self.children.append(child)
323 self._insert_into_sibling_maps(len(self.children) - 1, child)
325 def invalidate_sibling_maps(self) -> None:
326 self.prev_sibling_map: dict[int, NL | None] | None = None
327 self.next_sibling_map: dict[int, NL | None] | None = None
329 def _insert_into_sibling_maps(self, i: int, child: NL) -> None:
330 """Splice a newly inserted child into the cached sibling maps.
332 Keeps the maps valid without rebuilding them from scratch, which would
333 be O(len(children)) per call and quadratic when many children are
334 inserted while siblings are read in between (e.g. ``append_leaves``).
335 """
336 prev_map = self.prev_sibling_map
337 next_map = self.next_sibling_map
338 if prev_map is None or next_map is None:
339 return
340 before = self.children[i - 1] if i > 0 else None
341 after = self.children[i + 1] if i + 1 < len(self.children) else None
342 prev_map[id(child)] = before
343 next_map[id(child)] = after
344 next_map[id(before)] = child
345 if after is not None:
346 prev_map[id(after)] = child
348 def _remove_from_sibling_maps(self, child: NL) -> None:
349 """Splice a removed child out of the cached sibling maps."""
350 prev_map = self.prev_sibling_map
351 next_map = self.next_sibling_map
352 if prev_map is None or next_map is None:
353 return
354 if id(child) not in prev_map:
355 self.invalidate_sibling_maps()
356 return
357 before = prev_map.pop(id(child))
358 after = next_map.pop(id(child))
359 next_map[id(before)] = after
360 if after is not None:
361 prev_map[id(after)] = before
363 def _replace_in_sibling_maps(self, old: NL, child: NL) -> None:
364 """Swap ``old`` for ``child`` at the same position in the sibling maps."""
365 prev_map = self.prev_sibling_map
366 next_map = self.next_sibling_map
367 if prev_map is None or next_map is None:
368 return
369 if id(old) not in prev_map:
370 self.invalidate_sibling_maps()
371 return
372 before = prev_map.pop(id(old))
373 after = next_map.pop(id(old))
374 prev_map[id(child)] = before
375 next_map[id(child)] = after
376 next_map[id(before)] = child
377 if after is not None:
378 prev_map[id(after)] = child
380 def _replace_child_in_sibling_maps(self, old: NL, new_children: list[NL]) -> None:
381 """Swap ``old`` for ``new_children`` at the same position in the maps."""
382 prev_map = self.prev_sibling_map
383 next_map = self.next_sibling_map
384 if prev_map is None or next_map is None:
385 return
386 if id(old) not in prev_map:
387 self.invalidate_sibling_maps()
388 return
389 before = prev_map.pop(id(old))
390 after = next_map.pop(id(old))
391 previous = before
392 for child in new_children:
393 prev_map[id(child)] = previous
394 next_map[id(previous)] = child
395 previous = child
396 next_map[id(previous)] = after
397 if after is not None:
398 prev_map[id(after)] = previous
400 def update_sibling_maps(self) -> None:
401 _prev: dict[int, NL | None] = {}
402 _next: dict[int, NL | None] = {}
403 self.prev_sibling_map = _prev
404 self.next_sibling_map = _next
405 previous: NL | None = None
406 for current in self.children:
407 _prev[id(current)] = previous
408 _next[id(previous)] = current
409 previous = current
410 _next[id(current)] = None
413class Leaf(Base):
414 """Concrete implementation for leaf nodes."""
416 value: str
417 bracket_depth: int = 0
419 # Changed later in brackets.py
420 opening_bracket: Optional["Leaf"] = None
422 _prefix = "" # Whitespace and comments preceding this token in the input
423 lineno: int = 0 # Line where this token starts in the input
424 column: int = 0 # Column where this token starts in the input
426 # clone() shares the below fields verbatim
427 # These fields must either be immutable or not mutated, so as to prevent
428 # leaves from spookily affecting each other
430 # If not None, this Leaf is created by converting a block of fmt off/skip code.
431 # The first Leaf in the converted code
432 # Use read-only
433 fmt_pass_converted_first_leaf: Optional["Leaf"] = None
435 # Metadata for STANDALONE_COMMENT leaves converted from unchanged code for --line-ranges.
436 # The converted block's first physical line
437 line_ranges_first_lineno: int = 0
438 # The requested physical source lines; can be before `first_lineno`
439 line_ranges_selected: Optional[frozenset[int]] = None
441 def __init__(
442 self,
443 type: int,
444 value: str,
445 context: Context | None = None,
446 prefix: str | None = None,
447 opening_bracket: Optional["Leaf"] = None,
448 fmt_pass_converted_first_leaf: Optional["Leaf"] = None,
449 bracket_depth: int = 0,
450 line_ranges_first_lineno: int = 0,
451 line_ranges_selected: Optional[frozenset[int]] = None,
452 ) -> None:
453 """
454 Initializer.
456 Takes a type constant (a token number < 256), a string value, and an
457 optional context keyword argument.
458 """
460 assert 0 <= type < 256, type
461 if context is not None:
462 self._prefix, (self.lineno, self.column) = context
463 self.type = type
464 self.value = value
465 if prefix is not None:
466 self._prefix = prefix
467 self.children = []
468 self.opening_bracket = opening_bracket
469 self.fmt_pass_converted_first_leaf = fmt_pass_converted_first_leaf
470 self.bracket_depth = bracket_depth
471 self.line_ranges_first_lineno = line_ranges_first_lineno
472 self.line_ranges_selected = line_ranges_selected
474 def __repr__(self) -> str:
475 """Return a canonical string representation."""
476 from .pgen2.token import tok_name
478 assert self.type is not None
479 return (
480 f"{self.__class__.__name__}({tok_name.get(self.type, self.type)},"
481 f" {self.value!r})"
482 )
484 def __str__(self) -> str:
485 """
486 Return a pretty string representation.
488 This reproduces the input source exactly.
489 """
490 return self._prefix + str(self.value)
492 def _eq(self, other: "Leaf") -> bool:
493 """Compare two nodes for equality."""
494 return (self.type, self.value) == (other.type, other.value)
496 def clone(self) -> "Leaf":
497 assert self.type is not None
498 """Return a cloned (deep) copy of self."""
499 return Leaf(
500 self.type,
501 self.value,
502 (self.prefix, (self.lineno, self.column)),
503 fmt_pass_converted_first_leaf=self.fmt_pass_converted_first_leaf,
504 bracket_depth=self.bracket_depth,
505 line_ranges_first_lineno=self.line_ranges_first_lineno,
506 line_ranges_selected=self.line_ranges_selected,
507 )
509 def leaves(self) -> Iterator["Leaf"]:
510 yield self
512 def pre_order(self) -> Iterator["Leaf"]:
513 """Return a pre-order iterator for the tree."""
514 yield self
516 @property
517 def prefix(self) -> str:
518 """
519 The whitespace and comments preceding this token in the input.
520 """
521 return self._prefix
523 @prefix.setter
524 def prefix(self, prefix: str) -> None:
525 self._prefix = prefix
528def convert(gr: Grammar, raw_node: RawNode) -> NL:
529 """
530 Convert raw node information to a Node or Leaf instance.
532 This is passed to the parser driver which calls it whenever a reduction of a
533 grammar rule produces a new complete node, so that the tree is build
534 strictly bottom-up.
535 """
536 type, value, context, children = raw_node
537 if children or type in gr.number2symbol:
538 # If there's exactly one child, return that child instead of
539 # creating a new node.
540 assert children is not None
541 if len(children) == 1:
542 return children[0]
543 return Node(type, children)
544 else:
545 return Leaf(type, value or "", context=context)