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 910 # Superclasses, descendants and attributes. 911 912 self.bases = [] 913 self.descendants = set() 914 self.instattr = set() # instance attributes 915 self.relocated = set() # attributes which do not have the same 916 # position as those of the same name in 917 # some superclasses 918 919 # Caches. 920 921 self.reset_caches() 922 923 # Image generation details. 924 925 self.location = None 926 self.code_location = None 927 self.code_body_location = None # corresponds to the instantiator 928 929 self.instantiator = None 930 self.instance_template_location = None # for creating instances at run-time 931 932 # Program-related details. 933 934 self.blocks = None 935 self.temp_usage = 0 936 self.local_usage = 0 937 self.all_local_usage = 0 938 939 # Add this class to its attributes. 940 941 self.set("__class__", self) 942 943 def reset_caches(self): 944 945 "Reset the caches." 946 947 self.all_instattr = None # cache for instance_attributes 948 self.all_instattr_names = None # from all_instattr 949 self.all_classattr = None # cache for all_class_attributes 950 self.all_classattr_names = None # from all_classattr 951 self.allattr = None # cache for all_attributes 952 self.allattr_names = None # from allattr 953 954 def __repr__(self): 955 if self.location is not None: 956 return "Class(%r, %s, location=%r)" % (self.name, shortrepr(self.parent), self.location) 957 else: 958 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 959 960 def __shortrepr__(self): 961 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 962 963 def get_body_block(self): 964 return self.get_instantiator().blocks[0] 965 966 # Namespace-related methods. 967 968 def get_updated_context_values(self, context_values): 969 970 """ 971 Adapt the contexts found in the given 'context_values', returning a new 972 set. 973 See: docs/assignment.txt 974 """ 975 976 results = set() 977 978 for context, value in context_values: 979 980 # Change the ownership of functions. 981 982 if context is ReplaceableContext and value is not None and isinstance(value, Function): 983 results.add((self, value)) 984 else: 985 results.add((context, value)) 986 987 return NamespaceDict.get_updated_context_values(self, results) 988 989 # Administrative methods. 990 991 def finalise_attributes(self): 992 993 "Make sure that all attributes are fully defined." 994 995 if self.finalised: 996 return 997 998 self.finalise_class_attributes() 999 self.finalise_instance_attributes() 1000 self.finalised = 1 1001 1002 def unfinalise_attributes(self): 1003 1004 "Open attribute definitions to editing and subsequent finalisation." 1005 1006 self.reset_caches() 1007 self.finalised = 0 1008 1009 # Convenience methods for accessing functions and methods. 1010 1011 def get_instantiator(self): 1012 1013 "Return a function which can be used to instantiate the class." 1014 1015 if self.instantiator is None: 1016 self.instantiator = self.get_init_method().as_instantiator() 1017 return self.instantiator 1018 1019 def get_init_method(self): 1020 return self.all_class_attributes()["__init__"].get_value() 1021 1022 # Class-specific methods. 1023 1024 def add_base(self, base): 1025 self.bases.append(base) 1026 base.add_descendant(self) 1027 1028 def add_instance_attribute(self, name): 1029 self.instattr.add(name) 1030 1031 def add_descendant(self, cls): 1032 self.descendants.add(cls) 1033 for base in self.bases: 1034 base.add_descendant(cls) 1035 1036 def has_subclass(self, other): 1037 return other in self.descendants 1038 1039 def all_descendants(self): 1040 d = {} 1041 for cls in self.descendants: 1042 d[cls.full_name()] = cls 1043 return d 1044 1045 "Return the attribute names provided by this class only." 1046 1047 class_attribute_names = NamespaceDict.keys 1048 1049 def class_attributes(self): 1050 1051 "Return class attributes provided by this class only." 1052 1053 return dict(self) 1054 1055 def all_class_attribute_names(self): 1056 1057 "Return the attribute names provided by classes in this hierarchy." 1058 1059 if self.all_classattr_names is None: 1060 self.all_class_attributes() 1061 self.all_classattr_names = self.all_classattr.keys() 1062 return self.all_classattr_names 1063 1064 def all_class_attributes(self): 1065 1066 "Return all class attributes, indicating the class which provides them." 1067 1068 self.finalise_class_attributes() 1069 return self.all_classattr 1070 1071 def finalise_class_attributes(self): 1072 1073 "Make sure that the class attributes are fully defined." 1074 1075 if self.all_classattr is None: 1076 self.all_classattr = {} 1077 clsattr = {} 1078 1079 # Record provisional position information for attributes of this 1080 # class. 1081 1082 for name in self.class_attributes().keys(): 1083 clsattr[name] = set() # position not yet defined 1084 1085 reversed_bases = self.bases[:] 1086 reversed_bases.reverse() 1087 1088 # For the bases in reverse order, acquire class attribute details. 1089 1090 for cls in reversed_bases: 1091 for name, attr in cls.all_class_attributes().items(): 1092 self.all_classattr[name] = attr 1093 1094 # Record previous attribute information. 1095 1096 if clsattr.has_key(name): 1097 clsattr[name].add(attr.position) 1098 1099 # Record class attributes provided by this class and its bases, 1100 # along with their positions. 1101 1102 self.all_classattr.update(self.class_attributes()) 1103 1104 if clsattr: 1105 for i, name in enumerate(self._get_position_list(clsattr)): 1106 self.all_classattr[name].position = i 1107 1108 return self.all_classattr 1109 1110 def instance_attribute_names(self): 1111 1112 "Return the instance attribute names provided by the class." 1113 1114 if self.all_instattr_names is None: 1115 self.instance_attributes() 1116 return self.all_instattr_names 1117 1118 def instance_attributes(self): 1119 1120 "Return instance-only attributes for instances of this class." 1121 1122 self.finalise_instance_attributes() 1123 return self.all_instattr 1124 1125 def finalise_instance_attributes(self): 1126 1127 "Make sure that the instance attributes are fully defined." 1128 1129 # Cache the attributes by converting the positioned attributes into a 1130 # dictionary. 1131 1132 if self.all_instattr is None: 1133 self.all_instattr = self._get_attributes() 1134 self.all_instattr_names = self.all_instattr.keys() 1135 1136 return self.all_instattr 1137 1138 def _get_attributes(self): 1139 1140 """ 1141 Return a dictionary mapping names to Attr instances incorporating 1142 information about their positions in the final instance structure. 1143 """ 1144 1145 instattr = {} 1146 1147 # Record provisional position information for attributes of this 1148 # instance. 1149 1150 for name in self.instattr: 1151 instattr[name] = set() # position not yet defined 1152 1153 reversed_bases = self.bases[:] 1154 reversed_bases.reverse() 1155 1156 # For the bases in reverse order, acquire instance attribute 1157 # details. 1158 1159 for cls in reversed_bases: 1160 for name, attr in cls.instance_attributes().items(): 1161 1162 # Record previous attribute information. 1163 1164 if instattr.has_key(name): 1165 instattr[name].add(attr.position) 1166 else: 1167 instattr[name] = set([attr.position]) 1168 1169 # Build the dictionary of attributes using the existing positions known 1170 # for each name. 1171 1172 d = {} 1173 for i, name in enumerate(self._get_position_list(instattr)): 1174 d[name] = Attr(i, Instance(), name) 1175 return d 1176 1177 def _get_position_list(self, positions): 1178 1179 """ 1180 Return a list of attribute names for the given 'positions' mapping from 1181 names to positions, indicating the positions of the attributes in the 1182 final instance structure. 1183 """ 1184 1185 position_items = positions.items() 1186 namearray = [None] * len(position_items) 1187 1188 # Get the positions in ascending order of list size, with lists 1189 # of the same size ordered according to their smallest position 1190 # value. 1191 1192 position_items.sort(self._cmp_positions) 1193 1194 # Get the names in position order. 1195 1196 held = [] 1197 1198 for name, pos in position_items: 1199 pos = list(pos) 1200 pos.sort() 1201 if pos and pos[0] < len(namearray) and namearray[pos[0]] is None: 1202 namearray[pos[0]] = name 1203 else: 1204 if pos: 1205 self.relocated.add(name) 1206 held.append((name, pos)) 1207 1208 for i, attr in enumerate(namearray): 1209 if attr is None: 1210 name, pos = held.pop() 1211 namearray[i] = name 1212 1213 return namearray 1214 1215 def _cmp_positions(self, a, b): 1216 1217 "Compare name plus position list operands 'a' and 'b'." 1218 1219 name_a, list_a = a 1220 name_b, list_b = b 1221 if len(list_a) < len(list_b): 1222 return -1 1223 elif len(list_a) > len(list_b): 1224 return 1 1225 elif not list_a: 1226 return 0 1227 else: 1228 return cmp(min(list_a), min(list_b)) 1229 1230 def all_attribute_names(self): 1231 1232 """ 1233 Return the names of all attributes provided by instances of this class. 1234 """ 1235 1236 self.allattr_names = self.allattr_names or self.all_attributes().keys() 1237 return self.allattr_names 1238 1239 def all_attributes(self): 1240 1241 """ 1242 Return all attributes for an instance, indicating either the class which 1243 provides them or that the instance itself provides them. 1244 """ 1245 1246 if self.allattr is None: 1247 self.allattr = {} 1248 self.allattr.update(self.all_class_attributes()) 1249 for name, attr in self.instance_attributes().items(): 1250 if self.allattr.has_key(name): 1251 print "Instance attribute %r in %r overrides class attribute." % (name, self) 1252 self.allattr[name] = attr 1253 return self.allattr 1254 1255 class Function(NamespaceDict, Naming, Constant): 1256 1257 "An inspected function." 1258 1259 def __init__(self, name, parent, argnames, defaults, has_star, has_dstar, 1260 dynamic_def=0, module=None, node=None): 1261 1262 """ 1263 Initialise the function with the given 'name', 'parent', list of 1264 'argnames', list of 'defaults', the 'has_star' flag (indicating the 1265 presence of a * parameter), the 'has_dstar' flag (indicating the 1266 presence of a ** parameter), optional 'dynamic_def' (indicating that the 1267 function must be handled dynamically), optional 'module', and optional 1268 AST 'node'. 1269 """ 1270 1271 NamespaceDict.__init__(self, module) 1272 1273 if name is None: 1274 self.name = "lambda#%d" % new_lambda() 1275 self._is_lambda = 1 1276 else: 1277 self.name = name 1278 self._is_lambda = 0 1279 1280 self.parent = parent 1281 self.argnames = argnames 1282 self.defaults = defaults 1283 self.has_star = has_star 1284 self.has_dstar = has_dstar 1285 self.dynamic_def = dynamic_def 1286 self.astnode = node 1287 1288 # Initialise the positional names. 1289 1290 self.positional_names = self.argnames[:] 1291 if has_dstar: 1292 self.dstar_name = self.positional_names[-1] 1293 del self.positional_names[-1] 1294 if has_star: 1295 self.star_name = self.positional_names[-1] 1296 del self.positional_names[-1] 1297 1298 # Initialise default storage. 1299 # NOTE: This must be initialised separately due to the reliance on node 1300 # NOTE: visiting. 1301 1302 self.default_attrs = [] 1303 1304 # Initialise attribute usage. 1305 1306 for arg in argnames: 1307 1308 # Define attribute users. 1309 1310 if node is not None: 1311 self._define_attribute_user_for_name(node, arg) 1312 1313 # Or just record the usage. 1314 1315 else: 1316 self.attributes_used[-1][arg] = set() 1317 1318 # Caches. 1319 1320 self.localnames = None # cache for locals 1321 1322 # Add parameters to the namespace. 1323 1324 self._add_parameters(argnames) 1325 1326 # Image generation details. 1327 1328 self.dynamic = None 1329 self.location = None 1330 self.code_location = None 1331 self.code_body_location = None 1332 1333 # Program-related details. 1334 1335 self.blocks = None 1336 self.body_block = None 1337 1338 self.temp_usage = 0 1339 self.local_usage = 0 1340 self.all_local_usage = 0 1341 1342 def _add_parameters(self, argnames): 1343 for name in argnames: 1344 if isinstance(name, tuple): 1345 self._add_parameters(name) 1346 else: 1347 self.set(name, Instance()) 1348 1349 def __repr__(self): 1350 if self.location is not None: 1351 return "Function(%r, %s, %r, location=%r, code_location=%r)" % ( 1352 self.name, shortrepr(self.parent), self.argnames, self.location, self.code_location 1353 ) 1354 else: 1355 return "Function(%r, %s, %r)" % ( 1356 self.name, shortrepr(self.parent), self.argnames 1357 ) 1358 1359 def __shortrepr__(self): 1360 return "Function(%r, %s)" % ( 1361 self.name, shortrepr(self.parent) 1362 ) 1363 1364 def get_body_block(self): 1365 return self.body_block 1366 1367 def is_lambda(self): 1368 return self._is_lambda 1369 1370 # Defaults-related methods. 1371 1372 def store_default(self, attr_or_value): 1373 1374 """ 1375 Reserve space for defaults, set outside the function, potentially on a 1376 dynamic basis, using the 'attr_or_value'. 1377 """ 1378 1379 attr = Attr(None, self, None) 1380 self._set_using_attr(attr, attr_or_value) 1381 self.default_attrs.append(attr) 1382 1383 def make_dynamic(self): 1384 1385 "Return whether this function must be handled using a dynamic object." 1386 1387 if self.dynamic is None: 1388 for attr in self.default_attrs: 1389 if not attr.is_strict_constant() and self.dynamic_def: 1390 self.dynamic = 1 1391 self._make_dynamic() 1392 break 1393 else: 1394 self.dynamic = 0 1395 1396 return self.dynamic 1397 1398 is_dynamic = make_dynamic 1399 1400 def _make_dynamic(self): 1401 1402 "Where functions have dynamic defaults, add a context argument." 1403 1404 name = "<context>" 1405 self.argnames.insert(0, name) 1406 self.positional_names.insert(0, name) 1407 self.set(name, Instance()) 1408 1409 # Namespace-related methods. 1410 1411 def make_global(self, name): 1412 1413 "Declare 'name' as a global in the current namespace." 1414 1415 if name not in self.argnames and not self.has_key(name): 1416 self.globals.add(name) 1417 return 1 1418 else: 1419 return 0 1420 1421 def parameters(self): 1422 1423 """ 1424 Return a dictionary mapping parameter names to their position in the 1425 parameter list. 1426 """ 1427 1428 parameters = {} 1429 for i, name in enumerate(self.argnames): 1430 parameters[name] = i 1431 return parameters 1432 1433 def all_locals(self): 1434 1435 "Return a dictionary mapping names to local and parameter details." 1436 1437 return dict(self) 1438 1439 def locals(self): 1440 1441 "Return a dictionary mapping names to local details." 1442 1443 if self.localnames is None: 1444 self.localnames = {} 1445 self.localnames.update(self.all_locals()) 1446 for name in self.argnames: 1447 del self.localnames[name] 1448 return self.localnames 1449 1450 def is_method(self): 1451 1452 """ 1453 Return whether this function is a method explicitly defined in a class. 1454 """ 1455 1456 return isinstance(self.parent, Class) 1457 1458 def is_relocated(self, name): 1459 1460 """ 1461 Determine whether the given attribute 'name' is relocated for instances 1462 having this function as a method. 1463 """ 1464 1465 for cls in self.parent.descendants: 1466 if name in cls.relocated: 1467 return 1 1468 return 0 1469 1470 # Administrative methods. 1471 1472 def items_for_vacuum(self): 1473 return self.lambdas.items() 1474 1475 def vacuum_item(self, name): 1476 del self.lambdas[name] 1477 1478 def finalise_attributes(self): 1479 1480 """ 1481 Make sure all attributes (locals) are fully defined. Note that locals 1482 are not attributes in the sense of class, module or instance attributes. 1483 Defaults are also finalised by this method. 1484 """ 1485 1486 if self.finalised: 1487 return 1488 1489 # Defaults. 1490 1491 for i, default in enumerate(self.default_attrs): 1492 default.position = i 1493 1494 # Locals. 1495 1496 i = None 1497 for i, name in enumerate(self.argnames): 1498 self[name].position = i 1499 1500 if i is not None: 1501 nparams = i + 1 1502 else: 1503 nparams = 0 1504 1505 i = None 1506 for i, attr in enumerate(self.locals().values()): 1507 attr.position = i + nparams 1508 1509 if i is not None: 1510 nothers = i + 1 1511 else: 1512 nothers = 0 1513 1514 self.local_usage = nothers 1515 self.all_local_usage = nparams + nothers 1516 self.finalised = 1 1517 1518 def as_instantiator(self): 1519 1520 "Make an instantiator function from a method, keeping all arguments." 1521 1522 function = Function(self.parent.name, self.parent.parent, self.argnames, self.defaults, 1523 self.has_star, self.has_dstar, self.dynamic_def, self.module, self.astnode) 1524 function.default_attrs = self.default_attrs 1525 return function 1526 1527 class UnresolvedName(NamespaceDict, Constant): 1528 1529 "A module, class or function which was mentioned but could not be imported." 1530 1531 def __init__(self, name, parent_name, module=None): 1532 NamespaceDict.__init__(self, module) 1533 self.name = name 1534 self.parent_name = parent_name 1535 self.parent = None 1536 1537 self.descendants = set() 1538 1539 def add_descendant(self, cls): 1540 self.descendants.add(cls) 1541 1542 def all_class_attributes(self): 1543 return {} 1544 1545 def instance_attributes(self): 1546 return {} 1547 1548 def __repr__(self): 1549 return "UnresolvedName(%r, %r)" % (self.name, self.parent_name) 1550 1551 __shortrepr__ = __repr__ 1552 1553 def full_name(self): 1554 if self.name is not None: 1555 return self.parent_name + "." + self.name 1556 else: 1557 return self.parent_name 1558 1559 class Module(NamespaceDict, Constant): 1560 1561 "An inspected module's core details." 1562 1563 def __init__(self, name, importer): 1564 NamespaceDict.__init__(self, self) 1565 self.name = name 1566 self.importer = importer 1567 self.parent = None 1568 1569 # Original location details. 1570 1571 self.astnode = None 1572 1573 # Complete lists of classes and functions. 1574 1575 self.all_objects = set() 1576 1577 # Keyword records. 1578 1579 self.keyword_names = set() 1580 1581 # Image generation details. 1582 1583 self.location = None 1584 self.code_location = None 1585 1586 # Program-related details. 1587 1588 self.blocks = None 1589 self.temp_usage = 0 1590 self.local_usage = 0 1591 self.all_local_usage = 0 1592 1593 def full_name(self): 1594 return self.name 1595 1596 def __repr__(self): 1597 if self.location is not None: 1598 return "Module(%r, location=%r)" % (self.name, self.location) 1599 else: 1600 return "Module(%r)" % self.name 1601 1602 def __shortrepr__(self): 1603 return "Module(%r)" % self.name 1604 1605 # Attribute methods. 1606 1607 "Return the module attribute names provided by the module." 1608 1609 module_attribute_names = NamespaceDict.keys 1610 1611 def module_attributes(self): 1612 1613 "Return a dictionary mapping names to module attributes." 1614 1615 return dict(self) 1616 1617 # vim: tabstop=4 expandtab shiftwidth=4