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