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