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