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