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