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