1 #!/usr/bin/env python 2 3 """ 4 Inspect and obtain module structure. 5 6 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013, 7 2014, 2015, 2016 Paul Boddie <paul@boddie.org.uk> 8 9 This program is free software; you can redistribute it and/or modify it under 10 the terms of the GNU General Public License as published by the Free Software 11 Foundation; either version 3 of the License, or (at your option) any later 12 version. 13 14 This program is distributed in the hope that it will be useful, but WITHOUT 15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 16 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 17 details. 18 19 You should have received a copy of the GNU General Public License along with 20 this program. If not, see <http://www.gnu.org/licenses/>. 21 """ 22 23 from branching import BranchTracker 24 from common import get_argnames, init_item, predefined_constants 25 from modules import BasicModule, CacheWritingModule, InspectionNaming 26 from referencing import Reference 27 from resolving import NameResolving 28 from results import AccessRef, InstanceRef, InvocationRef, LiteralSequenceRef, \ 29 LocalNameRef, NameRef, ResolvedNameRef 30 import compiler 31 import sys 32 33 class InspectedModule(BasicModule, CacheWritingModule, NameResolving, InspectionNaming): 34 35 "A module inspector." 36 37 def __init__(self, name, importer): 38 39 "Initialise the module with basic details." 40 41 BasicModule.__init__(self, name, importer) 42 43 self.in_class = False 44 self.in_conditional = False 45 self.global_attr_accesses = {} 46 47 # Nested scope handling. 48 49 self.parent_function = None 50 self.propagated_names = {} 51 52 # Usage tracking. 53 54 self.trackers = [] 55 self.attr_accessor_branches = {} 56 57 def __repr__(self): 58 return "InspectedModule(%r, %r)" % (self.name, self.importer) 59 60 # Principal methods. 61 62 def parse(self, filename): 63 64 "Parse the file having the given 'filename'." 65 66 self.parse_file(filename) 67 68 # Inspect the module. 69 70 self.start_tracking_in_module() 71 72 # Detect and record imports and globals declared in the module. 73 74 self.assign_general_local("__name__", self.get_constant("str", self.name)) 75 self.assign_general_local("__file__", self.get_constant("str", filename)) 76 self.process_structure(self.astnode) 77 78 # Set the class of the module after the definition has occurred. 79 80 ref = self.get_builtin("object") 81 self.set_name("__class__", ref) 82 83 # Get module-level attribute usage details. 84 85 self.stop_tracking_in_module() 86 87 # Collect external name references. 88 89 self.collect_names() 90 91 def complete(self): 92 93 "Complete the module inspection." 94 95 # Resolve names not definitively mapped to objects. 96 97 self.resolve() 98 99 # Define the invocation requirements in each namespace. 100 101 self.set_invocation_usage() 102 103 # Propagate to the importer information needed in subsequent activities. 104 105 self.propagate() 106 107 # Accessory methods. 108 109 def collect_names(self): 110 111 "Collect the names used by each scope." 112 113 for path in self.names_used.keys(): 114 self.collect_names_for_path(path) 115 116 def collect_names_for_path(self, path): 117 118 "Collect the names used by the given 'path'." 119 120 names = self.names_used.get(path) 121 if not names: 122 return 123 124 in_function = self.function_locals.has_key(path) 125 126 for name in names: 127 if name in predefined_constants or in_function and name in self.function_locals[path]: 128 continue 129 130 # Find local definitions (within static namespaces). 131 132 key = "%s.%s" % (path, name) 133 ref = self.get_resolved_object(key) 134 if ref: 135 self.importer.all_name_references[key] = self.name_references[key] = ref.alias(key) 136 continue 137 138 # Find global or built-in definitions. 139 140 ref = self.get_resolved_global_or_builtin(name) 141 if ref: 142 self.importer.all_name_references[key] = self.name_references[key] = ref 143 continue 144 145 print >>sys.stderr, "Name not recognised: %s in %s" % (name, path) 146 init_item(self.names_missing, path, set) 147 self.names_missing[path].add(name) 148 149 def get_resolved_global_or_builtin(self, name): 150 151 "Return the resolved global or built-in object with the given 'name'." 152 153 return self.get_global(name) or self.importer.get_object("__builtins__.%s" % name) 154 155 def set_invocation_usage(self): 156 157 """ 158 Discard the current invocation storage figures, retaining the maximum 159 values. 160 """ 161 162 for path, (current, maximum) in self.function_targets.items(): 163 self.importer.function_targets[path] = self.function_targets[path] = maximum 164 165 for path, (current, maximum) in self.function_arguments.items(): 166 self.importer.function_arguments[path] = self.function_arguments[path] = maximum 167 168 # Module structure traversal. 169 170 def process_structure_node(self, n): 171 172 "Process the individual node 'n'." 173 174 # Module global detection. 175 176 if isinstance(n, compiler.ast.Global): 177 self.process_global_node(n) 178 179 # Module import declarations. 180 181 elif isinstance(n, compiler.ast.From): 182 self.process_from_node(n) 183 184 elif isinstance(n, compiler.ast.Import): 185 self.process_import_node(n) 186 187 # Nodes using operator module functions. 188 189 elif isinstance(n, compiler.ast.Operator): 190 return self.process_operator_node(n) 191 192 elif isinstance(n, compiler.ast.AugAssign): 193 self.process_augassign_node(n) 194 195 elif isinstance(n, compiler.ast.Compare): 196 return self.process_compare_node(n) 197 198 elif isinstance(n, compiler.ast.Slice): 199 return self.process_slice_node(n) 200 201 elif isinstance(n, compiler.ast.Sliceobj): 202 return self.process_sliceobj_node(n) 203 204 elif isinstance(n, compiler.ast.Subscript): 205 return self.process_subscript_node(n) 206 207 # Namespaces within modules. 208 209 elif isinstance(n, compiler.ast.Class): 210 self.process_class_node(n) 211 212 elif isinstance(n, compiler.ast.Function): 213 self.process_function_node(n, n.name) 214 215 elif isinstance(n, compiler.ast.Lambda): 216 return self.process_lambda_node(n) 217 218 # Assignments. 219 220 elif isinstance(n, compiler.ast.Assign): 221 222 # Handle each assignment node. 223 224 for node in n.nodes: 225 self.process_assignment_node(node, n.expr) 226 227 # Assignments within non-Assign nodes. 228 229 elif isinstance(n, compiler.ast.AssName): 230 self.process_assignment_node(n, None) 231 232 elif isinstance(n, compiler.ast.AssAttr): 233 self.process_attribute_access(n) 234 235 # Accesses. 236 237 elif isinstance(n, compiler.ast.Getattr): 238 return self.process_attribute_access(n) 239 240 # Name recording for later testing. 241 242 elif isinstance(n, compiler.ast.Name): 243 return self.process_name_node(n) 244 245 # Conditional statement tracking. 246 247 elif isinstance(n, compiler.ast.For): 248 self.process_for_node(n) 249 250 elif isinstance(n, compiler.ast.While): 251 self.process_while_node(n) 252 253 elif isinstance(n, compiler.ast.If): 254 self.process_if_node(n) 255 256 elif isinstance(n, (compiler.ast.And, compiler.ast.Or)): 257 return self.process_logical_node(n) 258 259 # Exception control-flow tracking. 260 261 elif isinstance(n, compiler.ast.TryExcept): 262 self.process_try_node(n) 263 264 elif isinstance(n, compiler.ast.TryFinally): 265 self.process_try_finally_node(n) 266 267 # Control-flow modification statements. 268 269 elif isinstance(n, compiler.ast.Break): 270 self.trackers[-1].suspend_broken_branch() 271 272 elif isinstance(n, compiler.ast.Continue): 273 self.trackers[-1].suspend_continuing_branch() 274 275 elif isinstance(n, compiler.ast.Raise): 276 self.process_structure(n) 277 self.trackers[-1].abandon_branch() 278 279 elif isinstance(n, compiler.ast.Return): 280 self.process_structure(n) 281 self.trackers[-1].abandon_returning_branch() 282 283 # Invocations. 284 285 elif isinstance(n, compiler.ast.CallFunc): 286 return self.process_invocation_node(n) 287 288 # Constant usage. 289 290 elif isinstance(n, compiler.ast.Const): 291 return self.get_literal_instance(n, n.value.__class__.__name__) 292 293 elif isinstance(n, compiler.ast.Dict): 294 return self.get_literal_instance(n, "dict") 295 296 elif isinstance(n, compiler.ast.List): 297 return self.get_literal_instance(n, "list") 298 299 elif isinstance(n, compiler.ast.Tuple): 300 return self.get_literal_instance(n, "tuple") 301 302 # List comprehensions and if expressions. 303 304 elif isinstance(n, compiler.ast.ListComp): 305 self.process_listcomp_node(n) 306 307 elif isinstance(n, compiler.ast.IfExp): 308 self.process_ifexp_node(n) 309 310 # All other nodes are processed depth-first. 311 312 else: 313 self.process_structure(n) 314 315 # By default, no expression details are returned. 316 317 return None 318 319 # Specific node handling. 320 321 def process_assignment_node(self, n, expr): 322 323 "Process the individual node 'n' to be assigned the contents of 'expr'." 324 325 # Names and attributes are assigned the entire expression. 326 327 if isinstance(n, compiler.ast.AssName): 328 329 name_ref = expr and self.process_structure_node(expr) 330 331 # Name assignments populate either function namespaces or the 332 # general namespace hierarchy. 333 334 self.assign_general_local(n.name, name_ref) 335 336 # Record usage of the name. 337 338 self.record_name(n.name) 339 340 elif isinstance(n, compiler.ast.AssAttr): 341 if expr: self.process_structure_node(expr) 342 self.process_attribute_access(n) 343 344 # Lists and tuples are matched against the expression and their 345 # items assigned to expression items. 346 347 elif isinstance(n, (compiler.ast.AssList, compiler.ast.AssTuple)): 348 self.process_assignment_node_items(n, expr) 349 350 # Slices and subscripts are permitted within assignment nodes. 351 352 elif isinstance(n, compiler.ast.Slice): 353 self.process_slice_node(n, expr) 354 355 elif isinstance(n, compiler.ast.Subscript): 356 self.process_subscript_node(n, expr) 357 358 def process_attribute_access(self, n): 359 360 "Process the given attribute access node 'n'." 361 362 # Obtain any completed chain and return the reference to it. 363 364 name_ref = self.process_attribute_chain(n) 365 if self.have_access_expression(n): 366 return name_ref 367 368 # Where the start of the chain of attributes has been reached, determine 369 # the complete access. 370 371 # Given a non-access node, this chain can be handled in its entirety, 372 # either being name-based and thus an access rooted on a name, or being 373 # based on some other node and thus an anonymous access of some kind. 374 375 path = self.get_namespace_path() 376 377 # Start with the the full attribute chain. 378 379 remaining = self.attrs 380 attrnames = ".".join(remaining) 381 382 # If the accessor cannot be identified, or where attributes 383 # remain in an attribute chain, record the anonymous accesses. 384 385 if not isinstance(name_ref, NameRef): # includes ResolvedNameRef 386 387 assignment = isinstance(n, compiler.ast.AssAttr) 388 389 init_item(self.attr_accesses, path, set) 390 self.attr_accesses[path].add(attrnames) 391 392 self.record_access_details(None, attrnames, assignment) 393 del self.attrs[0] 394 return 395 396 # Name-based accesses will handle the first attribute in a 397 # chain. 398 399 else: 400 attrname = remaining[0] 401 402 # Attribute assignments are used to identify instance attributes. 403 404 if isinstance(n, compiler.ast.AssAttr) and \ 405 self.in_class and self.in_function and n.expr.name == "self": 406 407 self.set_instance_attr(attrname) 408 409 # Record attribute usage using any name local to this namespace, 410 # if assigned in the namespace, or using an external name 411 # (presently just globals within classes). 412 413 name = self.get_name_for_tracking(name_ref.name, name_ref.final()) 414 tracker = self.trackers[-1] 415 416 immediate_access = len(self.attrs) == 1 417 assignment = immediate_access and isinstance(n, compiler.ast.AssAttr) 418 419 del self.attrs[0] 420 421 # Record global-based chains for subsequent resolution. 422 423 is_global = self.in_function and not self.function_locals[path].has_key(name) or \ 424 not self.in_function 425 426 if is_global: 427 self.record_global_access_details(name, attrnames) 428 429 # Make sure the name is being tracked: global names will not 430 # already be initialised in a branch and must be added 431 # explicitly. 432 433 if not tracker.have_name(name): 434 tracker.assign_names([name]) 435 if self.in_function: 436 self.scope_globals[path].add(name) 437 438 # Record attribute usage in the tracker, and record the branch 439 # information for the access. 440 441 branches = tracker.use_attribute(name, attrname) 442 443 if not branches: 444 print >>sys.stderr, "In %s, name %s is accessed using %s before an assignment." % ( 445 path, name, attrname) 446 branches = tracker.use_attribute(name, attrname) 447 448 self.record_branches_for_access(branches, name, attrnames) 449 access_number = self.record_access_details(name, attrnames, assignment) 450 return AccessRef(name, attrnames, access_number) 451 452 def process_class_node(self, n): 453 454 "Process the given class node 'n'." 455 456 path = self.get_namespace_path() 457 458 # To avoid notions of class "versions" where the same definition 459 # might be parameterised with different state and be referenced 460 # elsewhere (as base classes, for example), classes in functions or 461 # conditions are forbidden. 462 463 if self.in_function or self.in_conditional: 464 print >>sys.stderr, "In %s, class %s in function or conditional statement ignored." % ( 465 path, n.name) 466 return 467 468 # Resolve base classes. 469 470 bases = [] 471 472 for base in n.bases: 473 base_class = self.get_class(base) 474 475 if not base_class: 476 print >>sys.stderr, "In %s, class %s has unidentifiable base class: %s" % ( 477 path, n.name, base) 478 return 479 else: 480 bases.append(base_class) 481 482 # Record bases for the class and retain the class name. 483 484 class_name = self.get_object_path(n.name) 485 486 if not bases and class_name != "__builtins__.core.object": 487 ref = self.get_object("__builtins__.object") 488 bases.append(ref) 489 490 self.importer.classes[class_name] = self.classes[class_name] = bases 491 self.importer.subclasses[class_name] = set() 492 self.scope_globals[class_name] = set() 493 494 # Set the definition before entering the namespace rather than 495 # afterwards because methods may reference it. In normal Python, 496 # a class is not accessible until the definition is complete, but 497 # methods can generally reference it since upon being called the 498 # class will already exist. 499 500 self.set_definition(n.name, "<class>") 501 502 in_class = self.in_class 503 self.in_class = class_name 504 self.set_instance_attr("__class__", Reference("<class>", class_name)) 505 self.enter_namespace(n.name) 506 self.set_name("__fn__") # special instantiator attribute 507 self.set_name("__args__") # special instantiator attribute 508 self.assign_general_local("__name__", self.get_constant("str", class_name)) 509 self.process_structure_node(n.code) 510 self.exit_namespace() 511 self.in_class = in_class 512 513 def process_from_node(self, n): 514 515 "Process the given node 'n', importing from another module." 516 517 path = self.get_namespace_path() 518 519 module_name, names = self.get_module_name(n) 520 if module_name == self.name: 521 raise InspectError("Cannot import from the current module.", path, n) 522 523 self.queue_module(module_name) 524 525 # Attempt to obtain the referenced objects. 526 527 for name, alias in n.names: 528 if name == "*": 529 raise InspectError("Only explicitly specified names can be imported from modules.", path, n) 530 531 # Explicit names. 532 533 ref = self.import_name_from_module(name, module_name) 534 value = ResolvedNameRef(alias or name, ref) 535 self.set_general_local(alias or name, value) 536 537 def process_function_node(self, n, name): 538 539 """ 540 Process the given function or lambda node 'n' with the given 'name'. 541 """ 542 543 is_lambda = isinstance(n, compiler.ast.Lambda) 544 545 # Where a function is declared conditionally, use a separate name for 546 # the definition, and assign the definition to the stated name. 547 548 if (self.in_conditional or self.in_function) and not is_lambda: 549 original_name = name 550 name = self.get_lambda_name() 551 else: 552 original_name = None 553 554 # Initialise argument and local records. 555 556 function_name = self.get_object_path(name) 557 558 argnames = self.importer.function_parameters[function_name] = \ 559 self.function_parameters[function_name] = get_argnames(n.argnames) 560 locals = self.function_locals[function_name] = {} 561 562 for argname in argnames: 563 locals[argname] = Reference("<var>") 564 565 globals = self.scope_globals[function_name] = set() 566 567 # Process the defaults. 568 569 defaults = self.importer.function_defaults[function_name] = \ 570 self.function_defaults[function_name] = [] 571 572 for argname, default in compiler.ast.get_defaults(n): 573 if default: 574 575 # Obtain any reference for the default. 576 577 name_ref = self.process_structure_node(default) 578 defaults.append((argname, name_ref.is_name() and name_ref.reference() or Reference("<var>"))) 579 580 # Reset conditional tracking to focus on the function contents. 581 582 parent_function = self.parent_function 583 self.parent_function = self.in_function and self.get_namespace_path() or None 584 585 in_conditional = self.in_conditional 586 self.in_conditional = False 587 588 in_function = self.in_function 589 self.in_function = function_name 590 591 self.enter_namespace(name) 592 593 # Track attribute usage within the namespace. 594 595 path = self.get_namespace_path() 596 init_item(self.propagated_names, path, set) 597 598 self.start_tracking(locals) 599 self.process_structure_node(n.code) 600 self.stop_tracking() 601 602 # Propagate names from parent scopes. 603 604 for local in self.propagated_names[path]: 605 if not local in argnames and self.trackers[-1].have_name(local): 606 argnames.append(local) 607 defaults.append((local, Reference("<var>"))) 608 self.set_function_local(local) 609 610 # Exit to the parent and note propagated names. 611 612 self.exit_namespace() 613 614 parent = self.get_namespace_path() 615 if self.propagated_names.has_key(parent): 616 for local in self.propagated_names[path]: 617 self.propagated_names[parent].add(local) 618 619 # Update flags. 620 621 self.in_function = in_function 622 self.in_conditional = in_conditional 623 self.parent_function = parent_function 624 625 # Define the function using the appropriate name. 626 627 self.set_definition(name, "<function>") 628 629 # Where a function is set conditionally, assign the name. 630 631 if original_name: 632 self.process_assignment_for_function(original_name, name) 633 634 def process_global_node(self, n): 635 636 """ 637 Process the given "global" node 'n'. 638 """ 639 640 path = self.get_namespace_path() 641 642 if path != self.name: 643 self.scope_globals[path].update(n.names) 644 645 def process_if_node(self, n): 646 647 """ 648 Process the given "if" node 'n'. 649 """ 650 651 tracker = self.trackers[-1] 652 tracker.new_branchpoint() 653 654 for test, body in n.tests: 655 self.process_structure_node(test) 656 657 tracker.new_branch() 658 659 in_conditional = self.in_conditional 660 self.in_conditional = True 661 self.process_structure_node(body) 662 self.in_conditional = in_conditional 663 664 tracker.shelve_branch() 665 666 # Maintain a branch for the else clause. 667 668 tracker.new_branch() 669 if n.else_: 670 self.process_structure_node(n.else_) 671 tracker.shelve_branch() 672 673 tracker.merge_branches() 674 675 def process_ifexp_node(self, n): 676 677 "Process the given if expression node 'n'." 678 679 name_ref = self.process_structure_node(self.convert_ifexp_node(n)) 680 681 path = self.get_namespace_path() 682 self.allocate_arguments(path, self.function_defaults[name_ref.get_origin()]) 683 self.deallocate_arguments(path, self.function_defaults[name_ref.get_origin()]) 684 685 return InvocationRef(name_ref) 686 687 def process_import_node(self, n): 688 689 "Process the given import node 'n'." 690 691 path = self.get_namespace_path() 692 693 # Load the mentioned module. 694 695 for name, alias in n.names: 696 if name == self.name: 697 raise InspectError("Cannot import the current module.", path, n) 698 if not alias and len(n.names) > 1: 699 raise InspectError("Imported modules must be aliased unless a simple module is imported.", path, n) 700 701 self.set_module(alias or name.split(".")[-1], name) 702 self.queue_module(name, True) 703 704 def process_invocation_node(self, n): 705 706 "Process the given invocation node 'n'." 707 708 path = self.get_namespace_path() 709 710 self.allocate_arguments(path, n.args) 711 712 try: 713 # Process the expression, obtaining any identified reference. 714 715 name_ref = self.process_structure_node(n.node) 716 717 # Process the arguments. 718 719 for arg in n.args: 720 self.process_structure_node(arg) 721 722 # Detect class invocations. 723 724 if isinstance(name_ref, ResolvedNameRef) and name_ref.has_kind("<class>"): 725 return InstanceRef(name_ref.reference().instance_of()) 726 727 elif isinstance(name_ref, NameRef): 728 return InvocationRef(name_ref) 729 730 return None 731 732 finally: 733 self.deallocate_arguments(path, n.args) 734 735 def process_lambda_node(self, n): 736 737 "Process the given lambda node 'n'." 738 739 name = self.get_lambda_name() 740 self.process_function_node(n, name) 741 742 origin = self.get_object_path(name) 743 return ResolvedNameRef(name, Reference("<function>", origin)) 744 745 def process_listcomp_node(self, n): 746 747 "Process the given list comprehension node 'n'." 748 749 name_ref = self.process_structure_node(self.convert_listcomp_node(n)) 750 751 path = self.get_namespace_path() 752 self.allocate_arguments(path, self.function_defaults[name_ref.get_origin()]) 753 self.deallocate_arguments(path, self.function_defaults[name_ref.get_origin()]) 754 755 return InvocationRef(name_ref) 756 757 def process_logical_node(self, n): 758 759 "Process the given operator node 'n'." 760 761 self.process_operator_chain(n.nodes, self.process_structure_node) 762 763 def process_name_node(self, n): 764 765 "Process the given name node 'n'." 766 767 path = self.get_namespace_path() 768 769 # Special names. 770 771 if n.name.startswith("$"): 772 value = self.get_special(n.name) 773 if value: 774 return value 775 776 # Special case for operator functions introduced through code 777 # transformations. 778 779 if n.name.startswith("$op"): 780 781 # Obtain the location of the actual function defined in the operator 782 # package. 783 784 op = n.name[len("$op"):] 785 786 # Attempt to get a reference. 787 788 ref = self.import_name_from_module(op, "operator") 789 790 # Record the imported name and provide the resolved name reference. 791 792 value = ResolvedNameRef(n.name, ref) 793 self.set_special(n.name, value) 794 return value 795 796 # Record usage of the name. 797 798 self.record_name(n.name) 799 800 # Search for unknown names in non-function scopes immediately. 801 # External names in functions are resolved later. 802 803 ref = self.find_name(n.name) 804 if ref: 805 return ResolvedNameRef(n.name, ref) 806 807 # Global name. 808 809 elif self.in_function and n.name in self.scope_globals[path]: 810 return NameRef(n.name) 811 812 # Examine other names. 813 814 else: 815 tracker = self.trackers[-1] 816 817 # Check local names. 818 819 branches = tracker.tracking_name(n.name) 820 821 # Find names inherited from a parent scope. 822 823 if not branches and self.parent_function: 824 branches = tracker.have_name(n.name) 825 if branches: 826 self.propagate_name(n.name) 827 828 # Local or inherited name. 829 830 if branches: 831 self.record_branches_for_access(branches, n.name, None) 832 access_number = self.record_access_details(n.name, None, False) 833 return LocalNameRef(n.name, access_number) 834 835 # Possible global name. 836 837 else: 838 return NameRef(n.name) 839 840 def process_operator_chain(self, nodes, fn): 841 842 """ 843 Process the given chain of 'nodes', applying 'fn' to each node or item. 844 Each node starts a new conditional region, effectively making a deeply- 845 nested collection of if-like statements. 846 """ 847 848 tracker = self.trackers[-1] 849 850 for item in nodes: 851 tracker.new_branchpoint() 852 tracker.new_branch() 853 fn(item) 854 855 for item in nodes[:-1]: 856 tracker.shelve_branch() 857 tracker.new_branch() 858 tracker.shelve_branch() 859 tracker.merge_branches() 860 861 tracker.shelve_branch() 862 tracker.merge_branches() 863 864 def process_try_node(self, n): 865 866 """ 867 Process the given "try...except" node 'n'. 868 """ 869 870 tracker = self.trackers[-1] 871 tracker.new_branchpoint() 872 873 self.process_structure_node(n.body) 874 875 for name, var, handler in n.handlers: 876 if name is not None: 877 self.process_structure_node(name) 878 879 # Any abandoned branches from the body can now be resumed in a new 880 # branch. 881 882 tracker.resume_abandoned_branches() 883 884 # Establish the local for the handler. 885 886 if var is not None: 887 self.process_structure_node(var) 888 if handler is not None: 889 self.process_structure_node(handler) 890 891 tracker.shelve_branch() 892 893 # The else clause maintains the usage from the body but without the 894 # abandoned branches since they would never lead to the else clause 895 # being executed. 896 897 if n.else_: 898 tracker.new_branch() 899 self.process_structure_node(n.else_) 900 tracker.shelve_branch() 901 902 # Without an else clause, a null branch propagates the successful 903 # outcome. 904 905 else: 906 tracker.new_branch() 907 tracker.shelve_branch() 908 909 tracker.merge_branches() 910 911 def process_try_finally_node(self, n): 912 913 """ 914 Process the given "try...finally" node 'n'. 915 """ 916 917 tracker = self.trackers[-1] 918 self.process_structure_node(n.body) 919 920 # Any abandoned branches from the body can now be resumed. 921 922 branches = tracker.resume_all_abandoned_branches() 923 self.process_structure_node(n.final) 924 925 # At the end of the finally clause, abandoned branches are discarded. 926 927 tracker.restore_active_branches(branches) 928 929 def process_while_node(self, n): 930 931 "Process the given while node 'n'." 932 933 tracker = self.trackers[-1] 934 tracker.new_branchpoint(loop_node=True) 935 936 # Evaluate any test or iterator outside the loop. 937 938 self.process_structure_node(n.test) 939 940 # Propagate attribute usage to branches. 941 942 tracker.new_branch(loop_node=True) 943 944 # Enter the loop. 945 946 in_conditional = self.in_conditional 947 self.in_conditional = True 948 self.process_structure_node(n.body) 949 self.in_conditional = in_conditional 950 951 # Continuing branches are resumed before any test. 952 953 tracker.resume_continuing_branches() 954 955 # Evaluate any continuation test within the body. 956 957 self.process_structure_node(n.test) 958 959 tracker.shelve_branch(loop_node=True) 960 961 # Support the non-looping condition. 962 963 tracker.new_branch() 964 tracker.shelve_branch() 965 966 tracker.merge_branches() 967 968 # Evaluate any else clause outside branches. 969 970 if n.else_: 971 self.process_structure_node(n.else_) 972 973 # Connect broken branches to the code after any loop. 974 975 tracker.resume_broken_branches() 976 977 # Branch tracking methods. 978 979 def start_tracking(self, names): 980 981 """ 982 Start tracking attribute usage for names in the current namespace, 983 immediately registering the given 'names'. 984 """ 985 986 path = self.get_namespace_path() 987 parent = self.trackers[-1] 988 tracker = BranchTracker() 989 self.trackers.append(tracker) 990 991 # For functions created from expressions or for functions within 992 # functions, propagate usage to the new namespace. 993 994 if self.parent_function: 995 tracker.inherit_branches(parent, names) 996 997 # Record the given names established as new branches. 998 999 tracker.assign_names(names) 1000 1001 def assign_name(self, name, name_ref): 1002 1003 "Assign to 'name' the given 'name_ref' in the current namespace." 1004 1005 name = self.get_name_for_tracking(name) 1006 self.trackers[-1].assign_names([name], [name_ref]) 1007 1008 def stop_tracking(self): 1009 1010 """ 1011 Stop tracking attribute usage, recording computed usage for the current 1012 namespace. 1013 """ 1014 1015 path = self.get_namespace_path() 1016 tracker = self.trackers.pop() 1017 self.record_assignments_for_access(tracker) 1018 1019 self.attr_usage[path] = tracker.get_all_usage() 1020 self.name_initialisers[path] = tracker.get_all_values() 1021 1022 def start_tracking_in_module(self): 1023 1024 "Start tracking attribute usage in the module." 1025 1026 tracker = BranchTracker() 1027 self.trackers.append(tracker) 1028 1029 def stop_tracking_in_module(self): 1030 1031 "Stop tracking attribute usage in the module." 1032 1033 tracker = self.trackers[0] 1034 self.record_assignments_for_access(tracker) 1035 self.attr_usage[self.name] = tracker.get_all_usage() 1036 self.name_initialisers[self.name] = tracker.get_all_values() 1037 1038 def propagate_name(self, name): 1039 1040 "Propagate the given 'name' into the current namespace." 1041 1042 path = self.get_namespace_path() 1043 self.propagated_names[path].add(name) 1044 1045 def record_assignments_for_access(self, tracker): 1046 1047 """ 1048 For the current path, use the given 'tracker' to record assignment 1049 version information for attribute accesses. 1050 """ 1051 1052 path = self.get_path_for_access() 1053 1054 if not self.attr_accessor_branches.has_key(path): 1055 return 1056 1057 init_item(self.attr_accessors, path, dict) 1058 attr_accessors = self.attr_accessors[path] 1059 1060 # Obtain the branches applying during each access. 1061 1062 for access, all_branches in self.attr_accessor_branches[path].items(): 1063 name, attrnames = access 1064 init_item(attr_accessors, access, list) 1065 1066 # Obtain the assignments applying to each branch. 1067 1068 for branches in all_branches: 1069 positions = tracker.get_assignment_positions_for_branches(name, branches) 1070 1071 # Detect missing name information. 1072 1073 if None in positions: 1074 globals = self.global_attr_accesses.get(path) 1075 accesses = globals and globals.get(name) 1076 if not accesses: 1077 print >>sys.stderr, "In %s, %s may not be defined when used." % ( 1078 self.get_namespace_path(), name) 1079 positions.remove(None) 1080 1081 attr_accessors[access].append(positions) 1082 1083 def record_branches_for_access(self, branches, name, attrnames): 1084 1085 """ 1086 Record the given 'branches' for an access involving the given 'name' and 1087 'attrnames'. 1088 """ 1089 1090 access = name, attrnames 1091 path = self.get_path_for_access() 1092 1093 init_item(self.attr_accessor_branches, path, dict) 1094 attr_accessor_branches = self.attr_accessor_branches[path] 1095 1096 init_item(attr_accessor_branches, access, list) 1097 attr_accessor_branches[access].append(branches) 1098 1099 def record_access_details(self, name, attrnames, assignment): 1100 1101 """ 1102 For the given 'name' and 'attrnames', record an access indicating 1103 whether 'assignment' is occurring. 1104 1105 These details correspond to accesses otherwise recorded by the attribute 1106 accessor and attribute access dictionaries. 1107 """ 1108 1109 access = name, attrnames 1110 path = self.get_path_for_access() 1111 1112 init_item(self.attr_access_modifiers, path, dict) 1113 init_item(self.attr_access_modifiers[path], access, list) 1114 1115 access_number = len(self.attr_access_modifiers[path][access]) 1116 self.attr_access_modifiers[path][access].append(assignment) 1117 return access_number 1118 1119 def record_global_access_details(self, name, attrnames): 1120 1121 """ 1122 Record details of a global access via the given 'name' involving the 1123 indicated 'attrnames'. 1124 """ 1125 1126 path = self.get_namespace_path() 1127 1128 init_item(self.global_attr_accesses, path, dict) 1129 init_item(self.global_attr_accesses[path], name, set) 1130 self.global_attr_accesses[path][name].add(attrnames) 1131 1132 # Namespace modification. 1133 1134 def record_name(self, name): 1135 1136 "Record the use of 'name' in a namespace." 1137 1138 path = self.get_namespace_path() 1139 init_item(self.names_used, path, set) 1140 self.names_used[path].add(name) 1141 1142 def set_module(self, name, module_name): 1143 1144 """ 1145 Set a module in the current namespace using the given 'name' associated 1146 with the corresponding 'module_name'. 1147 """ 1148 1149 if name: 1150 self.set_general_local(name, Reference("<module>", module_name)) 1151 1152 def set_definition(self, name, kind): 1153 1154 """ 1155 Set the definition having the given 'name' and 'kind'. 1156 1157 Definitions are set in the static namespace hierarchy, but they can also 1158 be recorded for function locals. 1159 """ 1160 1161 if self.is_global(name): 1162 print >>sys.stderr, "In %s, %s is defined as being global." % ( 1163 self.get_namespace_path(), name) 1164 1165 path = self.get_object_path(name) 1166 self.set_object(path, kind) 1167 1168 ref = self.get_object(path) 1169 if ref.get_kind() == "<var>": 1170 print >>sys.stderr, "In %s, %s is defined more than once." % ( 1171 self.get_namespace_path(), name) 1172 1173 if not self.is_global(name) and self.in_function: 1174 self.set_function_local(name, ref) 1175 1176 def set_function_local(self, name, ref=None): 1177 1178 "Set the local with the given 'name' and optional 'ref'." 1179 1180 locals = self.function_locals[self.get_namespace_path()] 1181 multiple = not ref or locals.has_key(name) and locals[name] != ref 1182 locals[name] = multiple and Reference("<var>") or ref 1183 1184 def assign_general_local(self, name, name_ref): 1185 1186 """ 1187 Set for 'name' the given 'name_ref', recording the name for attribute 1188 usage tracking. 1189 """ 1190 1191 self.set_general_local(name, name_ref) 1192 self.assign_name(name, name_ref) 1193 1194 def set_general_local(self, name, value=None): 1195 1196 """ 1197 Set the 'name' with optional 'value' in any kind of local namespace, 1198 where the 'value' should be a reference if specified. 1199 """ 1200 1201 init_value = self.get_initialising_value(value) 1202 1203 # Module global names. 1204 1205 if self.is_global(name): 1206 path = self.get_global_path(name) 1207 self.set_object(path, init_value) 1208 1209 # Function local names. 1210 1211 elif self.in_function: 1212 path = self.get_object_path(name) 1213 self.set_function_local(name, init_value) 1214 1215 # Other namespaces (classes). 1216 1217 else: 1218 path = self.get_object_path(name) 1219 self.set_name(name, init_value) 1220 1221 def set_name(self, name, ref=None): 1222 1223 "Attach the 'name' with optional 'ref' to the current namespace." 1224 1225 self.set_object(self.get_object_path(name), ref) 1226 1227 def set_instance_attr(self, name, ref=None): 1228 1229 """ 1230 Add an instance attribute of the given 'name' to the current class, 1231 using the optional 'ref'. 1232 """ 1233 1234 init_item(self.instance_attrs, self.in_class, set) 1235 self.instance_attrs[self.in_class].add(name) 1236 1237 if ref: 1238 init_item(self.instance_attr_constants, self.in_class, dict) 1239 self.instance_attr_constants[self.in_class][name] = ref 1240 1241 def get_initialising_value(self, value): 1242 1243 "Return a suitable initialiser reference for 'value'." 1244 1245 # Includes LiteralSequenceRef, ResolvedNameRef... 1246 1247 if isinstance(value, (NameRef, AccessRef, InstanceRef)): 1248 return value.reference() 1249 1250 # In general, invocations do not produce known results. However, the 1251 # name initialisers are resolved once a module has been inspected. 1252 1253 elif isinstance(value, InvocationRef): 1254 return value.reference() 1255 1256 else: 1257 return value 1258 1259 # Static, program-relative naming. 1260 1261 def find_name(self, name): 1262 1263 """ 1264 Return the qualified name for the given 'name' used in the current 1265 non-function namespace. 1266 """ 1267 1268 path = self.get_namespace_path() 1269 ref = None 1270 1271 if not self.in_function and name not in predefined_constants: 1272 if self.in_class: 1273 ref = self.get_object(self.get_object_path(name)) 1274 if not ref: 1275 ref = self.get_global_or_builtin(name) 1276 1277 return ref 1278 1279 def get_class(self, node): 1280 1281 """ 1282 Use the given 'node' to obtain the identity of a class. Return a 1283 reference for the class. Unresolved dependencies are permitted and must 1284 be resolved later. 1285 """ 1286 1287 ref = self._get_class(node) 1288 return ref.has_kind(["<class>", "<depends>"]) and ref or None 1289 1290 def _get_class(self, node): 1291 1292 """ 1293 Use the given 'node' to find a class definition. Return a reference to 1294 the class. 1295 """ 1296 1297 if isinstance(node, compiler.ast.Getattr): 1298 1299 # Obtain the identity of the access target. 1300 1301 ref = self._get_class(node.expr) 1302 1303 # Where the target is a class or module, obtain the identity of the 1304 # attribute. 1305 1306 if ref.has_kind(["<function>", "<var>"]): 1307 return None 1308 else: 1309 attrname = "%s.%s" % (ref.get_origin(), node.attrname) 1310 return self.get_object(attrname) 1311 1312 # Names can be module-level or built-in. 1313 1314 elif isinstance(node, compiler.ast.Name): 1315 1316 # Record usage of the name and attempt to identify it. 1317 1318 self.record_name(node.name) 1319 return self.get_global_or_builtin(node.name) 1320 else: 1321 return None 1322 1323 def get_constant(self, name, value): 1324 1325 "Return a constant reference for the given type 'name' and 'value'." 1326 1327 ref = self.get_builtin_class(name) 1328 return self.get_constant_reference(ref, value) 1329 1330 def get_literal_instance(self, n, name): 1331 1332 "For node 'n', return a reference to an instance of 'name'." 1333 1334 # Get a reference to the built-in class. 1335 1336 ref = self.get_builtin_class(name) 1337 1338 # Obtain the details of the literal itself. 1339 # An alias to the type is generated for sequences. 1340 1341 if name in ("dict", "list", "tuple"): 1342 self.set_special_literal(name, ref) 1343 return self.process_literal_sequence_node(n, name, ref, LiteralSequenceRef) 1344 1345 # Constant values are independently recorded. 1346 1347 else: 1348 return self.get_constant_reference(ref, n.value) 1349 1350 # Special names. 1351 1352 def get_special(self, name): 1353 1354 "Return any stored value for the given special 'name'." 1355 1356 return self.special.get(name) 1357 1358 def set_special(self, name, value): 1359 1360 """ 1361 Set a special 'name' that merely tracks the use of an implicit object 1362 'value'. 1363 """ 1364 1365 self.special[name] = value 1366 1367 def set_special_literal(self, name, ref): 1368 1369 """ 1370 Set a special name for the literal type 'name' having type 'ref'. Such 1371 special names provide a way of referring to literal object types. 1372 """ 1373 1374 literal_name = "$L%s" % name 1375 value = ResolvedNameRef(literal_name, ref) 1376 self.set_special(literal_name, value) 1377 1378 # Functions and invocations. 1379 1380 def allocate_arguments(self, path, args): 1381 1382 """ 1383 Allocate temporary argument storage using current and maximum 1384 requirements for the given 'path' and 'args'. 1385 """ 1386 1387 init_item(self.function_targets, path, lambda: [0, 0]) 1388 t = self.function_targets[path] 1389 t[0] += 1 1390 t[1] = max(t[0], t[1]) 1391 1392 init_item(self.function_arguments, path, lambda: [0, 0]) 1393 t = self.function_arguments[path] 1394 t[0] += len(args) + 1 1395 t[1] = max(t[0], t[1]) 1396 1397 def deallocate_arguments(self, path, args): 1398 1399 "Deallocate temporary argument storage for the given 'path' and 'args'." 1400 1401 self.function_targets[path][0] -= 1 1402 self.function_arguments[path][0] -= len(args) + 1 1403 1404 # vim: tabstop=4 expandtab shiftwidth=4