1 #!/usr/bin/env python 2 3 """ 4 Track attribute usage for names. 5 6 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013, 7 2014, 2015, 2016 Paul Boddie <paul@boddie.org.uk> 8 9 This program is free software; you can redistribute it and/or modify it under 10 the terms of the GNU General Public License as published by the Free Software 11 Foundation; either version 3 of the License, or (at your option) any later 12 version. 13 14 This program is distributed in the hope that it will be useful, but WITHOUT 15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 16 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 17 details. 18 19 You should have received a copy of the GNU General Public License along with 20 this program. If not, see <http://www.gnu.org/licenses/>. 21 """ 22 23 from common import dict_for_keys, init_item 24 25 class Branch: 26 27 """ 28 A control-flow branch capturing local attribute usage for names. 29 Branches typically begin with assignments or function parameters and are 30 connected to others introduced by conditional and loop nodes. 31 32 Branches hosting accesses, and thus providing usage information, are 33 contributors to preceding branches. 34 35 Branches also provide a route from accesses back to assignments which are 36 the ultimate suppliers of the names involved. 37 """ 38 39 def __init__(self, names, assigning=False, values=None): 40 41 """ 42 Capture attribute usage for the given 'names', with the accompanying 43 'values' indicating assigned values for each name, if indicated. 44 """ 45 46 self.contributors = set() 47 self.suppliers = {} 48 self.assignments = set(assigning and names or []) 49 self.usage = {} 50 self.values = {} 51 52 # Initialise usage for each name. 53 54 for name in names: 55 self.usage[name] = set() 56 57 # Initialise assigned values if any were provided. 58 59 if values: 60 for name, value in zip(names, values): 61 if value: 62 self.values[name] = value 63 64 # Computed results. 65 66 self.combined_usage = None 67 68 def get_assignment_sources(self, name): 69 70 """ 71 Return the sources of 'name' from this branch's assignment information, 72 returning a list containing only this branch itself if it is the source. 73 """ 74 75 if name in self.assignments: 76 return [self] 77 else: 78 return [b for b in self.get_all_suppliers(name) if name in b.assignments] 79 80 def set_usage(self, name, attrname): 81 82 """ 83 Record usage on the given 'name' of the attribute 'attrname'. 84 """ 85 86 if self.usage.has_key(name): 87 self.usage[name].add(attrname) 88 89 def get_usage(self): 90 91 """ 92 Obtain usage from this node, combined with usage observed by its 93 contributors. Unlike the local usage which involves only a single set of 94 attribute names for a given variable name, the returned usage is a set 95 of attribute name combinations for a given variable name. For example: 96 97 {'a': set([('p', 'q', 'r'), ('p', 'r')])} 98 """ 99 100 if self.combined_usage is None: 101 102 # Accumulate usage observations from contributors. 103 104 all_usage = [] 105 106 for contributor in self.contributors: 107 108 # Record any usage that can be returned. 109 110 all_usage.append(contributor.get_usage()) 111 112 # Merge usage from the contributors. 113 114 merged_usage = merge_dicts(all_usage) 115 116 # Make the local usage compatible with the combined usage. 117 118 usage = deepen_dict(self.usage) 119 120 self.combined_usage = combine_dicts(usage, merged_usage, combine_sets) 121 122 return self.combined_usage 123 124 def get_all_suppliers(self, name, all_suppliers=None): 125 126 "Return all branches supplying this branch with definitions of 'name'." 127 128 all_suppliers = all_suppliers or set() 129 all_suppliers.add(self) 130 131 if self.suppliers.has_key(name): 132 for supplier in self.suppliers[name]: 133 if supplier not in all_suppliers: 134 supplier.get_all_suppliers(name, all_suppliers) 135 136 return all_suppliers 137 138 def __repr__(self): 139 return "Branch(%r, %r)" % (self.usage.keys(), 140 self.assignments and True or False) 141 142 class BranchTracker: 143 144 """ 145 A tracker of attribute usage for names in a namespace. This tracker directs 146 usage observations to branches which are the ultimate repositories of 147 attribute usage information. 148 149 As a program unit is inspected, the branches associated with names may 150 change. Assignments reset the branches; control-flow operations cause 151 branches to be accumulated from different code paths. 152 """ 153 154 def __init__(self): 155 156 # Track assignments. 157 158 self.assignments = {} 159 160 # Details of attributes at each active branch level. 161 162 self.attribute_branches = [{}] # stack of branches for names 163 self.attribute_branch_shelves = [] # stack of shelved branches 164 165 # Suspended branch details plus loop details. 166 167 self.suspended_broken_branches = [] # stack of lists of dicts 168 self.suspended_continuing_branches = [] # stack of lists of dicts 169 170 # Abandoned usage, useful for reviving usage for exception handlers. 171 172 self.abandoned_branches = [[]] # stack of lists of branches 173 174 # Returning branches are like abandoned branches but are only revived in 175 # finally clauses. 176 177 self.returning_branches = [[]] 178 179 # Branches active when starting loops. 180 181 self.loop_branches = [] 182 183 # Structure assembly methods. 184 185 def new_branchpoint(self, loop_node=False): 186 187 """ 188 Indicate that branches diverge, initialising resources dependent on 189 any given 'loop_node'. 190 """ 191 192 self.attribute_branch_shelves.append([]) 193 194 if loop_node: 195 self.suspended_broken_branches.append([]) 196 self.suspended_continuing_branches.append([]) 197 198 # Retain a record of abandoned branches. 199 200 self.abandoned_branches.append([]) 201 self.returning_branches.append([]) 202 203 def new_branch(self, loop_node=False): 204 205 "Create a new branch." 206 207 attribute_branches = self.attribute_branches[-1] 208 209 branch, new_branches = self._new_branch(attribute_branches) 210 211 if branch and loop_node: 212 self.loop_branches.append(branch) 213 214 # Start using the branch for known names. 215 216 self.attribute_branches.append(new_branches) 217 218 def _new_branch(self, attribute_branches): 219 220 """ 221 Define a new branch that will record attribute usage on known names from 222 'attribute_branches'. 223 """ 224 225 # Detect abandoned branches. 226 227 if isinstance(attribute_branches, AbandonedDict): 228 return None, AbandonedDict() 229 230 # Otherwise, define a new branch. 231 232 names = attribute_branches.keys() 233 234 new_branches = {} 235 branch = Branch(names) 236 237 for name in names: 238 new_branches[name] = [branch] 239 240 # Add this new branch as a contributor to the previously active 241 # branches. 242 243 self._connect_branches(attribute_branches, branch) 244 245 return branch, new_branches 246 247 def shelve_branch(self, loop_node=False): 248 249 "Retain the current branch for later merging." 250 251 branches = self.attribute_branches.pop() 252 self.attribute_branch_shelves[-1].append(branches) 253 254 # Connect any loop branch to the active branches as contributors. 255 256 if loop_node: 257 branch = self.loop_branches.pop() 258 self._connect_branches(branches, branch, loop_node) 259 260 def abandon_branch(self): 261 262 "Abandon the current branch, retaining it for later." 263 264 attribute_branches = self.attribute_branches[-1] 265 self._abandon_branch() 266 self.abandoned_branches[-1].append(attribute_branches) 267 268 def abandon_returning_branch(self): 269 270 "Abandon the current branch, retaining it for later." 271 272 attribute_branches = self.attribute_branches[-1] 273 self._abandon_branch() 274 self.returning_branches[-1].append(attribute_branches) 275 276 def suspend_broken_branch(self): 277 278 "Suspend a branch for breaking out of a loop." 279 280 attribute_branches = self.attribute_branches[-1] 281 282 branches = self.suspended_broken_branches[-1] 283 branches.append(attribute_branches) 284 self._abandon_branch() 285 286 def suspend_continuing_branch(self): 287 288 "Suspend a branch for loop continuation." 289 290 attribute_branches = self.attribute_branches[-1] 291 292 branches = self.suspended_continuing_branches[-1] 293 branches.append(attribute_branches) 294 self._abandon_branch() 295 296 def _abandon_branch(self): 297 298 "Abandon the current branch." 299 300 self.attribute_branches[-1] = AbandonedDict() 301 302 def resume_abandoned_branches(self): 303 304 """ 305 Resume branches previously abandoned. 306 307 Abandoned branches are not reset because they may not be handled by 308 exception handlers after all. 309 """ 310 311 current_branches = self.attribute_branches[-1] 312 abandoned_branches = self.abandoned_branches[-1] 313 merged_branches = merge_dicts(abandoned_branches + [current_branches]) 314 315 # Replace the combined branches with a new branch applying to all active 316 # names, connected to the supplying branches. 317 318 branch, new_branches = self._new_branch(merged_branches) 319 self.attribute_branches.append(new_branches) 320 321 # Although returning branches should not be considered as accumulating 322 # usage, they do provide sources of assignments. 323 324 if branch: 325 for returning_branches in self.returning_branches[-1]: 326 self._connect_suppliers(returning_branches, branch) 327 328 def resume_all_abandoned_branches(self): 329 330 """ 331 Resume branches previously abandoned including returning branches. 332 333 Abandoned branches are not reset because they may not be handled by 334 exception handlers after all. 335 """ 336 337 current_branches = self.attribute_branches[-1] 338 abandoned_branches = self.abandoned_branches[-1] 339 returning_branches = self.returning_branches[-1] 340 merged_branches = merge_dicts(abandoned_branches + returning_branches + [current_branches]) 341 self.replace_branches(merged_branches) 342 343 # Return the previously-active branches for later restoration. 344 345 return current_branches 346 347 def resume_broken_branches(self): 348 349 "Resume branches previously suspended for breaking out of a loop." 350 351 suspended_branches = self.suspended_broken_branches.pop() 352 current_branches = self.attribute_branches[-1] 353 354 # Merge suspended branches with the current branch. 355 356 merged_branches = merge_dicts(suspended_branches + [current_branches]) 357 self.replace_branches(merged_branches) 358 359 def resume_continuing_branches(self): 360 361 "Resume branches previously suspended for loop continuation." 362 363 suspended_branches = self.suspended_continuing_branches.pop() 364 current_branches = self.attribute_branches[-1] 365 366 # Merge suspended branches with the current branch. 367 368 merged_branches = merge_dicts(suspended_branches + [current_branches]) 369 self.replace_branches(merged_branches) 370 371 def replace_branches(self, merged_branches): 372 373 """ 374 Replace the 'merged_branches' with a new branch applying to all active 375 names, connected to the supplying branches. 376 """ 377 378 branch, new_branches = self._new_branch(merged_branches) 379 self.attribute_branches[-1] = new_branches 380 381 def restore_active_branches(self, branches): 382 383 "Restore the active 'branches'." 384 385 self.attribute_branches[-1] = branches 386 387 def merge_branches(self): 388 389 "Merge branches." 390 391 # Combine the attribute branches. This ensures that a list of branches 392 # affected by attribute usage is maintained for the current branch. 393 394 all_shelved_branches = self.attribute_branch_shelves.pop() 395 merged_branches = merge_dicts(all_shelved_branches, missing=make_missing) 396 self.replace_branches(merged_branches) 397 398 # Abandoned branches are retained for exception handling purposes. 399 400 all_abandoned_branches = self.abandoned_branches.pop() 401 new_abandoned_branches = merge_dicts(all_abandoned_branches) 402 self.abandoned_branches[-1].append(new_abandoned_branches) 403 404 # Returning branches are retained for finally clauses. 405 406 all_returning_branches = self.returning_branches.pop() 407 new_returning_branches = merge_dicts(all_returning_branches) 408 self.returning_branches[-1].append(new_returning_branches) 409 410 # Internal structure assembly methods. 411 412 def _connect_branches(self, attribute_branches, contributor, loop_node=False): 413 414 """ 415 Given the 'attribute_branches' mapping, connect the branches referenced 416 in the mapping to the given 'contributor' branch. If 'loop_node' is 417 set to a true value, connect only the branches so that the 'contributor' 418 references the nodes supplying it with name information. 419 """ 420 421 all_branches = self._connect_suppliers(attribute_branches, contributor) 422 if not loop_node: 423 self._connect_contributor(contributor, all_branches) 424 425 def _connect_suppliers(self, attribute_branches, contributor): 426 427 "Connect the 'attribute_branches' to the given 'contributor'." 428 429 # Gather branches involved with all known names into a single set. 430 431 all_branches = set() 432 433 for name, branches in attribute_branches.items(): 434 all_branches.update(branches) 435 436 # Also note receiving branches on the contributor. 437 438 for branch in branches: 439 init_item(contributor.suppliers, name, set) 440 contributor.suppliers[name].add(branch) 441 442 return all_branches 443 444 def _connect_contributor(self, contributor, branches): 445 446 "Connect the given 'contributor' branch to the given 'branches'." 447 448 for branch in branches: 449 branch.contributors.add(contributor) 450 451 # Attribute usage methods. 452 453 def tracking_name(self, name): 454 455 """ 456 Return whether 'name' is being tracked, returning all branches doing so 457 if it is. 458 """ 459 460 return self.assignments.has_key(name) and self.have_name(name) 461 462 def have_name(self, name): 463 464 "Return whether 'name' is known." 465 466 return self.attribute_branches[-1].get(name) 467 468 def assign_names(self, names, values=None): 469 470 """ 471 Define the start of usage tracking for the given 'names', each being 472 assigned with the corresponding 'values' if indicated. 473 """ 474 475 branches = self.attribute_branches[-1] 476 branch = Branch(names, True, values) 477 478 for name in names: 479 branches[name] = [branch] 480 init_item(self.assignments, name, list) 481 self.assignments[name].append(branch) 482 483 return branch 484 485 def use_attribute(self, name, attrname): 486 487 """ 488 Indicate the use on the given 'name' of an attribute with the given 489 'attrname'. 490 491 Return all branches that support 'name'. 492 """ 493 494 branches = self.attribute_branches[-1] 495 496 # Add the usage to all current branches. 497 498 if branches.has_key(name): 499 for branch in branches[name]: 500 branch.set_usage(name, attrname) 501 return branches[name] 502 else: 503 return None 504 505 # Query methods. 506 507 def get_assignment_positions_for_branches(self, name, branches, missing=True): 508 509 """ 510 Return the positions of assignments involving the given 'name' affected 511 by the given 'branches'. If 'missing' is set to a false value, branches 512 with missing name details will be excluded instead of contributing the 513 value None to the list of positions. 514 """ 515 516 if not branches: 517 return [None] 518 519 positions = set() 520 assignments = self.assignments[name] 521 522 for assignment in self.get_assignments_for_branches(name, branches): 523 524 # Use None to indicate a branch without assignment information. 525 526 if missing and isinstance(assignment, MissingBranch): 527 positions.add(None) 528 else: 529 pos = assignments.index(assignment) 530 positions.add(pos) 531 532 positions = list(positions) 533 positions.sort() 534 return positions 535 536 def get_assignments_for_branches(self, name, branches, missing=True): 537 538 """ 539 Return the origins of assignments involving the given 'name' affected 540 by the given 'branches'. The origins are a list of branches where names 541 are defined using assignments. If 'missing' is set to a false value, 542 branches with missing name details are excluded. 543 """ 544 545 all_branches = [] 546 assignments = self.assignments[name] 547 548 # Obtain the assignments recorded for each branch. 549 550 for branch in branches: 551 552 # Find the branch representing the definition of some names in the 553 # scope's assignments, making sure that the given name is involved. 554 555 for assignment in branch.get_assignment_sources(name): 556 557 # Capture branches without assignment information as well as 558 # genuine assignment branches. 559 560 if assignment in assignments or missing and isinstance(assignment, MissingBranch): 561 all_branches.append(assignment) 562 563 return all_branches 564 565 def get_all_usage(self): 566 567 """ 568 Convert usage observations from the tracker to a simple mapping of 569 names to sets of attribute names. 570 """ 571 572 d = {} 573 for name, branches in self.assignments.items(): 574 d[name] = self.get_usage_from_branches_for_name(branches, name) 575 return d 576 577 def get_usage_from_branches_for_name(self, branches, name): 578 579 """ 580 Convert usage observations from the 'branches' to a simple list of 581 usage sets for the given 'name'. 582 """ 583 584 l = [] 585 for branch in branches: 586 l.append(branch.get_usage()[name]) 587 return l 588 589 def get_all_values(self): 590 591 "Return a mapping from names to lists of assigned values." 592 593 d = {} 594 for name, branches in self.assignments.items(): 595 d[name] = [branch.values.get(name) for branch in branches] 596 return d 597 598 # Special objects. 599 600 class AbandonedDict(dict): 601 602 "A dictionary representing mappings in an abandoned branch." 603 604 def __repr__(self): 605 return "AbandonedDict()" 606 607 class MissingBranch(Branch): 608 609 "A branch introduced during dictionary merging." 610 611 def __repr__(self): 612 return "MissingBranch(%r, %r)" % (self.usage.keys(), 613 self.assignments and True or False) 614 615 def make_missing(name): 616 617 "Make a special branch indicating missing name information." 618 619 return set([MissingBranch([name], True)]) 620 621 # Dictionary utilities. 622 623 def merge_dicts(dicts, ignored=AbandonedDict, missing=None): 624 625 """ 626 Merge the given 'dicts' mapping keys to sets of values. 627 628 Where 'ignored' is specified, any dictionary of the given type is ignored. 629 Where all dictionaries to be merged are of the given type, an instance of 630 the type is returned as the merged dictionary. 631 632 Where 'missing' is specified, it provides a callable that produces a set of 633 suitable values for a given name. 634 """ 635 636 new_dict = {} 637 all_names = set() 638 639 # Determine all known names. 640 641 for old_dict in dicts: 642 all_names.update(old_dict.keys()) 643 644 # Merge the dictionaries, looking for all known names in each one. 645 646 have_dicts = False 647 648 for old_dict in dicts: 649 650 # Abandoned dictionaries should not contribute information. 651 652 if isinstance(old_dict, ignored): 653 continue 654 else: 655 have_dicts = True 656 657 for name in all_names: 658 659 # Find branches providing each name. 660 661 if old_dict.has_key(name): 662 values = old_dict[name] 663 664 # Branches not providing names may indicate usage before assignment. 665 666 elif missing: 667 values = missing(name) 668 else: 669 continue 670 671 # Initialise mappings in the resulting dictionary. 672 673 if not new_dict.has_key(name): 674 new_dict[name] = set(values) 675 else: 676 new_dict[name].update(values) 677 678 # Where no dictionaries contributed, all branches were abandoned. 679 680 if have_dicts: 681 return new_dict 682 else: 683 return ignored() 684 685 def deepen_dict(d): 686 687 """ 688 Return a version of dictionary 'd' with its values converted to sets 689 containing each original value as a single element in each new value. 690 Original values are assumed to be sequences. Thus... 691 692 {"self" : ("x", "y")} 693 694 ...would become... 695 696 {"self" : set([("x", "y")])} 697 698 ...allowing other such values to be added to the set alongside the original 699 value. 700 """ 701 702 l = [] 703 704 for key, value in d.items(): 705 706 # Sort the attribute name details for stable comparisons. 707 708 value = list(value) 709 value.sort() 710 l.append((key, set([tuple(value)]))) 711 712 return dict(l) 713 714 def combine_sets(s1, s2): 715 716 "Combine elements from sets 's1' and 's2'." 717 718 if not s1: 719 return s2 720 elif not s2: 721 return s1 722 723 s = set() 724 725 for i1 in s1: 726 for i2 in s2: 727 728 # Sort the attribute name details for stable comparisons. 729 730 l = list(set(i1 + i2)) 731 l.sort() 732 s.add(tuple(l)) 733 734 return s 735 736 def combine_dicts(d1, d2, combine=combine_sets): 737 738 """ 739 Combine dictionaries 'd1' and 'd2' such that the values for common keys 740 are themselves combined in the result. 741 """ 742 743 d = {} 744 745 for key in d1.keys(): 746 if d2.has_key(key): 747 d[key] = combine(d1[key], d2[key]) 748 else: 749 d[key] = d1[key] 750 751 return d 752 753 # vim: tabstop=4 expandtab shiftwidth=4