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