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