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