1 #!/usr/bin/env python 2 3 """ 4 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014 Paul Boddie <paul@boddie.org.uk> 5 6 This program is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free Software 8 Foundation; either version 3 of the License, or (at your option) any later 9 version. 10 11 This program is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 13 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 14 details. 15 16 You should have received a copy of the GNU General Public License along with 17 this program. If not, see <http://www.gnu.org/licenses/>. 18 """ 19 20 from micropython.errors import * 21 from micropython.objectset import * 22 from micropython.types import * 23 24 try: 25 set 26 except NameError: 27 from sets import Set as set 28 29 class AttributeUsage: 30 31 "Management of attribute usage in a program unit." 32 33 def __init__(self): 34 35 # Attributes accessed on objects, potentially narrowing their types. 36 # Specific namespaces should define known names during initialisation. 37 # For example, functions can define names belonging to parameters. 38 39 # Attribute users, defining names which use attributes. 40 41 self.attribute_users = [{}] # stack of assignments and branches 42 43 # Define attribute usage to identify active program sections. 44 # Attribute users are AST nodes defining names. 45 46 self.all_attribute_users = set() 47 48 # Finalisation of a program unit's information. 49 50 def finalise_attribute_usage(self): 51 52 "Propagate attribute usage for the namespace to the importer." 53 54 module = self.module 55 importer = module and module.importer 56 57 if importer is not None: 58 59 # Visit each user and examine the attribute usage for each name. 60 61 for user in self.all_attribute_users: 62 63 # First, visit the contributors and combine their attribute 64 # usage with the usage recorded directly on the user. 65 66 self.get_usage_from_contributors(user) 67 68 # Record the defining user on each contributor. 69 70 for contributor in user._attrcontributors: 71 contributor._attrdefs.append(user) 72 73 # Then, tell the importer about the usage. 74 75 for name in user._attrnames.keys(): 76 77 # Only provide information about names defined by this user. 78 79 usage = user._attrcombined.get(name, []) 80 81 # Skip reporting where no actual usage occurs. 82 83 if usage is None: 84 continue 85 86 # Eliminate non-usage. 87 88 importer.use_names(user, name, tuple([attrnames for attrnames in usage if attrnames]), self.full_name()) 89 90 def finalise_users(self, objtable): 91 92 "Record the object types for generating guards." 93 94 # Visit each user and examine the attribute usage for each name. 95 96 for user in self.all_attribute_users: 97 user._attrtypes = self._deduce_types(user._attrcombined, objtable) 98 self._finalise_contributor(user, objtable) 99 100 def _finalise_contributors(self, node, objtable): 101 102 """ 103 Visit the contributing branches of 'node', finalising them using the 104 given 'objtable'. 105 """ 106 107 for contributor in node._attrbranches: 108 self._finalise_contributor(contributor, objtable) 109 110 def _finalise_contributor(self, node, objtable): 111 112 """ 113 Record the specific object types being used in various regions of a 114 program unit. 115 """ 116 117 if node._attrspecifictypes is None: 118 merged = {} 119 120 # Get the combined usage information from the user definitions. 121 122 for user in node._attrdefs or [node]: 123 124 # Filter the usage for each name using the local usage 125 # information. 126 127 for name, usage in user._attrcombined.items(): 128 localusage = node._attrnames.get(name) 129 130 if usage and localusage: 131 if not merged.has_key(name): 132 merged[name] = ObjectSet() 133 134 for attrnames, value in usage.items(): 135 if attrnames and localusage.issubset(attrnames): 136 merged[name][attrnames] = value 137 138 node._attrmerged = merged 139 node._attrspecifictypes = self._deduce_types(node._attrmerged, objtable) 140 141 self._finalise_contributors(node, objtable) 142 143 def _deduce_types(self, usage, objtable): 144 145 """ 146 Deduce the types for names from the given attribute 'usage' and using 147 the given 'objtable'. 148 """ 149 150 attrtypes = {} 151 for name, combined_usage in usage.items(): 152 if combined_usage is not None: 153 objtypes = get_object_types_for_usage(combined_usage, objtable, name, self.full_name(), True, self.module.importer) 154 if objtypes: 155 if self.is_method() and name == "self": 156 objtypes = filter_using_self(objtypes, self.parent) 157 attrtypes[name] = objtypes 158 return attrtypes 159 160 def get_usage_from_contributors(self, node): 161 162 """ 163 Obtain usage information from the given 'node', combined with usage 164 details from its contributors, returning a tuple containing a set of all 165 contributors employed along with a dictionary mapping names to lists of 166 usage possibilities (each a collection of attribute names). 167 """ 168 169 unfinished = {} 170 171 # Process any unprocessed contributors, indicating the unfinished state 172 # of the associated data. 173 174 if node._attrcombined is None: 175 176 # Where an attempt is already underway to gather usage on this node, 177 # this special annotation value will be obtained from the node, 178 # causing the node to be regarded as unfinished. 179 180 node._attrcombined = Unset 181 182 for contributor in node._attrbranches: 183 184 # Get contributor details. 185 186 unfinished_contributors = self.get_usage_from_contributors(contributor) 187 188 # Collect unfinished contributors and affected nodes. 189 190 # Where the contributor is already set to Unset, a loop has 191 # occurred and this node will need to have its usage 192 # recalculated later for the unfinished contributor. 193 194 if contributor._attrcombined is Unset: 195 if not unfinished.has_key(contributor): 196 unfinished[contributor] = [] 197 unfinished[contributor].append(node) 198 continue 199 200 # Where the contributor provides usage details, it may also 201 # communicate unfinished contributor information. As a 202 # consequence, this node is also affected. 203 204 for unfinished_contributor, nodes in unfinished_contributors.items(): 205 if not unfinished.has_key(unfinished_contributor): 206 unfinished[unfinished_contributor] = nodes 207 else: 208 unfinished[unfinished_contributor] += nodes 209 210 if node not in unfinished[unfinished_contributor]: 211 unfinished[unfinished_contributor].append(node) 212 213 # Set the current state of the usage on this node. 214 215 node._attrcombined, node._attrcontributors = \ 216 self.get_usage_from_contributors_for_node(node) 217 218 # Complete unfinished contributors relying on this node. 219 220 if unfinished.has_key(node): 221 processed = set() 222 for contributor in unfinished[node]: 223 if not contributor in processed: 224 processed.add(contributor) 225 226 contributor._attrcombined, contributor._attrcontributors = \ 227 self.get_usage_from_contributors_for_node(contributor) 228 229 del unfinished[node] 230 231 return unfinished 232 233 def get_usage_from_contributors_for_node(self, node): 234 235 # Visit each contributor, gathering usage for each name. 236 237 contributor_usage = {} 238 all_contributions = [] 239 all_contributors = set() 240 241 for contributor in node._attrbranches: 242 usage = contributor._attrcombined 243 if usage is not Unset: 244 all_contributions.append(usage) 245 246 all_contributors.add(contributor) 247 contributors = contributor._attrcontributors 248 if contributors is not None: 249 all_contributors.update(contributors) 250 251 # Get contributed usage for each contributor. 252 # This gathers usage for each name such as {(a, b), (c, d)} and 253 # {(a, b), (e, f)} into a single set {(a, b), (c, d), (e, f)}. 254 255 update_mapping_dict(contributor_usage, all_contributions) 256 257 # Then get the resulting usage. 258 # First, make the current usage compatible with the contributed 259 # usage: this makes the attribute usage for each name merely one 260 # member in a list of many possibilities. 261 # Then, combine the current usage with the contributed usage. 262 # Thus, usage of {(f, g)} combined with {(a, b), (c, d)} would give 263 # {(f, g, a, b), (f, g, c, d)}. 264 265 return combine_mapping_dicts(deepen_mapping_dict(node._attrnames), contributor_usage), all_contributors 266 267 # Attribute usage methods. 268 269 def use_attribute(self, name, attrname, value=None): 270 271 """ 272 Note usage on the attribute user 'name' of the attribute 'attrname', 273 noting an assignment if 'value' is specified. 274 """ 275 276 return self._use_attribute(name, attrname, value) 277 278 def use_specific_attribute(self, objname, attrname): 279 280 "Declare the usage on 'objname' of the given 'attrname'." 281 282 self._use_specific_attribute(objname, attrname) 283 284 # These shadow various methods in the InspectedModule class, and provide 285 # implementations generally. 286 287 def _use_specific_attribute(self, objname, attrname, from_name=None): 288 289 """ 290 Note attribute usage specifically on 'objname' - an object which is 291 known at inspection time - or in the current unit if 'objname' is None, 292 nominating a specific attribute 'attrname'. 293 294 This bypasses attribute user mechanisms. 295 """ 296 297 from_name = from_name or self.full_name() 298 objname = objname or from_name 299 module = self.module 300 importer = module and module.importer 301 302 if importer is not None: 303 importer.use_specific_name(objname, attrname, from_name) 304 305 def _use_attribute(self, name, attrname, value=None): 306 307 """ 308 Indicate the use of the given 'name' in this namespace of an attribute 309 with the given 'attrname'. If the optional 'value' is specified, an 310 assignment using the given 'value' is recorded. 311 """ 312 313 users = self.attribute_users[-1] 314 315 # If no users are defined for the name, it cannot be handled. 316 317 if not users.has_key(name): 318 return [] 319 320 # Add the usage to all current users. 321 322 for user in users[name]: 323 values = user._attrnames[name] 324 if values is None: 325 values = user._attrnames[name] = ObjectSet() 326 327 # Add an entry for the attribute, optionally with an assigned 328 # value. 329 330 values.add(attrname) 331 if value is not None: 332 values[attrname].add(value) 333 334 return users[name] 335 336 def _define_attribute_user(self, node): 337 338 """ 339 Define 'node' as the user of attributes, indicating the point where the 340 user is defined. 341 """ 342 343 name = node.name 344 self._define_attribute_user_for_name(node, name) 345 346 def _define_attribute_user_for_name(self, node, name): 347 348 "Define 'node' as the user of attributes for the given 'name'." 349 350 users = self.attribute_users[-1] 351 352 # This node overrides previous definitions. 353 354 users[name] = set([node]) 355 356 # Record the attribute combinations for the name. 357 358 self._init_attribute_user_for_name(node, name) 359 360 # Remember this user. 361 362 self.all_attribute_users.add(node) 363 364 def _init_attribute_user_for_name(self, node, name): 365 366 "Make sure that 'node' is initialised for 'name'." 367 368 self._init_attribute_user(node) 369 node._attrnames[name] = None 370 371 def _init_attribute_user(self, node): 372 373 # Attribute usage for names. 374 375 if node._attrnames is None: 376 node._attrnames = {} 377 node._attrmerged = {} 378 379 # Branches contributing usage to this node. 380 381 if node._attrbranches is None: 382 node._attrbranches = [] 383 384 # Definitions receiving usage from this node. 385 386 if node._attrdefs is None: 387 node._attrdefs = [] 388 389 def _define_attribute_accessor(self, name, attrname, node, value): 390 391 # NOTE: Revisiting of nodes may occur for loops. 392 393 if node._attrusers is None: 394 node._attrusers = set() 395 396 node._attrusers.update(self.use_attribute(name, attrname, value)) 397 node._username = name 398 399 class ScopeUsage: 400 401 "Scope usage tracking." 402 403 def __init__(self): 404 405 # Scope usage, indicating the origin of names. 406 407 self.scope_usage = [{}] # stack of scope usage 408 409 def define_scope(self, name, scope): 410 411 """ 412 Define 'name' as being from the given 'scope' in the current namespace. 413 """ 414 415 self.scope_usage[-1][name] = scope 416 417 def defined_as_local(self, name): 418 419 "Return the scope defined for 'name' or None if it is not yet defined." 420 421 scope = self.scope_usage[-1].get(name) 422 return scope and (scope == "local" or isinstance(scope, ScopeConflict) and scope.is_benign()) 423 424 def note_scope(self, name, scope): 425 426 """ 427 Note usage of 'name' from the given 'scope' in the current namespace. 428 If a conflict has been recorded previously, raise an exception. 429 """ 430 431 scope_usage = self.scope_usage[-1] 432 433 if scope_usage.has_key(name): 434 found_scope = scope_usage[name] 435 if isinstance(found_scope, ScopeConflict): 436 if not found_scope.is_benign(): 437 raise InspectError("Scope conflict for %r: defined as %s." % ( 438 name, ", ".join(found_scope.scopes))) 439 else: 440 print >>sys.stderr, "Warning: name %r in %s may not be defined in all cases." % (name, self.full_name()) 441 442 scope_usage[name] = scope 443 444 def used_in_scope(self, name, scope): 445 446 """ 447 Return whether 'name' is used from the given 'scope' in the current 448 namespace. 449 """ 450 451 scope_usage = self.scope_usage[-1] 452 return scope_usage.get(name) == scope 453 454 class BranchTracking(AttributeUsage, ScopeUsage): 455 456 """ 457 Management of branches, relying on attribute usage support. 458 """ 459 460 def __init__(self): 461 AttributeUsage.__init__(self) 462 ScopeUsage.__init__(self) 463 464 # Details of attribute users at each active branch level. 465 466 self.attribute_user_shelves = [] 467 468 # Details of name scopes at each active branch level. 469 470 self.scope_shelves = [] 471 472 # Suspended user details plus loop details. 473 474 self.suspended_broken_users = [] # stack of lists of user dicts 475 self.suspended_continuing_users = [] # stack of lists of user dicts 476 477 # Abandoned usage, useful for reviving usage for exception handlers. 478 479 self.abandoned_users = [[]] # stack of lists of users 480 481 # Methods shadowing the convenience methods provided during inspection. 482 483 def _new_branchpoint(self, loop_node=None): 484 485 """ 486 Establish a new branchpoint where several control-flow branches diverge 487 and subsequently converge. 488 """ 489 490 self.attribute_user_shelves.append([]) 491 self.scope_shelves.append([]) 492 493 if loop_node is not None: 494 self.suspended_broken_users.append([]) 495 self.suspended_continuing_users.append((loop_node, [])) 496 497 def _new_branch(self, node): 498 499 """ 500 Establish a new control-flow branch, transferring attribute usage to 501 the new branch so that it may be augmented for each name locally. 502 503 Add the given 'node' as an active user to be informed of attribute 504 usage. 505 """ 506 507 attribute_users = self.attribute_users[-1] 508 509 # Define this node as the active attribute user for all currently 510 # defined names. 511 512 new_users = {} 513 514 for name in attribute_users.keys(): 515 new_users[name] = [node] 516 self._init_attribute_user_for_name(node, name) 517 518 self._init_attribute_user(node) 519 self.attribute_users.append(new_users) 520 521 # Add this user as a contributor to the previously active users. 522 523 self._connect_users_to_branch(attribute_users, node) 524 525 # Retain a record of scope usage. 526 527 scope_usage = {} 528 scope_usage.update(self.scope_usage[-1]) 529 self.scope_usage.append(scope_usage) 530 531 # Retain a record of abandoned branch users. 532 533 self.abandoned_users.append([]) 534 535 def _connect_users_to_branch(self, attribute_users, node): 536 537 """ 538 Given the 'attribute_users' mapping, connect the users referenced in the 539 mapping to the given branch 'node'. 540 """ 541 542 all_users = set() 543 544 for users in attribute_users.values(): 545 all_users.update(users) 546 547 for user in all_users: 548 self._init_attribute_user(user) 549 user._attrbranches.append(node) 550 551 def _abandon_branch(self, retain_branch=True): 552 553 """ 554 Abandon scope usage, permitting locally different scopes for names, 555 provided these cannot "escape" from the branch. 556 """ 557 558 attribute_users = self.attribute_users[-1] 559 560 self.attribute_users[-1] = {} 561 self.scope_usage[-1] = abandoned_branch_scope 562 563 if retain_branch: 564 self.abandoned_users[-1].append(attribute_users) 565 566 def _suspend_broken_branch(self): 567 568 """ 569 Suspend a branch for resumption after the current loop. 570 """ 571 572 attribute_users = self.attribute_users[-1] 573 574 users = self.suspended_broken_users[-1] 575 users.append(attribute_users) 576 self._abandon_branch(False) 577 578 def _suspend_continuing_branch(self): 579 580 """ 581 Suspend a branch for resumption after the current iteration. 582 """ 583 584 attribute_users = self.attribute_users[-1] 585 586 loop_node, users = self.suspended_continuing_users[-1] 587 users.append(attribute_users) 588 self._abandon_branch(False) 589 590 def _shelve_branch(self): 591 592 """ 593 Shelve the current control-flow branch, recording the attribute usage 594 for subsequent merging. If this branch should be abandoned, the usage 595 observations are still recorded but will not contribute to subsequent 596 observations after a merge. 597 """ 598 599 users = self.attribute_users.pop() 600 self.attribute_user_shelves[-1].append(users) 601 602 scope_usage = self.scope_usage.pop() 603 self.scope_shelves[-1].append(scope_usage) 604 605 def _merge_branches(self): 606 607 """ 608 Merge control-flow branches. This should find the users active within 609 each branch, which have been "shelved", and update the active users 610 dictionary with these contributions. 611 """ 612 613 # Combine the attribute users. This ensures that a list of users 614 # affected by attribute usage is maintained for the current branch. 615 616 all_shelved_users = self.attribute_user_shelves.pop() 617 new_users = merge_mapping_dicts(all_shelved_users) 618 self.attribute_users[-1] = new_users 619 620 # Abandoned users are retained for exception handling purposes. 621 622 all_abandoned_users = self.abandoned_users.pop() 623 new_abandoned_users = merge_mapping_dicts(all_abandoned_users) 624 self.abandoned_users[-1].append(new_abandoned_users) 625 626 # Combine the scope usage. 627 628 scope_usage = self.scope_usage[-1] 629 new_scope_usage = {} 630 631 all_scope_usage = self.scope_shelves.pop() 632 all_scope_names = set() 633 634 # Find all the names for whom scope information has been defined. 635 636 for shelved_usage in all_scope_usage: 637 all_scope_names.update(shelved_usage.keys()) 638 639 for shelved_usage in all_scope_usage: 640 for name in all_scope_names: 641 642 # Find the recorded scope for the name. 643 644 if shelved_usage.has_key(name): 645 scope = shelved_usage[name] 646 elif scope_usage.has_key(name): 647 scope = scope_usage[name] 648 649 # For abandoned branches, no scope is asserted for a name. 650 651 elif isinstance(shelved_usage, AbandonedBranchScope): 652 scope = None 653 654 # If no scope is recorded, find a suitable external source. 655 656 else: 657 attr, scope, full_name = self._get_with_scope(name, external=1) 658 if not attr: 659 scope = "unset" 660 661 # Attempt to record the scope, testing for conflicts. 662 663 if scope: 664 if not new_scope_usage.has_key(name): 665 new_scope_usage[name] = scope 666 else: 667 new_scope = new_scope_usage[name] 668 if new_scope != scope: 669 if isinstance(new_scope, ScopeConflict): 670 if isinstance(scope, ScopeConflict): 671 scopes = scope.scopes.union(new_scope.scopes) 672 else: 673 scopes = new_scope.scopes.union(set([scope])) 674 elif isinstance(scope, ScopeConflict): 675 scopes = scope.scopes.union(set([new_scope])) 676 else: 677 scopes = set([scope, new_scope]) 678 new_scope_usage[name] = ScopeConflict(scopes) 679 680 self.scope_usage[-1] = new_scope_usage 681 682 def _resume_broken_branches(self): 683 684 """ 685 Incorporate users from suspended broken branches into the current set of 686 active users. 687 """ 688 689 suspended_users = self.suspended_broken_users.pop() 690 current_users = self.attribute_users[-1] 691 new_users = merge_mapping_dicts(suspended_users + [current_users]) 692 self.attribute_users[-1] = new_users 693 694 def _resume_continuing_branches(self): 695 696 """ 697 Incorporate users from suspended continuing branches into the current 698 set of active users, merging usage from the latter with the former. 699 """ 700 701 loop_node, suspended_users = self.suspended_continuing_users.pop() 702 current_users = self.attribute_users[-1] 703 704 # Connect the suspended users to the loop node. 705 706 for users in suspended_users: 707 self._connect_users_to_branch(users, loop_node) 708 709 # Merge suspended branches with the current branch. 710 711 new_users = merge_mapping_dicts(suspended_users + [current_users]) 712 self.attribute_users[-1] = new_users 713 714 def _resume_abandoned_branches(self): 715 716 """ 717 Incorporate users from abandoned branches into the current set of active 718 users. The abandoned branches are taken from the containing branch. 719 """ 720 721 current_users = self.attribute_users[-1] 722 abandoned_users = self.abandoned_users[-2] 723 new_users = merge_mapping_dicts(abandoned_users + [current_users]) 724 self.attribute_users[-1] = new_users 725 726 # Special helper classes for usage and scope resolution. 727 728 class EmptyDict: 729 730 "A class providing dictionaries which retain no information." 731 732 def has_key(self, name): 733 return False 734 735 def __setitem__(self, name, value): 736 pass 737 738 def __getitem__(self, name): 739 raise KeyError, name 740 741 def get(self, name, default=None): 742 return default 743 744 def keys(self): 745 return [] 746 747 values = items = keys 748 749 class AbandonedBranchScope(EmptyDict): 750 751 """ 752 A class providing a value or state for an abandoned branch distinct from an 753 empty scope dictionary. 754 """ 755 756 pass 757 758 abandoned_branch_scope = AbandonedBranchScope() 759 760 class ScopeConflict: 761 762 """ 763 A class whose instances provide a collection of scope alternatives, either 764 potentially benign or indicating a serious problem. 765 766 A scope conflict is caused when different code branches contribute different 767 sources of names or where branches neglect to contribute names at all. Where 768 the sources (scopes) indicated are different, a serious problem exists 769 because the name has no single way of being accessed. 770 """ 771 772 def __init__(self, scopes): 773 self.scopes = scopes 774 775 def is_benign(self): 776 return len(self.scopes) == 2 and "unset" in self.scopes 777 778 class UnsetType: 779 780 "A None-like value." 781 782 def __nonzero__(self): 783 return False 784 785 Unset = UnsetType() 786 787 # vim: tabstop=4 expandtab shiftwidth=4