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