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