Lichen

Annotated optimiser.py

314:86368c6ae78b
2016-12-05 Paul Boddie Make sure that imported names referring to non-static objects are initialised.
paul@92 1
#!/usr/bin/env python
paul@92 2
paul@92 3
"""
paul@95 4
Optimise object layouts and generate access instruction plans.
paul@92 5
paul@92 6
Copyright (C) 2014, 2015, 2016 Paul Boddie <paul@boddie.org.uk>
paul@92 7
paul@92 8
This program is free software; you can redistribute it and/or modify it under
paul@92 9
the terms of the GNU General Public License as published by the Free Software
paul@92 10
Foundation; either version 3 of the License, or (at your option) any later
paul@92 11
version.
paul@92 12
paul@92 13
This program is distributed in the hope that it will be useful, but WITHOUT
paul@92 14
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
paul@92 15
FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
paul@92 16
details.
paul@92 17
paul@92 18
You should have received a copy of the GNU General Public License along with
paul@92 19
this program.  If not, see <http://www.gnu.org/licenses/>.
paul@92 20
"""
paul@92 21
paul@92 22
from common import add_counter_item, get_attrname_from_location, init_item, \
paul@92 23
                   sorted_output
paul@94 24
from encoders import encode_access_location, encode_instruction, get_kinds
paul@92 25
from os.path import exists, join
paul@92 26
from os import makedirs
paul@92 27
from referencing import Reference
paul@92 28
paul@92 29
class Optimiser:
paul@92 30
paul@92 31
    "Optimise objects in a program."
paul@92 32
paul@92 33
    def __init__(self, importer, deducer, output):
paul@92 34
paul@92 35
        """
paul@92 36
        Initialise an instance using the given 'importer' and 'deducer' that
paul@92 37
        will perform the arrangement of attributes for program objects, writing
paul@92 38
        the results to the given 'output' directory.
paul@92 39
        """
paul@92 40
paul@92 41
        self.importer = importer
paul@92 42
        self.deducer = deducer
paul@92 43
        self.output = output
paul@92 44
paul@92 45
        # Locations/offsets of attributes in objects.
paul@92 46
paul@92 47
        self.locations = None
paul@92 48
        self.attr_locations = None
paul@92 49
        self.all_attrnames = None
paul@92 50
paul@92 51
        # Locations of parameters in parameter tables.
paul@92 52
paul@92 53
        self.arg_locations = None
paul@92 54
        self.param_locations = None
paul@92 55
        self.all_paramnames = None
paul@92 56
paul@92 57
        # Specific attribute access information.
paul@92 58
paul@94 59
        self.access_instructions = {}
paul@234 60
        self.accessor_kinds = {}
paul@92 61
paul@92 62
        # Object structure information.
paul@92 63
paul@92 64
        self.structures = {}
paul@92 65
        self.attr_table = {}
paul@92 66
paul@92 67
        # Parameter list information.
paul@92 68
paul@92 69
        self.parameters = {}
paul@92 70
        self.param_table = {}
paul@92 71
paul@92 72
        # Constant literal information.
paul@92 73
paul@92 74
        self.constants = []
paul@92 75
        self.constant_numbers = {}
paul@92 76
paul@92 77
        # Optimiser activities.
paul@92 78
paul@92 79
        self.populate_objects()
paul@92 80
        self.position_attributes()
paul@92 81
        self.populate_parameters()
paul@92 82
        self.position_parameters()
paul@92 83
        self.populate_tables()
paul@92 84
        self.populate_constants()
paul@94 85
        self.initialise_access_instructions()
paul@92 86
paul@92 87
    def to_output(self):
paul@92 88
paul@92 89
        "Write the output files using optimisation information."
paul@92 90
paul@92 91
        if not exists(self.output):
paul@92 92
            makedirs(self.output)
paul@92 93
paul@92 94
        self.write_objects()
paul@92 95
paul@92 96
    def write_objects(self):
