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, 2007 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.names = {} 68 69 def get(self, obj): 70 return obj._unique_name 71 72 def set(self, obj, name): 73 if hasattr(obj, "_unique_name"): 74 return 75 if not self.names.has_key(name): 76 self.names[name] = 0 77 n = self.names[name] + 1 78 self.names[name] = n 79 obj._unique_name = "%s%s%d" % (name, self.index_separator, n) 80 81 naming = Naming() 82 83 def name(obj, name): 84 85 "Return a unique name for the given 'obj', indicating the base 'name'." 86 87 naming.set(obj, name) 88 return naming.get(obj) 89 90 # Elementary visitor support. 91 92 class Visitor(ASTVisitor): 93 94 "A visitor base class." 95 96 def __init__(self): 97 ASTVisitor.__init__(self) 98 99 def default(self, node, *args): 100 raise ValueError, node.__class__ 101 102 def dispatch(self, node, *args): 103 return ASTVisitor.dispatch(self, node, *args) 104 105 def dispatches(self, nodes, *args): 106 results = [] 107 for node in nodes: 108 results.append(self.dispatch(node, *args)) 109 return results 110 111 def dispatch_dict(self, d, *args): 112 results = {} 113 for name, node in d.items(): 114 results[name] = self.dispatch(node, *args) 115 return results 116 117 # Simplified program nodes. 118 119 class Node: 120 121 """ 122 A result node with common attributes: 123 124 original The original node from which this node was created. 125 defining Whether the node defines something in the original program. 126 name Any name involved (variable or attribute). 127 index Any index involved (temporary variable name). 128 value Any constant value. 129 ref Any reference to (for example) subprograms. 130 nstype Any indication of the namespace type involved in a name access. 131 132 Expression-related attributes: 133 134 expr Any contributing expression. 135 lvalue Any target expression. 136 test Any test expression in a conditional instruction. 137 138 Invocation and subprogram attributes: 139 140 args Any collection of argument nodes. 141 params Any collection of parameter nodes and defaults. 142 143 Statement-grouping attributes: 144 145 body Any conditional code depending on the success of a test. 146 else_ Any conditional code depending on the failure of a test. 147 handler Any exception handler code. 148 finally_ Any code which will be executed regardless. 149 code Any unconditional code. 150 choices Any choices which may be included in the final program. 151 """ 152 153 common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original" 154 expression_attributes = "expr", "lvalue", "test", "star", "dstar" 155 invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" 156 grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices" 157 158 def __init__(self, original=None, defining=0, **kw): 159 160 """ 161 Initialise a program node with a link to an optional 'original' AST 162 node. An optional 'defining' parameter (if set to a true value), sets 163 this node as the defining node in the original. 164 """ 165 166 self.original = original 167 self.defining = defining 168 self.copies = [] 169 170 if self.original is not None and defining: 171 self.original._node = self 172 for name, value in kw.items(): 173 setattr(self, name, value) 174 175 def __repr__(self): 176 177 "Return a readable representation." 178 179 if hasattr(self, "full_name"): 180 s = "%s '%s'" % (self.__class__.__name__, self.full_name()) 181 elif hasattr(self, "name"): 182 s = "%s '%s'" % (self.__class__.__name__, self.name) 183 elif hasattr(self, "index"): 184 s = "%s (%s)" % (self.__class__.__name__, self.index) 185 elif hasattr(self, "value"): 186 s = "%s %s" % (self.__class__.__name__, repr(self.value)) 187 elif hasattr(self, "ref"): 188 s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) 189 else: 190 s = "%s" % (self.__class__.__name__,) 191 192 # Annotations. 193 194 if hasattr(self, "types"): 195 return "%s -> %s" % (s, self.types) 196 else: 197 return s 198 199 def _pprint(self, indent, continuation, s, stream=None): 200 201 """ 202 Print, at the given 'indent' level, with the given 'continuation' text, 203 the string 's', either to the given, optional 'stream' or to standard 204 output, this node's "pretty" representation. 205 """ 206 207 stream = stream or sys.stdout 208 if continuation: 209 print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s 210 else: 211 print >>stream, (" " * indent) + s 212 213 def pprint(self, indent=0, continuation=None, stream=None): 214 215 """ 216 Print, at the given, optional 'indent', with the given optional 217 'continuation' text, either to the given, optional 'stream' or to 218 standard output, this node's "pretty" representation along with its 219 children and their "pretty" representation (and so on). 220 """ 221 222 stream = stream or sys.stdout 223 self._pprint(indent, continuation, repr(self), stream) 224 225 # Subprogram-related details. 226 227 if hasattr(self, "params"): 228 for name, default in self.params: 229 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 230 if hasattr(self, "star") and self.star: 231 name, default = self.star 232 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 233 if hasattr(self, "dstar") and self.dstar: 234 name, default = self.dstar 235 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 236 if getattr(self, "internal", 0): 237 self._pprint(indent + 2, "( ", "internal", stream=stream) 238 if getattr(self, "structure", 0): 239 self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) 240 241 # Expression-related details. 242 243 if hasattr(self, "expr"): 244 self.expr.pprint(indent + 2, "- ", stream=stream) 245 if hasattr(self, "nodes"): 246 for node in self.nodes: 247 node.pprint(indent + 2, "- ", stream=stream) 248 if hasattr(self, "lvalue"): 249 self.lvalue.pprint(indent + 2, "->", stream=stream) 250 if hasattr(self, "nstype"): 251 self._pprint(indent + 2, "", self.nstype, stream=stream) 252 if hasattr(self, "args"): 253 for arg in self.pos_args: 254 arg.pprint(indent + 2, "( ", stream=stream) 255 for name, arg in self.kw_args.items(): 256 arg.pprint(indent + 2, "( ", stream=stream) 257 if hasattr(self, "star") and self.star: 258 self.star.pprint(indent + 2, "( ", stream=stream) 259 if hasattr(self, "dstar") and self.dstar: 260 self.dstar.pprint(indent + 2, "( ", stream=stream) 261 262 # Statement-related details. 263 264 if hasattr(self, "test"): 265 self.test.pprint(indent + 2, "? ", stream=stream) 266 for attr in self.grouping_attributes: 267 if hasattr(self, attr) and getattr(self, attr): 268 self._pprint(indent, "", "%s {" % attr, stream=stream) 269 for node in getattr(self, attr): 270 node.pprint(indent + 2, stream=stream) 271 self._pprint(indent, "", "}", stream=stream) 272 273 # Annotations. 274 275 if hasattr(self, "accesses"): 276 self._pprint(indent, "", "--------", stream=stream) 277 for ref, attributes in self.accesses.items(): 278 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) 279 self._pprint(indent, "", "--------", stream=stream) 280 if hasattr(self, "writes"): 281 self._pprint(indent, "", "--------", stream=stream) 282 for ref, attribute in self.writes.items(): 283 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) 284 self._pprint(indent, "", "--------", stream=stream) 285 286 # Node discovery functions. 287 288 def active(self): 289 290 "Return the active copies of this node or a list containing this node." 291 292 return self.copies or [self] 293 294 # Node manipulation functions. 295 296 def copy(self, new_name=None): 297 298 """ 299 Perform a deep copy of the node, optionally specifying a 'new_name', 300 returning a new unannotated copy. 301 """ 302 303 # Copy the common attributes of this node. 304 305 common = {} 306 for attr in self.common_attributes: 307 if hasattr(self, attr): 308 common[attr] = getattr(self, attr) 309 310 if new_name is not None: 311 common["copy_of"] = self 312 common["name"] = new_name 313 314 # Instantiate the copy, avoiding side-effects with original and defining. 315 316 node = self.__class__(**common) 317 node.defining = self.defining 318 319 # Add links to copies from originals. 320 321 self.copies.append(node) 322 323 # Copy attributes of different types. 324 325 for attr in self.expression_attributes: 326 if hasattr(self, attr): 327 n = getattr(self, attr) 328 if n is None: 329 n2 = n 330 else: 331 n2 = n.copy() 332 setattr(node, attr, n2) 333 334 for attr in self.invocation_attributes: 335 if hasattr(self, attr): 336 l = getattr(self, attr) 337 l2 = [] 338 for name, n in l: 339 if n is None: 340 l2.append((name, n)) 341 else: 342 l2.append((name, n.copy())) 343 setattr(node, attr, l2) 344 345 for attr in self.grouping_attributes: 346 if hasattr(self, attr): 347 l = getattr(self, attr) 348 setattr(node, attr, [n.copy() for n in l]) 349 350 # Arguments are usually processed further - "args" is useless. 351 352 if hasattr(self, "pos_args"): 353 node.pos_args = [n.copy() for n in self.pos_args] 354 355 if hasattr(self, "kw_args"): 356 node.kw_args = {} 357 for name, n in self.kw_args.items(): 358 node.kw_args[name] = n.copy() 359 360 return node 361 362 # These are the supported "operations" described by simplified program nodes. 363 364 class Pass(Node): "A placeholder node corresponding to pass." 365 class Assign(Node): "A grouping node for assignment-related operations." 366 class Keyword(Node): "A grouping node for keyword arguments." 367 class Global(Node): "A global name designator." 368 class Import(Node): "A module import operation." 369 class LoadTemp(Node): "Load a previously-stored temporary value." 370 class LoadName(Node): "Load a named object." 371 class LoadAttr(Node): "Load an object attribute." 372 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 373 class LoadExc(Node): "Load a handled exception." 374 class ResetExc(Node): "Reset the exception state." 375 class StoreTemp(Node): "Store a temporary value." 376 class StoreName(Node): "Associate a name with an object." 377 class StoreAttr(Node): "Associate an object's attribute with a value." 378 class ReleaseTemp(Node): "Release a temporary value." 379 class Try(Node): "A try...except...else...finally grouping node." 380 class Raise(Node): "An exception raising node." 381 class Not(Node): "A negation of an expression." 382 class CheckType(Node): "Check a value's type from a list of choices." 383 384 # There are two types of return node: return from function and return from 385 # block. 386 387 class Return(Node): 388 389 "Return an evaluated expression." 390 391 pass 392 393 class ReturnFromFunction(Return): 394 pass 395 396 class ReturnFromBlock(Return): 397 pass 398 399 # Some behaviour is set as the default in conditional nodes but may be 400 # overridden. 401 402 class Conditional(Node): 403 404 "A conditional node consisting of a test and outcomes." 405 406 def __init__(self, *args, **kw): 407 self.isolate_test = 0 408 Node.__init__(self, *args, **kw) 409 410 # Invocations involve some more work to process calculated attributes. 411 412 class Invoke(Node): 413 414 "An invocation." 415 416 pass 417 418 class InvokeFunction(Invoke): 419 420 "A function or method invocation." 421 422 def __init__(self, *args, **kw): 423 self.args = [] 424 self.star = None 425 self.dstar = None 426 Invoke.__init__(self, *args, **kw) 427 self.set_args(self.args) 428 self.share_locals = 0 429 430 def set_args(self, args): 431 432 "Sort the 'args' into positional and keyword arguments." 433 434 self.pos_args = [] 435 self.kw_args = {} 436 add_kw = 0 437 for arg in args: 438 if not add_kw: 439 if not isinstance(arg, Keyword): 440 self.pos_args.append(arg) 441 else: 442 add_kw = 1 443 if add_kw: 444 if isinstance(arg, Keyword): 445 self.kw_args[arg.name] = arg.expr 446 else: 447 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 448 449 class InvokeBlock(Invoke): 450 451 "A block or loop invocation." 452 453 def __init__(self, *args, **kw): 454 self.share_locals = 1 455 Invoke.__init__(self, *args, **kw) 456 457 # Named nodes are those which can be referenced in some way. 458 459 class WithName: 460 461 "Node naming." 462 463 def __init__(self): 464 self._full_name = name(self, self.name or "$untitled") 465 466 def full_name(self): 467 return self._full_name 468 469 # Program structure nodes. 470 471 class Subprogram(Node, WithName): 472 473 "A subprogram: functions, methods and loops." 474 475 def __init__(self, *args, **kw): 476 Node.__init__(self, *args, **kw) 477 WithName.__init__(self) 478 479 class Comparable(Node): 480 481 "Comparable nodes implementing the 'full_name' method." 482 483 def __eq__(self, other): 484 # NOTE: Single instance: all instances are the same 485 # NOTE: Multiple instances: all instances are different 486 if hasattr(other, "full_name"): 487 return self.full_name() == other.full_name() 488 else: 489 return NotImplemented 490 491 def __hash__(self): 492 return id(self) 493 494 class Module(Comparable): 495 496 "A Python module." 497 498 def full_name(self): 499 return "module %s" % self.name 500 501 # Special non-program nodes. 502 503 class Structure(Comparable): "A non-program node containing some kind of namespace." 504 505 class _Class(Structure, WithName): 506 507 "A Python class." 508 509 def __init__(self, *args, **kw): 510 Structure.__init__(self, *args, **kw) 511 WithName.__init__(self) 512 513 def full_name(self): 514 return "class %s" % self._full_name 515 516 class SingleInstanceClass(_Class): 517 518 "A Python class." 519 520 def __init__(self, *args, **kw): 521 _Class.__init__(self, *args, **kw) 522 self.instance = None 523 524 def has_instance(self, node): 525 return self.instance is not None 526 527 def add_instance(self, node, instance): 528 self.instance = instance 529 530 def get_instance(self, node): 531 return self.instance 532 533 def get_instance_name(self, instance): 534 return self._full_name 535 536 # Attribute propagation. 537 538 def get_attribute_for_instance(self, attribute, instance): 539 return attribute 540 541 class MultipleInstanceClass(_Class): 542 543 "A Python class." 544 545 def __init__(self, *args, **kw): 546 _Class.__init__(self, *args, **kw) 547 self.instances = {} 548 self.attributes_for_instances = {} 549 550 def _get_key(self, node): 551 return id(getattr(node, "original", None)) # self.module.original 552 553 def has_instance(self, node): 554 return self.instances.has_key(self._get_key(node)) 555 556 def add_instance(self, node, instance): 557 self.instances[self._get_key(node)] = instance 558 559 def get_instance(self, node): 560 return self.instances[self._get_key(node)] 561 562 def get_instance_name(self, instance): 563 return name(instance, self._full_name) 564 565 # Attribute propagation. 566 567 def get_attribute_for_instance(self, attribute, instance): 568 if isinstance(attribute.type, Subprogram): 569 subprogram = attribute.type 570 key = (subprogram, instance) 571 if not self.attributes_for_instances.has_key(key): 572 self.attributes_for_instances[key] = Attribute(attribute.context, subprogram.copy(subprogram.full_name())) 573 return self.attributes_for_instances[key] 574 else: 575 return attribute 576 577 class Instance(Structure): 578 579 "An instance." 580 581 def full_name(self): 582 return self.get_class().get_instance_name(self) 583 584 def get_class(self): 585 return self.namespace.load("__class__")[0].type 586 587 def __repr__(self): 588 return "Instance of type '%s'" % self.full_name() 589 590 def __eq__(self, other): 591 # NOTE: Single instance: all instances are the same 592 # NOTE: Multiple instances: all instances are different 593 return self.full_name() == other.full_name() 594 595 def __hash__(self): 596 return id(self) 597 598 class Constant(Instance): 599 600 "A constant initialised with a type name for future processing." 601 602 def __init__(self, *args, **kw): 603 Instance.__init__(self, *args, **kw) 604 self.typename = self.value.__class__.__name__ 605 606 # NOTE: Hacked full_name avoiding instantiation ordering issues: 607 # NOTE: initialise built-in types, initialise built-in constants. 608 609 #def full_name(self): 610 # return self.typename + "-c" 611 612 class Attribute: 613 614 """ 615 An attribute abstraction, indicating the type of the attribute along with 616 its context or origin. 617 """ 618 619 def __init__(self, context, type): 620 self.context = context 621 self.type = type 622 623 def __eq__(self, other): 624 return hasattr(other, "type") and other.type == self.type or other == self.type 625 626 def __repr__(self): 627 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 628 629 def __hash__(self): 630 return id(self) 631 632 class Self: 633 634 """ 635 A program node encapsulating object/context information in an argument list. 636 This is not particularly like Attribute, Class, Instance or other such 637 things, since it actually appears in the program representation. 638 """ 639 640 def __init__(self, attribute): 641 self.types = [attribute] 642 643 class Op: 644 645 "A replacement AST node representing an operation in a Compare construct." 646 647 def __init__(self, name, expr): 648 self.name = name 649 self.expr = expr 650 651 # Configuration setting. 652 653 Class = SingleInstanceClass 654 #Class = MultipleInstanceClass 655 656 def set_single_instance_mode(): 657 global Class 658 Class = SingleInstanceClass 659 660 def set_multiple_instance_mode(): 661 global Class 662 Class = MultipleInstanceClass 663 664 # vim: tabstop=4 expandtab shiftwidth=4