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