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