paul@92 97
paul@92 98
        """
paul@92 99
        Write object-related output.
paul@92 100
paul@92 101
        The locations are a list of positions indicating the attributes residing
paul@92 102
        at each position in the different structures in a program.
paul@92 103
paul@92 104
        ----
paul@92 105
paul@92 106
        The parameter locations are a list of positions indicating the parameters
paul@92 107
        residing at each position in the different parameter lists in a program.
paul@92 108
paul@92 109
        ----
paul@92 110
paul@92 111
        Each attribute plan provides attribute details in the following format:
paul@92 112
paul@92 113
        location " " name " " test " " test type " " base
paul@92 114
                 " " traversed attributes " " traversed attribute ambiguity
paul@96 115
                 " " traversal access modes
paul@92 116
                 " " attributes to traverse " " attribute ambiguity
paul@92 117
                 " " context " " access method " " static attribute
paul@92 118
paul@92 119
        Locations have the following format:
paul@92 120
paul@92 121
        qualified name of scope "." local name ":" name version
paul@92 122
paul@96 123
        Traversal access modes are either "class" (obtain accessor class to
paul@96 124
        access attribute) or "object" (obtain attribute directly from accessor).
paul@96 125
paul@92 126
        ----
paul@92 127
paul@92 128
        The structures are presented as a table in the following format:
paul@92 129
paul@92 130
        qualified name " " attribute names
paul@92 131
paul@92 132
        The attribute names are separated by ", " characters and indicate the
paul@92 133
        attribute provided at each position in the structure associated with the
paul@92 134
        given type. Where no attribute is provided at a particular location
paul@92 135
        within a structure, "-" is given.
paul@92 136
paul@92 137
        ----
paul@92 138
paul@92 139
        The parameters are presented as a table in the following format:
paul@92 140
paul@92 141
        qualified name " " parameter details
paul@92 142
paul@92 143
        The parameter details are separated by ", " characters and indicate
paul@92 144
        the parameter name and list position for each parameter described at
paul@92 145
        each location in the parameter table associated with the given
paul@92 146
        function. Where no parameter details are provided at a particular
paul@92 147
        location within a parameter table, "-" is given. The name and list
paul@92 148
        position are separated by a colon (":").
paul@92 149
paul@92 150
        ----
paul@92 151
paul@92 152
        The attribute table is presented as a table in the following format:
paul@92 153
paul@92 154
        qualified name " " attribute identifiers
paul@92 155
paul@92 156
        Instead of attribute names, identifiers defined according to the order
paul@92 157
        given in the "attrnames" file are employed to denote the attributes
paul@92 158
        featured in each type's structure. Where no attribute is provided at a
paul@92 159
        particular location within a structure, "-" is given.
paul@92 160
paul@92 161
        ----
paul@92 162
paul@92 163
        The parameter table is presented as a table in the following format:
paul@92 164
paul@92 165
        qualified name " " parameter details
paul@92 166
paul@92 167
        Instead of parameter names, identifiers defined according to the order
paul@92 168
        given in the "paramnames" file are employed to denote the parameters
paul@92 169
        featured in each function's parameter table. Where no parameter is
paul@92 170
        provided at a particular location within a table, "-" is given.
paul@92 171
paul@92 172
        ----
paul@92 173
paul@92 174
        The ordered list of attribute names is given in the "attrnames" file.
paul@92 175
paul@92 176
        ----
paul@92 177
paul@92 178
        The ordered list of parameter names is given in the "paramnames" file.
paul@92 179
paul@92 180
        ----
paul@92 181
paul@92 182
        The ordered list of constant literals is given in the "constants" file.
paul@92 183
        """
paul@92 184
paul@92 185
        f = open(join(self.output, "locations"), "w")
paul@92 186
        try:
paul@92 187
            for attrnames in self.locations:
paul@92 188
                print >>f, sorted_output(attrnames)
paul@92 189
paul@92 190
        finally:
paul@92 191
            f.close()
paul@92 192
paul@92 193
        f = open(join(self.output, "parameter_locations"), "w")
paul@92 194
        try:
paul@92 195
            for argnames in self.arg_locations:
paul@92 196
                print >>f, sorted_output(argnames)
paul@92 197
paul@92 198
        finally:
paul@92 199
            f.close()
paul@92 200
paul@94 201
        f = open(join(self.output, "instruction_plans"), "w")
paul@94 202
        try:
paul@94 203
            access_instructions = self.access_instructions.items()
paul@94 204
            access_instructions.sort()
paul@94 205
paul@94 206
            for location, instructions in access_instructions:
paul@94 207
                print >>f, encode_access_location(location), "..."
paul@94 208
                for instruction in instructions:
paul@94 209
                    print >>f, encode_instruction(instruction)
paul@94 210
                print >>f
paul@92 211
paul@92 212
        finally:
paul@92 213
            f.close()
paul@92 214
paul@92 215
        f = open(join(self.output, "structures"), "w")
