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