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 # Expression-related details. 237 238 if hasattr(self, "expr"): 239 self.expr.pprint(indent + 2, "- ", stream=stream) 240 if hasattr(self, "nodes"): 241 for node in self.nodes: 242 node.pprint(indent + 2, "- ", stream=stream) 243 if hasattr(self, "lvalue"): 244 self.lvalue.pprint(indent + 2, "->", stream=stream) 245 if hasattr(self, "nstype"): 246 self._pprint(indent + 2, "", self.nstype, stream=stream) 247 if hasattr(self, "args"): 248 for arg in self.pos_args: 249 arg.pprint(indent + 2, "( ", stream=stream) 250 for name, arg in self.kw_args.items(): 251 arg.pprint(indent + 2, "( %s=" % name, stream=stream) 252 if hasattr(self, "star") and self.star: 253 self.star.pprint(indent + 2, "( ", stream=stream) 254 if hasattr(self, "dstar") and self.dstar: 255 self.dstar.pprint(indent + 2, "( ", stream=stream) 256 257 # Statement-related details. 258 259 if hasattr(self, "test"): 260 self.test.pprint(indent + 2, "? ", stream=stream) 261 for attr in "code", "body", "else_", "handler", "finally_", "choices": 262 if hasattr(self, attr) and getattr(self, attr): 263 self._pprint(indent, "", "%s {" % attr, stream=stream) 264 for node in getattr(self, attr): 265 node.pprint(indent + 2, stream=stream) 266 self._pprint(indent, "", "}", 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 CheckExc(Node): "Check a handled exception." 295 class StoreTemp(Node): "Store a temporary value." 296 class StoreName(Node): "Associate a name with an object." 297 class StoreAttr(Node): "Associate an object's attribute with a value." 298 class ReleaseTemp(Node): "Release a temporary value." 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 # Some behaviour is set as the default in conditional nodes but may be 305 # overridden. 306 307 class Conditional(Node): 308 309 "A conditional node consisting of a test and outcomes." 310 311 def __init__(self, *args, **kw): 312 self.isolate_test = 0 313 Node.__init__(self, *args, **kw) 314 315 # Invocations involve some more work to process calculated attributes. 316 317 class InvokeFunction(Invoke): 318 319 "A function or method invocation." 320 321 def __init__(self, *args, **kw): 322 Invoke.__init__(self, *args, **kw) 323 if hasattr(self, "args"): 324 self.set_args(self.args) 325 self.share_locals = 0 326 327 def set_args(self, args): 328 329 "Sort the 'args' into positional and keyword arguments." 330 331 self.pos_args = [] 332 self.kw_args = {} 333 add_kw = 0 334 for arg in args: 335 if not add_kw: 336 if not isinstance(arg, Keyword): 337 self.pos_args.append(arg) 338 else: 339 add_kw = 1 340 if add_kw: 341 if isinstance(arg, Keyword): 342 self.kw_args[arg.name] = arg 343 else: 344 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 345 346 class InvokeBlock(Invoke): 347 348 "A block or loop invocation." 349 350 def __init__(self, *args, **kw): 351 self.share_locals = 1 352 Invoke.__init__(self, *args, **kw) 353 354 # Named nodes are those which can be referenced in some way. 355 356 class WithName: 357 358 "Node naming." 359 360 def __init__(self): 361 self._full_name = name(self, self.name or "$untitled") 362 363 def full_name(self): 364 return self._full_name 365 366 # Program structure nodes. 367 368 class Module(Node): 369 370 "A Python module." 371 372 def full_name(self): 373 return "module %s" % self.name 374 375 class Subprogram(Node, WithName): 376 377 "A subprogram: functions, methods and loops." 378 379 def __init__(self, *args, **kw): 380 Node.__init__(self, *args, **kw) 381 WithName.__init__(self) 382 383 # Special non-program nodes. 384 385 class Structure(Node): "A non-program node containing some kind of namespace." 386 387 class Class(Structure, WithName): 388 389 "A Python class." 390 391 def __init__(self, *args, **kw): 392 Structure.__init__(self, *args, **kw) 393 WithName.__init__(self) 394 self.instances = [] 395 396 def full_name(self): 397 return "class %s" % self._full_name 398 399 class Instance(Structure): 400 401 "An instance." 402 403 def full_name(self): 404 # NOTE: Wrap the result in a call to name(self, ...) where multiple 405 # NOTE: instances per class can occur. 406 return self.get_class()._full_name 407 408 def get_class(self): 409 return self.namespace.load("__class__")[0].type 410 411 def __repr__(self): 412 return "Instance of type '%s'" % self.full_name() 413 414 def __eq__(self, other): 415 # NOTE: Assuming that multiple instances of the same class are equal. 416 return self.full_name() == other.full_name() 417 418 def __hash__(self): 419 return id(self) 420 421 class Constant(Instance): 422 423 "A constant initialised with a type name for future processing." 424 425 def __init__(self, *args, **kw): 426 Instance.__init__(self, *args, **kw) 427 self.typename = self.value.__class__.__name__ 428 429 # vim: tabstop=4 expandtab shiftwidth=4