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 730 # Superclasses, descendants and attributes. 731 732 self.bases = [] 733 self.descendants = set() 734 self.instattr = set() # instance attributes 735 self.relocated = set() # attributes which do not have the same 736 # position as those of the same name in 737 # some superclasses 738 739 # Caches. 740 741 self.reset_caches() 742 743 # Image generation details. 744 745 self.location = None 746 self.code_location = None 747 self.code_body_location = None # corresponds to the instantiator 748 749 self.instantiator = None 750 self.instance_template_location = None # for creating instances at run-time 751 752 # Program-related details. 753 754 self.blocks = None 755 self.temp_usage = 0 756 self.local_usage = 0 757 self.all_local_usage = 0 758 759 # Add this class to its attributes. 760 761 self.set("__class__", self) 762 763 def reset_caches(self): 764 765 "Reset the caches." 766 767 self.all_instattr = None # cache for instance_attributes 768 self.all_instattr_names = None # from all_instattr 769 self.all_classattr = None # cache for all_class_attributes 770 self.all_classattr_names = None # from all_classattr 771 self.allattr = None # cache for all_attributes 772 self.allattr_names = None # from allattr 773 774 def __repr__(self): 775 if self.location is not None: 776 return "Class(%r, %s, location=%r)" % (self.name, shortrepr(self.parent), self.location) 777 else: 778 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 779 780 def __shortrepr__(self): 781 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 782 783 def get_body_block(self): 784 return self.get_instantiator().blocks[0] 785 786 # Namespace-related methods. 787 788 def get_updated_context_values(self, context_values): 789 790 """ 791 Adapt the contexts found in the given 'context_values', returning a new 792 set. 793 See: docs/assignment.txt 794 """ 795 796 results = set() 797 798 for context, value in context_values: 799 800 # Change the ownership of functions. 801 802 if context is ReplaceableContext and value is not None and isinstance(value, Function): 803 results.add((self, value)) 804 else: 805 results.add((context, value)) 806 807 return NamespaceDict.get_updated_context_values(self, results) 808 809 def finalise_attributes(self): 810 811 "Make sure that all attributes are fully defined." 812 813 if self.finalised: 814 return 815 816 self.finalise_class_attributes() 817 self.finalise_instance_attributes() 818 self.finalised = 1 819 820 def unfinalise_attributes(self): 821 822 "Open attribute definitions to editing and subsequent finalisation." 823 824 self.reset_caches() 825 self.finalised = 0 826 827 # Convenience methods for accessing functions and methods. 828 829 def get_instantiator(self): 830 831 "Return a function which can be used to instantiate the class." 832 833 if self.instantiator is None: 834 self.instantiator = self.get_init_method().as_instantiator() 835 return self.instantiator 836 837 def get_init_method(self): 838 return self.all_class_attributes()["__init__"].get_value() 839 840 # Class-specific methods. 841 842 def add_base(self, base): 843 self.bases.append(base) 844 base.add_descendant(self) 845 846 def add_instance_attribute(self, name): 847 self.instattr.add(name) 848 849 def add_descendant(self, cls): 850 self.descendants.add(cls) 851 for base in self.bases: 852 base.add_descendant(cls) 853 854 def has_subclass(self, other): 855 return other in self.descendants 856 857 def all_descendants(self): 858 d = {} 859 for cls in self.descendants: 860 d[cls.full_name()] = cls 861 return d 862 863 "Return the attribute names provided by this class only." 864 865 class_attribute_names = NamespaceDict.keys 866 867 def class_attributes(self): 868 869 "Return class attributes provided by this class only." 870 871 return dict(self) 872 873 def all_class_attribute_names(self): 874 875 "Return the attribute names provided by classes in this hierarchy." 876 877 if self.all_classattr_names is None: 878 self.all_class_attributes() 879 self.all_classattr_names = self.all_classattr.keys() 880 return self.all_classattr_names 881 882 def all_class_attributes(self): 883 884 "Return all class attributes, indicating the class which provides them." 885 886 self.finalise_class_attributes() 887 return self.all_classattr 888 889 def finalise_class_attributes(self): 890 891 "Make sure that the class attributes are fully defined." 892 893 if self.all_classattr is None: 894 self.all_classattr = {} 895 clsattr = {} 896 897 # Record provisional position information for attributes of this 898 # class. 899 900 for name in self.class_attributes().keys(): 901 clsattr[name] = set() # position not yet defined 902 903 reversed_bases = self.bases[:] 904 reversed_bases.reverse() 905 906 # For the bases in reverse order, acquire class attribute details. 907 908 for cls in reversed_bases: 909 for name, attr in cls.all_class_attributes().items(): 910 self.all_classattr[name] = attr 911 912 # Record previous attribute information. 913 914 if clsattr.has_key(name): 915 clsattr[name].add(attr.position) 916 917 # Record class attributes provided by this class and its bases, 918 # along with their positions. 919 920 self.all_classattr.update(self.class_attributes()) 921 922 if clsattr: 923 for i, name in enumerate(self._get_position_list(clsattr)): 924 self.all_classattr[name].position = i 925 926 return self.all_classattr 927 928 def instance_attribute_names(self): 929 930 "Return the instance attribute names provided by the class." 931 932 if self.all_instattr_names is None: 933 self.instance_attributes() 934 return self.all_instattr_names 935 936 def instance_attributes(self): 937 938 "Return instance-only attributes for instances of this class." 939 940 self.finalise_instance_attributes() 941 return self.all_instattr 942 943 def finalise_instance_attributes(self): 944 945 "Make sure that the instance attributes are fully defined." 946 947 # Cache the attributes by converting the positioned attributes into a 948 # dictionary. 949 950 if self.all_instattr is None: 951 self.all_instattr = self._get_attributes() 952 self.all_instattr_names = self.all_instattr.keys() 953 954 return self.all_instattr 955 956 def _get_attributes(self): 957 958 """ 959 Return a dictionary mapping names to Attr instances incorporating 960 information about their positions in the final instance structure. 961 """ 962 963 instattr = {} 964 965 # Record provisional position information for attributes of this 966 # instance. 967 968 for name in self.instattr: 969 instattr[name] = set() # position not yet defined 970 971 reversed_bases = self.bases[:] 972 reversed_bases.reverse() 973 974 # For the bases in reverse order, acquire instance attribute 975 # details. 976 977 for cls in reversed_bases: 978 for name, attr in cls.instance_attributes().items(): 979 980 # Record previous attribute information. 981 982 if instattr.has_key(name): 983 instattr[name].add(attr.position) 984 else: 985 instattr[name] = set([attr.position]) 986 987 # Build the dictionary of attributes using the existing positions known 988 # for each name. 989 990 d = {} 991 for i, name in enumerate(self._get_position_list(instattr)): 992 d[name] = Attr(i, Instance(), name) 993 return d 994 995 def _get_position_list(self, positions): 996 997 """ 998 Return a list of attribute names for the given 'positions' mapping from 999 names to positions, indicating the positions of the attributes in the 1000 final instance structure. 1001 """ 1002 1003 position_items = positions.items() 1004 namearray = [None] * len(position_items) 1005 1006 # Get the positions in ascending order of list size, with lists 1007 # of the same size ordered according to their smallest position 1008 # value. 1009 1010 position_items.sort(self._cmp_positions) 1011 1012 # Get the names in position order. 1013 1014 held = [] 1015 1016 for name, pos in position_items: 1017 pos = list(pos) 1018 pos.sort() 1019 if pos and pos[0] < len(namearray) and namearray[pos[0]] is None: 1020 namearray[pos[0]] = name 1021 else: 1022 if pos: 1023 self.relocated.add(name) 1024 held.append((name, pos)) 1025 1026 for i, attr in enumerate(namearray): 1027 if attr is None: 1028 name, pos = held.pop() 1029 namearray[i] = name 1030 1031 return namearray 1032 1033 def _cmp_positions(self, a, b): 1034 1035 "Compare name plus position list operands 'a' and 'b'." 1036 1037 name_a, list_a = a 1038 name_b, list_b = b 1039 if len(list_a) < len(list_b): 1040 return -1 1041 elif len(list_a) > len(list_b): 1042 return 1 1043 elif not list_a: 1044 return 0 1045 else: 1046 return cmp(min(list_a), min(list_b)) 1047 1048 def all_attribute_names(self): 1049 1050 """ 1051 Return the names of all attributes provided by instances of this class. 1052 """ 1053 1054 self.allattr_names = self.allattr_names or self.all_attributes().keys() 1055 return self.allattr_names 1056 1057 def all_attributes(self): 1058 1059 """ 1060 Return all attributes for an instance, indicating either the class which 1061 provides them or that the instance itself provides them. 1062 """ 1063 1064 if self.allattr is None: 1065 self.allattr = {} 1066 self.allattr.update(self.all_class_attributes()) 1067 for name, attr in self.instance_attributes().items(): 1068 if self.allattr.has_key(name): 1069 print "Instance attribute %r in %r overrides class attribute." % (name, self) 1070 self.allattr[name] = attr 1071 return self.allattr 1072 1073 class Function(NamespaceDict, Naming, Constant): 1074 1075 "An inspected function." 1076 1077 def __init__(self, name, parent, argnames, defaults, has_star, has_dstar, module=None, node=None): 1078 1079 """ 1080 Initialise the function with the given 'name', 'parent', list of 1081 'argnames', list of 'defaults', the 'has_star' flag (indicating the 1082 presence of a * parameter), the 'has_dstar' flag (indicating the 1083 presence of a ** parameter), optional 'module', and optional AST 'node'. 1084 """ 1085 1086 NamespaceDict.__init__(self, module) 1087 self.name = name 1088 self.parent = parent 1089 self.argnames = argnames 1090 self.defaults = defaults 1091 self.has_star = has_star 1092 self.has_dstar = has_dstar 1093 self.astnode = node 1094 1095 # For lambda functions with defaults, add a context argument. 1096 1097 if name is None and defaults: 1098 self.argnames.insert(0, "<context>") 1099 1100 # Initialise the positional names. 1101 1102 self.positional_names = self.argnames[:] 1103 if has_dstar: 1104 self.dstar_name = self.positional_names[-1] 1105 del self.positional_names[-1] 1106 if has_star: 1107 self.star_name = self.positional_names[-1] 1108 del self.positional_names[-1] 1109 1110 # Initialise default storage. 1111 # NOTE: This must be initialised separately due to the reliance on node 1112 # NOTE: visiting. 1113 1114 self.default_attrs = [] 1115 1116 # Initialise attribute usage. 1117 1118 for arg in argnames: 1119 1120 # Define attribute users. 1121 1122 if node is not None: 1123 self._define_attribute_user_for_name(node, arg) 1124 1125 # Or just record the usage. 1126 1127 else: 1128 self.attributes_used[-1][arg] = set() 1129 1130 # Caches. 1131 1132 self.localnames = None # cache for locals 1133 1134 # Add parameters to the namespace. 1135 1136 self._add_parameters(argnames) 1137 1138 # Image generation details. 1139 1140 self.location = None 1141 self.code_location = None 1142 self.code_body_location = None 1143 1144 # Program-related details. 1145 1146 self.blocks = None 1147 self.body_block = None 1148 1149 self.temp_usage = 0 1150 self.local_usage = 0 1151 self.all_local_usage = 0 1152 1153 def _add_parameters(self, argnames): 1154 for name in argnames: 1155 if isinstance(name, tuple): 1156 self._add_parameters(name) 1157 else: 1158 self.set(name, None) 1159 1160 def __repr__(self): 1161 if self.location is not None: 1162 return "Function(%r, %s, %r, location=%r, code_location=%r)" % ( 1163 self.name, shortrepr(self.parent), self.argnames, self.location, self.code_location 1164 ) 1165 else: 1166 return "Function(%r, %s, %r)" % ( 1167 self.name, shortrepr(self.parent), self.argnames 1168 ) 1169 1170 def __shortrepr__(self): 1171 return "Function(%r, %s)" % ( 1172 self.name, shortrepr(self.parent) 1173 ) 1174 1175 def get_body_block(self): 1176 return self.body_block 1177 1178 # Namespace-related methods. 1179 1180 def store_default(self, value): 1181 attr = Attr(None, self, None) 1182 attr.update([self.get_context_and_value(value)], 1) 1183 self.default_attrs.append(attr) 1184 1185 def make_global(self, name): 1186 if name not in self.argnames and not self.has_key(name): 1187 self.globals.add(name) 1188 return 1 1189 else: 1190 return 0 1191 1192 def parameters(self): 1193 1194 """ 1195 Return a dictionary mapping parameter names to their position in the 1196 parameter list. 1197 """ 1198 1199 parameters = {} 1200 for i, name in enumerate(self.argnames): 1201 parameters[name] = i 1202 return parameters 1203 1204 def all_locals(self): 1205 1206 "Return a dictionary mapping names to local and parameter details." 1207 1208 return dict(self) 1209 1210 def locals(self): 1211 1212 "Return a dictionary mapping names to local details." 1213 1214 if self.localnames is None: 1215 self.localnames = {} 1216 self.localnames.update(self.all_locals()) 1217 for name in self.argnames: 1218 del self.localnames[name] 1219 return self.localnames 1220 1221 def is_method(self): 1222 1223 """ 1224 Return whether this function is a method explicitly defined in a class. 1225 """ 1226 1227 return isinstance(self.parent, Class) 1228 1229 def is_relocated(self, name): 1230 1231 """ 1232 Determine whether the given attribute 'name' is relocated for instances 1233 having this function as a method. 1234 """ 1235 1236 for cls in self.parent.descendants: 1237 if name in cls.relocated: 1238 return 1 1239 return 0 1240 1241 def finalise_attributes(self): 1242 1243 """ 1244 Make sure all attributes (locals) are fully defined. Note that locals 1245 are not attributes in the sense of class, module or instance attributes. 1246 Defaults are also finalised by this method. 1247 """ 1248 1249 if self.finalised: 1250 return 1251 1252 # Defaults. 1253 1254 for i, default in enumerate(self.default_attrs): 1255 default.position = i 1256 1257 # Locals. 1258 1259 i = None 1260 for i, name in enumerate(self.argnames): 1261 self[name].position = i 1262 1263 if i is not None: 1264 nparams = i + 1 1265 else: 1266 nparams = 0 1267 1268 i = None 1269 for i, attr in enumerate(self.locals().values()): 1270 attr.position = i + nparams 1271 1272 if i is not None: 1273 nothers = i + 1 1274 else: 1275 nothers = 0 1276 1277 self.local_usage = nothers 1278 self.all_local_usage = nparams + nothers 1279 self.finalised = 1 1280 1281 def as_instantiator(self): 1282 1283 "Make an instantiator function from a method, keeping all arguments." 1284 1285 function = Function(self.parent.name, self.parent.parent, self.argnames, self.defaults, 1286 self.has_star, self.has_dstar, self.module, self.astnode) 1287 function.default_attrs = self.default_attrs 1288 return function 1289 1290 class UnresolvedName(NamespaceDict, Constant): 1291 1292 "A module, class or function which was mentioned but could not be imported." 1293 1294 def __init__(self, name, parent_name, module=None): 1295 NamespaceDict.__init__(self, module) 1296 self.name = name 1297 self.parent_name = parent_name 1298 self.parent = None 1299 1300 self.descendants = set() 1301 1302 def add_descendant(self, cls): 1303 self.descendants.add(cls) 1304 1305 def all_class_attributes(self): 1306 return {} 1307 1308 def instance_attributes(self): 1309 return {} 1310 1311 def __repr__(self): 1312 return "UnresolvedName(%r, %r)" % (self.name, self.parent_name) 1313 1314 __shortrepr__ = __repr__ 1315 1316 def full_name(self): 1317 if self.name is not None: 1318 return self.parent_name + "." + self.name 1319 else: 1320 return self.parent_name 1321 1322 class Module(NamespaceDict, Constant): 1323 1324 "An inspected module's core details." 1325 1326 def __init__(self, name): 1327 NamespaceDict.__init__(self, self) 1328 self.name = name 1329 self.parent = None 1330 1331 # Original location details. 1332 1333 self.astnode = None 1334 1335 # Complete lists of classes and functions. 1336 1337 self.all_objects = set() 1338 1339 # Keyword records. 1340 1341 self.keyword_names = set() 1342 1343 # Image generation details. 1344 1345 self.location = None 1346 self.code_location = None 1347 1348 # Program-related details. 1349 1350 self.blocks = None 1351 self.temp_usage = 0 1352 self.local_usage = 0 1353 self.all_local_usage = 0 1354 1355 def full_name(self): 1356 return self.name 1357 1358 def __repr__(self): 1359 if self.location is not None: 1360 return "Module(%r, location=%r)" % (self.name, self.location) 1361 else: 1362 return "Module(%r)" % self.name 1363 1364 def __shortrepr__(self): 1365 return "Module(%r)" % self.name 1366 1367 # Attribute methods. 1368 1369 "Return the module attribute names provided by the module." 1370 1371 module_attribute_names = NamespaceDict.keys 1372 1373 def module_attributes(self): 1374 1375 "Return a dictionary mapping names to module attributes." 1376 1377 return dict(self) 1378 1379 # vim: tabstop=4 expandtab shiftwidth=4