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