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 for users in (self.attribute_users[-1], self.loop_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 432 users = self.attribute_users[-1] 433 434 if users.has_key(name): 435 return users[name] 436 else: 437 return [] 438 439 def _define_attribute_user(self, node): 440 441 """ 442 Define 'node' as the user of attributes, indicating the point where the 443 user is defined. 444 """ 445 446 name = node.name 447 self._define_attribute_user_for_name(node, name) 448 449 def _define_attribute_user_for_name(self, node, name): 450 451 "Define 'node' as the user of attributes for the given 'name'." 452 453 users = self.attribute_users[-1] 454 455 # This node overrides previous definitions. 456 457 users[name] = set([node]) 458 459 # Record the attribute combinations for the name. 460 461 self._init_attribute_user_for_name(node, name) 462 463 # Propagate any loop usage forward to any redefinition of a name. 464 465 loop_users = self.loop_users[-1] 466 467 if loop_users.has_key(name): 468 for loop_user in loop_users[name]: 469 node._attrnames[name].update(loop_user._attrnames[name]) 470 del loop_users[name] 471 472 # Remember this user. 473 474 self.all_attribute_users.add(node) 475 476 def _init_attribute_user_for_name(self, node, name): 477 478 "Make sure that 'node' is initialised for 'name'." 479 480 if not hasattr(node, "_attrnames"): 481 node._attrnames = {} 482 483 node._attrnames[name] = set() 484 485 # Branch management methods. 486 487 def _new_branchpoint(self): 488 489 """ 490 Establish a new branchpoint where several control-flow branches diverge 491 and subsequently converge. 492 """ 493 494 self.user_shelves.append([]) 495 self.scope_shelves.append([]) 496 497 def _new_branch(self, loop_node=None): 498 499 """ 500 Establish a new control-flow branch, transferring attribute usage to 501 the new branch so that it may be augmented for each name locally. 502 503 If the optional 'loop_node' is given, add it as an active user to be 504 informed of attribute usage. 505 """ 506 507 # Retain a record of active users. 508 509 new_users = {} 510 new_users.update(self.attribute_users[-1]) 511 self.attribute_users.append(new_users) 512 513 # Where a loop is the cause of the branch, register the loop node as a 514 # user of each name so that attribute usage is also recorded for the 515 # loop. 516 517 loop_users = {} 518 loop_users.update(self.loop_users[-1]) 519 self.loop_users.append(loop_users) 520 521 if loop_node is not None: 522 for name in new_users.keys(): 523 if not loop_users.has_key(name): 524 loop_users[name] = set([loop_node]) 525 else: 526 loop_users[name] = loop_users[name].union([loop_node]) 527 self._init_attribute_user_for_name(loop_node, name) 528 529 # Retain a record of scope usage. 530 531 scope_usage = {} 532 scope_usage.update(self.scope_usage[-1]) 533 self.scope_usage.append(scope_usage) 534 535 def _abandon_branch(self): 536 537 """ 538 Abandon scope usage, permitting locally different scopes for names, 539 provided these cannot "escape" from the branch. 540 """ 541 542 self.scope_usage[-1] = AbandonedBranchScope() 543 544 def _shelve_branch(self): 545 546 """ 547 Shelve the current control-flow branch, recording the attribute usage 548 for subsequent merging. If this branch should be abandoned, the usage 549 observations are still recorded but will not contribute to subsequent 550 observations after a merge. 551 """ 552 553 users = self.attribute_users.pop() 554 self.user_shelves[-1].append(users) 555 556 scope_usage = self.scope_usage.pop() 557 self.scope_shelves[-1].append(scope_usage) 558 559 def _merge_branches(self): 560 561 """ 562 Merge control-flow branches. This should find the users active within 563 each branch, which have been "shelved", and update the active users 564 dictionary with these contributions. 565 """ 566 567 # Combine the attribute users. This ensures that a list of users 568 # affected by attribute usage is maintained for the current branch. 569 570 users = self.attribute_users[-1] 571 new_users = {} 572 573 all_shelved_users = self.user_shelves.pop() 574 all_user_names = set() 575 576 # Find all the names defined by the branches. 577 578 for shelved_users in all_shelved_users: 579 all_user_names.update(shelved_users.keys()) 580 581 # Copy all definitions from the branches for the names, maintaining 582 # the existing users where a branch does not redefine a name. 583 584 for shelved_users in all_shelved_users: 585 for name in all_user_names: 586 587 if shelved_users.has_key(name): 588 nodes = shelved_users[name] 589 else: 590 nodes = users.get(name, set()) 591 592 if nodes: 593 if not new_users.has_key(name): 594 new_users[name] = set(nodes) 595 else: 596 new_users[name].update(nodes) 597 598 self.attribute_users[-1] = new_users 599 600 # Combine the scope usage. 601 602 scope_usage = self.scope_usage[-1] 603 new_scope_usage = {} 604 605 all_scope_usage = self.scope_shelves.pop() 606 all_scope_names = set() 607 608 # Find all the names for whom scope information has been defined. 609 610 for shelved_usage in all_scope_usage: 611 all_scope_names.update(shelved_usage.keys()) 612 613 for shelved_usage in all_scope_usage: 614 for name in all_scope_names: 615 616 # Find the recorded scope for the name. 617 618 if shelved_usage.has_key(name): 619 scope = shelved_usage[name] 620 elif scope_usage.has_key(name): 621 scope = scope_usage[name] 622 623 # For abandoned branches, no scope is asserted for a name. 624 625 elif isinstance(shelved_usage, AbandonedBranchScope): 626 scope = None 627 628 # If no scope is recorded, find a suitable external source. 629 630 else: 631 attr, scope, full_name = self._get_with_scope(name, external=1) 632 633 # Attempt to record the scope, testing for conflicts. 634 635 if scope: 636 if not new_scope_usage.has_key(name): 637 new_scope_usage[name] = scope 638 elif new_scope_usage[name] != scope: 639 new_scope_usage[name] = ScopeConflict(scope, new_scope_usage[name]) 640 641 self.scope_usage[-1] = new_scope_usage 642 643 # Scope usage methods. 644 645 def define_scope(self, name, scope): 646 647 """ 648 Define 'name' as being from the given 'scope' in the current namespace. 649 """ 650 651 self.scope_usage[-1][name] = scope 652 653 def note_scope(self, name, scope): 654 655 """ 656 Note usage of 'name' from the given 'scope' in the current namespace. 657 If a conflict has been recorded previously, raise an exception. 658 """ 659 660 scope_usage = self.scope_usage[-1] 661 662 if scope_usage.has_key(name): 663 found_scope = scope_usage[name] 664 if isinstance(found_scope, ScopeConflict): 665 raise InspectError("Scope conflict for %r: defined as both %s and %s." % ( 666 name, found_scope.old_scope, found_scope.new_scope)) 667 668 scope_usage[name] = scope 669 670 def used_in_scope(self, name, scope): 671 672 """ 673 Return whether 'name' is used from the given 'scope' in the current 674 namespace. 675 """ 676 677 scope_usage = self.scope_usage[-1] 678 return scope_usage.get(name) == scope 679 680 # Special helper classes for scope resolution. 681 682 class AbandonedBranchScope: 683 684 """ 685 A class providing a value or state for an abandoned branch distinct from an 686 empty scope dictionary. 687 """ 688 689 def has_key(self, name): 690 return 0 691 692 def __setitem__(self, name, value): 693 pass 694 695 def __getitem__(self, name): 696 raise KeyError, name 697 698 def get(self, name, default=None): 699 return default 700 701 def keys(self): 702 return [] 703 704 values = items = keys 705 706 class ScopeConflict: 707 708 """ 709 A scope conflict caused when different code branches contribute different 710 sources of names. 711 """ 712 713 def __init__(self, old_scope, new_scope): 714 self.old_scope = old_scope 715 self.new_scope = new_scope 716 717 # Program data structures. 718 719 class Attr: 720 721 "An attribute entry having a context." 722 723 def __init__(self, position, parent, name): 724 725 """ 726 Initialise the attribute with the given 'position' within the collection 727 of attributes of its 'parent', indicating its 'name'. 728 """ 729 730 self.position = position 731 self.parent = parent 732 self.name = name 733 734 # Possible values. 735 736 self.context_values = set() 737 738 # Number of assignments per name. 739 740 self.assignments = None 741 742 # Value-related methods. 743 744 def get_contexts(self): 745 return [c for (c, v) in self.context_values] 746 747 def get_values(self): 748 return [v for (c, v) in self.context_values] 749 750 def get_context(self): 751 if len(self.context_values) == 1: 752 return self.get_contexts()[0] 753 else: 754 return None 755 756 def get_value(self): 757 if len(self.context_values) == 1: 758 return self.get_values()[0] 759 else: 760 return None 761 762 def update(self, context_values, single_assignment): 763 764 """ 765 Update the attribute, adding the 'context_values' provided to the 766 known details associated with the attribute, changing the number of 767 assignments according to the 'single_assignment' status of the 768 operation, where a true value indicates that only one assignment is 769 associated with the update, and a false value indicates that potentially 770 many assignments may be involved. 771 """ 772 773 if self.assignments is None: 774 if single_assignment: 775 self.assignments = 1 776 else: 777 self.assignments = AtLeast(1) 778 else: 779 if single_assignment: 780 self.assignments += 1 781 else: 782 self.assignments += AtLeast(1) 783 784 self.context_values.update(context_values) 785 786 def is_constant(self): 787 788 """ 789 Return whether this attribute references something that can be regarded 790 as being constant within a particular scope. 791 """ 792 793 return self.assignments == 1 794 795 def is_strict_constant(self): 796 797 """ 798 Return whether this attribute references something that can be regarded 799 as being constant. 800 """ 801 802 value = self.get_value() 803 return not (value is None or isinstance(value, Instance)) 804 805 def is_static_attribute(self): 806 807 """ 808 Return whether this attribute is defined on a fixed/static object such 809 as a class or a module. 810 """ 811 812 return isinstance(self.parent, (Class, Module)) 813 814 def defines_ambiguous_class(self): 815 816 "Return whether this attribute defines more than one class." 817 818 if self.assignments > 1: 819 have_class = 0 820 for obj in self.get_values(): 821 if isinstance(obj, Class): 822 if have_class: 823 return 1 824 have_class = 1 825 826 return 0 827 828 def defined_within_hierarchy(self): 829 830 """ 831 Return whether the parent and context of the attribute belong to the 832 same class hierarchy. 833 """ 834 835 # Must be defined within a class. 836 837 if isinstance(self.parent, Class): 838 839 # To be sure, all contexts must be classes and be the same as the 840 # parent, or be a superclass of the parent, or be a subclass of the 841 # parent. 842 843 for context in self.get_contexts(): 844 if not ( 845 isinstance(context, Class) and ( 846 context is self.parent or 847 context.has_subclass(self.parent) or 848 self.parent.has_subclass(context)) 849 ): 850 return 0 851 852 return 1 853 854 # Instance attributes are not defined within a hierarchy. 855 856 else: 857 return 0 858 859 def defined_outside_hierarchy(self): 860 861 """ 862 Return whether the parent and context of the attribute never belong to 863 the same class hierarchy. 864 """ 865 866 # Must be defined within a class. 867 868 if isinstance(self.parent, Class): 869 870 # To be sure, all contexts must be classes and be the same as the 871 # parent, or be a superclass of the parent, or be a subclass of the 872 # parent. 873 874 for context in self.get_contexts(): 875 if not ( 876 isinstance(context, Class) and not ( 877 context is self.parent or 878 context.has_subclass(self.parent) or 879 self.parent.has_subclass(context)) 880 ): 881 return 0 882 883 return 1 884 885 # Instance attributes are not defined within a hierarchy. 886 887 else: 888 return 0 889 890 def __repr__(self): 891 return "Attr(%r, %s, %r) # {[%s] (%r)}" % ( 892 self.position, shortrepr(self.parent), self.name, 893 self._context_values_str(), self.assignments 894 ) 895 896 def __shortrepr__(self): 897 return "Attr(%r, %s, %r)" % ( 898 self.position, shortrepr(self.parent), self.name 899 ) 900 901 def _context_values_str(self): 902 l = [] 903 for (c, v) in self.context_values: 904 l.append("(c=%s, v=%s)" % (shortrepr(c), shortrepr(v))) 905 return ", ".join(l) 906 907 # Instances are special in that they need to be wrapped together with context in 908 # a running program, but they are not generally constant. 909 910 class Instance: 911 912 "A placeholder indicating the involvement of an instance." 913 914 def __init__(self): 915 self.parent = None 916 917 # Image generation details. 918 919 self.location = None 920 921 def __repr__(self): 922 return "Instance()" 923 924 __shortrepr__ = __repr__ 925 926 class Constant: 927 928 "A superclass for all constant or context-free structures." 929 930 pass 931 932 # Data objects appearing in programs before run-time. 933 934 class Const(Constant, Instance): 935 936 "A constant object with no context." 937 938 def __init__(self, value): 939 Instance.__init__(self) 940 self.value = value 941 942 def get_value(self): 943 return self.value 944 945 def __repr__(self): 946 if self.location is not None: 947 return "Const(%r, location=%r)" % (self.value, self.location) 948 else: 949 return "Const(%r)" % self.value 950 951 __shortrepr__ = __repr__ 952 953 # Support constants as dictionary keys in order to build constant tables. 954 955 def __eq__(self, other): 956 return other is not None and self.value == other.value and self.value.__class__ is other.value.__class__ 957 958 def __hash__(self): 959 return hash(self.value) 960 961 def value_type_name(self): 962 return "__builtins__." + self.value.__class__.__name__ 963 964 class Class(NamespaceDict, Naming, Constant): 965 966 "An inspected class." 967 968 def __init__(self, name, parent, module=None, node=None): 969 970 """ 971 Initialise the class with the given 'name', 'parent' object, optional 972 'module' and optional AST 'node'. 973 """ 974 975 NamespaceDict.__init__(self, module) 976 self.name = name 977 self.parent = parent 978 self.astnode = node 979 980 # Superclasses, descendants and attributes. 981 982 self.bases = [] 983 self.descendants = set() 984 self.instattr = set() # instance attributes 985 self.relocated = set() # attributes which do not have the same 986 # position as those of the same name in 987 # some superclasses 988 989 # Caches. 990 991 self.reset_caches() 992 993 # Image generation details. 994 995 self.location = None 996 self.code_location = None 997 self.code_body_location = None # corresponds to the instantiator 998 999 self.instantiator = None 1000 self.instance_template_location = None # for creating instances at run-time 1001 1002 # Program-related details. 1003 1004 self.blocks = None 1005 self.temp_usage = 0 1006 self.local_usage = 0 1007 self.all_local_usage = 0 1008 1009 # Add this class to its attributes. 1010 1011 self.set("__class__", self) 1012 1013 def reset_caches(self): 1014 1015 "Reset the caches." 1016 1017 self.all_instattr = None # cache for instance_attributes 1018 self.all_instattr_names = None # from all_instattr 1019 self.all_classattr = None # cache for all_class_attributes 1020 self.all_classattr_names = None # from all_classattr 1021 self.allattr = None # cache for all_attributes 1022 self.allattr_names = None # from allattr 1023 1024 def __repr__(self): 1025 if self.location is not None: 1026 return "Class(%r, %s, location=%r)" % (self.name, shortrepr(self.parent), self.location) 1027 else: 1028 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 1029 1030 def __shortrepr__(self): 1031 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 1032 1033 def get_body_block(self): 1034 return self.get_instantiator().blocks[0] 1035 1036 # Namespace-related methods. 1037 1038 def get_updated_context_values(self, context_values): 1039 1040 """ 1041 Adapt the contexts found in the given 'context_values', returning a new 1042 set. 1043 See: docs/assignment.txt 1044 """ 1045 1046 results = set() 1047 1048 for context, value in context_values: 1049 1050 # Change the ownership of functions. 1051 1052 if context is ReplaceableContext and value is not None and isinstance(value, Function): 1053 results.add((self, value)) 1054 else: 1055 results.add((context, value)) 1056 1057 return NamespaceDict.get_updated_context_values(self, results) 1058 1059 # Administrative methods. 1060 1061 def finalise_attributes(self): 1062 1063 "Make sure that all attributes are fully defined." 1064 1065 if self.finalised: 1066 return 1067 1068 self.finalise_class_attributes() 1069 self.finalise_instance_attributes() 1070 self.finalised = 1 1071 1072 def unfinalise_attributes(self): 1073 1074 "Open attribute definitions to editing and subsequent finalisation." 1075 1076 self.reset_caches() 1077 self.finalised = 0 1078 1079 # Convenience methods for accessing functions and methods. 1080 1081 def get_instantiator(self): 1082 1083 "Return a function which can be used to instantiate the class." 1084 1085 if self.instantiator is None: 1086 self.instantiator = self.get_init_method().as_instantiator() 1087 return self.instantiator 1088 1089 def get_init_method(self): 1090 return self.all_class_attributes()["__init__"].get_value() 1091 1092 # Class-specific methods. 1093 1094 def add_base(self, base): 1095 self.bases.append(base) 1096 base.add_descendant(self) 1097 1098 def add_instance_attribute(self, name): 1099 self.instattr.add(name) 1100 1101 def add_descendant(self, cls): 1102 self.descendants.add(cls) 1103 for base in self.bases: 1104 base.add_descendant(cls) 1105 1106 def has_subclass(self, other): 1107 return other in self.descendants 1108 1109 def all_descendants(self): 1110 d = {} 1111 for cls in self.descendants: 1112 d[cls.full_name()] = cls 1113 return d 1114 1115 "Return the attribute names provided by this class only." 1116 1117 class_attribute_names = NamespaceDict.keys 1118 1119 def class_attributes(self): 1120 1121 "Return class attributes provided by this class only." 1122 1123 return dict(self) 1124 1125 def all_class_attribute_names(self): 1126 1127 "Return the attribute names provided by classes in this hierarchy." 1128 1129 if self.all_classattr_names is None: 1130 self.all_class_attributes() 1131 self.all_classattr_names = self.all_classattr.keys() 1132 return self.all_classattr_names 1133 1134 def all_class_attributes(self): 1135 1136 "Return all class attributes, indicating the class which provides them." 1137 1138 self.finalise_class_attributes() 1139 return self.all_classattr 1140 1141 def finalise_class_attributes(self): 1142 1143 "Make sure that the class attributes are fully defined." 1144 1145 if self.all_classattr is None: 1146 self.all_classattr = {} 1147 clsattr = {} 1148 1149 # Record provisional position information for attributes of this 1150 # class. 1151 1152 for name in self.class_attributes().keys(): 1153 clsattr[name] = set() # position not yet defined 1154 1155 reversed_bases = self.bases[:] 1156 reversed_bases.reverse() 1157 1158 # For the bases in reverse order, acquire class attribute details. 1159 1160 for cls in reversed_bases: 1161 for name, attr in cls.all_class_attributes().items(): 1162 self.all_classattr[name] = attr 1163 1164 # Record previous attribute information. 1165 1166 if clsattr.has_key(name): 1167 clsattr[name].add(attr.position) 1168 1169 # Record class attributes provided by this class and its bases, 1170 # along with their positions. 1171 1172 self.all_classattr.update(self.class_attributes()) 1173 1174 if clsattr: 1175 for i, name in enumerate(self._get_position_list(clsattr)): 1176 self.all_classattr[name].position = i 1177 1178 return self.all_classattr 1179 1180 def instance_attribute_names(self): 1181 1182 "Return the instance attribute names provided by the class." 1183 1184 if self.all_instattr_names is None: 1185 self.instance_attributes() 1186 return self.all_instattr_names 1187 1188 def instance_attributes(self): 1189 1190 "Return instance-only attributes for instances of this class." 1191 1192 self.finalise_instance_attributes() 1193 return self.all_instattr 1194 1195 def finalise_instance_attributes(self): 1196 1197 "Make sure that the instance attributes are fully defined." 1198 1199 # Cache the attributes by converting the positioned attributes into a 1200 # dictionary. 1201 1202 if self.all_instattr is None: 1203 self.all_instattr = self._get_attributes() 1204 self.all_instattr_names = self.all_instattr.keys() 1205 1206 return self.all_instattr 1207 1208 def _get_attributes(self): 1209 1210 """ 1211 Return a dictionary mapping names to Attr instances incorporating 1212 information about their positions in the final instance structure. 1213 """ 1214 1215 instattr = {} 1216 1217 # Record provisional position information for attributes of this 1218 # instance. 1219 1220 for name in self.instattr: 1221 instattr[name] = set() # position not yet defined 1222 1223 reversed_bases = self.bases[:] 1224 reversed_bases.reverse() 1225 1226 # For the bases in reverse order, acquire instance attribute 1227 # details. 1228 1229 for cls in reversed_bases: 1230 for name, attr in cls.instance_attributes().items(): 1231 1232 # Record previous attribute information. 1233 1234 if instattr.has_key(name): 1235 instattr[name].add(attr.position) 1236 else: 1237 instattr[name] = set([attr.position]) 1238 1239 # Build the dictionary of attributes using the existing positions known 1240 # for each name. 1241 1242 d = {} 1243 for i, name in enumerate(self._get_position_list(instattr)): 1244 d[name] = Attr(i, Instance(), name) 1245 return d 1246 1247 def _get_position_list(self, positions): 1248 1249 """ 1250 Return a list of attribute names for the given 'positions' mapping from 1251 names to positions, indicating the positions of the attributes in the 1252 final instance structure. 1253 """ 1254 1255 position_items = positions.items() 1256 namearray = [None] * len(position_items) 1257 1258 # Get the positions in ascending order of list size, with lists 1259 # of the same size ordered according to their smallest position 1260 # value. 1261 1262 position_items.sort(self._cmp_positions) 1263 1264 # Get the names in position order. 1265 1266 held = [] 1267 1268 for name, pos in position_items: 1269 pos = list(pos) 1270 pos.sort() 1271 if pos and pos[0] < len(namearray) and namearray[pos[0]] is None: 1272 namearray[pos[0]] = name 1273 else: 1274 if pos: 1275 self.relocated.add(name) 1276 held.append((name, pos)) 1277 1278 for i, attr in enumerate(namearray): 1279 if attr is None: 1280 name, pos = held.pop() 1281 namearray[i] = name 1282 1283 return namearray 1284 1285 def _cmp_positions(self, a, b): 1286 1287 "Compare name plus position list operands 'a' and 'b'." 1288 1289 name_a, list_a = a 1290 name_b, list_b = b 1291 if len(list_a) < len(list_b): 1292 return -1 1293 elif len(list_a) > len(list_b): 1294 return 1 1295 elif not list_a: 1296 return 0 1297 else: 1298 return cmp(min(list_a), min(list_b)) 1299 1300 def all_attribute_names(self): 1301 1302 """ 1303 Return the names of all attributes provided by instances of this class. 1304 """ 1305 1306 self.allattr_names = self.allattr_names or self.all_attributes().keys() 1307 return self.allattr_names 1308 1309 def all_attributes(self): 1310 1311 """ 1312 Return all attributes for an instance, indicating either the class which 1313 provides them or that the instance itself provides them. 1314 """ 1315 1316 if self.allattr is None: 1317 self.allattr = {} 1318 self.allattr.update(self.all_class_attributes()) 1319 for name, attr in self.instance_attributes().items(): 1320 if self.allattr.has_key(name): 1321 print "Warning: instance attribute %r in %r overrides class attribute." % (name, self) 1322 self.allattr[name] = attr 1323 return self.allattr 1324 1325 class Function(NamespaceDict, Naming, Constant): 1326 1327 "An inspected function." 1328 1329 def __init__(self, name, parent, argnames, defaults, has_star, has_dstar, 1330 dynamic_def=0, module=None, node=None): 1331 1332 """ 1333 Initialise the function with the given 'name', 'parent', list of 1334 'argnames', list of 'defaults', the 'has_star' flag (indicating the 1335 presence of a * parameter), the 'has_dstar' flag (indicating the 1336 presence of a ** parameter), optional 'dynamic_def' (indicating that the 1337 function must be handled dynamically), optional 'module', and optional 1338 AST 'node'. 1339 """ 1340 1341 NamespaceDict.__init__(self, module) 1342 1343 if name is None: 1344 self.name = "lambda#%d" % new_lambda() 1345 self._is_lambda = 1 1346 else: 1347 self.name = name 1348 self._is_lambda = 0 1349 1350 self.parent = parent 1351 self.argnames = argnames 1352 self.defaults = defaults 1353 self.has_star = has_star 1354 self.has_dstar = has_dstar 1355 self.dynamic_def = dynamic_def 1356 self.astnode = node 1357 1358 # Initialise the positional names. 1359 1360 self.positional_names = self.argnames[:] 1361 if has_dstar: 1362 self.dstar_name = self.positional_names[-1] 1363 del self.positional_names[-1] 1364 if has_star: 1365 self.star_name = self.positional_names[-1] 1366 del self.positional_names[-1] 1367 1368 # Initialise default storage. 1369 # NOTE: This must be initialised separately due to the reliance on node 1370 # NOTE: visiting. 1371 1372 self.default_attrs = [] 1373 1374 # Initialise attribute usage. 1375 1376 if node is not None: 1377 for arg in argnames: 1378 1379 # Define attribute users. 1380 1381 self._define_attribute_user_for_name(node, arg) 1382 1383 # Caches. 1384 1385 self.localnames = None # cache for locals 1386 1387 # Add parameters to the namespace. 1388 1389 self._add_parameters(argnames) 1390 1391 # Image generation details. 1392 1393 self.dynamic = None 1394 self.location = None 1395 self.code_location = None 1396 self.code_body_location = None 1397 1398 # Program-related details. 1399 1400 self.blocks = None 1401 self.body_block = None 1402 1403 self.temp_usage = 0 1404 self.local_usage = 0 1405 self.all_local_usage = 0 1406 1407 def _add_parameters(self, argnames): 1408 for name in argnames: 1409 if isinstance(name, tuple): 1410 self._add_parameters(name) 1411 else: 1412 self.set(name, Instance()) 1413 1414 def __repr__(self): 1415 if self.location is not None: 1416 return "Function(%r, %s, %r, location=%r, code_location=%r)" % ( 1417 self.name, shortrepr(self.parent), self.argnames, self.location, self.code_location 1418 ) 1419 else: 1420 return "Function(%r, %s, %r)" % ( 1421 self.name, shortrepr(self.parent), self.argnames 1422 ) 1423 1424 def __shortrepr__(self): 1425 return "Function(%r, %s)" % ( 1426 self.name, shortrepr(self.parent) 1427 ) 1428 1429 def get_body_block(self): 1430 return self.body_block 1431 1432 def is_lambda(self): 1433 return self._is_lambda 1434 1435 # Defaults-related methods. 1436 1437 def store_default(self, attr_or_value): 1438 1439 """ 1440 Reserve space for defaults, set outside the function, potentially on a 1441 dynamic basis, using the 'attr_or_value'. 1442 """ 1443 1444 attr = Attr(None, self, None) 1445 self._set_using_attr(attr, attr_or_value) 1446 self.default_attrs.append(attr) 1447 1448 def make_dynamic(self): 1449 1450 "Return whether this function must be handled using a dynamic object." 1451 1452 if self.dynamic is None: 1453 for attr in self.default_attrs: 1454 if not attr.is_strict_constant() and self.dynamic_def: 1455 self.dynamic = 1 1456 self._make_dynamic() 1457 break 1458 else: 1459 self.dynamic = 0 1460 1461 return self.dynamic 1462 1463 is_dynamic = make_dynamic 1464 1465 def _make_dynamic(self): 1466 1467 "Where functions have dynamic defaults, add a context argument." 1468 1469 name = "<context>" 1470 self.argnames.insert(0, name) 1471 self.positional_names.insert(0, name) 1472 self.set(name, Instance()) 1473 1474 # Namespace-related methods. 1475 1476 def make_global(self, name): 1477 1478 "Declare 'name' as a global in the current namespace." 1479 1480 if name not in self.argnames and not self.has_key(name): 1481 self.globals.add(name) 1482 return 1 1483 else: 1484 return 0 1485 1486 def parameters(self): 1487 1488 """ 1489 Return a dictionary mapping parameter names to their position in the 1490 parameter list. 1491 """ 1492 1493 parameters = {} 1494 for i, name in enumerate(self.argnames): 1495 parameters[name] = i 1496 return parameters 1497 1498 def all_locals(self): 1499 1500 "Return a dictionary mapping names to local and parameter details." 1501 1502 return dict(self) 1503 1504 def locals(self): 1505 1506 "Return a dictionary mapping names to local details." 1507 1508 if self.localnames is None: 1509 self.localnames = {} 1510 self.localnames.update(self.all_locals()) 1511 for name in self.argnames: 1512 del self.localnames[name] 1513 return self.localnames 1514 1515 def is_method(self): 1516 1517 """ 1518 Return whether this function is a method explicitly defined in a class. 1519 """ 1520 1521 return isinstance(self.parent, Class) 1522 1523 def is_relocated(self, name): 1524 1525 """ 1526 Determine whether the given attribute 'name' is relocated for instances 1527 having this function as a method. 1528 """ 1529 1530 for cls in self.parent.descendants: 1531 if name in cls.relocated: 1532 return 1 1533 return 0 1534 1535 # Administrative methods. 1536 1537 def items_for_vacuum(self): 1538 return self.lambdas.items() 1539 1540 def vacuum_item(self, name): 1541 del self.lambdas[name] 1542 1543 def finalise_attributes(self): 1544 1545 """ 1546 Make sure all attributes (locals) are fully defined. Note that locals 1547 are not attributes in the sense of class, module or instance attributes. 1548 Defaults are also finalised by this method. 1549 """ 1550 1551 if self.finalised: 1552 return 1553 1554 # Defaults. 1555 1556 for i, default in enumerate(self.default_attrs): 1557 default.position = i 1558 1559 # Locals. 1560 1561 i = None 1562 for i, name in enumerate(self.argnames): 1563 self[name].position = i 1564 1565 if i is not None: 1566 nparams = i + 1 1567 else: 1568 nparams = 0 1569 1570 i = None 1571 for i, attr in enumerate(self.locals().values()): 1572 attr.position = i + nparams 1573 1574 if i is not None: 1575 nothers = i + 1 1576 else: 1577 nothers = 0 1578 1579 self.local_usage = nothers 1580 self.all_local_usage = nparams + nothers 1581 self.finalised = 1 1582 1583 def as_instantiator(self): 1584 1585 "Make an instantiator function from a method, keeping all arguments." 1586 1587 function = Function(self.parent.name, self.parent.parent, self.argnames, self.defaults, 1588 self.has_star, self.has_dstar, self.dynamic_def, self.module) 1589 function.default_attrs = self.default_attrs 1590 return function 1591 1592 class UnresolvedName(NamespaceDict, Constant): 1593 1594 "A module, class or function which was mentioned but could not be imported." 1595 1596 def __init__(self, name, parent_name, module=None): 1597 NamespaceDict.__init__(self, module) 1598 self.name = name 1599 self.parent_name = parent_name 1600 self.parent = None 1601 1602 self.descendants = set() 1603 1604 def add_descendant(self, cls): 1605 self.descendants.add(cls) 1606 1607 def all_attributes(self): 1608 return {} 1609 1610 def all_attribute_names(self): 1611 return [] 1612 1613 all_class_attributes = class_attributes = instance_attributes = all_attributes 1614 all_class_attribute_names = class_attribute_names = instance_attribute_names = all_attribute_names 1615 1616 def __repr__(self): 1617 return "UnresolvedName(%r, %r)" % (self.name, self.parent_name) 1618 1619 __shortrepr__ = __repr__ 1620 1621 def full_name(self): 1622 if self.name is not None: 1623 return self.parent_name + "." + self.name 1624 else: 1625 return self.parent_name 1626 1627 class Module(NamespaceDict, Constant): 1628 1629 "An inspected module's core details." 1630 1631 def __init__(self, name, importer): 1632 NamespaceDict.__init__(self, self) 1633 self.name = name 1634 self.importer = importer 1635 self.parent = None 1636 1637 # Original location details. 1638 1639 self.astnode = None 1640 1641 # Complete lists of classes and functions. 1642 1643 self.all_objects = set() 1644 1645 # Keyword records. 1646 1647 self.keyword_names = set() 1648 1649 # Image generation details. 1650 1651 self.location = None 1652 self.code_location = None 1653 1654 # Program-related details. 1655 1656 self.blocks = None 1657 self.temp_usage = 0 1658 self.local_usage = 0 1659 self.all_local_usage = 0 1660 1661 def full_name(self): 1662 return self.name 1663 1664 def __repr__(self): 1665 if self.location is not None: 1666 return "Module(%r, location=%r)" % (self.name, self.location) 1667 else: 1668 return "Module(%r)" % self.name 1669 1670 def __shortrepr__(self): 1671 return "Module(%r)" % self.name 1672 1673 # Attribute methods. 1674 1675 "Return the module attribute names provided by the module." 1676 1677 module_attribute_names = NamespaceDict.keys 1678 1679 def module_attributes(self): 1680 1681 "Return a dictionary mapping names to module attributes." 1682 1683 return dict(self) 1684 1685 # vim: tabstop=4 expandtab shiftwidth=4