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