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