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