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