Lichen

Annotated branching.py

934:2989aab1b4f7
6 months ago Paul Boddie Renamed the utf8string class to unicode, eliminating the unicode function. This means that the simple case of merely returning an object if it is already a Unicode object no longer occurs when using the unicode callable, but such behaviour might be better supported with more general customised instantiation functionality.
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