paul@92 216
        try:
paul@92 217
            structures = self.structures.items()
paul@92 218
            structures.sort()
paul@92 219
paul@92 220
            for name, attrnames in structures:
paul@92 221
                print >>f, name, ", ".join([s or "-" for s in attrnames])
paul@92 222
paul@92 223
        finally:
paul@92 224
            f.close()
paul@92 225
paul@92 226
        f = open(join(self.output, "parameters"), "w")
paul@92 227
        try:
paul@92 228
            parameters = self.parameters.items()
paul@92 229
            parameters.sort()
paul@92 230
paul@92 231
            for name, argnames in parameters:
paul@92 232
                print >>f, name, ", ".join([s and ("%s:%d" % s) or "-" for s in argnames])
paul@92 233
paul@92 234
        finally:
paul@92 235
            f.close()
paul@92 236
paul@92 237
        f = open(join(self.output, "attrtable"), "w")
paul@92 238
        try:
paul@92 239
            attr_table = self.attr_table.items()
paul@92 240
            attr_table.sort()
paul@92 241
paul@92 242
            for name, attrcodes in attr_table:
paul@92 243
                print >>f, name, ", ".join([i is not None and str(i) or "-" for i in attrcodes])
paul@92 244
paul@92 245
        finally:
paul@92 246
            f.close()
paul@92 247
paul@92 248
        f = open(join(self.output, "paramtable"), "w")
paul@92 249
        try:
paul@92 250
            param_table = self.param_table.items()
paul@92 251
            param_table.sort()
paul@92 252
paul@92 253
            for name, paramcodes in param_table:
paul@92 254
                print >>f, name, ", ".join([s and ("%d:%d" % s) or "-" for s in paramcodes])
paul@92 255
paul@92 256
        finally:
paul@92 257
            f.close()
paul@92 258
paul@92 259
        f = open(join(self.output, "attrnames"), "w")
paul@92 260
        try:
paul@92 261
            for name in self.all_attrnames:
paul@92 262
                print >>f, name
paul@92 263
paul@92 264
        finally:
paul@92 265
            f.close()
paul@92 266
paul@92 267
        f = open(join(self.output, "paramnames"), "w")
paul@92 268
        try:
paul@92 269
            for name in self.all_paramnames:
paul@92 270
                print >>f, name
paul@92 271
paul@92 272
        finally:
paul@92 273
            f.close()
paul@92 274
paul@92 275
        f = open(join(self.output, "constants"), "w")
paul@92 276
        try:
paul@92 277
            constants = [(n, value) for (value, n) in self.constants.items()]
paul@92 278
            constants.sort()
paul@92 279
            for n, value in constants:
paul@92 280
                print >>f, repr(value)
paul@92 281
paul@92 282
        finally:
paul@92 283
            f.close()
paul@92 284
paul@92 285
    def populate_objects(self):
paul@92 286
paul@92 287
        "Populate objects using attribute and usage information."
paul@92 288
paul@92 289
        all_attrs = {}
paul@92 290
paul@92 291
        # Partition attributes into separate sections so that class and instance
paul@92 292
        # attributes are treated separately.
paul@92 293
paul@92 294
        for source, objtype in [
paul@92 295
            (self.importer.all_class_attrs, "<class>"),
paul@92 296
            (self.importer.all_instance_attrs, "<instance>"),
paul@92 297
            (self.importer.all_module_attrs, "<module>")
paul@92 298
            ]:
paul@92 299
            for name, attrs in source.items():
paul@92 300
                all_attrs[(objtype, name)] = attrs
paul@92 301
paul@92 302
        self.locations = get_allocated_locations(all_attrs, get_attributes_and_sizes)
paul@92 303
paul@92 304
    def populate_parameters(self):
paul@92 305
paul@92 306
        "Populate parameter tables using parameter information."
paul@92 307
paul@130 308
        self.arg_locations = [set()] + get_allocated_locations(self.importer.function_parameters, get_parameters_and_sizes)
paul@92 309
paul@92 310
    def position_attributes(self):
paul@92 311
paul@92 312
        "Position specific attribute references."
paul@92 313
paul@92 314
        # Reverse the location mappings.
paul@92 315
paul@92 316
        attr_locations = self.attr_locations = {}
paul@92 317
paul@92 318
        for i, attrnames in enumerate(self.locations):
paul@92 319
            for attrname in attrnames:
paul@92 320
                attr_locations[attrname] = i
