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