Lichen

Annotated optimiser.py

420:742eee393766
2016-12-16 Paul Boddie Identify predefined constant names earlier in order to make them available in function default information and elsewhere.
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@397 277
            constants = []
paul@406 278
            for (value, value_type, encoding), n in self.constants.items():
paul@406 279
                constants.append((n, value_type, encoding, value))
paul@92 280
            constants.sort()
paul@406 281
            for n, value_type, encoding, value in constants:
paul@406 282
                print >>f, value_type, encoding or "{}", repr(value)
paul@92 283
paul@92 284
        finally:
paul@92 285
            f.close()
paul@92 286
paul@92 287
    def populate_objects(self):
paul@92 288
paul@92 289
        "Populate objects using attribute and usage information."
paul@92 290
paul@92 291
        all_attrs = {}
paul@92 292
paul@92 293
        # Partition attributes into separate sections so that class and instance
paul@92 294
        # attributes are treated separately.
paul@92 295
paul@92 296
        for source, objtype in [
paul@92 297
            (self.importer.all_class_attrs, "<class>"),
paul@92 298
            (self.importer.all_instance_attrs, "<instance>"),
paul@92 299
            (self.importer.all_module_attrs, "<module>")
paul@92 300
            ]:
paul@92 301
            for name, attrs in source.items():
paul@92 302
                all_attrs[(objtype, name)] = attrs
paul@92 303
paul@92 304
        self.locations = get_allocated_locations(all_attrs, get_attributes_and_sizes)
paul@92 305
paul@92 306
    def populate_parameters(self):
paul@92 307
paul@92 308
        "Populate parameter tables using parameter information."
paul@92 309
paul@130 310
        self.arg_locations = [set()] + get_allocated_locations(self.importer.function_parameters, get_parameters_and_sizes)
paul@92 311
paul@92 312
    def position_attributes(self):
paul@92 313
paul@92 314
        "Position specific attribute references."
paul@92 315
paul@92 316
        # Reverse the location mappings.
paul@92 317
paul@92 318
        attr_locations = self.attr_locations = {}
paul@92 319
paul@92 320
        for i, attrnames in enumerate(self.locations):
paul@92 321
            for attrname in attrnames:
paul@92 322
                attr_locations[attrname] = i
paul@92 323
paul@92 324
        # Record the structures.
paul@92 325
paul@92 326
        for source, objtype in [
paul@92 327
            (self.importer.all_class_attrs, "<class>"),
paul@92 328
            (self.importer.all_instance_attrs, "<instance>"),
paul@92 329
            (self.importer.all_module_attrs, "<module>")
paul@92 330
            ]:
paul@92 331
paul@92 332
            for name, attrnames in source.items():
paul@92 333
                key = Reference(objtype, name)
paul@92 334
                l = self.structures[key] = [None] * len(attrnames)
paul@92 335
                for attrname in attrnames:
paul@92 336
                    position = attr_locations[attrname]
paul@92 337
                    if position >= len(l):
paul@92 338
                        l.extend([None] * (position - len(l) + 1))
paul@92 339
                    l[position] = attrname
paul@92 340
paul@94 341
    def initialise_access_instructions(self):
paul@94 342
paul@94 343
        "Expand access plans into instruction sequences."
paul@94 344
paul@97 345
        for access_location, access_plan in self.deducer.access_plans.items():
paul@94 346
paul@94 347
            # Obtain the access details.
paul@94 348
paul@234 349
            name, test, test_type, base, \
paul@234 350
                traversed, traversal_modes, attrnames, \
paul@234 351
                context, context_test, \
paul@234 352
                first_method, final_method, \
paul@234 353
                origin, accessor_kinds = access_plan
paul@94 354
paul@94 355
            instructions = []
paul@94 356
            emit = instructions.append
paul@94 357
paul@94 358
            if base:
paul@94 359
                original_accessor = base
paul@94 360
            else:
paul@95 361
                original_accessor = "<expr>" # use a generic placeholder
paul@94 362
paul@94 363
            # Prepare for any first attribute access.
paul@94 364
paul@94 365
            if traversed:
paul@94 366
                attrname = traversed[0]
