Lichen

branching.py

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