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