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