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