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