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