paul@92 321
paul@92 322
        # Record the structures.
paul@92 323
paul@92 324
        for source, objtype in [
paul@92 325
            (self.importer.all_class_attrs, "<class>"),
paul@92 326
            (self.importer.all_instance_attrs, "<instance>"),
paul@92 327
            (self.importer.all_module_attrs, "<module>")
paul@92 328
            ]:
paul@92 329
paul@92 330
            for name, attrnames in source.items():
paul@92 331
                key = Reference(objtype, name)
paul@92 332
                l = self.structures[key] = [None] * len(attrnames)
paul@92 333
                for attrname in attrnames:
paul@92 334
                    position = attr_locations[attrname]
paul@92 335
                    if position >= len(l):
paul@92 336
                        l.extend([None] * (position - len(l) + 1))
paul@92 337
                    l[position] = attrname
paul@92 338
paul@94 339
    def initialise_access_instructions(self):
paul@94 340
paul@94 341
        "Expand access plans into instruction sequences."
paul@94 342
paul@97 343
        for access_location, access_plan in self.deducer.access_plans.items():
paul@94 344
paul@94 345
            # Obtain the access details.
paul@94 346
paul@234 347
            name, test, test_type, base, \
paul@234 348
                traversed, traversal_modes, attrnames, \
paul@234 349
                context, context_test, \
paul@234 350
                first_method, final_method, \
paul@234 351
                origin, accessor_kinds = access_plan
paul@94 352
paul@94 353
            instructions = []
paul@94 354
            emit = instructions.append
paul@94 355
paul@94 356
            if base:
paul@94 357
                original_accessor = base
paul@94 358
            else:
paul@95 359
                original_accessor = "<expr>" # use a generic placeholder
paul@94 360
paul@94 361
            # Prepare for any first attribute access.
paul@94 362
paul@94 363
            if traversed:
paul@94 364
                attrname = traversed[0]
paul@94 365
                del traversed[0]
paul@94 366
            elif attrnames:
paul@94 367
                attrname = attrnames[0]
paul@94 368
                del attrnames[0]
paul@94 369
paul@98 370
            # Perform the first access explicitly if at least one operation
paul@98 371
            # requires it.
paul@98 372
paul@98 373
            access_first_attribute = final_method in ("access", "assign") or traversed or attrnames
paul@98 374
paul@98 375
            # Determine whether the first access involves assignment.
paul@98 376
paul@98 377
            assigning = not traversed and not attrnames and final_method == "assign"
paul@94 378
paul@94 379
            # Set the context if already available.
paul@100 380
paul@103 381
            if context == "base":
paul@103 382
                accessor = context_var = (base,)
paul@103 383
            elif context == "original-accessor":
paul@104 384
paul@104 385
                # Prevent re-evaluation of any dynamic expression by storing it.
paul@104 386
paul@103 387
                if original_accessor == "<expr>":
paul@113 388
                    emit(("__set_accessor", original_accessor))
paul@113 389
                    accessor = context_var = ("<accessor>",)
paul@103 390
                else:
paul@104 391
                    accessor = context_var = (original_accessor,)
paul@100 392
paul@98 393
            # Assigning does not set the context.
paul@94 394
paul@102 395
            elif context in ("final-accessor", "unset") and access_first_attribute:
paul@104 396
paul@104 397
                # Prevent re-evaluation of any dynamic expression by storing it.
paul@104 398
paul@103 399
                if original_accessor == "<expr>":
paul@113 400
                    emit(("__set_accessor", original_accessor))
paul@113 401
                    accessor = ("<accessor>",)
paul@103 402
                else:
paul@104 403
                    accessor = (original_accessor,)
paul@94 404
paul@94 405
            # Apply any test.
paul@94 406
paul@236 407
            if test[0] == "test":
paul@236 408
                accessor = ("__%s_%s_%s" % test, accessor, test_type)
paul@94 409
paul@94 410
            # Perform the first or final access.
paul@94 411
            # The access only needs performing if the resulting accessor is used.
paul@94 412
paul@102 413
            remaining = len(traversed + attrnames)
paul@102 414
paul@94 415
            if access_first_attribute:
paul@94 416
paul@94 417
                if first_method == "relative-class":
paul@98 418
                    if assigning:
paul@113 419
                        emit(("__store_via_class", accessor, attrname, "<assexpr>"))
paul@98 420
                    else:
paul@113 421
                        accessor = ("__load_via_class", accessor, attrname)
