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