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