Lichen

Annotated branching.py

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