1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/branching.py Tue Aug 30 16:51:10 2016 +0200
1.3 @@ -0,0 +1,818 @@
1.4 +#!/usr/bin/env python
1.5 +
1.6 +"""
1.7 +Track attribute usage for names.
1.8 +
1.9 +Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013,
1.10 + 2014, 2015, 2016 Paul Boddie <paul@boddie.org.uk>
1.11 +
1.12 +This program is free software; you can redistribute it and/or modify it under
1.13 +the terms of the GNU General Public License as published by the Free Software
1.14 +Foundation; either version 3 of the License, or (at your option) any later
1.15 +version.
1.16 +
1.17 +This program is distributed in the hope that it will be useful, but WITHOUT
1.18 +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.19 +FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
1.20 +details.
1.21 +
1.22 +You should have received a copy of the GNU General Public License along with
1.23 +this program. If not, see <http://www.gnu.org/licenses/>.
1.24 +"""
1.25 +
1.26 +from common import dict_for_keys, init_item
1.27 +
1.28 +class Branch:
1.29 +
1.30 + """
1.31 + A control-flow branch capturing local attribute usage for names.
1.32 + Branches typically begin with assignments or function parameters and are
1.33 + connected to others introduced by conditional and loop nodes.
1.34 +
1.35 + Branches hosting accesses, and thus providing usage information, are
1.36 + contributors to preceding branches.
1.37 +
1.38 + Branches also provide a route from accesses back to assignments which are
1.39 + the ultimate suppliers of the names involved.
1.40 + """
1.41 +
1.42 + def __init__(self, names, assigning=False, values=None):
1.43 +
1.44 + """
1.45 + Capture attribute usage for the given 'names', with the accompanying
1.46 + 'values' indicating assigned values for each name, if indicated.
1.47 + """
1.48 +
1.49 + self.contributors = set()
1.50 + self.suppliers = {}
1.51 + self.assignments = set(assigning and names or [])
1.52 + self.usage = {}
1.53 + self.values = {}
1.54 +
1.55 + # Initialise usage for each name.
1.56 +
1.57 + for name in names:
1.58 + self.usage[name] = set()
1.59 +
1.60 + # Initialise assigned values if any were provided.
1.61 +
1.62 + if values:
1.63 + for name, value in zip(names, values):
1.64 + if value:
1.65 + self.values[name] = value
1.66 +
1.67 + # Computed results.
1.68 +
1.69 + self.combined_usage = None
1.70 +
1.71 + def get_assignment_sources(self, name):
1.72 +
1.73 + """
1.74 + Return the sources of 'name' from this branch's assignment information,
1.75 + returning a list containing only this branch itself if it is the source.
1.76 + """
1.77 +
1.78 + if name in self.assignments:
1.79 + return [self]
1.80 + else:
1.81 + return [b for b in self.get_all_suppliers(name) if name in b.assignments]
1.82 +
1.83 + def set_usage(self, name, attrname):
1.84 +
1.85 + """
1.86 + Record usage on the given 'name' of the attribute 'attrname'.
1.87 + """
1.88 +
1.89 + if self.usage.has_key(name):
1.90 + self.usage[name].add(attrname)
1.91 +
1.92 + def get_usage(self):
1.93 +
1.94 + """
1.95 + Obtain usage from this node, combined with usage observed by its
1.96 + contributors. Unlike the local usage which involves only a single set of
1.97 + attribute names for a given variable name, the returned usage is a set
1.98 + of attribute name combinations for a given variable name. For example:
1.99 +
1.100 + {'a': set([('p', 'q', 'r'), ('p', 'r')])}
1.101 + """
1.102 +
1.103 + if self.combined_usage is None:
1.104 +
1.105 + # Accumulate usage observations from contributors.
1.106 +
1.107 + all_usage = []
1.108 +
1.109 + for contributor in self.contributors:
1.110 +
1.111 + # Record any usage that can be returned.
1.112 +
1.113 + all_usage.append(contributor.get_usage())
1.114 +
1.115 + # Merge usage from the contributors.
1.116 +
1.117 + merged_usage = merge_dicts(all_usage)
1.118 +
1.119 + # Make the local usage compatible with the combined usage.
1.120 +
1.121 + usage = deepen_dict(self.usage)
1.122 +
1.123 + self.combined_usage = combine_dicts(usage, merged_usage, combine_sets)
1.124 +
1.125 + return self.combined_usage
1.126 +
1.127 + def get_all_suppliers(self, name, all_suppliers=None):
1.128 +
1.129 + "Return all branches supplying this branch with definitions of 'name'."
1.130 +
1.131 + all_suppliers = all_suppliers or set()
1.132 + all_suppliers.add(self)
1.133 +
1.134 + if self.suppliers.has_key(name):
1.135 + for supplier in self.suppliers[name]:
1.136 + if supplier not in all_suppliers:
1.137 + supplier.get_all_suppliers(name, all_suppliers)
1.138 +
1.139 + return all_suppliers
1.140 +
1.141 + def __repr__(self):
1.142 + return "Branch(%r, %r)" % (self.usage.keys(),
1.143 + self.assignments and True or False)
1.144 +
1.145 +class BranchTracker:
1.146 +
1.147 + """
1.148 + A tracker of attribute usage for names in a namespace. This tracker directs
1.149 + usage observations to branches which are the ultimate repositories of
1.150 + attribute usage information.
1.151 +
1.152 + As a program unit is inspected, the branches associated with names may
1.153 + change. Assignments reset the branches; control-flow operations cause
1.154 + branches to be accumulated from different code paths.
1.155 + """
1.156 +
1.157 + def __init__(self):
1.158 +
1.159 + # Track assignments.
1.160 +
1.161 + self.assignments = {}
1.162 +
1.163 + # Details of attributes at each active branch level.
1.164 +
1.165 + self.attribute_branches = [{}] # stack of branches for names
1.166 + self.attribute_branch_shelves = [] # stack of shelved branches
1.167 +
1.168 + # Suspended branch details plus loop details.
1.169 +
1.170 + self.suspended_broken_branches = [] # stack of lists of dicts
1.171 + self.suspended_continuing_branches = [] # stack of lists of dicts
1.172 +
1.173 + # Abandoned usage, useful for reviving usage for exception handlers.
1.174 +
1.175 + self.abandoned_branches = [[]] # stack of lists of branches
1.176 +
1.177 + # Returning branches are like abandoned branches but are only revived in
1.178 + # finally clauses.
1.179 +
1.180 + self.returning_branches = [[]]
1.181 +
1.182 + # Branches active when starting loops.
1.183 +
1.184 + self.loop_branches = []
1.185 +
1.186 + # Inherited usage.
1.187 +
1.188 + self.inherited = None
1.189 +
1.190 + # Structure assembly methods.
1.191 +
1.192 + def new_branchpoint(self, loop_node=False):
1.193 +
1.194 + """
1.195 + Indicate that branches diverge, initialising resources dependent on
1.196 + any given 'loop_node'.
1.197 + """
1.198 +
1.199 + self.attribute_branch_shelves.append([])
1.200 +
1.201 + if loop_node:
1.202 + self.suspended_broken_branches.append([])
1.203 + self.suspended_continuing_branches.append([])
1.204 +
1.205 + # Retain a record of abandoned branches.
1.206 +
1.207 + self.abandoned_branches.append([])
1.208 + self.returning_branches.append([])
1.209 +
1.210 + def new_branch(self, loop_node=False):
1.211 +
1.212 + "Create a new branch."
1.213 +
1.214 + attribute_branches = self.attribute_branches[-1]
1.215 +
1.216 + branch, new_branches = self._new_branch(attribute_branches)
1.217 +
1.218 + if branch and loop_node:
1.219 + self.loop_branches.append(branch)
1.220 +
1.221 + # Start using the branch for known names.
1.222 +
1.223 + self.attribute_branches.append(new_branches)
1.224 +
1.225 + def _new_branch(self, attribute_branches):
1.226 +
1.227 + """
1.228 + Define a new branch that will record attribute usage on known names from
1.229 + 'attribute_branches'.
1.230 + """
1.231 +
1.232 + # Detect abandoned branches.
1.233 +
1.234 + if isinstance(attribute_branches, AbandonedDict):
1.235 + return None, AbandonedDict()
1.236 +
1.237 + # Otherwise, define a new branch.
1.238 +
1.239 + names = attribute_branches.keys()
1.240 +
1.241 + new_branches = {}
1.242 + branch = Branch(names)
1.243 +
1.244 + for name in names:
1.245 + new_branches[name] = [branch]
1.246 +
1.247 + # Add this new branch as a contributor to the previously active
1.248 + # branches.
1.249 +
1.250 + self._connect_branches(attribute_branches, branch)
1.251 +
1.252 + return branch, new_branches
1.253 +
1.254 + def shelve_branch(self, loop_node=False):
1.255 +
1.256 + "Retain the current branch for later merging."
1.257 +
1.258 + branches = self.attribute_branches.pop()
1.259 + self.attribute_branch_shelves[-1].append(branches)
1.260 +
1.261 + # Connect any loop branch to the active branches as contributors.
1.262 +
1.263 + if loop_node:
1.264 + branch = self.loop_branches.pop()
1.265 + self._connect_branches(branches, branch, loop_node)
1.266 +
1.267 + def abandon_branch(self):
1.268 +
1.269 + "Abandon the current branch, retaining it for later."
1.270 +
1.271 + attribute_branches = self.attribute_branches[-1]
1.272 + self._abandon_branch()
1.273 + self.abandoned_branches[-1].append(attribute_branches)
1.274 +
1.275 + def abandon_returning_branch(self):
1.276 +
1.277 + "Abandon the current branch, retaining it for later."
1.278 +
1.279 + attribute_branches = self.attribute_branches[-1]
1.280 + self._abandon_branch()
1.281 + self.returning_branches[-1].append(attribute_branches)
1.282 +
1.283 + def suspend_broken_branch(self):
1.284 +
1.285 + "Suspend a branch for breaking out of a loop."
1.286 +
1.287 + attribute_branches = self.attribute_branches[-1]
1.288 +
1.289 + branches = self.suspended_broken_branches[-1]
1.290 + branches.append(attribute_branches)
1.291 + self._abandon_branch()
1.292 +
1.293 + def suspend_continuing_branch(self):
1.294 +
1.295 + "Suspend a branch for loop continuation."
1.296 +
1.297 + attribute_branches = self.attribute_branches[-1]
1.298 +
1.299 + branches = self.suspended_continuing_branches[-1]
1.300 + branches.append(attribute_branches)
1.301 + self._abandon_branch()
1.302 +
1.303 + def _abandon_branch(self):
1.304 +
1.305 + "Abandon the current branch."
1.306 +
1.307 + self.attribute_branches[-1] = AbandonedDict()
1.308 +
1.309 + def resume_abandoned_branches(self):
1.310 +
1.311 + """
1.312 + Resume branches previously abandoned.
1.313 +
1.314 + Abandoned branches are not reset because they may not be handled by
1.315 + exception handlers after all.
1.316 + """
1.317 +
1.318 + current_branches = self.attribute_branches[-1]
1.319 + abandoned_branches = self.abandoned_branches[-1]
1.320 + merged_branches = merge_dicts(abandoned_branches + [current_branches])
1.321 +
1.322 + # Replace the combined branches with a new branch applying to all active
1.323 + # names, connected to the supplying branches.
1.324 +
1.325 + branch, new_branches = self._new_branch(merged_branches)
1.326 + self.attribute_branches.append(new_branches)
1.327 +
1.328 + # Although returning branches should not be considered as accumulating
1.329 + # usage, they do provide sources of assignments.
1.330 +
1.331 + if branch:
1.332 + for returning_branches in self.returning_branches[-1]:
1.333 + self._connect_suppliers(returning_branches, branch)
1.334 +
1.335 + def resume_all_abandoned_branches(self):
1.336 +
1.337 + """
1.338 + Resume branches previously abandoned including returning branches.
1.339 +
1.340 + Abandoned branches are not reset because they may not be handled by
1.341 + exception handlers after all.
1.342 + """
1.343 +
1.344 + current_branches = self.attribute_branches[-1]
1.345 + abandoned_branches = self.abandoned_branches[-1]
1.346 + returning_branches = self.returning_branches[-1]
1.347 + merged_branches = merge_dicts(abandoned_branches + returning_branches + [current_branches])
1.348 + self.replace_branches(merged_branches)
1.349 +
1.350 + # Return the previously-active branches for later restoration.
1.351 +
1.352 + return current_branches
1.353 +
1.354 + def resume_broken_branches(self):
1.355 +
1.356 + "Resume branches previously suspended for breaking out of a loop."
1.357 +
1.358 + suspended_branches = self.suspended_broken_branches.pop()
1.359 + current_branches = self.attribute_branches[-1]
1.360 +
1.361 + # Merge suspended branches with the current branch.
1.362 +
1.363 + merged_branches = merge_dicts(suspended_branches + [current_branches])
1.364 + self.replace_branches(merged_branches)
1.365 +
1.366 + def resume_continuing_branches(self):
1.367 +
1.368 + "Resume branches previously suspended for loop continuation."
1.369 +
1.370 + suspended_branches = self.suspended_continuing_branches.pop()
1.371 + current_branches = self.attribute_branches[-1]
1.372 +
1.373 + # Merge suspended branches with the current branch.
1.374 +
1.375 + merged_branches = merge_dicts(suspended_branches + [current_branches])
1.376 + self.replace_branches(merged_branches)
1.377 +
1.378 + def replace_branches(self, merged_branches):
1.379 +
1.380 + """
1.381 + Replace the 'merged_branches' with a new branch applying to all active
1.382 + names, connected to the supplying branches.
1.383 + """
1.384 +
1.385 + branch, new_branches = self._new_branch(merged_branches)
1.386 + self.attribute_branches[-1] = new_branches
1.387 +
1.388 + def restore_active_branches(self, branches):
1.389 +
1.390 + "Restore the active 'branches'."
1.391 +
1.392 + self.attribute_branches[-1] = branches
1.393 +
1.394 + def merge_branches(self):
1.395 +
1.396 + "Merge branches."
1.397 +
1.398 + # Combine the attribute branches. This ensures that a list of branches
1.399 + # affected by attribute usage is maintained for the current branch.
1.400 +
1.401 + all_shelved_branches = self.attribute_branch_shelves.pop()
1.402 + merged_branches = merge_dicts(all_shelved_branches, missing=make_missing)
1.403 + self.replace_branches(merged_branches)
1.404 +
1.405 + # Abandoned branches are retained for exception handling purposes.
1.406 +
1.407 + all_abandoned_branches = self.abandoned_branches.pop()
1.408 + new_abandoned_branches = merge_dicts(all_abandoned_branches)
1.409 + self.abandoned_branches[-1].append(new_abandoned_branches)
1.410 +
1.411 + # Returning branches are retained for finally clauses.
1.412 +
1.413 + all_returning_branches = self.returning_branches.pop()
1.414 + new_returning_branches = merge_dicts(all_returning_branches)
1.415 + self.returning_branches[-1].append(new_returning_branches)
1.416 +
1.417 + # Internal structure assembly methods.
1.418 +
1.419 + def _connect_branches(self, attribute_branches, contributor, loop_node=False):
1.420 +
1.421 + """
1.422 + Given the 'attribute_branches' mapping, connect the branches referenced
1.423 + in the mapping to the given 'contributor' branch. If 'loop_node' is
1.424 + set to a true value, connect only the branches so that the 'contributor'
1.425 + references the nodes supplying it with name information.
1.426 + """
1.427 +
1.428 + all_branches = self._connect_suppliers(attribute_branches, contributor)
1.429 + if not loop_node:
1.430 + self._connect_contributor(contributor, all_branches)
1.431 +
1.432 + def _connect_suppliers(self, attribute_branches, contributor):
1.433 +
1.434 + "Connect the 'attribute_branches' to the given 'contributor'."
1.435 +
1.436 + # Gather branches involved with all known names into a single set.
1.437 +
1.438 + all_branches = set()
1.439 +
1.440 + for name, branches in attribute_branches.items():
1.441 + all_branches.update(branches)
1.442 +
1.443 + # Also note receiving branches on the contributor.
1.444 +
1.445 + for branch in branches:
1.446 + init_item(contributor.suppliers, name, set)
1.447 + contributor.suppliers[name].add(branch)
1.448 +
1.449 + return all_branches
1.450 +
1.451 + def _connect_contributor(self, contributor, branches):
1.452 +
1.453 + "Connect the given 'contributor' branch to the given 'branches'."
1.454 +
1.455 + for branch in branches:
1.456 + branch.contributors.add(contributor)
1.457 +
1.458 + # Namespace methods.
1.459 +
1.460 + def inherit_branches(self, tracker, names):
1.461 +
1.462 + """
1.463 + Propagate branches from the given 'tracker' excluding those associated
1.464 + with 'names'.
1.465 + """
1.466 +
1.467 + # For each inherited name, create a branch connected to the inherited
1.468 + # branches.
1.469 +
1.470 + self.inherited = {}
1.471 +
1.472 + for name, branches in tracker.attribute_branches[-1].items():
1.473 +
1.474 + # Do not inherit any listed names (typically parameters) or any
1.475 + # special names.
1.476 +
1.477 + if name in names or name.startswith("$"):
1.478 + continue
1.479 +
1.480 + # Make a tentative assignment for the name.
1.481 +
1.482 + contributor = Branch([name], True)
1.483 + init_item(self.assignments, name, list)
1.484 + self.assignments[name].append(contributor)
1.485 +
1.486 + # Connect the inherited branch to the new one.
1.487 +
1.488 + for branch in branches:
1.489 + init_item(contributor.suppliers, name, set)
1.490 + contributor.suppliers[name].add(branch)
1.491 + branch.contributors.add(contributor)
1.492 +
1.493 + # Record the inherited branch.
1.494 +
1.495 + self.inherited[name] = [contributor]
1.496 +
1.497 + self.attribute_branches[-1].update(self.inherited)
1.498 +
1.499 + def disconnect_name(self, name):
1.500 +
1.501 + "Disconnect inherited branches for 'name'."
1.502 +
1.503 + if not self.inherited or not self.inherited.has_key(name):
1.504 + return
1.505 +
1.506 + # Remove the new branch from the inherited branches for the name.
1.507 +
1.508 + for contributor in self.inherited[name]:
1.509 + for supplier in contributor.suppliers[name]:
1.510 + supplier.contributors.remove(contributor)
1.511 + del contributor.suppliers[name]
1.512 +
1.513 + del self.inherited[name]
1.514 +
1.515 + # Attribute usage methods.
1.516 +
1.517 + def tracking_name(self, name):
1.518 +
1.519 + """
1.520 + Return whether 'name' is being tracked, returning all branches doing so
1.521 + if it is.
1.522 + """
1.523 +
1.524 + return self.assignments.has_key(name) and \
1.525 + (not self.inherited or not self.inherited.has_key(name)) and \
1.526 + self.have_name(name)
1.527 +
1.528 + def have_name(self, name):
1.529 +
1.530 + "Return whether 'name' is known, perhaps having been inherited."
1.531 +
1.532 + return self.attribute_branches[-1].get(name)
1.533 +
1.534 + def assign_names(self, names, values=None):
1.535 +
1.536 + """
1.537 + Define the start of usage tracking for the given 'names', each being
1.538 + assigned with the corresponding 'values' if indicated.
1.539 + """
1.540 +
1.541 + branches = self.attribute_branches[-1]
1.542 + branch = Branch(names, True, values)
1.543 +
1.544 + for name in names:
1.545 + self.disconnect_name(name)
1.546 +
1.547 + branches[name] = [branch]
1.548 + init_item(self.assignments, name, list)
1.549 + self.assignments[name].append(branch)
1.550 +
1.551 + return branch
1.552 +
1.553 + def use_attribute(self, name, attrname):
1.554 +
1.555 + """
1.556 + Indicate the use on the given 'name' of an attribute with the given
1.557 + 'attrname'.
1.558 +
1.559 + Return all branches that support 'name'.
1.560 + """
1.561 +
1.562 + branches = self.attribute_branches[-1]
1.563 +
1.564 + # Add the usage to all current branches.
1.565 +
1.566 + if branches.has_key(name):
1.567 + for branch in branches[name]:
1.568 + branch.set_usage(name, attrname)
1.569 + return branches[name]
1.570 + else:
1.571 + return None
1.572 +
1.573 + # Query methods.
1.574 +
1.575 + def get_assignment_positions_for_branches(self, name, branches, missing=True):
1.576 +
1.577 + """
1.578 + Return the positions of assignments involving the given 'name' affected
1.579 + by the given 'branches'. If 'missing' is set to a false value, branches
1.580 + with missing name details will be excluded instead of contributing the
1.581 + value None to the list of positions.
1.582 + """
1.583 +
1.584 + if not branches:
1.585 + return [None]
1.586 +
1.587 + positions = set()
1.588 + assignments = self.assignments[name]
1.589 +
1.590 + for assignment in self.get_assignments_for_branches(name, branches):
1.591 +
1.592 + # Use None to indicate a branch without assignment information.
1.593 +
1.594 + if missing and isinstance(assignment, MissingBranch):
1.595 + positions.add(None)
1.596 + else:
1.597 + pos = assignments.index(assignment)
1.598 + positions.add(pos)
1.599 +
1.600 + positions = list(positions)
1.601 + positions.sort()
1.602 + return positions
1.603 +
1.604 + def get_assignments_for_branches(self, name, branches, missing=True):
1.605 +
1.606 + """
1.607 + Return the origins of assignments involving the given 'name' affected
1.608 + by the given 'branches'. The origins are a list of branches where names
1.609 + are defined using assignments. If 'missing' is set to a false value,
1.610 + branches with missing name details are excluded.
1.611 + """
1.612 +
1.613 + all_branches = []
1.614 + assignments = self.assignments[name]
1.615 +
1.616 + # Obtain the assignments recorded for each branch.
1.617 +
1.618 + for branch in branches:
1.619 +
1.620 + # Find the branch representing the definition of some names in the
1.621 + # scope's assignments, making sure that the given name is involved.
1.622 +
1.623 + for assignment in branch.get_assignment_sources(name):
1.624 +
1.625 + # Capture branches without assignment information as well as
1.626 + # genuine assignment branches.
1.627 +
1.628 + if assignment in assignments or missing and isinstance(assignment, MissingBranch):
1.629 + all_branches.append(assignment)
1.630 +
1.631 + return all_branches
1.632 +
1.633 + def get_all_usage(self):
1.634 +
1.635 + """
1.636 + Convert usage observations from the tracker to a simple mapping of
1.637 + names to sets of attribute names.
1.638 + """
1.639 +
1.640 + d = {}
1.641 + for name, branches in self.assignments.items():
1.642 + d[name] = self.get_usage_from_branches_for_name(branches, name)
1.643 + return d
1.644 +
1.645 + def get_usage_from_branches_for_name(self, branches, name):
1.646 +
1.647 + """
1.648 + Convert usage observations from the 'branches' to a simple list of
1.649 + usage sets for the given 'name'.
1.650 + """
1.651 +
1.652 + l = []
1.653 + for branch in branches:
1.654 + l.append(branch.get_usage()[name])
1.655 + return l
1.656 +
1.657 + def get_all_values(self):
1.658 +
1.659 + "Return a mapping from names to lists of assigned values."
1.660 +
1.661 + d = {}
1.662 + for name, branches in self.assignments.items():
1.663 + d[name] = [branch.values.get(name) for branch in branches]
1.664 + return d
1.665 +
1.666 +# Special objects.
1.667 +
1.668 +class AbandonedDict(dict):
1.669 +
1.670 + "A dictionary representing mappings in an abandoned branch."
1.671 +
1.672 + def __repr__(self):
1.673 + return "AbandonedDict()"
1.674 +
1.675 +class MissingBranch(Branch):
1.676 +
1.677 + "A branch introduced during dictionary merging."
1.678 +
1.679 + def __repr__(self):
1.680 + return "MissingBranch(%r, %r)" % (self.usage.keys(),
1.681 + self.assignments and True or False)
1.682 +
1.683 +def make_missing(name):
1.684 +
1.685 + "Make a special branch indicating missing name information."
1.686 +
1.687 + return set([MissingBranch([name], True)])
1.688 +
1.689 +# Dictionary utilities.
1.690 +
1.691 +def merge_dicts(dicts, ignored=AbandonedDict, missing=None):
1.692 +
1.693 + """
1.694 + Merge the given 'dicts' mapping keys to sets of values.
1.695 +
1.696 + Where 'ignored' is specified, any dictionary of the given type is ignored.
1.697 + Where all dictionaries to be merged are of the given type, an instance of
1.698 + the type is returned as the merged dictionary.
1.699 +
1.700 + Where 'missing' is specified, it provides a callable that produces a set of
1.701 + suitable values for a given name.
1.702 + """
1.703 +
1.704 + new_dict = {}
1.705 + all_names = set()
1.706 +
1.707 + # Determine all known names.
1.708 +
1.709 + for old_dict in dicts:
1.710 + all_names.update(old_dict.keys())
1.711 +
1.712 + # Merge the dictionaries, looking for all known names in each one.
1.713 +
1.714 + have_dicts = False
1.715 +
1.716 + for old_dict in dicts:
1.717 +
1.718 + # Abandoned dictionaries should not contribute information.
1.719 +
1.720 + if isinstance(old_dict, ignored):
1.721 + continue
1.722 + else:
1.723 + have_dicts = True
1.724 +
1.725 + for name in all_names:
1.726 +
1.727 + # Find branches providing each name.
1.728 +
1.729 + if old_dict.has_key(name):
1.730 + values = old_dict[name]
1.731 +
1.732 + # Branches not providing names may indicate usage before assignment.
1.733 +
1.734 + elif missing:
1.735 + values = missing(name)
1.736 + else:
1.737 + continue
1.738 +
1.739 + # Initialise mappings in the resulting dictionary.
1.740 +
1.741 + if not new_dict.has_key(name):
1.742 + new_dict[name] = set(values)
1.743 + else:
1.744 + new_dict[name].update(values)
1.745 +
1.746 + # Where no dictionaries contributed, all branches were abandoned.
1.747 +
1.748 + if have_dicts:
1.749 + return new_dict
1.750 + else:
1.751 + return ignored()
1.752 +
1.753 +def deepen_dict(d):
1.754 +
1.755 + """
1.756 + Return a version of dictionary 'd' with its values converted to sets
1.757 + containing each original value as a single element in each new value.
1.758 + Original values are assumed to be sequences. Thus...
1.759 +
1.760 + {"self" : ("x", "y")}
1.761 +
1.762 + ...would become...
1.763 +
1.764 + {"self" : set([("x", "y")])}
1.765 +
1.766 + ...allowing other such values to be added to the set alongside the original
1.767 + value.
1.768 + """
1.769 +
1.770 + l = []
1.771 +
1.772 + for key, value in d.items():
1.773 +
1.774 + # Sort the attribute name details for stable comparisons.
1.775 +
1.776 + value = list(value)
1.777 + value.sort()
1.778 + l.append((key, set([tuple(value)])))
1.779 +
1.780 + return dict(l)
1.781 +
1.782 +def combine_sets(s1, s2):
1.783 +
1.784 + "Combine elements from sets 's1' and 's2'."
1.785 +
1.786 + if not s1:
1.787 + return s2
1.788 + elif not s2:
1.789 + return s1
1.790 +
1.791 + s = set()
1.792 +
1.793 + for i1 in s1:
1.794 + for i2 in s2:
1.795 +
1.796 + # Sort the attribute name details for stable comparisons.
1.797 +
1.798 + l = list(set(i1 + i2))
1.799 + l.sort()
1.800 + s.add(tuple(l))
1.801 +
1.802 + return s
1.803 +
1.804 +def combine_dicts(d1, d2, combine=combine_sets):
1.805 +
1.806 + """
1.807 + Combine dictionaries 'd1' and 'd2' such that the values for common keys
1.808 + are themselves combined in the result.
1.809 + """
1.810 +
1.811 + d = {}
1.812 +
1.813 + for key in d1.keys():
1.814 + if d2.has_key(key):
1.815 + d[key] = combine(d1[key], d2[key])
1.816 + else:
1.817 + d[key] = d1[key]
1.818 +
1.819 + return d
1.820 +
1.821 +# vim: tabstop=4 expandtab shiftwidth=4