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