1 #!/usr/bin/env python 2 3 """ 4 Annotate program node structures. The code in this module operates upon nodes 5 which are produced when simplifying AST node trees originating from the compiler 6 module. 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 27 To use this module, the easiest approach is to use the annotate function: 28 29 annotate(module, builtins) 30 31 The more complicated approach involves obtaining an Annotator: 32 33 annotator = Annotator() 34 35 Then, processing an existing module with it: 36 37 annotator.process(module) 38 39 If a module containing built-in classes and functions has already been 40 annotated, such a module should be passed in as an additional argument: 41 42 annotator.process(module, builtins) 43 """ 44 45 from simplified import * 46 import compiler 47 48 class System: 49 50 """ 51 A class maintaining the state of the annotation system. When the system 52 counter can no longer be incremented by any annotation operation, the 53 system may be considered stable and fully annotated. 54 """ 55 56 def __init__(self): 57 self.count = 0 58 def init(self, node): 59 if not hasattr(node, "types"): 60 node.types = [] 61 def annotate(self, node, types): 62 self.init(node) 63 for type in types: 64 if type not in node.types: 65 node.types.append(type) 66 self.count += 1 67 68 system = System() 69 70 # Exceptions. 71 72 class FailureError(Exception): 73 def __init__(self, exc, node, *args): 74 Exception.__init__(self, *args) 75 self.nodes = [node] 76 self.exc = exc 77 def add(self, node): 78 self.nodes.append(node) 79 def __str__(self): 80 return "%s, %s" % (self.exc, self.nodes) 81 82 # Annotation. 83 84 class Annotator(Visitor): 85 86 """ 87 The type annotator which traverses the program nodes, typically depth-first, 88 and maintains a record of the current set of types applying to the currently 89 considered operation. Such types are also recorded on the nodes, and a 90 special "system" record is maintained to monitor the level of annotation 91 activity with a view to recognising when no more annotations are possible. 92 93 Throughout the annotation activity, type information consists of lists of 94 Attribute objects where such objects retain information about the context of 95 the type (since a value in the program may be associated with an object or 96 class) and the actual type of the value being manipulated. Upon accessing 97 attribute information on namespaces, additional accessor information is also 98 exchanged - this provides a means of distinguishing between the different 99 types possible when the means of constructing the namespace may depend on 100 run-time behaviour. 101 """ 102 103 def __init__(self): 104 105 "Initialise the visitor." 106 107 Visitor.__init__(self) 108 self.system = system 109 110 # Satisfy visitor issues. 111 112 self.visitor = self 113 114 def process(self, module, builtins=None): 115 116 """ 117 Process the given 'module', using the optional 'builtins' to access 118 built-in classes and functions. 119 """ 120 121 self.subprograms = [] 122 self.current_subprograms = [] 123 self.current_namespaces = [] 124 125 # Give constants their own namespace. 126 127 for value, constant in module.simplifier.constants.items(): 128 constant.namespace = Namespace() 129 130 # Process the module, supplying builtins if possible. 131 132 self.global_namespace = Namespace() 133 134 if builtins is not None: 135 self.builtins_namespace = builtins.namespace 136 else: 137 self.builtins_namespace = self.global_namespace 138 139 return self.process_node(module) 140 141 def process_node(self, node, locals=None): 142 143 """ 144 Process a subprogram or module 'node', indicating any initial 'locals'. 145 Return an annotated subprogram or module. Note that this method may 146 mutate nodes in the original program. 147 """ 148 149 if locals: 150 self.namespace = locals 151 else: 152 self.namespace = self.global_namespace 153 154 # Record the current subprogram and namespace. 155 156 self.current_subprograms.append(node) 157 self.current_namespaces.append(self.namespace) 158 159 # Add namespace details to any structure involved. 160 161 if getattr(node, "structure", None) is not None: 162 node.structure.namespace = Namespace() 163 164 # Initialise bases where appropriate. 165 166 if hasattr(node.structure, "bases"): 167 base_refs = [] 168 for base in node.structure.bases: 169 self.dispatch(base) 170 base_refs.append(self.namespace.types) 171 node.structure.base_refs = base_refs 172 173 # Dispatch to the code itself. 174 175 node.namespace = self.namespace 176 result = self.dispatch(node) 177 result.namespace = self.namespace 178 179 # Obtain the return values. 180 181 self.last_returns = self.namespace.returns 182 self.returned_locals = self.namespace.return_locals 183 184 # Restore the previous subprogram and namespace. 185 186 self.current_namespaces.pop() 187 if self.current_namespaces: 188 self.namespace = self.current_namespaces[-1] 189 190 self.current_subprograms.pop() 191 192 return result 193 194 def annotate(self, node): 195 196 "Annotate the given 'node' in the system." 197 198 self.system.annotate(node, self.namespace.types) 199 200 # Visitor methods. 201 202 def default(self, node): 203 204 """ 205 Process the given 'node', given that it does not have a specific 206 handler. 207 """ 208 209 for attr in ("expr", "lvalue", "test", "handler"): 210 value = getattr(node, attr, None) 211 if value is not None: 212 setattr(node, attr, self.dispatch(value)) 213 for attr in ("body", "else_", "finally_", "code"): 214 value = getattr(node, attr, None) 215 if value is not None: 216 setattr(node, attr, self.dispatches(value)) 217 return node 218 219 def dispatch(self, node, *args): 220 try: 221 return Visitor.dispatch(self, node, *args) 222 except FailureError, exc: 223 exc.add(node) 224 raise 225 except Exception, exc: 226 raise FailureError(exc, node) 227 228 def visitLoadRef(self, loadref): 229 self.namespace.set_types([Attribute(None, loadref.ref)]) 230 self.annotate(loadref) 231 return loadref 232 233 def visitLoadName(self, loadname): 234 self.namespace.set_types(self.namespace.load(loadname.name)) 235 result = loadname 236 self.annotate(result) 237 return result 238 239 def visitStoreName(self, storename): 240 storename.expr = self.dispatch(storename.expr) 241 self.namespace.store(storename.name, self.namespace.types) 242 return storename 243 244 def visitLoadTemp(self, loadtemp): 245 index = getattr(loadtemp, "index", None) 246 self.namespace.set_types(self.namespace.temp[index][-1]) 247 self.annotate(loadtemp) 248 return loadtemp 249 250 def visitStoreTemp(self, storetemp): 251 storetemp.expr = self.dispatch(storetemp.expr) 252 index = getattr(storetemp, "index", None) 253 if not self.namespace.temp.has_key(index): 254 self.namespace.temp[index] = [] 255 self.namespace.temp[index].append(self.namespace.types) 256 return storetemp 257 258 def visitReleaseTemp(self, releasetemp): 259 index = getattr(releasetemp, "index", None) 260 self.namespace.temp[index].pop() 261 return releasetemp 262 263 def visitLoadAttr(self, loadattr): 264 loadattr.expr = self.dispatch(loadattr.expr) 265 types = [] 266 accesses = {} 267 for attr in self.namespace.types: 268 if not accesses.has_key(attr.type): 269 accesses[attr.type] = [] 270 for attribute, accessor in get_attributes(attr.type, loadattr.name): 271 if attribute is not None: 272 types.append(attribute) 273 else: 274 print "Empty attribute via accessor", accessor 275 accesses[attr.type].append((attribute, accessor)) 276 self.namespace.set_types(types) 277 loadattr.accesses = accesses 278 self.annotate(loadattr) 279 return loadattr 280 281 def visitStoreAttr(self, storeattr): 282 storeattr.expr = self.dispatch(storeattr.expr) 283 expr = self.namespace.types 284 storeattr.lvalue = self.dispatch(storeattr.lvalue) 285 writes = {} 286 for attr in self.namespace.types: 287 if attr is None: 288 print "Empty attribute storage attempt" 289 continue 290 attr.type.namespace.store(storeattr.name, expr) 291 writes[attr.type] = attr.type.namespace.load(storeattr.name) 292 storeattr.writes = writes 293 return storeattr 294 295 def visitConditional(self, conditional): 296 297 # Conditionals keep local namespace changes isolated. 298 # With Return nodes inside the body/else sections, the changes are 299 # communicated to the caller. 300 301 conditional.test = self.dispatch(conditional.test) 302 saved_namespace = self.namespace 303 304 self.namespace = Namespace() 305 self.namespace.merge_namespace(saved_namespace) 306 conditional.body = self.dispatches(conditional.body) 307 body_namespace = self.namespace 308 309 self.namespace = Namespace() 310 self.namespace.merge_namespace(saved_namespace) 311 conditional.else_ = self.dispatches(conditional.else_) 312 else_namespace = self.namespace 313 314 self.namespace = Namespace() 315 self.namespace.merge_namespace(body_namespace) 316 self.namespace.merge_namespace(else_namespace) 317 return conditional 318 319 def visitReturn(self, return_): 320 if hasattr(return_, "expr"): 321 return_.expr = self.dispatch(return_.expr) 322 self.namespace.returns += self.namespace.types 323 self.namespace.snapshot() 324 return return_ 325 326 def visitInvoke(self, invoke): 327 invoke.expr = self.dispatch(invoke.expr) 328 invocation_types = self.namespace.types 329 330 self.process_args(invoke) 331 332 # Now locate and invoke the subprogram. This can be complicated because 333 # the target may be a class or object, and there may be many different 334 # related subprograms. 335 336 invocations = {} 337 338 # Visit each callable in turn, finding subprograms. 339 340 for attr in invocation_types: 341 342 # Deal with class invocations by providing instance objects. 343 # Here, each class is queried for the __init__ method, which may 344 # exist for some combinations of classes in a hierarchy but not for 345 # others. 346 347 if isinstance(attr.type, Class): 348 attributes = get_attributes(attr.type, "__init__") 349 350 # Deal with object invocations by using __call__ methods. 351 352 elif isinstance(attr.type, Instance): 353 attributes = get_attributes(attr.type, "__call__") 354 355 # Normal functions or methods are more straightforward. 356 # Here, we model them using an attribute with no context and with 357 # no associated accessor. 358 359 else: 360 attributes = [(attr, None)] 361 362 # Inspect each attribute and extract the subprogram. 363 364 for attribute, accessor in attributes: 365 366 # If a class is involved, presume that it must create a new 367 # object. 368 369 if isinstance(attr.type, Class): 370 371 # Instantiate the class. 372 # NOTE: Should probably only allocate a single instance. 373 374 instance = Instance() 375 instance.namespace = Namespace() 376 instance.namespace.store("__class__", [attr.type]) 377 378 # For instantiations, switch the context. 379 380 if attribute is not None: 381 attribute = Attribute(instance, attribute.type) 382 383 # Skip cases where no callable is found. 384 385 if attribute is not None: 386 387 # If a subprogram is defined, invoke it. 388 389 self.invoke_subprogram(invoke, attribute) 390 invocations[callable] = attribute.type 391 392 else: 393 print "Invocation type is None" 394 395 if isinstance(attr.type, Class): 396 397 # Associate the instance with the result of this invocation. 398 399 self.namespace.set_types([Attribute(None, instance)]) 400 self.annotate(invoke) 401 402 invoke.invocations = invocations 403 404 return invoke 405 406 # Utility methods. 407 408 def invoke_subprogram(self, invoke, subprogram): 409 410 """ 411 Invoke using the given 'invoke' node the given 'subprogram'. 412 """ 413 414 # Test to see if anything has changed. 415 416 if hasattr(invoke, "syscount") and invoke.syscount == self.system.count: 417 return 418 419 # Test for context information, making it into a real attribute. 420 421 if subprogram.context is not None: 422 context = Attribute(None, subprogram.context) 423 target = subprogram.type 424 else: 425 context = None 426 target = subprogram.type 427 428 # Provide the correct namespace for the invocation. 429 430 if isinstance(invoke, InvokeBlock): 431 namespace = Namespace() 432 namespace.merge_namespace(self.namespace) 433 else: 434 items = self.make_items(invoke, target, context) 435 namespace = self.make_namespace(items) 436 437 # Process the subprogram. 438 439 self.process_node(target, namespace) 440 441 # NOTE: Improve and verify this. 442 443 if getattr(target, "returns_value", 0): 444 self.namespace.set_types(self.last_returns) 445 self.annotate(invoke) 446 447 if isinstance(invoke, InvokeBlock): 448 for locals in self.returned_locals: 449 self.namespace.merge_namespace(locals) 450 451 # Remember the state of the system. 452 453 invoke.syscount = self.system.count 454 455 def process_args(self, invoke): 456 457 # NOTE: Consider initialiser invocation for classes. 458 459 types = [] 460 args = [] 461 462 # Get type information for regular arguments. 463 464 for arg in invoke.args: 465 args.append(self.dispatch(arg)) 466 types.append(self.namespace.types) 467 468 # Get type information for star and dstar arguments. 469 470 if invoke.star is not None: 471 param, default = invoke.star 472 default = self.dispatch(default) 473 invoke.star = param, default 474 types.append(default.types) 475 476 if invoke.dstar is not None: 477 param, default = invoke.dstar 478 default = self.dispatch(default) 479 invoke.dstar = param, default 480 types.append(default.types) 481 482 invoke.args = args 483 484 def make_items(self, invocation, subprogram, context): 485 486 """ 487 Make an items mapping for the 'invocation' of the 'subprogram' using the 488 given 'context' (which may be None). 489 """ 490 491 if context is not None: 492 args = [Self(context)] + invocation.args 493 else: 494 args = invocation.args 495 496 params = subprogram.params 497 items = [] 498 keywords = {} 499 500 # Process the specified arguments. 501 502 for arg in args: 503 if isinstance(arg, Keyword): 504 keywords[arg.name] = arg.expr 505 continue 506 elif params: 507 param, default = params[0] 508 if arg is None: 509 arg = default 510 else: 511 raise TypeError, "Invocation has too many arguments." 512 items.append((param, arg.types)) 513 params = params[1:] 514 515 # Collect the remaining defaults. 516 517 while params: 518 param, default = params[0] 519 if keywords.has_key(param): 520 arg = keywords[param] 521 else: 522 arg = self.dispatch(default) # NOTE: Review reprocessing. 523 items.append((param, arg.types)) 524 params = params[1:] 525 526 # Add star and dstar. 527 528 if invocation.star is not None: 529 if subprogram.star is not None: 530 param, default = subprogram.star 531 items.append((param, invocation.star.types)) 532 else: 533 raise TypeError, "Invocation provides unwanted *args." 534 elif subprogram.star is not None: 535 param, default = subprogram.star 536 arg = self.dispatch(default) # NOTE: Review reprocessing. 537 items.append((param, arg.types)) 538 539 if invocation.dstar is not None: 540 if subprogram.dstar is not None: 541 param, default = subprogram.dstar 542 items.append((param, invocation.dstar.types)) 543 else: 544 raise TypeError, "Invocation provides unwanted **args." 545 elif subprogram.dstar is not None: 546 param, default = subprogram.dstar 547 arg = self.dispatch(default) # NOTE: Review reprocessing. 548 items.append((param, arg.types)) 549 550 return items 551 552 def make_namespace(self, items): 553 namespace = Namespace() 554 namespace.merge_items(items) 555 return namespace 556 557 # Namespace-related abstractions. 558 559 class Namespace: 560 561 """ 562 A local namespace which may either relate to a genuine set of function 563 locals or the initialisation of a structure or module. 564 """ 565 566 def __init__(self): 567 568 """ 569 Initialise the namespace with a mapping of local names to possible 570 types, a list of return values and of possible returned local 571 namespaces. The namespace also tracks the "current" types and a mapping 572 of temporary value names to types. 573 """ 574 575 self.names = {} 576 self.returns = [] 577 self.return_locals = [] 578 self.temp = {} 579 self.types = [] 580 581 def set_types(self, types): 582 self.types = types 583 584 def store(self, name, types): 585 self.names[name] = types 586 587 def load(self, name): 588 return self.names[name] 589 590 def merge(self, name, types): 591 if not self.names.has_key(name): 592 self.names[name] = types[:] 593 else: 594 existing = self.names[name] 595 for type in types: 596 if type not in existing: 597 existing.append(type) 598 599 def merge_namespace(self, namespace): 600 self.merge_items(namespace.names.items()) 601 602 def merge_items(self, items): 603 for name, types in items: 604 self.merge(name, types) 605 606 def snapshot(self): 607 608 "Make a snapshot of the locals and remember them." 609 610 namespace = Namespace() 611 namespace.merge_namespace(self) 612 self.return_locals.append(namespace) 613 614 def __repr__(self): 615 return repr(self.names) 616 617 class Attribute: 618 619 """ 620 An attribute abstraction, indicating the type of the attribute along with 621 its context or origin. 622 """ 623 624 def __init__(self, context, type): 625 self.context = context 626 self.type = type 627 628 def __eq__(self, other): 629 return hasattr(other, "type") and other.type == self.type or other == self.type 630 631 def __repr__(self): 632 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 633 634 class Self: 635 def __init__(self, attribute): 636 self.types = [attribute] 637 638 def find_attributes(structure, name): 639 640 """ 641 Find for the given 'structure' all attributes for the given 'name', visiting 642 base classes where appropriate and returning the attributes in order of 643 descending precedence for all possible base classes. 644 645 The elements in the result list are 2-tuples which contain the attribute and 646 the structure involved in accessing the attribute. 647 """ 648 649 # First attempt to search the instance/class namespace. 650 651 try: 652 l = structure.namespace.load(name) 653 attributes = [] 654 for attribute in l: 655 attributes.append((attribute, structure)) 656 657 # If that does not work, attempt to investigate any class or base classes. 658 659 except KeyError: 660 attributes = [] 661 662 # Investigate any instance's implementing class. 663 664 if isinstance(structure, Instance): 665 for cls in structure.namespace.load("__class__"): 666 l = get_attributes(cls, name) 667 for attribute in l: 668 if attribute not in attributes: 669 attributes.append(attribute) 670 671 # Investigate any class's base classes. 672 673 elif isinstance(structure, Class): 674 675 # If no base classes exist, return an indicator that no attribute 676 # exists. 677 678 if not structure.base_refs: 679 return [(None, structure)] 680 681 # Otherwise, find all possible base classes. 682 683 for base_refs in structure.base_refs: 684 base_attributes = [] 685 686 # For each base class, find attributes either in the base 687 # class or its own base classes. 688 689 for base_ref in base_refs: 690 l = get_attributes(base_ref, name) 691 for attribute in l: 692 if attribute not in base_attributes: 693 base_attributes.append(attribute) 694 695 attributes += base_attributes 696 697 return attributes 698 699 def get_attributes(structure, name): 700 701 """ 702 Return all possible attributes for the given 'structure' having the given 703 'name', wrapping each attribute in an Attribute object which includes 704 context information for the attribute access. 705 706 The elements in the result list are 2-tuples which contain the attribute and 707 the structure involved in accessing the attribute. 708 """ 709 710 if isinstance(structure, Attribute): 711 structure = structure.type 712 results = [] 713 for attribute, accessor in find_attributes(structure, name): 714 if attribute is not None and isinstance(structure, Structure): 715 results.append((Attribute(structure, attribute.type), accessor)) 716 else: 717 results.append((attribute, accessor)) 718 return results 719 720 # Convenience functions. 721 722 def annotate(module, builtins=None): 723 724 """ 725 Annotate the given 'module', also employing the optional 'builtins' module, 726 if specified. 727 """ 728 729 annotator = Annotator() 730 if builtins is not None: 731 annotator.process(module, builtins) 732 else: 733 annotator.process(module) 734 735 def annotate_all(modules, builtins): 736 annotate(builtins) 737 for module in modules: 738 annotate(module, builtins) 739 740 # vim: tabstop=4 expandtab shiftwidth=4