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 self.instantiator = self.get_init_method().function_from_method() 440 return self.instantiator 441 442 def get_init_method(self): 443 return self.all_class_attributes()["__init__"].value 444 445 # Class-specific methods. 446 447 def add_base(self, base): 448 self.bases.append(base) 449 base.add_descendant(self) 450 451 def add_instance_attribute(self, name): 452 self.instattr.add(name) 453 454 def add_descendant(self, cls): 455 self.descendants.add(cls) 456 for base in self.bases: 457 base.add_descendant(cls) 458 459 def has_subclass(self, other): 460 return other in self.descendants 461 462 def all_descendants(self): 463 d = {} 464 for cls in self.descendants: 465 d[cls.full_name()] = cls 466 return d 467 468 "Return the attribute names provided by this class only." 469 470 class_attribute_names = NamespaceDict.keys 471 472 def class_attributes(self): 473 474 "Return class attributes provided by this class only." 475 476 self.finalise_class_attributes() 477 return dict(self) 478 479 def all_class_attribute_names(self): 480 481 "Return the attribute names provided by classes in this hierarchy." 482 483 if self.all_classattr_names is None: 484 self.all_class_attributes() 485 return self.all_classattr_names 486 487 def all_class_attributes(self): 488 489 "Return all class attributes, indicating the class which provides them." 490 491 self.finalise_class_attributes() 492 return self.all_classattr 493 494 def finalise_class_attributes(self): 495 496 "Make sure that the class attributes are fully defined." 497 498 if self.all_classattr is None: 499 self.all_classattr = {} 500 clsattr = {} 501 502 # Record provisional position information for attributes of this 503 # class. 504 505 for name in self.class_attributes().keys(): 506 clsattr[name] = set() # position not yet defined 507 508 reversed_bases = self.bases[:] 509 reversed_bases.reverse() 510 511 # For the bases in reverse order, acquire class attribute details. 512 513 for cls in reversed_bases: 514 for name, attr in cls.all_class_attributes().items(): 515 self.all_classattr[name] = attr 516 517 # Record previous attribute information. 518 519 if clsattr.has_key(name): 520 clsattr[name].add(attr.position) 521 522 # Record class attributes provided by this class and its bases, 523 # along with their positions. 524 525 self.all_classattr.update(self.class_attributes()) 526 527 if clsattr: 528 for i, name in enumerate(self._get_position_list(clsattr)): 529 self.all_classattr[name].position = i 530 531 return self.all_classattr 532 533 def instance_attribute_names(self): 534 535 "Return the instance attribute names provided by the class." 536 537 if self.all_instattr_names is None: 538 self.instance_attributes() 539 return self.all_instattr_names 540 541 def instance_attributes(self): 542 543 "Return instance-only attributes for instances of this class." 544 545 self.finalise_instance_attributes() 546 return self.all_instattr 547 548 def finalise_instance_attributes(self): 549 550 "Make sure that the instance attributes are fully defined." 551 552 if self.all_instattr is None: 553 self.all_instattr = {} 554 instattr = {} 555 556 # Record provisional position information for attributes of this 557 # instance. 558 559 for name in self.instattr: 560 instattr[name] = set() # position not yet defined 561 562 reversed_bases = self.bases[:] 563 reversed_bases.reverse() 564 565 # For the bases in reverse order, acquire instance attribute 566 # details. 567 568 for cls in reversed_bases: 569 for name, attr in cls.instance_attributes().items(): 570 571 # Record previous attribute information. 572 573 if instattr.has_key(name): 574 instattr[name].add(attr.position) 575 576 # Cache the attributes by converting the positioned attributes into 577 # a dictionary. 578 579 if not instattr: 580 self.all_instattr = {} 581 else: 582 self.all_instattr = self._get_attributes(instattr) 583 584 self.all_instattr_names = self.all_instattr.keys() 585 586 return self.all_instattr 587 588 def _get_position_list(self, positions): 589 590 """ 591 Return a list of attribute names for the given 'positions' mapping from 592 names to positions, indicating the positions of the attributes in the 593 final instance structure. 594 """ 595 596 position_items = positions.items() 597 namearray = [None] * len(position_items) 598 599 # Get the positions in ascending order of list size, with lists 600 # of the same size ordered according to their smallest position 601 # value. 602 603 position_items.sort(self._cmp_positions) 604 605 # Get the names in position order. 606 607 held = [] 608 609 for name, pos in position_items: 610 pos = list(pos) 611 pos.sort() 612 if pos and pos[0] < len(namearray) and namearray[pos[0]] is None: 613 namearray[pos[0]] = name 614 else: 615 if pos: 616 self.relocated.add(name) 617 held.append((name, pos)) 618 619 for i, attr in enumerate(namearray): 620 if attr is None: 621 name, pos = held.pop() 622 namearray[i] = name 623 624 #print self.name, positions 625 #print "->", namearray 626 return namearray 627 628 def _get_attributes(self, positions): 629 630 """ 631 For the given 'positions' mapping from names to positions, return a 632 dictionary mapping names to Attr instances incorporating information 633 about their positions in the final instance structure. 634 """ 635 636 d = {} 637 for i, name in enumerate(self._get_position_list(positions)): 638 d[name] = Attr(i, Instance(), None, name, None) 639 return d 640 641 def _cmp_positions(self, a, b): 642 643 "Compare name plus position list operands 'a' and 'b'." 644 645 name_a, list_a = a 646 name_b, list_b = b 647 if len(list_a) < len(list_b): 648 return -1 649 elif len(list_a) > len(list_b): 650 return 1 651 elif not list_a: 652 return 0 653 else: 654 return cmp(min(list_a), min(list_b)) 655 656 def all_attribute_names(self): 657 658 """ 659 Return the names of all attributes provided by instances of this class. 660 """ 661 662 self.allattr_names = self.allattr_names or self.all_attributes().keys() 663 return self.allattr_names 664 665 def all_attributes(self): 666 667 """ 668 Return all attributes for an instance, indicating either the class which 669 provides them or that the instance itself provides them. 670 """ 671 672 if self.allattr is None: 673 self.allattr = {} 674 self.allattr.update(self.all_class_attributes()) 675 for name, attr in self.instance_attributes().items(): 676 if self.allattr.has_key(name): 677 print "Instance attribute %r in %r overrides class attribute." % (name, self) 678 self.allattr[name] = attr 679 return self.allattr 680 681 class Function(NamespaceDict, Naming, Constant): 682 683 "An inspected function." 684 685 def __init__(self, name, parent, argnames, defaults, has_star, has_dstar, global_namespace=None, node=None): 686 687 """ 688 Initialise the function with the given 'name', 'parent', list of 689 'argnames', list of 'defaults', the 'has_star' flag (indicating the 690 presence of a * parameter), the 'has_dstar' flag (indicating the 691 presence of a ** parameter), optional 'global_namespace', and optional 692 AST 'node'. 693 """ 694 695 NamespaceDict.__init__(self, global_namespace) 696 self.name = name 697 self.parent = parent 698 self.argnames = argnames 699 self.defaults = defaults 700 self.has_star = has_star 701 self.has_dstar = has_dstar 702 self.astnode = node 703 704 # Initialise the positional names. 705 706 self.positional_names = self.argnames[:] 707 if has_dstar: 708 self.dstar_name = self.positional_names[-1] 709 del self.positional_names[-1] 710 if has_star: 711 self.star_name = self.positional_names[-1] 712 del self.positional_names[-1] 713 714 # Initialise default storage. 715 # NOTE: This must be initialised separately due to the reliance on node 716 # NOTE: visiting. 717 718 self.default_attrs = [] 719 720 # Caches. 721 722 self.localnames = None # cache for locals 723 724 # Add parameters to the namespace. 725 726 self._add_parameters(argnames) 727 728 # Image generation details. 729 730 self.location = None 731 self.code_location = None 732 733 # Program-related details. 734 735 self.temp_usage = 0 736 self.local_usage = 0 737 self.all_local_usage = 0 738 739 def _add_parameters(self, argnames): 740 for name in argnames: 741 if isinstance(name, tuple): 742 self._add_parameters(name) 743 else: 744 self.set(name, None) 745 746 def __repr__(self): 747 if self.location is not None: 748 return "Function(%r, %s, %r, location=%r, code_location=%r)" % ( 749 self.name, shortrepr(self.parent), self.argnames, self.location, self.code_location 750 ) 751 else: 752 return "Function(%r, %s, %r)" % ( 753 self.name, shortrepr(self.parent), self.argnames 754 ) 755 756 def __shortrepr__(self): 757 return "Function(%r, %s)" % ( 758 self.name, shortrepr(self.parent) 759 ) 760 761 def store_default(self, value): 762 attr = Attr(None, self, None, None, value) 763 attr.update(value, 1) 764 self.default_attrs.append(attr) 765 766 def make_global(self, name): 767 if name not in self.argnames and not self.has_key(name): 768 self.globals.add(name) 769 else: 770 raise InspectError(self.full_name(), self.astnode, "Name %r is global and local in %r" % (name, self.full_name())) 771 772 def parameters(self): 773 774 """ 775 Return a dictionary mapping parameter names to their position in the 776 parameter list. 777 """ 778 779 parameters = {} 780 for i, name in enumerate(self.argnames): 781 parameters[name] = i 782 return parameters 783 784 def all_locals(self): 785 786 "Return a dictionary mapping names to local and parameter details." 787 788 return dict(self) 789 790 def locals(self): 791 792 "Return a dictionary mapping names to local details." 793 794 if self.localnames is None: 795 self.localnames = {} 796 self.localnames.update(self.all_locals()) 797 for name in self.argnames: 798 del self.localnames[name] 799 return self.localnames 800 801 def is_method(self): 802 803 "Return whether this function is a method." 804 805 return isinstance(self.parent, Class) 806 807 def is_relocated(self, name): 808 809 """ 810 Determine whether the given attribute 'name' is relocated for instances 811 having this function as a method. 812 """ 813 814 for cls in self.parent.descendants: 815 if name in cls.relocated: 816 return 1 817 return 0 818 819 def finalise_attributes(self): 820 821 """ 822 Make sure all attributes (locals) are fully defined. Note that locals 823 are not attributes in the sense of class, module or instance attributes. 824 Defaults are also finalised by this method. 825 """ 826 827 for i, default in enumerate(self.default_attrs): 828 default.position = i 829 830 i = None 831 for i, name in enumerate(self.argnames): 832 self[name].position = i 833 834 if i is not None: 835 nparams = i + 1 836 else: 837 nparams = 0 838 839 i = None 840 for i, attr in enumerate(self.locals().values()): 841 attr.position = i + nparams 842 843 if i is not None: 844 nothers = i + 1 845 else: 846 nothers = 0 847 848 self.local_usage = nothers 849 self.all_local_usage = nparams + nothers 850 self.finalised = 1 851 852 def function_from_method(self): 853 854 "Make a function from a method." 855 856 function = Function(self.name, self.parent, self.argnames[1:], self.defaults, 857 self.has_star, self.has_dstar, self.global_namespace, self.astnode) 858 function.default_attrs = self.default_attrs 859 return function 860 861 class UnresolvedName(NamespaceDict, Constant): 862 863 "A module, class or function which was mentioned but could not be imported." 864 865 def __init__(self, name, parent_name, global_namespace=None): 866 NamespaceDict.__init__(self, global_namespace) 867 self.name = name 868 self.parent_name = parent_name 869 self.parent = None 870 871 def all_class_attributes(self): 872 return {} 873 874 def instance_attributes(self): 875 return {} 876 877 def __repr__(self): 878 return "UnresolvedName(%r, %r)" % (self.name, self.parent_name) 879 880 __shortrepr__ = __repr__ 881 882 def full_name(self): 883 if self.name is not None: 884 return self.parent_name + "." + self.name 885 else: 886 return self.parent_name 887 888 class Module(NamespaceDict, Constant): 889 890 "An inspected module's core details." 891 892 def __init__(self, name): 893 NamespaceDict.__init__(self, self) 894 self.name = name 895 self.parent = None 896 897 # Original location details. 898 899 self.astnode = None 900 901 # Complete lists of classes and functions. 902 903 self.all_objects = set() 904 905 # Keyword records. 906 907 self.keyword_names = set() 908 909 # Image generation details. 910 911 self.location = None 912 self.code_location = None 913 914 # Program-related details. 915 916 self.temp_usage = 0 917 self.local_usage = 0 918 self.all_local_usage = 0 919 920 def full_name(self): 921 return self.name 922 923 def __repr__(self): 924 if self.location is not None: 925 return "Module(%r, location=%r)" % (self.name, self.location) 926 else: 927 return "Module(%r)" % self.name 928 929 def __shortrepr__(self): 930 return "Module(%r)" % self.name 931 932 # Attribute methods. 933 934 "Return the module attribute names provided by the module." 935 936 module_attribute_names = NamespaceDict.keys 937 938 def module_attributes(self): 939 940 "Return a dictionary mapping names to module attributes." 941 942 return dict(self) 943 944 # vim: tabstop=4 expandtab shiftwidth=4