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