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