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