Lichen

compiler/transformer.py

934:2989aab1b4f7
7 months ago Paul Boddie Renamed the utf8string class to unicode, eliminating the unicode function. This means that the simple case of merely returning an object if it is already a Unicode object no longer occurs when using the unicode callable, but such behaviour might be better supported with more general customised instantiation functionality.
     1 """Parse tree transformation module.     2      3 Transforms Python source code into an abstract syntax tree (AST)     4 defined in the ast module.     5      6 The simplest ways to invoke this module are via parse and parseFile.     7 parse(buf) -> AST     8 parseFile(path) -> AST     9 """    10     11 # Original version written by Greg Stein (gstein@lyra.org)    12 #                         and Bill Tutt (rassilon@lima.mudlib.org)    13 # February 1997.    14 #    15 # Modifications and improvements for Python 2.0 by Jeremy Hylton and    16 # Mark Hammond    17 #    18 # Some fixes to try to have correct line number on almost all nodes    19 # (except Module, Discard and Stmt) added by Sylvain Thenault    20 #    21 # Portions of this file are:    22 # Copyright (C) 1997-1998 Greg Stein. All Rights Reserved.    23 #    24 # This module is provided under a BSD-ish license. See    25 #   http://www.opensource.org/licenses/bsd-license.html    26 # and replace OWNER, ORGANIZATION, and YEAR as appropriate.    27     28 from compiler.ast import *    29 from pyparser.pygram import syms as symbol, sym_name, tokens as token, tok_name    30 import pyparser.pyparse as parser    31     32 class WalkerError(StandardError):    33     pass    34     35 from compiler.consts import CO_VARARGS, CO_VARKEYWORDS    36 from compiler.consts import OP_ASSIGN, OP_DELETE, OP_APPLY    37     38 def parseFile(path):    39     f = open(path, "U")    40     # XXX The parser API tolerates files without a trailing newline,    41     # but not strings without a trailing newline.  Always add an extra    42     # newline to the file contents, since we're going through the string    43     # version of the API.    44     src = f.read() + "\n"    45     f.close()    46     return parse(src)    47     48 def parse(buf, mode="exec"):    49     if mode == "exec" or mode == "single":    50         return Transformer().parsesuite(buf)    51     elif mode == "eval":    52         return Transformer().parseexpr(buf)    53     else:    54         raise ValueError("compile() arg 3 must be"    55                          " 'exec' or 'eval' or 'single'")    56     57 def extractLineNo(ast):    58     if not isinstance(ast[1], tuple):    59         # get a terminal node    60         return ast[2]    61     for child in ast[1:]:    62         if isinstance(child, tuple):    63             lineno = extractLineNo(child)    64             if lineno is not None:    65                 return lineno    66     67 def Node(*args):    68     kind = args[0]    69     if kind in nodes:    70         try:    71             return nodes[kind](*args[1:])    72         except TypeError:    73             print nodes[kind], len(args), args    74             raise    75     else:    76         raise WalkerError, "Can't find appropriate Node type: %s" % str(args)    77         #return apply(ast.Node, args)    78     79 class Transformer:    80     """Utility object for transforming Python parse trees.    81     82     Exposes the following methods:    83         tree = transform(ast_tree)    84         tree = parsesuite(text)    85         tree = parseexpr(text)    86         tree = parsefile(fileob | filename)    87     """    88     89     def __init__(self):    90         self._dispatch = {}    91         for value, name in sym_name.items():    92             if hasattr(self, name):    93                 self._dispatch[value] = getattr(self, name)    94         self._dispatch[token["NEWLINE"]] = self.com_NEWLINE    95         self._atom_dispatch = {token["LPAR"]: self.atom_lpar,    96                                token["LSQB"]: self.atom_lsqb,    97                                token["LBRACE"]: self.atom_lbrace,    98                                token["BACKQUOTE"]: self.atom_backquote,    99                                token["NUMBER"]: self.atom_number,   100                                token["STRING"]: self.atom_string,   101                                token["NAME"]: self.atom_name,   102                                }   103         self.encoding = None   104    105     def transform(self, tree):   106         """Transform an AST into a modified parse tree."""   107         if not (isinstance(tree, tuple) or isinstance(tree, list)):   108             tree = parser.st2tuple(tree, line_info=1)   109         return self.compile_node(tree)   110    111     def parsesuite(self, text):   112         """Return a modified parse tree for the given suite text."""   113         return self.transform(parser.suite(text))   114    115     def parseexpr(self, text):   116         """Return a modified parse tree for the given expression text."""   117         return self.transform(parser.expr(text))   118    119     def parsefile(self, file):   120         """Return a modified parse tree for the contents of the given file."""   121         if type(file) == type(''):   122             file = open(file)   123         return self.parsesuite(file.read())   124    125     # --------------------------------------------------------------   126     #   127     # PRIVATE METHODS   128     #   129    130     def compile_node(self, node):   131         ### emit a line-number node?   132         n = node[0]   133    134         if n == symbol["encoding_decl"]:   135             self.encoding = node[2]   136             node = node[1]   137             n = node[0]   138    139         if n == symbol["single_input"]:   140             return self.single_input(node[1:])   141         if n == symbol["file_input"]:   142             return self.file_input(node[1:])   143         if n == symbol["eval_input"]:   144             return self.eval_input(node[1:])   145         if n == symbol["lambdef"]:   146             return self.lambdef(node[1:])   147         if n == symbol["funcdef"]:   148             return self.funcdef(node[1:])   149         if n == symbol["classdef"]:   150             return self.classdef(node[1:])   151    152         raise WalkerError, ('unexpected node type', n)   153    154     def single_input(self, node):   155         ### do we want to do anything about being "interactive" ?   156    157         # NEWLINE | simple_stmt | compound_stmt NEWLINE   158         n = node[0][0]   159         if n != token["NEWLINE"]:   160             return self.com_stmt(node[0])   161    162         return Pass()   163    164     def file_input(self, nodelist):   165         doc = self.get_docstring(nodelist, symbol["file_input"])   166         if doc is not None:   167             i = 1   168         else:   169             i = 0   170         stmts = []   171         for node in nodelist[i:]:   172             if node[0] != token["ENDMARKER"] and node[0] != token["NEWLINE"]:   173                 self.com_append_stmt(stmts, node)   174         return Module(doc, Stmt(stmts))   175    176     def eval_input(self, nodelist):   177         # from the built-in function input()   178         ### is this sufficient?   179         return Expression(self.com_node(nodelist[0]))   180    181     def funcdef(self, nodelist):   182         #          -5    -4   -3         -2  -1   183         # funcdef: 'def' NAME parameters ':' suite   184         # parameters: '(' [varargslist] ')'   185    186         assert len(nodelist) == 5   187         decorators = None   188    189         lineno = nodelist[-4][2]   190         name = nodelist[-4][1]   191         args = nodelist[-3][2]   192    193         if args[0] == symbol["varargslist"]:   194             names, defaults, flags = self.com_arglist(args[1:])   195         else:   196             names = defaults = ()   197             flags = 0   198         doc = self.get_docstring(nodelist[-1])   199    200         # code for function   201         code = self.com_node(nodelist[-1])   202    203         if doc is not None:   204             assert isinstance(code, Stmt)   205             assert isinstance(code.nodes[0], Discard)   206             del code.nodes[0]   207         return Function(decorators, name, names, defaults, flags, doc, code,   208                      lineno=lineno)   209    210     def lambdef(self, nodelist):   211         # lambdef: 'lambda' [varargslist] ':' test   212         if nodelist[2][0] == symbol["varargslist"]:   213             names, defaults, flags = self.com_arglist(nodelist[2][1:])   214         else:   215             names = defaults = ()   216             flags = 0   217    218         # code for lambda   219         code = self.com_node(nodelist[-1])   220    221         return Lambda(names, defaults, flags, code, lineno=nodelist[1][2])   222     old_lambdef = lambdef   223    224     def classdef(self, nodelist):   225         # classdef: 'class' NAME ['(' [testlist] ')'] ':' suite   226    227         name = nodelist[1][1]   228         doc = self.get_docstring(nodelist[-1])   229         if nodelist[2][0] == token["COLON"]:   230             bases = []   231         elif nodelist[3][0] == token["RPAR"]:   232             bases = []   233         else:   234             bases = self.com_bases(nodelist[3])   235    236         # code for class   237         code = self.com_node(nodelist[-1])   238    239         if doc is not None:   240             assert isinstance(code, Stmt)   241             assert isinstance(code.nodes[0], Discard)   242             del code.nodes[0]   243    244         return Class(name, bases, doc, code, lineno=nodelist[1][2])   245    246     def stmt(self, nodelist):   247         return self.com_stmt(nodelist[0])   248    249     small_stmt = stmt   250     flow_stmt = stmt   251     compound_stmt = stmt   252    253     def simple_stmt(self, nodelist):   254         # small_stmt (';' small_stmt)* [';'] NEWLINE   255         stmts = []   256         for i in range(0, len(nodelist), 2):   257             self.com_append_stmt(stmts, nodelist[i])   258         return Stmt(stmts)   259    260     def parameters(self, nodelist):   261         raise WalkerError   262    263     def varargslist(self, nodelist):   264         raise WalkerError   265    266     def fpdef(self, nodelist):   267         raise WalkerError   268    269     def fplist(self, nodelist):   270         raise WalkerError   271    272     def dotted_name(self, nodelist):   273         raise WalkerError   274    275     def comp_op(self, nodelist):   276         raise WalkerError   277    278     def trailer(self, nodelist):   279         raise WalkerError   280    281     def sliceop(self, nodelist):   282         raise WalkerError   283    284     def argument(self, nodelist):   285         raise WalkerError   286    287     # --------------------------------------------------------------   288     #   289     # STATEMENT NODES  (invoked by com_node())   290     #   291    292     def expr_stmt(self, nodelist):   293         # augassign testlist | testlist ('=' testlist)*   294         en = nodelist[-1]   295         exprNode = self.lookup_node(en)(en[1:])   296         if len(nodelist) == 1:   297             return Discard(exprNode, lineno=exprNode.lineno)   298         if nodelist[1][0] == token["EQUAL"]:   299             nodesl = []   300             for i in range(0, len(nodelist) - 2, 2):   301                 nodesl.append(self.com_assign(nodelist[i], OP_ASSIGN))   302             return Assign(nodesl, exprNode, lineno=nodelist[1][2])   303         else:   304             lval = self.com_augassign(nodelist[0])   305             op = self.com_augassign_op(nodelist[1])   306             return AugAssign(lval, op[1], exprNode, lineno=op[2])   307         raise WalkerError, "can't get here"   308    309     def print_stmt(self, nodelist):   310         # print ([ test (',' test)* [','] ] | '>>' test [ (',' test)+ [','] ])   311         items = []   312         if len(nodelist) == 1:   313             start = 1   314             dest = None   315         elif nodelist[1][0] == token["RIGHTSHIFT"]:   316             assert len(nodelist) == 3 \   317                    or nodelist[3][0] == token["COMMA"]   318             dest = self.com_node(nodelist[2])   319             start = 4   320         else:   321             dest = None   322             start = 1   323         for i in range(start, len(nodelist), 2):   324             items.append(self.com_node(nodelist[i]))   325         if nodelist[-1][0] == token["COMMA"]:   326             return Print(items, dest, lineno=nodelist[0][2])   327         return Printnl(items, dest, lineno=nodelist[0][2])   328    329     def del_stmt(self, nodelist):   330         return self.com_assign(nodelist[1], OP_DELETE)   331    332     def pass_stmt(self, nodelist):   333         return Pass(lineno=nodelist[0][2])   334    335     def break_stmt(self, nodelist):   336         return Break(lineno=nodelist[0][2])   337    338     def continue_stmt(self, nodelist):   339         return Continue(lineno=nodelist[0][2])   340    341     def return_stmt(self, nodelist):   342         # return: [testlist]   343         if len(nodelist) < 2:   344             return Return(Const(None), lineno=nodelist[0][2])   345         return Return(self.com_node(nodelist[1]), lineno=nodelist[0][2])   346    347     def raise_stmt(self, nodelist):   348         # raise: [test [',' test [',' test]]]   349         if len(nodelist) > 5:   350             expr3 = self.com_node(nodelist[5])   351         else:   352             expr3 = None   353         if len(nodelist) > 3:   354             expr2 = self.com_node(nodelist[3])   355         else:   356             expr2 = None   357         if len(nodelist) > 1:   358             expr1 = self.com_node(nodelist[1])   359         else:   360             expr1 = None   361         return Raise(expr1, expr2, expr3, lineno=nodelist[0][2])   362    363     def import_stmt(self, nodelist):   364         # import_stmt: import_name | import_from   365         assert len(nodelist) == 1   366         return self.com_node(nodelist[0])   367    368     def import_name(self, nodelist):   369         # import_name: 'import' dotted_as_names   370         return Import(self.com_dotted_as_names(nodelist[1]),   371                       lineno=nodelist[0][2])   372    373     def import_from(self, nodelist):   374         # import_from: 'from' ('.'* dotted_name | '.') 'import' ('*' |   375         #    '(' import_as_names ')' | import_as_names)   376         assert nodelist[0][1] == 'from'   377         idx = 1   378         while nodelist[idx][1] == '.':   379             idx += 1   380         level = idx - 1   381         if nodelist[idx][0] == symbol["dotted_name"]:   382             fromname = self.com_dotted_name(nodelist[idx])   383             idx += 1   384         else:   385             fromname = ""   386         assert nodelist[idx][1] == 'import'   387         if nodelist[idx + 1][0] == token["STAR"]:   388             return From(fromname, [('*', None)], level,   389                         lineno=nodelist[0][2])   390         else:   391             node = nodelist[idx + 1 + (nodelist[idx + 1][0] == token["LPAR"])]   392             return From(fromname, self.com_import_as_names(node), level,   393                         lineno=nodelist[0][2])   394    395     def global_stmt(self, nodelist):   396         # global: NAME (',' NAME)*   397         names = []   398         for i in range(1, len(nodelist), 2):   399             names.append(nodelist[i][1])   400         return Global(names, lineno=nodelist[0][2])   401    402     def exec_stmt(self, nodelist):   403         # exec_stmt: 'exec' expr ['in' expr [',' expr]]   404         expr1 = self.com_node(nodelist[1])   405         if len(nodelist) >= 4:   406             expr2 = self.com_node(nodelist[3])   407             if len(nodelist) >= 6:   408                 expr3 = self.com_node(nodelist[5])   409             else:   410                 expr3 = None   411         else:   412             expr2 = expr3 = None   413    414         return Exec(expr1, expr2, expr3, lineno=nodelist[0][2])   415    416     def assert_stmt(self, nodelist):   417         # 'assert': test, [',' test]   418         expr1 = self.com_node(nodelist[1])   419         if (len(nodelist) == 4):   420             expr2 = self.com_node(nodelist[3])   421         else:   422             expr2 = None   423         return Assert(expr1, expr2, lineno=nodelist[0][2])   424    425     def if_stmt(self, nodelist):   426         # if: test ':' suite ('elif' test ':' suite)* ['else' ':' suite]   427         tests = []   428         for i in range(0, len(nodelist) - 3, 4):   429             testNode = self.com_node(nodelist[i + 1])   430             suiteNode = self.com_node(nodelist[i + 3])   431             tests.append((testNode, suiteNode))   432    433         if len(nodelist) % 4 == 3:   434             elseNode = self.com_node(nodelist[-1])   435 ##      elseNode.lineno = nodelist[-1][1][2]   436         else:   437             elseNode = None   438         return If(tests, elseNode, lineno=nodelist[0][2])   439    440     def while_stmt(self, nodelist):   441         # 'while' test ':' suite ['else' ':' suite]   442    443         testNode = self.com_node(nodelist[1])   444         bodyNode = self.com_node(nodelist[3])   445    446         if len(nodelist) > 4:   447             elseNode = self.com_node(nodelist[6])   448         else:   449             elseNode = None   450    451         return While(testNode, bodyNode, elseNode, lineno=nodelist[0][2])   452    453     def for_stmt(self, nodelist):   454         # 'for' exprlist 'in' exprlist ':' suite ['else' ':' suite]   455    456         assignNode = self.com_assign(nodelist[1], OP_ASSIGN)   457         listNode = self.com_node(nodelist[3])   458         bodyNode = self.com_node(nodelist[5])   459    460         if len(nodelist) > 8:   461             elseNode = self.com_node(nodelist[8])   462         else:   463             elseNode = None   464    465         return For(assignNode, listNode, bodyNode, elseNode,   466                    lineno=nodelist[0][2])   467    468     def try_stmt(self, nodelist):   469         return self.com_try_except_finally(nodelist)   470    471     def suite(self, nodelist):   472         # simple_stmt | NEWLINE INDENT NEWLINE* (stmt NEWLINE*)+ DEDENT   473         if len(nodelist) == 1:   474             return self.com_stmt(nodelist[0])   475    476         stmts = []   477         for node in nodelist:   478             if node[0] == symbol["stmt"]:   479                 self.com_append_stmt(stmts, node)   480         return Stmt(stmts)   481    482     # --------------------------------------------------------------   483     #   484     # EXPRESSION NODES  (invoked by com_node())   485     #   486    487     def testlist(self, nodelist):   488         # testlist: expr (',' expr)* [',']   489         # testlist_safe: test [(',' test)+ [',']]   490         # exprlist: expr (',' expr)* [',']   491         return self.com_binary(Tuple, nodelist)   492    493     testlist_safe = testlist # XXX   494     testlist1 = testlist   495     exprlist = testlist   496    497     def testlist_comp(self, nodelist):   498         # test ( (',' test)* [','] )   499         assert nodelist[0][0] == symbol["test"]   500         return self.testlist(nodelist)   501    502     def test(self, nodelist):   503         # or_test | lambdef   504         if len(nodelist) == 1 and nodelist[0][0] == symbol["lambdef"]:   505             return self.lambdef(nodelist[0])   506         then = self.com_node(nodelist[0])   507         return then   508    509     def or_test(self, nodelist):   510         # and_test ('or' and_test)* | lambdef   511         if len(nodelist) == 1 and nodelist[0][0] == symbol["lambdef"]:   512             return self.lambdef(nodelist[0])   513         return self.com_binary(Or, nodelist)   514     old_test = or_test   515    516     def and_test(self, nodelist):   517         # not_test ('and' not_test)*   518         return self.com_binary(And, nodelist)   519    520     def not_test(self, nodelist):   521         # 'not' not_test | comparison   522         result = self.com_node(nodelist[-1])   523         if len(nodelist) == 2:   524             return Not(result, lineno=nodelist[0][2])   525         return result   526    527     def comparison(self, nodelist):   528         # comparison: expr (comp_op expr)*   529         node = self.com_node(nodelist[0])   530         if len(nodelist) == 1:   531             return node   532    533         results = []   534         for i in range(2, len(nodelist), 2):   535             nl = nodelist[i-1]   536    537             # comp_op: '<' | '>' | '=' | '>=' | '<=' | '<>' | '!=' | '=='   538             #          | 'in' | 'not' 'in' | 'is' | 'is' 'not'   539             n = nl[1]   540             if n[0] == token["NAME"]:   541                 type = n[1]   542                 if len(nl) == 3:   543                     if type == 'not':   544                         type = 'not in'   545                     else:   546                         type = 'is not'   547             else:   548                 type = _cmp_types[n[0]]   549    550             lineno = nl[1][2]   551             results.append((type, self.com_node(nodelist[i])))   552    553         # we need a special "compare" node so that we can distinguish   554         #   3 < x < 5   from    (3 < x) < 5   555         # the two have very different semantics and results (note that the   556         # latter form is always true)   557    558         return Compare(node, results, lineno=lineno)   559    560     def expr(self, nodelist):   561         # xor_expr ('|' xor_expr)*   562         return self.com_binary(Bitor, nodelist)   563    564     def xor_expr(self, nodelist):   565         # xor_expr ('^' xor_expr)*   566         return self.com_binary(Bitxor, nodelist)   567    568     def and_expr(self, nodelist):   569         # xor_expr ('&' xor_expr)*   570         return self.com_binary(Bitand, nodelist)   571    572     def shift_expr(self, nodelist):   573         # shift_expr ('<<'|'>>' shift_expr)*   574         node = self.com_node(nodelist[0])   575         for i in range(2, len(nodelist), 2):   576             right = self.com_node(nodelist[i])   577             if nodelist[i-1][0] == token["LEFTSHIFT"]:   578                 node = LeftShift([node, right], lineno=nodelist[1][2])   579             elif nodelist[i-1][0] == token["RIGHTSHIFT"]:   580                 node = RightShift([node, right], lineno=nodelist[1][2])   581             else:   582                 raise ValueError, "unexpected token: %s" % nodelist[i-1][0]   583         return node   584    585     def arith_expr(self, nodelist):   586         node = self.com_node(nodelist[0])   587         for i in range(2, len(nodelist), 2):   588             right = self.com_node(nodelist[i])   589             if nodelist[i-1][0] == token["PLUS"]:   590                 node = Add([node, right], lineno=nodelist[1][2])   591             elif nodelist[i-1][0] == token["MINUS"]:   592                 node = Sub([node, right], lineno=nodelist[1][2])   593             else:   594                 raise ValueError, "unexpected token: %s" % nodelist[i-1][0]   595         return node   596    597     def term(self, nodelist):   598         node = self.com_node(nodelist[0])   599         for i in range(2, len(nodelist), 2):   600             right = self.com_node(nodelist[i])   601             t = nodelist[i-1][0]   602             if t == token["STAR"]:   603                 node = Mul([node, right])   604             elif t == token["SLASH"]:   605                 node = Div([node, right])   606             elif t == token["PERCENT"]:   607                 node = Mod([node, right])   608             elif t == token["DOUBLESLASH"]:   609                 node = FloorDiv([node, right])   610             else:   611                 raise ValueError, "unexpected token: %s" % t   612             node.lineno = nodelist[1][2]   613         return node   614    615     def factor(self, nodelist):   616         elt = nodelist[0]   617         t = elt[0]   618         node = self.lookup_node(nodelist[-1])(nodelist[-1][1:])   619         # need to handle (unary op)constant here...   620         if t == token["PLUS"]:   621             return UnaryAdd(node, lineno=elt[2])   622         elif t == token["MINUS"]:   623             return UnarySub(node, lineno=elt[2])   624         elif t == token["TILDE"]:   625             node = Invert(node, lineno=elt[2])   626         return node   627    628     def power(self, nodelist):   629         # power: atom trailer* ('**' factor)*   630         node = self.com_node(nodelist[0])   631         for i in range(1, len(nodelist)):   632             elt = nodelist[i]   633             if elt[0] == token["DOUBLESTAR"]:   634                 return Power([node, self.com_node(nodelist[i+1])],   635                              lineno=elt[2])   636    637             node = self.com_apply_trailer(node, elt)   638    639         return node   640    641     def atom(self, nodelist):   642         return self._atom_dispatch[nodelist[0][0]](nodelist)   643    644     def atom_lpar(self, nodelist):   645         if nodelist[1][0] == token["RPAR"]:   646             return Tuple((), lineno=nodelist[0][2])   647         return self.com_node(nodelist[1])   648    649     def atom_lsqb(self, nodelist):   650         if nodelist[1][0] == token["RSQB"]:   651             return List((), lineno=nodelist[0][2])   652         return self.com_list_constructor(nodelist[1])   653    654     def atom_lbrace(self, nodelist):   655         if nodelist[1][0] == token["RBRACE"]:   656             return Dict((), lineno=nodelist[0][2])   657         return self.com_dictorsetmaker(nodelist[1])   658    659     def atom_backquote(self, nodelist):   660         return Backquote(self.com_node(nodelist[1]))   661    662     def atom_number(self, nodelist):   663         ### need to verify this matches compile.c   664         k = eval(nodelist[0][1])   665         return Const(k, nodelist[0][1], lineno=nodelist[0][2])   666    667     def decode_literal(self, lit):   668         if self.encoding:   669             # this is particularly fragile & a bit of a   670             # hack... changes in compile.c:parsestr and   671             # tokenizer.c must be reflected here.   672             if self.encoding != 'utf-8':   673                 lit = unicode(lit, 'utf-8').encode(self.encoding)   674             return eval("# coding: %s\n%s" % (self.encoding, lit))   675         else:   676             return eval(lit)   677    678     def atom_string(self, nodelist):   679         k = ''   680         l = []   681         for node in nodelist:   682             k += self.decode_literal(node[1])   683             l.append(node[1])   684         return Const(k, l, lineno=nodelist[0][2])   685    686     def atom_name(self, nodelist):   687         return Name(nodelist[0][1], lineno=nodelist[0][2])   688    689     # --------------------------------------------------------------   690     #   691     # INTERNAL PARSING UTILITIES   692     #   693    694     # The use of com_node() introduces a lot of extra stack frames,   695     # enough to cause a stack overflow compiling test.test_parser with   696     # the standard interpreter recursionlimit.  The com_node() is a   697     # convenience function that hides the dispatch details, but comes   698     # at a very high cost.  It is more efficient to dispatch directly   699     # in the callers.  In these cases, use lookup_node() and call the   700     # dispatched node directly.   701    702     def lookup_node(self, node):   703         return self._dispatch[node[0]]   704    705     def com_node(self, node):   706         # Note: compile.c has handling in com_node for del_stmt, pass_stmt,   707         #       break_stmt, stmt, small_stmt, flow_stmt, simple_stmt,   708         #       and compound_stmt.   709         #       We'll just dispatch them.   710         return self._dispatch[node[0]](node[1:])   711    712     def com_NEWLINE(self, *args):   713         # A ';' at the end of a line can make a NEWLINE token appear   714         # here, Render it harmless. (genc discards ('discard',   715         # ('const', xxxx)) Nodes)   716         return Discard(Const(None))   717    718     def com_arglist(self, nodelist):   719         # varargslist:   720         #     (fpdef ['=' test] ',')* ('*' NAME [',' '**' NAME] | '**' NAME)   721         #   | fpdef ['=' test] (',' fpdef ['=' test])* [',']   722         # fpdef: NAME | '.' NAME | '(' fplist ')'   723         # fplist: fpdef (',' fpdef)* [',']   724         names = []   725         defaults = []   726         flags = 0   727    728         i = 0   729         while i < len(nodelist):   730             node = nodelist[i]   731             if node[0] == token["STAR"] or node[0] == token["DOUBLESTAR"]:   732                 if node[0] == token["STAR"]:   733                     node = nodelist[i+1]   734                     if node[0] == token["NAME"]:   735                         names.append(node[1])   736                         flags = flags | CO_VARARGS   737                         i = i + 3   738    739                 if i < len(nodelist):   740                     # should be DOUBLESTAR   741                     t = nodelist[i][0]   742                     if t == token["DOUBLESTAR"]:   743                         node = nodelist[i+1]   744                     else:   745                         raise ValueError, "unexpected token: %s" % t   746                     names.append(node[1])   747                     flags = flags | CO_VARKEYWORDS   748    749                 break   750    751             # fpdef: NAME | '.' NAME | '(' fplist ')'   752             names.append(self.com_fpdef(node))   753    754             i = i + 1   755             if i < len(nodelist) and nodelist[i][0] == token["EQUAL"]:   756                 defaults.append(self.com_node(nodelist[i + 1]))   757                 i = i + 2   758             elif len(defaults):   759                 # we have already seen an argument with default, but here   760                 # came one without   761                 raise SyntaxError, "non-default argument follows default argument"   762    763             # skip the comma   764             i = i + 1   765    766         return names, defaults, flags   767    768     def com_fpdef(self, node):   769         # fpdef: NAME | '.' NAME | '(' fplist ')'   770         if node[1][0] == token["LPAR"]:   771             return self.com_fplist(node[2])   772         elif node[1][0] == token["DOT"]:   773             return node[1][1] + node[2][1]   774         return node[1][1]   775    776     def com_fplist(self, node):   777         # fplist: fpdef (',' fpdef)* [',']   778         if len(node) == 2:   779             return self.com_fpdef(node[1])   780         list = []   781         for i in range(1, len(node), 2):   782             list.append(self.com_fpdef(node[i]))   783         return tuple(list)   784    785     def com_dotted_name(self, node):   786         # String together the dotted names and return the string   787         name = ""   788         for n in node:   789             if type(n) == type(()) and n[0] == 1:   790                 name = name + n[1] + '.'   791         return name[:-1]   792    793     def com_dotted_as_name(self, node):   794         assert node[0] == symbol["dotted_as_name"]   795         node = node[1:]   796         dot = self.com_dotted_name(node[0][1:])   797         if len(node) == 1:   798             return dot, None   799         assert node[1][1] == 'as'   800         assert node[2][0] == token["NAME"]   801         return dot, node[2][1]   802    803     def com_dotted_as_names(self, node):   804         assert node[0] == symbol["dotted_as_names"]   805         node = node[1:]   806         names = [self.com_dotted_as_name(node[0])]   807         for i in range(2, len(node), 2):   808             names.append(self.com_dotted_as_name(node[i]))   809         return names   810    811     def com_import_as_name(self, node):   812         assert node[0] == symbol["import_as_name"]   813         node = node[1:]   814         assert node[0][0] == token["NAME"]   815         if len(node) == 1:   816             return node[0][1], None   817         assert node[1][1] == 'as', node   818         assert node[2][0] == token["NAME"]   819         return node[0][1], node[2][1]   820    821     def com_import_as_names(self, node):   822         assert node[0] == symbol["import_as_names"]   823         node = node[1:]   824         names = [self.com_import_as_name(node[0])]   825         for i in range(2, len(node), 2):   826             names.append(self.com_import_as_name(node[i]))   827         return names   828    829     def com_bases(self, node):   830         bases = []   831         for i in range(1, len(node), 2):   832             bases.append(self.com_node(node[i]))   833         return bases   834    835     def com_try_except_finally(self, nodelist):   836         # ('try' ':' suite   837         #  ((except_clause ':' suite)+ ['else' ':' suite] ['finally' ':' suite]   838         #   | 'finally' ':' suite))   839    840         if nodelist[3][0] == token["NAME"]:   841             # first clause is a finally clause: only try-finally   842             return TryFinally(self.com_node(nodelist[2]),   843                               self.com_node(nodelist[5]),   844                               lineno=nodelist[0][2])   845    846         #tryexcept:  [TryNode, [except_clauses], elseNode)]   847         clauses = []   848         elseNode = None   849         finallyNode = None   850         for i in range(3, len(nodelist), 3):   851             node = nodelist[i]   852             if node[0] == symbol["except_clause"]:   853                 # except_clause: 'except' [expr [(',' | 'as') expr]] */   854                 if len(node) > 2:   855                     expr1 = self.com_node(node[2])   856                     if len(node) > 4:   857                         expr2 = self.com_assign(node[4], OP_ASSIGN)   858                     else:   859                         expr2 = None   860                 else:   861                     expr1 = expr2 = None   862                 clauses.append((expr1, expr2, self.com_node(nodelist[i+2])))   863    864             if node[0] == token["NAME"]:   865                 if node[1] == 'else':   866                     elseNode = self.com_node(nodelist[i+2])   867                 elif node[1] == 'finally':   868                     finallyNode = self.com_node(nodelist[i+2])   869         try_except = TryExcept(self.com_node(nodelist[2]), clauses, elseNode,   870                                lineno=nodelist[0][2])   871         if finallyNode:   872             return TryFinally(try_except, finallyNode, lineno=nodelist[0][2])   873         else:   874             return try_except   875    876     def com_augassign_op(self, node):   877         assert node[0] == symbol["augassign"]   878         return node[1]   879    880     def com_augassign(self, node):   881         """Return node suitable for lvalue of augmented assignment   882    883         Names, slices, and attributes are the only allowable nodes.   884         """   885         l = self.com_node(node)   886         if l.__class__ in (Name, Slice, Subscript, Getattr):   887             return l   888         raise SyntaxError, "can't assign to %s" % l.__class__.__name__   889    890     def com_assign(self, node, assigning):   891         # return a node suitable for use as an "lvalue"   892         # loop to avoid trivial recursion   893         while 1:   894             t = node[0]   895             if t in (symbol["exprlist"], symbol["testlist"], symbol["testlist_safe"], symbol["testlist_comp"]):   896                 if len(node) > 2:   897                     return self.com_assign_tuple(node, assigning)   898                 node = node[1]   899             elif t in _assign_types:   900                 if len(node) > 2:   901                     raise SyntaxError, "can't assign to operator"   902                 node = node[1]   903             elif t == symbol["power"]:   904                 if node[1][0] != symbol["atom"]:   905                     raise SyntaxError, "can't assign to operator"   906                 if len(node) > 2:   907                     primary = self.com_node(node[1])   908                     for i in range(2, len(node)-1):   909                         ch = node[i]   910                         if ch[0] == token["DOUBLESTAR"]:   911                             raise SyntaxError, "can't assign to operator"   912                         primary = self.com_apply_trailer(primary, ch)   913                     return self.com_assign_trailer(primary, node[-1],   914                                                    assigning)   915                 node = node[1]   916             elif t == symbol["atom"]:   917                 t = node[1][0]   918                 if t == token["LPAR"]:   919                     node = node[2]   920                     if node[0] == token["RPAR"]:   921                         raise SyntaxError, "can't assign to ()"   922                 elif t == token["LSQB"]:   923                     node = node[2]   924                     if node[0] == token["RSQB"]:   925                         raise SyntaxError, "can't assign to []"   926                     return self.com_assign_list(node, assigning)   927                 elif t == token["NAME"]:   928                     return self.com_assign_name(node[1], assigning)   929                 else:   930                     raise SyntaxError, "can't assign to literal"   931             else:   932                 raise SyntaxError, "bad assignment (%s)" % t   933    934     def com_assign_tuple(self, node, assigning):   935         assigns = []   936         for i in range(1, len(node), 2):   937             assigns.append(self.com_assign(node[i], assigning))   938         return AssTuple(assigns, lineno=extractLineNo(node))   939    940     def com_assign_list(self, node, assigning):   941         assigns = []   942         for i in range(1, len(node), 2):   943             if i + 1 < len(node):   944                 if node[i + 1][0] == symbol["list_for"]:   945                     raise SyntaxError, "can't assign to list comprehension"   946                 assert node[i + 1][0] == token["COMMA"], node[i + 1]   947             assigns.append(self.com_assign(node[i], assigning))   948         return AssList(assigns, lineno=extractLineNo(node))   949    950     def com_assign_name(self, node, assigning):   951         return AssName(node[1], assigning, lineno=node[2])   952    953     def com_assign_trailer(self, primary, node, assigning):   954         t = node[1][0]   955         if t == token["DOT"]:   956             return self.com_assign_attr(primary, node[2], assigning)   957         if t == token["LSQB"]:   958             return self.com_subscriptlist(primary, node[2], assigning)   959         if t == token["LPAR"]:   960             raise SyntaxError, "can't assign to function call"   961         raise SyntaxError, "unknown trailer type: %s" % t   962    963     def com_assign_attr(self, primary, node, assigning):   964         return AssAttr(primary, node[1], assigning, lineno=node[-1])   965    966     def com_binary(self, constructor, nodelist):   967         "Compile 'NODE (OP NODE)*' into (type, [ node1, ..., nodeN ])."   968         l = len(nodelist)   969         if l == 1:   970             n = nodelist[0]   971             return self.lookup_node(n)(n[1:])   972         items = []   973         for i in range(0, l, 2):   974             n = nodelist[i]   975             items.append(self.lookup_node(n)(n[1:]))   976         return constructor(items, lineno=extractLineNo(nodelist))   977    978     def com_stmt(self, node):   979         result = self.lookup_node(node)(node[1:])   980         assert result is not None   981         if isinstance(result, Stmt):   982             return result   983         return Stmt([result])   984    985     def com_append_stmt(self, stmts, node):   986         result = self.lookup_node(node)(node[1:])   987         assert result is not None   988         if isinstance(result, Stmt):   989             stmts.extend(result.nodes)   990         else:   991             stmts.append(result)   992    993     def com_list_constructor(self, nodelist):   994         # listmaker: test ( (',' test)* [','] )   995         values = []   996         for i in range(1, len(nodelist)):   997             if nodelist[i][0] == token["COMMA"]:   998                 continue   999             values.append(self.com_node(nodelist[i]))  1000         return List(values, lineno=values[0].lineno)  1001   1002     def com_dictorsetmaker(self, nodelist):  1003         # dictorsetmaker: ( (test ':' test ( (',' test ':' test)* [','])) |  1004         #                   (test ( (',' test)* [','])) )  1005         assert nodelist[0] == symbol["dictorsetmaker"]  1006         nodelist = nodelist[1:]  1007         if len(nodelist) == 1 or nodelist[1][0] == token["COMMA"]:  1008             # set literal  1009             items = []  1010             for i in range(0, len(nodelist), 2):  1011                 items.append(self.com_node(nodelist[i]))  1012             return Set(items, lineno=items[0].lineno)  1013         else:  1014             # dict literal  1015             items = []  1016             for i in range(0, len(nodelist), 4):  1017                 items.append((self.com_node(nodelist[i]),  1018                               self.com_node(nodelist[i+2])))  1019             return Dict(items, lineno=items[0][0].lineno)  1020   1021     def com_apply_trailer(self, primaryNode, nodelist):  1022         t = nodelist[1][0]  1023         if t == token["LPAR"]:  1024             return self.com_call_function(primaryNode, nodelist[2])  1025         if t == token["DOT"]:  1026             return self.com_select_member(primaryNode, nodelist[2])  1027         if t == token["LSQB"]:  1028             return self.com_subscriptlist(primaryNode, nodelist[2], OP_APPLY)  1029   1030         raise SyntaxError, 'unknown node type: %s' % t  1031   1032     def com_select_member(self, primaryNode, nodelist):  1033         if nodelist[0] != token["NAME"]:  1034             raise SyntaxError, "member must be a name"  1035         return Getattr(primaryNode, nodelist[1], lineno=nodelist[2])  1036   1037     def com_call_function(self, primaryNode, nodelist):  1038         if nodelist[0] == token["RPAR"]:  1039             return CallFunc(primaryNode, [], lineno=extractLineNo(nodelist))  1040         args = []  1041         kw = 0  1042         star_node = dstar_node = None  1043         len_nodelist = len(nodelist)  1044         i = 1  1045         while i < len_nodelist:  1046             node = nodelist[i]  1047   1048             if node[0]==token["STAR"]:  1049                 if star_node is not None:  1050                     raise SyntaxError, 'already have the varargs indentifier'  1051                 star_node = self.com_node(nodelist[i+1])  1052                 i = i + 3  1053                 continue  1054             elif node[0]==token["DOUBLESTAR"]:  1055                 if dstar_node is not None:  1056                     raise SyntaxError, 'already have the kwargs indentifier'  1057                 dstar_node = self.com_node(nodelist[i+1])  1058                 i = i + 3  1059                 continue  1060   1061             # positional or named parameters  1062             kw, result = self.com_argument(node, kw, star_node)  1063   1064             args.append(result)  1065             i = i + 2  1066   1067         return CallFunc(primaryNode, args, star_node, dstar_node,  1068                         lineno=extractLineNo(nodelist))  1069   1070     def com_argument(self, nodelist, kw, star_node):  1071         if len(nodelist) == 2:  1072             if kw:  1073                 raise SyntaxError, "non-keyword arg after keyword arg"  1074             if star_node:  1075                 raise SyntaxError, "only named arguments may follow *expression"  1076             return 0, self.com_node(nodelist[1])  1077         result = self.com_node(nodelist[3])  1078         n = nodelist[1]  1079         while len(n) == 2 and n[0] != token["NAME"]:  1080             n = n[1]  1081         if n[0] != token["NAME"]:  1082             raise SyntaxError, "keyword can't be an expression (%s)"%n[0]  1083         node = Keyword(n[1], result, lineno=n[2])  1084         return 1, node  1085   1086     def com_subscriptlist(self, primary, nodelist, assigning):  1087         # slicing:      simple_slicing | extended_slicing  1088         # simple_slicing:   primary "[" short_slice "]"  1089         # extended_slicing: primary "[" slice_list "]"  1090         # slice_list:   slice_item ("," slice_item)* [","]  1091   1092         # backwards compat slice for '[i:j]'  1093         if len(nodelist) == 2:  1094             sub = nodelist[1]  1095             if (sub[1][0] == token["COLON"] or \  1096                             (len(sub) > 2 and sub[2][0] == token["COLON"])) and \  1097                             sub[-1][0] != symbol["sliceop"]:  1098                 return self.com_slice(primary, sub, assigning)  1099   1100         subscripts = []  1101         for i in range(1, len(nodelist), 2):  1102             subscripts.append(self.com_subscript(nodelist[i]))  1103         return Subscript(primary, assigning, subscripts,  1104                          lineno=extractLineNo(nodelist))  1105   1106     def com_subscript(self, node):  1107         # slice_item: expression | proper_slice | ellipsis  1108         ch = node[1]  1109         t = ch[0]  1110         if t == token["DOT"] and node[2][0] == token["DOT"]:  1111             return Ellipsis()  1112         if t == token["COLON"] or len(node) > 2:  1113             return self.com_sliceobj(node)  1114         return self.com_node(ch)  1115   1116     def com_sliceobj(self, node):  1117         # proper_slice: short_slice | long_slice  1118         # short_slice:  [lower_bound] ":" [upper_bound]  1119         # long_slice:   short_slice ":" [stride]  1120         # lower_bound:  expression  1121         # upper_bound:  expression  1122         # stride:       expression  1123         #  1124         # Note: a stride may be further slicing...  1125   1126         items = []  1127   1128         if node[1][0] == token["COLON"]:  1129             items.append(Const(None))  1130             i = 2  1131         else:  1132             items.append(self.com_node(node[1]))  1133             # i == 2 is a COLON  1134             i = 3  1135   1136         if i < len(node) and node[i][0] == symbol["test"]:  1137             items.append(self.com_node(node[i]))  1138             i = i + 1  1139         else:  1140             items.append(Const(None))  1141   1142         # a short_slice has been built. look for long_slice now by looking  1143         # for strides...  1144         for j in range(i, len(node)):  1145             ch = node[j]  1146             if len(ch) == 2:  1147                 items.append(Const(None))  1148             else:  1149                 items.append(self.com_node(ch[2]))  1150         return Sliceobj(items, lineno=extractLineNo(node))  1151   1152     def com_slice(self, primary, node, assigning):  1153         # short_slice:  [lower_bound] ":" [upper_bound]  1154         lower = upper = None  1155         if len(node) == 3:  1156             if node[1][0] == token["COLON"]:  1157                 upper = self.com_node(node[2])  1158             else:  1159                 lower = self.com_node(node[1])  1160         elif len(node) == 4:  1161             lower = self.com_node(node[1])  1162             upper = self.com_node(node[3])  1163         return Slice(primary, assigning, lower, upper,  1164                      lineno=extractLineNo(node))  1165   1166     def get_docstring(self, node, n=None):  1167         if n is None:  1168             n = node[0]  1169             node = node[1:]  1170         if n == symbol["suite"]:  1171             if len(node) == 1:  1172                 return self.get_docstring(node[0])  1173             for sub in node:  1174                 if sub[0] == symbol["stmt"]:  1175                     return self.get_docstring(sub)  1176             return None  1177         if n == symbol["file_input"]:  1178             for sub in node:  1179                 if sub[0] == symbol["stmt"]:  1180                     return self.get_docstring(sub)  1181             return None  1182         if n == symbol["atom"]:  1183             if node[0][0] == token["STRING"]:  1184                 s = ''  1185                 for t in node:  1186                     s = s + eval(t[1])  1187                 return s  1188             return None  1189         if n == symbol["stmt"] or n == symbol["simple_stmt"] \  1190            or n == symbol["small_stmt"]:  1191             return self.get_docstring(node[0])  1192         if n in _doc_nodes and len(node) == 1:  1193             return self.get_docstring(node[0])  1194         return None  1195   1196   1197 _doc_nodes = [  1198     symbol["expr_stmt"],  1199     symbol["testlist"],  1200     symbol["testlist_safe"],  1201     symbol["test"],  1202     symbol["or_test"],  1203     symbol["and_test"],  1204     symbol["not_test"],  1205     symbol["comparison"],  1206     symbol["expr"],  1207     symbol["xor_expr"],  1208     symbol["and_expr"],  1209     symbol["shift_expr"],  1210     symbol["arith_expr"],  1211     symbol["term"],  1212     symbol["factor"],  1213     symbol["power"],  1214     ]  1215   1216 # comp_op: '<' | '>' | '=' | '>=' | '<=' | '<>' | '!=' | '=='  1217 #             | 'in' | 'not' 'in' | 'is' | 'is' 'not'  1218 _cmp_types = {  1219     token["LESS"] : '<',  1220     token["GREATER"] : '>',  1221     token["EQEQUAL"] : '==',  1222     token["EQUAL"] : '==',  1223     token["LESSEQUAL"] : '<=',  1224     token["GREATEREQUAL"] : '>=',  1225     token["NOTEQUAL"] : '!=',  1226     }  1227   1228 _legal_node_types = [  1229     symbol["funcdef"],  1230     symbol["classdef"],  1231     symbol["stmt"],  1232     symbol["small_stmt"],  1233     symbol["flow_stmt"],  1234     symbol["simple_stmt"],  1235     symbol["compound_stmt"],  1236     symbol["expr_stmt"],  1237     symbol["print_stmt"],  1238     symbol["del_stmt"],  1239     symbol["pass_stmt"],  1240     symbol["break_stmt"],  1241     symbol["continue_stmt"],  1242     symbol["return_stmt"],  1243     symbol["raise_stmt"],  1244     symbol["import_stmt"],  1245     symbol["global_stmt"],  1246     symbol["exec_stmt"],  1247     symbol["assert_stmt"],  1248     symbol["if_stmt"],  1249     symbol["while_stmt"],  1250     symbol["for_stmt"],  1251     symbol["try_stmt"],  1252     symbol["suite"],  1253     symbol["testlist"],  1254     symbol["testlist_safe"],  1255     symbol["test"],  1256     symbol["and_test"],  1257     symbol["not_test"],  1258     symbol["comparison"],  1259     symbol["exprlist"],  1260     symbol["expr"],  1261     symbol["xor_expr"],  1262     symbol["and_expr"],  1263     symbol["shift_expr"],  1264     symbol["arith_expr"],  1265     symbol["term"],  1266     symbol["factor"],  1267     symbol["power"],  1268     symbol["atom"],  1269     ]  1270   1271 _assign_types = [  1272     symbol["test"],  1273     symbol["or_test"],  1274     symbol["and_test"],  1275     symbol["not_test"],  1276     symbol["comparison"],  1277     symbol["expr"],  1278     symbol["xor_expr"],  1279     symbol["and_expr"],  1280     symbol["shift_expr"],  1281     symbol["arith_expr"],  1282     symbol["term"],  1283     symbol["factor"],  1284     ]  1285   1286 _names = {}  1287 for k, v in sym_name.items():  1288     _names[k] = v  1289 for k, v in tok_name.items():  1290     _names[k] = v  1291   1292 def debug_tree(tree):  1293     l = []  1294     for elt in tree:  1295         if isinstance(elt, int):  1296             l.append(_names.get(elt, elt))  1297         elif isinstance(elt, str):  1298             l.append(elt)  1299         else:  1300             l.append(debug_tree(elt))  1301     return l