paul@98 422
paul@94 423
                elif first_method == "relative-object":
paul@98 424
                    if assigning:
paul@113 425
                        emit(("__store_via_object", accessor, attrname, "<assexpr>"))
paul@98 426
                    else:
paul@113 427
                        accessor = ("__load_via_object", accessor, attrname)
paul@98 428
paul@94 429
                elif first_method == "relative-object-class":
paul@98 430
                    if assigning:
paul@113 431
                        emit(("__get_class_and_store", accessor, attrname, "<assexpr>"))
paul@98 432
                    else:
paul@113 433
                        accessor = ("__get_class_and_load", accessor, attrname)
paul@98 434
paul@94 435
                elif first_method == "check-class":
paul@98 436
                    if assigning:
paul@113 437
                        emit(("__check_and_store_via_class", accessor, attrname, "<assexpr>"))
paul@98 438
                    else:
paul@113 439
                        accessor = ("__check_and_load_via_class", accessor, attrname)
paul@98 440
paul@94 441
                elif first_method == "check-object":
paul@98 442
                    if assigning:
paul@113 443
                        emit(("__check_and_store_via_object", accessor, attrname, "<assexpr>"))
paul@98 444
                    else:
paul@113 445
                        accessor = ("__check_and_load_via_object", accessor, attrname)
paul@98 446
paul@94 447
                elif first_method == "check-object-class":
paul@98 448
                    if assigning:
paul@113 449
                        emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>"))
paul@98 450
                    else:
paul@113 451
                        accessor = ("__check_and_load_via_any", accessor, attrname)
paul@94 452
paul@102 453
            # Traverse attributes using the accessor.
paul@94 454
paul@94 455
            if traversed:
paul@96 456
                for attrname, traversal_mode in zip(traversed, traversal_modes):
paul@98 457
                    assigning = remaining == 1 and final_method == "assign"
paul@94 458
paul@94 459
                    # Set the context, if appropriate.
paul@94 460
paul@98 461
                    if remaining == 1 and final_method != "assign" and context == "final-accessor":
paul@113 462
                        emit(("__set_context", accessor))
paul@113 463
                        accessor = context_var = "<context>"
paul@94 464
paul@94 465
                    # Perform the access only if not achieved directly.
paul@94 466
paul@98 467
                    if remaining > 1 or final_method in ("access", "assign"):
paul@98 468
paul@96 469
                        if traversal_mode == "class":
paul@98 470
                            if assigning:
paul@113 471
                                emit(("__store_via_class", accessor, attrname, "<assexpr>"))
paul@98 472
                            else:
paul@113 473
                                accessor = ("__load_via_class", accessor, attrname)
paul@96 474
                        else:
paul@98 475
                            if assigning:
paul@113 476
                                emit(("__store_via_object", accessor, attrname, "<assexpr>"))
paul@98 477
                            else:
paul@113 478
                                accessor = ("__load_via_object", accessor, attrname)
paul@94 479
paul@94 480
                    remaining -= 1
paul@94 481
paul@94 482
            if attrnames:
paul@96 483
                for attrname in attrnames:
paul@98 484
                    assigning = remaining == 1 and final_method == "assign"
paul@94 485
paul@94 486
                    # Set the context, if appropriate.
paul@94 487
paul@98 488
                    if remaining == 1 and final_method != "assign" and context == "final-accessor":
paul@113 489
                        emit(("__set_context", accessor))
paul@113 490
                        accessor = context_var = "<context>"
paul@94 491
paul@94 492
                    # Perform the access only if not achieved directly.
paul@94 493
paul@98 494
                    if remaining > 1 or final_method in ("access", "assign"):
paul@98 495
paul@98 496
                        if assigning:
paul@113 497
                            emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>"))
paul@98 498
                        else:
paul@113 499
                            accessor = ("__check_and_load_via_any", accessor, attrname)
paul@94 500
paul@94 501
                    remaining -= 1
paul@94 502
paul@118 503
            # Define or emit the means of accessing the actual target.
paul@118 504
paul@98 505
            if final_method == "static-assign":
paul@118 506
                parent, attrname = origin.rsplit(".", 1)
paul@118 507
                emit(("__store_via_object", parent, attrname, "<assexpr>"))
paul@118 508
paul@200 509
            elif final_method in ("static", "static-invoke"):
paul@200 510
                parent, attrname = origin.rsplit(".", 1)
paul@200 511
                accessor = ("__load_static", parent, origin)
