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