1 #!/usr/bin/env python 2 3 """ 4 Simplified program nodes for easier type propagation and analysis. This module 5 contains nodes representing program instructions or operations, program 6 structure or organisation, and abstract program data. 7 8 Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk> 9 10 This software is free software; you can redistribute it and/or 11 modify it under the terms of the GNU General Public License as 12 published by the Free Software Foundation; either version 2 of 13 the License, or (at your option) any later version. 14 15 This software is distributed in the hope that it will be useful, 16 but WITHOUT ANY WARRANTY; without even the implied warranty of 17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 GNU General Public License for more details. 19 20 You should have received a copy of the GNU General Public 21 License along with this library; see the file LICENCE.txt 22 If not, write to the Free Software Foundation, Inc., 23 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 24 """ 25 26 from compiler.visitor import ASTVisitor 27 import sys 28 29 # Exceptions. 30 31 class SimplifiedError(Exception): 32 33 "An error in the annotation process." 34 35 def __init__(self, exc, node, *args): 36 37 """ 38 Initialise the error with an existing exception 'exc', the 'node' at 39 which this error occurs, along with additional optional arguments. 40 """ 41 42 Exception.__init__(self, *args) 43 self.nodes = [node] 44 self.exc = exc 45 46 def add(self, node): 47 48 "Add the given 'node' to the path of nodes leading from the exception." 49 50 self.nodes.append(node) 51 52 def __str__(self): 53 54 "Return a string showing the principal exception details." 55 56 return "%s, %s" % (self.exc, self.nodes) 57 58 # Unique name registration. 59 60 class Naming: 61 62 "Maintain records of unique names for each simple name." 63 64 index_separator = "-" 65 66 def __init__(self): 67 self.obj_to_name = {} 68 self.names = {} 69 70 def get(self, obj): 71 return self.obj_to_name[obj] 72 73 def set(self, obj, name): 74 if self.obj_to_name.has_key(obj): 75 return 76 if not self.names.has_key(name): 77 self.names[name] = 0 78 n = self.names[name] + 1 79 self.names[name] = n 80 self.obj_to_name[obj] = "%s%s%d" % (name, self.index_separator, n) 81 82 naming = Naming() 83 84 def name(obj, name): 85 86 "Return a unique name for the given 'obj', indicating the base 'name'." 87 88 naming.set(obj, name) 89 return naming.get(obj) 90 91 # Elementary visitor support. 92 93 class Visitor(ASTVisitor): 94 95 "A visitor base class." 96 97 def __init__(self): 98 ASTVisitor.__init__(self) 99 100 def default(self, node, *args): 101 raise ValueError, node.__class__ 102 103 def dispatch(self, node, *args): 104 return ASTVisitor.dispatch(self, node, *args) 105 106 def dispatches(self, nodes, *args): 107 results = [] 108 for node in nodes: 109 results.append(self.dispatch(node, *args)) 110 return results 111 112 def dispatch_dict(self, d, *args): 113 results = {} 114 for name, node in d.items(): 115 results[name] = self.dispatch(node, *args) 116 return results 117 118 # Simplified program nodes. 119 120 class Node: 121 122 """ 123 A result node with common attributes: 124 125 original The original node from which this node was created. 126 defining Whether the node defines something in the original program. 127 name Any name involved (variable or attribute). 128 index Any index involved (temporary variable name). 129 value Any constant value. 130 ref Any reference to (for example) subprograms. 131 nstype Any indication of the namespace type involved in a name access. 132 133 Expression-related attributes: 134 135 expr Any contributing expression. 136 lvalue Any target expression. 137 test Any test expression in a conditional instruction. 138 139 Invocation and subprogram attributes: 140 141 args Any collection of argument nodes. 142 params Any collection of parameter nodes and defaults. 143 144 Statement-grouping attributes: 145 146 body Any conditional code depending on the success of a test. 147 else_ Any conditional code depending on the failure of a test. 148 handler Any exception handler code. 149 finally_ Any code which will be executed regardless. 150 code Any unconditional code. 151 choices Any choices which may be included in the final program. 152 """ 153 154 def __init__(self, original=None, defining=0, **kw): 155 156 """ 157 Initialise a program node with a link to an optional 'original' AST 158 node. An optional 'defining' parameter (if set to a true value), sets 159 this node as the defining node in the original. 160 """ 161 162 self.original = original 163 self.defining = defining 164 165 if self.original is not None and defining: 166 self.original._node = self 167 for name, value in kw.items(): 168 setattr(self, name, value) 169 170 def __repr__(self): 171 172 "Return a readable representation." 173 174 if hasattr(self, "full_name"): 175 s = "%s '%s'" % (self.__class__.__name__, self.full_name()) 176 elif hasattr(self, "name"): 177 s = "%s '%s'" % (self.__class__.__name__, self.name) 178 elif hasattr(self, "index"): 179 s = "%s (%s)" % (self.__class__.__name__, self.index) 180 elif hasattr(self, "value"): 181 s = "%s %s" % (self.__class__.__name__, repr(self.value)) 182 elif hasattr(self, "ref"): 183 s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) 184 else: 185 s = "%s" % (self.__class__.__name__,) 186 187 # Annotations. 188 189 if hasattr(self, "types"): 190 return "%s -> %s" % (s, self.types) 191 else: 192 return s 193 194 def _pprint(self, indent, continuation, s, stream=None): 195 196 """ 197 Print, at the given 'indent' level, with the given 'continuation' text, 198 the string 's', either to the given, optional 'stream' or to standard 199 output, this node's "pretty" representation. 200 """ 201 202 stream = stream or sys.stdout 203 if continuation: 204 print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s 205 else: 206 print >>stream, (" " * indent) + s 207 208 def pprint(self, indent=0, continuation=None, stream=None): 209 210 """ 211 Print, at the given, optional 'indent', with the given optional 212 'continuation' text, either to the given, optional 'stream' or to 213 standard output, this node's "pretty" representation along with its 214 children and their "pretty" representation (and so on). 215 """ 216 217 stream = stream or sys.stdout 218 self._pprint(indent, continuation, repr(self), stream) 219 220 # Subprogram-related details. 221 222 if hasattr(self, "params"): 223 for name, default in self.params: 224 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 225 if hasattr(self, "star") and self.star: 226 name, default = self.star 227 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 228 if hasattr(self, "dstar") and self.dstar: 229 name, default = self.dstar 230 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 231 if getattr(self, "internal", 0): 232 self._pprint(indent + 2, "( ", "internal", stream=stream) 233 if getattr(self, "structure", 0): 234 self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) 235 236 # Statement-related details. 237 238 if hasattr(self, "test"): 239 self.test.pprint(indent + 2, "? ", stream=stream) 240 for attr in "code", "body", "else_", "handler", "finally_", "choices": 241 if hasattr(self, attr) and getattr(self, attr): 242 self._pprint(indent, "", "%s {" % attr, stream=stream) 243 for node in getattr(self, attr): 244 node.pprint(indent + 2, stream=stream) 245 self._pprint(indent, "", "}", stream=stream) 246 247 # Expression-related details. 248 249 if hasattr(self, "expr"): 250 self.expr.pprint(indent + 2, "- ", stream=stream) 251 if hasattr(self, "nodes"): 252 for node in self.nodes: 253 node.pprint(indent + 2, "- ", stream=stream) 254 if hasattr(self, "lvalue"): 255 self.lvalue.pprint(indent + 2, "->", stream=stream) 256 if hasattr(self, "nstype"): 257 self._pprint(indent + 2, "", self.nstype, stream=stream) 258 if hasattr(self, "args"): 259 for arg in self.pos_args: 260 arg.pprint(indent + 2, "( ", stream=stream) 261 for name, arg in self.kw_args.items(): 262 arg.pprint(indent + 2, "( %s=" % name, stream=stream) 263 if hasattr(self, "star") and self.star: 264 self.star.pprint(indent + 2, "( ", stream=stream) 265 if hasattr(self, "dstar") and self.dstar: 266 self.dstar.pprint(indent + 2, "( ", stream=stream) 267 268 # Annotations. 269 270 if hasattr(self, "accesses"): 271 self._pprint(indent, "", "--------", stream=stream) 272 for ref, attributes in self.accesses.items(): 273 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) 274 self._pprint(indent, "", "--------", stream=stream) 275 if hasattr(self, "writes"): 276 self._pprint(indent, "", "--------", stream=stream) 277 for ref, attribute in self.writes.items(): 278 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) 279 self._pprint(indent, "", "--------", stream=stream) 280 281 # These are the supported "operations" described by simplified program nodes. 282 283 class Pass(Node): "A placeholder node corresponding to pass." 284 class Return(Node): "Return an evaluated expression." 285 class Assign(Node): "A grouping node for assignment-related operations." 286 class Keyword(Node): "A grouping node for keyword arguments." 287 class Global(Node): "A global name designator." 288 class Import(Node): "A module import operation." 289 class LoadTemp(Node): "Load a previously-stored temporary value." 290 class LoadName(Node): "Load a named object." 291 class LoadAttr(Node): "Load an object attribute." 292 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 293 class LoadExc(Node): "Load a handled exception." 294 class StoreTemp(Node): "Store a temporary value." 295 class StoreName(Node): "Associate a name with an object." 296 class StoreAttr(Node): "Associate an object's attribute with a value." 297 class ReleaseTemp(Node): "Release a temporary value." 298 class Conditional(Node): "A conditional node consisting of a test and outcomes." 299 class Try(Node): "A try...except...else...finally grouping node." 300 class Raise(Node): "An exception raising node." 301 class Not(Node): "A negation of an expression." 302 class Invoke(Node): "An invocation." 303 304 # Invocations involve some more work to process calculated attributes. 305 306 class InvokeFunction(Invoke): 307 308 "A function or method invocation." 309 310 def __init__(self, *args, **kw): 311 Invoke.__init__(self, *args, **kw) 312 if hasattr(self, "args"): 313 self.set_args(self.args) 314 self.share_locals = 0 315 316 def set_args(self, args): 317 318 "Sort the 'args' into positional and keyword arguments." 319 320 self.pos_args = [] 321 self.kw_args = {} 322 add_kw = 0 323 for arg in args: 324 if not add_kw: 325 if not isinstance(arg, Keyword): 326 self.pos_args.append(arg) 327 else: 328 add_kw = 1 329 if add_kw: 330 if isinstance(arg, Keyword): 331 self.kw_args[arg.name] = arg 332 else: 333 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 334 335 class InvokeBlock(Invoke): 336 337 "A block or loop invocation." 338 339 def __init__(self, *args, **kw): 340 self.share_locals = 1 341 Invoke.__init__(self, *args, **kw) 342 343 # Named nodes are those which can be referenced in some way. 344 345 class WithName: 346 347 "Node naming." 348 349 def __init__(self): 350 self._full_name = name(self, self.name or "$untitled") 351 352 def full_name(self): 353 return self._full_name 354 355 # Program structure nodes. 356 357 class Module(Node): 358 359 "A Python module." 360 361 def full_name(self): 362 return "module %s" % self.name 363 364 class Subprogram(Node, WithName): 365 366 "A subprogram: functions, methods and loops." 367 368 def __init__(self, *args, **kw): 369 Node.__init__(self, *args, **kw) 370 WithName.__init__(self) 371 372 # Special non-program nodes. 373 374 class Structure(Node): "A non-program node containing some kind of namespace." 375 376 class Class(Structure, WithName): 377 378 "A Python class." 379 380 def __init__(self, *args, **kw): 381 Structure.__init__(self, *args, **kw) 382 WithName.__init__(self) 383 self.instances = [] 384 385 def full_name(self): 386 return "class %s" % self._full_name 387 388 class Instance(Structure): 389 390 "An instance." 391 392 def full_name(self): 393 # NOTE: Wrap the result in a call to name(self, ...) where multiple 394 # NOTE: instances per class can occur. 395 return self.namespace.load("__class__")[0].type._full_name 396 397 def __repr__(self): 398 return "Instance of type '%s'" % self.full_name() 399 400 def __eq__(self, other): 401 # NOTE: Assuming that multiple instances of the same class are equal. 402 return self.full_name() == other.full_name() 403 404 def __hash__(self): 405 return id(self) 406 407 class Constant(Instance): 408 409 "A constant initialised with a type name for future processing." 410 411 def __init__(self, *args, **kw): 412 Instance.__init__(self, *args, **kw) 413 self.typename = self.value.__class__.__name__ 414 415 # vim: tabstop=4 expandtab shiftwidth=4