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