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