paul@118 512
paul@118 513
            # Wrap accesses in context operations.
paul@118 514
paul@102 515
            if context_test == "test":
paul@113 516
                emit(("__test_context", context_var, accessor))
paul@118 517
paul@102 518
            elif context_test == "replace":
paul@118 519
paul@118 520
                # Static invocation targets have a context added but no other
paul@118 521
                # transformation performed.
paul@118 522
paul@118 523
                if final_method == "static-invoke":
paul@118 524
                    emit(("__update_context", context_var, accessor))
paul@118 525
paul@118 526
                # Other invocation targets gain a context and have the bound
paul@118 527
                # version of the callable activated.
paul@118 528
paul@118 529
                else:
paul@118 530
                    emit(("__replace_context", context_var, accessor))
paul@118 531
paul@103 532
            elif final_method not in ("assign", "static-assign"):
paul@103 533
                emit(accessor)
paul@94 534
paul@94 535
            self.access_instructions[access_location] = instructions
paul@234 536
            self.accessor_kinds[access_location] = accessor_kinds
paul@92 537
paul@92 538
    def get_ambiguity_for_attributes(self, attrnames):
paul@92 539
paul@92 540
        """
paul@92 541
        Return a list of attribute position alternatives corresponding to each
paul@92 542
        of the given 'attrnames'.
paul@92 543
        """
paul@92 544
paul@92 545
        ambiguity = []
paul@92 546
paul@92 547
        for attrname in attrnames:
paul@92 548
            position = self.attr_locations[attrname]
paul@92 549
            ambiguity.append(len(self.locations[position]))
paul@92 550
paul@92 551
        return ambiguity
paul@92 552
paul@92 553
    def position_parameters(self):
paul@92 554
paul@92 555
        "Position the parameters for each function's parameter table."
paul@92 556
paul@92 557
        # Reverse the location mappings.
paul@92 558
paul@92 559
        param_locations = self.param_locations = {}
paul@92 560
paul@92 561
        for i, argnames in enumerate(self.arg_locations):
paul@125 562
paul@130 563
            # Position the arguments.
paul@125 564
paul@92 565
            for argname in argnames:
paul@130 566
                param_locations[argname] = i
paul@92 567
paul@92 568
        for name, argnames in self.importer.function_parameters.items():
paul@125 569
paul@125 570
            # Allocate an extra context parameter in the table.
paul@125 571
paul@133 572
            l = self.parameters[name] = [None] + [None] * len(argnames)
paul@92 573
paul@92 574
            # Store an entry for the name along with the name's position in the
paul@92 575
            # parameter list.
paul@92 576
paul@92 577
            for pos, argname in enumerate(argnames):
paul@125 578
paul@125 579
                # Position the argument in the table.
paul@125 580
paul@92 581
                position = param_locations[argname]
paul@92 582
                if position >= len(l):
paul@92 583
                    l.extend([None] * (position - len(l) + 1))
paul@125 584
paul@125 585
                # Indicate an argument list position starting from 1 (after the
paul@125 586
                # initial context argument).
paul@125 587
paul@133 588
                l[position] = (argname, pos + 1)
paul@92 589
paul@92 590
    def populate_tables(self):
paul@92 591
paul@92 592
        """
paul@92 593
        Assign identifiers to attributes and encode structure information using
paul@92 594
        these identifiers.
paul@92 595
        """
paul@92 596
paul@92 597
        self.all_attrnames, d = self._get_name_mapping(self.attr_locations)
paul@92 598
paul@92 599
        # Record the numbers indicating the locations of the names.
paul@92 600
paul@92 601
        for key, attrnames in self.structures.items():
paul@92 602
            l = self.attr_table[key] = []
paul@92 603
            for attrname in attrnames:
paul@92 604
                if attrname is None:
paul@92 605
                    l.append(None)
paul@92 606
                else:
paul@92 607
                    l.append(d[attrname])
paul@92 608
paul@92 609
        self.all_paramnames, d = self._get_name_mapping(self.param_locations)
paul@92 610
paul@92 611
        # Record the numbers indicating the locations of the names.
paul@92 612
paul@92 613
        for key, values in self.parameters.items():
paul@92 614
            l = self.param_table[key] = []
paul@92 615
            for value in values:
paul@92 616
                if value is None:
paul@92 617
                    l.append(None)
paul@92 618
                else:
paul@92 619
                    name, pos = value
paul@92 620
                    l.append((d[name], pos))
