1 #!/usr/bin/env python 2 3 """ 4 Data classes. 5 6 Copyright (C) 2007, 2008 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 21 -------- 22 23 The central classes in this module are the following: 24 25 * Class 26 * Function 27 * Module 28 29 All of the above support the Naming interface either explicitly or through 30 general conformance, meaning that all can be asked to provide their 'full_name' 31 using the method of that name. 32 33 Additionally, all of the above also support a dictionary interface in order to 34 access names within their defined scopes. Specific methods also exist in order 35 to distinguish between certain kinds of attributes: 36 37 * Class: (class|all_class|instance|all)_attributes 38 * Function: parameters, locals, all_locals 39 * Module: module_attributes 40 41 These specific methods are useful in certain situations. 42 43 The above classes also provide an 'astnode' attribute, indicating the AST node 44 where each such object is defined. 45 """ 46 47 from micropython.common import * 48 49 def shortrepr(obj): 50 if obj is None: 51 return repr(None) 52 else: 53 return obj.__shortrepr__() 54 55 # Mix-ins and abstract classes. 56 57 class NamespaceDict: 58 59 "A mix-in providing dictionary methods." 60 61 def __init__(self, global_namespace=None): 62 self.namespace = {} 63 self.globals = set() 64 self.global_namespace = global_namespace 65 self.finalised = 0 66 67 def __getitem__(self, name): 68 return self.namespace[name] 69 70 def get(self, name, default=None): 71 return self.namespace.get(name, default) 72 73 def __setitem__(self, name, value): 74 self.set(name, value) 75 76 def set(self, name, value, single_assignment=1): 77 78 """ 79 A more powerful set operation, making 'name' refer to 'value' whilst 80 indicating whether a 'single_assignment' (true by default) occurs in 81 this operation (or whether the operation covers potentially many 82 assignments in the lifetime of a program). 83 """ 84 85 if name in self.globals: 86 self.global_namespace.set(name, value, 0) 87 else: 88 attr = self._set(name, value) 89 attr.update(attr.value, single_assignment) 90 91 def set_module(self, name, value): 92 93 """ 94 A specialised set operation, making 'name' refer to 'value' in the 95 context of making a module reference available in association with 96 'name' as part of the import of that module or a submodule of that 97 module. 98 """ 99 100 attr = self._set(name, value) 101 if attr.assignments is None: 102 attr.assignments = 1 103 attr.assignment_values.add(attr.value) 104 105 def _set(self, name, value): 106 107 "The underlying set operation associating 'name' with 'value'." 108 109 if not self.namespace.has_key(name): 110 111 # Either accept the attribute as specified. 112 113 if isinstance(value, Attr): 114 if value.context is not None: 115 self.namespace[name] = Attr(None, self, value.context, name, value.value) 116 return self.namespace[name] 117 else: 118 value = value.value 119 120 # Or attempt to fix the context. 121 122 context = self._context(value) 123 self.namespace[name] = Attr(None, self, context, name, value) 124 125 return self.namespace[name] 126 127 def _context(self, value): 128 129 """ 130 Return the context to be used when storing the given 'value'. 131 NOTE: This context is not likely to be useful when preparing an image 132 NOTE: since only instance contexts have significant effects at run-time. 133 """ 134 135 return None 136 137 def __delitem__(self, name): 138 del self.namespace[name] 139 140 def has_key(self, name): 141 return self.namespace.has_key(name) 142 143 def keys(self): 144 return self.namespace.keys() 145 146 def values(self): 147 return self.namespace.values() 148 149 def items(self): 150 return self.namespace.items() 151 152 def make_global(self, name): 153 if not self.namespace.has_key(name): 154 self.globals.add(name) 155 else: 156 raise InspectError(self.full_name(), self.astnode, "Name %r is both global and local in %r" % (name, self.full_name())) 157 158 def get_assignments(self, name): 159 if self.assignments.has_key(name): 160 return max(self.assignments[name], len(self.assignment_values[name])) 161 else: 162 return None 163 164 def attributes_as_list(self): 165 166 "Return the attributes in a list." 167 168 self.finalise_attributes() 169 l = [None] * len(self.keys()) 170 for attr in self.values(): 171 l[attr.position] = attr 172 return l 173 174 def finalise_attributes(self): 175 176 "Make sure all attributes are fully defined." 177 178 if self.finalised: 179 return 180 181 # The default action is to assign attribute positions sequentially. 182 183 for i, attr in enumerate(self.values()): 184 attr.position = i 185 186 self.finalised = 1 187 188 # Program data structures. There are two separate kinds of structures: those 189 # with context, which are the values manipulated by programs, and those without 190 # context, which are typically constant things which are stored alongside the 191 # program but which are wrapped in context-dependent structures in the running 192 # program. 193 194 class Attr: 195 196 "An attribute entry having a context." 197 198 def __init__(self, position, parent, context, name, value=None, assignments=None): 199 200 """ 201 Initialise the attribute with the given 'position' within the collection 202 of attributes of its 'parent', indicating the 'context' or origin of the 203 attribute (where it was first defined), along with its 'name'. 204 205 An optional 'value' indicates the typical contents of the attribute, and 206 the optional number of 'assignments' may be used to determine whether 207 the attribute is effectively constant. 208 """ 209 210 self.position = position 211 self.parent = parent 212 self.context = context 213 self.name = name 214 self.value = value 215 216 # Number of assignments per name. 217 218 self.assignments = assignments 219 self.assignment_values = set() 220 221 def update(self, value, single_assignment): 222 223 """ 224 Update the attribute, adding the 'value' provided to the known values 225 associated with the attribute, changing the number of assignments 226 according to the 'single_assignment' status of the operation, where 227 a true value indicates that only one assignment is associated with the 228 update, and a false value indicates that potentially many assignments 229 may be involved. 230 """ 231 232 if self.assignments is None: 233 if single_assignment: 234 self.assignments = 1 235 else: 236 self.assignments = AtLeast(1) 237 else: 238 if single_assignment: 239 self.assignments += 1 240 else: 241 self.assignments += AtLeast(1) 242 243 if value is not None: 244 self.assignment_values.add(value) 245 246 def via_instance(self): 247 248 """ 249 Return either this attribute or a replacement where it is being accessed 250 via an instance. 251 """ 252 253 if self.context is not None: 254 255 # Check compatibility of the context with the parent. 256 # Where the attribute originates within the same hierarchy, use an 257 # instance as the context. 258 259 if self.defined_within_hierarchy(): 260 context = Instance() 261 262 # Otherwise, preserve the existing context. 263 264 else: 265 context = self.context 266 267 return Attr(self.position, self.parent, context, self.name, self.value, self.assignments) 268 269 # Unknown contexts remain in use. 270 271 else: 272 return self 273 274 def is_class_attribute(self): 275 return isinstance(self.parent, Class) 276 277 def defined_within_hierarchy(self): 278 279 """ 280 Return whether the parent and context of the attribute belong to the 281 same class hierarchy. 282 """ 283 284 return isinstance(self.parent, Class) and isinstance(self.context, Class) and ( 285 self.context is self.parent or 286 self.context.has_subclass(self.parent) or 287 self.parent.has_subclass(self.context)) 288 289 def __repr__(self): 290 return "Attr(%r, %s, %s, %r, %s, %r)" % ( 291 self.position, shortrepr(self.parent), shortrepr(self.context), 292 self.name, shortrepr(self.value), self.assignments 293 ) 294 295 # Instances are special in that they need to be wrapped together with context in 296 # a running program, but they are not generally constant. 297 298 class Instance: 299 300 "A placeholder indicating the involvement of an instance." 301 302 def __init__(self): 303 self.parent = None 304 305 # Image generation details. 306 307 self.location = None 308 309 def __repr__(self): 310 return "Instance()" 311 312 __shortrepr__ = __repr__ 313 314 class Constant: 315 316 "A superclass for all constant or context-free structures." 317 318 pass 319 320 class Const(Constant, Instance): 321 322 "A constant object with no context." 323 324 def __init__(self, value): 325 self.value = value 326 self.parent = None 327 328 def __repr__(self): 329 if self.location is not None: 330 return "Const(%r, location=%r)" % (self.value, self.location) 331 else: 332 return "Const(%r)" % self.value 333 334 __shortrepr__ = __repr__ 335 336 # Support constants as dictionary keys in order to build constant tables. 337 338 def __eq__(self, other): 339 return self.value == other.value 340 341 def __hash__(self): 342 return hash(self.value) 343 344 def value_type_name(self): 345 return "__builtins__." + self.value.__class__.__name__ 346 347 class Class(NamespaceDict, Naming, Constant): 348 349 "An inspected class." 350 351 def __init__(self, name, parent, global_namespace=None, node=None): 352 353 """ 354 Initialise the class with the given 'name', 'parent' object, optional 355 'global_namespace' and optional AST 'node'. 356 """ 357 358 NamespaceDict.__init__(self, global_namespace) 359 self.name = name 360 self.parent = parent 361 self.astnode = node 362 363 # Superclasses, descendants and attributes. 364 365 self.bases = [] 366 self.descendants = set() 367 self.instattr = set() # instance attributes 368 self.relocated = set() # attributes which do not have the same 369 # position as those of the same name in 370 # some superclasses 371 372 # Caches. 373 374 self.all_instattr = None # cache for instance_attributes 375 self.all_instattr_names = None # from all_instattr 376 self.all_classattr = None # cache for all_class_attributes 377 self.all_classattr_names = None # from all_classattr 378 self.allattr = None # cache for all_attributes 379 self.allattr_names = None # from allattr 380 381 # Add this class to its attributes. 382 383 self.set("__class__", self) 384 385 # Image generation details. 386 387 self.location = None 388 self.code_location = None 389 self.instantiator = None 390 391 # Program-related details. 392 393 self.temp_usage = 0 394 self.local_usage = 0 395 self.all_local_usage = 0 396 397 def __repr__(self): 398 if self.location is not None: 399 return "Class(%r, %s, location=%r)" % (self.name, shortrepr(self.parent), self.location) 400 else: 401 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 402 403 def __shortrepr__(self): 404 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 405 406 def _context(self, value): 407 408 """ 409 Return the context to be used when storing the given 'value'. 410 NOTE: This context is not likely to be useful when preparing an image 411 NOTE: since only instance contexts have significant effects at run-time. 412 """ 413 414 if value is not None: 415 context = value.parent 416 if isinstance(context, Module): 417 return self 418 else: 419 return context 420 else: 421 return None 422 423 def finalise_attributes(self): 424 425 "Make sure that all attributes are fully defined." 426 427 if self.finalised: 428 return 429 430 self.finalise_class_attributes() 431 self.finalise_instance_attributes() 432 self.finalised = 1 433 434 def get_instantiator(self): 435 436 "Return a function which can be used to instantiate the class." 437 438 if self.instantiator is None: 439 init_method = self.all_class_attributes()["__init__"].value 440 self.instantiator = init_method.function_from_method() 441 return self.instantiator 442 443 # Class-specific methods. 444 445 def add_base(self, base): 446 self.bases.append(base) 447 base.add_descendant(self) 448 449 def add_instance_attribute(self, name): 450 self.instattr.add(name) 451 452 def add_descendant(self, cls): 453 self.descendants.add(cls) 454 for base in self.bases: 455 base.add_descendant(cls) 456 457 def has_subclass(self, other): 458 return other in self.descendants 459 460 "Return the attribute names provided by this class only." 461 462 class_attribute_names = NamespaceDict.keys 463 464 def class_attributes(self): 465 466 "Return class attributes provided by this class only." 467 468 self.finalise_class_attributes() 469 return dict(self) 470 471 def all_class_attribute_names(self): 472 473 "Return the attribute names provided by classes in this hierarchy." 474 475 if self.all_classattr_names is None: 476 self.all_class_attributes() 477 return self.all_classattr_names 478 479 def all_class_attributes(self): 480 481 "Return all class attributes, indicating the class which provides them." 482 483 self.finalise_class_attributes() 484 return self.all_classattr 485 486 def finalise_class_attributes(self): 487 488 "Make sure that the class attributes are fully defined." 489 490 if self.all_classattr is None: 491 self.all_classattr = {} 492 clsattr = {} 493 494 # Record provisional position information for attributes of this 495 # class. 496 497 for name in self.class_attributes().keys(): 498 clsattr[name] = set() # position not yet defined 499 500 reversed_bases = self.bases[:] 501 reversed_bases.reverse() 502 503 # For the bases in reverse order, acquire class attribute details. 504 505 for cls in reversed_bases: 506 for name, attr in cls.all_class_attributes().items(): 507 self.all_classattr[name] = attr 508 509 # Record previous attribute information. 510 511 if clsattr.has_key(name): 512 clsattr[name].add(attr.position) 513 514 # Record class attributes provided by this class and its bases, 515 # along with their positions. 516 517 self.all_classattr.update(self.class_attributes()) 518 519 if clsattr: 520 for i, name in enumerate(self._get_position_list(clsattr)): 521 self.all_classattr[name].position = i 522 523 return self.all_classattr 524 525 def instance_attribute_names(self): 526 527 "Return the instance attribute names provided by the class." 528 529 if self.all_instattr_names is None: 530 self.instance_attributes() 531 return self.all_instattr_names 532 533 def instance_attributes(self): 534 535 "Return instance-only attributes for instances of this class." 536 537 self.finalise_instance_attributes() 538 return self.all_instattr 539 540 def finalise_instance_attributes(self): 541 542 "Make sure that the instance attributes are fully defined." 543 544 if self.all_instattr is None: 545 self.all_instattr = {} 546 instattr = {} 547 548 # Record provisional position information for attributes of this 549 # instance. 550 551 for name in self.instattr: 552 instattr[name] = set() # position not yet defined 553 554 reversed_bases = self.bases[:] 555 reversed_bases.reverse() 556 557 # For the bases in reverse order, acquire instance attribute 558 # details. 559 560 for cls in reversed_bases: 561 for name, attr in cls.instance_attributes().items(): 562 563 # Record previous attribute information. 564 565 if instattr.has_key(name): 566 instattr[name].add(attr.position) 567 568 # Cache the attributes by converting the positioned attributes into 569 # a dictionary. 570 571 if not instattr: 572 self.all_instattr = {} 573 else: 574 self.all_instattr = self._get_attributes(instattr) 575 576 self.all_instattr_names = self.all_instattr.keys() 577 578 return self.all_instattr 579 580 def _get_position_list(self, positions): 581 582 """ 583 Return a list of attribute names for the given 'positions' mapping from 584 names to positions, indicating the positions of the attributes in the 585 final instance structure. 586 """ 587 588 position_items = positions.items() 589 namearray = [None] * len(position_items) 590 591 # Get the positions in ascending order of list size, with lists 592 # of the same size ordered according to their smallest position 593 # value. 594 595 position_items.sort(self._cmp_positions) 596 597 # Get the names in position order. 598 599 held = [] 600 601 for name, pos in position_items: 602 pos = list(pos) 603 pos.sort() 604 if pos and pos[0] < len(namearray) and namearray[pos[0]] is None: 605 namearray[pos[0]] = name 606 else: 607 if pos: 608 self.relocated.add(name) 609 held.append((name, pos)) 610 611 for i, attr in enumerate(namearray): 612 if attr is None: 613 name, pos = held.pop() 614 namearray[i] = name 615 616 #print self.name, positions 617 #print "->", namearray 618 return namearray 619 620 def _get_attributes(self, positions): 621 622 """ 623 For the given 'positions' mapping from names to positions, return a 624 dictionary mapping names to Attr instances incorporating information 625 about their positions in the final instance structure. 626 """ 627 628 d = {} 629 for i, name in enumerate(self._get_position_list(positions)): 630 d[name] = Attr(i, Instance(), None, name, None) 631 return d 632 633 def _cmp_positions(self, a, b): 634 635 "Compare name plus position list operands 'a' and 'b'." 636 637 name_a, list_a = a 638 name_b, list_b = b 639 if len(list_a) < len(list_b): 640 return -1 641 elif len(list_a) > len(list_b): 642 return 1 643 elif not list_a: 644 return 0 645 else: 646 return cmp(min(list_a), min(list_b)) 647 648 def all_attribute_names(self): 649 650 """ 651 Return the names of all attributes provided by instances of this class. 652 """ 653 654 self.allattr_names = self.allattr_names or self.all_attributes().keys() 655 return self.allattr_names 656 657 def all_attributes(self): 658 659 """ 660 Return all attributes for an instance, indicating either the class which 661 provides them or that the instance itself provides them. 662 """ 663 664 if self.allattr is None: 665 self.allattr = {} 666 self.allattr.update(self.all_class_attributes()) 667 for name, attr in self.instance_attributes().items(): 668 if self.allattr.has_key(name): 669 print "Instance attribute %r in %r overrides class attribute." % (name, self) 670 self.allattr[name] = attr 671 return self.allattr 672 673 class Function(NamespaceDict, Naming, Constant): 674 675 "An inspected function." 676 677 def __init__(self, name, parent, argnames, defaults, has_star, has_dstar, global_namespace=None, node=None): 678 679 """ 680 Initialise the function with the given 'name', 'parent', list of 681 'argnames', list of 'defaults', the 'has_star' flag (indicating the 682 presence of a * parameter), the 'has_dstar' flag (indicating the 683 presence of a ** parameter), optional 'global_namespace', and optional 684 AST 'node'. 685 """ 686 687 NamespaceDict.__init__(self, global_namespace) 688 self.name = name 689 self.parent = parent 690 self.argnames = argnames 691 self.defaults = defaults 692 self.has_star = has_star 693 self.has_dstar = has_dstar 694 self.astnode = node 695 696 # Initialise the positional names. 697 698 self.positional_names = self.argnames[:] 699 if has_dstar: 700 self.dstar_name = self.positional_names[-1] 701 del self.positional_names[-1] 702 if has_star: 703 self.star_name = self.positional_names[-1] 704 del self.positional_names[-1] 705 706 # Initialise default storage. 707 # NOTE: This must be initialised separately due to the reliance on node 708 # NOTE: visiting. 709 710 self.default_attrs = [] 711 712 # Caches. 713 714 self.localnames = None # cache for locals 715 716 # Add parameters to the namespace. 717 718 self._add_parameters(argnames) 719 720 # Image generation details. 721 722 self.location = None 723 self.code_location = None 724 725 # Program-related details. 726 727 self.temp_usage = 0 728 self.local_usage = 0 729 self.all_local_usage = 0 730 731 def _add_parameters(self, argnames): 732 for name in argnames: 733 if isinstance(name, tuple): 734 self._add_parameters(name) 735 else: 736 self.set(name, None) 737 738 def __repr__(self): 739 if self.location is not None: 740 return "Function(%r, %s, %r, location=%r, code_location=%r)" % ( 741 self.name, shortrepr(self.parent), self.argnames, self.location, self.code_location 742 ) 743 else: 744 return "Function(%r, %s, %r)" % ( 745 self.name, shortrepr(self.parent), self.argnames 746 ) 747 748 def __shortrepr__(self): 749 return "Function(%r, %s)" % ( 750 self.name, shortrepr(self.parent) 751 ) 752 753 def store_default(self, value): 754 attr = Attr(None, self, None, None, value) 755 attr.update(value, 1) 756 self.default_attrs.append(attr) 757 758 def make_global(self, name): 759 if name not in self.argnames and not self.has_key(name): 760 self.globals.add(name) 761 else: 762 raise InspectError(self.full_name(), self.astnode, "Name %r is global and local in %r" % (name, self.full_name())) 763 764 def parameters(self): 765 766 """ 767 Return a dictionary mapping parameter names to their position in the 768 parameter list. 769 """ 770 771 parameters = {} 772 for i, name in enumerate(self.argnames): 773 parameters[name] = i 774 return parameters 775 776 def all_locals(self): 777 778 "Return a dictionary mapping names to local and parameter details." 779 780 return dict(self) 781 782 def locals(self): 783 784 "Return a dictionary mapping names to local details." 785 786 if self.localnames is None: 787 self.localnames = {} 788 self.localnames.update(self.all_locals()) 789 for name in self.argnames: 790 del self.localnames[name] 791 return self.localnames 792 793 def is_method(self): 794 795 "Return whether this function is a method." 796 797 return isinstance(self.parent, Class) 798 799 def is_relocated(self, name): 800 801 """ 802 Determine whether the given attribute 'name' is relocated for instances 803 having this function as a method. 804 """ 805 806 for cls in self.parent.descendants: 807 if name in cls.relocated: 808 return 1 809 return 0 810 811 def finalise_attributes(self): 812 813 """ 814 Make sure all attributes (locals) are fully defined. Note that locals 815 are not attributes in the sense of class, module or instance attributes. 816 Defaults are also finalised by this method. 817 """ 818 819 for i, default in enumerate(self.default_attrs): 820 default.position = i 821 822 i = None 823 for i, name in enumerate(self.argnames): 824 self[name].position = i 825 826 if i is not None: 827 j = i + 1 828 else: 829 j = 0 830 831 i = 0 832 for i, attr in enumerate(self.locals().values()): 833 attr.position = i + j 834 835 self.local_usage = i + 1 836 self.all_local_usage = i + j + 1 837 self.finalised = 1 838 839 def function_from_method(self): 840 841 "Make a function from a method." 842 843 function = Function(self.name, self.parent, self.argnames[1:], self.defaults, 844 self.has_star, self.has_dstar, self.global_namespace, self.astnode) 845 function.default_attrs = self.default_attrs 846 return function 847 848 class UnresolvedName(NamespaceDict, Constant): 849 850 "A module, class or function which was mentioned but could not be imported." 851 852 def __init__(self, name, parent_name, global_namespace=None): 853 NamespaceDict.__init__(self, global_namespace) 854 self.name = name 855 self.parent_name = parent_name 856 self.parent = None 857 858 def all_class_attributes(self): 859 return {} 860 861 def instance_attributes(self): 862 return {} 863 864 def __repr__(self): 865 return "UnresolvedName(%r, %r)" % (self.name, self.parent_name) 866 867 __shortrepr__ = __repr__ 868 869 def full_name(self): 870 if self.name is not None: 871 return self.parent_name + "." + self.name 872 else: 873 return self.parent_name 874 875 class Module(NamespaceDict, Constant): 876 877 "An inspected module's core details." 878 879 def __init__(self, name): 880 NamespaceDict.__init__(self, self) 881 self.name = name 882 self.parent = None 883 884 # Original location details. 885 886 self.astnode = None 887 888 # Complete lists of classes and functions. 889 890 self.all_objects = set() 891 892 # Keyword records. 893 894 self.keyword_names = set() 895 896 # Image generation details. 897 898 self.location = None 899 self.code_location = None 900 901 # Program-related details. 902 903 self.temp_usage = 0 904 self.local_usage = 0 905 self.all_local_usage = 0 906 907 def full_name(self): 908 return self.name 909 910 def __repr__(self): 911 if self.location is not None: 912 return "Module(%r, location=%r)" % (self.name, self.location) 913 else: 914 return "Module(%r)" % self.name 915 916 def __shortrepr__(self): 917 return "Module(%r)" % self.name 918 919 # Attribute methods. 920 921 "Return the module attribute names provided by the module." 922 923 module_attribute_names = NamespaceDict.keys 924 925 def module_attributes(self): 926 927 "Return a dictionary mapping names to module attributes." 928 929 return dict(self) 930 931 # vim: tabstop=4 expandtab shiftwidth=4