X-Git-Url: https://git.madduck.net/etc/vim.git/blobdiff_plain/2f3fa1f6d0cbc2a3f31c7440c422da173b068e7b:/src/blib2to3/pytree.py..dc71922c768e543c9c3bbb1db5ea6d7fa801a814:/.vim/bundle/black/src/blib2to3/static/git-logo.png diff --git a/src/blib2to3/pytree.py b/src/blib2to3/pytree.py deleted file mode 100644 index 7843467..0000000 --- a/src/blib2to3/pytree.py +++ /dev/null @@ -1,980 +0,0 @@ -# Copyright 2006 Google, Inc. All Rights Reserved. -# Licensed to PSF under a Contributor Agreement. - -""" -Python parse tree definitions. - -This is a very concrete parse tree; we need to keep every token and -even the comments and whitespace between tokens. - -There's also a pattern matching implementation here. -""" - -# mypy: allow-untyped-defs - -from typing import ( - Any, - Callable, - Dict, - Iterator, - List, - Optional, - Text, - Tuple, - TypeVar, - Union, - Set, - Iterable, -) -from blib2to3.pgen2.grammar import Grammar - -__author__ = "Guido van Rossum " - -import sys -from io import StringIO - -HUGE: int = 0x7FFFFFFF # maximum repeat count, default max - -_type_reprs: Dict[int, Union[Text, int]] = {} - - -def type_repr(type_num: int) -> Union[Text, int]: - global _type_reprs - if not _type_reprs: - from .pygram import python_symbols - - # printing tokens is possible but not as useful - # from .pgen2 import token // token.__dict__.items(): - for name in dir(python_symbols): - val = getattr(python_symbols, name) - if type(val) == int: - _type_reprs[val] = name - return _type_reprs.setdefault(type_num, type_num) - - -_P = TypeVar("_P") - -NL = Union["Node", "Leaf"] -Context = Tuple[Text, Tuple[int, int]] -RawNode = Tuple[int, Optional[Text], Optional[Context], Optional[List[NL]]] - - -class Base(object): - - """ - Abstract base class for Node and Leaf. - - This provides some default functionality and boilerplate using the - template pattern. - - A node may be a subnode of at most one parent. - """ - - # Default values for instance variables - type: int # int: token number (< 256) or symbol number (>= 256) - parent: Optional["Node"] = None # Parent node pointer, or None - children: List[NL] # List of subnodes - was_changed: bool = False - was_checked: bool = False - - def __new__(cls, *args, **kwds): - """Constructor that prevents Base from being instantiated.""" - assert cls is not Base, "Cannot instantiate Base" - return object.__new__(cls) - - def __eq__(self, other: Any) -> bool: - """ - Compare two nodes for equality. - - This calls the method _eq(). - """ - if self.__class__ is not other.__class__: - return NotImplemented - return self._eq(other) - - __hash__ = None # type: Any # For Py3 compatibility. - - @property - def prefix(self) -> Text: - raise NotImplementedError - - def _eq(self: _P, other: _P) -> bool: - """ - Compare two nodes for equality. - - This is called by __eq__ and __ne__. It is only called if the two nodes - have the same type. This must be implemented by the concrete subclass. - Nodes should be considered equal if they have the same structure, - ignoring the prefix string and other context information. - """ - raise NotImplementedError - - def clone(self: _P) -> _P: - """ - Return a cloned (deep) copy of self. - - This must be implemented by the concrete subclass. - """ - raise NotImplementedError - - def post_order(self) -> Iterator[NL]: - """ - Return a post-order iterator for the tree. - - This must be implemented by the concrete subclass. - """ - raise NotImplementedError - - def pre_order(self) -> Iterator[NL]: - """ - Return a pre-order iterator for the tree. - - This must be implemented by the concrete subclass. - """ - raise NotImplementedError - - def replace(self, new: Union[NL, List[NL]]) -> None: - """Replace this node with a new one in the parent.""" - assert self.parent is not None, str(self) - assert new is not None - if not isinstance(new, list): - new = [new] - l_children = [] - found = False - for ch in self.parent.children: - if ch is self: - assert not found, (self.parent.children, self, new) - if new is not None: - l_children.extend(new) - found = True - else: - l_children.append(ch) - assert found, (self.children, self, new) - self.parent.children = l_children - self.parent.changed() - self.parent.invalidate_sibling_maps() - for x in new: - x.parent = self.parent - self.parent = None - - def get_lineno(self) -> Optional[int]: - """Return the line number which generated the invocant node.""" - node = self - while not isinstance(node, Leaf): - if not node.children: - return None - node = node.children[0] - return node.lineno - - def changed(self) -> None: - if self.was_changed: - return - if self.parent: - self.parent.changed() - self.was_changed = True - - def remove(self) -> Optional[int]: - """ - Remove the node from the tree. Returns the position of the node in its - parent's children before it was removed. - """ - if self.parent: - for i, node in enumerate(self.parent.children): - if node is self: - del self.parent.children[i] - self.parent.changed() - self.parent.invalidate_sibling_maps() - self.parent = None - return i - return None - - @property - def next_sibling(self) -> Optional[NL]: - """ - The node immediately following the invocant in their parent's children - list. If the invocant does not have a next sibling, it is None - """ - if self.parent is None: - return None - - if self.parent.next_sibling_map is None: - self.parent.update_sibling_maps() - assert self.parent.next_sibling_map is not None - return self.parent.next_sibling_map[id(self)] - - @property - def prev_sibling(self) -> Optional[NL]: - """ - The node immediately preceding the invocant in their parent's children - list. If the invocant does not have a previous sibling, it is None. - """ - if self.parent is None: - return None - - if self.parent.prev_sibling_map is None: - self.parent.update_sibling_maps() - assert self.parent.prev_sibling_map is not None - return self.parent.prev_sibling_map[id(self)] - - def leaves(self) -> Iterator["Leaf"]: - for child in self.children: - yield from child.leaves() - - def depth(self) -> int: - if self.parent is None: - return 0 - return 1 + self.parent.depth() - - def get_suffix(self) -> Text: - """ - Return the string immediately following the invocant node. This is - effectively equivalent to node.next_sibling.prefix - """ - next_sib = self.next_sibling - if next_sib is None: - return "" - prefix = next_sib.prefix - return prefix - - -class Node(Base): - - """Concrete implementation for interior nodes.""" - - fixers_applied: Optional[List[Any]] - used_names: Optional[Set[Text]] - - def __init__( - self, - type: int, - children: List[NL], - context: Optional[Any] = None, - prefix: Optional[Text] = None, - fixers_applied: Optional[List[Any]] = None, - ) -> None: - """ - Initializer. - - Takes a type constant (a symbol number >= 256), a sequence of - child nodes, and an optional context keyword argument. - - As a side effect, the parent pointers of the children are updated. - """ - assert type >= 256, type - self.type = type - self.children = list(children) - for ch in self.children: - assert ch.parent is None, repr(ch) - ch.parent = self - self.invalidate_sibling_maps() - if prefix is not None: - self.prefix = prefix - if fixers_applied: - self.fixers_applied = fixers_applied[:] - else: - self.fixers_applied = None - - def __repr__(self) -> Text: - """Return a canonical string representation.""" - assert self.type is not None - return "%s(%s, %r)" % ( - self.__class__.__name__, - type_repr(self.type), - self.children, - ) - - def __str__(self) -> Text: - """ - Return a pretty string representation. - - This reproduces the input source exactly. - """ - return "".join(map(str, self.children)) - - def _eq(self, other) -> bool: - """Compare two nodes for equality.""" - return (self.type, self.children) == (other.type, other.children) - - def clone(self) -> "Node": - assert self.type is not None - """Return a cloned (deep) copy of self.""" - return Node( - self.type, - [ch.clone() for ch in self.children], - fixers_applied=self.fixers_applied, - ) - - def post_order(self) -> Iterator[NL]: - """Return a post-order iterator for the tree.""" - for child in self.children: - yield from child.post_order() - yield self - - def pre_order(self) -> Iterator[NL]: - """Return a pre-order iterator for the tree.""" - yield self - for child in self.children: - yield from child.pre_order() - - @property - def prefix(self) -> Text: - """ - The whitespace and comments preceding this node in the input. - """ - if not self.children: - return "" - return self.children[0].prefix - - @prefix.setter - def prefix(self, prefix) -> None: - if self.children: - self.children[0].prefix = prefix - - def set_child(self, i: int, child: NL) -> None: - """ - Equivalent to 'node.children[i] = child'. This method also sets the - child's parent attribute appropriately. - """ - child.parent = self - self.children[i].parent = None - self.children[i] = child - self.changed() - self.invalidate_sibling_maps() - - def insert_child(self, i: int, child: NL) -> None: - """ - Equivalent to 'node.children.insert(i, child)'. This method also sets - the child's parent attribute appropriately. - """ - child.parent = self - self.children.insert(i, child) - self.changed() - self.invalidate_sibling_maps() - - def append_child(self, child: NL) -> None: - """ - Equivalent to 'node.children.append(child)'. This method also sets the - child's parent attribute appropriately. - """ - child.parent = self - self.children.append(child) - self.changed() - self.invalidate_sibling_maps() - - def invalidate_sibling_maps(self) -> None: - self.prev_sibling_map: Optional[Dict[int, Optional[NL]]] = None - self.next_sibling_map: Optional[Dict[int, Optional[NL]]] = None - - def update_sibling_maps(self) -> None: - _prev: Dict[int, Optional[NL]] = {} - _next: Dict[int, Optional[NL]] = {} - self.prev_sibling_map = _prev - self.next_sibling_map = _next - previous: Optional[NL] = None - for current in self.children: - _prev[id(current)] = previous - _next[id(previous)] = current - previous = current - _next[id(current)] = None - - -class Leaf(Base): - - """Concrete implementation for leaf nodes.""" - - # Default values for instance variables - value: Text - fixers_applied: List[Any] - bracket_depth: int - opening_bracket: "Leaf" - used_names: Optional[Set[Text]] - _prefix = "" # Whitespace and comments preceding this token in the input - lineno: int = 0 # Line where this token starts in the input - column: int = 0 # Column where this token starts in the input - - def __init__( - self, - type: int, - value: Text, - context: Optional[Context] = None, - prefix: Optional[Text] = None, - fixers_applied: List[Any] = [], - ) -> None: - """ - Initializer. - - Takes a type constant (a token number < 256), a string value, and an - optional context keyword argument. - """ - - assert 0 <= type < 256, type - if context is not None: - self._prefix, (self.lineno, self.column) = context - self.type = type - self.value = value - if prefix is not None: - self._prefix = prefix - self.fixers_applied: Optional[List[Any]] = fixers_applied[:] - self.children = [] - - def __repr__(self) -> str: - """Return a canonical string representation.""" - from .pgen2.token import tok_name - - assert self.type is not None - return "%s(%s, %r)" % ( - self.__class__.__name__, - tok_name.get(self.type, self.type), - self.value, - ) - - def __str__(self) -> Text: - """ - Return a pretty string representation. - - This reproduces the input source exactly. - """ - return self.prefix + str(self.value) - - def _eq(self, other) -> bool: - """Compare two nodes for equality.""" - return (self.type, self.value) == (other.type, other.value) - - def clone(self) -> "Leaf": - assert self.type is not None - """Return a cloned (deep) copy of self.""" - return Leaf( - self.type, - self.value, - (self.prefix, (self.lineno, self.column)), - fixers_applied=self.fixers_applied, - ) - - def leaves(self) -> Iterator["Leaf"]: - yield self - - def post_order(self) -> Iterator["Leaf"]: - """Return a post-order iterator for the tree.""" - yield self - - def pre_order(self) -> Iterator["Leaf"]: - """Return a pre-order iterator for the tree.""" - yield self - - @property - def prefix(self) -> Text: - """ - The whitespace and comments preceding this token in the input. - """ - return self._prefix - - @prefix.setter - def prefix(self, prefix) -> None: - self.changed() - self._prefix = prefix - - -def convert(gr: Grammar, raw_node: RawNode) -> NL: - """ - Convert raw node information to a Node or Leaf instance. - - This is passed to the parser driver which calls it whenever a reduction of a - grammar rule produces a new complete node, so that the tree is build - strictly bottom-up. - """ - type, value, context, children = raw_node - if children or type in gr.number2symbol: - # If there's exactly one child, return that child instead of - # creating a new node. - assert children is not None - if len(children) == 1: - return children[0] - return Node(type, children, context=context) - else: - return Leaf(type, value or "", context=context) - - -_Results = Dict[Text, NL] - - -class BasePattern(object): - - """ - A pattern is a tree matching pattern. - - It looks for a specific node type (token or symbol), and - optionally for a specific content. - - This is an abstract base class. There are three concrete - subclasses: - - - LeafPattern matches a single leaf node; - - NodePattern matches a single node (usually non-leaf); - - WildcardPattern matches a sequence of nodes of variable length. - """ - - # Defaults for instance variables - type: Optional[int] - type = None # Node type (token if < 256, symbol if >= 256) - content: Any = None # Optional content matching pattern - name: Optional[Text] = None # Optional name used to store match in results dict - - def __new__(cls, *args, **kwds): - """Constructor that prevents BasePattern from being instantiated.""" - assert cls is not BasePattern, "Cannot instantiate BasePattern" - return object.__new__(cls) - - def __repr__(self) -> Text: - assert self.type is not None - args = [type_repr(self.type), self.content, self.name] - while args and args[-1] is None: - del args[-1] - return "%s(%s)" % (self.__class__.__name__, ", ".join(map(repr, args))) - - def _submatch(self, node, results=None) -> bool: - raise NotImplementedError - - def optimize(self) -> "BasePattern": - """ - A subclass can define this as a hook for optimizations. - - Returns either self or another node with the same effect. - """ - return self - - def match(self, node: NL, results: Optional[_Results] = None) -> bool: - """ - Does this pattern exactly match a node? - - Returns True if it matches, False if not. - - If results is not None, it must be a dict which will be - updated with the nodes matching named subpatterns. - - Default implementation for non-wildcard patterns. - """ - if self.type is not None and node.type != self.type: - return False - if self.content is not None: - r: Optional[_Results] = None - if results is not None: - r = {} - if not self._submatch(node, r): - return False - if r: - assert results is not None - results.update(r) - if results is not None and self.name: - results[self.name] = node - return True - - def match_seq(self, nodes: List[NL], results: Optional[_Results] = None) -> bool: - """ - Does this pattern exactly match a sequence of nodes? - - Default implementation for non-wildcard patterns. - """ - if len(nodes) != 1: - return False - return self.match(nodes[0], results) - - def generate_matches(self, nodes: List[NL]) -> Iterator[Tuple[int, _Results]]: - """ - Generator yielding all matches for this pattern. - - Default implementation for non-wildcard patterns. - """ - r: _Results = {} - if nodes and self.match(nodes[0], r): - yield 1, r - - -class LeafPattern(BasePattern): - def __init__( - self, - type: Optional[int] = None, - content: Optional[Text] = None, - name: Optional[Text] = None, - ) -> None: - """ - Initializer. Takes optional type, content, and name. - - The type, if given must be a token type (< 256). If not given, - this matches any *leaf* node; the content may still be required. - - The content, if given, must be a string. - - If a name is given, the matching node is stored in the results - dict under that key. - """ - if type is not None: - assert 0 <= type < 256, type - if content is not None: - assert isinstance(content, str), repr(content) - self.type = type - self.content = content - self.name = name - - def match(self, node: NL, results=None): - """Override match() to insist on a leaf node.""" - if not isinstance(node, Leaf): - return False - return BasePattern.match(self, node, results) - - def _submatch(self, node, results=None): - """ - Match the pattern's content to the node's children. - - This assumes the node type matches and self.content is not None. - - Returns True if it matches, False if not. - - If results is not None, it must be a dict which will be - updated with the nodes matching named subpatterns. - - When returning False, the results dict may still be updated. - """ - return self.content == node.value - - -class NodePattern(BasePattern): - - wildcards: bool = False - - def __init__( - self, - type: Optional[int] = None, - content: Optional[Iterable[Text]] = None, - name: Optional[Text] = None, - ) -> None: - """ - Initializer. Takes optional type, content, and name. - - The type, if given, must be a symbol type (>= 256). If the - type is None this matches *any* single node (leaf or not), - except if content is not None, in which it only matches - non-leaf nodes that also match the content pattern. - - The content, if not None, must be a sequence of Patterns that - must match the node's children exactly. If the content is - given, the type must not be None. - - If a name is given, the matching node is stored in the results - dict under that key. - """ - if type is not None: - assert type >= 256, type - if content is not None: - assert not isinstance(content, str), repr(content) - newcontent = list(content) - for i, item in enumerate(newcontent): - assert isinstance(item, BasePattern), (i, item) - if isinstance(item, WildcardPattern): - self.wildcards = True - self.type = type - self.content = newcontent - self.name = name - - def _submatch(self, node, results=None) -> bool: - """ - Match the pattern's content to the node's children. - - This assumes the node type matches and self.content is not None. - - Returns True if it matches, False if not. - - If results is not None, it must be a dict which will be - updated with the nodes matching named subpatterns. - - When returning False, the results dict may still be updated. - """ - if self.wildcards: - for c, r in generate_matches(self.content, node.children): - if c == len(node.children): - if results is not None: - results.update(r) - return True - return False - if len(self.content) != len(node.children): - return False - for subpattern, child in zip(self.content, node.children): - if not subpattern.match(child, results): - return False - return True - - -class WildcardPattern(BasePattern): - - """ - A wildcard pattern can match zero or more nodes. - - This has all the flexibility needed to implement patterns like: - - .* .+ .? .{m,n} - (a b c | d e | f) - (...)* (...)+ (...)? (...){m,n} - - except it always uses non-greedy matching. - """ - - min: int - max: int - - def __init__( - self, - content: Optional[Text] = None, - min: int = 0, - max: int = HUGE, - name: Optional[Text] = None, - ) -> None: - """ - Initializer. - - Args: - content: optional sequence of subsequences of patterns; - if absent, matches one node; - if present, each subsequence is an alternative [*] - min: optional minimum number of times to match, default 0 - max: optional maximum number of times to match, default HUGE - name: optional name assigned to this match - - [*] Thus, if content is [[a, b, c], [d, e], [f, g, h]] this is - equivalent to (a b c | d e | f g h); if content is None, - this is equivalent to '.' in regular expression terms. - The min and max parameters work as follows: - min=0, max=maxint: .* - min=1, max=maxint: .+ - min=0, max=1: .? - min=1, max=1: . - If content is not None, replace the dot with the parenthesized - list of alternatives, e.g. (a b c | d e | f g h)* - """ - assert 0 <= min <= max <= HUGE, (min, max) - if content is not None: - f = lambda s: tuple(s) - wrapped_content = tuple(map(f, content)) # Protect against alterations - # Check sanity of alternatives - assert len(wrapped_content), repr( - wrapped_content - ) # Can't have zero alternatives - for alt in wrapped_content: - assert len(alt), repr(alt) # Can have empty alternatives - self.content = wrapped_content - self.min = min - self.max = max - self.name = name - - def optimize(self) -> Any: - """Optimize certain stacked wildcard patterns.""" - subpattern = None - if ( - self.content is not None - and len(self.content) == 1 - and len(self.content[0]) == 1 - ): - subpattern = self.content[0][0] - if self.min == 1 and self.max == 1: - if self.content is None: - return NodePattern(name=self.name) - if subpattern is not None and self.name == subpattern.name: - return subpattern.optimize() - if ( - self.min <= 1 - and isinstance(subpattern, WildcardPattern) - and subpattern.min <= 1 - and self.name == subpattern.name - ): - return WildcardPattern( - subpattern.content, - self.min * subpattern.min, - self.max * subpattern.max, - subpattern.name, - ) - return self - - def match(self, node, results=None) -> bool: - """Does this pattern exactly match a node?""" - return self.match_seq([node], results) - - def match_seq(self, nodes, results=None) -> bool: - """Does this pattern exactly match a sequence of nodes?""" - for c, r in self.generate_matches(nodes): - if c == len(nodes): - if results is not None: - results.update(r) - if self.name: - results[self.name] = list(nodes) - return True - return False - - def generate_matches(self, nodes) -> Iterator[Tuple[int, _Results]]: - """ - Generator yielding matches for a sequence of nodes. - - Args: - nodes: sequence of nodes - - Yields: - (count, results) tuples where: - count: the match comprises nodes[:count]; - results: dict containing named submatches. - """ - if self.content is None: - # Shortcut for special case (see __init__.__doc__) - for count in range(self.min, 1 + min(len(nodes), self.max)): - r = {} - if self.name: - r[self.name] = nodes[:count] - yield count, r - elif self.name == "bare_name": - yield self._bare_name_matches(nodes) - else: - # The reason for this is that hitting the recursion limit usually - # results in some ugly messages about how RuntimeErrors are being - # ignored. We only have to do this on CPython, though, because other - # implementations don't have this nasty bug in the first place. - if hasattr(sys, "getrefcount"): - save_stderr = sys.stderr - sys.stderr = StringIO() - try: - for count, r in self._recursive_matches(nodes, 0): - if self.name: - r[self.name] = nodes[:count] - yield count, r - except RuntimeError: - # We fall back to the iterative pattern matching scheme if the recursive - # scheme hits the recursion limit. - for count, r in self._iterative_matches(nodes): - if self.name: - r[self.name] = nodes[:count] - yield count, r - finally: - if hasattr(sys, "getrefcount"): - sys.stderr = save_stderr - - def _iterative_matches(self, nodes) -> Iterator[Tuple[int, _Results]]: - """Helper to iteratively yield the matches.""" - nodelen = len(nodes) - if 0 >= self.min: - yield 0, {} - - results = [] - # generate matches that use just one alt from self.content - for alt in self.content: - for c, r in generate_matches(alt, nodes): - yield c, r - results.append((c, r)) - - # for each match, iterate down the nodes - while results: - new_results = [] - for c0, r0 in results: - # stop if the entire set of nodes has been matched - if c0 < nodelen and c0 <= self.max: - for alt in self.content: - for c1, r1 in generate_matches(alt, nodes[c0:]): - if c1 > 0: - r = {} - r.update(r0) - r.update(r1) - yield c0 + c1, r - new_results.append((c0 + c1, r)) - results = new_results - - def _bare_name_matches(self, nodes) -> Tuple[int, _Results]: - """Special optimized matcher for bare_name.""" - count = 0 - r = {} # type: _Results - done = False - max = len(nodes) - while not done and count < max: - done = True - for leaf in self.content: - if leaf[0].match(nodes[count], r): - count += 1 - done = False - break - assert self.name is not None - r[self.name] = nodes[:count] - return count, r - - def _recursive_matches(self, nodes, count) -> Iterator[Tuple[int, _Results]]: - """Helper to recursively yield the matches.""" - assert self.content is not None - if count >= self.min: - yield 0, {} - if count < self.max: - for alt in self.content: - for c0, r0 in generate_matches(alt, nodes): - for c1, r1 in self._recursive_matches(nodes[c0:], count + 1): - r = {} - r.update(r0) - r.update(r1) - yield c0 + c1, r - - -class NegatedPattern(BasePattern): - def __init__(self, content: Optional[Any] = None) -> None: - """ - Initializer. - - The argument is either a pattern or None. If it is None, this - only matches an empty sequence (effectively '$' in regex - lingo). If it is not None, this matches whenever the argument - pattern doesn't have any matches. - """ - if content is not None: - assert isinstance(content, BasePattern), repr(content) - self.content = content - - def match(self, node, results=None) -> bool: - # We never match a node in its entirety - return False - - def match_seq(self, nodes, results=None) -> bool: - # We only match an empty sequence of nodes in its entirety - return len(nodes) == 0 - - def generate_matches(self, nodes) -> Iterator[Tuple[int, _Results]]: - if self.content is None: - # Return a match if there is an empty sequence - if len(nodes) == 0: - yield 0, {} - else: - # Return a match if the argument pattern has no matches - for c, r in self.content.generate_matches(nodes): - return - yield 0, {} - - -def generate_matches( - patterns: List[BasePattern], nodes: List[NL] -) -> Iterator[Tuple[int, _Results]]: - """ - Generator yielding matches for a sequence of patterns and nodes. - - Args: - patterns: a sequence of patterns - nodes: a sequence of nodes - - Yields: - (count, results) tuples where: - count: the entire sequence of patterns matches nodes[:count]; - results: dict containing named submatches. - """ - if not patterns: - yield 0, {} - else: - p, rest = patterns[0], patterns[1:] - for c0, r0 in p.generate_matches(nodes): - if not rest: - yield c0, r0 - else: - for c1, r1 in generate_matches(rest, nodes[c0:]): - r = {} - r.update(r0) - r.update(r1) - yield c0 + c1, r - - -_Convert = Callable[[Grammar, RawNode], Any]