1 #

2 # Tree visitor and transform framework

3 #

4 import inspect

5 import Nodes

6 import ExprNodes

7 import Naming

8 from StringEncoding import EncodedString

9

10 class BasicVisitor(object):

11 """A generic visitor base class which can be used for visiting any kind of object."""

12 # Note: If needed, this can be replaced with a more efficient metaclass

13 # approach, resolving the jump table at module load time rather than per visitor

14 # instance.

15 def __init__(self):

16 self.dispatch_table = {}

17

18 def visit(self, obj):

19 cls = type(obj)

20 try:

21 handler_method = self.dispatch_table[cls]

22 except KeyError:

23 #print "Cache miss for class %s in visitor %s" % (

24 # cls.__name__, type(self).__name__)

25 # Must resolve, try entire hierarchy

26 pattern = "visit_%s"

27 mro = inspect.getmro(cls)

28 for mro_cls in mro:

29 try:

30 handler_method = getattr(self, pattern % mro_cls.__name__)

31 break

32 except AttributeError:

33 pass

34 else:

35 print type(self), type(obj)

36 if hasattr(self, 'access_path'):

37 print self.access_path

38 print self.access_path[-1][0].pos

39 print self.access_path[-1][0].__dict__

40 raise RuntimeError("Visitor does not accept object: %s" % obj)

41 #print "Caching " + cls.__name__

42 self.dispatch_table[cls] = handler_method

43 return handler_method(obj)

44

45 class TreeVisitor(BasicVisitor):

46 """

47 Base class for writing visitors for a Cython tree, contains utilities for

48 recursing such trees using visitors. Each node is

49 expected to have a child_attrs iterable containing the names of attributes

50 containing child nodes or lists of child nodes. Lists are not considered

51 part of the tree structure (i.e. contained nodes are considered direct

52 children of the parent node).

53

54 visit_children visits each of the children of a given node (see the visit_children

55 documentation). When recursing the tree using visit_children, an attribute

56 access_path is maintained which gives information about the current location

57 in the tree as a stack of tuples: (parent_node, attrname, index), representing

58 the node, attribute and optional list index that was taken in each step in the path to

59 the current node.

60

61 Example:

62

63 >>> class SampleNode:

64 ... child_attrs = ["head", "body"]

65 ... def __init__(self, value, head=None, body=None):

66 ... self.value = value

67 ... self.head = head

68 ... self.body = body

69 ... def __repr__(self): return "SampleNode(%s)" % self.value

70 ...

71 >>> tree = SampleNode(0, SampleNode(1), [SampleNode(2), SampleNode(3)])

72 >>> class MyVisitor(TreeVisitor):

73 ... def visit_SampleNode(self, node):

74 ... print "in", node.value, self.access_path

75 ... self.visitchildren(node)

76 ... print "out", node.value

77 ...

78 >>> MyVisitor().visit(tree)

79 in 0 []

80 in 1 [(SampleNode(0), 'head', None)]

81 out 1

82 in 2 [(SampleNode(0), 'body', 0)]

83 out 2

84 in 3 [(SampleNode(0), 'body', 1)]

85 out 3

86 out 0

87 """

88

89 def __init__(self):

90 super(TreeVisitor, self).__init__()

91 self.access_path = []

92

93 def visitchild(self, child, parent, attrname, idx):

94 self.access_path.append((parent, attrname, idx))

95 result = self.visit(child)

96 self.access_path.pop()

97 return result

98

99 def visitchildren(self, parent, attrs=None):

100 """

101 Visits the children of the given parent. If parent is None, returns

102 immediately (returning None).

103

104 The return value is a dictionary giving the results for each

105 child (mapping the attribute name to either the return value

106 or a list of return values (in the case of multiple children

107 in an attribute)).

108 """

109

110 if parent is None: return None

111 result = {}

112 for attr in parent.child_attrs:

113 if attrs is not None and attr not in attrs: continue

114 child = getattr(parent, attr)

115 if child is not None:

116 if isinstance(child, list):

117 childretval = [self.visitchild(x, parent, attr, idx) for idx, x in enumerate(child)]

118 else:

119 childretval = self.visitchild(child, parent, attr, None)

120 assert not isinstance(childretval, list), 'Cannot insert list here: %s in %r' % (attr, parent)

121 result[attr] = childretval

122 return result

123

124

125 class VisitorTransform(TreeVisitor):

