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