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, "( ", 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 Assign(Node): "A grouping node for assignment-related operations." 285 class Keyword(Node): "A grouping node for keyword arguments." 286 class Global(Node): "A global name designator." 287 class Import(Node): "A module import operation." 288 class LoadTemp(Node): "Load a previously-stored temporary value." 289 class LoadName(Node): "Load a named object." 290 class LoadAttr(Node): "Load an object attribute." 291 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 292 class LoadExc(Node): "Load a handled exception." 293 class CheckExc(Node): "Check 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 Try(Node): "A try...except...else...finally grouping node." 299 class Raise(Node): "An exception raising node." 300 class Not(Node): "A negation of an expression." 301 302 # There are two types of return node: return from function and return from 303 # block. 304 305 class Return(Node): 306 307 "Return an evaluated expression." 308 309 pass 310 311 class ReturnFromFunction(Return): 312 pass 313 314 class ReturnFromBlock(Return): 315 pass 316 317 # Some behaviour is set as the default in conditional nodes but may be 318 # overridden. 319 320 class Conditional(Node): 321 322 "A conditional node consisting of a test and outcomes." 323 324 def __init__(self, *args, **kw): 325 self.isolate_test = 0 326 Node.__init__(self, *args, **kw) 327 328 # Invocations involve some more work to process calculated attributes. 329 330 class Invoke(Node): 331 332 "An invocation." 333 334 pass 335 336 class InvokeFunction(Invoke): 337 338 "A function or method invocation." 339 340 def __init__(self, *args, **kw): 341 self.args = [] 342 self.star = None 343 self.dstar = None 344 Invoke.__init__(self, *args, **kw) 345 self.set_args(self.args) 346 self.share_locals = 0 347 348 def set_args(self, args): 349 350 "Sort the 'args' into positional and keyword arguments." 351 352 self.pos_args = [] 353 self.kw_args = {} 354 add_kw = 0 355 for arg in args: 356 if not add_kw: 357 if not isinstance(arg, Keyword): 358 self.pos_args.append(arg) 359 else: 360 add_kw = 1 361 if add_kw: 362 if isinstance(arg, Keyword): 363 self.kw_args[arg.name] = arg.expr 364 else: 365 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 366 367 class InvokeBlock(Invoke): 368 369 "A block or loop invocation." 370 371 def __init__(self, *args, **kw): 372 self.share_locals = 1 373 Invoke.__init__(self, *args, **kw) 374 375 # Named nodes are those which can be referenced in some way. 376 377 class WithName: 378 379 "Node naming." 380 381 def __init__(self): 382 self._full_name = name(self, self.name or "$untitled") 383 384 def full_name(self): 385 return self._full_name 386 387 # Program structure nodes. 388 389 class Module(Node): 390 391 "A Python module." 392 393 def full_name(self): 394 return "module %s" % self.name 395 396 class Subprogram(Node, WithName): 397 398 "A subprogram: functions, methods and loops." 399 400 def __init__(self, *args, **kw): 401 Node.__init__(self, *args, **kw) 402 WithName.__init__(self) 403 404 # Special non-program nodes. 405 406 class Structure(Node): "A non-program node containing some kind of namespace." 407 408 class _Class(Structure, WithName): 409 410 "A Python class." 411 412 def __init__(self, *args, **kw): 413 Structure.__init__(self, *args, **kw) 414 WithName.__init__(self) 415 416 def full_name(self): 417 return "class %s" % self._full_name 418 419 class SingleInstanceClass(_Class): 420 421 "A Python class." 422 423 def __init__(self, *args, **kw): 424 _Class.__init__(self, *args, **kw) 425 self.instance = None 426 427 def has_instance(self, node): 428 return self.instance is not None 429 430 def add_instance(self, node, instance): 431 self.instance = instance 432 433 def get_instance(self, node): 434 return self.instance 435 436 def get_instance_name(self, instance): 437 return self._full_name 438 439 class MultipleInstanceClass(_Class): 440 441 "A Python class." 442 443 def __init__(self, *args, **kw): 444 _Class.__init__(self, *args, **kw) 445 self.instances = {} 446 447 def has_instance(self, node): 448 key = id(node) 449 return self.instances.has_key(key) 450 451 def add_instance(self, node, instance): 452 key = id(node) 453 self.instances[key] = instance 454 455 def get_instance(self, node): 456 key = id(node) 457 return self.instances[key] 458 459 def get_instance_name(self, instance): 460 return name(instance, self._full_name) 461 462 class Instance(Structure): 463 464 "An instance." 465 466 def full_name(self): 467 return self.get_class().get_instance_name(self) 468 469 def get_class(self): 470 return self.namespace.load("__class__")[0].type 471 472 def __repr__(self): 473 return "Instance of type '%s'" % self.full_name() 474 475 def __eq__(self, other): 476 # NOTE: Single instance: all instances are the same 477 # NOTE: Multiple instances: all instances are different 478 return self.full_name() == other.full_name() 479 480 def __hash__(self): 481 return id(self) 482 483 class Constant(Instance): 484 485 "A constant initialised with a type name for future processing." 486 487 def __init__(self, *args, **kw): 488 Instance.__init__(self, *args, **kw) 489 self.typename = self.value.__class__.__name__ 490 491 # Configuration setting. 492 493 Class = SingleInstanceClass 494 #Class = MultipleInstanceClass 495 496 def set_single_instance_mode(): 497 global Class 498 Class = SingleInstanceClass 499 500 def set_multiple_instance_mode(): 501 global Class 502 Class = MultipleInstanceClass 503 504 # vim: tabstop=4 expandtab shiftwidth=4