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