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