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