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