paul@92 621
paul@92 622
    def _get_name_mapping(self, locations):
paul@92 623
paul@92 624
        """
paul@92 625
        Get a sorted list of names from 'locations', then map them to
paul@92 626
        identifying numbers. Return the list and the mapping.
paul@92 627
        """
paul@92 628
paul@92 629
        all_names = locations.keys()
paul@92 630
        all_names.sort()
paul@92 631
        return all_names, dict([(name, i) for i, name in enumerate(all_names)])
paul@92 632
paul@92 633
    def populate_constants(self):
paul@92 634
paul@92 635
        """
paul@92 636
        Obtain a collection of distinct constant literals, building a mapping
paul@92 637
        from constant references to those in this collection.
paul@92 638
        """
paul@92 639
paul@92 640
        # Obtain mappings from constant values to identifiers.
paul@92 641
paul@92 642
        self.constants = {}
paul@92 643
paul@92 644
        for path, constants in self.importer.all_constants.items():
paul@92 645
            for constant, n in constants.items():
paul@92 646
paul@92 647
                # Record constants and obtain a number for them.
paul@92 648
paul@92 649
                add_counter_item(self.constants, constant)
paul@92 650
paul@92 651
        self.constant_numbers = {}
paul@92 652
paul@92 653
        for name, (value, value_type) in self.importer.all_constant_values.items():
paul@92 654
            self.constant_numbers[name] = self.constants[value]
paul@92 655
paul@92 656
def combine_rows(a, b):
paul@92 657
    c = []
paul@92 658
    for i, j in zip(a, b):
paul@92 659
        if i is None or j is None:
paul@92 660
            c.append(i or j)
paul@92 661
        else:
paul@92 662
            return None
paul@92 663
    return c
paul@92 664
paul@92 665
def get_attributes_and_sizes(d):
paul@92 666
paul@92 667
    """
paul@92 668
    Return a matrix of attributes, a list of type names corresponding to columns
paul@92 669
    in the matrix, and a list of ranked sizes each indicating...
paul@92 670
paul@92 671
     * a weighted size depending on the kind of object
paul@92 672
     * the minimum size of an object employing an attribute
paul@92 673
     * the number of free columns in the matrix for the attribute
paul@92 674
     * the attribute name itself
paul@92 675
    """
paul@92 676
paul@92 677
    attrs = {}
paul@92 678
    sizes = {}
paul@92 679
    objtypes = {}
paul@92 680
paul@92 681
    for name, attrnames in d.items():
paul@92 682
        objtype, _name = name
paul@92 683
paul@92 684
        for attrname in attrnames:
paul@92 685
paul@92 686
            # Record each type supporting the attribute.
paul@92 687
paul@92 688
            init_item(attrs, attrname, set)
paul@92 689
            attrs[attrname].add(name)
paul@92 690
paul@92 691
            # Maintain a record of the smallest object size supporting the given
paul@92 692
            # attribute.
paul@92 693
paul@92 694
            if not sizes.has_key(attrname):
paul@92 695
                sizes[attrname] = len(attrnames)
paul@92 696
            else:
paul@92 697
                sizes[attrname] = min(sizes[attrname], len(attrnames))
paul@92 698
paul@92 699
            # Record the object types/kinds supporting the attribute.
paul@92 700
paul@92 701
            init_item(objtypes, attrname, set)
paul@92 702
            objtypes[attrname].add(objtype)
paul@92 703
paul@92 704
    # Obtain attribute details in order of size and occupancy.
paul@92 705
paul@92 706
    names = d.keys()
paul@92 707
paul@92 708
    rsizes = []
paul@92 709
    for attrname, size in sizes.items():
paul@92 710
        priority = "<instance>" in objtypes[attrname] and 0.5 or 1
paul@92 711
        occupied = len(attrs[attrname])
paul@92 712
        key = (priority * size, size, len(names) - occupied, attrname)
paul@92 713
        rsizes.append(key)
paul@92 714
paul@92 715
    rsizes.sort()
paul@92 716
paul@92 717
    # Make a matrix of attributes.
paul@92 718
paul@92 719
    matrix = {}
paul@92 720
    for attrname, types in attrs.items():
paul@92 721
        row = []
paul@92 722
        for name in names:
paul@92 723
            if name in types:
paul@92 724
                row.append(attrname)
paul@92 725
            else:
paul@92 726
                row.append(None)
paul@92 727
        matrix[attrname] = row
