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