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