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