paul@94 367
                del traversed[0]
paul@94 368
            elif attrnames:
paul@94 369
                attrname = attrnames[0]
paul@94 370
                del attrnames[0]
paul@94 371
paul@98 372
            # Perform the first access explicitly if at least one operation
paul@98 373
            # requires it.
paul@98 374
paul@98 375
            access_first_attribute = final_method in ("access", "assign") or traversed or attrnames
paul@98 376
paul@98 377
            # Determine whether the first access involves assignment.
paul@98 378
paul@98 379
            assigning = not traversed and not attrnames and final_method == "assign"
paul@368 380
            set_accessor = assigning and "__set_target_accessor" or "__set_accessor"
paul@368 381
            stored_accessor = assigning and "<target_accessor>" or "<accessor>"
paul@94 382
paul@94 383
            # Set the context if already available.
paul@100 384
paul@103 385
            if context == "base":
paul@103 386
                accessor = context_var = (base,)
paul@103 387
            elif context == "original-accessor":
paul@104 388
paul@104 389
                # Prevent re-evaluation of any dynamic expression by storing it.
paul@104 390
paul@103 391
                if original_accessor == "<expr>":
paul@368 392
                    emit((set_accessor, original_accessor))
paul@368 393
                    accessor = context_var = (stored_accessor,)
paul@103 394
                else:
paul@104 395
                    accessor = context_var = (original_accessor,)
paul@100 396
paul@98 397
            # Assigning does not set the context.
paul@94 398
paul@102 399
            elif context in ("final-accessor", "unset") and access_first_attribute:
paul@104 400
paul@104 401
                # Prevent re-evaluation of any dynamic expression by storing it.
paul@104 402
paul@103 403
                if original_accessor == "<expr>":
paul@368 404
                    emit((set_accessor, original_accessor))
paul@368 405
                    accessor = (stored_accessor,)
paul@103 406
                else:
paul@104 407
                    accessor = (original_accessor,)
paul@94 408
paul@94 409
            # Apply any test.
paul@94 410
paul@236 411
            if test[0] == "test":
paul@236 412
                accessor = ("__%s_%s_%s" % test, accessor, test_type)
paul@94 413
paul@94 414
            # Perform the first or final access.
paul@94 415
            # The access only needs performing if the resulting accessor is used.
paul@94 416
paul@102 417
            remaining = len(traversed + attrnames)
paul@102 418
paul@94 419
            if access_first_attribute:
paul@94 420
paul@94 421
                if first_method == "relative-class":
paul@98 422
                    if assigning:
paul@113 423
                        emit(("__store_via_class", accessor, attrname, "<assexpr>"))
paul@98 424
                    else:
paul@113 425
                        accessor = ("__load_via_class", accessor, attrname)
paul@98 426
paul@94 427
                elif first_method == "relative-object":
paul@98 428
                    if assigning:
paul@113 429
                        emit(("__store_via_object", accessor, attrname, "<assexpr>"))
paul@98 430
                    else:
paul@113 431
                        accessor = ("__load_via_object", accessor, attrname)
paul@98 432
paul@94 433
                elif first_method == "relative-object-class":
paul@98 434
                    if assigning:
paul@113 435
                        emit(("__get_class_and_store", accessor, attrname, "<assexpr>"))
paul@98 436
                    else:
paul@113 437
                        accessor = ("__get_class_and_load", accessor, attrname)
paul@98 438
paul@94 439
                elif first_method == "check-class":
paul@98 440
                    if assigning:
paul@113 441
                        emit(("__check_and_store_via_class", accessor, attrname, "<assexpr>"))
paul@98 442
                    else:
paul@113 443
                        accessor = ("__check_and_load_via_class", accessor, attrname)
paul@98 444
paul@94 445
                elif first_method == "check-object":
paul@98 446
                    if assigning:
paul@113 447
                        emit(("__check_and_store_via_object", accessor, attrname, "<assexpr>"))
paul@98 448
                    else:
paul@113 449
                        accessor = ("__check_and_load_via_object", accessor, attrname)
paul@98 450
paul@94 451
                elif first_method == "check-object-class":
