1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver""" @package antlr3.tree 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver@brief ANTLR3 runtime package, treewizard module 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 4324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverA utility module to create ASTs at runtime. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverSee <http://www.antlr.org/wiki/display/~admin/2007/07/02/Exploring+Concept+of+TreeWizard> for an overview. Note that the API of the Python implementation is slightly different. 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver""" 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# begin[licence] 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# [The "BSD licence"] 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# Copyright (c) 2005-2008 Terence Parr 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# All rights reserved. 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# Redistribution and use in source and binary forms, with or without 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# modification, are permitted provided that the following conditions 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# are met: 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 1. Redistributions of source code must retain the above copyright 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# notice, this list of conditions and the following disclaimer. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 2. Redistributions in binary form must reproduce the above copyright 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# notice, this list of conditions and the following disclaimer in the 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# documentation and/or other materials provided with the distribution. 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 3. The name of the author may not be used to endorse or promote products 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# derived from this software without specific prior written permission. 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# end[licence] 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverfrom antlr3.constants import INVALID_TOKEN_TYPE 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverfrom antlr3.tokens import CommonToken 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverfrom antlr3.tree import CommonTree, CommonTreeAdaptor 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverdef computeTokenTypes(tokenNames): 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Compute a dict that is an inverted index of 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenNames (which maps int token types to names). 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if tokenNames is None: 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return {} 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return dict((name, type) for type, name in enumerate(tokenNames)) 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver## token types for pattern parser 57324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverEOF = -1 58324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverBEGIN = 1 59324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverEND = 2 60324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverID = 3 61324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverARG = 4 62324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverPERCENT = 5 63324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverCOLON = 6 64324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverDOT = 7 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverclass TreePatternLexer(object): 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def __init__(self, pattern): 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ## The tree pattern to lex like "(A B C)" 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.pattern = pattern 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ## Index into input string 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.p = -1 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ## Current char 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.c = None 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ## How long is the pattern in char? 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.n = len(pattern) 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ## Set when token type is ID or ARG 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.sval = None 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.error = False 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver __idStartChar = frozenset( 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_' 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ) 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver __idChar = __idStartChar | frozenset('0123456789') 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def nextToken(self): 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.sval = "" 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while self.c != EOF: 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.c in (' ', '\n', '\r', '\t'): 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.c in self.__idStartChar: 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.sval += self.c 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while self.c in self.__idChar: 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.sval += self.c 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ID 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.c == '(': 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return BEGIN 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.c == ')': 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return END 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.c == '%': 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return PERCENT 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.c == ':': 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return COLON 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.c == '.': 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DOT 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.c == '[': # grab [x] as a string, returning x 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while self.c != ']': 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.c == '\\': 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.c != ']': 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.sval += '\\' 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.sval += self.c 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else: 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.sval += self.c 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ARG 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.consume() 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.error = True 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return EOF 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return EOF 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def consume(self): 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.p += 1 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.p >= self.n: 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.c = EOF 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else: 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.c = self.pattern[self.p] 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverclass TreePatternParser(object): 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def __init__(self, tokenizer, wizard, adaptor): 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.tokenizer = tokenizer 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.wizard = wizard 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.adaptor = adaptor 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.ttype = tokenizer.nextToken() # kickstart 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def pattern(self): 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype == BEGIN: 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return self.parseTree() 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elif self.ttype == ID: 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver node = self.parseNode() 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype == EOF: 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return node 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None # extra junk on end 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def parseTree(self): 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype != BEGIN: 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.ttype = self.tokenizer.nextToken() 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver root = self.parseNode() 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if root is None: 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while self.ttype in (BEGIN, ID, PERCENT, DOT): 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype == BEGIN: 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver subtree = self.parseTree() 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.adaptor.addChild(root, subtree) 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else: 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child = self.parseNode() 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if child is None: 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.adaptor.addChild(root, child) 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype != END: 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.ttype = self.tokenizer.nextToken() 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return root 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def parseNode(self): 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # "%label:" prefix 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label = None 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype == PERCENT: 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.ttype = self.tokenizer.nextToken() 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype != ID: 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label = self.tokenizer.sval 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.ttype = self.tokenizer.nextToken() 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype != COLON: 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.ttype = self.tokenizer.nextToken() # move to ID following colon 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # Wildcard? 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype == DOT: 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.ttype = self.tokenizer.nextToken() 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver wildcardPayload = CommonToken(0, ".") 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver node = WildcardTreePattern(wildcardPayload) 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if label is not None: 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver node.label = label 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return node 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # "ID" or "ID[arg]" 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype != ID: 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenName = self.tokenizer.sval 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.ttype = self.tokenizer.nextToken() 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if tokenName == "nil": 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return self.adaptor.nil() 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver text = tokenName 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # check for arg 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver arg = None 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.ttype == ARG: 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver arg = self.tokenizer.sval 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver text = arg 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.ttype = self.tokenizer.nextToken() 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # create node 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver treeNodeType = self.wizard.getTokenType(tokenName) 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if treeNodeType == INVALID_TOKEN_TYPE: 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver node = self.adaptor.createFromType(treeNodeType, text) 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if label is not None and isinstance(node, TreePattern): 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver node.label = label 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if arg is not None and isinstance(node, TreePattern): 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver node.hasTextArg = True 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return node 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverclass TreePattern(CommonTree): 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver When using %label:TOKENNAME in a tree for parse(), we must 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver track the label. 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def __init__(self, payload): 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver CommonTree.__init__(self, payload) 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.label = None 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.hasTextArg = None 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def toString(self): 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.label is not None: 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return '%' + self.label + ':' + CommonTree.toString(self) 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else: 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return CommonTree.toString(self) 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverclass WildcardTreePattern(TreePattern): 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pass 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverclass TreePatternTreeAdaptor(CommonTreeAdaptor): 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """This adaptor creates TreePattern objects for use during scan()""" 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def createWithPayload(self, payload): 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return TreePattern(payload) 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverclass TreeWizard(object): 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Build and navigate trees with this object. Must know about the names 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver of tokens so you have to pass in a map or array of token names (from which 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this class can build the map). I.e., Token DECL means nothing unless the 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver class can translate it to a token type. 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver In order to create nodes and navigate, this class needs a TreeAdaptor. 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver This class can build a token type -> node index for repeated use or for 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver iterating over the various nodes with a particular type. 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver This class works in conjunction with the TreeAdaptor rather than moving 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver all this functionality into the adaptor. An adaptor helps build and 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver navigate trees using methods. This class helps you do it with string 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver patterns like "(A B C)". You can create a tree from that pattern or 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver match subtrees against it. 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def __init__(self, adaptor=None, tokenNames=None, typeMap=None): 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if adaptor is None: 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.adaptor = CommonTreeAdaptor() 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else: 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.adaptor = adaptor 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if typeMap is None: 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.tokenNameToTypeMap = computeTokenTypes(tokenNames) 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else: 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if tokenNames is not None: 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver raise ValueError("Can't have both tokenNames and typeMap") 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.tokenNameToTypeMap = typeMap 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def getTokenType(self, tokenName): 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """Using the map of token names to token types, return the type.""" 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver try: 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return self.tokenNameToTypeMap[tokenName] 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver except KeyError: 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return INVALID_TOKEN_TYPE 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def create(self, pattern): 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Create a tree or node from the indicated tree pattern that closely 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver follows ANTLR tree grammar tree element syntax: 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (root child1 ... child2). 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver You can also just pass in a node: ID 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Any node can have a text argument: ID[foo] 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (notice there are no quotes around foo--it's clear it's a string). 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nil is a special name meaning "give me a nil node". Useful for 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver making lists: (nil A B C) is a list of A B C. 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenizer = TreePatternLexer(pattern) 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parser = TreePatternParser(tokenizer, self, self.adaptor) 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return parser.pattern() 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def index(self, tree): 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """Walk the entire tree and make a node name to nodes mapping. 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver For now, use recursion but later nonrecursive version may be 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver more efficient. Returns a dict int -> list where the list is 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver of your AST node type. The int is the token type of the node. 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver m = {} 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self._index(tree, m) 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return m 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def _index(self, t, m): 383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """Do the work for index""" 384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if t is None: 386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ttype = self.adaptor.getType(t) 389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elements = m.get(ttype) 390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if elements is None: 391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver m[ttype] = elements = [] 392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elements.append(t) 394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for i in range(self.adaptor.getChildCount(t)): 395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child = self.adaptor.getChild(t, i) 396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self._index(child, m) 397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def find(self, tree, what): 400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """Return a list of matching token. 401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver what may either be an integer specifzing the token type to find or 403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver a string with a pattern that must be matched. 404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if isinstance(what, (int, long)): 408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return self._findTokenType(tree, what) 409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elif isinstance(what, basestring): 411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return self._findPattern(tree, what) 412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else: 414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver raise TypeError("'what' must be string or integer") 415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def _findTokenType(self, t, ttype): 418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """Return a List of tree nodes with token type ttype""" 419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodes = [] 421324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def visitor(tree, parent, childIndex, labels): 423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodes.append(tree) 424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.visit(t, ttype, visitor) 426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return nodes 428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def _findPattern(self, t, pattern): 431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """Return a List of subtrees matching pattern.""" 432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver subtrees = [] 434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # Create a TreePattern from the pattern 436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenizer = TreePatternLexer(pattern) 437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parser = TreePatternParser(tokenizer, self, TreePatternTreeAdaptor()) 438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tpattern = parser.pattern() 439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # don't allow invalid patterns 441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tpattern is None or tpattern.isNil() 442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver or isinstance(tpattern, WildcardTreePattern)): 443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return None 444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver rootTokenType = tpattern.getType() 446324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 447324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def visitor(tree, parent, childIndex, label): 448324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self._parse(tree, tpattern, None): 449324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver subtrees.append(tree) 450324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 451324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.visit(t, rootTokenType, visitor) 452324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 453324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return subtrees 454324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 455324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 456324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def visit(self, tree, what, visitor): 457324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """Visit every node in tree matching what, invoking the visitor. 458324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 459324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver If what is a string, it is parsed as a pattern and only matching 460324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver subtrees will be visited. 461324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver The implementation uses the root node of the pattern in combination 462324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver with visit(t, ttype, visitor) so nil-rooted patterns are not allowed. 463324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Patterns with wildcard roots are also not allowed. 464324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 465324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver If what is an integer, it is used as a token type and visit will match 466324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver all nodes of that type (this is faster than the pattern match). 467324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver The labels arg of the visitor action method is never set (it's None) 468324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver since using a token type rather than a pattern doesn't let us set a 469324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label. 470324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 471324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 472324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if isinstance(what, (int, long)): 473324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self._visitType(tree, None, 0, what, visitor) 474324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 475324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elif isinstance(what, basestring): 476324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self._visitPattern(tree, what, visitor) 477324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 478324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else: 479324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver raise TypeError("'what' must be string or integer") 480324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 481324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 482324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def _visitType(self, t, parent, childIndex, ttype, visitor): 483324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """Do the recursive work for visit""" 484324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 485324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if t is None: 486324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 487324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 488324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.adaptor.getType(t) == ttype: 489324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver visitor(t, parent, childIndex, None) 490324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 491324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for i in range(self.adaptor.getChildCount(t)): 492324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child = self.adaptor.getChild(t, i) 493324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self._visitType(child, t, i, ttype, visitor) 494324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 495324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 496324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def _visitPattern(self, tree, pattern, visitor): 497324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 498324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver For all subtrees that match the pattern, execute the visit action. 499324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 500324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 501324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # Create a TreePattern from the pattern 502324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenizer = TreePatternLexer(pattern) 503324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parser = TreePatternParser(tokenizer, self, TreePatternTreeAdaptor()) 504324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tpattern = parser.pattern() 505324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 506324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # don't allow invalid patterns 507324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tpattern is None or tpattern.isNil() 508324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver or isinstance(tpattern, WildcardTreePattern)): 509324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 510324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 511324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver rootTokenType = tpattern.getType() 512324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 513324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def rootvisitor(tree, parent, childIndex, labels): 514324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labels = {} 515324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self._parse(tree, tpattern, labels): 516324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver visitor(tree, parent, childIndex, labels) 517324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 518324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.visit(tree, rootTokenType, rootvisitor) 519324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 520324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 521324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def parse(self, t, pattern, labels=None): 522324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 523324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Given a pattern like (ASSIGN %lhs:ID %rhs:.) with optional labels 524324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver on the various nodes and '.' (dot) as the node/subtree wildcard, 525324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true if the pattern matches and fill the labels Map with 526324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver the labels pointing at the appropriate nodes. Return false if 527324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver the pattern is malformed or the tree does not match. 528324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 529324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver If a node specifies a text arg in pattern, then that must match 530324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for that node in t. 531324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 532324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 533324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokenizer = TreePatternLexer(pattern) 534324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parser = TreePatternParser(tokenizer, self, TreePatternTreeAdaptor()) 535324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tpattern = parser.pattern() 536324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 537324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return self._parse(t, tpattern, labels) 538324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 539324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 540324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def _parse(self, t1, tpattern, labels): 541324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 542324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Do the work for parse. Check to see if the tpattern fits the 543324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver structure and token types in t1. Check text if the pattern has 544324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver text arguments on nodes. Fill labels map with pointers to nodes 545324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver in tree matched against nodes in pattern with labels. 546324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 547324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 548324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # make sure both are non-null 549324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if t1 is None or tpattern is None: 550324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return False 551324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 552324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # check roots (wildcard matches anything) 553324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if not isinstance(tpattern, WildcardTreePattern): 554324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if self.adaptor.getType(t1) != tpattern.getType(): 555324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return False 556324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 557324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # if pattern has text, check node text 558324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (tpattern.hasTextArg 559324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver and self.adaptor.getText(t1) != tpattern.getText()): 560324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return False 561324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 562324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if tpattern.label is not None and labels is not None: 563324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # map label in pattern to node in t1 564324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labels[tpattern.label] = t1 565324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 566324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # check children 567324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n1 = self.adaptor.getChildCount(t1) 568324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n2 = tpattern.getChildCount() 569324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if n1 != n2: 570324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return False 571324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 572324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for i in range(n1): 573324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child1 = self.adaptor.getChild(t1, i) 574324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child2 = tpattern.getChild(i) 575324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if not self._parse(child1, child2, labels): 576324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return False 577324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 578324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return True 579324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 580324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 581324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def equals(self, t1, t2, adaptor=None): 582324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 583324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Compare t1 and t2; return true if token types/text, structure match 584324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver exactly. 585324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver The trees are examined in their entirety so that (A B) does not match 586324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (A B C) nor (A (B C)). 587324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 588324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 589324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if adaptor is None: 590324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver adaptor = self.adaptor 591324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 592324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return self._equals(t1, t2, adaptor) 593324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 594324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 595324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def _equals(self, t1, t2, adaptor): 596324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # make sure both are non-null 597324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if t1 is None or t2 is None: 598324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return False 599324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 600324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # check roots 601324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if adaptor.getType(t1) != adaptor.getType(t2): 602324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return False 603324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 604324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if adaptor.getText(t1) != adaptor.getText(t2): 605324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return False 606324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 607324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # check children 608324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n1 = adaptor.getChildCount(t1) 609324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n2 = adaptor.getChildCount(t2) 610324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if n1 != n2: 611324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return False 612324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 613324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for i in range(n1): 614324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child1 = adaptor.getChild(t1, i) 615324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child2 = adaptor.getChild(t2, i) 616324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if not self._equals(child1, child2, adaptor): 617324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return False 618324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 619324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return True 620