Lib/compiler/transformer.py

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