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