1 #

2 # Tree visitor and transform framework

3 #

4 import cython

5 import inspect

6 import Nodes

7 import ExprNodes

8 import Naming

9 import Errors

10 from StringEncoding import EncodedString

11

12 class BasicVisitor(object):

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

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

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

16 # instance.

17 def __init__(self):

18 self.dispatch_table = {}

19

20 def visit(self, obj):

21 cls = type(obj)

22 try:

23 handler_method = self.dispatch_table[cls]

24 except KeyError:

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

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

27 # Must resolve, try entire hierarchy

28 pattern = "visit_%s"

29 mro = inspect.getmro(cls)

30 handler_method = None

31 for mro_cls in mro:

32 if hasattr(self, pattern % mro_cls.__name__):

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

34 break

35 if handler_method is None:

36 print type(self), type(obj)

37 if hasattr(self, 'access_path') and self.access_path:

38 print self.access_path

39 if self.access_path:

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

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

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

43 #print "Caching " + cls.__name__

44 self.dispatch_table[cls] = handler_method

45 return handler_method(obj)

46

47 class TreeVisitor(BasicVisitor):

48 """

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

50 recursing such trees using visitors. Each node is

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

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

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

54 children of the parent node).

55

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

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

58 access_path is maintained which gives information about the current location

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

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

61 the current node.

62

63 Example:

64

65 >>> class SampleNode(object):

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

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

68 ... self.value = value

69 ... self.head = head

70 ... self.body = body

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

72 ...

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

74 >>> class MyVisitor(TreeVisitor):

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

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

77 ... self.visitchildren(node)

78 ... print "out", node.value

79 ...

80 >>> MyVisitor().visit(tree)

81 in 0 []

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

83 out 1

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

85 out 2

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

87 out 3

88 out 0

89 """

90

91 def __init__(self):

92 super(TreeVisitor, self).__init__()

93 self.access_path = []

94

95 def dump_node(self, node, indent=0):

96 ignored = list(node.child_attrs) + [u'child_attrs', u'pos']

97 values = []

98 pos = node.pos

99 if pos:

100 source = pos[0]

101 if source:

102 import os.path

103 source = os.path.basename(source.get_description())

104 values.append(u'%s:%s:%s' % (source, pos[1], pos[2]))

105 attribute_names = dir(node)

106 attribute_names.sort()

107 for attr in attribute_names:

108 if attr in ignored:

109 continue

110 if attr.startswith(u'_') or attr.endswith(u'_'):

111 continue

112 value = getattr(node, attr, None)

113 if value is None:

114 continue

115 elif isinstance(value, list):

116 value = u'[...]'

117 elif not isinstance(value, (str, unicode, long, int, float)):

118 continue

119 else:

120 value = repr(value)

121 values.append(u'%s = %s' % (attr, value))

122 return u'%s(%s)' % (node.__class__.__name__,

123 u',\n '.join(values))

124

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

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

127 try:

128 result = self.visit(child)

129 except Errors.CompilerCrash:

130 raise

131 except Exception, e:

132 import sys

133 trace = ['']

134 for parent, attribute, index in self.access_path:

135 node = getattr(parent, attribute)

136 if index is None:

137 index = ''

138 else:

139 node = node[index]

140 index = u'[%d]' % index

141 trace.append(u'%s.%s%s = %s' % (

142 parent.__class__.__name__, attribute, index,

143 self.dump_node(node)))

144 raise Errors.CompilerCrash(

145 node.pos, self.__class__.__name__,

146 u'\n'.join(trace), e, sys.exc_info()[2])

147 self.access_path.pop()

148 return result

149

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

151 """

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

153 immediately (returning None).

154

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

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

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

158 in an attribute)).

159 """

160

161 if parent is None: return None

162 result = {}

163 for attr in parent.child_attrs:

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

165 child = getattr(parent, attr)

166 if child is not None:

167 if isinstance(child, list):

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

169 else:

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

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

172 result[attr] = childretval

173 return result

174

175

176 class VisitorTransform(TreeVisitor):

177 """

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

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

180

181 It implements __call__ to simply visit the argument node.

182

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

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

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

186 a visitor method is:

187

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

189 removed if in a list)

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

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

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

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

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

195 """

196 def __init__(self):

197 super(VisitorTransform, self).__init__()

198 self._super_visitchildren = super(VisitorTransform, self).visitchildren

199

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

201 result = cython.declare(dict)

202 result = self._super_visitchildren(parent, attrs)

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

204 if not isinstance(newnode, list):

205 setattr(parent, attr, newnode)

206 else:

207 # Flatten the list one level and remove any None

208 newlist = []

209 for x in newnode:

210 if x is not None:

211 if isinstance(x, list):

212 newlist += x

213 else:

214 newlist.append(x)

215 setattr(parent, attr, newlist)

216 return result

217

218 def recurse_to_children(self, node):

219 self.visitchildren(node)

220 return node

221

222 def __call__(self, root):

223 return self.visit(root)

224

225 class CythonTransform(VisitorTransform):

226 """

227 Certain common conventions and utilitues for Cython transforms.

228 """

229 def __init__(self, context):

230 super(CythonTransform, self).__init__()

231 self.context = context

232

233 def __call__(self, node):

234 import ModuleNode

235 if isinstance(node, ModuleNode.ModuleNode):

236 self.current_directives = node.directives

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

238

239 def visit_CompilerDirectivesNode(self, node):

240 old = self.current_directives

241 self.current_directives = node.directives

242 self.visitchildren(node)

243 self.current_directives = old

244 return node

245

246 def visit_Node(self, node):

247 self.visitchildren(node)

248 return node

249

250

251

252

253 # Utils

254 def ensure_statlist(node):

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

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

257 return node

258

259 def replace_node(ptr, value):

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

261 (parent, attrname, listidx|None)

262 """

263 parent, attrname, listidx = ptr

264 if listidx is None:

265 setattr(parent, attrname, value)

266 else:

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

268

269 class PrintTree(TreeVisitor):

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

271 Subclass and override repr_of to provide more information

272 about nodes. """

273 def __init__(self):

274 TreeVisitor.__init__(self)

275 self._indent = ""

276

277 def indent(self):

278 self._indent += " "

279 def unindent(self):

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

281

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

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

284 self.visit(tree)

285 return tree

286

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

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

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

290 # the hierarchy.

291 def visit_Node(self, node):

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

293 name = "(root)"

294 else:

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

296 if idx is not None:

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

298 else:

299 name = attr

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

301 self.indent()

302 self.visitchildren(node)

303 self.unindent()

304 return node

305

306 def repr_of(self, node):

307 if node is None:

308 return "(none)"

309 else:

310 result = node.__class__.__name__

311 if isinstance(node, ExprNodes.NameNode):

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

313 elif isinstance(node, Nodes.DefNode):

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

315 elif isinstance(node, ExprNodes.ExprNode):

316 t = node.type

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

318

319 return result

320

321 if __name__ == "__main__":

322 import doctest

323 doctest.testmod()