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