1 #!/usr/bin/env python 2 3 """ 4 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 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 node._attrcombined = Unset 176 177 for contributor in node._attrbranches: 178 179 # Get contributor details. 180 181 unfinished_contributors = self.get_usage_from_contributors(contributor) 182 183 # Collect unfinished contributors and affected nodes. 184 185 # Where the contributor is already set to Unset, a loop has 186 # occurred and this node will need to have its usage 187 # recalculated later for the unfinished contributor. 188 189 if contributor._attrcombined is Unset: 190 if not unfinished.has_key(contributor): 191 unfinished[contributor] = [] 192 unfinished[contributor].append(node) 193 continue 194 195 # Where the contributor provides usage details, it may also 196 # communicate unfinished contributor information. As a 197 # consequence, this node is also affected. 198 199 for unfinished_contributor, nodes in unfinished_contributors.items(): 200 if not unfinished.has_key(unfinished_contributor): 201 unfinished[unfinished_contributor] = nodes 202 else: 203 unfinished[unfinished_contributor] += nodes 204 205 if node not in unfinished[unfinished_contributor]: 206 unfinished[unfinished_contributor].append(node) 207 208 # Set the current state of the usage on this node. 209 210 node._attrcombined, node._attrcontributors = \ 211 self.get_usage_from_contributors_for_node(node) 212 213 # Complete unfinished contributors relying on this node. 214 215 if unfinished.has_key(node): 216 processed = set() 217 for contributor in unfinished[node]: 218 if not contributor in processed: 219 processed.add(contributor) 220 221 contributor._attrcombined, contributor._attrcontributors = \ 222 self.get_usage_from_contributors_for_node(contributor) 223 224 del unfinished[node] 225 226 return unfinished 227 228 def get_usage_from_contributors_for_node(self, node): 229 230 # Visit each contributor, gathering usage for each name. 231 232 contributor_usage = {} 233 all_contributions = [] 234 all_contributors = set() 235 236 for contributor in node._attrbranches: 237 usage = contributor._attrcombined 238 if usage is not Unset: 239 all_contributions.append(usage) 240 241 all_contributors.add(contributor) 242 contributors = contributor._attrcontributors 243 if contributors is not None: 244 all_contributors.update(contributors) 245 246 # Get contributed usage for each contributor. 247 # This gathers usage for each name such as {(a, b), (c, d)} and 248 # {(a, b), (e, f)} into a single set {(a, b), (c, d), (e, f)}. 249 250 update_mapping_dict(contributor_usage, all_contributions) 251 252 # Then get the resulting usage. 253 # First, make the current usage compatible with the contributed 254 # usage: this makes the attribute usage for each name merely one 255 # member in a list of many possibilities. 256 # Then, combine the current usage with the contributed usage. 257 # Thus, usage of {(f, g)} combined with {(a, b), (c, d)} would give 258 # {(f, g, a, b), (f, g, c, d)}. 259 260 return combine_mapping_dicts(deepen_mapping_dict(node._attrnames), contributor_usage), all_contributors 261 262 # Attribute usage methods. 263 264 def use_attribute(self, name, attrname, value=None): 265 266 """ 267 Note usage on the attribute user 'name' of the attribute 'attrname', 268 noting an assignment if 'value' is specified. 269 """ 270 271 return self._use_attribute(name, attrname, value) 272 273 def use_specific_attribute(self, objname, attrname): 274 275 "Declare the usage on 'objname' of the given 'attrname'." 276 277 self._use_specific_attribute(objname, attrname) 278 279 # These shadow various methods in the InspectedModule class, and provide 280 # implementations generally. 281 282 def _use_specific_attribute(self, objname, attrname, from_name=None): 283 284 """ 285 Note attribute usage specifically on 'objname' - an object which is 286 known at inspection time - or in the current unit if 'objname' is None, 287 nominating a specific attribute 'attrname'. 288 289 This bypasses attribute user mechanisms. 290 """ 291 292 from_name = from_name or self.full_name() 293 objname = objname or from_name 294 module = self.module 295 importer = module and module.importer 296 297 if importer is not None: 298 importer.use_specific_name(objname, attrname, from_name) 299 300 def _use_attribute(self, name, attrname, value=None): 301 302 """ 303 Indicate the use of the given 'name' in this namespace of an attribute 304 with the given 'attrname'. If the optional 'value' is specified, an 305 assignment using the given 'value' is recorded. 306 """ 307 308 users = self.attribute_users[-1] 309 310 # If no users are defined for the name, it cannot be handled. 311 312 if not users.has_key(name): 313 return [] 314 315 # Add the usage to all current users. 316 317 for user in users[name]: 318 values = user._attrnames[name] 319 if values is None: 320 values = user._attrnames[name] = ObjectSet() 321 322 # Add an entry for the attribute, optionally with an assigned 323 # value. 324 325 values.add(attrname) 326 if value is not None: 327 values[attrname].add(value) 328 329 return users[name] 330 331 def _define_attribute_user(self, node): 332 333 """ 334 Define 'node' as the user of attributes, indicating the point where the 335 user is defined. 336 """ 337 338 name = node.name 339 self._define_attribute_user_for_name(node, name) 340 341 def _define_attribute_user_for_name(self, node, name): 342 343 "Define 'node' as the user of attributes for the given 'name'." 344 345 users = self.attribute_users[-1] 346 347 # This node overrides previous definitions. 348 349 users[name] = set([node]) 350 351 # Record the attribute combinations for the name. 352 353 self._init_attribute_user_for_name(node, name) 354 355 # Remember this user. 356 357 self.all_attribute_users.add(node) 358 359 def _init_attribute_user_for_name(self, node, name): 360 361 "Make sure that 'node' is initialised for 'name'." 362 363 self._init_attribute_user(node) 364 node._attrnames[name] = None 365 366 def _init_attribute_user(self, node): 367 368 # Attribute usage for names. 369 370 if node._attrnames is None: 371 node._attrnames = {} 372 node._attrmerged = {} 373 374 # Branches contributing usage to this node. 375 376 if node._attrbranches is None: 377 node._attrbranches = [] 378 379 # Definitions receiving usage from this node. 380 381 if node._attrdefs is None: 382 node._attrdefs = [] 383 384 def _define_attribute_accessor(self, name, attrname, node, value): 385 386 # NOTE: Revisiting of nodes may occur for loops. 387 388 if node._attrusers is None: 389 node._attrusers = set() 390 391 node._attrusers.update(self.use_attribute(name, attrname, value)) 392 node._username = name 393 394 class ScopeUsage: 395 396 "Scope usage tracking." 397 398 def __init__(self): 399 400 # Scope usage, indicating the origin of names. 401 402 self.scope_usage = [{}] # stack of scope usage 403 404 def define_scope(self, name, scope): 405 406 """ 407 Define 'name' as being from the given 'scope' in the current namespace. 408 """ 409 410 self.scope_usage[-1][name] = scope 411 412 def note_scope(self, name, scope): 413 414 """ 415 Note usage of 'name' from the given 'scope' in the current namespace. 416 If a conflict has been recorded previously, raise an exception. 417 """ 418 419 scope_usage = self.scope_usage[-1] 420 421 if scope_usage.has_key(name): 422 found_scope = scope_usage[name] 423 if isinstance(found_scope, ScopeConflict): 424 raise InspectError("Scope conflict for %r: defined as %s." % ( 425 name, ", ".join(found_scope.scopes))) 426 427 scope_usage[name] = scope 428 429 def used_in_scope(self, name, scope): 430 431 """ 432 Return whether 'name' is used from the given 'scope' in the current 433 namespace. 434 """ 435 436 scope_usage = self.scope_usage[-1] 437 return scope_usage.get(name) == scope 438 439 class BranchTracking(AttributeUsage, ScopeUsage): 440 441 """ 442 Management of branches, relying on attribute usage support. 443 """ 444 445 def __init__(self): 446 AttributeUsage.__init__(self) 447 ScopeUsage.__init__(self) 448 449 # Details of attribute users at each active branch level. 450 451 self.attribute_user_shelves = [] 452 453 # Details of name scopes at each active branch level. 454 455 self.scope_shelves = [] 456 457 # Suspended user details plus loop details. 458 459 self.suspended_broken_users = [] # stack of lists of user dicts 460 self.suspended_continuing_users = [] # stack of lists of user dicts 461 462 # Abandoned usage, useful for reviving usage for exception handlers. 463 464 self.abandoned_users = [[]] # stack of lists of users 465 466 # Methods shadowing the convenience methods provided during inspection. 467 468 def _new_branchpoint(self, loop_node=None): 469 470 """ 471 Establish a new branchpoint where several control-flow branches diverge 472 and subsequently converge. 473 """ 474 475 self.attribute_user_shelves.append([]) 476 self.scope_shelves.append([]) 477 478 if loop_node is not None: 479 self.suspended_broken_users.append([]) 480 self.suspended_continuing_users.append((loop_node, [])) 481 482 def _new_branch(self, node): 483 484 """ 485 Establish a new control-flow branch, transferring attribute usage to 486 the new branch so that it may be augmented for each name locally. 487 488 Add the given 'node' as an active user to be informed of attribute 489 usage. 490 """ 491 492 attribute_users = self.attribute_users[-1] 493 494 # Define this node as the active attribute user for all currently 495 # defined names. 496 497 new_users = {} 498 499 for name in attribute_users.keys(): 500 new_users[name] = [node] 501 self._init_attribute_user_for_name(node, name) 502 503 self._init_attribute_user(node) 504 self.attribute_users.append(new_users) 505 506 # Add this user as a contributor to the previously active users. 507 508 self._connect_users_to_branch(attribute_users, node) 509 510 # Retain a record of scope usage. 511 512 scope_usage = {} 513 scope_usage.update(self.scope_usage[-1]) 514 self.scope_usage.append(scope_usage) 515 516 # Retain a record of abandoned branch users. 517 518 self.abandoned_users.append([]) 519 520 def _connect_users_to_branch(self, attribute_users, node): 521 522 """ 523 Given the 'attribute_users' mapping, connect the users referenced in the 524 mapping to the given branch 'node'. 525 """ 526 527 all_users = set() 528 529 for users in attribute_users.values(): 530 all_users.update(users) 531 532 for user in all_users: 533 self._init_attribute_user(user) 534 user._attrbranches.append(node) 535 536 def _abandon_branch(self, retain_branch=True): 537 538 """ 539 Abandon scope usage, permitting locally different scopes for names, 540 provided these cannot "escape" from the branch. 541 """ 542 543 attribute_users = self.attribute_users[-1] 544 545 self.attribute_users[-1] = {} 546 self.scope_usage[-1] = abandoned_branch_scope 547 548 if retain_branch: 549 self.abandoned_users[-1].append(attribute_users) 550 551 def _suspend_broken_branch(self): 552 553 """ 554 Suspend a branch for resumption after the current loop. 555 """ 556 557 attribute_users = self.attribute_users[-1] 558 559 users = self.suspended_broken_users[-1] 560 users.append(attribute_users) 561 self._abandon_branch(False) 562 563 def _suspend_continuing_branch(self): 564 565 """ 566 Suspend a branch for resumption after the current iteration. 567 """ 568 569 attribute_users = self.attribute_users[-1] 570 571 loop_node, users = self.suspended_continuing_users[-1] 572 users.append(attribute_users) 573 self._abandon_branch(False) 574 575 def _shelve_branch(self): 576 577 """ 578 Shelve the current control-flow branch, recording the attribute usage 579 for subsequent merging. If this branch should be abandoned, the usage 580 observations are still recorded but will not contribute to subsequent 581 observations after a merge. 582 """ 583 584 users = self.attribute_users.pop() 585 self.attribute_user_shelves[-1].append(users) 586 587 scope_usage = self.scope_usage.pop() 588 self.scope_shelves[-1].append(scope_usage) 589 590 def _merge_branches(self): 591 592 """ 593 Merge control-flow branches. This should find the users active within 594 each branch, which have been "shelved", and update the active users 595 dictionary with these contributions. 596 """ 597 598 # Combine the attribute users. This ensures that a list of users 599 # affected by attribute usage is maintained for the current branch. 600 601 all_shelved_users = self.attribute_user_shelves.pop() 602 new_users = merge_mapping_dicts(all_shelved_users) 603 self.attribute_users[-1] = new_users 604 605 # Abandoned users are retained for exception handling purposes. 606 607 all_abandoned_users = self.abandoned_users.pop() 608 new_abandoned_users = merge_mapping_dicts(all_abandoned_users) 609 self.abandoned_users[-1].append(new_abandoned_users) 610 611 # Combine the scope usage. 612 613 scope_usage = self.scope_usage[-1] 614 new_scope_usage = {} 615 616 all_scope_usage = self.scope_shelves.pop() 617 all_scope_names = set() 618 619 # Find all the names for whom scope information has been defined. 620 621 for shelved_usage in all_scope_usage: 622 all_scope_names.update(shelved_usage.keys()) 623 624 for shelved_usage in all_scope_usage: 625 for name in all_scope_names: 626 627 # Find the recorded scope for the name. 628 629 if shelved_usage.has_key(name): 630 scope = shelved_usage[name] 631 elif scope_usage.has_key(name): 632 scope = scope_usage[name] 633 634 # For abandoned branches, no scope is asserted for a name. 635 636 elif isinstance(shelved_usage, AbandonedBranchScope): 637 scope = None 638 639 # If no scope is recorded, find a suitable external source. 640 641 else: 642 attr, scope, full_name = self._get_with_scope(name, external=1) 643 644 # Attempt to record the scope, testing for conflicts. 645 646 if scope: 647 if not new_scope_usage.has_key(name): 648 new_scope_usage[name] = scope 649 else: 650 new_scope = new_scope_usage[name] 651 if new_scope != scope: 652 if isinstance(new_scope, ScopeConflict): 653 if isinstance(scope, ScopeConflict): 654 scopes = scope.scopes.union(new_scope.scopes) 655 else: 656 scopes = new_scope.scopes.union(set([scope])) 657 elif isinstance(scope, ScopeConflict): 658 scopes = scope.scopes.union(set([new_scope])) 659 else: 660 scopes = set([scope, new_scope]) 661 new_scope_usage[name] = ScopeConflict(scopes) 662 663 self.scope_usage[-1] = new_scope_usage 664 665 def _resume_broken_branches(self): 666 667 """ 668 Incorporate users from suspended broken branches into the current set of 669 active users. 670 """ 671 672 suspended_users = self.suspended_broken_users.pop() 673 current_users = self.attribute_users[-1] 674 new_users = merge_mapping_dicts(suspended_users + [current_users]) 675 self.attribute_users[-1] = new_users 676 677 def _resume_continuing_branches(self): 678 679 """ 680 Incorporate users from suspended continuing branches into the current 681 set of active users, merging usage from the latter with the former. 682 """ 683 684 loop_node, suspended_users = self.suspended_continuing_users.pop() 685 current_users = self.attribute_users[-1] 686 687 # Connect the suspended users to the loop node. 688 689 for users in suspended_users: 690 self._connect_users_to_branch(users, loop_node) 691 692 # Merge suspended branches with the current branch. 693 694 new_users = merge_mapping_dicts(suspended_users + [current_users]) 695 self.attribute_users[-1] = new_users 696 697 def _resume_abandoned_branches(self): 698 699 """ 700 Incorporate users from abandoned branches into the current set of active 701 users. The abandoned branches are taken from the containing branch. 702 """ 703 704 current_users = self.attribute_users[-1] 705 abandoned_users = self.abandoned_users[-2] 706 new_users = merge_mapping_dicts(abandoned_users + [current_users]) 707 self.attribute_users[-1] = new_users 708 709 # Special helper classes for usage and scope resolution. 710 711 class EmptyDict: 712 713 "A class providing dictionaries which retain no information." 714 715 def has_key(self, name): 716 return False 717 718 def __setitem__(self, name, value): 719 pass 720 721 def __getitem__(self, name): 722 raise KeyError, name 723 724 def get(self, name, default=None): 725 return default 726 727 def keys(self): 728 return [] 729 730 values = items = keys 731 732 class AbandonedBranchScope(EmptyDict): 733 734 """ 735 A class providing a value or state for an abandoned branch distinct from an 736 empty scope dictionary. 737 """ 738 739 pass 740 741 abandoned_branch_scope = AbandonedBranchScope() 742 743 class ScopeConflict: 744 745 """ 746 A scope conflict caused when different code branches contribute different 747 sources of names. 748 """ 749 750 def __init__(self, scopes): 751 self.scopes = scopes 752 753 class UnsetType: 754 755 "A None-like value." 756 757 def __nonzero__(self): 758 return False 759 760 Unset = UnsetType() 761 762 # vim: tabstop=4 expandtab shiftwidth=4