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