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