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.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 common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original" 155 expression_attributes = "expr", "lvalue", "test", "star", "dstar" 156 invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" 157 grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices" 158 159 def __init__(self, original=None, defining=0, **kw): 160 161 """ 162 Initialise a program node with a link to an optional 'original' AST 163 node. An optional 'defining' parameter (if set to a true value), sets 164 this node as the defining node in the original. 165 """ 166 167 self.original = original 168 self.defining = defining 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 manipulation functions. 287 288 def copy(self, new_name=None): 289 290 """ 291 Perform a deep copy of the node, optionally specifying a 'new_name', 292 returning a new unannotated copy. 293 """ 294 295 # Copy the common attributes of this node. 296 297 common = {} 298 for attr in self.common_attributes: 299 if hasattr(self, attr): 300 common[attr] = getattr(self, attr) 301 302 if new_name is not None: 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: 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 CheckExc(Node): "Check a handled exception." 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 377 # There are two types of return node: return from function and return from 378 # block. 379 380 class Return(Node): 381 382 "Return an evaluated expression." 383 384 pass 385 386 class ReturnFromFunction(Return): 387 pass 388 389 class ReturnFromBlock(Return): 390 pass 391 392 # Some behaviour is set as the default in conditional nodes but may be 393 # overridden. 394 395 class Conditional(Node): 396 397 "A conditional node consisting of a test and outcomes." 398 399 def __init__(self, *args, **kw): 400 self.isolate_test = 0 401 Node.__init__(self, *args, **kw) 402 403 # Invocations involve some more work to process calculated attributes. 404 405 class Invoke(Node): 406 407 "An invocation." 408 409 pass 410 411 class InvokeFunction(Invoke): 412 413 "A function or method invocation." 414 415 def __init__(self, *args, **kw): 416 self.args = [] 417 self.star = None 418 self.dstar = None 419 Invoke.__init__(self, *args, **kw) 420 self.set_args(self.args) 421 self.share_locals = 0 422 423 def set_args(self, args): 424 425 "Sort the 'args' into positional and keyword arguments." 426 427 self.pos_args = [] 428 self.kw_args = {} 429 add_kw = 0 430 for arg in args: 431 if not add_kw: 432 if not isinstance(arg, Keyword): 433 self.pos_args.append(arg) 434 else: 435 add_kw = 1 436 if add_kw: 437 if isinstance(arg, Keyword): 438 self.kw_args[arg.name] = arg.expr 439 else: 440 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 441 442 class InvokeBlock(Invoke): 443 444 "A block or loop invocation." 445 446 def __init__(self, *args, **kw): 447 self.share_locals = 1 448 Invoke.__init__(self, *args, **kw) 449 450 # Named nodes are those which can be referenced in some way. 451 452 class WithName: 453 454 "Node naming." 455 456 def __init__(self): 457 self._full_name = name(self, self.name or "$untitled") 458 459 def full_name(self): 460 return self._full_name 461 462 # Program structure nodes. 463 464 class Subprogram(Node, WithName): 465 466 "A subprogram: functions, methods and loops." 467 468 def __init__(self, *args, **kw): 469 Node.__init__(self, *args, **kw) 470 WithName.__init__(self) 471 472 class Comparable(Node): 473 474 "Comparable nodes implementing the 'full_name' method." 475 476 def __eq__(self, other): 477 # NOTE: Single instance: all instances are the same 478 # NOTE: Multiple instances: all instances are different 479 return self.full_name() == other.full_name() 480 481 def __hash__(self): 482 return id(self) 483 484 class Module(Comparable): 485 486 "A Python module." 487 488 def full_name(self): 489 return "module %s" % self.name 490 491 # Special non-program nodes. 492 493 class Structure(Comparable): "A non-program node containing some kind of namespace." 494 495 class _Class(Structure, WithName): 496 497 "A Python class." 498 499 def __init__(self, *args, **kw): 500 Structure.__init__(self, *args, **kw) 501 WithName.__init__(self) 502 503 def full_name(self): 504 return "class %s" % self._full_name 505 506 class SingleInstanceClass(_Class): 507 508 "A Python class." 509 510 def __init__(self, *args, **kw): 511 _Class.__init__(self, *args, **kw) 512 self.instance = None 513 514 def has_instance(self, node): 515 return self.instance is not None 516 517 def add_instance(self, node, instance): 518 self.instance = instance 519 520 def get_instance(self, node): 521 return self.instance 522 523 def get_instance_name(self, instance): 524 return self._full_name 525 526 # Attribute propagation. 527 528 def get_attribute_for_instance(self, attribute, instance): 529 return attribute 530 531 class MultipleInstanceClass(_Class): 532 533 "A Python class." 534 535 def __init__(self, *args, **kw): 536 _Class.__init__(self, *args, **kw) 537 self.instances = {} 538 self.attributes_for_instances = {} 539 540 def _get_key(self, node): 541 return id(getattr(node, "original", None)) # self.module.original 542 543 def has_instance(self, node): 544 return self.instances.has_key(self._get_key(node)) 545 546 def add_instance(self, node, instance): 547 self.instances[self._get_key(node)] = instance 548 549 def get_instance(self, node): 550 return self.instances[self._get_key(node)] 551 552 def get_instance_name(self, instance): 553 return name(instance, self._full_name) 554 555 # Attribute propagation. 556 557 def get_attribute_for_instance(self, attribute, instance): 558 if isinstance(attribute.type, Subprogram): 559 subprogram = attribute.type 560 key = (subprogram, instance) 561 if not self.attributes_for_instances.has_key(key): 562 self.attributes_for_instances[key] = Attribute(attribute.context, subprogram.copy(subprogram.full_name())) 563 return self.attributes_for_instances[key] 564 else: 565 return attribute 566 567 class Instance(Structure): 568 569 "An instance." 570 571 def full_name(self): 572 return self.get_class().get_instance_name(self) 573 574 def get_class(self): 575 return self.namespace.load("__class__")[0].type 576 577 def __repr__(self): 578 return "Instance of type '%s'" % self.full_name() 579 580 def __eq__(self, other): 581 # NOTE: Single instance: all instances are the same 582 # NOTE: Multiple instances: all instances are different 583 return self.full_name() == other.full_name() 584 585 def __hash__(self): 586 return id(self) 587 588 class Constant(Instance): 589 590 "A constant initialised with a type name for future processing." 591 592 def __init__(self, *args, **kw): 593 Instance.__init__(self, *args, **kw) 594 self.typename = self.value.__class__.__name__ 595 596 # NOTE: Hacked full_name avoiding instantiation ordering issues: 597 # NOTE: initialise built-in types, initialise built-in constants. 598 599 #def full_name(self): 600 # return self.typename + "-c" 601 602 class Attribute: 603 604 """ 605 An attribute abstraction, indicating the type of the attribute along with 606 its context or origin. 607 """ 608 609 def __init__(self, context, type): 610 self.context = context 611 self.type = type 612 613 def __eq__(self, other): 614 return hasattr(other, "type") and other.type == self.type or other == self.type 615 616 def __repr__(self): 617 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 618 619 def __hash__(self): 620 return id(self) 621 622 class Self: 623 624 """ 625 A program node encapsulating object/context information in an argument list. 626 This is not particularly like Attribute, Class, Instance or other such 627 things, since it actually appears in the program representation. 628 """ 629 630 def __init__(self, attribute): 631 self.types = [attribute] 632 633 # Configuration setting. 634 635 Class = SingleInstanceClass 636 #Class = MultipleInstanceClass 637 638 def set_single_instance_mode(): 639 global Class 640 Class = SingleInstanceClass 641 642 def set_multiple_instance_mode(): 643 global Class 644 Class = MultipleInstanceClass 645 646 # vim: tabstop=4 expandtab shiftwidth=4