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