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