<s> """<STR_LIT>""" <EOL> from antlr3 . constants import INVALID_TOKEN_TYPE <EOL> from antlr3 . tokens import CommonToken <EOL> from antlr3 . tree import CommonTree , CommonTreeAdaptor <EOL> def computeTokenTypes ( tokenNames ) : <EOL> """<STR_LIT>""" <EOL> if tokenNames is None : <EOL> return { } <EOL> return dict ( ( name , type ) for type , name in enumerate ( tokenNames ) ) <EOL> EOF = - <NUM_LIT:1> <EOL> BEGIN = <NUM_LIT:1> <EOL> END = <NUM_LIT:2> <EOL> ID = <NUM_LIT:3> <EOL> ARG = <NUM_LIT:4> <EOL> PERCENT = <NUM_LIT:5> <EOL> COLON = <NUM_LIT:6> <EOL> DOT = <NUM_LIT:7> <EOL> class TreePatternLexer ( object ) : <EOL> def __init__ ( self , pattern ) : <EOL> self . pattern = pattern <EOL> self . p = - <NUM_LIT:1> <EOL> self . c = None <EOL> self . n = len ( pattern ) <EOL> self . sval = None <EOL> self . error = False <EOL> self . consume ( ) <EOL> __idStartChar = frozenset ( <EOL> '<STR_LIT>' <EOL> ) <EOL> __idChar = __idStartChar | frozenset ( '<STR_LIT>' ) <EOL> def nextToken ( self ) : <EOL> self . sval = "<STR_LIT>" <EOL> while self . c != EOF : <EOL> if self . c in ( '<STR_LIT:U+0020>' , '<STR_LIT:\n>' , '<STR_LIT:\r>' , '<STR_LIT:\t>' ) : <EOL> self . consume ( ) <EOL> continue <EOL> if self . c in self . __idStartChar : <EOL> self . sval += self . c <EOL> self . consume ( ) <EOL> while self . c in self . __idChar : <EOL> self . sval += self . c <EOL> self . consume ( ) <EOL> return ID <EOL> if self . c == '<STR_LIT:(>' : <EOL> self . consume ( ) <EOL> return BEGIN <EOL> if self . c == '<STR_LIT:)>' : <EOL> self . consume ( ) <EOL> return END <EOL> if self . c == '<STR_LIT:%>' : <EOL> self . consume ( ) <EOL> return PERCENT <EOL> if self . c == '<STR_LIT::>' : <EOL> self . consume ( ) <EOL> return COLON <EOL> if self . c == '<STR_LIT:.>' : <EOL> self . consume ( ) <EOL> return DOT <EOL> if self . c == '<STR_LIT:[>' : <EOL> self . consume ( ) <EOL> while self . c != '<STR_LIT:]>' : <EOL> if self . c == '<STR_LIT:\\>' : <EOL> self . consume ( ) <EOL> if self . c != '<STR_LIT:]>' : <EOL> self . sval += '<STR_LIT:\\>' <EOL> self . sval += self . c <EOL> else : <EOL> self . sval += self . c <EOL> self . consume ( ) <EOL> self . consume ( ) <EOL> return ARG <EOL> self . consume ( ) <EOL> self . error = True <EOL> return EOF <EOL> return EOF <EOL> def consume ( self ) : <EOL> self . p += <NUM_LIT:1> <EOL> if self . p >= self . n : <EOL> self . c = EOF <EOL> else : <EOL> self . c = self . pattern [ self . p ] <EOL> class TreePatternParser ( object ) : <EOL> def __init__ ( self , tokenizer , wizard , adaptor ) : <EOL> self . tokenizer = tokenizer <EOL> self . wizard = wizard <EOL> self . adaptor = adaptor <EOL> self . ttype = tokenizer . nextToken ( ) <EOL> def pattern ( self ) : <EOL> if self . ttype == BEGIN : <EOL> return self . parseTree ( ) <EOL> elif self . ttype == ID : <EOL> node = self . parseNode ( ) <EOL> if self . ttype == EOF : <EOL> return node <EOL> return None <EOL> return None <EOL> def parseTree ( self ) : <EOL> if self . ttype != BEGIN : <EOL> return None <EOL> self . ttype = self . tokenizer . nextToken ( ) <EOL> root = self . parseNode ( ) <EOL> if root is None : <EOL> return None <EOL> while self . ttype in ( BEGIN , ID , PERCENT , DOT ) : <EOL> if self . ttype == BEGIN : <EOL> subtree = self . parseTree ( ) <EOL> self . adaptor . addChild ( root , subtree ) <EOL> else : <EOL> child = self . parseNode ( ) <EOL> if child is None : <EOL> return None <EOL> self . adaptor . addChild ( root , child ) <EOL> if self . ttype != END : <EOL> return None <EOL> self . ttype = self . tokenizer . nextToken ( ) <EOL> return root <EOL> def parseNode ( self ) : <EOL> label = None <EOL> if self . ttype == PERCENT : <EOL> self . ttype = self . tokenizer . nextToken ( ) <EOL> if self . ttype != ID : <EOL> return None <EOL> label = self . tokenizer . sval <EOL> self . ttype = self . tokenizer . nextToken ( ) <EOL> if self . ttype != COLON : <EOL> return None <EOL> self . ttype = self . tokenizer . nextToken ( ) <EOL> if self . ttype == DOT : <EOL> self . ttype = self . tokenizer . nextToken ( ) <EOL> wildcardPayload = CommonToken ( <NUM_LIT:0> , "<STR_LIT:.>" ) <EOL> node = WildcardTreePattern ( wildcardPayload ) <EOL> if label is not None : <EOL> node . label = label <EOL> return node <EOL> if self . ttype != ID : <EOL> return None <EOL> tokenName = self . tokenizer . sval <EOL> self . ttype = self . tokenizer . nextToken ( ) <EOL> if tokenName == "<STR_LIT>" : <EOL> return self . adaptor . nil ( ) <EOL> text = tokenName <EOL> arg = None <EOL> if self . ttype == ARG : <EOL> arg = self . tokenizer . sval <EOL> text = arg <EOL> self . ttype = self . tokenizer . nextToken ( ) <EOL> treeNodeType = self . wizard . getTokenType ( tokenName ) <EOL> if treeNodeType == INVALID_TOKEN_TYPE : <EOL> return None <EOL> node = self . adaptor . createFromType ( treeNodeType , text ) <EOL> if label is not None and isinstance ( node , TreePattern ) : <EOL> node . label = label <EOL> if arg is not None and isinstance ( node , TreePattern ) : <EOL> node . hasTextArg = True <EOL> return node <EOL> class TreePattern ( CommonTree ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , payload ) : <EOL> CommonTree . __init__ ( self , payload ) <EOL> self . label = None <EOL> self . hasTextArg = None <EOL> def toString ( self ) : <EOL> if self . label is not None : <EOL> return '<STR_LIT:%>' + self . label + '<STR_LIT::>' + CommonTree . toString ( self ) <EOL> else : <EOL> return CommonTree . toString ( self ) <EOL> class WildcardTreePattern ( TreePattern ) : <EOL> pass <EOL> class TreePatternTreeAdaptor ( CommonTreeAdaptor ) : <EOL> """<STR_LIT>""" <EOL> def createWithPayload ( self , payload ) : <EOL> return TreePattern ( payload ) <EOL> class TreeWizard ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , adaptor = None , tokenNames = None , typeMap = None ) : <EOL> self . adaptor = adaptor <EOL> if typeMap is None : <EOL> self . tokenNameToTypeMap = computeTokenTypes ( tokenNames ) <EOL> else : <EOL> if tokenNames is not None : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> self . tokenNameToTypeMap = typeMap <EOL> def getTokenType ( self , tokenName ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> return self . tokenNameToTypeMap [ tokenName ] <EOL> except KeyError : <EOL> return INVALID_TOKEN_TYPE <EOL> def create ( self , pattern ) : <EOL> """<STR_LIT>""" <EOL> tokenizer = TreePatternLexer ( pattern ) <EOL> parser = TreePatternParser ( tokenizer , self , self . adaptor ) <EOL> return parser . pattern ( ) <EOL> def index ( self , tree ) : <EOL> """<STR_LIT>""" <EOL> m = { } <EOL> self . _index ( tree , m ) <EOL> return m <EOL> def _index ( self , t , m ) : <EOL> """<STR_LIT>""" <EOL> if t is None : <EOL> return <EOL> ttype = self . adaptor . getType ( t ) <EOL> elements = m . get ( ttype ) <EOL> if elements is None : <EOL> m [ ttype ] = elements = [ ] <EOL> elements . append ( t ) <EOL> for i in range ( self . adaptor . getChildCount ( t ) ) : <EOL> child = self . adaptor . getChild ( t , i ) <EOL> self . _index ( child , m ) <EOL> def find ( self , tree , what ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( what , ( int , long ) ) : <EOL> return self . _findTokenType ( tree , what ) <EOL> elif isinstance ( what , basestring ) : <EOL> return self . _findPattern ( tree , what ) <EOL> else : <EOL> raise TypeError ( "<STR_LIT>" ) <EOL> def _findTokenType ( self , t , ttype ) : <EOL> """<STR_LIT>""" <EOL> nodes = [ ] <EOL> def visitor ( tree , parent , childIndex , labels ) : <EOL> nodes . append ( tree ) <EOL> self . visit ( t , ttype , visitor ) <EOL> return nodes <EOL> def _findPattern ( self , t , pattern ) : <EOL> """<STR_LIT>""" <EOL> subtrees = [ ] <EOL> tokenizer = TreePatternLexer ( pattern ) <EOL> parser = TreePatternParser ( tokenizer , self , TreePatternTreeAdaptor ( ) ) <EOL> tpattern = parser . pattern ( ) <EOL> if ( tpattern is None or tpattern . isNil ( ) <EOL> or isinstance ( tpattern , WildcardTreePattern ) ) : <EOL> return None <EOL> rootTokenType = tpattern . getType ( ) <EOL> def visitor ( tree , parent , childIndex , label ) : <EOL> if self . _parse ( tree , tpattern , None ) : <EOL> subtrees . append ( tree ) <EOL> self . visit ( t , rootTokenType , visitor ) <EOL> return subtrees <EOL> def visit ( self , tree , what , visitor ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( what , ( int , long ) ) : <EOL> self . _visitType ( tree , None , <NUM_LIT:0> , what , visitor ) <EOL> elif isinstance ( what , basestring ) : <EOL> self . _visitPattern ( tree , what , visitor ) <EOL> else : <EOL> raise TypeError ( "<STR_LIT>" ) <EOL> def _visitType ( self , t , parent , childIndex , ttype , visitor ) : <EOL> """<STR_LIT>""" <EOL> if t is None : <EOL> return <EOL> if self . adaptor . getType ( t ) == ttype : <EOL> visitor ( t , parent , childIndex , None ) <EOL> for i in range ( self . adaptor . getChildCount ( t ) ) : <EOL> child = self . adaptor . getChild ( t , i ) <EOL> self . _visitType ( child , t , i , ttype , visitor ) <EOL> def _visitPattern ( self , tree , pattern , visitor ) : <EOL> """<STR_LIT>""" <EOL> tokenizer = TreePatternLexer ( pattern ) <EOL> parser = TreePatternParser ( tokenizer , self , TreePatternTreeAdaptor ( ) ) <EOL> tpattern = parser . pattern ( ) <EOL> if ( tpattern is None or tpattern . isNil ( ) <EOL> or isinstance ( tpattern , WildcardTreePattern ) ) : <EOL> return <EOL> rootTokenType = tpattern . getType ( ) <EOL> def rootvisitor ( tree , parent , childIndex , labels ) : <EOL> labels = { } <EOL> if self . _parse ( tree , tpattern , labels ) : <EOL> visitor ( tree , parent , childIndex , labels ) <EOL> self . visit ( tree , rootTokenType , rootvisitor ) <EOL> def parse ( self , t , pattern , labels = None ) : <EOL> """<STR_LIT>""" <EOL> tokenizer = TreePatternLexer ( pattern ) <EOL> parser = TreePatternParser ( tokenizer , self , TreePatternTreeAdaptor ( ) ) <EOL> tpattern = parser . pattern ( ) <EOL> return self . _parse ( t , tpattern , labels ) <EOL> def _parse ( self , t1 , t2 , labels ) : <EOL> """<STR_LIT>""" <EOL> if t1 is None or t2 is None : <EOL> return False <EOL> if not isinstance ( t2 , WildcardTreePattern ) : <EOL> if self . adaptor . getType ( t1 ) != t2 . getType ( ) : <EOL> return False <EOL> if t2 . hasTextArg and self . adaptor . getText ( t1 ) != t2 . getText ( ) : <EOL> return False <EOL> if t2 . label is not None and labels is not None : <EOL> labels [ t2 . label ] = t1 <EOL> n1 = self . adaptor . getChildCount ( t1 ) <EOL> n2 = t2 . getChildCount ( ) <EOL> if n1 != n2 : <EOL> return False <EOL> for i in range ( n1 ) : <EOL> child1 = self . adaptor . getChild ( t1 , i ) <EOL> child2 = t2 . getChild ( i ) <EOL> if not self . _parse ( child1 , child2 , labels ) : <EOL> return False <EOL> return True <EOL> def equals ( self , t1 , t2 , adaptor = None ) : <EOL> """<STR_LIT>""" <EOL> if adaptor is None : <EOL> adaptor = self . adaptor <EOL> return self . _equals ( t1 , t2 , adaptor ) <EOL> def _equals ( self , t1 , t2 , adaptor ) : <EOL> if t1 is None or t2 is None : <EOL> return False <EOL> if adaptor . getType ( t1 ) != adaptor . getType ( t2 ) : <EOL> return False <EOL> if adaptor . getText ( t1 ) != adaptor . getText ( t2 ) : <EOL> return False <EOL> n1 = adaptor . getChildCount ( t1 ) <EOL> n2 = adaptor . getChildCount ( t2 ) <EOL> if n1 != n2 : <EOL> return False <EOL> for i in range ( n1 ) : <EOL> child1 = adaptor . getChild ( t1 , i ) <EOL> child2 = adaptor . getChild ( t2 , i ) <EOL> if not self . _equals ( child1 , child2 , adaptor ) : <EOL> return False <EOL> return True </s>