paul@98 452
                    if assigning:
paul@113 453
                        emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>"))
paul@98 454
                    else:
paul@113 455
                        accessor = ("__check_and_load_via_any", accessor, attrname)
paul@94 456
paul@102 457
            # Traverse attributes using the accessor.
paul@94 458
paul@94 459
            if traversed:
paul@96 460
                for attrname, traversal_mode in zip(traversed, traversal_modes):
paul@98 461
                    assigning = remaining == 1 and final_method == "assign"
paul@94 462
paul@94 463
                    # Set the context, if appropriate.
paul@94 464
paul@98 465
                    if remaining == 1 and final_method != "assign" and context == "final-accessor":
paul@113 466
                        emit(("__set_context", accessor))
paul@113 467
                        accessor = context_var = "<context>"
paul@94 468
paul@94 469
                    # Perform the access only if not achieved directly.
paul@94 470
paul@98 471
                    if remaining > 1 or final_method in ("access", "assign"):
paul@98 472
paul@96 473
                        if traversal_mode == "class":
paul@98 474
                            if assigning:
paul@113 475
                                emit(("__store_via_class", accessor, attrname, "<assexpr>"))
paul@98 476
                            else:
paul@113 477
                                accessor = ("__load_via_class", accessor, attrname)
paul@96 478
                        else:
paul@98 479
                            if assigning:
paul@113 480
                                emit(("__store_via_object", accessor, attrname, "<assexpr>"))
paul@98 481
                            else:
paul@113 482
                                accessor = ("__load_via_object", accessor, attrname)
paul@94 483
paul@94 484
                    remaining -= 1
paul@94 485
paul@94 486
            if attrnames:
paul@96 487
                for attrname in attrnames:
paul@98 488
                    assigning = remaining == 1 and final_method == "assign"
paul@94 489
paul@94 490
                    # Set the context, if appropriate.
paul@94 491
paul@98 492
                    if remaining == 1 and final_method != "assign" and context == "final-accessor":
paul@113 493
                        emit(("__set_context", accessor))
paul@113 494
                        accessor = context_var = "<context>"
paul@94 495
paul@94 496
                    # Perform the access only if not achieved directly.
paul@94 497
paul@98 498
                    if remaining > 1 or final_method in ("access", "assign"):
paul@98 499
paul@98 500
                        if assigning:
paul@113 501
                            emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>"))
paul@98 502
                        else:
paul@113 503
                            accessor = ("__check_and_load_via_any", accessor, attrname)
paul@94 504
paul@94 505
                    remaining -= 1
paul@94 506
paul@118 507
            # Define or emit the means of accessing the actual target.
paul@118 508
paul@98 509
            if final_method == "static-assign":
paul@118 510
                parent, attrname = origin.rsplit(".", 1)
paul@118 511
                emit(("__store_via_object", parent, attrname, "<assexpr>"))
paul@118 512
paul@200 513
            elif final_method in ("static", "static-invoke"):
paul@200 514
                parent, attrname = origin.rsplit(".", 1)
paul@200 515
                accessor = ("__load_static", parent, origin)
paul@118 516
paul@118 517
            # Wrap accesses in context operations.
paul@118 518
paul@102 519
            if context_test == "test":
paul@113 520
                emit(("__test_context", context_var, accessor))
paul@118 521
paul@102 522
            elif context_test == "replace":
paul@118 523
paul@118 524
                # Static invocation targets have a context added but no other
paul@118 525
                # transformation performed.
paul@118 526
paul@118 527
                if final_method == "static-invoke":
paul@118 528
                    emit(("__update_context", context_var, accessor))
paul@118 529
paul@118 530
                # Other invocation targets gain a context and have the bound
paul@118 531
                # version of the callable activated.
paul@118 532
paul@118 533
                else:
paul@118 534
                    emit(("__replace_context", context_var, accessor))
paul@118 535
paul@103 536
            elif final_method not in ("assign", "static-assign"):
paul@103 537
                emit(accessor)
paul@94 538
paul@94 539
            self.access_instructions[access_location] = instructions
paul@234 540
            self.accessor_kinds[access_location] = accessor_kinds
