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