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