Lichen

compiler/transformer.py

934:2989aab1b4f7
13 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