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 defined_within_hierarchy(self): 275 276 """ 277 Return whether the parent and context of the attribute belong to the 278 same class hierarchy. 279 """ 280 281 return isinstance(self.parent, Class) and isinstance(self.context, Class) and ( 282 self.context is self.parent or 283 self.context in self.parent.descendants or 284 self.parent in self.context.descendants) 285 286 def __repr__(self): 287 return "Attr(%r, %s, %s, %r, %s, %r)" % ( 288 self.position, shortrepr(self.parent), shortrepr(self.context), 289 self.name, shortrepr(self.value), self.assignments 290 ) 291 292 # Instances are special in that they need to be wrapped together with context in 293 # a running program, but they are not generally constant. 294 295 class Instance: 296 297 "A placeholder indicating the involvement of an instance." 298 299 def __init__(self): 300 self.parent = None 301 302 # Image generation details. 303 304 self.location = None 305 306 def __repr__(self): 307 return "Instance()" 308 309 __shortrepr__ = __repr__ 310 311 class Constant: 312 313 "A superclass for all constant or context-free structures." 314 315 pass 316 317 class Const(Constant, Instance): 318 319 "A constant object with no context." 320 321 def __init__(self, value): 322 self.value = value 323 self.parent = None 324 325 def __repr__(self): 326 if self.location is not None: 327 return "Const(%r, location=%r)" % (self.value, self.location) 328 else: 329 return "Const(%r)" % self.value 330 331 __shortrepr__ = __repr__ 332 333 # Support constants as dictionary keys in order to build constant tables. 334 335 def __eq__(self, other): 336 return self.value == other.value 337 338 def __hash__(self): 339 return hash(self.value) 340 341 def value_type_name(self): 342 return "__builtins__." + self.value.__class__.__name__ 343 344 class Class(NamespaceDict, Naming, Constant): 345 346 "An inspected class." 347 348 def __init__(self, name, parent, global_namespace=None, node=None): 349 350 """ 351 Initialise the class with the given 'name', 'parent' object, optional 352 'global_namespace' and optional AST 'node'. 353 """ 354 355 NamespaceDict.__init__(self, global_namespace) 356 self.name = name 357 self.parent = parent 358 self.astnode = node 359 360 # Superclasses, descendants and attributes. 361 362 self.bases = [] 363 self.descendants = set() 364 self.instattr = set() # instance attributes 365 self.relocated = set() # attributes which do not have the same 366 # position as those of the same name in 367 # some superclasses 368 369 # Caches. 370 371 self.all_instattr = None # cache for instance_attributes 372 self.all_instattr_names = None # from all_instattr 373 self.all_classattr = None # cache for all_class_attributes 374 self.all_classattr_names = None # from all_classattr 375 self.allattr = None # cache for all_attributes 376 self.allattr_names = None # from allattr 377 378 # Add this class to its attributes. 379 380 self.set("__class__", self) 381 382 # Image generation details. 383 384 self.location = None 385 self.code_location = None 386 self.instantiator = None 387 388 # Program-related details. 389 390 self.temp_usage = 0 391 self.local_usage = 0 392 393 def __repr__(self): 394 if self.location is not None: 395 return "Class(%r, %s, location=%r)" % (self.name, shortrepr(self.parent), self.location) 396 else: 397 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 398 399 def __shortrepr__(self): 400 return "Class(%r, %s)" % (self.name, shortrepr(self.parent)) 401 402 def _context(self, value): 403 404 """ 405 Return the context to be used when storing the given 'value'. 406 NOTE: This context is not likely to be useful when preparing an image 407 NOTE: since only instance contexts have significant effects at run-time. 408 """ 409 410 if value is not None: 411 context = value.parent 412 if isinstance(context, Module): 413 return self 414 else: 415 return context 416 else: 417 return None 418 419 def finalise_attributes(self): 420 421 "Make sure that all attributes are fully defined." 422 423 if self.finalised: 424 return 425 426 self.finalise_class_attributes() 427 self.finalise_instance_attributes() 428 self.finalised = 1 429 430 def get_instantiator(self): 431 432 "Return a function which can be used to instantiate the class." 433 434 if self.instantiator is None: 435 init_method = self.all_class_attributes()["__init__"].value 436 self.instantiator = init_method.function_from_method() 437 return self.instantiator 438 439 # Class-specific methods. 440 441 def add_base(self, base): 442 self.bases.append(base) 443 base.add_descendant(self) 444 445 def add_instance_attribute(self, name): 446 self.instattr.add(name) 447 448 def add_descendant(self, cls): 449 self.descendants.add(cls) 450 for base in self.bases: 451 base.add_descendant(cls) 452 453 "Return the attribute names provided by this class only." 454 455 class_attribute_names = NamespaceDict.keys 456 457 def class_attributes(self): 458 459 "Return class attributes provided by this class only." 460 461 self.finalise_class_attributes() 462 return dict(self) 463 464 def all_class_attribute_names(self): 465 466 "Return the attribute names provided by classes in this hierarchy." 467 468 if self.all_classattr_names is None: 469 self.all_class_attributes() 470 return self.all_classattr_names 471 472 def all_class_attributes(self): 473 474 "Return all class attributes, indicating the class which provides them." 475 476 self.finalise_class_attributes() 477 return self.all_classattr 478 479 def finalise_class_attributes(self): 480 481 "Make sure that the class attributes are fully defined." 482 483 if self.all_classattr is None: 484 self.all_classattr = {} 485 clsattr = {} 486 487 # Record provisional position information for attributes of this 488 # class. 489 490 for name in self.class_attributes().keys(): 491 clsattr[name] = set() # position not yet defined 492 493 reversed_bases = self.bases[:] 494 reversed_bases.reverse() 495 496 # For the bases in reverse order, acquire class attribute details. 497 498 for cls in reversed_bases: 499 for name, attr in cls.all_class_attributes().items(): 500 self.all_classattr[name] = attr 501 502 # Record previous attribute information. 503 504 if clsattr.has_key(name): 505 clsattr[name].add(attr.position) 506 507 # Record class attributes provided by this class and its bases, 508 # along with their positions. 509 510 self.all_classattr.update(self.class_attributes()) 511 512 if clsattr: 513 for i, name in enumerate(self._get_position_list(clsattr)): 514 self.all_classattr[name].position = i 515 516 return self.all_classattr 517 518 def instance_attribute_names(self): 519 520 "Return the instance attribute names provided by the class." 521 522 if self.all_instattr_names is None: 523 self.instance_attributes() 524 return self.all_instattr_names 525 526 def instance_attributes(self): 527 528 "Return instance-only attributes for instances of this class." 529 530 self.finalise_instance_attributes() 531 return self.all_instattr 532 533 def finalise_instance_attributes(self): 534 535 "Make sure that the instance attributes are fully defined." 536 537 if self.all_instattr is None: 538 self.all_instattr = {} 539 instattr = {} 540 541 # Record provisional position information for attributes of this 542 # instance. 543 544 for name in self.instattr: 545 instattr[name] = set() # position not yet defined 546 547 reversed_bases = self.bases[:] 548 reversed_bases.reverse() 549 550 # For the bases in reverse order, acquire instance attribute 551 # details. 552 553 for cls in reversed_bases: 554 for name, attr in cls.instance_attributes().items(): 555 556 # Record previous attribute information. 557 558 if instattr.has_key(name): 559 instattr[name].add(attr.position) 560 561 # Cache the attributes by converting the positioned attributes into 562 # a dictionary. 563 564 if not instattr: 565 self.all_instattr = {} 566 else: 567 self.all_instattr = self._get_attributes(instattr) 568 569 self.all_instattr_names = self.all_instattr.keys() 570 571 return self.all_instattr 572 573 def _get_position_list(self, positions): 574 575 """ 576 Return a list of attribute names for the given 'positions' mapping from 577 names to positions, indicating the positions of the attributes in the 578 final instance structure. 579 """ 580 581 position_items = positions.items() 582 namearray = [None] * len(position_items) 583 584 # Get the positions in ascending order of list size, with lists 585 # of the same size ordered according to their smallest position 586 # value. 587 588 position_items.sort(self._cmp_positions) 589 590 # Get the names in position order. 591 592 held = [] 593 594 for name, pos in position_items: 595 pos = list(pos) 596 pos.sort() 597 if pos and pos[0] < len(namearray) and namearray[pos[0]] is None: 598 namearray[pos[0]] = name 599 else: 600 if pos: 601 self.relocated.add(name) 602 held.append((name, pos)) 603 604 for i, attr in enumerate(namearray): 605 if attr is None: 606 name, pos = held.pop() 607 namearray[i] = name 608 609 #print self.name, positions 610 #print "->", namearray 611 return namearray 612 613 def _get_attributes(self, positions): 614 615 """ 616 For the given 'positions' mapping from names to positions, return a 617 dictionary mapping names to Attr instances incorporating information 618 about their positions in the final instance structure. 619 """ 620 621 d = {} 622 for i, name in enumerate(self._get_position_list(positions)): 623 d[name] = Attr(i, Instance(), None, name, None) 624 return d 625 626 def _cmp_positions(self, a, b): 627 628 "Compare name plus position list operands 'a' and 'b'." 629 630 name_a, list_a = a 631 name_b, list_b = b 632 if len(list_a) < len(list_b): 633 return -1 634 elif len(list_a) > len(list_b): 635 return 1 636 elif not list_a: 637 return 0 638 else: 639 return cmp(min(list_a), min(list_b)) 640 641 def all_attribute_names(self): 642 643 """ 644 Return the names of all attributes provided by instances of this class. 645 """ 646 647 self.allattr_names = self.allattr_names or self.all_attributes().keys() 648 return self.allattr_names 649 650 def all_attributes(self): 651 652 """ 653 Return all attributes for an instance, indicating either the class which 654 provides them or that the instance itself provides them. 655 """ 656 657 if self.allattr is None: 658 self.allattr = {} 659 self.allattr.update(self.all_class_attributes()) 660 for name, attr in self.instance_attributes().items(): 661 if self.allattr.has_key(name): 662 print "Instance attribute %r in %r overrides class attribute." % (name, self) 663 self.allattr[name] = attr 664 return self.allattr 665 666 class Function(NamespaceDict, Naming, Constant): 667 668 "An inspected function." 669 670 def __init__(self, name, parent, argnames, defaults, has_star, has_dstar, global_namespace=None, node=None): 671 672 """ 673 Initialise the function with the given 'name', 'parent', list of 674 'argnames', list of 'defaults', the 'has_star' flag (indicating the 675 presence of a * parameter), the 'has_dstar' flag (indicating the 676 presence of a ** parameter), optional 'global_namespace', and optional 677 AST 'node'. 678 """ 679 680 NamespaceDict.__init__(self, global_namespace) 681 self.name = name 682 self.parent = parent 683 self.argnames = argnames 684 self.defaults = defaults 685 self.has_star = has_star 686 self.has_dstar = has_dstar 687 self.astnode = node 688 689 # Initialise the positional names. 690 691 self.positional_names = self.argnames[:] 692 if has_dstar: 693 self.dstar_name = self.positional_names[-1] 694 del self.positional_names[-1] 695 if has_star: 696 self.star_name = self.positional_names[-1] 697 del self.positional_names[-1] 698 699 # Initialise default storage. 700 # NOTE: This must be initialised separately due to the reliance on node 701 # NOTE: visiting. 702 703 self.default_attrs = [] 704 705 # Caches. 706 707 self.localnames = None # cache for locals 708 709 # Add parameters to the namespace. 710 711 self._add_parameters(argnames) 712 713 # Image generation details. 714 715 self.location = None 716 self.code_location = None 717 718 # Program-related details. 719 720 self.temp_usage = 0 721 self.local_usage = 0 722 723 def _add_parameters(self, argnames): 724 for name in argnames: 725 if isinstance(name, tuple): 726 self._add_parameters(name) 727 else: 728 self.set(name, None) 729 730 def __repr__(self): 731 if self.location is not None: 732 return "Function(%r, %s, %r, location=%r, code_location=%r)" % ( 733 self.name, shortrepr(self.parent), self.argnames, self.location, self.code_location 734 ) 735 else: 736 return "Function(%r, %s, %r)" % ( 737 self.name, shortrepr(self.parent), self.argnames 738 ) 739 740 def __shortrepr__(self): 741 return "Function(%r, %s)" % ( 742 self.name, shortrepr(self.parent) 743 ) 744 745 def store_default(self, value): 746 attr = Attr(None, self, None, None, value) 747 attr.update(value, 1) 748 self.default_attrs.append(attr) 749 750 def make_global(self, name): 751 if name not in self.argnames and not self.has_key(name): 752 self.globals.add(name) 753 else: 754 raise InspectError(self.full_name(), self.astnode, "Name %r is global and local in %r" % (name, self.full_name())) 755 756 def parameters(self): 757 758 """ 759 Return a dictionary mapping parameter names to their position in the 760 parameter list. 761 """ 762 763 parameters = {} 764 for i, name in enumerate(self.argnames): 765 parameters[name] = i 766 return parameters 767 768 def all_locals(self): 769 770 "Return a dictionary mapping names to local and parameter details." 771 772 return dict(self) 773 774 def locals(self): 775 776 "Return a dictionary mapping names to local details." 777 778 if self.localnames is None: 779 self.localnames = {} 780 self.localnames.update(self.all_locals()) 781 for name in self.argnames: 782 del self.localnames[name] 783 return self.localnames 784 785 def is_method(self): 786 787 "Return whether this function is a method." 788 789 return isinstance(self.parent, Class) 790 791 def is_relocated(self, name): 792 793 """ 794 Determine whether the given attribute 'name' is relocated for instances 795 having this function as a method. 796 """ 797 798 for cls in self.parent.descendants: 799 if name in cls.relocated: 800 return 1 801 return 0 802 803 def finalise_attributes(self): 804 805 """ 806 Make sure all attributes (locals) are fully defined. Note that locals 807 are not attributes in the sense of class, module or instance attributes. 808 Defaults are also finalised by this method. 809 """ 810 811 for i, default in enumerate(self.default_attrs): 812 default.position = i 813 814 i = None 815 for i, name in enumerate(self.argnames): 816 self[name].position = i 817 818 if i is not None: 819 j = i + 1 820 else: 821 j = 0 822 823 i = 0 824 for i, attr in enumerate(self.locals().values()): 825 attr.position = i + j 826 827 self.local_usage = i + j 828 self.finalised = 1 829 830 def function_from_method(self): 831 832 "Make a function from a method." 833 834 function = Function(self.name, self.parent, self.argnames[1:], self.defaults, 835 self.has_star, self.has_dstar, self.global_namespace, self.astnode) 836 function.default_attrs = self.default_attrs 837 return function 838 839 class UnresolvedName(NamespaceDict, Constant): 840 841 "A module, class or function which was mentioned but could not be imported." 842 843 def __init__(self, name, parent_name, global_namespace=None): 844 NamespaceDict.__init__(self, global_namespace) 845 self.name = name 846 self.parent_name = parent_name 847 self.parent = None 848 849 def all_class_attributes(self): 850 return {} 851 852 def instance_attributes(self): 853 return {} 854 855 def __repr__(self): 856 return "UnresolvedName(%r, %r)" % (self.name, self.parent_name) 857 858 __shortrepr__ = __repr__ 859 860 def full_name(self): 861 if self.name is not None: 862 return self.parent_name + "." + self.name 863 else: 864 return self.parent_name 865 866 class Module(NamespaceDict, Constant): 867 868 "An inspected module's core details." 869 870 def __init__(self, name): 871 NamespaceDict.__init__(self, self) 872 self.name = name 873 self.parent = None 874 875 # Original location details. 876 877 self.astnode = None 878 879 # Complete lists of classes and functions. 880 881 self.all_objects = set() 882 883 # Keyword records. 884 885 self.keyword_names = set() 886 887 # Image generation details. 888 889 self.location = None 890 self.code_location = None 891 892 # Program-related details. 893 894 self.temp_usage = 0 895 self.local_usage = 0 896 897 def full_name(self): 898 return self.name 899 900 def __repr__(self): 901 if self.location is not None: 902 return "Module(%r, location=%r)" % (self.name, self.location) 903 else: 904 return "Module(%r)" % self.name 905 906 def __shortrepr__(self): 907 return "Module(%r)" % self.name 908 909 # Attribute methods. 910 911 "Return the module attribute names provided by the module." 912 913 module_attribute_names = NamespaceDict.keys 914 915 def module_attributes(self): 916 917 "Return a dictionary mapping names to module attributes." 918 919 return dict(self) 920 921 # vim: tabstop=4 expandtab shiftwidth=4