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