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