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