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.importer.all_name_references[key] = self.name_references[key] = ref 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 self.add_deferred(ref) 793 794 # Record the imported name and provide the resolved name reference. 795 796 value = ResolvedNameRef(n.name, ref) 797 self.set_special(n.name, value) 798 return value 799 800 # Record usage of the name. 801 802 self.record_name(n.name) 803 804 # Search for unknown names in non-function scopes immediately. 805 # External names in functions are resolved later. 806 807 ref = self.find_name(n.name) 808 if ref: 809 return ResolvedNameRef(n.name, ref) 810 811 # Global name. 812 813 elif self.in_function and n.name in self.scope_globals[path]: 814 return NameRef(n.name) 815 816 # Examine other names. 817 818 else: 819 tracker = self.trackers[-1] 820 821 # Check local names. 822 823 branches = tracker.tracking_name(n.name) 824 825 # Find names inherited from a parent scope. 826 827 if not branches and self.parent_function: 828 branches = tracker.have_name(n.name) 829 if branches: 830 self.propagate_name(n.name) 831 832 # Local or inherited name. 833 834 if branches: 835 self.record_branches_for_access(branches, n.name, None) 836 access_number = self.record_access_details(n.name, None, False) 837 return LocalNameRef(n.name, access_number) 838 839 # Possible global name. 840 841 else: 842 return NameRef(n.name) 843 844 def process_operator_chain(self, nodes, fn): 845 846 """ 847 Process the given chain of 'nodes', applying 'fn' to each node or item. 848 Each node starts a new conditional region, effectively making a deeply- 849 nested collection of if-like statements. 850 """ 851 852 tracker = self.trackers[-1] 853 854 for item in nodes: 855 tracker.new_branchpoint() 856 tracker.new_branch() 857 fn(item) 858 859 for item in nodes[:-1]: 860 tracker.shelve_branch() 861 tracker.new_branch() 862 tracker.shelve_branch() 863 tracker.merge_branches() 864 865 tracker.shelve_branch() 866 tracker.merge_branches() 867 868 def process_try_node(self, n): 869 870 """ 871 Process the given "try...except" node 'n'. 872 """ 873 874 tracker = self.trackers[-1] 875 tracker.new_branchpoint() 876 877 self.process_structure_node(n.body) 878 879 for name, var, handler in n.handlers: 880 if name is not None: 881 self.process_structure_node(name) 882 883 # Any abandoned branches from the body can now be resumed in a new 884 # branch. 885 886 tracker.resume_abandoned_branches() 887 888 # Establish the local for the handler. 889 890 if var is not None: 891 self.process_structure_node(var) 892 if handler is not None: 893 self.process_structure_node(handler) 894 895 tracker.shelve_branch() 896 897 # The else clause maintains the usage from the body but without the 898 # abandoned branches since they would never lead to the else clause 899 # being executed. 900 901 if n.else_: 902 tracker.new_branch() 903 self.process_structure_node(n.else_) 904 tracker.shelve_branch() 905 906 # Without an else clause, a null branch propagates the successful 907 # outcome. 908 909 else: 910 tracker.new_branch() 911 tracker.shelve_branch() 912 913 tracker.merge_branches() 914 915 def process_try_finally_node(self, n): 916 917 """ 918 Process the given "try...finally" node 'n'. 919 """ 920 921 tracker = self.trackers[-1] 922 self.process_structure_node(n.body) 923 924 # Any abandoned branches from the body can now be resumed. 925 926 branches = tracker.resume_all_abandoned_branches() 927 self.process_structure_node(n.final) 928 929 # At the end of the finally clause, abandoned branches are discarded. 930 931 tracker.restore_active_branches(branches) 932 933 def process_while_node(self, n): 934 935 "Process the given while node 'n'." 936 937 tracker = self.trackers[-1] 938 tracker.new_branchpoint(loop_node=True) 939 940 # Evaluate any test or iterator outside the loop. 941 942 self.process_structure_node(n.test) 943 944 # Propagate attribute usage to branches. 945 946 tracker.new_branch(loop_node=True) 947 948 # Enter the loop. 949 950 in_conditional = self.in_conditional 951 self.in_conditional = True 952 self.process_structure_node(n.body) 953 self.in_conditional = in_conditional 954 955 # Continuing branches are resumed before any test. 956 957 tracker.resume_continuing_branches() 958 959 # Evaluate any continuation test within the body. 960 961 self.process_structure_node(n.test) 962 963 tracker.shelve_branch(loop_node=True) 964 965 # Support the non-looping condition. 966 967 tracker.new_branch() 968 tracker.shelve_branch() 969 970 tracker.merge_branches() 971 972 # Evaluate any else clause outside branches. 973 974 if n.else_: 975 self.process_structure_node(n.else_) 976 977 # Connect broken branches to the code after any loop. 978 979 tracker.resume_broken_branches() 980 981 # Branch tracking methods. 982 983 def start_tracking(self, names): 984 985 """ 986 Start tracking attribute usage for names in the current namespace, 987 immediately registering the given 'names'. 988 """ 989 990 path = self.get_namespace_path() 991 parent = self.trackers[-1] 992 tracker = BranchTracker() 993 self.trackers.append(tracker) 994 995 # For functions created from expressions or for functions within 996 # functions, propagate usage to the new namespace. 997 998 if self.parent_function: 999 tracker.inherit_branches(parent, names) 1000 1001 # Record the given names established as new branches. 1002 1003 tracker.assign_names(names) 1004 1005 def assign_name(self, name, name_ref): 1006 1007 "Assign to 'name' the given 'name_ref' in the current namespace." 1008 1009 name = self.get_name_for_tracking(name) 1010 self.trackers[-1].assign_names([name], [name_ref]) 1011 1012 def stop_tracking(self): 1013 1014 """ 1015 Stop tracking attribute usage, recording computed usage for the current 1016 namespace. 1017 """ 1018 1019 path = self.get_namespace_path() 1020 tracker = self.trackers.pop() 1021 self.record_assignments_for_access(tracker) 1022 1023 self.attr_usage[path] = tracker.get_all_usage() 1024 self.name_initialisers[path] = tracker.get_all_values() 1025 1026 def start_tracking_in_module(self): 1027 1028 "Start tracking attribute usage in the module." 1029 1030 tracker = BranchTracker() 1031 self.trackers.append(tracker) 1032 1033 def stop_tracking_in_module(self): 1034 1035 "Stop tracking attribute usage in the module." 1036 1037 tracker = self.trackers[0] 1038 self.record_assignments_for_access(tracker) 1039 self.attr_usage[self.name] = tracker.get_all_usage() 1040 self.name_initialisers[self.name] = tracker.get_all_values() 1041 1042 def propagate_name(self, name): 1043 1044 "Propagate the given 'name' into the current namespace." 1045 1046 path = self.get_namespace_path() 1047 self.propagated_names[path].add(name) 1048 1049 def record_assignments_for_access(self, tracker): 1050 1051 """ 1052 For the current path, use the given 'tracker' to record assignment 1053 version information for attribute accesses. 1054 """ 1055 1056 path = self.get_path_for_access() 1057 1058 if not self.attr_accessor_branches.has_key(path): 1059 return 1060 1061 init_item(self.attr_accessors, path, dict) 1062 attr_accessors = self.attr_accessors[path] 1063 1064 # Obtain the branches applying during each access. 1065 1066 for access, all_branches in self.attr_accessor_branches[path].items(): 1067 name, attrnames = access 1068 init_item(attr_accessors, access, list) 1069 1070 # Obtain the assignments applying to each branch. 1071 1072 for branches in all_branches: 1073 positions = tracker.get_assignment_positions_for_branches(name, branches) 1074 1075 # Detect missing name information. 1076 1077 if None in positions: 1078 globals = self.global_attr_accesses.get(path) 1079 accesses = globals and globals.get(name) 1080 if not accesses: 1081 print >>sys.stderr, "In %s, %s may not be defined when used." % ( 1082 self.get_namespace_path(), name) 1083 positions.remove(None) 1084 1085 attr_accessors[access].append(positions) 1086 1087 def record_branches_for_access(self, branches, name, attrnames): 1088 1089 """ 1090 Record the given 'branches' for an access involving the given 'name' and 1091 'attrnames'. 1092 """ 1093 1094 access = name, attrnames 1095 path = self.get_path_for_access() 1096 1097 init_item(self.attr_accessor_branches, path, dict) 1098 attr_accessor_branches = self.attr_accessor_branches[path] 1099 1100 init_item(attr_accessor_branches, access, list) 1101 attr_accessor_branches[access].append(branches) 1102 1103 def record_access_details(self, name, attrnames, assignment): 1104 1105 """ 1106 For the given 'name' and 'attrnames', record an access indicating 1107 whether 'assignment' is occurring. 1108 1109 These details correspond to accesses otherwise recorded by the attribute 1110 accessor and attribute access dictionaries. 1111 """ 1112 1113 access = name, attrnames 1114 path = self.get_path_for_access() 1115 1116 init_item(self.attr_access_modifiers, path, dict) 1117 init_item(self.attr_access_modifiers[path], access, list) 1118 1119 access_number = len(self.attr_access_modifiers[path][access]) 1120 self.attr_access_modifiers[path][access].append(assignment) 1121 return access_number 1122 1123 def record_global_access_details(self, name, attrnames): 1124 1125 """ 1126 Record details of a global access via the given 'name' involving the 1127 indicated 'attrnames'. 1128 """ 1129 1130 path = self.get_namespace_path() 1131 1132 init_item(self.global_attr_accesses, path, dict) 1133 init_item(self.global_attr_accesses[path], name, set) 1134 self.global_attr_accesses[path][name].add(attrnames) 1135 1136 # Namespace modification. 1137 1138 def record_name(self, name): 1139 1140 "Record the use of 'name' in a namespace." 1141 1142 path = self.get_namespace_path() 1143 init_item(self.names_used, path, set) 1144 self.names_used[path].add(name) 1145 1146 def set_module(self, name, module_name): 1147 1148 """ 1149 Set a module in the current namespace using the given 'name' associated 1150 with the corresponding 'module_name'. 1151 """ 1152 1153 if name: 1154 self.set_general_local(name, Reference("<module>", module_name)) 1155 1156 def set_definition(self, name, kind): 1157 1158 """ 1159 Set the definition having the given 'name' and 'kind'. 1160 1161 Definitions are set in the static namespace hierarchy, but they can also 1162 be recorded for function locals. 1163 """ 1164 1165 if self.is_global(name): 1166 print >>sys.stderr, "In %s, %s is defined as being global." % ( 1167 self.get_namespace_path(), name) 1168 1169 path = self.get_object_path(name) 1170 self.set_object(path, kind) 1171 1172 ref = self.get_object(path) 1173 if ref.get_kind() == "<var>": 1174 print >>sys.stderr, "In %s, %s is defined more than once." % ( 1175 self.get_namespace_path(), name) 1176 1177 if not self.is_global(name) and self.in_function: 1178 self.set_function_local(name, ref) 1179 1180 def set_function_local(self, name, ref=None): 1181 1182 "Set the local with the given 'name' and optional 'ref'." 1183 1184 locals = self.function_locals[self.get_namespace_path()] 1185 multiple = not ref or locals.has_key(name) and locals[name] != ref 1186 locals[name] = multiple and Reference("<var>") or ref 1187 1188 def assign_general_local(self, name, name_ref): 1189 1190 """ 1191 Set for 'name' the given 'name_ref', recording the name for attribute 1192 usage tracking. 1193 """ 1194 1195 self.set_general_local(name, name_ref) 1196 self.assign_name(name, name_ref) 1197 1198 def set_general_local(self, name, value=None): 1199 1200 """ 1201 Set the 'name' with optional 'value' in any kind of local namespace, 1202 where the 'value' should be a reference if specified. 1203 """ 1204 1205 init_value = self.get_initialising_value(value) 1206 1207 # Module global names. 1208 1209 if self.is_global(name): 1210 path = self.get_global_path(name) 1211 self.set_object(path, init_value) 1212 1213 # Function local names. 1214 1215 elif self.in_function: 1216 path = self.get_object_path(name) 1217 self.set_function_local(name, init_value) 1218 1219 # Other namespaces (classes). 1220 1221 else: 1222 path = self.get_object_path(name) 1223 self.set_name(name, init_value) 1224 1225 def set_name(self, name, ref=None): 1226 1227 "Attach the 'name' with optional 'ref' to the current namespace." 1228 1229 self.set_object(self.get_object_path(name), ref) 1230 1231 def set_instance_attr(self, name, ref=None): 1232 1233 """ 1234 Add an instance attribute of the given 'name' to the current class, 1235 using the optional 'ref'. 1236 """ 1237 1238 init_item(self.instance_attrs, self.in_class, set) 1239 self.instance_attrs[self.in_class].add(name) 1240 1241 if ref: 1242 init_item(self.instance_attr_constants, self.in_class, dict) 1243 self.instance_attr_constants[self.in_class][name] = ref 1244 1245 def get_initialising_value(self, value): 1246 1247 "Return a suitable initialiser reference for 'value'." 1248 1249 # Includes LiteralSequenceRef, ResolvedNameRef... 1250 1251 if isinstance(value, (NameRef, AccessRef, InstanceRef)): 1252 return value.reference() 1253 1254 # In general, invocations do not produce known results. However, the 1255 # name initialisers are resolved once a module has been inspected. 1256 1257 elif isinstance(value, InvocationRef): 1258 return value.reference() 1259 1260 else: 1261 return value 1262 1263 # Static, program-relative naming. 1264 1265 def find_name(self, name): 1266 1267 """ 1268 Return the qualified name for the given 'name' used in the current 1269 non-function namespace. 1270 """ 1271 1272 path = self.get_namespace_path() 1273 ref = None 1274 1275 if not self.in_function and name not in predefined_constants: 1276 if self.in_class: 1277 ref = self.get_object(self.get_object_path(name)) 1278 if not ref: 1279 ref = self.get_global_or_builtin(name) 1280 1281 return ref 1282 1283 def get_class(self, node): 1284 1285 """ 1286 Use the given 'node' to obtain the identity of a class. Return a 1287 reference for the class. Unresolved dependencies are permitted and must 1288 be resolved later. 1289 """ 1290 1291 ref = self._get_class(node) 1292 return ref.has_kind(["<class>", "<depends>"]) and ref or None 1293 1294 def _get_class(self, node): 1295 1296 """ 1297 Use the given 'node' to find a class definition. Return a reference to 1298 the class. 1299 """ 1300 1301 if isinstance(node, compiler.ast.Getattr): 1302 1303 # Obtain the identity of the access target. 1304 1305 ref = self._get_class(node.expr) 1306 1307 # Where the target is a class or module, obtain the identity of the 1308 # attribute. 1309 1310 if ref.has_kind(["<function>", "<var>"]): 1311 return None 1312 else: 1313 attrname = "%s.%s" % (ref.get_origin(), node.attrname) 1314 return self.get_object(attrname) 1315 1316 # Names can be module-level or built-in. 1317 1318 elif isinstance(node, compiler.ast.Name): 1319 1320 # Record usage of the name and attempt to identify it. 1321 1322 self.record_name(node.name) 1323 return self.get_global_or_builtin(node.name) 1324 else: 1325 return None 1326 1327 def get_constant(self, name, value): 1328 1329 "Return a constant reference for the given type 'name' and 'value'." 1330 1331 ref = self.get_builtin_class(name) 1332 return self.get_constant_reference(ref, value) 1333 1334 def get_literal_instance(self, n, name): 1335 1336 "For node 'n', return a reference to an instance of 'name'." 1337 1338 # Get a reference to the built-in class. 1339 1340 ref = self.get_builtin_class(name) 1341 1342 # Obtain the details of the literal itself. 1343 # An alias to the type is generated for sequences. 1344 1345 if name in ("dict", "list", "tuple"): 1346 self.set_special_literal(name, ref) 1347 return self.process_literal_sequence_node(n, name, ref, LiteralSequenceRef) 1348 1349 # Constant values are independently recorded. 1350 1351 else: 1352 return self.get_constant_reference(ref, n.value) 1353 1354 # Special names. 1355 1356 def get_special(self, name): 1357 1358 "Return any stored value for the given special 'name'." 1359 1360 return self.special.get(name) 1361 1362 def set_special(self, name, value): 1363 1364 """ 1365 Set a special 'name' that merely tracks the use of an implicit object 1366 'value'. 1367 """ 1368 1369 self.special[name] = value 1370 1371 def set_special_literal(self, name, ref): 1372 1373 """ 1374 Set a special name for the literal type 'name' having type 'ref'. Such 1375 special names provide a way of referring to literal object types. 1376 """ 1377 1378 literal_name = "$L%s" % name 1379 value = ResolvedNameRef(literal_name, ref) 1380 self.set_special(literal_name, value) 1381 1382 # Functions and invocations. 1383 1384 def allocate_arguments(self, path, args): 1385 1386 """ 1387 Allocate temporary argument storage using current and maximum 1388 requirements for the given 'path' and 'args'. 1389 """ 1390 1391 init_item(self.function_targets, path, lambda: [0, 0]) 1392 t = self.function_targets[path] 1393 t[0] += 1 1394 t[1] = max(t[0], t[1]) 1395 1396 init_item(self.function_arguments, path, lambda: [0, 0]) 1397 t = self.function_arguments[path] 1398 t[0] += len(args) + 1 1399 t[1] = max(t[0], t[1]) 1400 1401 def deallocate_arguments(self, path, args): 1402 1403 "Deallocate temporary argument storage for the given 'path' and 'args'." 1404 1405 self.function_targets[path][0] -= 1 1406 self.function_arguments[path][0] -= len(args) + 1 1407 1408 # vim: tabstop=4 expandtab shiftwidth=4