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