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, 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 self.record_exception_handler() 924 925 tracker = self.trackers[-1] 926 tracker.new_branchpoint() 927 928 self.process_structure_node(n.body) 929 930 for name, var, handler in n.handlers: 931 if name is not None: 932 self.process_structure_node(name) 933 934 # Any abandoned branches from the body can now be resumed in a new 935 # branch. 936 937 tracker.resume_abandoned_branches() 938 939 # Establish the local for the handler. 940 941 if var is not None: 942 self.process_assignment_node(var, None) 943 if handler is not None: 944 self.process_structure_node(handler) 945 946 tracker.shelve_branch() 947 948 # The else clause maintains the usage from the body but without the 949 # abandoned branches since they would never lead to the else clause 950 # being executed. 951 952 if n.else_: 953 tracker.new_branch() 954 self.process_structure_node(n.else_) 955 tracker.shelve_branch() 956 957 # Without an else clause, a null branch propagates the successful 958 # outcome. 959 960 else: 961 tracker.new_branch() 962 tracker.shelve_branch() 963 964 tracker.merge_branches() 965 966 def process_try_finally_node(self, n): 967 968 """ 969 Process the given "try...finally" node 'n'. 970 """ 971 972 self.record_exception_handler() 973 974 tracker = self.trackers[-1] 975 self.process_structure_node(n.body) 976 977 # Any abandoned branches from the body can now be resumed. 978 979 branches = tracker.resume_all_abandoned_branches() 980 self.process_structure_node(n.final) 981 982 # At the end of the finally clause, abandoned branches are discarded. 983 984 tracker.restore_active_branches(branches) 985 986 def process_while_node(self, n): 987 988 "Process the given while node 'n'." 989 990 tracker = self.trackers[-1] 991 tracker.new_branchpoint(loop_node=True) 992 993 # Evaluate any test or iterator outside the loop. 994 995 self.process_structure_node(n.test) 996 997 # Propagate attribute usage to branches. 998 999 tracker.new_branch(loop_node=True) 1000 1001 # Enter the loop. 1002 1003 in_conditional = self.in_conditional 1004 self.in_conditional = True 1005 self.process_structure_node(n.body) 1006 self.in_conditional = in_conditional 1007 1008 # Continuing branches are resumed before any test. 1009 1010 tracker.resume_continuing_branches() 1011 1012 # Evaluate any continuation test within the body. 1013 1014 self.process_structure_node(n.test) 1015 1016 tracker.shelve_branch(loop_node=True) 1017 1018 # Support the non-looping condition. 1019 1020 tracker.new_branch() 1021 tracker.shelve_branch() 1022 1023 tracker.merge_branches() 1024 1025 # Evaluate any else clause outside branches. 1026 1027 if n.else_: 1028 self.process_structure_node(n.else_) 1029 1030 # Connect broken branches to the code after any loop. 1031 1032 tracker.resume_broken_branches() 1033 1034 # Branch tracking methods. 1035 1036 def start_tracking(self, names): 1037 1038 """ 1039 Start tracking attribute usage for names in the current namespace, 1040 immediately registering the given 'names'. 1041 """ 1042 1043 path = self.get_namespace_path() 1044 parent = self.trackers[-1] 1045 tracker = BranchTracker() 1046 self.trackers.append(tracker) 1047 1048 # Record the given names established as new branches. 1049 1050 tracker.assign_names(names) 1051 1052 def assign_name(self, name, name_ref): 1053 1054 "Assign to 'name' the given 'name_ref' in the current namespace." 1055 1056 name = self.get_name_for_tracking(name) 1057 self.trackers[-1].assign_names([name], [name_ref]) 1058 1059 def stop_tracking(self): 1060 1061 """ 1062 Stop tracking attribute usage, recording computed usage for the current 1063 namespace. 1064 """ 1065 1066 path = self.get_namespace_path() 1067 tracker = self.trackers.pop() 1068 self.record_assignments_for_access(tracker) 1069 1070 self.attr_usage[path] = tracker.get_all_usage() 1071 self.name_initialisers[path] = tracker.get_all_values() 1072 1073 def start_tracking_in_module(self): 1074 1075 "Start tracking attribute usage in the module." 1076 1077 tracker = BranchTracker() 1078 self.trackers.append(tracker) 1079 1080 def stop_tracking_in_module(self): 1081 1082 "Stop tracking attribute usage in the module." 1083 1084 tracker = self.trackers[0] 1085 self.record_assignments_for_access(tracker) 1086 self.attr_usage[self.name] = tracker.get_all_usage() 1087 self.name_initialisers[self.name] = tracker.get_all_values() 1088 1089 def record_assignments_for_access(self, tracker): 1090 1091 """ 1092 For the current path, use the given 'tracker' to record assignment 1093 version information for attribute accesses. 1094 """ 1095 1096 path = self.get_path_for_access() 1097 1098 if not self.attr_accessor_branches.has_key(path): 1099 return 1100 1101 init_item(self.attr_accessors, path, dict) 1102 attr_accessors = self.attr_accessors[path] 1103 1104 # Obtain the branches applying during each access. 1105 1106 for access, all_branches in self.attr_accessor_branches[path].items(): 1107 name, attrnames = access 1108 init_item(attr_accessors, access, list) 1109 1110 # Obtain the assignments applying to each branch. 1111 1112 for branches in all_branches: 1113 positions = tracker.get_assignment_positions_for_branches(name, branches) 1114 1115 # Detect missing name information. 1116 1117 if None in positions: 1118 globals = self.global_attr_accesses.get(path) 1119 accesses = globals and globals.get(name) 1120 if not accesses: 1121 print >>sys.stderr, "In %s, %s may not be defined when used." % ( 1122 self.get_namespace_path(), name) 1123 positions.remove(None) 1124 1125 attr_accessors[access].append(positions) 1126 1127 def record_branches_for_access(self, branches, name, attrnames): 1128 1129 """ 1130 Record the given 'branches' for an access involving the given 'name' and 1131 'attrnames'. 1132 """ 1133 1134 access = name, attrnames 1135 path = self.get_path_for_access() 1136 1137 init_item(self.attr_accessor_branches, path, dict) 1138 attr_accessor_branches = self.attr_accessor_branches[path] 1139 1140 init_item(attr_accessor_branches, access, list) 1141 attr_accessor_branches[access].append(branches) 1142 1143 def record_access_details(self, name, attrnames, assignment, invocation): 1144 1145 """ 1146 For the given 'name' and 'attrnames', record an access indicating 1147 whether 'assignment' is occurring. 1148 1149 These details correspond to accesses otherwise recorded by the attribute 1150 accessor and attribute access dictionaries. 1151 """ 1152 1153 access = name, attrnames 1154 path = self.get_path_for_access() 1155 1156 init_item(self.attr_access_modifiers, path, dict) 1157 init_item(self.attr_access_modifiers[path], access, list) 1158 1159 access_number = len(self.attr_access_modifiers[path][access]) 1160 self.attr_access_modifiers[path][access].append((assignment, invocation)) 1161 return access_number 1162 1163 def record_global_access_details(self, name, attrnames): 1164 1165 """ 1166 Record details of a global access via the given 'name' involving the 1167 indicated 'attrnames'. 1168 """ 1169 1170 path = self.get_namespace_path() 1171 1172 init_item(self.global_attr_accesses, path, dict) 1173 init_item(self.global_attr_accesses[path], name, set) 1174 self.global_attr_accesses[path][name].add(attrnames) 1175 1176 # Namespace modification. 1177 1178 def record_name(self, name): 1179 1180 "Record the use of 'name' in a namespace." 1181 1182 path = self.get_namespace_path() 1183 init_item(self.names_used, path, set) 1184 self.names_used[path].add(name) 1185 1186 def set_module(self, name, module_name): 1187 1188 """ 1189 Set a module in the current namespace using the given 'name' associated 1190 with the corresponding 'module_name'. 1191 """ 1192 1193 if name: 1194 self.set_general_local(name, Reference("<module>", module_name)) 1195 1196 def set_definition(self, name, kind): 1197 1198 """ 1199 Set the definition having the given 'name' and 'kind'. 1200 1201 Definitions are set in the static namespace hierarchy, but they can also 1202 be recorded for function locals. 1203 """ 1204 1205 if self.is_global(name): 1206 print >>sys.stderr, "In %s, %s is defined as being global." % ( 1207 self.get_namespace_path(), name) 1208 1209 path = self.get_object_path(name) 1210 self.set_object(path, kind) 1211 1212 ref = self.get_object(path) 1213 if ref.get_kind() == "<var>": 1214 print >>sys.stderr, "In %s, %s is defined more than once." % ( 1215 self.get_namespace_path(), name) 1216 1217 if not self.is_global(name) and self.in_function: 1218 self.set_function_local(name, ref) 1219 1220 def set_function_local(self, name, ref=None): 1221 1222 "Set the local with the given 'name' and optional 'ref'." 1223 1224 locals = self.function_locals[self.get_namespace_path()] 1225 multiple = not ref or locals.has_key(name) and locals[name] != ref 1226 locals[name] = multiple and Reference("<var>") or ref 1227 1228 def assign_general_local(self, name, name_ref): 1229 1230 """ 1231 Set for 'name' the given 'name_ref', recording the name for attribute 1232 usage tracking. 1233 """ 1234 1235 self.set_general_local(name, name_ref) 1236 self.assign_name(name, name_ref) 1237 1238 def set_general_local(self, name, value=None): 1239 1240 """ 1241 Set the 'name' with optional 'value' in any kind of local namespace, 1242 where the 'value' should be a reference if specified. 1243 """ 1244 1245 init_value = self.get_initialising_value(value) 1246 1247 # Module global names. 1248 1249 if self.is_global(name): 1250 path = self.get_global_path(name) 1251 self.set_object(path, init_value) 1252 1253 # Function local names. 1254 1255 elif self.in_function: 1256 path = self.get_object_path(name) 1257 self.set_function_local(name, init_value) 1258 1259 # Other namespaces (classes). 1260 1261 else: 1262 path = self.get_object_path(name) 1263 self.set_name(name, init_value) 1264 1265 def set_name(self, name, ref=None): 1266 1267 "Attach the 'name' with optional 'ref' to the current namespace." 1268 1269 self.set_object(self.get_object_path(name), ref) 1270 1271 def set_instance_attr(self, name, ref=None): 1272 1273 """ 1274 Add an instance attribute of the given 'name' to the current class, 1275 using the optional 'ref'. 1276 """ 1277 1278 self._set_instance_attr(self.in_class, name, ref) 1279 1280 def _set_instance_attr(self, path, name, ref=None): 1281 1282 init_item(self.instance_attrs, path, set) 1283 self.instance_attrs[path].add(name) 1284 1285 if ref: 1286 init_item(self.instance_attr_constants, path, dict) 1287 self.instance_attr_constants[path][name] = ref 1288 1289 def get_initialising_value(self, value): 1290 1291 "Return a suitable initialiser reference for 'value'." 1292 1293 # Includes LiteralSequenceRef, ResolvedNameRef... 1294 1295 if isinstance(value, (NameRef, AccessRef, InstanceRef)): 1296 return value.reference() 1297 1298 # In general, invocations do not produce known results. However, the 1299 # name initialisers are resolved once a module has been inspected. 1300 1301 elif isinstance(value, InvocationRef): 1302 return value.reference() 1303 1304 # Variable references are unknown results. 1305 1306 elif isinstance(value, VariableRef): 1307 return value.reference() 1308 1309 else: 1310 return value 1311 1312 # Static, program-relative naming. 1313 1314 def find_name(self, name): 1315 1316 """ 1317 Return the qualified name for the given 'name' used in the current 1318 non-function namespace. 1319 """ 1320 1321 path = self.get_namespace_path() 1322 ref = None 1323 1324 if not self.in_function and name not in predefined_constants: 1325 if self.in_class: 1326 ref = self.get_object(self.get_object_path(name), False) 1327 if not ref: 1328 ref = self.get_global_or_builtin(name) 1329 1330 return ref 1331 1332 def get_class(self, node): 1333 1334 """ 1335 Use the given 'node' to obtain the identity of a class. Return a 1336 reference for the class. Unresolved dependencies are permitted and must 1337 be resolved later. 1338 """ 1339 1340 ref = self._get_class(node) 1341 return ref.has_kind(["<class>", "<depends>"]) and ref or None 1342 1343 def _get_class(self, node): 1344 1345 """ 1346 Use the given 'node' to find a class definition. Return a reference to 1347 the class. 1348 """ 1349 1350 if isinstance(node, compiler.ast.Getattr): 1351 1352 # Obtain the identity of the access target. 1353 1354 ref = self._get_class(node.expr) 1355 1356 # Where the target is a class or module, obtain the identity of the 1357 # attribute. 1358 1359 if ref.has_kind(["<function>", "<var>"]): 1360 return None 1361 else: 1362 attrname = "%s.%s" % (ref.get_origin(), node.attrname) 1363 return self.get_object(attrname) 1364 1365 # Names can be module-level or built-in. 1366 1367 elif isinstance(node, compiler.ast.Name): 1368 1369 # Record usage of the name and attempt to identify it. 1370 1371 self.record_name(node.name) 1372 return self.find_name(node.name) 1373 else: 1374 return None 1375 1376 def get_constant(self, name, value): 1377 1378 "Return a constant reference for the given type 'name' and 'value'." 1379 1380 ref = self.get_builtin_class(name) 1381 return self.get_constant_reference(ref, value) 1382 1383 def get_literal_instance(self, n, name=None): 1384 1385 """ 1386 For node 'n', return a reference to an instance of 'name', or if 'name' 1387 is not specified, deduce the type from the value. 1388 """ 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 # Obtain the details of the literal itself. 1396 # An alias to the type is generated for sequences. 1397 1398 if name in ("dict", "list", "tuple"): 1399 ref = self.get_builtin_class(name) 1400 self.set_special_literal(name, ref) 1401 return self.process_literal_sequence_node(n, name, ref, LiteralSequenceRef) 1402 1403 # Constant values are independently recorded. 1404 1405 else: 1406 value, typename, encoding = self.get_constant_value(n.value, n.literal) 1407 name = get_builtin_type(typename) 1408 ref = self.get_builtin_class(name) 1409 return self.get_constant_reference(ref, value, encoding) 1410 1411 # Special names. 1412 1413 def get_special(self, name): 1414 1415 "Return any stored value for the given special 'name'." 1416 1417 value = self.special.get(name) 1418 if value: 1419 ref, paths = value 1420 else: 1421 ref = None 1422 return ref 1423 1424 def set_special(self, name, value): 1425 1426 """ 1427 Set a special 'name' that merely tracks the use of an implicit object 1428 'value'. 1429 """ 1430 1431 if not self.special.has_key(name): 1432 paths = set() 1433 self.special[name] = value, paths 1434 else: 1435 _ref, paths = self.special[name] 1436 1437 paths.add(self.get_namespace_path()) 1438 1439 def set_special_literal(self, name, ref): 1440 1441 """ 1442 Set a special name for the literal type 'name' having type 'ref'. Such 1443 special names provide a way of referring to literal object types. 1444 """ 1445 1446 literal_name = "$L%s" % name 1447 value = ResolvedNameRef(literal_name, ref) 1448 self.set_special(literal_name, value) 1449 1450 # Functions and invocations. 1451 1452 def set_invocation_usage(self): 1453 1454 """ 1455 Discard the current invocation storage figures, retaining the maximum 1456 values. 1457 """ 1458 1459 for path, (current, maximum) in self.function_targets.items(): 1460 self.importer.function_targets[path] = self.function_targets[path] = maximum 1461 1462 for path, (current, maximum) in self.function_arguments.items(): 1463 self.importer.function_arguments[path] = self.function_arguments[path] = maximum 1464 1465 def allocate_arguments(self, path, args): 1466 1467 """ 1468 Allocate temporary argument storage using current and maximum 1469 requirements for the given 'path' and 'args'. 1470 """ 1471 1472 # Class and module initialisation is ultimately combined. 1473 1474 if not self.in_function: 1475 path = self.name 1476 1477 init_item(self.function_targets, path, lambda: [0, 0]) 1478 t = self.function_targets[path] 1479 t[0] += 1 1480 t[1] = max(t[0], t[1]) 1481 1482 init_item(self.function_arguments, path, lambda: [0, 0]) 1483 t = self.function_arguments[path] 1484 t[0] += len(args) + 1 1485 t[1] = max(t[0], t[1]) 1486 1487 def deallocate_arguments(self, path, args): 1488 1489 "Deallocate temporary argument storage for the given 'path' and 'args'." 1490 1491 # Class and module initialisation is ultimately combined. 1492 1493 if not self.in_function: 1494 path = self.name 1495 1496 self.function_targets[path][0] -= 1 1497 self.function_arguments[path][0] -= len(args) + 1 1498 1499 # Exceptions. 1500 1501 def record_exception_handler(self): 1502 1503 "Record the current namespace as employing an exception handler." 1504 1505 self.exception_namespaces.add(self.get_namespace_path()) 1506 1507 # vim: tabstop=4 expandtab shiftwidth=4