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