]> git.madduck.net Git - etc/vim.git/blobdiff - src/blib2to3/pgen2/parse.py

madduck's git repository

Every one of the projects in this repository is available at the canonical URL git://git.madduck.net/madduck/pub/<projectpath> — see each project's metadata for the exact URL.

All patches and comments are welcome. Please squash your changes to logical commits before using git-format-patch and git-send-email to patches@git.madduck.net. If you'd read over the Git project's submission guidelines and adhered to them, I'd be especially grateful.

SSH access, as well as push access can be individually arranged.

If you use my repositories frequently, consider adding the following snippet to ~/.gitconfig and using the third clone URL listed for each project:

[url "git://git.madduck.net/madduck/"]
  insteadOf = madduck:

exclude tests/data/.* from mypy (#3917)
[etc/vim.git] / src / blib2to3 / pgen2 / parse.py
index 792e8e66698246f578fef7ce88d7bf69258af3e9..299cc24a15f4bd353d155b62ef645d8d6a9ef148 100644 (file)
@@ -9,33 +9,32 @@ See Parser/parser.c in the Python distribution for additional info on
 how this parsing engine works.
 
 """
 how this parsing engine works.
 
 """
-import copy
 from contextlib import contextmanager
 from contextlib import contextmanager
-
-# Local imports
-from . import grammar, token, tokenize
 from typing import (
 from typing import (
-    cast,
+    TYPE_CHECKING,
     Any,
     Any,
-    Optional,
-    Text,
-    Union,
-    Tuple,
+    Callable,
     Dict,
     Dict,
-    List,
     Iterator,
     Iterator,
-    Callable,
+    List,
+    Optional,
     Set,
     Set,
-    TYPE_CHECKING,
+    Tuple,
+    Union,
+    cast,
 )
 )
+
 from blib2to3.pgen2.grammar import Grammar
 from blib2to3.pgen2.grammar import Grammar
-from blib2to3.pytree import convert, NL, Context, RawNode, Leaf, Node
+from blib2to3.pytree import NL, Context, Leaf, Node, RawNode, convert
+
+# Local imports
+from . import grammar, token, tokenize
 
 if TYPE_CHECKING:
 
 if TYPE_CHECKING:
-    from blib2to3.driver import TokenProxy
+    from blib2to3.pgen2.driver import TokenProxy
 
 
 
 
-Results = Dict[Text, NL]
+Results = Dict[str, NL]
 Convert = Callable[[Grammar, RawNode], Union[Node, Leaf]]
 DFA = List[List[Tuple[int, int]]]
 DFAS = Tuple[DFA, Dict[int, int]]
 Convert = Callable[[Grammar, RawNode], Union[Node, Leaf]]
 DFA = List[List[Tuple[int, int]]]
 DFAS = Tuple[DFA, Dict[int, int]]
@@ -46,6 +45,17 @@ def lam_sub(grammar: Grammar, node: RawNode) -> NL:
     return Node(type=node[0], children=node[3], context=node[2])
 
 
     return Node(type=node[0], children=node[3], context=node[2])
 
 
+# A placeholder node, used when parser is backtracking.
+DUMMY_NODE = (-1, None, None, None)
+
+
+def stack_copy(
+    stack: List[Tuple[DFAS, int, RawNode]]
+) -> List[Tuple[DFAS, int, RawNode]]:
+    """Nodeless stack copy."""
+    return [(dfa, label, DUMMY_NODE) for dfa, label, _ in stack]
+
+
 class Recorder:
     def __init__(self, parser: "Parser", ilabels: List[int], context: Context) -> None:
         self.parser = parser
 class Recorder:
     def __init__(self, parser: "Parser", ilabels: List[int], context: Context) -> None:
         self.parser = parser
@@ -53,8 +63,8 @@ class Recorder:
         self.context = context  # not really matter
 
         self._dead_ilabels: Set[int] = set()
         self.context = context  # not really matter
 
         self._dead_ilabels: Set[int] = set()
-        self._start_point = copy.deepcopy(self.parser.stack)
-        self._points = {ilabel: copy.deepcopy(self._start_point) for ilabel in ilabels}
+        self._start_point = self.parser.stack
+        self._points = {ilabel: stack_copy(self._start_point) for ilabel in ilabels}
 
     @property
     def ilabels(self) -> Set[int]:
 
     @property
     def ilabels(self) -> Set[int]:
@@ -62,15 +72,34 @@ class Recorder:
 
     @contextmanager
     def switch_to(self, ilabel: int) -> Iterator[None]:
 
     @contextmanager
     def switch_to(self, ilabel: int) -> Iterator[None]:
-        self.parser.stack = self._points[ilabel]
+        with self.backtrack():
+            self.parser.stack = self._points[ilabel]
+            try:
+                yield
+            except ParseError:
+                self._dead_ilabels.add(ilabel)
+            finally:
+                self.parser.stack = self._start_point
+
+    @contextmanager
+    def backtrack(self) -> Iterator[None]:
+        """
+        Use the node-level invariant ones for basic parsing operations (push/pop/shift).
+        These still will operate on the stack; but they won't create any new nodes, or
+        modify the contents of any other existing nodes.
+
+        This saves us a ton of time when we are backtracking, since we
+        want to restore to the initial state as quick as possible, which
+        can only be done by having as little mutatations as possible.
+        """
+        is_backtracking = self.parser.is_backtracking
         try:
         try:
+            self.parser.is_backtracking = True
             yield
             yield
-        except ParseError:
-            self._dead_ilabels.add(ilabel)
         finally:
         finally:
-            self.parser.stack = self._start_point
+            self.parser.is_backtracking = is_backtracking
 
 
-    def add_token(self, tok_type: int, tok_val: Text, raw: bool = False) -> None:
+    def add_token(self, tok_type: int, tok_val: str, raw: bool = False) -> None:
         func: Callable[..., Any]
         if raw:
             func = self.parser._addtoken
         func: Callable[..., Any]
         if raw:
             func = self.parser._addtoken
@@ -84,7 +113,9 @@ class Recorder:
                     args.insert(0, ilabel)
                 func(*args)
 
                     args.insert(0, ilabel)
                 func(*args)
 
-    def determine_route(self, value: Text = None, force: bool = False) -> Optional[int]:
+    def determine_route(
+        self, value: Optional[str] = None, force: bool = False
+    ) -> Optional[int]:
         alive_ilabels = self.ilabels
         if len(alive_ilabels) == 0:
             *_, most_successful_ilabel = self._dead_ilabels
         alive_ilabels = self.ilabels
         if len(alive_ilabels) == 0:
             *_, most_successful_ilabel = self._dead_ilabels
@@ -101,10 +132,10 @@ class ParseError(Exception):
     """Exception to signal the parser is stuck."""
 
     def __init__(
     """Exception to signal the parser is stuck."""
 
     def __init__(
-        self, msg: Text, type: Optional[int], value: Optional[Text], context: Context
+        self, msg: str, type: Optional[int], value: Optional[str], context: Context
     ) -> None:
         Exception.__init__(
     ) -> None:
         Exception.__init__(
-            self, "%s: type=%r, value=%r, context=%r" % (msg, type, value, context)
+            self, f"{msg}: type={type!r}, value={value!r}, context={context!r}"
         )
         self.msg = msg
         self.type = type
         )
         self.msg = msg
         self.type = type
@@ -112,7 +143,7 @@ class ParseError(Exception):
         self.context = context
 
 
         self.context = context
 
 
-class Parser(object):
+class Parser:
     """Parser engine.
 
     The proper usage sequence is:
     """Parser engine.
 
     The proper usage sequence is:
@@ -179,6 +210,7 @@ class Parser(object):
         self.grammar = grammar
         # See note in docstring above. TL;DR this is ignored.
         self.convert = convert or lam_sub
         self.grammar = grammar
         # See note in docstring above. TL;DR this is ignored.
         self.convert = convert or lam_sub
+        self.is_backtracking = False
 
     def setup(self, proxy: "TokenProxy", start: Optional[int] = None) -> None:
         """Prepare for parsing.
 
     def setup(self, proxy: "TokenProxy", start: Optional[int] = None) -> None:
         """Prepare for parsing.
@@ -205,7 +237,7 @@ class Parser(object):
         self.used_names: Set[str] = set()
         self.proxy = proxy
 
         self.used_names: Set[str] = set()
         self.proxy = proxy
 
-    def addtoken(self, type: int, value: Text, context: Context) -> bool:
+    def addtoken(self, type: int, value: str, context: Context) -> bool:
         """Add a token; return True iff this is the end of the program."""
         # Map from token to label
         ilabels = self.classify(type, value, context)
         """Add a token; return True iff this is the end of the program."""
         # Map from token to label
         ilabels = self.classify(type, value, context)
@@ -238,6 +270,10 @@ class Parser(object):
                     break
 
                 next_token_type, next_token_value, *_ = proxy.eat(counter)
                     break
 
                 next_token_type, next_token_value, *_ = proxy.eat(counter)
+                if next_token_type in (tokenize.COMMENT, tokenize.NL):
+                    counter += 1
+                    continue
+
                 if next_token_type == tokenize.OP:
                     next_token_type = grammar.opmap[next_token_value]
 
                 if next_token_type == tokenize.OP:
                     next_token_type = grammar.opmap[next_token_value]
 
@@ -249,7 +285,7 @@ class Parser(object):
 
         return self._addtoken(ilabel, type, value, context)
 
 
         return self._addtoken(ilabel, type, value, context)
 
-    def _addtoken(self, ilabel: int, type: int, value: Text, context: Context) -> bool:
+    def _addtoken(self, ilabel: int, type: int, value: str, context: Context) -> bool:
         # Loop until the token is shifted; may raise exceptions
         while True:
             dfa, state, node = self.stack[-1]
         # Loop until the token is shifted; may raise exceptions
         while True:
             dfa, state, node = self.stack[-1]
@@ -294,7 +330,7 @@ class Parser(object):
                     # No success finding a transition
                     raise ParseError("bad input", type, value, context)
 
                     # No success finding a transition
                     raise ParseError("bad input", type, value, context)
 
-    def classify(self, type: int, value: Text, context: Context) -> List[int]:
+    def classify(self, type: int, value: str, context: Context) -> List[int]:
         """Turn a token into a label.  (Internal)
 
         Depending on whether the value is a soft-keyword or not,
         """Turn a token into a label.  (Internal)
 
         Depending on whether the value is a soft-keyword or not,
@@ -317,30 +353,42 @@ class Parser(object):
             raise ParseError("bad token", type, value, context)
         return [ilabel]
 
             raise ParseError("bad token", type, value, context)
         return [ilabel]
 
-    def shift(self, type: int, value: Text, newstate: int, context: Context) -> None:
+    def shift(self, type: int, value: str, newstate: int, context: Context) -> None:
         """Shift a token.  (Internal)"""
         """Shift a token.  (Internal)"""
-        dfa, state, node = self.stack[-1]
-        rawnode: RawNode = (type, value, context, None)
-        newnode = convert(self.grammar, rawnode)
-        assert node[-1] is not None
-        node[-1].append(newnode)
-        self.stack[-1] = (dfa, newstate, node)
+        if self.is_backtracking:
+            dfa, state, _ = self.stack[-1]
+            self.stack[-1] = (dfa, newstate, DUMMY_NODE)
+        else:
+            dfa, state, node = self.stack[-1]
+            rawnode: RawNode = (type, value, context, None)
+            newnode = convert(self.grammar, rawnode)
+            assert node[-1] is not None
+            node[-1].append(newnode)
+            self.stack[-1] = (dfa, newstate, node)
 
     def push(self, type: int, newdfa: DFAS, newstate: int, context: Context) -> None:
         """Push a nonterminal.  (Internal)"""
 
     def push(self, type: int, newdfa: DFAS, newstate: int, context: Context) -> None:
         """Push a nonterminal.  (Internal)"""
-        dfa, state, node = self.stack[-1]
-        newnode: RawNode = (type, None, context, [])
-        self.stack[-1] = (dfa, newstate, node)
-        self.stack.append((newdfa, 0, newnode))
+        if self.is_backtracking:
+            dfa, state, _ = self.stack[-1]
+            self.stack[-1] = (dfa, newstate, DUMMY_NODE)
+            self.stack.append((newdfa, 0, DUMMY_NODE))
+        else:
+            dfa, state, node = self.stack[-1]
+            newnode: RawNode = (type, None, context, [])
+            self.stack[-1] = (dfa, newstate, node)
+            self.stack.append((newdfa, 0, newnode))
 
     def pop(self) -> None:
         """Pop a nonterminal.  (Internal)"""
 
     def pop(self) -> None:
         """Pop a nonterminal.  (Internal)"""
-        popdfa, popstate, popnode = self.stack.pop()
-        newnode = convert(self.grammar, popnode)
-        if self.stack:
-            dfa, state, node = self.stack[-1]
-            assert node[-1] is not None
-            node[-1].append(newnode)
+        if self.is_backtracking:
+            self.stack.pop()
         else:
         else:
-            self.rootnode = newnode
-            self.rootnode.used_names = self.used_names
+            popdfa, popstate, popnode = self.stack.pop()
+            newnode = convert(self.grammar, popnode)
+            if self.stack:
+                dfa, state, node = self.stack[-1]
+                assert node[-1] is not None
+                node[-1].append(newnode)
+            else:
+                self.rootnode = newnode
+                self.rootnode.used_names = self.used_names