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 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 DataObject, DataValue, ReplaceableContext, PlaceholderContext 56 57 def shortrepr(obj): 58 if obj is None: 59 return repr(None) 60 else: 61 return obj.__shortrepr__() 62 63 # Special representations. 64 65 class AtLeast: 66 67 "A special representation for numbers of a given value or greater." 68 69 def __init__(self, count): 70 self.count = count 71 72 def __eq__(self, other): 73 return 0 74 75 __lt__ = __le__ = __eq__ 76 77 def __ne__(self, other): 78 return 1 79 80 def __gt__(self, other): 81 if isinstance(other, AtLeast): 82 return 0 83 else: 84 return self.count > other 85 86 def __ge__(self, other): 87 if isinstance(other, AtLeast): 88 return 0 89 else: 90 return self.count >= other 91 92 def __iadd__(self, other): 93 if isinstance(other, AtLeast): 94 self.count += other.count 95 else: 96 self.count += other 97 return self 98 99 def __radd__(self, other): 100 if isinstance(other, AtLeast): 101 return AtLeast(self.count + other.count) 102 else: 103 return AtLeast(self.count + other) 104 105 def __repr__(self): 106 return "AtLeast(%r)" % self.count 107 108 # Mix-ins and abstract classes. 109 110 class Naming: 111 112 "A mix-in providing naming conveniences." 113 114 def full_name(self): 115 if self.name is not None: 116 return self.parent.full_name() + "." + self.name 117 else: 118 return self.parent.full_name() 119 120 class NamespaceDict: 121 122 "A mix-in providing dictionary methods." 123 124 def __init__(self, module=None): 125 self.namespace = {} 126 self.globals = set() 127 self.module = module 128 self.finalised = 0 129 130 # Attributes accessed on objects, potentially narrowing their types. 131 # Specific namespaces should define known names during initialisation. 132 # For example, functions can define names belonging to parameters. 133 134 # Attribute users, defining names which use attributes. 135 136 self.attribute_users = [{}] # stack of assignments 137 self.user_shelves = [] 138 self.loop_users = [{}] # stack of loop nodes 139 140 # Define attribute usage to identify active program sections. 141 142 self.all_attribute_users = set() 143 144 # Attribute/name definition and access. 145 146 def __delitem__(self, name): 147 del self.namespace[name] 148 149 def has_key(self, name): 150 return self.namespace.has_key(name) 151 152 def keys(self): 153 return self.namespace.keys() 154 155 def values(self): 156 return self.namespace.values() 157 158 def items(self): 159 return self.namespace.items() 160 161 def __getitem__(self, name): 162 return self.namespace[name] 163 164 def get(self, name, default=None): 165 return self.namespace.get(name, default) 166 167 def __setitem__(self, name, value): 168 self.set(name, value) 169 170 def set(self, name, value, single_assignment=1): 171 172 """ 173 A more powerful set operation, making 'name' refer to 'value' whilst 174 indicating whether a 'single_assignment' (true by default) occurs in 175 this operation (or whether the operation covers potentially many 176 assignments in the lifetime of a program). 177 """ 178 179 if name in self.globals: 180 self.module.set(name, value, 0) 181 else: 182 self._set(name, value, single_assignment) 183 184 def set_module(self, name, value): 185 186 """ 187 A specialised set operation, making 'name' refer to 'value' in the 188 context of making a module reference available in association with 189 'name' as part of the import of that module or a submodule of that 190 module. 191 """ 192 193 self._set(name, value, 1) 194 195 def _set(self, name, attr_or_value, single_assignment=1): 196 197 """ 198 The underlying set operation associating 'name' with the given 199 'attr_or_value'. 200 See: docs/assignment.txt 201 """ 202 203 # Add and/or obtain the namespace entry. 204 205 if not self.namespace.has_key(name): 206 self.namespace[name] = Attr(None, self, name) 207 208 attr = self.namespace[name] 209 self._set_using_attr(attr, attr_or_value, single_assignment) 210 211 def _set_using_attr(self, attr, attr_or_value, single_assignment=1): 212 213 # Handle attribute assignment as well as assignment of basic objects. 214 # Attempt to fix the context if not explicitly defined. 215 216 if isinstance(attr_or_value, Attr): 217 context_values = self.get_updated_context_values(attr_or_value.context_values) 218 else: 219 context_values = self.get_updated_context_values([self.get_context_and_value(attr_or_value)]) 220 221 attr.update(context_values, single_assignment) 222 223 def get_context_and_value(self, value): 224 225 "Return a context, value tuple for the given 'value'." 226 227 # Functions have a replaceable context. 228 229 if isinstance(value, Function): 230 return (ReplaceableContext, value) 231 232 # Classes use placeholder contexts which cannot be replaced but which 233 # do not communicate useful contextual information. 234 235 elif isinstance(value, Class): 236 return (PlaceholderContext, value) 237 238 # Other values employ themselves as the context. 239 240 else: 241 return (value, value) 242 243 def get_updated_context_values(self, context_values): 244 245 """ 246 Adapt the contexts found in the given 'context_values', returning a new 247 set. 248 See: docs/assignment.txt 249 """ 250 251 results = set() 252 253 for context, value in context_values: 254 255 # Set the context of instances to themselves. 256 257 if isinstance(value, Instance): 258 results.add((value, value)) 259 else: 260 results.add((context, value)) 261 262 return results 263 264 def make_global(self, name): 265 266 "Declare 'name' as a global in the current namespace." 267 268 if not self.namespace.has_key(name): 269 self.globals.add(name) 270 return 1 271 else: 272 return 0 273 274 # Attribute positioning. 275 276 def attributes_as_list(self): 277 278 "Return the attributes in a list." 279 280 self.finalise_attributes() 281 l = [None] * len(self.keys()) 282 for attr in self.values(): 283 l[attr.position] = attr 284 return l 285 286 def finalise_attributes(self): 287 288 "Make sure all attributes are fully defined." 289 290 if self.finalised: 291 return 292 293 # The default action is to assign attribute positions sequentially. 294 295 for i, attr in enumerate(self.values()): 296 attr.position = i 297 298 self.finalised = 1 299 300 def unfinalise_attributes(self): 301 302 "Open attribute definitions to editing and subsequent finalisation." 303 304 self.finalised = 0 305 306 # Attribute usage methods. 307 308 def get_all_attribute_usage(self): 309 310 """ 311 Return a set of all usage tuples for attributes used with the different 312 local names. 313 """ 314 315 usage = set() 316 for user in self.all_attribute_users: 317 for name, attrnames in user._attrnames.items(): 318 usage.add(tuple(attrnames)) 319 return usage 320 321 def use_attribute(self, name, attrname): 322 323 "Declare the usage on 'name' of the given 'attrname'." 324 325 return self._use_attribute(name, attrname) 326 327 # These shadow various methods in the InspectedModule class, and provide 328 # implementations generally. 329 330 def _use_attribute(self, name, attrname): 331 332 """ 333 Indicate the use of the given 'name' in this namespace of an attribute 334 with the given 'attrname'. 335 """ 336 337 for users in (self.attribute_users[-1], self.loop_users[-1]): 338 339 # Add the usage to all current users. 340 341 if users.has_key(name): 342 for user in users[name]: 343 user._attrnames[name].add(attrname) 344 345 users = self.attribute_users[-1] 346 347 if users.has_key(name): 348 return users[name] 349 else: 350 return [] 351 352 def _define_attribute_user(self, node): 353 354 """ 355 Define 'node' as the user of attributes, indicating the point where the 356 user is defined. 357 """ 358 359 name = node.name 360 self._define_attribute_user_for_name(node, name) 361 362 def _define_attribute_user_for_name(self, node, name): 363 364 "Define 'node' as the user of attributes for the given 'name'." 365 366 users = self.attribute_users[-1] 367 368 # This node overrides previous definitions. 369 370 users[name] = set([node]) 371 372 # Record the attribute combinations for the name. 373 374 self._init_attribute_user_for_name(node, name) 375 376 # Propagate any loop usage forward to any redefinition of a name. 377 378 loop_users = self.loop_users[-1] 379 380 if loop_users.has_key(name): 381 for loop_user in loop_users[name]: 382 node._attrnames[name].update(loop_user._attrnames[name]) 383 del loop_users[name] 384 385 # Remember this user. 386 387 self.all_attribute_users.add(node) 388 389 def _init_attribute_user_for_name(self, node, name): 390 391 "Make sure that 'node' is initialised for 'name'." 392 393 if not hasattr(node, "_attrnames"): 394 node._attrnames = {} 395 396 node._attrnames[name] = set() 397 398 def _new_branchpoint(self): 399 400 """ 401 Establish a new branchpoint where several control-flow branches diverge 402 and subsequently converge. 403 """ 404 405 self.user_shelves.append([]) 406 407 def _new_branch(self, loop_node=None): 408 409 """ 410 Establish a new control-flow branch, transferring attribute usage to 411 the new branch so that it may be augmented for each name locally. 412 413 If the optional 'loop_node' is given, add it as an active user to be 414 informed of attribute usage. 415 """ 416 417 # Retain a record of active users. 418 419 d = {} 420 d.update(self.attribute_users[-1]) 421 self.attribute_users.append(d) 422 423 new_users = self.attribute_users[-1] 424 425 d = {} 426 d.update(self.loop_users[-1]) 427 428 if loop_node is not None: 429 for name in new_users.keys(): 430 if not d.has_key(name): 431 d[name] = set([loop_node]) 432 else: 433 d[name] = d[name].union([loop_node]) 434 self._init_attribute_user_for_name(loop_node, name) 435 436 self.loop_users.append(d) 437 438 def _abandon_branch(self): 439 pass 440 441 def _shelve_branch(self): 442 443 """ 444 Shelve the current control-flow branch, recording the attribute usage 445 for subsequent merging. If this branch should be abandoned, the usage 446 observations are still recorded but will not contribute to subsequent 447 observations after a merge. 448 """ 449 450 users = self.attribute_users.pop() 451 self.user_shelves[-1].append(users) 452 453 def _merge_branches(self): 454 455 """ 456 Merge control-flow branches. This should find the users active within 457 each branch, which have been "shelved", and update the active users 458 dictionary with these contributions. 459 """ 460 461 # Combine the attribute users. This ensures that a list of users 462 # affected by attribute usage is maintained for the current branch. 463 464 users = self.attribute_users[-1] 465 new_users = {} 466 467 all_shelved_users = self.user_shelves.pop() 468 all_user_names = set() 469 470 # Find all the names defined by the branches. 471 472 for shelved_users in all_shelved_users: 473 all_user_names.update(shelved_users.keys()) 474 475 # Copy all definitions from the branches for the names, maintaining 476 # the existing users where a branch does not redefine a name. 477 478 for shelved_users in all_shelved_users: 479 for name in all_user_names: 480 481 if shelved_users.has_key(name): 482 nodes = shelved_users[name] 483 else: 484 nodes = users.get(name, set()) 485 486 if nodes: 487 if not new_users.has_key(name): 488 new_users[name] = set(nodes) 489 else: 490 new_users[name].update(nodes) 491 492 self.attribute_users[-1] = new_users 493 494 # Program data structures. 495 496 class Attr: 497 498 "An attribute entry having a context." 499 500 def __init__(self, position, parent, name): 501 502 """ 503 Initialise the attribute with the given 'position' within the collection 504 of attributes of its 'parent', indicating its 'name'. 505 """ 506 507 self.position = position 508 self.parent = parent 509 self.name = name 510 511 # Possible values. 512 513 self.context_values = set() 514 515 # Number of assignments per name. 516 517 self.assignments = None 518 519 # Value-related methods. 520 521 def get_contexts(self): 522 return [c for (c, v) in self.context_values] 523 524 def get_values(self): 525 return [v for (c, v) in self.context_values] 526 527 def get_context(self): 528 if len(self.context_values) == 1: 529 return self.get_contexts()[0] 530 else: 531 return None 532 533 def get_value(self): 534 if len(self.context_values) == 1: 535 return self.get_values()[0] 536 else: 537 return None 538 539 def update(self, context_values, single_assignment): 540 541 """ 542 Update the attribute, adding the 'context_values' provided to the 543 known details associated with the attribute, changing the number of 544 assignments according to the 'single_assignment' status of the 545 operation, where a true value indicates that only one assignment is 546 associated with the update, and a false value indicates that potentially 547 many assignments may be involved. 548 """ 549 550 if self.assignments is None: 551 if single_assignment: 552 self.assignments = 1 553 else: 554 self.assignments = AtLeast(1) 555 else: 556 if single_assignment: 557 self.assignments += 1 558 else: 559 self.assignments += AtLeast(1) 560 561 self.context_values.update(context_values) 562 563 def is_static_attribute(self): 564 565 """ 566 Return whether this attribute is defined on a fixed/static object such 567 as a class or a module. 568 """ 569 570 return isinstance(self.parent, (Class, Module)) 571 572 def defines_ambiguous_class(self): 573 574 "Return whether this attribute defines more than one class." 575 576 if self.assignments > 1: 577 have_class = 0 578 for obj in self.get_values(): 579 if isinstance(obj, Class): 580 if have_class: 581 return 1 582 have_class = 1 583 584 return 0 585 586 def defined_within_hierarchy(self): 587 588 """ 589 Return whether the parent and context of the attribute belong to the 590 same class hierarchy. 591 """ 592 593 # Must be defined within a class. 594 595 if isinstance(self.parent, Class): 596 597 # To be sure, all contexts must be classes and be the same as the 598 # parent, or be a superclass of the parent, or be a subclass of the 599 # parent. 600 601 for context in self.get_contexts(): 602 if not ( 603 isinstance(context, Class) and ( 604 context is self.parent or 605 context.has_subclass(self.parent) or 606 self.parent.has_subclass(context)) 607 ): 608 return 0 609 610 return 1 611 612 # Instance attributes are not defined within a hierarchy. 613 614 else: 615 return 0 616 617 def defined_outside_hierarchy(self): 618 619 """ 620 Return whether the parent and context of the attribute never belong to 621 the same class hierarchy. 622 """ 623 624 # Must be defined within a class. 625 626 if isinstance(self.parent, Class): 627 628 # To be sure, all contexts must be classes and be the same as the 629 # parent, or be a superclass of the parent, or be a subclass of the 630 # parent. 631 632 for context in self.get_contexts(): 633 if not ( 634 isinstance(context, Class) and not ( 635 context is self.parent or 636 context.has_subclass(self.parent) or 637 self.parent.has_subclass(context)) 638 ): 639 return 0 640 641 return 1 642 643 # Instance attributes are not defined within a hierarchy. 644 645 else: 646 return 0 647 648 def __repr__(self): 649 return "Attr(%r, %s, %r) # [%s], %r" % ( 650 self.position, shortrepr(self.parent), self.name, 651 self._context_values_str(), self.assignments 652 ) 653 654 def __shortrepr__(self): 655 return "Attr(%r, %s, %r)" % ( 656 self.position, shortrepr(self.parent), self.name 657 ) 658 659 def _context_values_str(self): 660 l = [] 661 for (c, v) in self.context_values: 662 l.append("(c=%s, v=%s)" % (shortrepr(c), shortrepr(v))) 663 return ", ".join(l) 664 665 # Instances are special in that they need to be wrapped together with context in 666 # a running program, but they are not generally constant. 667 668 class Instance: 669 670 "A placeholder indicating the involvement of an instance." 671 672 def __init__(self): 673 self.parent = None 674 675 # Image generation details. 676 677 self.location = None 678 679 def __repr__(self): 680 return "Instance()" 681 682 __shortrepr__ = __repr__ 683 684 class Constant: 685 686 "A superclass for all constant or context-free structures." 687 688 pass 689 690 # Data objects appearing in programs before run-time. 691 692 class Const(Constant, Instance): 693 694 "A constant object with no context." 695 696 def __init__(self, value): 697 Instance.__init__(self) 698 self.value = value 699 700 def get_value(self): 701 return self.value 702 703 def __repr__(self): 704 if self.location is not None: 705 return "Const(%r, location=%r)" % (self.value, self.location) 706 else: 707 return "Const(%r)" % self.value 708 709 __shortrepr__ = __repr__ 710 711 # Support constants as dictionary keys in order to build constant tables. 712 713 def __eq__(self, other): 714 return other is not None and self.value == other.value and self.value.__class__ is other.value.__class__ 715 716 def __hash__(self): 717 return hash(self.value) 718 719 def value_type_name(self): 720 return "__builtins__." + self.value.__class__.__name__ 721 722 class Class(NamespaceDict, Naming, Constant): 723 724 "An inspected class." 725 726 def __init__(self, name, parent, module=None, node=None): 727 728 """ 729 Initialise the class with the given 'name', 'parent' object, optional 730 'module' and optional AST 'node'. 731 """ 732 733 NamespaceDict.__init__(self, module) 734 self.name = name 735 self.parent = parent 736 self.astnode = node 737 node._def = self 738 739 # Superclasses, descendants and attributes. 740 741 self.bases = [] 742 self.descendants = set() 743 self.instattr = set() # instance attributes 744 self.relocated = set() # attributes which do not have the same 745 # position as those of the same name in 746 # some superclasses 747 748 # Caches. 749 750 self.reset_caches() 751 752 # Image generation details. 753 754 self.location = None 755 self.code_location = None 756 self.code_body_location = None # corresponds to the instantiator 757 758 self.instantiator = None 759 self.instance_template_location = None # for creating instances at run-time 760 761 # Program-related details. 762 763 self.blocks = None 764 self.temp_usage = 0 765 self.local_usage = 0 766 self.all_local_usage = 0 767 768 # Add this class to its attributes. 769 770 self.set("__class__", self) 771 772 def reset_caches(self): 773 774 "Reset the caches." 775 776 self.all_instattr = None # cache for instance_attributes 777 self.all_instattr_names = None # from all_instattr 778 self.all_classattr = None # cache for all_class_attributes 779 self.all_classattr_names = None # from all_classattr 780 self.allattr = None # cache for all_attributes 781 self.allattr_names = None # from allattr 782 783 def __repr__(self): 784 if self.location is not None: 785 return "Class(%r, %s, location=%r)" % (self.name, shortrepr(self.parent), self.location) 786 else: 787 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 788 789 def __shortrepr__(self): 790 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 791 792 def get_body_block(self): 793 return self.get_instantiator().blocks[0] 794 795 # Namespace-related methods. 796 797 def get_updated_context_values(self, context_values): 798 799 """ 800 Adapt the contexts found in the given 'context_values', returning a new 801 set. 802 See: docs/assignment.txt 803 """ 804 805 results = set() 806 807 for context, value in context_values: 808 809 # Change the ownership of functions. 810 811 if context is ReplaceableContext and value is not None and isinstance(value, Function): 812 results.add((self, value)) 813 else: 814 results.add((context, value)) 815 816 return NamespaceDict.get_updated_context_values(self, results) 817 818 def finalise_attributes(self): 819 820 "Make sure that all attributes are fully defined." 821 822 if self.finalised: 823 return 824 825 self.finalise_class_attributes() 826 self.finalise_instance_attributes() 827 self.finalised = 1 828 829 def unfinalise_attributes(self): 830 831 "Open attribute definitions to editing and subsequent finalisation." 832 833 self.reset_caches() 834 self.finalised = 0 835 836 # Convenience methods for accessing functions and methods. 837 838 def get_instantiator(self): 839 840 "Return a function which can be used to instantiate the class." 841 842 if self.instantiator is None: 843 self.instantiator = self.get_init_method().as_instantiator() 844 return self.instantiator 845 846 def get_init_method(self): 847 return self.all_class_attributes()["__init__"].get_value() 848 849 # Class-specific methods. 850 851 def add_base(self, base): 852 self.bases.append(base) 853 base.add_descendant(self) 854 855 def add_instance_attribute(self, name): 856 self.instattr.add(name) 857 858 def add_descendant(self, cls): 859 self.descendants.add(cls) 860 for base in self.bases: 861 base.add_descendant(cls) 862 863 def has_subclass(self, other): 864 return other in self.descendants 865 866 def all_descendants(self): 867 d = {} 868 for cls in self.descendants: 869 d[cls.full_name()] = cls 870 return d 871 872 "Return the attribute names provided by this class only." 873 874 class_attribute_names = NamespaceDict.keys 875 876 def class_attributes(self): 877 878 "Return class attributes provided by this class only." 879 880 return dict(self) 881 882 def all_class_attribute_names(self): 883 884 "Return the attribute names provided by classes in this hierarchy." 885 886 if self.all_classattr_names is None: 887 self.all_class_attributes() 888 self.all_classattr_names = self.all_classattr.keys() 889 return self.all_classattr_names 890 891 def all_class_attributes(self): 892 893 "Return all class attributes, indicating the class which provides them." 894 895 self.finalise_class_attributes() 896 return self.all_classattr 897 898 def finalise_class_attributes(self): 899 900 "Make sure that the class attributes are fully defined." 901 902 if self.all_classattr is None: 903 self.all_classattr = {} 904 clsattr = {} 905 906 # Record provisional position information for attributes of this 907 # class. 908 909 for name in self.class_attributes().keys(): 910 clsattr[name] = set() # position not yet defined 911 912 reversed_bases = self.bases[:] 913 reversed_bases.reverse() 914 915 # For the bases in reverse order, acquire class attribute details. 916 917 for cls in reversed_bases: 918 for name, attr in cls.all_class_attributes().items(): 919 self.all_classattr[name] = attr 920 921 # Record previous attribute information. 922 923 if clsattr.has_key(name): 924 clsattr[name].add(attr.position) 925 926 # Record class attributes provided by this class and its bases, 927 # along with their positions. 928 929 self.all_classattr.update(self.class_attributes()) 930 931 if clsattr: 932 for i, name in enumerate(self._get_position_list(clsattr)): 933 self.all_classattr[name].position = i 934 935 return self.all_classattr 936 937 def instance_attribute_names(self): 938 939 "Return the instance attribute names provided by the class." 940 941 if self.all_instattr_names is None: 942 self.instance_attributes() 943 return self.all_instattr_names 944 945 def instance_attributes(self): 946 947 "Return instance-only attributes for instances of this class." 948 949 self.finalise_instance_attributes() 950 return self.all_instattr 951 952 def finalise_instance_attributes(self): 953 954 "Make sure that the instance attributes are fully defined." 955 956 # Cache the attributes by converting the positioned attributes into a 957 # dictionary. 958 959 if self.all_instattr is None: 960 self.all_instattr = self._get_attributes() 961 self.all_instattr_names = self.all_instattr.keys() 962 963 return self.all_instattr 964 965 def _get_attributes(self): 966 967 """ 968 Return a dictionary mapping names to Attr instances incorporating 969 information about their positions in the final instance structure. 970 """ 971 972 instattr = {} 973 974 # Record provisional position information for attributes of this 975 # instance. 976 977 for name in self.instattr: 978 instattr[name] = set() # position not yet defined 979 980 reversed_bases = self.bases[:] 981 reversed_bases.reverse() 982 983 # For the bases in reverse order, acquire instance attribute 984 # details. 985 986 for cls in reversed_bases: 987 for name, attr in cls.instance_attributes().items(): 988 989 # Record previous attribute information. 990 991 if instattr.has_key(name): 992 instattr[name].add(attr.position) 993 else: 994 instattr[name] = set([attr.position]) 995 996 # Build the dictionary of attributes using the existing positions known 997 # for each name. 998 999 d = {} 1000 for i, name in enumerate(self._get_position_list(instattr)): 1001 d[name] = Attr(i, Instance(), name) 1002 return d 1003 1004 def _get_position_list(self, positions): 1005 1006 """ 1007 Return a list of attribute names for the given 'positions' mapping from 1008 names to positions, indicating the positions of the attributes in the 1009 final instance structure. 1010 """ 1011 1012 position_items = positions.items() 1013 namearray = [None] * len(position_items) 1014 1015 # Get the positions in ascending order of list size, with lists 1016 # of the same size ordered according to their smallest position 1017 # value. 1018 1019 position_items.sort(self._cmp_positions) 1020 1021 # Get the names in position order. 1022 1023 held = [] 1024 1025 for name, pos in position_items: 1026 pos = list(pos) 1027 pos.sort() 1028 if pos and pos[0] < len(namearray) and namearray[pos[0]] is None: 1029 namearray[pos[0]] = name 1030 else: 1031 if pos: 1032 self.relocated.add(name) 1033 held.append((name, pos)) 1034 1035 for i, attr in enumerate(namearray): 1036 if attr is None: 1037 name, pos = held.pop() 1038 namearray[i] = name 1039 1040 return namearray 1041 1042 def _cmp_positions(self, a, b): 1043 1044 "Compare name plus position list operands 'a' and 'b'." 1045 1046 name_a, list_a = a 1047 name_b, list_b = b 1048 if len(list_a) < len(list_b): 1049 return -1 1050 elif len(list_a) > len(list_b): 1051 return 1 1052 elif not list_a: 1053 return 0 1054 else: 1055 return cmp(min(list_a), min(list_b)) 1056 1057 def all_attribute_names(self): 1058 1059 """ 1060 Return the names of all attributes provided by instances of this class. 1061 """ 1062 1063 self.allattr_names = self.allattr_names or self.all_attributes().keys() 1064 return self.allattr_names 1065 1066 def all_attributes(self): 1067 1068 """ 1069 Return all attributes for an instance, indicating either the class which 1070 provides them or that the instance itself provides them. 1071 """ 1072 1073 if self.allattr is None: 1074 self.allattr = {} 1075 self.allattr.update(self.all_class_attributes()) 1076 for name, attr in self.instance_attributes().items(): 1077 if self.allattr.has_key(name): 1078 print "Instance attribute %r in %r overrides class attribute." % (name, self) 1079 self.allattr[name] = attr 1080 return self.allattr 1081 1082 class Function(NamespaceDict, Naming, Constant): 1083 1084 "An inspected function." 1085 1086 def __init__(self, name, parent, argnames, defaults, has_star, has_dstar, module=None, node=None): 1087 1088 """ 1089 Initialise the function with the given 'name', 'parent', list of 1090 'argnames', list of 'defaults', the 'has_star' flag (indicating the 1091 presence of a * parameter), the 'has_dstar' flag (indicating the 1092 presence of a ** parameter), optional 'module', and optional AST 'node'. 1093 """ 1094 1095 NamespaceDict.__init__(self, module) 1096 self.name = name 1097 self.parent = parent 1098 self.argnames = argnames 1099 self.defaults = defaults 1100 self.has_star = has_star 1101 self.has_dstar = has_dstar 1102 self.astnode = node 1103 node._def = self 1104 1105 # For lambda functions with defaults, add a context argument. 1106 1107 if name is None and defaults: 1108 self.argnames.insert(0, "<context>") 1109 1110 # Initialise the positional names. 1111 1112 self.positional_names = self.argnames[:] 1113 if has_dstar: 1114 self.dstar_name = self.positional_names[-1] 1115 del self.positional_names[-1] 1116 if has_star: 1117 self.star_name = self.positional_names[-1] 1118 del self.positional_names[-1] 1119 1120 # Initialise default storage. 1121 # NOTE: This must be initialised separately due to the reliance on node 1122 # NOTE: visiting. 1123 1124 self.default_attrs = [] 1125 1126 # Initialise attribute usage. 1127 1128 for arg in argnames: 1129 1130 # Define attribute users. 1131 1132 if node is not None: 1133 self._define_attribute_user_for_name(node, arg) 1134 1135 # Or just record the usage. 1136 1137 else: 1138 self.attributes_used[-1][arg] = set() 1139 1140 # Caches. 1141 1142 self.localnames = None # cache for locals 1143 1144 # Add parameters to the namespace. 1145 1146 self._add_parameters(argnames) 1147 1148 # Image generation details. 1149 1150 self.location = None 1151 self.code_location = None 1152 self.code_body_location = None 1153 1154 # Program-related details. 1155 1156 self.blocks = None 1157 self.body_block = None 1158 1159 self.temp_usage = 0 1160 self.local_usage = 0 1161 self.all_local_usage = 0 1162 1163 def _add_parameters(self, argnames): 1164 for name in argnames: 1165 if isinstance(name, tuple): 1166 self._add_parameters(name) 1167 else: 1168 self.set(name, Instance()) 1169 1170 def __repr__(self): 1171 if self.location is not None: 1172 return "Function(%r, %s, %r, location=%r, code_location=%r)" % ( 1173 self.name, shortrepr(self.parent), self.argnames, self.location, self.code_location 1174 ) 1175 else: 1176 return "Function(%r, %s, %r)" % ( 1177 self.name, shortrepr(self.parent), self.argnames 1178 ) 1179 1180 def __shortrepr__(self): 1181 return "Function(%r, %s)" % ( 1182 self.name, shortrepr(self.parent) 1183 ) 1184 1185 def get_body_block(self): 1186 return self.body_block 1187 1188 # Namespace-related methods. 1189 1190 def store_default(self, attr_or_value): 1191 1192 """ 1193 Reserve space for defaults, set outside the function, potentially on a 1194 dynamic basis, using the 'attr_or_value'. 1195 """ 1196 1197 attr = Attr(None, self, None) 1198 self._set_using_attr(attr, attr_or_value) 1199 self.default_attrs.append(attr) 1200 1201 def make_global(self, name): 1202 if name not in self.argnames and not self.has_key(name): 1203 self.globals.add(name) 1204 return 1 1205 else: 1206 return 0 1207 1208 def parameters(self): 1209 1210 """ 1211 Return a dictionary mapping parameter names to their position in the 1212 parameter list. 1213 """ 1214 1215 parameters = {} 1216 for i, name in enumerate(self.argnames): 1217 parameters[name] = i 1218 return parameters 1219 1220 def all_locals(self): 1221 1222 "Return a dictionary mapping names to local and parameter details." 1223 1224 return dict(self) 1225 1226 def locals(self): 1227 1228 "Return a dictionary mapping names to local details." 1229 1230 if self.localnames is None: 1231 self.localnames = {} 1232 self.localnames.update(self.all_locals()) 1233 for name in self.argnames: 1234 del self.localnames[name] 1235 return self.localnames 1236 1237 def is_method(self): 1238 1239 """ 1240 Return whether this function is a method explicitly defined in a class. 1241 """ 1242 1243 return isinstance(self.parent, Class) 1244 1245 def is_relocated(self, name): 1246 1247 """ 1248 Determine whether the given attribute 'name' is relocated for instances 1249 having this function as a method. 1250 """ 1251 1252 for cls in self.parent.descendants: 1253 if name in cls.relocated: 1254 return 1 1255 return 0 1256 1257 def finalise_attributes(self): 1258 1259 """ 1260 Make sure all attributes (locals) are fully defined. Note that locals 1261 are not attributes in the sense of class, module or instance attributes. 1262 Defaults are also finalised by this method. 1263 """ 1264 1265 if self.finalised: 1266 return 1267 1268 # Defaults. 1269 1270 for i, default in enumerate(self.default_attrs): 1271 default.position = i 1272 1273 # Locals. 1274 1275 i = None 1276 for i, name in enumerate(self.argnames): 1277 self[name].position = i 1278 1279 if i is not None: 1280 nparams = i + 1 1281 else: 1282 nparams = 0 1283 1284 i = None 1285 for i, attr in enumerate(self.locals().values()): 1286 attr.position = i + nparams 1287 1288 if i is not None: 1289 nothers = i + 1 1290 else: 1291 nothers = 0 1292 1293 self.local_usage = nothers 1294 self.all_local_usage = nparams + nothers 1295 self.finalised = 1 1296 1297 def as_instantiator(self): 1298 1299 "Make an instantiator function from a method, keeping all arguments." 1300 1301 function = Function(self.parent.name, self.parent.parent, self.argnames, self.defaults, 1302 self.has_star, self.has_dstar, self.module, self.astnode) 1303 function.default_attrs = self.default_attrs 1304 return function 1305 1306 class UnresolvedName(NamespaceDict, Constant): 1307 1308 "A module, class or function which was mentioned but could not be imported." 1309 1310 def __init__(self, name, parent_name, module=None): 1311 NamespaceDict.__init__(self, module) 1312 self.name = name 1313 self.parent_name = parent_name 1314 self.parent = None 1315 1316 self.descendants = set() 1317 1318 def add_descendant(self, cls): 1319 self.descendants.add(cls) 1320 1321 def all_class_attributes(self): 1322 return {} 1323 1324 def instance_attributes(self): 1325 return {} 1326 1327 def __repr__(self): 1328 return "UnresolvedName(%r, %r)" % (self.name, self.parent_name) 1329 1330 __shortrepr__ = __repr__ 1331 1332 def full_name(self): 1333 if self.name is not None: 1334 return self.parent_name + "." + self.name 1335 else: 1336 return self.parent_name 1337 1338 class Module(NamespaceDict, Constant): 1339 1340 "An inspected module's core details." 1341 1342 def __init__(self, name): 1343 NamespaceDict.__init__(self, self) 1344 self.name = name 1345 self.parent = None 1346 1347 # Original location details. 1348 1349 self.astnode = None 1350 1351 # Complete lists of classes and functions. 1352 1353 self.all_objects = set() 1354 1355 # Keyword records. 1356 1357 self.keyword_names = set() 1358 1359 # Image generation details. 1360 1361 self.location = None 1362 self.code_location = None 1363 1364 # Program-related details. 1365 1366 self.blocks = None 1367 self.temp_usage = 0 1368 self.local_usage = 0 1369 self.all_local_usage = 0 1370 1371 def full_name(self): 1372 return self.name 1373 1374 def __repr__(self): 1375 if self.location is not None: 1376 return "Module(%r, location=%r)" % (self.name, self.location) 1377 else: 1378 return "Module(%r)" % self.name 1379 1380 def __shortrepr__(self): 1381 return "Module(%r)" % self.name 1382 1383 # Attribute methods. 1384 1385 "Return the module attribute names provided by the module." 1386 1387 module_attribute_names = NamespaceDict.keys 1388 1389 def module_attributes(self): 1390 1391 "Return a dictionary mapping names to module attributes." 1392 1393 return dict(self) 1394 1395 # vim: tabstop=4 expandtab shiftwidth=4