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