paul@92 541
paul@92 542
    def get_ambiguity_for_attributes(self, attrnames):
paul@92 543
paul@92 544
        """
paul@92 545
        Return a list of attribute position alternatives corresponding to each
paul@92 546
        of the given 'attrnames'.
paul@92 547
        """
paul@92 548
paul@92 549
        ambiguity = []
paul@92 550
paul@92 551
        for attrname in attrnames:
paul@92 552
            position = self.attr_locations[attrname]
paul@92 553
            ambiguity.append(len(self.locations[position]))
paul@92 554
paul@92 555
        return ambiguity
paul@92 556
paul@92 557
    def position_parameters(self):
paul@92 558
paul@92 559
        "Position the parameters for each function's parameter table."
paul@92 560
paul@92 561
        # Reverse the location mappings.
paul@92 562
paul@92 563
        param_locations = self.param_locations = {}
paul@92 564
paul@92 565
        for i, argnames in enumerate(self.arg_locations):
paul@125 566
paul@130 567
            # Position the arguments.
paul@125 568
paul@92 569
            for argname in argnames:
paul@130 570
                param_locations[argname] = i
paul@92 571
paul@92 572
        for name, argnames in self.importer.function_parameters.items():
paul@125 573
paul@125 574
            # Allocate an extra context parameter in the table.
paul@125 575
paul@133 576
            l = self.parameters[name] = [None] + [None] * len(argnames)
paul@92 577
paul@92 578
            # Store an entry for the name along with the name's position in the
paul@92 579
            # parameter list.
paul@92 580
paul@92 581
            for pos, argname in enumerate(argnames):
paul@125 582
paul@125 583
                # Position the argument in the table.
paul@125 584
paul@92 585
                position = param_locations[argname]
paul@92 586
                if position >= len(l):
paul@92 587
                    l.extend([None] * (position - len(l) + 1))
paul@125 588
paul@125 589
                # Indicate an argument list position starting from 1 (after the
paul@125 590
                # initial context argument).
paul@125 591
paul@133 592
                l[position] = (argname, pos + 1)
paul@92 593
paul@92 594
    def populate_tables(self):
paul@92 595
paul@92 596
        """
paul@92 597
        Assign identifiers to attributes and encode structure information using
paul@92 598
        these identifiers.
paul@92 599
        """
paul@92 600
paul@92 601
        self.all_attrnames, d = self._get_name_mapping(self.attr_locations)
paul@92 602
paul@92 603
        # Record the numbers indicating the locations of the names.
paul@92 604
paul@92 605
        for key, attrnames in self.structures.items():
paul@92 606
            l = self.attr_table[key] = []
paul@92 607
            for attrname in attrnames:
paul@92 608
                if attrname is None:
paul@92 609
                    l.append(None)
paul@92 610
                else:
paul@92 611
                    l.append(d[attrname])
paul@92 612
paul@92 613
        self.all_paramnames, d = self._get_name_mapping(self.param_locations)
paul@92 614
paul@92 615
        # Record the numbers indicating the locations of the names.
paul@92 616
paul@92 617
        for key, values in self.parameters.items():
paul@92 618
            l = self.param_table[key] = []
paul@92 619
            for value in values:
paul@92 620
                if value is None:
paul@92 621
                    l.append(None)
paul@92 622
                else:
paul@92 623
                    name, pos = value
paul@92 624
                    l.append((d[name], pos))
paul@92 625
paul@92 626
    def _get_name_mapping(self, locations):
paul@92 627
paul@92 628
        """
paul@92 629
        Get a sorted list of names from 'locations', then map them to
paul@92 630
        identifying numbers. Return the list and the mapping.
paul@92 631
        """
paul@92 632
paul@92 633
        all_names = locations.keys()
paul@92 634
        all_names.sort()
paul@92 635
        return all_names, dict([(name, i) for i, name in enumerate(all_names)])
paul@92 636
paul@92 637
    def populate_constants(self):
paul@92 638
paul@92 639
        """
paul@92 640
        Obtain a collection of distinct constant literals, building a mapping
paul@92 641
        from constant references to those in this collection.
paul@92 642
        """