paul@92 728
paul@92 729
    return matrix, names, rsizes
paul@92 730
paul@92 731
def get_parameters_and_sizes(d):
paul@92 732
paul@92 733
    """
paul@92 734
    Return a matrix of parameters, a list of functions corresponding to columns
paul@92 735
    in the matrix, and a list of ranked sizes each indicating...
paul@92 736
paul@92 737
     * a weighted size depending on the kind of object
paul@92 738
     * the minimum size of a parameter list employing a parameter
paul@92 739
     * the number of free columns in the matrix for the parameter
paul@92 740
     * the parameter name itself
paul@92 741
paul@92 742
    This is a slightly simpler version of the above 'get_attributes_and_sizes'
paul@92 743
    function.
paul@92 744
    """
paul@92 745
paul@92 746
    params = {}
paul@92 747
    sizes = {}
paul@92 748
paul@92 749
    for name, argnames in d.items():
paul@92 750
        for argname in argnames:
paul@92 751
paul@92 752
            # Record each function supporting the parameter.
paul@92 753
paul@92 754
            init_item(params, argname, set)
paul@92 755
            params[argname].add(name)
paul@92 756
paul@92 757
            # Maintain a record of the smallest parameter list supporting the
paul@92 758
            # given parameter.
paul@92 759
paul@92 760
            if not sizes.has_key(argname):
paul@92 761
                sizes[argname] = len(argnames)
paul@92 762
            else:
paul@92 763
                sizes[argname] = min(sizes[argname], len(argnames))
paul@92 764
paul@92 765
    # Obtain attribute details in order of size and occupancy.
paul@92 766
paul@92 767
    names = d.keys()
paul@92 768
paul@92 769
    rsizes = []
paul@92 770
    for argname, size in sizes.items():
paul@92 771
        occupied = len(params[argname])
paul@92 772
        key = (size, size, len(names) - occupied, argname)
paul@92 773
        rsizes.append(key)
paul@92 774
paul@92 775
    rsizes.sort()
paul@92 776
paul@92 777
    # Make a matrix of parameters.
paul@92 778
paul@92 779
    matrix = {}
paul@92 780
    for argname, types in params.items():
paul@92 781
        row = []
paul@92 782
        for name in names:
paul@92 783
            if name in types:
paul@92 784
                row.append(argname)
paul@92 785
            else:
paul@92 786
                row.append(None)
paul@92 787
        matrix[argname] = row
paul@92 788
paul@92 789
    return matrix, names, rsizes
paul@92 790
paul@92 791
def get_allocated_locations(d, fn):
paul@92 792
paul@92 793
    """
paul@92 794
    Return a list where each element corresponds to a structure location and
paul@92 795
    contains a set of attribute names that may be stored at that location, given
paul@92 796
    a mapping 'd' whose keys are (object type, object name) tuples and whose
paul@92 797
    values are collections of attributes.
paul@92 798
    """
paul@92 799
paul@92 800
    matrix, names, rsizes = fn(d)
paul@92 801
    allocated = []
paul@92 802
paul@92 803
    x = 0
paul@92 804
    while x < len(rsizes):
paul@92 805
        weight, size, free, attrname = rsizes[x]
paul@92 806
        base = matrix[attrname]
paul@92 807
        y = x + 1
paul@92 808
        while y < len(rsizes):
paul@92 809
            _weight, _size, _free, _attrname = rsizes[y]
paul@92 810
            occupied = len(names) - _free
paul@92 811
            if occupied > free:
paul@92 812
                break
paul@92 813
            new = combine_rows(base, matrix[_attrname])
paul@92 814
            if new:
paul@92 815
                del matrix[_attrname]
paul@92 816
                del rsizes[y]
paul@92 817
                base = new
paul@92 818
                free -= occupied
paul@92 819
            else:
paul@92 820
                y += 1
paul@92 821
        allocated.append(base)
paul@92 822
        x += 1
paul@92 823
paul@92 824
    # Return the list of attribute names from each row of the allocated
paul@92 825
    # attributes table.
paul@92 826
paul@130 827
    locations = []
paul@130 828
    for attrnames in allocated:
paul@130 829
        l = set()
paul@130 830
        for attrname in attrnames:
paul@130 831
            if attrname:
paul@130 832
                l.add(attrname)
paul@130 833
        locations.append(l)
paul@130 834
    return locations
paul@92 835
paul@92 836
# vim: tabstop=4 expandtab shiftwidth=4