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