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