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