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