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