paul@92 643
paul@92 644
        # Obtain mappings from constant values to identifiers.
paul@92 645
paul@92 646
        self.constants = {}
paul@92 647
paul@92 648
        for path, constants in self.importer.all_constants.items():
paul@92 649
paul@397 650
            # Record constants and obtain a number for them.
paul@406 651
            # Each constant is actually (value, value_type, encoding).
paul@92 652
paul@397 653
            for constant, n in constants.items():
paul@92 654
                add_counter_item(self.constants, constant)
paul@92 655
paul@92 656
        self.constant_numbers = {}
paul@92 657
paul@397 658
        for name, constant in self.importer.all_constant_values.items():
paul@397 659
            self.constant_numbers[name] = self.constants[constant]
paul@92 660
paul@92 661
def combine_rows(a, b):
paul@92 662
    c = []
paul@92 663
    for i, j in zip(a, b):
paul@92 664
        if i is None or j is None:
paul@92 665
            c.append(i or j)
paul@92 666
        else:
paul@92 667
            return None
paul@92 668
    return c
paul@92 669
paul@92 670
def get_attributes_and_sizes(d):
paul@92 671
paul@92 672
    """
paul@92 673
    Return a matrix of attributes, a list of type names corresponding to columns
paul@92 674
    in the matrix, and a list of ranked sizes each indicating...
paul@92 675
paul@92 676
     * a weighted size depending on the kind of object
paul@92 677
     * the minimum size of an object employing an attribute
paul@92 678
     * the number of free columns in the matrix for the attribute
paul@92 679
     * the attribute name itself
paul@92 680
    """
paul@92 681
paul@92 682
    attrs = {}
paul@92 683
    sizes = {}
paul@92 684
    objtypes = {}
paul@92 685
paul@92 686
    for name, attrnames in d.items():
paul@92 687
        objtype, _name = name
paul@92 688
paul@92 689
        for attrname in attrnames:
paul@92 690
paul@92 691
            # Record each type supporting the attribute.
paul@92 692
paul@92 693
            init_item(attrs, attrname, set)
paul@92 694
            attrs[attrname].add(name)
paul@92 695
paul@92 696
            # Maintain a record of the smallest object size supporting the given
paul@92 697
            # attribute.
paul@92 698
paul@92 699
            if not sizes.has_key(attrname):
paul@92 700
                sizes[attrname] = len(attrnames)
paul@92 701
            else:
paul@92 702
                sizes[attrname] = min(sizes[attrname], len(attrnames))
paul@92 703
paul@92 704
            # Record the object types/kinds supporting the attribute.
paul@92 705
paul@92 706
            init_item(objtypes, attrname, set)
paul@92 707
            objtypes[attrname].add(objtype)
paul@92 708
paul@92 709
    # Obtain attribute details in order of size and occupancy.
paul@92 710
paul@92 711
    names = d.keys()
paul@92 712
paul@92 713
    rsizes = []
paul@92 714
    for attrname, size in sizes.items():
paul@92 715
        priority = "<instance>" in objtypes[attrname] and 0.5 or 1
paul@92 716
        occupied = len(attrs[attrname])
paul@92 717
        key = (priority * size, size, len(names) - occupied, attrname)
paul@92 718
        rsizes.append(key)
paul@92 719
paul@92 720
    rsizes.sort()
paul@92 721
paul@92 722
    # Make a matrix of attributes.
paul@92 723
paul@92 724
    matrix = {}
paul@92 725
    for attrname, types in attrs.items():
paul@92 726
        row = []
paul@92 727
        for name in names:
paul@92 728
            if name in types:
paul@92 729
                row.append(attrname)
paul@92 730
            else:
paul@92 731
                row.append(None)
paul@92 732
        matrix[attrname] = row
paul@92 733
paul@92 734
    return matrix, names, rsizes
