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