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