paul@92 735
paul@92 736
def get_parameters_and_sizes(d):
paul@92 737
paul@92 738
    """
paul@92 739
    Return a matrix of parameters, a list of functions corresponding to columns
paul@92 740
    in the matrix, and a list of ranked sizes each indicating...
paul@92 741
paul@92 742
     * a weighted size depending on the kind of object
paul@92 743
     * the minimum size of a parameter list employing a parameter
paul@92 744
     * the number of free columns in the matrix for the parameter
paul@92 745
     * the parameter name itself
paul@92 746
paul@92 747
    This is a slightly simpler version of the above 'get_attributes_and_sizes'
paul@92 748
    function.
paul@92 749
    """
paul@92 750
paul@92 751
    params = {}
paul@92 752
    sizes = {}
paul@92 753
paul@92 754
    for name, argnames in d.items():
paul@92 755
        for argname in argnames:
paul@92 756
paul@92 757
            # Record each function supporting the parameter.
paul@92 758
paul@92 759
            init_item(params, argname, set)
paul@92 760
            params[argname].add(name)
paul@92 761
paul@92 762
            # Maintain a record of the smallest parameter list supporting the
paul@92 763
            # given parameter.
paul@92 764
paul@92 765
            if not sizes.has_key(argname):
paul@92 766
                sizes[argname] = len(argnames)
paul@92 767
            else:
paul@92 768
                sizes[argname] = min(sizes[argname], len(argnames))
paul@92 769
paul@92 770
    # Obtain attribute details in order of size and occupancy.
paul@92 771
paul@92 772
    names = d.keys()
paul@92 773
paul@92 774
    rsizes = []
paul@92 775
    for argname, size in sizes.items():
paul@92 776
        occupied = len(params[argname])
paul@92 777
        key = (size, size, len(names) - occupied, argname)
paul@92 778
        rsizes.append(key)
paul@92 779
paul@92 780
    rsizes.sort()
paul@92 781
paul@92 782
    # Make a matrix of parameters.
paul@92 783
paul@92 784
    matrix = {}
paul@92 785
    for argname, types in params.items():
paul@92 786
        row = []
paul@92 787
        for name in names:
paul@92 788
            if name in types:
paul@92 789
                row.append(argname)
paul@92 790
            else:
paul@92 791
                row.append(None)
paul@92 792
        matrix[argname] = row
paul@92 793
paul@92 794
    return matrix, names, rsizes
paul@92 795
paul@92 796
def get_allocated_locations(d, fn):
paul@92 797
paul@92 798
    """
paul@92 799
    Return a list where each element corresponds to a structure location and
paul@92 800
    contains a set of attribute names that may be stored at that location, given
paul@92 801
    a mapping 'd' whose keys are (object type, object name) tuples and whose
paul@92 802
    values are collections of attributes.
paul@92 803
    """
paul@92 804
paul@92 805
    matrix, names, rsizes = fn(d)
paul@92 806
    allocated = []
paul@92 807
paul@92 808
    x = 0
paul@92 809
    while x < len(rsizes):
paul@92 810
        weight, size, free, attrname = rsizes[x]
paul@92 811
        base = matrix[attrname]
paul@92 812
        y = x + 1
paul@92 813
        while y < len(rsizes):
paul@92 814
            _weight, _size, _free, _attrname = rsizes[y]
paul@92 815
            occupied = len(names) - _free
paul@92 816
            if occupied > free:
paul@92 817
                break
paul@92 818
            new = combine_rows(base, matrix[_attrname])
paul@92 819
            if new:
paul@92 820
                del matrix[_attrname]
paul@92 821
                del rsizes[y]
paul@92 822
                base = new
paul@92 823
                free -= occupied
paul@92 824
            else:
paul@92 825
                y += 1
paul@92 826
        allocated.append(base)
paul@92 827
        x += 1
paul@92 828
paul@92 829
    # Return the list of attribute names from each row of the allocated
paul@92 830
    # attributes table.
paul@92 831
paul@130 832
    locations = []
paul@130 833
    for attrnames in allocated:
paul@130 834
        l = set()
paul@130 835
        for attrname in attrnames:
paul@130 836
            if attrname:
paul@130 837
                l.add(attrname)
paul@130 838
        locations.append(l)
paul@130 839
    return locations
paul@92 840
paul@92 841
# vim: tabstop=4 expandtab shiftwidth=4