• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Copyright 2006 Google, Inc. All Rights Reserved.
2# Licensed to PSF under a Contributor Agreement.
3
4"""Pattern compiler.
5
6The grammar is taken from PatternGrammar.txt.
7
8The compiler compiles a pattern to a pytree.*Pattern instance.
9"""
10
11__author__ = "Guido van Rossum <guido@python.org>"
12
13# Python imports
14import io
15
16# Fairly local imports
17from .pgen2 import driver, literals, token, tokenize, parse, grammar
18
19# Really local imports
20from . import pytree
21from . import pygram
22
23
24class PatternSyntaxError(Exception):
25    pass
26
27
28def tokenize_wrapper(input):
29    """Tokenizes a string suppressing significant whitespace."""
30    skip = {token.NEWLINE, token.INDENT, token.DEDENT}
31    tokens = tokenize.generate_tokens(io.StringIO(input).readline)
32    for quintuple in tokens:
33        type, value, start, end, line_text = quintuple
34        if type not in skip:
35            yield quintuple
36
37
38class PatternCompiler(object):
39
40    def __init__(self, grammar_file=None):
41        """Initializer.
42
43        Takes an optional alternative filename for the pattern grammar.
44        """
45        if grammar_file is None:
46            self.grammar = pygram.pattern_grammar
47            self.syms = pygram.pattern_symbols
48        else:
49            self.grammar = driver.load_grammar(grammar_file)
50            self.syms = pygram.Symbols(self.grammar)
51        self.pygrammar = pygram.python_grammar
52        self.pysyms = pygram.python_symbols
53        self.driver = driver.Driver(self.grammar, convert=pattern_convert)
54
55    def compile_pattern(self, input, debug=False, with_tree=False):
56        """Compiles a pattern string to a nested pytree.*Pattern object."""
57        tokens = tokenize_wrapper(input)
58        try:
59            root = self.driver.parse_tokens(tokens, debug=debug)
60        except parse.ParseError as e:
61            raise PatternSyntaxError(str(e)) from None
62        if with_tree:
63            return self.compile_node(root), root
64        else:
65            return self.compile_node(root)
66
67    def compile_node(self, node):
68        """Compiles a node, recursively.
69
70        This is one big switch on the node type.
71        """
72        # XXX Optimize certain Wildcard-containing-Wildcard patterns
73        # that can be merged
74        if node.type == self.syms.Matcher:
75            node = node.children[0] # Avoid unneeded recursion
76
77        if node.type == self.syms.Alternatives:
78            # Skip the odd children since they are just '|' tokens
79            alts = [self.compile_node(ch) for ch in node.children[::2]]
80            if len(alts) == 1:
81                return alts[0]
82            p = pytree.WildcardPattern([[a] for a in alts], min=1, max=1)
83            return p.optimize()
84
85        if node.type == self.syms.Alternative:
86            units = [self.compile_node(ch) for ch in node.children]
87            if len(units) == 1:
88                return units[0]
89            p = pytree.WildcardPattern([units], min=1, max=1)
90            return p.optimize()
91
92        if node.type == self.syms.NegatedUnit:
93            pattern = self.compile_basic(node.children[1:])
94            p = pytree.NegatedPattern(pattern)
95            return p.optimize()
96
97        assert node.type == self.syms.Unit
98
99        name = None
100        nodes = node.children
101        if len(nodes) >= 3 and nodes[1].type == token.EQUAL:
102            name = nodes[0].value
103            nodes = nodes[2:]
104        repeat = None
105        if len(nodes) >= 2 and nodes[-1].type == self.syms.Repeater:
106            repeat = nodes[-1]
107            nodes = nodes[:-1]
108
109        # Now we've reduced it to: STRING | NAME [Details] | (...) | [...]
110        pattern = self.compile_basic(nodes, repeat)
111
112        if repeat is not None:
113            assert repeat.type == self.syms.Repeater
114            children = repeat.children
115            child = children[0]
116            if child.type == token.STAR:
117                min = 0
118                max = pytree.HUGE
119            elif child.type == token.PLUS:
120                min = 1
121                max = pytree.HUGE
122            elif child.type == token.LBRACE:
123                assert children[-1].type == token.RBRACE
124                assert  len(children) in (3, 5)
125                min = max = self.get_int(children[1])
126                if len(children) == 5:
127                    max = self.get_int(children[3])
128            else:
129                assert False
130            if min != 1 or max != 1:
131                pattern = pattern.optimize()
132                pattern = pytree.WildcardPattern([[pattern]], min=min, max=max)
133
134        if name is not None:
135            pattern.name = name
136        return pattern.optimize()
137
138    def compile_basic(self, nodes, repeat=None):
139        # Compile STRING | NAME [Details] | (...) | [...]
140        assert len(nodes) >= 1
141        node = nodes[0]
142        if node.type == token.STRING:
143            value = str(literals.evalString(node.value))
144            return pytree.LeafPattern(_type_of_literal(value), value)
145        elif node.type == token.NAME:
146            value = node.value
147            if value.isupper():
148                if value not in TOKEN_MAP:
149                    raise PatternSyntaxError("Invalid token: %r" % value)
150                if nodes[1:]:
151                    raise PatternSyntaxError("Can't have details for token")
152                return pytree.LeafPattern(TOKEN_MAP[value])
153            else:
154                if value == "any":
155                    type = None
156                elif not value.startswith("_"):
157                    type = getattr(self.pysyms, value, None)
158                    if type is None:
159                        raise PatternSyntaxError("Invalid symbol: %r" % value)
160                if nodes[1:]: # Details present
161                    content = [self.compile_node(nodes[1].children[1])]
162                else:
163                    content = None
164                return pytree.NodePattern(type, content)
165        elif node.value == "(":
166            return self.compile_node(nodes[1])
167        elif node.value == "[":
168            assert repeat is None
169            subpattern = self.compile_node(nodes[1])
170            return pytree.WildcardPattern([[subpattern]], min=0, max=1)
171        assert False, node
172
173    def get_int(self, node):
174        assert node.type == token.NUMBER
175        return int(node.value)
176
177
178# Map named tokens to the type value for a LeafPattern
179TOKEN_MAP = {"NAME": token.NAME,
180             "STRING": token.STRING,
181             "NUMBER": token.NUMBER,
182             "TOKEN": None}
183
184
185def _type_of_literal(value):
186    if value[0].isalpha():
187        return token.NAME
188    elif value in grammar.opmap:
189        return grammar.opmap[value]
190    else:
191        return None
192
193
194def pattern_convert(grammar, raw_node_info):
195    """Converts raw node information to a Node or Leaf instance."""
196    type, value, context, children = raw_node_info
197    if children or type in grammar.number2symbol:
198        return pytree.Node(type, children, context=context)
199    else:
200        return pytree.Leaf(type, value, context=context)
201
202
203def compile_pattern(pattern):
204    return PatternCompiler().compile_pattern(pattern)
205