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, "acquire_locals", 0): 232 self._pprint(indent + 2, "( ", "acquiring locals", 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 Choice(Node): "A special node which indicates a choice of expressions." 303 class Invoke(Node): "An invocation." 304 305 # Invocations involve some more work to process calculated attributes. 306 307 class InvokeFunction(Invoke): 308 309 "A function or method invocation." 310 311 def __init__(self, *args, **kw): 312 Node.__init__(self, *args, **kw) 313 if hasattr(self, "args"): 314 self.set_args(self.args) 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): "A block or loop invocation." 336 337 # Named nodes are those which can be referenced in some way. 338 339 class WithName: 340 341 "Node naming." 342 343 def __init__(self): 344 self._full_name = name(self, self.name or "$untitled") 345 346 def full_name(self): 347 return self._full_name 348 349 # Program structure nodes. 350 351 class Module(Node): 352 353 "A Python module." 354 355 def full_name(self): 356 return "module %s" % self.name 357 358 class Subprogram(Node, WithName): 359 360 "A subprogram: functions, methods and loops." 361 362 def __init__(self, *args, **kw): 363 Node.__init__(self, *args, **kw) 364 WithName.__init__(self) 365 366 # Special non-program nodes. 367 368 class Structure(Node): "A non-program node containing some kind of namespace." 369 370 class Class(Structure, WithName): 371 372 "A Python class." 373 374 def __init__(self, *args, **kw): 375 Structure.__init__(self, *args, **kw) 376 WithName.__init__(self) 377 self.instances = [] 378 379 def full_name(self): 380 return "class %s" % self._full_name 381 382 class Instance(Structure): 383 384 "An instance." 385 386 def full_name(self): 387 # NOTE: Wrap the result in a call to name(self, ...) where multiple 388 # NOTE: instances per class can occur. 389 return self.namespace.load("__class__")[0].type._full_name 390 391 def __repr__(self): 392 return "Instance of type '%s'" % self.full_name() 393 394 def __eq__(self, other): 395 # NOTE: Assuming that multiple instances of the same class are equal. 396 return self.full_name() == other.full_name() 397 398 def __hash__(self): 399 return id(self) 400 401 class Constant(Instance): 402 403 "A constant initialised with a type name for future processing." 404 405 def __init__(self, *args, **kw): 406 Instance.__init__(self, *args, **kw) 407 self.typename = self.value.__class__.__name__ 408 409 # vim: tabstop=4 expandtab shiftwidth=4