Lib/lib2to3/patcomp.py

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