1 #!/usr/bin/env python 2 3 """ 4 Program data structures. There are two separate kinds of structures: those with 5 context, which are the values manipulated by programs, and those without 6 context, which are typically constant things which are stored alongside the 7 program but which are wrapped in context-dependent structures in the running 8 program. 9 10 Copyright (C) 2007, 2008, 2009, 2010 Paul Boddie <paul@boddie.org.uk> 11 12 This program is free software; you can redistribute it and/or modify it under 13 the terms of the GNU General Public License as published by the Free Software 14 Foundation; either version 3 of the License, or (at your option) any later 15 version. 16 17 This program is distributed in the hope that it will be useful, but WITHOUT 18 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 19 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 20 details. 21 22 You should have received a copy of the GNU General Public License along with 23 this program. If not, see <http://www.gnu.org/licenses/>. 24 25 -------- 26 27 The principal value structure class in this module is the Attr class which 28 represents attributes of objects and retains the context of each reference to an 29 attribute. This class models program behaviour at run-time. 30 31 The central data structure classes in this module are the following: 32 33 * Class 34 * Function 35 * Module 36 37 All of the above support the Naming interface either explicitly or through 38 general conformance, meaning that all can be asked to provide their 'full_name' 39 using the method of that name. 40 41 Additionally, all of the above also support a dictionary interface in order to 42 access names within their defined scopes. Specific methods also exist in order 43 to distinguish between certain kinds of attributes: 44 45 * Class: class_attributes, all_class_attributes, instance_attributes, all_attributes 46 * Function: parameters, locals, all_locals 47 * Module: module_attributes 48 49 These specific methods are useful in certain situations. 50 51 The above classes also provide an 'astnode' attribute, indicating the AST node 52 where each such object is defined. 53 """ 54 55 from micropython.program import DataObject, DataValue, ReplaceableContext, PlaceholderContext 56 from micropython.common import AtLeast, InspectError 57 58 def shortrepr(obj): 59 if obj is None: 60 return repr(None) 61 else: 62 return obj.__shortrepr__() 63 64 lambda_index = 0 65 66 def new_lambda(): 67 68 "Return a new sequence number for a lambda definition." 69 70 global lambda_index 71 lambda_index += 1 72 return lambda_index 73 74 # Mix-ins and abstract classes. 75 76 class Naming: 77 78 "A mix-in providing naming conveniences." 79 80 def full_name(self): 81 if self.name is not None: 82 return self.parent.full_name() + "." + self.name 83 else: 84 return self.parent.full_name() 85 86 class NamespaceDict: 87 88 "A mix-in providing dictionary methods." 89 90 def __init__(self, module=None): 91 self.module = module 92 self.namespace = {} 93 self.globals = set() 94 self.lambdas = {} # only really useful for functions 95 self.finalised = 0 96 97 # Attributes accessed on objects, potentially narrowing their types. 98 # Specific namespaces should define known names during initialisation. 99 # For example, functions can define names belonging to parameters. 100 101 # Attribute users, defining names which use attributes. 102 103 self.attribute_users = [{}] # stack of assignments and branches 104 self.attribute_user_shelves = [] 105 106 # Scope usage, indicating the origin of names. 107 108 self.scope_usage = [{}] # stack of scope usage 109 self.scope_shelves = [] 110 111 # Define attribute usage to identify active program sections. 112 # Attribute users are AST nodes defining names. 113 114 self.all_attribute_users = set() 115 116 # Attribute/name definition and access. 117 118 def __delitem__(self, name): 119 del self.namespace[name] 120 121 def has_key(self, name): 122 return self.namespace.has_key(name) 123 124 def keys(self): 125 return self.namespace.keys() 126 127 def values(self): 128 return self.namespace.values() 129 130 def items(self): 131 return self.namespace.items() 132 133 def __getitem__(self, name): 134 return self.namespace[name] 135 136 def get(self, name, default=None): 137 return self.namespace.get(name, default) 138 139 # Administrative methods. 140 141 def items_for_vacuum(self): 142 return self.items() + self.lambdas.items() 143 144 def vacuum_item(self, name): 145 if self.has_key(name): 146 del self[name] 147 148 def add_lambda(self, obj): 149 attr = Attr(None, self, obj.name) 150 attr.update([self.get_context_and_value(obj)], single_assignment=1) 151 self.lambdas[obj.name] = attr 152 153 # Specialised access methods. 154 155 def get_using_node(self, name, node): 156 157 """ 158 Access the given 'name' through this namespace, making use of the module 159 and builtins namespaces if necessary, annotating the given 'node' with 160 the scope involved. 161 """ 162 163 attr, scope, full_name = self._get_with_scope(name) 164 165 if scope is not None: 166 node._scope = scope 167 self.note_scope(name, scope) 168 169 if full_name is not None: 170 self.use_specific_attribute(full_name, name) 171 172 return attr 173 174 def _get_with_scope(self, name, external=0): 175 176 """ 177 Find the source of the given 'name', returning the attribute object, 178 scope (constant, local, global or builtins), and the full name of the 179 source namespace (or None for constants). 180 181 If the optional 'external' flag is set to a true value, only external 182 (non-local) namespaces will be involved in the search. 183 """ 184 185 module = self.module 186 builtins = module and module.builtins or None 187 importer = module and module.importer or None 188 189 # Constants. 190 191 if importer is not None and importer.predefined_constants.has_key(name): 192 return importer.get_predefined_constant(name), "constant", None 193 194 # Locals. 195 196 elif not external and self.has_key(name): 197 return self[name], "local", self.full_name() 198 199 # Globals. 200 201 elif module is not None and module is not self and module.has_key(name): 202 return module[name], "global", module.full_name() 203 204 # Builtins. 205 206 elif builtins is not None and builtins.has_key(name): 207 return builtins[name], "builtins", builtins.full_name() 208 209 # Unknown. 210 211 else: 212 return None, None, None 213 214 # Attribute definition methods. 215 216 def __setitem__(self, name, value): 217 self.set(name, value) 218 219 def set(self, name, value, single_assignment=1): 220 221 """ 222 A more powerful set operation, making 'name' refer to 'value' whilst 223 indicating whether a 'single_assignment' (true by default) occurs in 224 this operation (or whether the operation covers potentially many 225 assignments in the lifetime of a program). 226 """ 227 228 if name in self.globals: 229 self.module.set(name, value, 0) 230 else: 231 self._set(name, value, single_assignment) 232 self.define_scope(name, "local") 233 234 def set_module(self, name, value): 235 236 """ 237 A specialised set operation, making 'name' refer to 'value' in the 238 context of making a module reference available in association with 239 'name' as part of the import of that module or a submodule of that 240 module. 241 """ 242 243 self._set(name, value, 1) 244 245 def _set(self, name, attr_or_value, single_assignment=1): 246 247 """ 248 The underlying set operation associating 'name' with the given 249 'attr_or_value'. 250 See: docs/assignment.txt 251 """ 252 253 # Add and/or obtain the namespace entry. 254 255 if not self.namespace.has_key(name): 256 self.namespace[name] = Attr(None, self, name) 257 258 attr = self.namespace[name] 259 self._set_using_attr(attr, attr_or_value, single_assignment) 260 261 def _set_using_attr(self, attr, attr_or_value, single_assignment=1): 262 263 # Handle attribute assignment as well as assignment of basic objects. 264 # Attempt to fix the context if not explicitly defined. 265 266 if isinstance(attr_or_value, Attr): 267 context_values = self.get_updated_context_values(attr_or_value.context_values) 268 else: 269 context_values = self.get_updated_context_values([self.get_context_and_value(attr_or_value)]) 270 271 attr.update(context_values, single_assignment) 272 273 def get_context_and_value(self, value): 274 275 "Return a context, value tuple for the given 'value'." 276 277 # Functions have a replaceable context. 278 279 if isinstance(value, Function): 280 return (ReplaceableContext, value) 281 282 # Classes use placeholder contexts which cannot be replaced but which 283 # do not communicate useful contextual information. 284 285 elif isinstance(value, Class): 286 return (PlaceholderContext, value) 287 288 # Other values employ themselves as the context. 289 290 else: 291 return (value, value) 292 293 def get_updated_context_values(self, context_values): 294 295 """ 296 Adapt the contexts found in the given 'context_values', returning a new 297 set. 298 See: docs/assignment.txt 299 """ 300 301 results = set() 302 303 for context, value in context_values: 304 305 # Set the context of instances to themselves. 306 307 if isinstance(value, Instance): 308 results.add((value, value)) 309 else: 310 results.add((context, value)) 311 312 return results 313 314 def make_global(self, name): 315 316 "Declare 'name' as a global in the current namespace." 317 318 if not self.namespace.has_key(name): 319 self.globals.add(name) 320 self.define_scope(name, "global") 321 return 1 322 else: 323 return 0 324 325 # Attribute positioning. 326 327 def attributes_as_list(self): 328 329 "Return the attributes in a list." 330 331 self.finalise_attributes() 332 l = [None] * len(self.keys()) 333 for attr in self.values(): 334 l[attr.position] = attr 335 return l 336 337 def finalise_attributes(self): 338 339 "Make sure all attributes are fully defined." 340 341 if self.finalised: 342 return 343 344 # The default action is to assign attribute positions sequentially. 345 346 for i, attr in enumerate(self.values()): 347 attr.position = i 348 349 self.finalised = 1 350 351 def unfinalise_attributes(self): 352 353 "Open attribute definitions to editing and subsequent finalisation." 354 355 self.finalised = 0 356 357 # Attribute usage methods. 358 359 def finalise_attribute_usage(self): 360 361 "Propagate attribute usage for the namespace to the importer." 362 363 module = self.module 364 importer = module and module.importer 365 366 if importer is not None: 367 for names in self.get_all_attribute_usage(): 368 importer.use_names(names, self.full_name()) 369 370 def get_all_attribute_usage(self): 371 372 """ 373 Return a set of all usage tuples for attributes used with the different 374 local names. 375 """ 376 377 usage = set() 378 for user in self.all_attribute_users: 379 380 # First, visit the contributors and combine their usage with the 381 # usage for each user. 382 383 user._attrcombined = combined_usage = self.get_usage_from_contributors(user) 384 385 for name, all_usage in combined_usage.items(): 386 for attrnames in all_usage: 387 usage.add(tuple(attrnames)) 388 389 return usage 390 391 def get_usage_from_contributors(self, node): 392 393 """ 394 Obtain usage information from the given 'node', combined with usage 395 details from its contributors, returning a dictionary mapping names to 396 lists of usage possibilities. 397 """ 398 399 usage = {} 400 contributor_usage = {} 401 402 # Visit each contributor, gathering usage for each name. 403 404 for contributor in node._attrbranches: 405 406 # Get contributed usage for each contributor. 407 # This gathers usage for each name such as {(a, b), (c, d)} and 408 # {(a, b), (e, f)} into a single set {(a, b), (c, d), (e, f)}. 409 410 for name, all_usage in self.get_usage_from_contributors(contributor).items(): 411 if not contributor_usage.has_key(name): 412 contributor_usage[name] = set() 413 contributor_usage[name].update(all_usage) 414 415 # Then get the resulting usage. 416 417 contributed_names = contributor_usage.keys() 418 current_usage = node._attrnames 419 420 for name in contributed_names: 421 422 # Where contributors define names not present at this level, just 423 # use the contributed usage. 424 425 current_usage_for_name = current_usage.get(name) 426 427 if current_usage_for_name is None: 428 usage[name] = contributor_usage[name] 429 430 # Otherwise, combine the current usage with the contributed usage. 431 # Thus, usage of (f, g) combined with {(a, b), (c, d)} would give 432 # {(f, g, a, b), (f, g, c, d)}. 433 434 else: 435 usage[name] = set() 436 for attrnames in contributor_usage[name]: 437 usage[name].add(tuple(current_usage_for_name.union(attrnames))) 438 439 # Maintain usage not affected by contributors. 440 # Usage of (f, g) would become {(f, g)}. 441 442 for name in current_usage.keys(): 443 if name not in contributed_names: 444 usage[name] = set([tuple(current_usage[name])]) 445 446 return usage 447 448 def use_attribute(self, name, attrname): 449 450 "Declare the usage on 'name' of the given 'attrname'." 451 452 return self._use_attribute(name, attrname) 453 454 def use_specific_attribute(self, objname, attrname): 455 456 "Declare the usage on 'objname' of the given 'attrname'." 457 458 self._use_specific_attribute(objname, attrname) 459 460 # These shadow various methods in the InspectedModule class, and provide 461 # implementations generally. 462 463 def _use_specific_attribute(self, objname, attrname): 464 465 """ 466 Note attribute usage specifically on 'objname' - an object which is 467 known at inspection time - or in the current unit if 'objname' is None, 468 nominating a specific attribute 'attrname'. 469 470 This bypasses attribute user mechanisms. 471 """ 472 473 from_name = self.full_name() 474 objname = objname or from_name 475 module = self.module 476 importer = module and module.importer 477 478 if importer is not None: 479 importer.use_specific_name(objname, attrname, from_name) 480 481 def _use_attribute(self, name, attrname): 482 483 """ 484 Indicate the use of the given 'name' in this namespace of an attribute 485 with the given 'attrname'. 486 """ 487 488 users = self.attribute_users[-1] 489 490 # Add the usage to all current users. 491 492 if users.has_key(name): 493 for user in users[name]: 494 user._attrnames[name].add(attrname) 495 return users[name] 496 else: 497 return [] 498 499 def _define_attribute_user(self, node): 500 501 """ 502 Define 'node' as the user of attributes, indicating the point where the 503 user is defined. 504 """ 505 506 name = node.name 507 self._define_attribute_user_for_name(node, name) 508 509 def _define_attribute_user_for_name(self, node, name): 510 511 "Define 'node' as the user of attributes for the given 'name'." 512 513 users = self.attribute_users[-1] 514 515 # This node overrides previous definitions. 516 517 users[name] = set([node]) 518 519 # Record the attribute combinations for the name. 520 521 self._init_attribute_user_for_name(node, name) 522 523 # Remember this user. 524 525 self.all_attribute_users.add(node) 526 527 def _init_attribute_user_for_name(self, node, name): 528 529 "Make sure that 'node' is initialised for 'name'." 530 531 self._init_attribute_user(node) 532 node._attrnames[name] = set() 533 534 def _init_attribute_user(self, node): 535 if not hasattr(node, "_attrnames"): 536 node._attrnames = {} 537 538 if not hasattr(node, "_attrbranches"): 539 node._attrbranches = [] 540 541 # Branch management methods. 542 543 def _new_branchpoint(self): 544 545 """ 546 Establish a new branchpoint where several control-flow branches diverge 547 and subsequently converge. 548 """ 549 550 self.attribute_user_shelves.append([]) 551 self.scope_shelves.append([]) 552 553 def _new_branch(self, node): 554 555 """ 556 Establish a new control-flow branch, transferring attribute usage to 557 the new branch so that it may be augmented for each name locally. 558 559 Add the given 'node' as an active user to be informed of attribute 560 usage. 561 """ 562 563 attribute_users = self.attribute_users[-1] 564 565 # Define this node as the active attribute user for all currently 566 # defined names. 567 568 new_users = {} 569 570 for name in attribute_users.keys(): 571 new_users[name] = [node] 572 self._init_attribute_user_for_name(node, name) 573 574 self._init_attribute_user(node) 575 self.attribute_users.append(new_users) 576 577 # Add this user as a contributor to the previously active users. 578 579 all_users = set() 580 581 for users in attribute_users.values(): 582 all_users.update(users) 583 584 for user in all_users: 585 self._init_attribute_user(user) 586 user._attrbranches.append(node) 587 588 # Retain a record of scope usage. 589 590 scope_usage = {} 591 scope_usage.update(self.scope_usage[-1]) 592 self.scope_usage.append(scope_usage) 593 594 def _abandon_branch(self): 595 596 """ 597 Abandon scope usage, permitting locally different scopes for names, 598 provided these cannot "escape" from the branch. 599 """ 600 601 self.scope_usage[-1] = AbandonedBranchScope() 602 603 def _shelve_branch(self): 604 605 """ 606 Shelve the current control-flow branch, recording the attribute usage 607 for subsequent merging. If this branch should be abandoned, the usage 608 observations are still recorded but will not contribute to subsequent 609 observations after a merge. 610 """ 611 612 users = self.attribute_users.pop() 613 self.attribute_user_shelves[-1].append(users) 614 615 scope_usage = self.scope_usage.pop() 616 self.scope_shelves[-1].append(scope_usage) 617 618 def _merge_branches(self): 619 620 """ 621 Merge control-flow branches. This should find the users active within 622 each branch, which have been "shelved", and update the active users 623 dictionary with these contributions. 624 """ 625 626 # Combine the attribute users. This ensures that a list of users 627 # affected by attribute usage is maintained for the current branch. 628 629 users = self.attribute_users[-1] 630 new_users = {} 631 632 all_shelved_users = self.attribute_user_shelves.pop() 633 all_user_names = set() 634 635 # Find all the names defined by the branches. 636 637 for shelved_users in all_shelved_users: 638 all_user_names.update(shelved_users.keys()) 639 640 # Copy all definitions from the branches for the names, maintaining 641 # the existing users where a branch does not redefine a name. 642 643 for shelved_users in all_shelved_users: 644 for name in all_user_names: 645 646 if shelved_users.has_key(name): 647 nodes = shelved_users[name] 648 else: 649 nodes = users.get(name, set()) 650 651 if nodes: 652 if not new_users.has_key(name): 653 new_users[name] = set(nodes) 654 else: 655 new_users[name].update(nodes) 656 657 self.attribute_users[-1] = new_users 658 659 # Combine the scope usage. 660 661 scope_usage = self.scope_usage[-1] 662 new_scope_usage = {} 663 664 all_scope_usage = self.scope_shelves.pop() 665 all_scope_names = set() 666 667 # Find all the names for whom scope information has been defined. 668 669 for shelved_usage in all_scope_usage: 670 all_scope_names.update(shelved_usage.keys()) 671 672 for shelved_usage in all_scope_usage: 673 for name in all_scope_names: 674 675 # Find the recorded scope for the name. 676 677 if shelved_usage.has_key(name): 678 scope = shelved_usage[name] 679 elif scope_usage.has_key(name): 680 scope = scope_usage[name] 681 682 # For abandoned branches, no scope is asserted for a name. 683 684 elif isinstance(shelved_usage, AbandonedBranchScope): 685 scope = None 686 687 # If no scope is recorded, find a suitable external source. 688 689 else: 690 attr, scope, full_name = self._get_with_scope(name, external=1) 691 692 # Attempt to record the scope, testing for conflicts. 693 694 if scope: 695 if not new_scope_usage.has_key(name): 696 new_scope_usage[name] = scope 697 elif new_scope_usage[name] != scope: 698 new_scope_usage[name] = ScopeConflict(scope, new_scope_usage[name]) 699 700 self.scope_usage[-1] = new_scope_usage 701 702 # Scope usage methods. 703 704 def define_scope(self, name, scope): 705 706 """ 707 Define 'name' as being from the given 'scope' in the current namespace. 708 """ 709 710 self.scope_usage[-1][name] = scope 711 712 def note_scope(self, name, scope): 713 714 """ 715 Note usage of 'name' from the given 'scope' in the current namespace. 716 If a conflict has been recorded previously, raise an exception. 717 """ 718 719 scope_usage = self.scope_usage[-1] 720 721 if scope_usage.has_key(name): 722 found_scope = scope_usage[name] 723 if isinstance(found_scope, ScopeConflict): 724 raise InspectError("Scope conflict for %r: defined as both %s and %s." % ( 725 name, found_scope.old_scope, found_scope.new_scope)) 726 727 scope_usage[name] = scope 728 729 def used_in_scope(self, name, scope): 730 731 """ 732 Return whether 'name' is used from the given 'scope' in the current 733 namespace. 734 """ 735 736 scope_usage = self.scope_usage[-1] 737 return scope_usage.get(name) == scope 738 739 # Special helper classes for scope resolution. 740 741 class AbandonedBranchScope: 742 743 """ 744 A class providing a value or state for an abandoned branch distinct from an 745 empty scope dictionary. 746 """ 747 748 def has_key(self, name): 749 return 0 750 751 def __setitem__(self, name, value): 752 pass 753 754 def __getitem__(self, name): 755 raise KeyError, name 756 757 def get(self, name, default=None): 758 return default 759 760 def keys(self): 761 return [] 762 763 values = items = keys 764 765 class ScopeConflict: 766 767 """ 768 A scope conflict caused when different code branches contribute different 769 sources of names. 770 """ 771 772 def __init__(self, old_scope, new_scope): 773 self.old_scope = old_scope 774 self.new_scope = new_scope 775 776 class NullBranch: 777 778 "A class representing an attribute user for a non-existent branch." 779 780 pass 781 782 # Program data structures. 783 784 class Attr: 785 786 "An attribute entry having a context." 787 788 def __init__(self, position, parent, name): 789 790 """ 791 Initialise the attribute with the given 'position' within the collection 792 of attributes of its 'parent', indicating its 'name'. 793 """ 794 795 self.position = position 796 self.parent = parent 797 self.name = name 798 799 # Possible values. 800 801 self.context_values = set() 802 803 # Number of assignments per name. 804 805 self.assignments = None 806 807 # Value-related methods. 808 809 def get_contexts(self): 810 return [c for (c, v) in self.context_values] 811 812 def get_values(self): 813 return [v for (c, v) in self.context_values] 814 815 def get_context(self): 816 if len(self.context_values) == 1: 817 return self.get_contexts()[0] 818 else: 819 return None 820 821 def get_value(self): 822 if len(self.context_values) == 1: 823 return self.get_values()[0] 824 else: 825 return None 826 827 def update(self, context_values, single_assignment): 828 829 """ 830 Update the attribute, adding the 'context_values' provided to the 831 known details associated with the attribute, changing the number of 832 assignments according to the 'single_assignment' status of the 833 operation, where a true value indicates that only one assignment is 834 associated with the update, and a false value indicates that potentially 835 many assignments may be involved. 836 """ 837 838 if self.assignments is None: 839 if single_assignment: 840 self.assignments = 1 841 else: 842 self.assignments = AtLeast(1) 843 else: 844 if single_assignment: 845 self.assignments += 1 846 else: 847 self.assignments += AtLeast(1) 848 849 self.context_values.update(context_values) 850 851 def is_constant(self): 852 853 """ 854 Return whether this attribute references something that can be regarded 855 as being constant within a particular scope. 856 """ 857 858 return self.assignments == 1 859 860 def is_strict_constant(self): 861 862 """ 863 Return whether this attribute references something that can be regarded 864 as being constant. 865 """ 866 867 value = self.get_value() 868 return not (value is None or isinstance(value, Instance)) 869 870 def is_static_attribute(self): 871 872 """ 873 Return whether this attribute is defined on a fixed/static object such 874 as a class or a module. 875 """ 876 877 return isinstance(self.parent, (Class, Module)) 878 879 def defines_ambiguous_class(self): 880 881 "Return whether this attribute defines more than one class." 882 883 if self.assignments > 1: 884 have_class = 0 885 for obj in self.get_values(): 886 if isinstance(obj, Class): 887 if have_class: 888 return 1 889 have_class = 1 890 891 return 0 892 893 def defined_within_hierarchy(self): 894 895 """ 896 Return whether the parent and context of the attribute belong to the 897 same class hierarchy. 898 """ 899 900 # Must be defined within a class. 901 902 if isinstance(self.parent, Class): 903 904 # To be sure, all contexts must be classes and be the same as the 905 # parent, or be a superclass of the parent, or be a subclass of the 906 # parent. 907 908 for context in self.get_contexts(): 909 if not ( 910 isinstance(context, Class) and ( 911 context is self.parent or 912 context.has_subclass(self.parent) or 913 self.parent.has_subclass(context)) 914 ): 915 return 0 916 917 return 1 918 919 # Instance attributes are not defined within a hierarchy. 920 921 else: 922 return 0 923 924 def defined_outside_hierarchy(self): 925 926 """ 927 Return whether the parent and context of the attribute never belong to 928 the same class hierarchy. 929 """ 930 931 # Must be defined within a class. 932 933 if isinstance(self.parent, Class): 934 935 # To be sure, all contexts must be classes and be the same as the 936 # parent, or be a superclass of the parent, or be a subclass of the 937 # parent. 938 939 for context in self.get_contexts(): 940 if not ( 941 isinstance(context, Class) and not ( 942 context is self.parent or 943 context.has_subclass(self.parent) or 944 self.parent.has_subclass(context)) 945 ): 946 return 0 947 948 return 1 949 950 # Instance attributes are not defined within a hierarchy. 951 952 else: 953 return 0 954 955 def __repr__(self): 956 return "Attr(%r, %s, %r) # {[%s] (%r)}" % ( 957 self.position, shortrepr(self.parent), self.name, 958 self._context_values_str(), self.assignments 959 ) 960 961 def __shortrepr__(self): 962 return "Attr(%r, %s, %r)" % ( 963 self.position, shortrepr(self.parent), self.name 964 ) 965 966 def _context_values_str(self): 967 l = [] 968 for (c, v) in self.context_values: 969 l.append("(c=%s, v=%s)" % (shortrepr(c), shortrepr(v))) 970 return ", ".join(l) 971 972 # Instances are special in that they need to be wrapped together with context in 973 # a running program, but they are not generally constant. 974 975 class Instance: 976 977 "A placeholder indicating the involvement of an instance." 978 979 def __init__(self): 980 self.parent = None 981 982 # Image generation details. 983 984 self.location = None 985 986 def __repr__(self): 987 return "Instance()" 988 989 __shortrepr__ = __repr__ 990 991 class Constant: 992 993 "A superclass for all constant or context-free structures." 994 995 pass 996 997 # Data objects appearing in programs before run-time. 998 999 class Const(Constant, Instance): 1000 1001 "A constant object with no context." 1002 1003 def __init__(self, value): 1004 Instance.__init__(self) 1005 self.value = value 1006 1007 def get_value(self): 1008 return self.value 1009 1010 def __repr__(self): 1011 if self.location is not None: 1012 return "Const(%r, location=%r)" % (self.value, self.location) 1013 else: 1014 return "Const(%r)" % self.value 1015 1016 __shortrepr__ = __repr__ 1017 1018 # Support constants as dictionary keys in order to build constant tables. 1019 1020 def __eq__(self, other): 1021 return other is not None and self.value == other.value and self.value.__class__ is other.value.__class__ 1022 1023 def __hash__(self): 1024 return hash(self.value) 1025 1026 def value_type_name(self): 1027 return "__builtins__." + self.value.__class__.__name__ 1028 1029 class Class(NamespaceDict, Naming, Constant): 1030 1031 "An inspected class." 1032 1033 def __init__(self, name, parent, module=None, node=None): 1034 1035 """ 1036 Initialise the class with the given 'name', 'parent' object, optional 1037 'module' and optional AST 'node'. 1038 """ 1039 1040 NamespaceDict.__init__(self, module) 1041 self.name = name 1042 self.parent = parent 1043 self.astnode = node 1044 1045 # Superclasses, descendants and attributes. 1046 1047 self.bases = [] 1048 self.descendants = set() 1049 self.instattr = set() # instance attributes 1050 self.relocated = set() # attributes which do not have the same 1051 # position as those of the same name in 1052 # some superclasses 1053 1054 # Caches. 1055 1056 self.reset_caches() 1057 1058 # Image generation details. 1059 1060 self.location = None 1061 self.code_location = None 1062 self.code_body_location = None # corresponds to the instantiator 1063 1064 self.instantiator = None 1065 self.instance_template_location = None # for creating instances at run-time 1066 1067 # Program-related details. 1068 1069 self.blocks = None 1070 self.temp_usage = 0 1071 self.local_usage = 0 1072 self.all_local_usage = 0 1073 1074 # Add this class to its attributes. 1075 1076 self.set("__class__", self) 1077 1078 def reset_caches(self): 1079 1080 "Reset the caches." 1081 1082 self.all_instattr = None # cache for instance_attributes 1083 self.all_instattr_names = None # from all_instattr 1084 self.all_classattr = None # cache for all_class_attributes 1085 self.all_classattr_names = None # from all_classattr 1086 self.allattr = None # cache for all_attributes 1087 self.allattr_names = None # from allattr 1088 1089 def __repr__(self): 1090 if self.location is not None: 1091 return "Class(%r, %s, location=%r)" % (self.name, shortrepr(self.parent), self.location) 1092 else: 1093 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 1094 1095 def __shortrepr__(self): 1096 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 1097 1098 def get_body_block(self): 1099 return self.get_instantiator().blocks[0] 1100 1101 # Namespace-related methods. 1102 1103 def get_updated_context_values(self, context_values): 1104 1105 """ 1106 Adapt the contexts found in the given 'context_values', returning a new 1107 set. 1108 See: docs/assignment.txt 1109 """ 1110 1111 results = set() 1112 1113 for context, value in context_values: 1114 1115 # Change the ownership of functions. 1116 1117 if context is ReplaceableContext and value is not None and isinstance(value, Function): 1118 results.add((self, value)) 1119 else: 1120 results.add((context, value)) 1121 1122 return NamespaceDict.get_updated_context_values(self, results) 1123 1124 # Administrative methods. 1125 1126 def finalise_attributes(self): 1127 1128 "Make sure that all attributes are fully defined." 1129 1130 if self.finalised: 1131 return 1132 1133 self.finalise_class_attributes() 1134 self.finalise_instance_attributes() 1135 self.finalised = 1 1136 1137 def unfinalise_attributes(self): 1138 1139 "Open attribute definitions to editing and subsequent finalisation." 1140 1141 self.reset_caches() 1142 self.finalised = 0 1143 1144 # Convenience methods for accessing functions and methods. 1145 1146 def get_instantiator(self): 1147 1148 "Return a function which can be used to instantiate the class." 1149 1150 if self.instantiator is None: 1151 self.instantiator = self.get_init_method().as_instantiator() 1152 return self.instantiator 1153 1154 def get_init_method(self): 1155 return self.all_class_attributes()["__init__"].get_value() 1156 1157 # Class-specific methods. 1158 1159 def add_base(self, base): 1160 self.bases.append(base) 1161 base.add_descendant(self) 1162 1163 def add_instance_attribute(self, name): 1164 self.instattr.add(name) 1165 1166 def add_descendant(self, cls): 1167 self.descendants.add(cls) 1168 for base in self.bases: 1169 base.add_descendant(cls) 1170 1171 def has_subclass(self, other): 1172 return other in self.descendants 1173 1174 def all_descendants(self): 1175 d = {} 1176 for cls in self.descendants: 1177 d[cls.full_name()] = cls 1178 return d 1179 1180 "Return the attribute names provided by this class only." 1181 1182 class_attribute_names = NamespaceDict.keys 1183 1184 def class_attributes(self): 1185 1186 "Return class attributes provided by this class only." 1187 1188 return dict(self) 1189 1190 def all_class_attribute_names(self): 1191 1192 "Return the attribute names provided by classes in this hierarchy." 1193 1194 if self.all_classattr_names is None: 1195 self.all_class_attributes() 1196 self.all_classattr_names = self.all_classattr.keys() 1197 return self.all_classattr_names 1198 1199 def all_class_attributes(self): 1200 1201 "Return all class attributes, indicating the class which provides them." 1202 1203 self.finalise_class_attributes() 1204 return self.all_classattr 1205 1206 def finalise_class_attributes(self): 1207 1208 "Make sure that the class attributes are fully defined." 1209 1210 if self.all_classattr is None: 1211 self.all_classattr = {} 1212 clsattr = {} 1213 1214 # Record provisional position information for attributes of this 1215 # class. 1216 1217 for name in self.class_attributes().keys(): 1218 clsattr[name] = set() # position not yet defined 1219 1220 reversed_bases = self.bases[:] 1221 reversed_bases.reverse() 1222 1223 # For the bases in reverse order, acquire class attribute details. 1224 1225 for cls in reversed_bases: 1226 for name, attr in cls.all_class_attributes().items(): 1227 self.all_classattr[name] = attr 1228 1229 # Record previous attribute information. 1230 1231 if clsattr.has_key(name): 1232 clsattr[name].add(attr.position) 1233 1234 # Record class attributes provided by this class and its bases, 1235 # along with their positions. 1236 1237 self.all_classattr.update(self.class_attributes()) 1238 1239 if clsattr: 1240 for i, name in enumerate(self._get_position_list(clsattr)): 1241 self.all_classattr[name].position = i 1242 1243 return self.all_classattr 1244 1245 def instance_attribute_names(self): 1246 1247 "Return the instance attribute names provided by the class." 1248 1249 if self.all_instattr_names is None: 1250 self.instance_attributes() 1251 return self.all_instattr_names 1252 1253 def instance_attributes(self): 1254 1255 "Return instance-only attributes for instances of this class." 1256 1257 self.finalise_instance_attributes() 1258 return self.all_instattr 1259 1260 def finalise_instance_attributes(self): 1261 1262 "Make sure that the instance attributes are fully defined." 1263 1264 # Cache the attributes by converting the positioned attributes into a 1265 # dictionary. 1266 1267 if self.all_instattr is None: 1268 self.all_instattr = self._get_attributes() 1269 self.all_instattr_names = self.all_instattr.keys() 1270 1271 return self.all_instattr 1272 1273 def _get_attributes(self): 1274 1275 """ 1276 Return a dictionary mapping names to Attr instances incorporating 1277 information about their positions in the final instance structure. 1278 """ 1279 1280 instattr = {} 1281 1282 # Record provisional position information for attributes of this 1283 # instance. 1284 1285 for name in self.instattr: 1286 instattr[name] = set() # position not yet defined 1287 1288 reversed_bases = self.bases[:] 1289 reversed_bases.reverse() 1290 1291 # For the bases in reverse order, acquire instance attribute 1292 # details. 1293 1294 for cls in reversed_bases: 1295 for name, attr in cls.instance_attributes().items(): 1296 1297 # Record previous attribute information. 1298 1299 if instattr.has_key(name): 1300 instattr[name].add(attr.position) 1301 else: 1302 instattr[name] = set([attr.position]) 1303 1304 # Build the dictionary of attributes using the existing positions known 1305 # for each name. 1306 1307 d = {} 1308 for i, name in enumerate(self._get_position_list(instattr)): 1309 d[name] = Attr(i, Instance(), name) 1310 return d 1311 1312 def _get_position_list(self, positions): 1313 1314 """ 1315 Return a list of attribute names for the given 'positions' mapping from 1316 names to positions, indicating the positions of the attributes in the 1317 final instance structure. 1318 """ 1319 1320 position_items = positions.items() 1321 namearray = [None] * len(position_items) 1322 1323 # Get the positions in ascending order of list size, with lists 1324 # of the same size ordered according to their smallest position 1325 # value. 1326 1327 position_items.sort(self._cmp_positions) 1328 1329 # Get the names in position order. 1330 1331 held = [] 1332 1333 for name, pos in position_items: 1334 pos = list(pos) 1335 pos.sort() 1336 if pos and pos[0] < len(namearray) and namearray[pos[0]] is None: 1337 namearray[pos[0]] = name 1338 else: 1339 if pos: 1340 self.relocated.add(name) 1341 held.append((name, pos)) 1342 1343 for i, attr in enumerate(namearray): 1344 if attr is None: 1345 name, pos = held.pop() 1346 namearray[i] = name 1347 1348 return namearray 1349 1350 def _cmp_positions(self, a, b): 1351 1352 "Compare name plus position list operands 'a' and 'b'." 1353 1354 name_a, list_a = a 1355 name_b, list_b = b 1356 if len(list_a) < len(list_b): 1357 return -1 1358 elif len(list_a) > len(list_b): 1359 return 1 1360 elif not list_a: 1361 return 0 1362 else: 1363 return cmp(min(list_a), min(list_b)) 1364 1365 def all_attribute_names(self): 1366 1367 """ 1368 Return the names of all attributes provided by instances of this class. 1369 """ 1370 1371 self.allattr_names = self.allattr_names or self.all_attributes().keys() 1372 return self.allattr_names 1373 1374 def all_attributes(self): 1375 1376 """ 1377 Return all attributes for an instance, indicating either the class which 1378 provides them or that the instance itself provides them. 1379 """ 1380 1381 if self.allattr is None: 1382 self.allattr = {} 1383 self.allattr.update(self.all_class_attributes()) 1384 for name, attr in self.instance_attributes().items(): 1385 if self.allattr.has_key(name): 1386 print "Warning: instance attribute %r in %r overrides class attribute." % (name, self) 1387 self.allattr[name] = attr 1388 return self.allattr 1389 1390 class Function(NamespaceDict, Naming, Constant): 1391 1392 "An inspected function." 1393 1394 def __init__(self, name, parent, argnames, defaults, has_star, has_dstar, 1395 dynamic_def=0, module=None, node=None): 1396 1397 """ 1398 Initialise the function with the given 'name', 'parent', list of 1399 'argnames', list of 'defaults', the 'has_star' flag (indicating the 1400 presence of a * parameter), the 'has_dstar' flag (indicating the 1401 presence of a ** parameter), optional 'dynamic_def' (indicating that the 1402 function must be handled dynamically), optional 'module', and optional 1403 AST 'node'. 1404 """ 1405 1406 NamespaceDict.__init__(self, module) 1407 1408 if name is None: 1409 self.name = "lambda#%d" % new_lambda() 1410 self._is_lambda = 1 1411 else: 1412 self.name = name 1413 self._is_lambda = 0 1414 1415 self.parent = parent 1416 self.argnames = argnames 1417 self.defaults = defaults 1418 self.has_star = has_star 1419 self.has_dstar = has_dstar 1420 self.dynamic_def = dynamic_def 1421 self.astnode = node 1422 1423 # Initialise the positional names. 1424 1425 self.positional_names = self.argnames[:] 1426 if has_dstar: 1427 self.dstar_name = self.positional_names[-1] 1428 del self.positional_names[-1] 1429 if has_star: 1430 self.star_name = self.positional_names[-1] 1431 del self.positional_names[-1] 1432 1433 # Initialise default storage. 1434 # NOTE: This must be initialised separately due to the reliance on node 1435 # NOTE: visiting. 1436 1437 self.default_attrs = [] 1438 1439 # Initialise attribute usage. 1440 1441 if node is not None: 1442 for arg in argnames: 1443 1444 # Define attribute users. 1445 1446 self._define_attribute_user_for_name(node, arg) 1447 1448 # Caches. 1449 1450 self.localnames = None # cache for locals 1451 1452 # Add parameters to the namespace. 1453 1454 self._add_parameters(argnames) 1455 1456 # Image generation details. 1457 1458 self.dynamic = None 1459 self.location = None 1460 self.code_location = None 1461 self.code_body_location = None 1462 1463 # Program-related details. 1464 1465 self.blocks = None 1466 self.body_block = None 1467 1468 self.temp_usage = 0 1469 self.local_usage = 0 1470 self.all_local_usage = 0 1471 1472 def _add_parameters(self, argnames): 1473 1474 "Add 'argnames' to the namespace." 1475 1476 for name in argnames: 1477 self.set(name, Instance()) 1478 1479 for name, top_level in self._flattened_parameters(argnames): 1480 if not top_level: 1481 self.set(name, Instance()) 1482 1483 def _flattened_parameters(self, argnames, top_level=1): 1484 l = [] 1485 for name in argnames: 1486 if isinstance(name, tuple): 1487 l += self._flattened_parameters(name, 0) 1488 else: 1489 l.append((name, top_level)) 1490 return l 1491 1492 def __repr__(self): 1493 if self.location is not None: 1494 return "Function(%r, %s, %r, location=%r, code_location=%r)" % ( 1495 self.name, shortrepr(self.parent), self.argnames, self.location, self.code_location 1496 ) 1497 else: 1498 return "Function(%r, %s, %r)" % ( 1499 self.name, shortrepr(self.parent), self.argnames 1500 ) 1501 1502 def __shortrepr__(self): 1503 return "Function(%r, %s)" % ( 1504 self.name, shortrepr(self.parent) 1505 ) 1506 1507 def get_body_block(self): 1508 return self.body_block 1509 1510 def is_lambda(self): 1511 return self._is_lambda 1512 1513 # Defaults-related methods. 1514 1515 def store_default(self, attr_or_value): 1516 1517 """ 1518 Reserve space for defaults, set outside the function, potentially on a 1519 dynamic basis, using the 'attr_or_value'. 1520 """ 1521 1522 attr = Attr(None, self, None) 1523 self._set_using_attr(attr, attr_or_value) 1524 self.default_attrs.append(attr) 1525 1526 def make_dynamic(self): 1527 1528 "Return whether this function must be handled using a dynamic object." 1529 1530 if self.dynamic is None: 1531 for attr in self.default_attrs: 1532 if not attr.is_strict_constant() and self.dynamic_def: 1533 self.dynamic = 1 1534 self._make_dynamic() 1535 break 1536 else: 1537 self.dynamic = 0 1538 1539 return self.dynamic 1540 1541 is_dynamic = make_dynamic 1542 1543 def _make_dynamic(self): 1544 1545 "Where functions have dynamic defaults, add a context argument." 1546 1547 name = "<context>" 1548 self.argnames.insert(0, name) 1549 self.positional_names.insert(0, name) 1550 self.set(name, Instance()) 1551 1552 # Namespace-related methods. 1553 1554 def make_global(self, name): 1555 1556 "Declare 'name' as a global in the current namespace." 1557 1558 if name not in self.argnames and not self.has_key(name): 1559 self.globals.add(name) 1560 return 1 1561 else: 1562 return 0 1563 1564 def parameters(self): 1565 1566 """ 1567 Return a dictionary mapping parameter names to their position in the 1568 parameter list. 1569 """ 1570 1571 parameters = {} 1572 for i, name in enumerate(self.argnames): 1573 parameters[name] = i 1574 return parameters 1575 1576 def tuple_parameters(self, argnames=None): 1577 1578 """ 1579 Return a list of (position, parameter) entries corresponding to tuple 1580 parameters, where each parameter may either be a string or another such 1581 list of entries. 1582 """ 1583 1584 names = argnames or self.argnames 1585 1586 l = [] 1587 for i, name in enumerate(names): 1588 if isinstance(name, tuple): 1589 l.append((i, self.tuple_parameters(name))) 1590 elif argnames: 1591 l.append((i, name)) 1592 return l 1593 1594 def all_locals(self): 1595 1596 "Return a dictionary mapping names to local and parameter details." 1597 1598 return dict(self) 1599 1600 def locals(self): 1601 1602 "Return a dictionary mapping names to local details." 1603 1604 if self.localnames is None: 1605 self.localnames = {} 1606 self.localnames.update(self.all_locals()) 1607 for name in self.argnames: 1608 del self.localnames[name] 1609 return self.localnames 1610 1611 def is_method(self): 1612 1613 """ 1614 Return whether this function is a method explicitly defined in a class. 1615 """ 1616 1617 return isinstance(self.parent, Class) 1618 1619 def is_relocated(self, name): 1620 1621 """ 1622 Determine whether the given attribute 'name' is relocated for instances 1623 having this function as a method. 1624 """ 1625 1626 for cls in self.parent.descendants: 1627 if name in cls.relocated: 1628 return 1 1629 return 0 1630 1631 # Administrative methods. 1632 1633 def items_for_vacuum(self): 1634 return self.lambdas.items() 1635 1636 def vacuum_item(self, name): 1637 del self.lambdas[name] 1638 1639 def finalise_attributes(self): 1640 1641 """ 1642 Make sure all attributes (locals) are fully defined. Note that locals 1643 are not attributes in the sense of class, module or instance attributes. 1644 Defaults are also finalised by this method. 1645 """ 1646 1647 if self.finalised: 1648 return 1649 1650 # Defaults. 1651 1652 for i, default in enumerate(self.default_attrs): 1653 default.position = i 1654 1655 # Parameters. 1656 1657 i = self._finalise_parameters() 1658 1659 if i is not None: 1660 nparams = i + 1 1661 else: 1662 nparams = 0 1663 1664 # Locals (and tuple parameter names). 1665 1666 i = None 1667 for i, attr in enumerate(self.locals().values()): 1668 attr.position = i + nparams 1669 1670 if i is not None: 1671 nothers = i + 1 1672 else: 1673 nothers = 0 1674 1675 self.local_usage = nothers 1676 self.all_local_usage = nparams + nothers 1677 self.finalised = 1 1678 1679 def _finalise_parameters(self): 1680 if not self.argnames: 1681 return None 1682 1683 for i, name in enumerate(self.argnames): 1684 self[name].position = i 1685 1686 return i 1687 1688 def as_instantiator(self): 1689 1690 "Make an instantiator function from a method, keeping all arguments." 1691 1692 function = Function(self.parent.name, self.parent.parent, self.argnames, self.defaults, 1693 self.has_star, self.has_dstar, self.dynamic_def, self.module) 1694 function.default_attrs = self.default_attrs 1695 return function 1696 1697 class UnresolvedName(NamespaceDict, Constant): 1698 1699 "A module, class or function which was mentioned but could not be imported." 1700 1701 def __init__(self, name, parent_name, module=None): 1702 NamespaceDict.__init__(self, module) 1703 self.name = name 1704 self.parent_name = parent_name 1705 self.parent = None 1706 1707 self.descendants = set() 1708 1709 def add_descendant(self, cls): 1710 self.descendants.add(cls) 1711 1712 def all_attributes(self): 1713 return {} 1714 1715 def all_attribute_names(self): 1716 return [] 1717 1718 all_class_attributes = class_attributes = instance_attributes = all_attributes 1719 all_class_attribute_names = class_attribute_names = instance_attribute_names = all_attribute_names 1720 1721 def __repr__(self): 1722 return "UnresolvedName(%r, %r)" % (self.name, self.parent_name) 1723 1724 __shortrepr__ = __repr__ 1725 1726 def full_name(self): 1727 if self.name is not None: 1728 return self.parent_name + "." + self.name 1729 else: 1730 return self.parent_name 1731 1732 class Module(NamespaceDict, Constant): 1733 1734 "An inspected module's core details." 1735 1736 def __init__(self, name, importer): 1737 NamespaceDict.__init__(self, self) 1738 self.name = name 1739 self.importer = importer 1740 self.parent = None 1741 1742 # Original location details. 1743 1744 self.astnode = None 1745 1746 # Complete lists of classes and functions. 1747 1748 self.all_objects = set() 1749 1750 # Keyword records. 1751 1752 self.keyword_names = set() 1753 1754 # Image generation details. 1755 1756 self.location = None 1757 self.code_location = None 1758 1759 # Program-related details. 1760 1761 self.blocks = None 1762 self.temp_usage = 0 1763 self.local_usage = 0 1764 self.all_local_usage = 0 1765 1766 def full_name(self): 1767 return self.name 1768 1769 def __repr__(self): 1770 if self.location is not None: 1771 return "Module(%r, location=%r)" % (self.name, self.location) 1772 else: 1773 return "Module(%r)" % self.name 1774 1775 def __shortrepr__(self): 1776 return "Module(%r)" % self.name 1777 1778 # Attribute methods. 1779 1780 "Return the module attribute names provided by the module." 1781 1782 module_attribute_names = NamespaceDict.keys 1783 1784 def module_attributes(self): 1785 1786 "Return a dictionary mapping names to module attributes." 1787 1788 return dict(self) 1789 1790 # vim: tabstop=4 expandtab shiftwidth=4