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 dynamic_def=0, 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 'dynamic_def' (indicating that the 1126 function must be handled dynamically), optional 'module', and optional 1127 AST 'node'. 1128 """ 1129 1130 NamespaceDict.__init__(self, module) 1131 1132 if name is None: 1133 self.name = "lambda#%d" % new_lambda() 1134 self._is_lambda = True 1135 else: 1136 self.name = name 1137 self._is_lambda = False 1138 1139 self.original_name = original_name or name 1140 1141 self.parent = parent 1142 self.argnames = argnames 1143 self.defaults = defaults 1144 self.has_star = has_star 1145 self.has_dstar = has_dstar 1146 self.dynamic_def = dynamic_def 1147 self.astnode = node 1148 1149 # Initialise the positional names. 1150 1151 self.positional_names = self.argnames[:] 1152 if has_dstar: 1153 self.dstar_name = self.positional_names[-1] 1154 del self.positional_names[-1] 1155 if has_star: 1156 self.star_name = self.positional_names[-1] 1157 del self.positional_names[-1] 1158 1159 # Initialise default storage. 1160 # NOTE: This must be initialised separately due to the reliance on node 1161 # NOTE: visiting. 1162 1163 self.default_attrs = [] 1164 1165 # Initialise attribute usage. 1166 1167 if node is not None: 1168 for arg in argnames: 1169 1170 # Define attribute users. 1171 1172 self._define_attribute_user_for_name(node, arg) 1173 1174 # Caches. 1175 1176 self.localnames = None # cache for locals 1177 1178 # Add parameters to the namespace. 1179 1180 self._add_parameters(argnames) 1181 1182 # Image generation details. 1183 1184 self.dynamic = None 1185 1186 # Program-related details. 1187 1188 self.blocks = None 1189 self.body_block = None 1190 1191 self.temp_usage = 0 1192 self.local_usage = 0 1193 self.all_local_usage = 0 1194 1195 def _add_parameters(self, argnames): 1196 1197 "Add 'argnames' to the namespace." 1198 1199 for name in argnames: 1200 self.set(name, make_instance()) 1201 1202 for name, top_level in self._flattened_parameters(argnames): 1203 if not top_level: 1204 self.set(name, make_instance()) 1205 1206 def _flattened_parameters(self, argnames, top_level=1): 1207 l = [] 1208 for name in argnames: 1209 if isinstance(name, tuple): 1210 l += self._flattened_parameters(name, 0) 1211 else: 1212 l.append((name, top_level)) 1213 return l 1214 1215 def __repr__(self): 1216 return "<function %s>" % shortrepr(self) 1217 1218 def __shortrepr__(self): 1219 return "%s.%s(%s)" % (shortrepr(self.parent), self.name, ", ".join(self.argnames)) 1220 1221 def get_body_block(self): 1222 return self.body_block 1223 1224 def is_lambda(self): 1225 return self._is_lambda 1226 1227 # Defaults-related methods. 1228 1229 def store_default(self, attr_or_value): 1230 1231 """ 1232 Reserve space for defaults, set outside the function, potentially on a 1233 dynamic basis, using the 'attr_or_value'. 1234 """ 1235 1236 attr = Attr(None, self, None) 1237 self._set_using_attr(attr, attr_or_value) 1238 self.default_attrs.append(attr) 1239 1240 def make_dynamic(self): 1241 1242 "Return whether this function must be handled using a dynamic object." 1243 1244 if self.dynamic is None: 1245 for attr in self.default_attrs: 1246 if not attr.is_strict_constant() and self.dynamic_def: 1247 self.dynamic = True 1248 self._make_dynamic() 1249 break 1250 else: 1251 self.dynamic = False 1252 1253 return self.dynamic 1254 1255 is_dynamic = make_dynamic 1256 1257 def _make_dynamic(self): 1258 1259 "Where functions have dynamic defaults, add a context argument." 1260 1261 name = "<context>" 1262 self.argnames.insert(0, name) 1263 self.positional_names.insert(0, name) 1264 self.set(name, make_instance()) 1265 1266 # Namespace-related methods. 1267 1268 def make_global(self, name): 1269 1270 "Declare 'name' as a global in the current namespace." 1271 1272 if name not in self.argnames and not self.has_key(name): 1273 self.globals.add(name) 1274 return True 1275 else: 1276 return False 1277 1278 def parameters(self): 1279 1280 """ 1281 Return a dictionary mapping parameter names to their position in the 1282 parameter list. 1283 """ 1284 1285 parameters = {} 1286 for i, name in enumerate(self.argnames): 1287 parameters[name] = i 1288 return parameters 1289 1290 def tuple_parameters(self, argnames=None): 1291 1292 """ 1293 Return a list of (position, parameter) entries corresponding to tuple 1294 parameters, where each parameter may either be a string or another such 1295 list of entries. 1296 """ 1297 1298 names = argnames or self.argnames 1299 1300 l = [] 1301 for i, name in enumerate(names): 1302 if isinstance(name, tuple): 1303 l.append((i, self.tuple_parameters(name))) 1304 elif argnames: 1305 l.append((i, name)) 1306 return l 1307 1308 def all_locals(self): 1309 1310 "Return a dictionary mapping names to local and parameter details." 1311 1312 return dict(self) 1313 1314 def locals(self): 1315 1316 "Return a dictionary mapping names to local details." 1317 1318 if self.localnames is None: 1319 self.localnames = {} 1320 self.localnames.update(self.all_locals()) 1321 for name in self.argnames: 1322 del self.localnames[name] 1323 return self.localnames 1324 1325 def is_method(self): 1326 1327 """ 1328 Return whether this function is a method explicitly defined in a class. 1329 """ 1330 1331 return isinstance(self.parent, Class) 1332 1333 def is_relocated(self, name): 1334 1335 """ 1336 Determine whether the given attribute 'name' is relocated for instances 1337 having this function as a method. 1338 """ 1339 1340 for cls in self.parent.descendants: 1341 if name in cls.relocated: 1342 return True 1343 return False 1344 1345 # Administrative methods. 1346 1347 def items_for_vacuum(self): 1348 return self.lambdas.items() 1349 1350 def vacuum_item(self, name): 1351 del self.lambdas[name] 1352 return True 1353 1354 def finalise_attributes(self): 1355 1356 """ 1357 Make sure all attributes (locals) are fully defined. Note that locals 1358 are not attributes in the sense of class, module or instance attributes. 1359 Defaults are also finalised by this method. 1360 """ 1361 1362 if self.finalised: 1363 return 1364 1365 # Defaults. 1366 1367 for i, default in enumerate(self.default_attrs): 1368 default.position = i 1369 1370 # Parameters. 1371 1372 i = self._finalise_parameters() 1373 1374 if i is not None: 1375 nparams = i + 1 1376 else: 1377 nparams = 0 1378 1379 # Locals (and tuple parameter names). 1380 1381 i = None 1382 for i, attr in enumerate(self.locals().values()): 1383 attr.position = i + nparams 1384 1385 if i is not None: 1386 nothers = i + 1 1387 else: 1388 nothers = 0 1389 1390 self.local_usage = nothers 1391 self.all_local_usage = nparams + nothers 1392 self.finalised = True 1393 1394 def _finalise_parameters(self): 1395 if not self.argnames: 1396 return None 1397 1398 for i, name in enumerate(self.argnames): 1399 self[name].position = i 1400 1401 return i 1402 1403 def as_instantiator(self): 1404 1405 "Make an instantiator function from a method, keeping all arguments." 1406 1407 function = Function(self.parent.name, self.parent.parent, self.argnames, self.defaults, 1408 self.has_star, self.has_dstar, self.dynamic_def, self.module) 1409 function.default_attrs = self.default_attrs 1410 return function 1411 1412 class UnresolvedName(NamespaceDict, Constant): 1413 1414 "A module, class or function which was mentioned but could not be imported." 1415 1416 def __init__(self, name, parent_name, module=None): 1417 NamespaceDict.__init__(self, module) 1418 self.name = name 1419 self.parent_name = parent_name 1420 self.parent = None 1421 1422 self.descendants = set() 1423 1424 def add_descendant(self, cls): 1425 self.descendants.add(cls) 1426 1427 def all_attributes(self): 1428 return {} 1429 1430 def all_attribute_names(self): 1431 return [] 1432 1433 all_class_attributes = class_attributes = instance_attributes = all_attributes 1434 all_class_attribute_names = class_attribute_names = instance_attribute_names = all_attribute_names 1435 1436 def __repr__(self): 1437 return "<unknown %s>" % shortrepr(self) 1438 1439 def __shortrepr__(self): 1440 if self.name is not None: 1441 return "%s.%s" % (self.parent_name, self.name) 1442 else: 1443 return self.parent_name 1444 1445 def full_name(self): 1446 if self.name is not None: 1447 return self.parent_name + "." + self.name 1448 else: 1449 return self.parent_name 1450 1451 class Module(NamespaceDict, Constant): 1452 1453 "An inspected module's core details." 1454 1455 def __init__(self, name, importer): 1456 NamespaceDict.__init__(self, self) 1457 self.name = name 1458 self.importer = importer 1459 self.parent = None 1460 1461 # Original location details. 1462 1463 self.astnode = None 1464 1465 # Complete lists of classes and functions. 1466 1467 self.all_objects = set() 1468 1469 # Whether the module is imported in a circular fashion, exposing the 1470 # unfinished namespace to external modification. 1471 1472 self.circular_import = self in importer.circular_imports 1473 1474 # A set of global names that cannot support combined attribute usage 1475 # observations because they may be modified within functions during 1476 # initialisation. 1477 1478 self.modified_names = set() 1479 1480 # Keyword records. 1481 1482 self.keyword_names = set() 1483 1484 # Program-related details. 1485 1486 self.blocks = None 1487 self.temp_usage = 0 1488 self.local_usage = 0 1489 self.all_local_usage = 0 1490 1491 def full_name(self): 1492 return self.name 1493 1494 def __repr__(self): 1495 return "<module %s>" % shortrepr(self) 1496 1497 def __shortrepr__(self): 1498 return self.name 1499 1500 # Attribute methods. 1501 1502 "Return the module attribute names provided by the module." 1503 1504 module_attribute_names = NamespaceDict.keys 1505 1506 def module_attributes(self): 1507 1508 "Return a dictionary mapping names to module attributes." 1509 1510 return dict(self) 1511 1512 all_attributes = module_attributes 1513 1514 def get_static_attribute(self, name): 1515 1516 """ 1517 Return a static attribute for the given 'name' or None if no such 1518 attribute exists. 1519 """ 1520 1521 return self.get(name) 1522 1523 def modify_name(self, name): 1524 1525 """ 1526 Modify a global 'name' invalidating various assumptions about its 1527 behaviour based on the module namespace being "safe" and suitable for 1528 attribute usage and constant value observations. 1529 """ 1530 1531 self.modified_names.add(name) 1532 1533 # Establish an attribute directly in the namespace if not present. 1534 1535 if not self.namespace.has_key(name): 1536 self.namespace[name] = Attr(None, self, name) 1537 1538 # Indicate that there is at least one assignment to the name, although 1539 # no actual values are recorded. 1540 1541 attr = self.namespace[name] 1542 attr.update_assignments(1, False) 1543 1544 def set(self, name, value, single_assignment=1): 1545 1546 """ 1547 Set the module attribute with the given 'name', having the given 'value' 1548 that is assigned once if 'single_assignment' is omitted to given as a 1549 true value. 1550 1551 Where the module is imported before it is completely initialised, all 1552 assignments will be regarded as multiple assignments since it is 1553 possible that an external assignment to the name may occur. 1554 """ 1555 1556 NamespaceDict.set(self, name, value, not self.circular_import and single_assignment) 1557 1558 # Attribute usage methods that apply to module globals in certain 1559 # circumstances. 1560 1561 def can_use_name_for_usage(self, name): 1562 return name not in self.modified_names and not self.circular_import 1563 1564 def _use_attribute(self, name, attrname, value=None): 1565 if self.can_use_name_for_usage(name): 1566 return NamespaceDict._use_attribute(self, name, attrname, value) 1567 else: 1568 self.importer.use_name(attrname, self.full_name(), value) 1569 return [] 1570 1571 def _define_attribute_user_for_name(self, node, name): 1572 if self.can_use_name_for_usage(name): 1573 NamespaceDict._define_attribute_user_for_name(self, node, name) 1574 1575 def _init_attribute_user_for_name(self, node, name): 1576 if self.can_use_name_for_usage(name): 1577 NamespaceDict._init_attribute_user_for_name(self, node, name) 1578 1579 def _define_attribute_accessor(self, name, attrname, node, value): 1580 if self.can_use_name_for_usage(name): 1581 NamespaceDict._define_attribute_accessor(self, name, attrname, node, value) 1582 else: 1583 self.importer.use_name(attrname, self.full_name(), value) 1584 1585 # Pre-made class instances. 1586 # For each of these, their details will be filled in later. 1587 1588 premade = { 1589 "bool" : Class("bool"), 1590 "float" : Class("float"), 1591 "int" : Class("int"), 1592 "long" : Class("long"), 1593 "str" : Class("str"), 1594 "unicode" : Class("unicode"), 1595 "type" : Class("type"), 1596 "NoneType" : Class("NoneType"), 1597 } 1598 1599 def get_constant_class(name): 1600 return premade[name] 1601 1602 # Class construction. 1603 1604 def get_class(name, parent, module, node): 1605 1606 """ 1607 Return a Class instance for the class with the given 'name', 'parent', 1608 'module' and 'node'. 1609 """ 1610 1611 if premade.has_key(name) and module.full_name() == "__builtins__": 1612 cls = premade[name] 1613 cls.set_context(parent, module, node) 1614 else: 1615 # Where names are reused in a namespace, differentiate between classes 1616 # using a name index. 1617 1618 original_name = name 1619 1620 if parent.has_key(name): 1621 assignments = parent[name].static_assignments 1622 if assignments > 1: 1623 name = "%s#%d" % (name, assignments + 1) 1624 1625 cls = Class(name, parent, module, node, original_name) 1626 1627 # Add a reference for the class's "shadow" name. 1628 1629 parent.use_specific_attribute(parent.full_name(), name) 1630 1631 return cls 1632 1633 # Function construction. 1634 1635 def get_function(name, parent, argnames, defaults, has_star, has_dstar, 1636 dynamic_def=0, module=None, node=None): 1637 1638 """ 1639 Return a Function instance for the class with the given 'name', 'parent', 1640 and other details. 1641 """ 1642 1643 original_name = name 1644 1645 if parent.has_key(name): 1646 assignments = parent[name].static_assignments 1647 if assignments > 1: 1648 name = "%s#%d" % (name, assignments + 1) 1649 1650 fn = Function(name, parent, argnames, defaults, has_star, has_dstar, 1651 dynamic_def, module, node, original_name) 1652 1653 # Add a reference for the function's "shadow" name. 1654 1655 if name: 1656 parent.use_specific_attribute(parent.full_name(), name) 1657 1658 return fn 1659 1660 # Lambda sequence numbering. 1661 1662 lambda_index = 0 1663 1664 def new_lambda(): 1665 1666 "Return a new sequence number for a lambda definition." 1667 1668 global lambda_index 1669 lambda_index += 1 1670 return lambda_index 1671 1672 # Special representations. 1673 1674 class AtLeast: 1675 1676 "A special representation for numbers of a given value or greater." 1677 1678 def __init__(self, count): 1679 self.count = count 1680 1681 def __eq__(self, other): 1682 return False 1683 1684 __lt__ = __le__ = __eq__ 1685 1686 def __ne__(self, other): 1687 return True 1688 1689 def __gt__(self, other): 1690 if isinstance(other, AtLeast): 1691 return False 1692 else: 1693 return self.count > other 1694 1695 def __ge__(self, other): 1696 if isinstance(other, AtLeast): 1697 return False 1698 else: 1699 return self.count >= other 1700 1701 def __iadd__(self, other): 1702 if isinstance(other, AtLeast): 1703 self.count += other.count 1704 else: 1705 self.count += other 1706 return self 1707 1708 def __radd__(self, other): 1709 if isinstance(other, AtLeast): 1710 return AtLeast(self.count + other.count) 1711 else: 1712 return AtLeast(self.count + other) 1713 1714 def __repr__(self): 1715 return "AtLeast(%r)" % self.count 1716 1717 # vim: tabstop=4 expandtab shiftwidth=4