126 """

127 A tree transform is a base class for visitors that wants to do stream

128 processing of the structure (rather than attributes etc.) of a tree.

129

130 It implements __call__ to simply visit the argument node.

131

132 It requires the visitor methods to return the nodes which should take

133 the place of the visited node in the result tree (which can be the same

134 or one or more replacement). Specifically, if the return value from

135 a visitor method is:

136

137 - [] or None; the visited node will be removed (set to None if an attribute and

138 removed if in a list)

139 - A single node; the visited node will be replaced by the returned node.

140 - A list of nodes; the visited nodes will be replaced by all the nodes in the

141 list. This will only work if the node was already a member of a list; if it

142 was not, an exception will be raised. (Typically you want to ensure that you

143 are within a StatListNode or similar before doing this.)

144 """

145 def visitchildren(self, parent, attrs=None):

146 result = super(VisitorTransform, self).visitchildren(parent, attrs)

147 for attr, newnode in result.iteritems():

148 if not isinstance(newnode, list):

149 setattr(parent, attr, newnode)

150 else:

151 # Flatten the list one level and remove any None

152 newlist = []

153 for x in newnode:

154 if x is not None:

155 if isinstance(x, list):

156 newlist += x

157 else:

158 newlist.append(x)

159 setattr(parent, attr, newlist)

160 return result

161

162 def __call__(self, root):

163 return self.visit(root)

164

165 class CythonTransform(VisitorTransform):

166 """

167 Certain common conventions and utilitues for Cython transforms.

168 """

169 def __init__(self, context):

170 super(CythonTransform, self).__init__()

171 self.context = context

172

173 def __call__(self, node):

174 import ModuleNode

175 if isinstance(node, ModuleNode.ModuleNode):

176 self.current_directives = node.directives

177 return super(CythonTransform, self).__call__(node)

178

179 def visit_CompilerDirectivesNode(self, node):

180 old = self.current_directives

181 self.current_directives = node.directives

182 self.visitchildren(node)

183 self.current_directives = old

184 return node

185

186 def visit_Node(self, node):

187 self.visitchildren(node)

188 return node

189

190

191

192

193 # Utils

194 def ensure_statlist(node):

195 if not isinstance(node, Nodes.StatListNode):

196 node = Nodes.StatListNode(pos=node.pos, stats=[node])

197 return node

198

199 def replace_node(ptr, value):

200 """Replaces a node. ptr is of the form used on the access path stack

201 (parent, attrname, listidx|None)

202 """

203 parent, attrname, listidx = ptr

204 if listidx is None:

205 setattr(parent, attrname, value)

206 else:

207 getattr(parent, attrname)[listidx] = value

208

209 class PrintTree(TreeVisitor):

210 """Prints a representation of the tree to standard output.

211 Subclass and override repr_of to provide more information

212 about nodes. """

213 def __init__(self):

214 TreeVisitor.__init__(self)

215 self._indent = ""

216

217 def indent(self):

218 self._indent += " "

219 def unindent(self):

220 self._indent = self._indent[:-2]

221

222 def __call__(self, tree, phase=None):

223 print("Parse tree dump at phase '%s'" % phase)

224 self.visit(tree)

225 return tree

226

227 # Don't do anything about process_list, the defaults gives

228 # nice-looking name[idx] nodes which will visually appear

229 # under the parent-node, not displaying the list itself in

230 # the hierarchy.

231 def visit_Node(self, node):

232 if len(self.access_path) == 0:

233 name = "(root)"

234 else:

235 parent, attr, idx = self.access_path[-1]

236 if idx is not None:

237 name = "%s[%d]" % (attr, idx)

238 else:

239 name = attr

240 print("%s- %s: %s" % (self._indent, name, self.repr_of(node)))

241 self.indent()

242 self.visitchildren(node)

243 self.unindent()

244 return node

245

246 def repr_of(self, node):

247 if node is None:

248 return "(none)"

249 else:

250 result = node.__class__.__name__

251 if isinstance(node, ExprNodes.NameNode):

252 result += "(type=%s, name=\"%s\")" % (repr(node.type), node.name)

253 elif isinstance(node, Nodes.DefNode):

254 result += "(name=\"%s\")" % node.name

255 elif isinstance(node, ExprNodes.ExprNode):

256 t = node.type

257 result += "(type=%s)" % repr(t)

258

259 return result

260

261 if __name__ == "__main__":

262 import doctest

263 doctest.testmod()