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