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