paul@0 | 1 | from compiler import ast |
paul@0 | 2 | |
paul@0 | 3 | # XXX should probably rename ASTVisitor to ASTWalker |
paul@0 | 4 | # XXX can it be made even more generic? |
paul@0 | 5 | |
paul@0 | 6 | class ASTVisitor: |
paul@0 | 7 | """Performs a depth-first walk of the AST |
paul@0 | 8 | |
paul@0 | 9 | The ASTVisitor will walk the AST, performing either a preorder or |
paul@0 | 10 | postorder traversal depending on which method is called. |
paul@0 | 11 | |
paul@0 | 12 | methods: |
paul@0 | 13 | preorder(tree, visitor) |
paul@0 | 14 | postorder(tree, visitor) |
paul@0 | 15 | tree: an instance of ast.Node |
paul@0 | 16 | visitor: an instance with visitXXX methods |
paul@0 | 17 | |
paul@0 | 18 | The ASTVisitor is responsible for walking over the tree in the |
paul@0 | 19 | correct order. For each node, it checks the visitor argument for |
paul@0 | 20 | a method named 'visitNodeType' where NodeType is the name of the |
paul@0 | 21 | node's class, e.g. Class. If the method exists, it is called |
paul@0 | 22 | with the node as its sole argument. |
paul@0 | 23 | |
paul@0 | 24 | The visitor method for a particular node type can control how |
paul@0 | 25 | child nodes are visited during a preorder walk. (It can't control |
paul@0 | 26 | the order during a postorder walk, because it is called _after_ |
paul@0 | 27 | the walk has occurred.) The ASTVisitor modifies the visitor |
paul@0 | 28 | argument by adding a visit method to the visitor; this method can |
paul@0 | 29 | be used to visit a child node of arbitrary type. |
paul@0 | 30 | """ |
paul@0 | 31 | |
paul@0 | 32 | VERBOSE = 0 |
paul@0 | 33 | |
paul@0 | 34 | def __init__(self): |
paul@0 | 35 | self.node = None |
paul@0 | 36 | self._cache = {} |
paul@0 | 37 | |
paul@0 | 38 | def default(self, node, *args): |
paul@0 | 39 | for child in node.getChildNodes(): |
paul@0 | 40 | self.dispatch(child, *args) |
paul@0 | 41 | |
paul@0 | 42 | def dispatch(self, node, *args): |
paul@0 | 43 | self.node = node |
paul@0 | 44 | klass = node.__class__ |
paul@0 | 45 | meth = self._cache.get(klass, None) |
paul@0 | 46 | if meth is None: |
paul@0 | 47 | className = klass.__name__ |
paul@0 | 48 | meth = getattr(self.visitor, 'visit' + className, self.default) |
paul@0 | 49 | self._cache[klass] = meth |
paul@0 | 50 | ## if self.VERBOSE > 0: |
paul@0 | 51 | ## className = klass.__name__ |
paul@0 | 52 | ## if self.VERBOSE == 1: |
paul@0 | 53 | ## if meth == 0: |
paul@0 | 54 | ## print "dispatch", className |
paul@0 | 55 | ## else: |
paul@0 | 56 | ## print "dispatch", className, (meth and meth.__name__ or '') |
paul@0 | 57 | return meth(node, *args) |
paul@0 | 58 | |
paul@0 | 59 | def preorder(self, tree, visitor, *args): |
paul@0 | 60 | """Do preorder walk of tree using visitor""" |
paul@0 | 61 | self.visitor = visitor |
paul@0 | 62 | visitor.visit = self.dispatch |
paul@0 | 63 | self.dispatch(tree, *args) # XXX *args make sense? |
paul@0 | 64 | |
paul@0 | 65 | class ExampleASTVisitor(ASTVisitor): |
paul@0 | 66 | """Prints examples of the nodes that aren't visited |
paul@0 | 67 | |
paul@0 | 68 | This visitor-driver is only useful for development, when it's |
paul@0 | 69 | helpful to develop a visitor incrementally, and get feedback on what |
paul@0 | 70 | you still have to do. |
paul@0 | 71 | """ |
paul@0 | 72 | examples = {} |
paul@0 | 73 | |
paul@0 | 74 | def dispatch(self, node, *args): |
paul@0 | 75 | self.node = node |
paul@0 | 76 | meth = self._cache.get(node.__class__, None) |
paul@0 | 77 | className = node.__class__.__name__ |
paul@0 | 78 | if meth is None: |
paul@0 | 79 | meth = getattr(self.visitor, 'visit' + className, 0) |
paul@0 | 80 | self._cache[node.__class__] = meth |
paul@0 | 81 | if self.VERBOSE > 1: |
paul@0 | 82 | print "dispatch", className, (meth and meth.__name__ or '') |
paul@0 | 83 | if meth: |
paul@0 | 84 | meth(node, *args) |
paul@0 | 85 | elif self.VERBOSE > 0: |
paul@0 | 86 | klass = node.__class__ |
paul@0 | 87 | if not self.examples.has_key(klass): |
paul@0 | 88 | self.examples[klass] = klass |
paul@0 | 89 | print |
paul@0 | 90 | print self.visitor |
paul@0 | 91 | print klass |
paul@0 | 92 | for attr in dir(node): |
paul@0 | 93 | if attr[0] != '_': |
paul@0 | 94 | print "\t", "%-12.12s" % attr, getattr(node, attr) |
paul@0 | 95 | print |
paul@0 | 96 | return self.default(node, *args) |
paul@0 | 97 | |
paul@0 | 98 | # XXX this is an API change |
paul@0 | 99 | |
paul@0 | 100 | _walker = ASTVisitor |
paul@0 | 101 | def walk(tree, visitor, walker=None, verbose=None): |
paul@0 | 102 | if walker is None: |
paul@0 | 103 | walker = _walker() |
paul@0 | 104 | if verbose is not None: |
paul@0 | 105 | walker.VERBOSE = verbose |
paul@0 | 106 | walker.preorder(tree, visitor) |
paul@0 | 107 | return walker.visitor |
paul@0 | 108 | |
paul@0 | 109 | def dumpNode(node): |
paul@0 | 110 | print node.__class__ |
paul@0 | 111 | for attr in dir(node): |
paul@0 | 112 | if attr[0] != '_': |
paul@0 | 113 | print "\t", "%-10.10s" % attr, getattr(node, attr) |