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