1 #!/usr/bin/env python 2 3 """ 4 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013 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 note_scope(self, name, scope): 418 419 """ 420 Note usage of 'name' from the given 'scope' in the current namespace. 421 If a conflict has been recorded previously, raise an exception. 422 """ 423 424 scope_usage = self.scope_usage[-1] 425 426 if scope_usage.has_key(name): 427 found_scope = scope_usage[name] 428 if isinstance(found_scope, ScopeConflict): 429 raise InspectError("Scope conflict for %r: defined as %s." % ( 430 name, ", ".join(found_scope.scopes))) 431 432 scope_usage[name] = scope 433 434 def used_in_scope(self, name, scope): 435 436 """ 437 Return whether 'name' is used from the given 'scope' in the current 438 namespace. 439 """ 440 441 scope_usage = self.scope_usage[-1] 442 return scope_usage.get(name) == scope 443 444 class BranchTracking(AttributeUsage, ScopeUsage): 445 446 """ 447 Management of branches, relying on attribute usage support. 448 """ 449 450 def __init__(self): 451 AttributeUsage.__init__(self) 452 ScopeUsage.__init__(self) 453 454 # Details of attribute users at each active branch level. 455 456 self.attribute_user_shelves = [] 457 458 # Details of name scopes at each active branch level. 459 460 self.scope_shelves = [] 461 462 # Suspended user details plus loop details. 463 464 self.suspended_broken_users = [] # stack of lists of user dicts 465 self.suspended_continuing_users = [] # stack of lists of user dicts 466 467 # Abandoned usage, useful for reviving usage for exception handlers. 468 469 self.abandoned_users = [[]] # stack of lists of users 470 471 # Methods shadowing the convenience methods provided during inspection. 472 473 def _new_branchpoint(self, loop_node=None): 474 475 """ 476 Establish a new branchpoint where several control-flow branches diverge 477 and subsequently converge. 478 """ 479 480 self.attribute_user_shelves.append([]) 481 self.scope_shelves.append([]) 482 483 if loop_node is not None: 484 self.suspended_broken_users.append([]) 485 self.suspended_continuing_users.append((loop_node, [])) 486 487 def _new_branch(self, node): 488 489 """ 490 Establish a new control-flow branch, transferring attribute usage to 491 the new branch so that it may be augmented for each name locally. 492 493 Add the given 'node' as an active user to be informed of attribute 494 usage. 495 """ 496 497 attribute_users = self.attribute_users[-1] 498 499 # Define this node as the active attribute user for all currently 500 # defined names. 501 502 new_users = {} 503 504 for name in attribute_users.keys(): 505 new_users[name] = [node] 506 self._init_attribute_user_for_name(node, name) 507 508 self._init_attribute_user(node) 509 self.attribute_users.append(new_users) 510 511 # Add this user as a contributor to the previously active users. 512 513 self._connect_users_to_branch(attribute_users, node) 514 515 # Retain a record of scope usage. 516 517 scope_usage = {} 518 scope_usage.update(self.scope_usage[-1]) 519 self.scope_usage.append(scope_usage) 520 521 # Retain a record of abandoned branch users. 522 523 self.abandoned_users.append([]) 524 525 def _connect_users_to_branch(self, attribute_users, node): 526 527 """ 528 Given the 'attribute_users' mapping, connect the users referenced in the 529 mapping to the given branch 'node'. 530 """ 531 532 all_users = set() 533 534 for users in attribute_users.values(): 535 all_users.update(users) 536 537 for user in all_users: 538 self._init_attribute_user(user) 539 user._attrbranches.append(node) 540 541 def _abandon_branch(self, retain_branch=True): 542 543 """ 544 Abandon scope usage, permitting locally different scopes for names, 545 provided these cannot "escape" from the branch. 546 """ 547 548 attribute_users = self.attribute_users[-1] 549 550 self.attribute_users[-1] = {} 551 self.scope_usage[-1] = abandoned_branch_scope 552 553 if retain_branch: 554 self.abandoned_users[-1].append(attribute_users) 555 556 def _suspend_broken_branch(self): 557 558 """ 559 Suspend a branch for resumption after the current loop. 560 """ 561 562 attribute_users = self.attribute_users[-1] 563 564 users = self.suspended_broken_users[-1] 565 users.append(attribute_users) 566 self._abandon_branch(False) 567 568 def _suspend_continuing_branch(self): 569 570 """ 571 Suspend a branch for resumption after the current iteration. 572 """ 573 574 attribute_users = self.attribute_users[-1] 575 576 loop_node, users = self.suspended_continuing_users[-1] 577 users.append(attribute_users) 578 self._abandon_branch(False) 579 580 def _shelve_branch(self): 581 582 """ 583 Shelve the current control-flow branch, recording the attribute usage 584 for subsequent merging. If this branch should be abandoned, the usage 585 observations are still recorded but will not contribute to subsequent 586 observations after a merge. 587 """ 588 589 users = self.attribute_users.pop() 590 self.attribute_user_shelves[-1].append(users) 591 592 scope_usage = self.scope_usage.pop() 593 self.scope_shelves[-1].append(scope_usage) 594 595 def _merge_branches(self): 596 597 """ 598 Merge control-flow branches. This should find the users active within 599 each branch, which have been "shelved", and update the active users 600 dictionary with these contributions. 601 """ 602 603 # Combine the attribute users. This ensures that a list of users 604 # affected by attribute usage is maintained for the current branch. 605 606 all_shelved_users = self.attribute_user_shelves.pop() 607 new_users = merge_mapping_dicts(all_shelved_users) 608 self.attribute_users[-1] = new_users 609 610 # Abandoned users are retained for exception handling purposes. 611 612 all_abandoned_users = self.abandoned_users.pop() 613 new_abandoned_users = merge_mapping_dicts(all_abandoned_users) 614 self.abandoned_users[-1].append(new_abandoned_users) 615 616 # Combine the scope usage. 617 618 scope_usage = self.scope_usage[-1] 619 new_scope_usage = {} 620 621 all_scope_usage = self.scope_shelves.pop() 622 all_scope_names = set() 623 624 # Find all the names for whom scope information has been defined. 625 626 for shelved_usage in all_scope_usage: 627 all_scope_names.update(shelved_usage.keys()) 628 629 for shelved_usage in all_scope_usage: 630 for name in all_scope_names: 631 632 # Find the recorded scope for the name. 633 634 if shelved_usage.has_key(name): 635 scope = shelved_usage[name] 636 elif scope_usage.has_key(name): 637 scope = scope_usage[name] 638 639 # For abandoned branches, no scope is asserted for a name. 640 641 elif isinstance(shelved_usage, AbandonedBranchScope): 642 scope = None 643 644 # If no scope is recorded, find a suitable external source. 645 646 else: 647 attr, scope, full_name = self._get_with_scope(name, external=1) 648 649 # Attempt to record the scope, testing for conflicts. 650 651 if scope: 652 if not new_scope_usage.has_key(name): 653 new_scope_usage[name] = scope 654 else: 655 new_scope = new_scope_usage[name] 656 if new_scope != scope: 657 if isinstance(new_scope, ScopeConflict): 658 if isinstance(scope, ScopeConflict): 659 scopes = scope.scopes.union(new_scope.scopes) 660 else: 661 scopes = new_scope.scopes.union(set([scope])) 662 elif isinstance(scope, ScopeConflict): 663 scopes = scope.scopes.union(set([new_scope])) 664 else: 665 scopes = set([scope, new_scope]) 666 new_scope_usage[name] = ScopeConflict(scopes) 667 668 self.scope_usage[-1] = new_scope_usage 669 670 def _resume_broken_branches(self): 671 672 """ 673 Incorporate users from suspended broken branches into the current set of 674 active users. 675 """ 676 677 suspended_users = self.suspended_broken_users.pop() 678 current_users = self.attribute_users[-1] 679 new_users = merge_mapping_dicts(suspended_users + [current_users]) 680 self.attribute_users[-1] = new_users 681 682 def _resume_continuing_branches(self): 683 684 """ 685 Incorporate users from suspended continuing branches into the current 686 set of active users, merging usage from the latter with the former. 687 """ 688 689 loop_node, suspended_users = self.suspended_continuing_users.pop() 690 current_users = self.attribute_users[-1] 691 692 # Connect the suspended users to the loop node. 693 694 for users in suspended_users: 695 self._connect_users_to_branch(users, loop_node) 696 697 # Merge suspended branches with the current branch. 698 699 new_users = merge_mapping_dicts(suspended_users + [current_users]) 700 self.attribute_users[-1] = new_users 701 702 def _resume_abandoned_branches(self): 703 704 """ 705 Incorporate users from abandoned branches into the current set of active 706 users. The abandoned branches are taken from the containing branch. 707 """ 708 709 current_users = self.attribute_users[-1] 710 abandoned_users = self.abandoned_users[-2] 711 new_users = merge_mapping_dicts(abandoned_users + [current_users]) 712 self.attribute_users[-1] = new_users 713 714 # Special helper classes for usage and scope resolution. 715 716 class EmptyDict: 717 718 "A class providing dictionaries which retain no information." 719 720 def has_key(self, name): 721 return False 722 723 def __setitem__(self, name, value): 724 pass 725 726 def __getitem__(self, name): 727 raise KeyError, name 728 729 def get(self, name, default=None): 730 return default 731 732 def keys(self): 733 return [] 734 735 values = items = keys 736 737 class AbandonedBranchScope(EmptyDict): 738 739 """ 740 A class providing a value or state for an abandoned branch distinct from an 741 empty scope dictionary. 742 """ 743 744 pass 745 746 abandoned_branch_scope = AbandonedBranchScope() 747 748 class ScopeConflict: 749 750 """ 751 A scope conflict caused when different code branches contribute different 752 sources of names. 753 """ 754 755 def __init__(self, scopes): 756 self.scopes = scopes 757 758 class UnsetType: 759 760 "A None-like value." 761 762 def __nonzero__(self): 763 return False 764 765 Unset = UnsetType() 766 767 # vim: tabstop=4 expandtab shiftwidth=4