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