Lichen

Annotated deducer.py

932:c07b0dd14f85
13 months ago Paul Boddie Moved integer instantiation support to library functions.
paul@44 1
#!/usr/bin/env python
paul@44 2
paul@44 3
"""
paul@44 4
Deduce types for usage observations.
paul@44 5
paul@825 6
Copyright (C) 2014, 2015, 2016, 2017, 2018 Paul Boddie <paul@boddie.org.uk>
paul@44 7
paul@44 8
This program is free software; you can redistribute it and/or modify it under
paul@44 9
the terms of the GNU General Public License as published by the Free Software
paul@44 10
Foundation; either version 3 of the License, or (at your option) any later
paul@44 11
version.
paul@44 12
paul@44 13
This program is distributed in the hope that it will be useful, but WITHOUT
paul@44 14
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
paul@44 15
FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
paul@44 16
details.
paul@44 17
paul@44 18
You should have received a copy of the GNU General Public License along with
paul@44 19
this program.  If not, see <http://www.gnu.org/licenses/>.
paul@44 20
"""
paul@44 21
paul@791 22
from common import first, get_assigned_attributes, get_attrnames, \
paul@90 23
                   get_invoked_attributes, get_name_path, init_item, \
paul@791 24
                   order_dependencies_partial, sorted_output, \
paul@791 25
                   AccessLocation, CommonOutput, Location
paul@789 26
from encoders import encode_access_location, encode_alias_location, \
paul@789 27
                     encode_constrained, encode_instruction, encode_location, \
paul@789 28
                     encode_usage, get_kinds, \
paul@789 29
                     test_label_for_kind, test_label_for_type
paul@71 30
from errors import DeduceError
paul@44 31
from os.path import join
paul@57 32
from referencing import combine_types, is_single_class_type, separate_types, \
paul@57 33
                        Reference
paul@44 34
paul@44 35
class Deducer(CommonOutput):
paul@44 36
paul@44 37
    "Deduce types in a program."
paul@44 38
paul@654 39
    root_class_type = "__builtins__.object"
paul@654 40
paul@44 41
    def __init__(self, importer, output):
paul@44 42
paul@44 43
        """
paul@44 44
        Initialise an instance using the given 'importer' that will perform
paul@44 45
        deductions on the program information, writing the results to the given
paul@44 46
        'output' directory.
paul@44 47
        """
paul@44 48
paul@44 49
        self.importer = importer
paul@44 50
        self.output = output
paul@44 51
paul@44 52
        # Descendants of classes.
paul@44 53
paul@44 54
        self.descendants = {}
paul@44 55
        self.init_descendants()
paul@44 56
        self.init_special_attributes()
paul@44 57
paul@44 58
        # Map locations to usage in order to determine specific types.
paul@44 59
paul@44 60
        self.location_index = {}
paul@44 61
paul@44 62
        # Map access locations to definition locations.
paul@44 63
paul@44 64
        self.access_index = {}
paul@44 65
paul@742 66
        # Map definition locations to affected accesses.
paul@742 67
paul@742 68
        self.access_index_rev = {}
paul@742 69
paul@44 70
        # Map aliases to accesses that define them.
paul@44 71
paul@44 72
        self.alias_index = {}
paul@44 73
paul@742 74
        # Map accesses to aliases whose initial values are influenced by them.
paul@742 75
paul@742 76
        self.alias_index_rev = {}
paul@742 77
paul@791 78
        # Map definitions and accesses to initialised names.
paul@791 79
paul@791 80
        self.initialised_names = {}
paul@791 81
        self.initialised_accesses = {}
paul@791 82
paul@64 83
        # Map constant accesses to redefined accesses.
paul@64 84
paul@64 85
        self.const_accesses = {}
paul@67 86
        self.const_accesses_rev = {}
paul@64 87
paul@44 88
        # Map usage observations to assigned attributes.
paul@44 89
paul@44 90
        self.assigned_attrs = {}
paul@44 91
paul@44 92
        # Map usage observations to objects.
paul@44 93
paul@44 94
        self.attr_class_types = {}
paul@44 95
        self.attr_instance_types = {}
paul@44 96
        self.attr_module_types = {}
paul@44 97
paul@501 98
        # All known attribute names.
paul@501 99
paul@501 100
        self.all_attrnames = set()
paul@501 101
paul@44 102
        # Modified attributes from usage observations.
paul@44 103
paul@44 104
        self.modified_attributes = {}
paul@44 105
paul@117 106
        # Accesses that are assignments or invocations.
paul@71 107
paul@71 108
        self.reference_assignments = set()
paul@553 109
        self.reference_invocations = {}
paul@553 110
        self.reference_invocations_unsuitable = {}
paul@71 111
paul@44 112
        # Map locations to types, constrained indicators and attributes.
paul@44 113
paul@44 114
        self.accessor_class_types = {}
paul@44 115
        self.accessor_instance_types = {}
paul@44 116
        self.accessor_module_types = {}
paul@44 117
        self.provider_class_types = {}
paul@44 118
        self.provider_instance_types = {}
paul@44 119
        self.provider_module_types = {}
paul@67 120
        self.accessor_constrained = set()
paul@44 121
        self.access_constrained = set()
paul@44 122
        self.referenced_attrs = {}
paul@44 123
        self.referenced_objects = {}
paul@44 124
paul@67 125
        # Details of access operations.
paul@67 126
paul@67 127
        self.access_plans = {}
paul@67 128
paul@653 129
        # Specific attribute access information.
paul@653 130
paul@653 131
        self.access_instructions = {}
paul@653 132
        self.accessor_kinds = {}
paul@653 133
paul@44 134
        # Accumulated information about accessors and providers.
paul@44 135
paul@44 136
        self.accessor_general_class_types = {}
paul@44 137
        self.accessor_general_instance_types = {}
paul@44 138
        self.accessor_general_module_types = {}
paul@44 139
        self.accessor_all_types = {}
paul@44 140
        self.accessor_all_general_types = {}
paul@44 141
        self.provider_all_types = {}
paul@44 142
        self.accessor_guard_tests = {}
paul@44 143
paul@44 144
        # Accumulated information about accessed attributes and
paul@67 145
        # access/attribute-specific accessor tests.
paul@44 146
paul@44 147
        self.reference_all_attrs = {}
paul@687 148
        self.reference_all_providers = {}
paul@687 149
        self.reference_all_provider_kinds = {}
paul@67 150
        self.reference_all_accessor_types = {}
paul@67 151
        self.reference_all_accessor_general_types = {}
paul@44 152
        self.reference_test_types = {}
paul@77 153
        self.reference_test_accessor_type = {}
paul@44 154
paul@44 155
        # The processing workflow itself.
paul@44 156
paul@44 157
        self.init_usage_index()
paul@501 158
        self.init_attr_type_indexes()
paul@501 159
        self.init_combined_attribute_index()
paul@44 160
        self.init_accessors()
paul@44 161
        self.init_accesses()
paul@44 162
        self.init_aliases()
paul@44 163
        self.modify_mutated_attributes()
paul@44 164
        self.identify_references()
paul@44 165
        self.classify_accessors()
paul@44 166
        self.classify_accesses()
paul@67 167
        self.initialise_access_plans()
paul@653 168
        self.initialise_access_instructions()
paul@411 169
        self.identify_dependencies()
paul@44 170
paul@44 171
    def to_output(self):
paul@44 172
paul@44 173
        "Write the output files using deduction information."
paul@44 174
paul@44 175
        self.check_output()
paul@44 176
paul@44 177
        self.write_mutations()
paul@44 178
        self.write_accessors()
paul@44 179
        self.write_accesses()
paul@65 180
        self.write_access_plans()
paul@44 181
paul@44 182
    def write_mutations(self):
paul@44 183
paul@44 184
        """
paul@44 185
        Write mutation-related output in the following format:
paul@44 186
paul@44 187
        qualified name " " original object type
paul@44 188
paul@44 189
        Object type can be "<class>", "<function>" or "<var>".
paul@44 190
        """
paul@44 191
paul@44 192
        f = open(join(self.output, "mutations"), "w")
paul@44 193
        try:
paul@44 194
            attrs = self.modified_attributes.items()
paul@44 195
            attrs.sort()
paul@44 196
paul@44 197
            for attr, value in attrs:
paul@44 198
                print >>f, attr, value
paul@44 199
        finally:
paul@44 200
            f.close()
paul@44 201
paul@44 202
    def write_accessors(self):
paul@44 203
paul@44 204
        """
paul@44 205
        Write reference-related output in the following format for types:
paul@44 206
paul@44 207
        location " " ( "constrained" | "deduced" ) " " attribute type " " most general type names " " number of specific types
paul@44 208
paul@44 209
        Note that multiple lines can be given for each location, one for each
paul@44 210
        attribute type.
paul@44 211
paul@44 212
        Locations have the following format:
paul@44 213
paul@788 214
        qualified name of scope ":" local name ":" name version
paul@44 215
paul@44 216
        The attribute type can be "<class>", "<instance>", "<module>" or "<>",
paul@44 217
        where the latter indicates an absence of suitable references.
paul@44 218
paul@44 219
        Type names indicate the type providing the attributes, being either a
paul@44 220
        class or module qualified name.
paul@44 221
paul@44 222
        ----
paul@44 223
paul@44 224
        A summary of accessor types is formatted as follows:
paul@44 225
paul@44 226
        location " " ( "constrained" | "deduced" ) " " ( "specific" | "common" | "unguarded" ) " " most general type names " " number of specific types
paul@44 227
paul@44 228
        This summary groups all attribute types (class, instance, module) into a
paul@44 229
        single line in order to determine the complexity of identifying an
paul@44 230
        accessor.
paul@44 231
paul@44 232
        ----
paul@44 233
paul@44 234
        References that cannot be supported by any types are written to a
paul@44 235
        warnings file in the following format:
paul@44 236
paul@44 237
        location
paul@44 238
paul@44 239
        ----
paul@44 240
paul@44 241
        For each location where a guard would be asserted to guarantee the
paul@44 242
        nature of an object, the following format is employed:
paul@44 243
paul@44 244
        location " " ( "specific" | "common" ) " " object kind " " object types
paul@44 245
paul@44 246
        Object kind can be "<class>", "<instance>" or "<module>".
paul@788 247
paul@788 248
        ----
paul@788 249
paul@788 250
        A summary of aliases is formatted as follows:
paul@788 251
paul@788 252
        location " " locations
paul@44 253
        """
paul@44 254
paul@44 255
        f_type_summary = open(join(self.output, "type_summary"), "w")
paul@44 256
        f_types = open(join(self.output, "types"), "w")
paul@44 257
        f_warnings = open(join(self.output, "type_warnings"), "w")
paul@44 258
        f_guards = open(join(self.output, "guards"), "w")
paul@788 259
        f_aliases = open(join(self.output, "aliases"), "w")
paul@44 260
paul@44 261
        try:
paul@44 262
            locations = self.accessor_class_types.keys()
paul@44 263
            locations.sort()
paul@44 264
paul@44 265
            for location in locations:
paul@67 266
                constrained = location in self.accessor_constrained
paul@44 267
paul@44 268
                # Accessor information.
paul@44 269
paul@44 270
                class_types = self.accessor_class_types[location]
paul@44 271
                instance_types = self.accessor_instance_types[location]
paul@44 272
                module_types = self.accessor_module_types[location]
paul@44 273
paul@44 274
                general_class_types = self.accessor_general_class_types[location]
paul@44 275
                general_instance_types = self.accessor_general_instance_types[location]
paul@44 276
                general_module_types = self.accessor_general_module_types[location]
paul@44 277
paul@44 278
                all_types = self.accessor_all_types[location]
paul@44 279
                all_general_types = self.accessor_all_general_types[location]
paul@44 280
paul@44 281
                if class_types:
paul@44 282
                    print >>f_types, encode_location(location), encode_constrained(constrained), "<class>", \
paul@44 283
                        sorted_output(general_class_types), len(class_types)
paul@44 284
paul@44 285
                if instance_types:
paul@44 286
                    print >>f_types, encode_location(location), encode_constrained(constrained), "<instance>", \
paul@44 287
                        sorted_output(general_instance_types), len(instance_types)
paul@44 288
paul@44 289
                if module_types:
paul@44 290
                    print >>f_types, encode_location(location), encode_constrained(constrained), "<module>", \
paul@44 291
                        sorted_output(general_module_types), len(module_types)
paul@44 292
paul@44 293
                if not all_types:
paul@44 294
                    print >>f_types, encode_location(location), "deduced", "<>", 0
paul@55 295
                    attrnames = list(self.location_index[location])
paul@55 296
                    attrnames.sort()
paul@55 297
                    print >>f_warnings, encode_location(location), "; ".join(map(encode_usage, attrnames))
paul@44 298
paul@44 299
                guard_test = self.accessor_guard_tests.get(location)
paul@237 300
                if guard_test:
paul@237 301
                    guard_test_type, guard_test_arg = guard_test
paul@44 302
paul@44 303
                # Write specific type guard details.
paul@44 304
paul@237 305
                if guard_test and guard_test_type == "specific":
paul@237 306
                    print >>f_guards, encode_location(location), "-".join(guard_test), \
paul@237 307
                        first(get_kinds(all_types)), \
paul@44 308
                        sorted_output(all_types)
paul@44 309
paul@44 310
                # Write common type guard details.
paul@44 311
paul@237 312
                elif guard_test and guard_test_type == "common":
paul@237 313
                    print >>f_guards, encode_location(location), "-".join(guard_test), \
paul@237 314
                        first(get_kinds(all_general_types)), \
paul@44 315
                        sorted_output(all_general_types)
paul@44 316
paul@44 317
                print >>f_type_summary, encode_location(location), encode_constrained(constrained), \
paul@237 318
                    guard_test and "-".join(guard_test) or "unguarded", sorted_output(all_general_types), len(all_types)
paul@44 319
paul@788 320
            # Aliases are visited separately from accessors, even though they
paul@788 321
            # are often the same thing.
paul@788 322
paul@788 323
            locations = self.alias_index.keys()
paul@788 324
            locations.sort()
paul@788 325
paul@788 326
            for location in locations:
paul@788 327
                accesses = []
paul@788 328
                for access_location in self.alias_index[location]:
paul@789 329
                    invocation = access_location in self.reference_invocations
paul@789 330
                    accesses.append(encode_alias_location(access_location, invocation))
paul@789 331
                invocation = location in self.reference_invocations
paul@789 332
                print >>f_aliases, encode_alias_location(location, invocation), ", ".join(accesses)
paul@788 333
paul@44 334
        finally:
paul@44 335
            f_type_summary.close()
paul@44 336
            f_types.close()
paul@44 337
            f_warnings.close()
paul@44 338
            f_guards.close()
paul@788 339
            f_aliases.close()
paul@44 340
paul@44 341
    def write_accesses(self):
paul@44 342
paul@44 343
        """
paul@44 344
        Specific attribute output is produced in the following format:
paul@44 345
paul@44 346
        location " " ( "constrained" | "deduced" ) " " attribute type " " attribute references
paul@44 347
paul@44 348
        Note that multiple lines can be given for each location and attribute
paul@44 349
        name, one for each attribute type.
paul@44 350
paul@44 351
        Locations have the following format:
paul@44 352
paul@788 353
        qualified name of scope ":" local name ":" attribute name ":" access number
paul@44 354
paul@44 355
        The attribute type can be "<class>", "<instance>", "<module>" or "<>",
paul@44 356
        where the latter indicates an absence of suitable references.
paul@44 357
paul@44 358
        Attribute references have the following format:
paul@44 359
paul@44 360
        object type ":" qualified name
paul@44 361
paul@44 362
        Object type can be "<class>", "<function>" or "<var>".
paul@44 363
paul@44 364
        ----
paul@44 365
paul@44 366
        A summary of attributes is formatted as follows:
paul@44 367
paul@44 368
        location " " attribute name " " ( "constrained" | "deduced" ) " " test " " attribute references
paul@44 369
paul@44 370
        This summary groups all attribute types (class, instance, module) into a
paul@44 371
        single line in order to determine the complexity of each access.
paul@44 372
paul@44 373
        Tests can be "validate", "specific", "untested", "guarded-validate" or "guarded-specific".
paul@44 374
paul@44 375
        ----
paul@44 376
paul@44 377
        For each access where a test would be asserted to guarantee the
paul@44 378
        nature of an attribute, the following formats are employed:
paul@44 379
paul@44 380
        location " " attribute name " " "validate"
paul@44 381
        location " " attribute name " " "specific" " " attribute type " " object type
paul@44 382
paul@44 383
        ----
paul@44 384
paul@44 385
        References that cannot be supported by any types are written to a
paul@44 386
        warnings file in the following format:
paul@44 387
paul@44 388
        location
paul@44 389
        """
paul@44 390
paul@44 391
        f_attr_summary = open(join(self.output, "attribute_summary"), "w")
paul@44 392
        f_attrs = open(join(self.output, "attributes"), "w")
paul@44 393
        f_tests = open(join(self.output, "tests"), "w")
paul@44 394
        f_warnings = open(join(self.output, "attribute_warnings"), "w")
paul@553 395
        f_unsuitable = open(join(self.output, "invocation_warnings"), "w")
paul@44 396
paul@44 397
        try:
paul@44 398
            locations = self.referenced_attrs.keys()
paul@44 399
            locations.sort()
paul@44 400
paul@44 401
            for location in locations:
paul@44 402
                constrained = location in self.access_constrained
paul@44 403
paul@44 404
                # Attribute information, both name-based and anonymous.
paul@44 405
paul@44 406
                referenced_attrs = self.referenced_attrs[location]
paul@44 407
paul@44 408
                if referenced_attrs:
paul@791 409
                    attrname = location.get_attrname()
paul@44 410
paul@738 411
                    all_accessed_attrs = list(set(self.reference_all_attrs[location]))
paul@738 412
                    all_accessed_attrs.sort()
paul@44 413
paul@44 414
                    for attrtype, attrs in self.get_referenced_attrs(location):
paul@44 415
                        print >>f_attrs, encode_access_location(location), encode_constrained(constrained), attrtype, sorted_output(attrs)
paul@44 416
paul@44 417
                    test_type = self.reference_test_types.get(location)
paul@44 418
paul@44 419
                    # Write the need to test at run time.
paul@44 420
paul@237 421
                    if test_type[0] == "validate":
paul@237 422
                        print >>f_tests, encode_access_location(location), "-".join(test_type)
paul@44 423
paul@44 424
                    # Write any type checks for anonymous accesses.
paul@44 425
paul@77 426
                    elif test_type and self.reference_test_accessor_type.get(location):
paul@240 427
                        print >>f_tests, encode_access_location(location), "-".join(test_type), \
paul@44 428
                            sorted_output(all_accessed_attrs), \
paul@77 429
                            self.reference_test_accessor_type[location]
paul@44 430
paul@44 431
                    print >>f_attr_summary, encode_access_location(location), encode_constrained(constrained), \
paul@237 432
                        test_type and "-".join(test_type) or "untested", sorted_output(all_accessed_attrs)
paul@44 433
paul@553 434
                    # Write details of potentially unsuitable invocation
paul@553 435
                    # occurrences.
paul@553 436
paul@553 437
                    unsuitable = self.reference_invocations_unsuitable.get(location)
paul@553 438
                    if unsuitable:
paul@553 439
                        unsuitable = map(str, unsuitable)
paul@553 440
                        unsuitable.sort()
paul@553 441
                        print >>f_unsuitable, encode_access_location(location), ", ".join(unsuitable)
paul@553 442
paul@44 443
                else:
paul@44 444
                    print >>f_warnings, encode_access_location(location)
paul@44 445
paul@44 446
        finally:
paul@44 447
            f_attr_summary.close()
paul@44 448
            f_attrs.close()
paul@44 449
            f_tests.close()
paul@44 450
            f_warnings.close()
paul@553 451
            f_unsuitable.close()
paul@44 452
paul@67 453
    def write_access_plans(self):
paul@67 454
paul@91 455
        """
paul@653 456
        Write access and instruction plans.
paul@653 457
paul@91 458
        Each attribute access is written out as a plan of the following form:
paul@91 459
paul@91 460
        location " " name " " test " " test type " " base " " traversed attributes
paul@653 461
                 " " traversal access modes " " attributes to traverse
paul@653 462
                 " " context " " context test " " first access method
paul@653 463
                 " " final access method " " static attribute " " accessor kinds
paul@653 464
paul@653 465
        Locations have the following format:
paul@653 466
paul@653 467
        qualified name of scope "." local name ":" name version
paul@653 468
paul@653 469
        Traversal access modes are either "class" (obtain accessor class to
paul@653 470
        access attribute) or "object" (obtain attribute directly from accessor).
paul@91 471
        """
paul@67 472
paul@67 473
        f_attrs = open(join(self.output, "attribute_plans"), "w")
paul@67 474
paul@67 475
        try:
paul@67 476
            locations = self.access_plans.keys()
paul@67 477
            locations.sort()
paul@67 478
paul@67 479
            for location in locations:
paul@234 480
                name, test, test_type, base, \
paul@234 481
                    traversed, traversal_modes, attrnames, \
paul@102 482
                    context, context_test, \
paul@234 483
                    first_method, final_method, \
paul@234 484
                    attr, accessor_kinds = self.access_plans[location]
paul@77 485
paul@75 486
                print >>f_attrs, encode_access_location(location), \
paul@213 487
                                 name or "{}", \
paul@237 488
                                 test and "-".join(test) or "{}", \
paul@237 489
                                 test_type or "{}", \
paul@75 490
                                 base or "{}", \
paul@67 491
                                 ".".join(traversed) or "{}", \
paul@96 492
                                 ".".join(traversal_modes) or "{}", \
paul@67 493
                                 ".".join(attrnames) or "{}", \
paul@102 494
                                 context, context_test, \
paul@234 495
                                 first_method, final_method, attr or "{}", \
paul@234 496
                                 ",".join(accessor_kinds)
paul@67 497
paul@67 498
        finally:
paul@67 499
            f_attrs.close()
paul@67 500
paul@653 501
        f = open(join(self.output, "instruction_plans"), "w")
paul@653 502
        try:
paul@653 503
            access_instructions = self.access_instructions.items()
paul@653 504
            access_instructions.sort()
paul@653 505
paul@653 506
            for location, instructions in access_instructions:
paul@653 507
                print >>f, encode_access_location(location), "..."
paul@653 508
                for instruction in instructions:
paul@653 509
                    print >>f, encode_instruction(instruction)
paul@653 510
                print >>f
paul@653 511
paul@653 512
        finally:
paul@653 513
            f.close()
paul@653 514
paul@44 515
    def classify_accessors(self):
paul@44 516
paul@44 517
        "For each program location, classify accessors."
paul@44 518
paul@44 519
        # Where instance and module types are defined, class types are also
paul@44 520
        # defined. See: init_definition_details
paul@44 521
paul@44 522
        locations = self.accessor_class_types.keys()
paul@44 523
paul@44 524
        for location in locations:
paul@67 525
            constrained = location in self.accessor_constrained
paul@44 526
paul@44 527
            # Provider information.
paul@44 528
paul@44 529
            class_types = self.provider_class_types[location]
paul@44 530
            instance_types = self.provider_instance_types[location]
paul@44 531
            module_types = self.provider_module_types[location]
paul@44 532
paul@44 533
            # Collect specific and general type information.
paul@44 534
paul@69 535
            self.provider_all_types[location] = \
paul@57 536
                combine_types(class_types, instance_types, module_types)
paul@44 537
paul@44 538
            # Accessor information.
paul@44 539
paul@44 540
            class_types = self.accessor_class_types[location]
paul@44 541
            self.accessor_general_class_types[location] = \
paul@69 542
                general_class_types = self.get_most_general_class_types(class_types)
paul@44 543
paul@44 544
            instance_types = self.accessor_instance_types[location]
paul@44 545
            self.accessor_general_instance_types[location] = \
paul@69 546
                general_instance_types = self.get_most_general_class_types(instance_types)
paul@44 547
paul@44 548
            module_types = self.accessor_module_types[location]
paul@44 549
            self.accessor_general_module_types[location] = \
paul@44 550
                general_module_types = self.get_most_general_module_types(module_types)
paul@44 551
paul@44 552
            # Collect specific and general type information.
paul@44 553
paul@44 554
            self.accessor_all_types[location] = all_types = \
paul@57 555
                combine_types(class_types, instance_types, module_types)
paul@44 556
paul@44 557
            self.accessor_all_general_types[location] = all_general_types = \
paul@57 558
                combine_types(general_class_types, general_instance_types, general_module_types)
paul@44 559
paul@742 560
            # Record guard information but only for accessors employed by
paul@742 561
            # accesses. There are no attribute accesses to guard, otherwise.
paul@742 562
paul@742 563
            if not constrained and self.access_index_rev.get(location):
paul@44 564
paul@816 565
                # Test for self parameters in methods that could not be
paul@816 566
                # constrained, potentially due to usage unsupported by the class
paul@816 567
                # defining the method (such as in mix-in classes).
paul@816 568
paul@816 569
                if location.name != "self" or self.in_method(location.path):
paul@816 570
                    self.record_guard(location, all_types, all_general_types)
paul@816 571
paul@816 572
    def record_guard(self, location, all_types, all_general_types):
paul@816 573
paul@816 574
        """
paul@816 575
        For the accessor 'location', record a guard if 'all_types' or
paul@816 576
        'all_general_types' are appropriate. Where no guard is recorded, access
paul@816 577
        tests will need to be applied.
paul@816 578
        """
paul@816 579
paul@816 580
        # Record specific type guard details.
paul@816 581
paul@816 582
        if len(all_types) == 1:
paul@816 583
            self.accessor_guard_tests[location] = ("specific", test_label_for_type(first(all_types)))
paul@816 584
        elif is_single_class_type(all_types):
paul@816 585
            self.accessor_guard_tests[location] = ("specific", "object")
paul@816 586
paul@816 587
        # Record common type guard details.
paul@816 588
paul@816 589
        elif len(all_general_types) == 1:
paul@816 590
            self.accessor_guard_tests[location] = ("common", test_label_for_type(first(all_types)))
paul@816 591
        elif is_single_class_type(all_general_types):
paul@816 592
            self.accessor_guard_tests[location] = ("common", "object")
paul@816 593
paul@816 594
        # Otherwise, no convenient guard can be defined.
paul@44 595
paul@44 596
    def classify_accesses(self):
paul@44 597
paul@44 598
        "For each program location, classify accesses."
paul@44 599
paul@44 600
        # Attribute accesses use potentially different locations to those of
paul@44 601
        # accessors.
paul@44 602
paul@44 603
        locations = self.referenced_attrs.keys()
paul@44 604
paul@44 605
        for location in locations:
paul@44 606
            constrained = location in self.access_constrained
paul@44 607
paul@69 608
            # Combine type information from all accessors supplying the access.
paul@44 609
paul@44 610
            accessor_locations = self.get_accessors_for_access(location)
paul@44 611
paul@44 612
            all_provider_types = set()
paul@44 613
            all_accessor_types = set()
paul@44 614
            all_accessor_general_types = set()
paul@44 615
paul@44 616
            for accessor_location in accessor_locations:
paul@44 617
paul@44 618
                # Obtain the provider types for guard-related attribute access
paul@44 619
                # checks.
paul@44 620
paul@67 621
                all_provider_types.update(self.provider_all_types.get(accessor_location))
paul@67 622
paul@67 623
                # Obtain the accessor guard types (specific and general).
paul@67 624
paul@67 625
                all_accessor_types.update(self.accessor_all_types.get(accessor_location))
paul@67 626
                all_accessor_general_types.update(self.accessor_all_general_types.get(accessor_location))
paul@44 627
paul@70 628
            # Obtain basic properties of the types involved in the access.
paul@70 629
paul@70 630
            single_accessor_type = len(all_accessor_types) == 1
paul@70 631
            single_accessor_class_type = is_single_class_type(all_accessor_types)
paul@70 632
            single_accessor_general_type = len(all_accessor_general_types) == 1
paul@70 633
            single_accessor_general_class_type = is_single_class_type(all_accessor_general_types)
paul@70 634
paul@69 635
            # Determine whether the attribute access is guarded or not.
paul@44 636
paul@44 637
            guarded = (
paul@70 638
                single_accessor_type or single_accessor_class_type or
paul@70 639
                single_accessor_general_type or single_accessor_general_class_type
paul@44 640
                )
paul@44 641
paul@44 642
            if guarded:
paul@44 643
                (guard_class_types, guard_instance_types, guard_module_types,
paul@57 644
                    _function_types, _var_types) = separate_types(all_provider_types)
paul@44 645
paul@67 646
            self.reference_all_accessor_types[location] = all_accessor_types
paul@67 647
            self.reference_all_accessor_general_types[location] = all_accessor_general_types
paul@63 648
paul@44 649
            # Attribute information, both name-based and anonymous.
paul@44 650
paul@44 651
            referenced_attrs = self.referenced_attrs[location]
paul@44 652
paul@71 653
            if not referenced_attrs:
paul@839 654
                raise DeduceError("In %s, access via %s to attribute %s (occurrence %d) cannot be identified." %
paul@839 655
                    (location.path, location.name, location.get_attrname(), location.access_number))
paul@71 656
paul@71 657
            # Record attribute information for each name used on the
paul@71 658
            # accessor.
paul@71 659
paul@791 660
            attrname = location.get_attrname()
paul@71 661
paul@843 662
            self.reference_all_attrs[location] = all_accessed_attrs = set()
paul@843 663
            self.reference_all_providers[location] = all_providers = set()
paul@687 664
            self.reference_all_provider_kinds[location] = all_provider_kinds = set()
paul@71 665
paul@71 666
            # Obtain provider and attribute details for this kind of
paul@71 667
            # object.
paul@71 668
paul@71 669
            for attrtype, object_type, attr in referenced_attrs:
paul@843 670
                all_accessed_attrs.add(attr)
paul@843 671
                all_providers.add(object_type)
paul@687 672
                all_provider_kinds.add(attrtype)
paul@687 673
paul@687 674
            # Obtain reference and provider information as sets for the
paul@687 675
            # operations below, retaining the list forms for use with
paul@687 676
            # instruction plan preparation.
paul@687 677
paul@71 678
            all_general_providers = self.get_most_general_types(all_providers)
paul@71 679
paul@71 680
            # Determine which attributes would be provided by the
paul@71 681
            # accessor types upheld by a guard.
paul@71 682
paul@71 683
            if guarded:
paul@71 684
                guard_attrs = set()
paul@555 685
paul@71 686
                for _attrtype, object_type, attr in \
paul@555 687
                    self._identify_reference_attribute(location, attrname, guard_class_types, guard_instance_types, guard_module_types):
paul@555 688
paul@71 689
                    guard_attrs.add(attr)
paul@71 690
            else:
paul@71 691
                guard_attrs = None
paul@71 692
paul@71 693
            # Constrained accesses guarantee the nature of the accessor.
paul@71 694
            # However, there may still be many types involved.
paul@71 695
paul@71 696
            if constrained:
paul@71 697
                if single_accessor_type:
paul@237 698
                    self.reference_test_types[location] = ("constrained", "specific", test_label_for_type(first(all_accessor_types)))
paul@71 699
                elif single_accessor_class_type:
paul@237 700
                    self.reference_test_types[location] = ("constrained", "specific", "object")
paul@71 701
                elif single_accessor_general_type:
paul@237 702
                    self.reference_test_types[location] = ("constrained", "common", test_label_for_type(first(all_accessor_general_types)))
paul@71 703
                elif single_accessor_general_class_type:
paul@237 704
                    self.reference_test_types[location] = ("constrained", "common", "object")
paul@44 705
                else:
paul@237 706
                    self.reference_test_types[location] = ("constrained", "many")
paul@71 707
paul@71 708
            # Suitably guarded accesses, where the nature of the
paul@71 709
            # accessor can be guaranteed, do not require the attribute
paul@71 710
            # involved to be validated. Otherwise, for unguarded
paul@71 711
            # accesses, access-level tests are required.
paul@71 712
paul@71 713
            elif guarded and all_accessed_attrs.issubset(guard_attrs):
paul@71 714
                if single_accessor_type:
paul@237 715
                    self.reference_test_types[location] = ("guarded", "specific", test_label_for_type(first(all_accessor_types)))
paul@71 716
                elif single_accessor_class_type:
paul@237 717
                    self.reference_test_types[location] = ("guarded", "specific", "object")
paul@71 718
                elif single_accessor_general_type:
paul@237 719
                    self.reference_test_types[location] = ("guarded", "common", test_label_for_type(first(all_accessor_general_types)))
paul@71 720
                elif single_accessor_general_class_type:
paul@237 721
                    self.reference_test_types[location] = ("guarded", "common", "object")
paul@71 722
paul@71 723
            # Record the need to test the type of anonymous and
paul@71 724
            # unconstrained accessors.
paul@71 725
paul@71 726
            elif len(all_providers) == 1:
paul@71 727
                provider = first(all_providers)
paul@654 728
                if provider != self.root_class_type:
paul@71 729
                    all_accessor_kinds = set(get_kinds(all_accessor_types))
paul@71 730
                    if len(all_accessor_kinds) == 1:
paul@385 731
                        test_type = ("test", "specific", test_label_for_kind(first(all_accessor_kinds)))
paul@70 732
                    else:
paul@237 733
                        test_type = ("test", "specific", "object")
paul@71 734
                    self.reference_test_types[location] = test_type
paul@77 735
                    self.reference_test_accessor_type[location] = provider
paul@71 736
paul@71 737
            elif len(all_general_providers) == 1:
paul@71 738
                provider = first(all_general_providers)
paul@654 739
                if provider != self.root_class_type:
paul@71 740
                    all_accessor_kinds = set(get_kinds(all_accessor_general_types))
paul@71 741
                    if len(all_accessor_kinds) == 1:
paul@385 742
                        test_type = ("test", "common", test_label_for_kind(first(all_accessor_kinds)))
paul@71 743
                    else:
paul@237 744
                        test_type = ("test", "common", "object")
paul@71 745
                    self.reference_test_types[location] = test_type
paul@77 746
                    self.reference_test_accessor_type[location] = provider
paul@71 747
paul@71 748
            # Record the need to test the identity of the attribute.
paul@71 749
paul@71 750
            else:
paul@237 751
                self.reference_test_types[location] = ("validate",)
paul@44 752
paul@67 753
    def initialise_access_plans(self):
paul@67 754
paul@67 755
        "Define attribute access plans."
paul@67 756
paul@67 757
        for location in self.referenced_attrs.keys():
paul@76 758
            original_location = self.const_accesses_rev.get(location)
paul@76 759
            self.access_plans[original_location or location] = self.get_access_plan(location)
paul@67 760
paul@411 761
    def identify_dependencies(self):
paul@411 762
paul@411 763
        "Introduce more module dependencies to the importer."
paul@411 764
paul@411 765
        for location, referenced_attrs in self.referenced_attrs.items():
paul@411 766
paul@418 767
            # Identify references providing dependencies.
paul@411 768
paul@411 769
            for attrtype, objtype, attr in referenced_attrs:
paul@791 770
                self.importer.add_dependency(location.path, attr.get_origin())
paul@411 771
paul@44 772
    def get_referenced_attrs(self, location):
paul@44 773
paul@44 774
        """
paul@44 775
        Return attributes referenced at the given access 'location' by the given
paul@44 776
        'attrname' as a list of (attribute type, attribute set) tuples.
paul@44 777
        """
paul@44 778
paul@69 779
        d = {}
paul@69 780
        for attrtype, objtype, attr in self.referenced_attrs[location]:
paul@69 781
            init_item(d, attrtype, set)
paul@246 782
            d[attrtype].add(attr.unaliased())
paul@69 783
        l = d.items()
paul@69 784
        l.sort() # class, module, instance
paul@44 785
        return l
paul@44 786
paul@44 787
    # Initialisation methods.
paul@44 788
paul@44 789
    def init_descendants(self):
paul@44 790
paul@44 791
        "Identify descendants of each class."
paul@44 792
paul@44 793
        for name in self.importer.classes.keys():
paul@44 794
            self.get_descendants_for_class(name)
paul@44 795
paul@44 796
    def get_descendants_for_class(self, name):
paul@44 797
paul@44 798
        """
paul@44 799
        Use subclass information to deduce the descendants for the class of the
paul@44 800
        given 'name'.
paul@44 801
        """
paul@44 802
paul@44 803
        if not self.descendants.has_key(name):
paul@44 804
            descendants = set()
paul@44 805
paul@44 806
            for subclass in self.importer.subclasses[name]:
paul@44 807
                descendants.update(self.get_descendants_for_class(subclass))
paul@44 808
                descendants.add(subclass)
paul@44 809
paul@44 810
            self.descendants[name] = descendants
paul@44 811
paul@44 812
        return self.descendants[name]
paul@44 813
paul@44 814
    def init_special_attributes(self):
paul@44 815
paul@44 816
        "Add special attributes to the classes for inheritance-related tests."
paul@44 817
paul@44 818
        all_class_attrs = self.importer.all_class_attrs
paul@44 819
paul@44 820
        for name, descendants in self.descendants.items():
paul@44 821
            for descendant in descendants:
paul@44 822
                all_class_attrs[descendant]["#%s" % name] = name
paul@44 823
paul@44 824
        for name in all_class_attrs.keys():
paul@44 825
            all_class_attrs[name]["#%s" % name] = name
paul@44 826
paul@44 827
    def init_usage_index(self):
paul@44 828
paul@44 829
        """
paul@44 830
        Create indexes for module and function attribute usage and for anonymous
paul@44 831
        accesses.
paul@44 832
        """
paul@44 833
paul@44 834
        for module in self.importer.get_modules():
paul@44 835
            for path, assignments in module.attr_usage.items():
paul@44 836
                self.add_usage(assignments, path)
paul@44 837
paul@791 838
        for path, all_attrnames in self.importer.all_attr_accesses.items():
paul@44 839
            for attrnames in all_attrnames:
paul@44 840
                attrname = get_attrnames(attrnames)[-1]
paul@791 841
                access_location = AccessLocation(path, None, attrnames, 0)
paul@107 842
                self.add_usage_term(access_location, ((attrname, False, False),))
paul@44 843
paul@44 844
    def add_usage(self, assignments, path):
paul@44 845
paul@44 846
        """
paul@44 847
        Collect usage from the given 'assignments', adding 'path' details to
paul@44 848
        each record if specified. Add the usage to an index mapping to location
paul@44 849
        information, as well as to an index mapping locations to usages.
paul@44 850
        """
paul@44 851
paul@44 852
        for name, versions in assignments.items():
paul@44 853
            for i, usages in enumerate(versions):
paul@791 854
                location = Location(path, name, None, i)
paul@44 855
paul@88 856
                for usage in usages:
paul@88 857
                    self.add_usage_term(location, usage)
paul@88 858
paul@88 859
    def add_usage_term(self, location, usage):
paul@44 860
paul@44 861
        """
paul@88 862
        For 'location' and using 'usage' as a description of usage, record
paul@44 863
        in the usage index a mapping from the usage to 'location', and record in
paul@44 864
        the location index a mapping from 'location' to the usage.
paul@44 865
        """
paul@44 866
paul@44 867
        init_item(self.location_index, location, set)
paul@88 868
        self.location_index[location].add(usage)
paul@44 869
paul@44 870
    def init_accessors(self):
paul@44 871
paul@44 872
        "Create indexes for module and function accessor information."
paul@44 873
paul@44 874
        for module in self.importer.get_modules():
paul@44 875
            for path, all_accesses in module.attr_accessors.items():
paul@44 876
                self.add_accessors(all_accesses, path)
paul@44 877
paul@44 878
    def add_accessors(self, all_accesses, path):
paul@44 879
paul@44 880
        """
paul@44 881
        For attribute accesses described by the mapping of 'all_accesses' from
paul@44 882
        name details to accessor details, record the locations of the accessors
paul@44 883
        for each access.
paul@44 884
        """
paul@44 885
paul@44 886
        # Get details for each access combining the given name and attribute.
paul@44 887
paul@44 888
        for (name, attrnames), accesses in all_accesses.items():
paul@44 889
paul@44 890
            # Obtain the usage details using the access information.
paul@44 891
paul@44 892
            for access_number, versions in enumerate(accesses):
paul@791 893
                access_location = AccessLocation(path, name, attrnames, access_number)
paul@44 894
                locations = []
paul@44 895
paul@44 896
                for version in versions:
paul@791 897
                    location = Location(path, name, None, version)
paul@44 898
                    locations.append(location)
paul@44 899
paul@742 900
                    # Map accessors to affected accesses.
paul@742 901
paul@742 902
                    l = init_item(self.access_index_rev, location, set)
paul@742 903
                    l.add(access_location)
paul@742 904
paul@742 905
                # Map accesses to supplying accessors.
paul@742 906
paul@44 907
                self.access_index[access_location] = locations
paul@44 908
paul@44 909
    def get_accessors_for_access(self, access_location):
paul@44 910
paul@44 911
        "Find a definition providing accessor details, if necessary."
paul@44 912
paul@44 913
        try:
paul@44 914
            return self.access_index[access_location]
paul@44 915
        except KeyError:
paul@44 916
            return [access_location]
paul@44 917
paul@44 918
    def init_accesses(self):
paul@44 919
paul@44 920
        """
paul@501 921
        Check that attributes used in accesses are actually defined on some
paul@501 922
        object. This can be overlooked if unknown attributes are employed in
paul@501 923
        attribute chains.
paul@501 924
paul@44 925
        Initialise collections for accesses involving assignments.
paul@44 926
        """
paul@44 927
paul@44 928
        # For each scope, obtain access details.
paul@44 929
paul@44 930
        for path, all_accesses in self.importer.all_attr_access_modifiers.items():
paul@44 931
paul@44 932
            # For each combination of name and attribute names, obtain
paul@44 933
            # applicable modifiers.
paul@44 934
paul@112 935
            for (name, attrname_str), modifiers in all_accesses.items():
paul@44 936
paul@44 937
                # For each access, determine the name versions affected by
paul@44 938
                # assignments.
paul@44 939
paul@117 940
                for access_number, (assignment, invocation) in enumerate(modifiers):
paul@112 941
paul@44 942
                    if name:
paul@791 943
                        access_location = AccessLocation(path, name, attrname_str, access_number)
paul@44 944
                    else:
paul@791 945
                        access_location = AccessLocation(path, None, attrname_str, 0)
paul@112 946
paul@501 947
                    # Plain name accesses do not employ attributes and are
paul@717 948
                    # ignored. Whether they are invoked is of interest, however.
paul@501 949
paul@502 950
                    if not attrname_str:
paul@717 951
                        if invocation:
paul@717 952
                            self.reference_invocations[access_location] = invocation
paul@501 953
                        continue
paul@501 954
paul@501 955
                    attrnames = get_attrnames(attrname_str)
paul@501 956
paul@501 957
                    # Check the attribute names.
paul@501 958
paul@501 959
                    for attrname in attrnames:
paul@501 960
                        if not attrname in self.all_attrnames:
paul@501 961
                            raise DeduceError("In %s, attribute %s is not defined in the program." % (path, attrname))
paul@501 962
paul@501 963
                    # Now only process assignments and invocations.
paul@501 964
paul@117 965
                    if invocation:
paul@553 966
                        self.reference_invocations[access_location] = invocation
paul@117 967
                        continue
paul@501 968
                    elif not assignment:
paul@501 969
                        continue
paul@501 970
paul@501 971
                    # Associate assignments with usage.
paul@117 972
paul@112 973
                    self.reference_assignments.add(access_location)
paul@71 974
paul@112 975
                    # Assignment occurs for the only attribute.
paul@112 976
paul@112 977
                    if len(attrnames) == 1:
paul@112 978
                        accessor_locations = self.get_accessors_for_access(access_location)
paul@112 979
paul@112 980
                        for location in accessor_locations:
paul@112 981
                            for usage in self.location_index[location]:
paul@88 982
                                init_item(self.assigned_attrs, usage, set)
paul@112 983
                                self.assigned_attrs[usage].add((path, name, attrnames[0]))
paul@112 984
paul@112 985
                    # Assignment occurs for the final attribute.
paul@112 986
paul@112 987
                    else:
paul@112 988
                        usage = ((attrnames[-1], False, False),)
paul@112 989
                        init_item(self.assigned_attrs, usage, set)
paul@112 990
                        self.assigned_attrs[usage].add((path, name, attrnames[-1]))
paul@44 991
paul@44 992
    def init_aliases(self):
paul@44 993
paul@44 994
        "Expand aliases so that alias-based accesses can be resolved."
paul@44 995
paul@44 996
        # Get aliased names with details of their accesses.
paul@44 997
paul@681 998
        for (path, name), all_aliases in self.importer.all_aliased_names.items():
paul@44 999
paul@742 1000
            # For each version of the name, obtain the access locations.
paul@742 1001
paul@742 1002
            for version, aliases in all_aliases.items():
paul@742 1003
                for (original_path, original_name, attrnames, access_number) in aliases:
paul@791 1004
                    accessor_location = Location(path, name, None, version)
paul@791 1005
                    access_location = AccessLocation(original_path, original_name, attrnames, access_number)
paul@742 1006
                    init_item(self.alias_index, accessor_location, list)
paul@742 1007
                    self.alias_index[accessor_location].append(access_location)
paul@44 1008
paul@791 1009
        # Get initialised name information for accessors and accesses.
paul@791 1010
paul@791 1011
        for (path, name), versions in self.importer.all_initialised_names.items():
paul@791 1012
            for version, ref in versions.items():
paul@791 1013
                location = Location(path, name, None, version)
paul@791 1014
paul@791 1015
                self.initialised_names[location] = ref
paul@791 1016
paul@791 1017
                access_locations = self.access_index_rev.get(location)
paul@791 1018
                if access_locations:
paul@791 1019
                    for access_location in access_locations:
paul@791 1020
                        init_item(self.initialised_accesses, access_location, set)
paul@791 1021
                        self.initialised_accesses[access_location].add(ref)
paul@44 1022
paul@742 1023
        # Get a mapping from accesses to affected aliases.
paul@735 1024
paul@735 1025
        for accessor_location, access_locations in self.alias_index.items():
paul@735 1026
            for access_location in access_locations:
paul@735 1027
                init_item(self.alias_index_rev, access_location, set)
paul@735 1028
                self.alias_index_rev[access_location].add(accessor_location)
paul@735 1029
paul@44 1030
    # Attribute mutation for types.
paul@44 1031
paul@44 1032
    def modify_mutated_attributes(self):
paul@44 1033
paul@44 1034
        "Identify known, mutated attributes and change their state."
paul@44 1035
paul@44 1036
        # Usage-based accesses.
paul@44 1037
paul@44 1038
        for usage, all_attrnames in self.assigned_attrs.items():
paul@44 1039
            if not usage:
paul@44 1040
                continue
paul@44 1041
paul@112 1042
            for path, name, attrname in all_attrnames:
paul@44 1043
                class_types = self.get_class_types_for_usage(usage)
paul@44 1044
                only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)
paul@44 1045
                module_types = self.get_module_types_for_usage(usage)
paul@44 1046
paul@44 1047
                # Detect self usage within methods in order to narrow the scope
paul@44 1048
                # of the mutation.
paul@44 1049
paul@44 1050
                t = name == "self" and self.constrain_self_reference(path, class_types, only_instance_types)
paul@44 1051
                if t:
paul@44 1052
                    class_types, only_instance_types, module_types, constrained = t
paul@44 1053
                objects = set(class_types).union(only_instance_types).union(module_types)
paul@44 1054
paul@112 1055
                self.mutate_attribute(objects, attrname)
paul@112 1056
paul@112 1057
    def mutate_attribute(self, objects, attrname):
paul@112 1058
paul@112 1059
        "Mutate static 'objects' with the given 'attrname'."
paul@44 1060
paul@44 1061
        for name in objects:
paul@112 1062
            attr = "%s.%s" % (name, attrname)
paul@44 1063
            value = self.importer.get_object(attr)
paul@44 1064
paul@44 1065
            # If the value is None, the attribute is
paul@44 1066
            # inherited and need not be set explicitly on
paul@44 1067
            # the class concerned.
paul@44 1068
paul@44 1069
            if value:
paul@44 1070
                self.modified_attributes[attr] = value
paul@44 1071
                self.importer.set_object(attr, value.as_var())
paul@44 1072
paul@44 1073
    # Simplification of types.
paul@44 1074
paul@69 1075
    def get_most_general_types(self, types):
paul@69 1076
paul@69 1077
        "Return the most general types for the given 'types'."
paul@69 1078
paul@69 1079
        module_types = set()
paul@69 1080
        class_types = set()
paul@69 1081
paul@69 1082
        for type in types:
paul@69 1083
            ref = self.importer.identify(type)
paul@69 1084
            if ref.has_kind("<module>"):
paul@69 1085
                module_types.add(type)
paul@69 1086
            else:
paul@69 1087
                class_types.add(type)
paul@69 1088
paul@69 1089
        types = set(self.get_most_general_module_types(module_types))
paul@69 1090
        types.update(self.get_most_general_class_types(class_types))
paul@69 1091
        return types
paul@69 1092
paul@69 1093
    def get_most_general_class_types(self, class_types):
paul@44 1094
paul@44 1095
        "Return the most general types for the given 'class_types'."
paul@44 1096
paul@44 1097
        class_types = set(class_types)
paul@44 1098
        to_remove = set()
paul@44 1099
paul@44 1100
        for class_type in class_types:
paul@44 1101
            for base in self.importer.classes[class_type]:
paul@44 1102
                base = base.get_origin()
paul@44 1103
                descendants = self.descendants[base]
paul@44 1104
                if base in class_types and descendants.issubset(class_types):
paul@44 1105
                    to_remove.update(descendants)
paul@44 1106
paul@44 1107
        class_types.difference_update(to_remove)
paul@44 1108
        return class_types
paul@44 1109
paul@44 1110
    def get_most_general_module_types(self, module_types):
paul@44 1111
paul@44 1112
        "Return the most general type for the given 'module_types'."
paul@44 1113
paul@44 1114
        # Where all modules are provided, an object would provide the same
paul@44 1115
        # attributes.
paul@44 1116
paul@44 1117
        if len(module_types) == len(self.importer.modules):
paul@654 1118
            return [self.root_class_type]
paul@44 1119
        else:
paul@44 1120
            return module_types
paul@44 1121
paul@44 1122
    # More efficient usage-to-type indexing and retrieval.
paul@44 1123
paul@44 1124
    def init_attr_type_indexes(self):
paul@44 1125
paul@44 1126
        "Identify the types that can support each attribute name."
paul@44 1127
paul@44 1128
        self._init_attr_type_index(self.attr_class_types, self.importer.all_class_attrs)
paul@107 1129
        self._init_attr_type_index(self.attr_instance_types, self.importer.all_instance_attrs, True)
paul@107 1130
        self._init_attr_type_index(self.attr_instance_types, self.importer.all_combined_attrs, False)
paul@44 1131
        self._init_attr_type_index(self.attr_module_types, self.importer.all_module_attrs)
paul@44 1132
paul@107 1133
    def _init_attr_type_index(self, attr_types, attrs, assignment=None):
paul@44 1134
paul@44 1135
        """
paul@44 1136
        Initialise the 'attr_types' attribute-to-types mapping using the given
paul@44 1137
        'attrs' type-to-attributes mapping.
paul@44 1138
        """
paul@44 1139
paul@44 1140
        for name, attrnames in attrs.items():
paul@44 1141
            for attrname in attrnames:
paul@107 1142
paul@107 1143
                # Permit general access for certain kinds of object.
paul@107 1144
paul@107 1145
                if assignment is None:
paul@107 1146
                    init_item(attr_types, (attrname, False), set)
paul@107 1147
                    init_item(attr_types, (attrname, True), set)
paul@107 1148
                    attr_types[(attrname, False)].add(name)
paul@107 1149
                    attr_types[(attrname, True)].add(name)
paul@107 1150
paul@107 1151
                # Restrict attribute assignment for instances.
paul@107 1152
paul@107 1153
                else:
paul@107 1154
                    init_item(attr_types, (attrname, assignment), set)
paul@107 1155
                    attr_types[(attrname, assignment)].add(name)
paul@44 1156
paul@88 1157
    def get_class_types_for_usage(self, usage):
paul@88 1158
paul@88 1159
        "Return names of classes supporting the given 'usage'."
paul@88 1160
paul@88 1161
        return self._get_types_for_usage(usage, self.attr_class_types, self.importer.all_class_attrs)
paul@88 1162
paul@88 1163
    def get_instance_types_for_usage(self, usage):
paul@44 1164
paul@44 1165
        """
paul@88 1166
        Return names of classes whose instances support the given 'usage'
paul@44 1167
        (as either class or instance attributes).
paul@44 1168
        """
paul@44 1169
paul@88 1170
        return self._get_types_for_usage(usage, self.attr_instance_types, self.importer.all_combined_attrs)
paul@88 1171
paul@88 1172
    def get_module_types_for_usage(self, usage):
paul@88 1173
paul@88 1174
        "Return names of modules supporting the given 'usage'."
paul@88 1175
paul@88 1176
        return self._get_types_for_usage(usage, self.attr_module_types, self.importer.all_module_attrs)
paul@88 1177
paul@88 1178
    def _get_types_for_usage(self, usage, attr_types, attrs):
paul@44 1179
paul@44 1180
        """
paul@88 1181
        For the given 'usage' representing attribute usage, return types
paul@44 1182
        recorded in the 'attr_types' attribute-to-types mapping that support
paul@44 1183
        such usage, with the given 'attrs' type-to-attributes mapping used to
paul@44 1184
        quickly assess whether a type supports all of the stated attributes.
paul@44 1185
        """
paul@44 1186
paul@44 1187
        # Where no attributes are used, any type would be acceptable.
paul@44 1188
paul@88 1189
        if not usage:
paul@44 1190
            return attrs.keys()
paul@44 1191
paul@107 1192
        keys = []
paul@107 1193
        for attrname, invocation, assignment in usage:
paul@107 1194
            keys.append((attrname, assignment))
paul@107 1195
paul@107 1196
        # Obtain types supporting the first (attribute name, assignment) key...
paul@107 1197
paul@107 1198
        types = set(attr_types.get(keys[0]) or [])
paul@107 1199
paul@107 1200
        for key in keys[1:]:
paul@107 1201
            
paul@44 1202
            # Record types that support all of the other attributes as well.
paul@44 1203
paul@107 1204
            types.intersection_update(attr_types.get(key) or [])
paul@44 1205
paul@44 1206
        return types
paul@44 1207
paul@501 1208
    def init_combined_attribute_index(self):
paul@501 1209
paul@501 1210
        "Initialise a combined index for the detection of invalid attributes."
paul@501 1211
paul@501 1212
        self.all_attrnames = set()
paul@501 1213
        for attrs in (self.importer.all_combined_attrs, self.importer.all_module_attrs):
paul@501 1214
            for name, attrnames in attrs.items():
paul@501 1215
                self.all_attrnames.update(attrnames)
paul@501 1216
paul@44 1217
    # Reference identification.
paul@44 1218
paul@44 1219
    def identify_references(self):
paul@44 1220
paul@44 1221
        "Identify references using usage and name reference information."
paul@44 1222
paul@44 1223
        # Names with associated attribute usage.
paul@44 1224
paul@44 1225
        for location, usages in self.location_index.items():
paul@44 1226
paul@44 1227
            # Obtain attribute usage associated with a name, deducing the nature
paul@44 1228
            # of the name. Obtain types only for branches involving attribute
paul@44 1229
            # usage. (In the absence of usage, any type could be involved, but
paul@44 1230
            # then no accesses exist to require knowledge of the type.)
paul@44 1231
paul@44 1232
            have_usage = False
paul@44 1233
            have_no_usage_branch = False
paul@44 1234
paul@44 1235
            for usage in usages:
paul@44 1236
                if not usage:
paul@44 1237
                    have_no_usage_branch = True
paul@44 1238
                    continue
paul@44 1239
                elif not have_usage:
paul@44 1240
                    self.init_definition_details(location)
paul@44 1241
                    have_usage = True
paul@44 1242
                self.record_types_for_usage(location, usage)
paul@44 1243
paul@44 1244
            # Where some usage occurs, but where branches without usage also
paul@44 1245
            # occur, record the types for those branches anyway.
paul@44 1246
paul@44 1247
            if have_usage and have_no_usage_branch:
paul@44 1248
                self.init_definition_details(location)
paul@44 1249
                self.record_types_for_usage(location, None)
paul@44 1250
paul@44 1251
        # Specific name-based attribute accesses.
paul@44 1252
paul@44 1253
        for access_location, accessor_locations in self.access_index.items():
paul@742 1254
            self.record_types_for_access(access_location, accessor_locations)
paul@44 1255
paul@44 1256
        # Anonymous references with attribute chains.
paul@44 1257
paul@791 1258
        for path, accesses in self.importer.all_attr_accesses.items():
paul@44 1259
paul@44 1260
            # Get distinct attribute names.
paul@44 1261
paul@44 1262
            all_attrnames = set()
paul@44 1263
paul@44 1264
            for attrnames in accesses:
paul@44 1265
                all_attrnames.update(get_attrnames(attrnames))
paul@44 1266
paul@44 1267
            # Get attribute and accessor details for each attribute name.
paul@44 1268
paul@44 1269
            for attrname in all_attrnames:
paul@791 1270
                access_location = AccessLocation(path, None, attrname, 0)
paul@44 1271
                self.record_types_for_attribute(access_location, attrname)
paul@44 1272
paul@44 1273
        # References via constant/identified objects.
paul@44 1274
paul@791 1275
        for path, name_accesses in self.importer.all_const_accesses.items():
paul@44 1276
paul@44 1277
            # A mapping from the original name and attributes to resolved access
paul@44 1278
            # details.
paul@44 1279
paul@44 1280
            for original_access, access in name_accesses.items():
paul@44 1281
                original_name, original_attrnames = original_access
paul@44 1282
                objpath, ref, attrnames = access
paul@44 1283
paul@44 1284
                # Build an accessor combining the name and attribute names used.
paul@44 1285
paul@44 1286
                original_accessor = tuple([original_name] + original_attrnames.split("."))
paul@44 1287
paul@44 1288
                # Direct accesses to attributes.
paul@44 1289
paul@44 1290
                if not attrnames:
paul@44 1291
paul@44 1292
                    # Build a descriptive location based on the original
paul@44 1293
                    # details, exposing the final attribute name.
paul@44 1294
paul@44 1295
                    oa, attrname = original_accessor[:-1], original_accessor[-1]
paul@44 1296
                    oa = ".".join(oa)
paul@44 1297
paul@791 1298
                    access_location = AccessLocation(path, oa, attrname, 0)
paul@791 1299
                    accessor_location = Location(path, oa, None, 0)
paul@44 1300
                    self.access_index[access_location] = [accessor_location]
paul@44 1301
paul@44 1302
                    self.init_access_details(access_location)
paul@44 1303
                    self.init_definition_details(accessor_location)
paul@44 1304
paul@44 1305
                    # Obtain a reference for the accessor in order to properly
paul@44 1306
                    # determine its type.
paul@44 1307
paul@44 1308
                    if ref.get_kind() != "<instance>":
paul@44 1309
                        objpath = ref.get_origin()
paul@44 1310
paul@44 1311
                    objpath = objpath.rsplit(".", 1)[0]
paul@44 1312
paul@44 1313
                    # Where the object name conflicts with the module
paul@44 1314
                    # providing it, obtain the module details.
paul@44 1315
paul@44 1316
                    if objpath in self.importer.modules:
paul@44 1317
                        accessor = Reference("<module>", objpath)
paul@44 1318
                    else:
paul@44 1319
                        accessor = self.importer.get_object(objpath)
paul@44 1320
paul@44 1321
                    self.referenced_attrs[access_location] = [(accessor.get_kind(), accessor.get_origin(), ref)]
paul@44 1322
                    self.access_constrained.add(access_location)
paul@44 1323
paul@57 1324
                    class_types, instance_types, module_types = accessor.get_types()
paul@44 1325
                    self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True)
paul@64 1326
paul@64 1327
                else:
paul@44 1328
paul@64 1329
                    # Build a descriptive location based on the original
paul@64 1330
                    # details, employing the first remaining attribute name.
paul@64 1331
paul@64 1332
                    l = get_attrnames(attrnames)
paul@64 1333
                    attrname = l[0]
paul@44 1334
paul@64 1335
                    oa = original_accessor[:-len(l)]
paul@64 1336
                    oa = ".".join(oa)
paul@44 1337
paul@791 1338
                    access_location = AccessLocation(path, oa, attrnames, 0)
paul@791 1339
                    accessor_location = Location(path, oa, None, 0)
paul@64 1340
                    self.access_index[access_location] = [accessor_location]
paul@64 1341
paul@64 1342
                    self.init_access_details(access_location)
paul@64 1343
                    self.init_definition_details(accessor_location)
paul@44 1344
paul@64 1345
                    class_types, instance_types, module_types = ref.get_types()
paul@64 1346
paul@64 1347
                    self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, True)
paul@64 1348
                    self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True)
paul@64 1349
paul@679 1350
                # Define mappings between the original and access locations
paul@679 1351
                # so that translation can work from the source details.
paul@679 1352
paul@791 1353
                original_location = AccessLocation(path, original_name, original_attrnames, 0)
paul@64 1354
paul@64 1355
                if original_location != access_location:
paul@64 1356
                    self.const_accesses[original_location] = access_location
paul@67 1357
                    self.const_accesses_rev[access_location] = original_location
paul@44 1358
paul@735 1359
        # Propagate alias-related information.
paul@735 1360
paul@735 1361
        affected_aliases = set(self.alias_index.keys())
paul@735 1362
paul@735 1363
        while True:
paul@735 1364
paul@735 1365
            # Aliased name definitions. All aliases with usage will have been
paul@735 1366
            # defined, but they may be refined according to referenced accesses.
paul@735 1367
paul@735 1368
            updated_aliases = set()
paul@735 1369
paul@735 1370
            for location in affected_aliases:
paul@735 1371
                if self.record_types_for_alias(location):
paul@735 1372
                    updated_aliases.add(location)
paul@735 1373
paul@742 1374
            # Define accesses employing aliases.
paul@742 1375
paul@742 1376
            alias_accesses = set()
paul@742 1377
            affected_aliases = set()
paul@742 1378
paul@742 1379
            for alias in updated_aliases:
paul@742 1380
paul@742 1381
                # Access affected by the alias.
paul@742 1382
paul@742 1383
                if self.access_index_rev.has_key(alias):
paul@742 1384
                    alias_accesses.update(self.access_index_rev[alias])
paul@742 1385
paul@742 1386
                # Another alias affected by the alias.
paul@742 1387
paul@742 1388
                elif self.alias_index_rev.has_key(alias):
paul@742 1389
                    affected_aliases.update(self.alias_index_rev[alias])
paul@742 1390
paul@735 1391
            # Update accesses employing aliases.
paul@735 1392
paul@735 1393
            updated_accesses = set()
paul@735 1394
paul@735 1395
            for access_location in alias_accesses:
paul@735 1396
                if self.record_types_for_access(access_location, self.access_index[access_location]):
paul@735 1397
                    updated_accesses.add(access_location)
paul@735 1398
paul@742 1399
            # Determine which aliases are affected by the updated accesses.
paul@735 1400
paul@735 1401
            for access_location in updated_accesses:
paul@735 1402
                if self.alias_index_rev.has_key(access_location):
paul@735 1403
                    affected_aliases.update(self.alias_index_rev[access_location])
paul@735 1404
paul@735 1405
            if not affected_aliases:
paul@735 1406
                break
paul@44 1407
paul@44 1408
    def constrain_types(self, path, class_types, instance_types, module_types):
paul@44 1409
paul@44 1410
        """
paul@44 1411
        Using the given 'path' to an object, constrain the given 'class_types',
paul@44 1412
        'instance_types' and 'module_types'.
paul@44 1413
paul@44 1414
        Return the class, instance, module types plus whether the types are
paul@44 1415
        constrained to a specific kind of type.
paul@44 1416
        """
paul@44 1417
paul@44 1418
        ref = self.importer.identify(path)
paul@44 1419
        if ref:
paul@44 1420
paul@44 1421
            # Constrain usage suggestions using the identified object.
paul@44 1422
paul@44 1423
            if ref.has_kind("<class>"):
paul@44 1424
                return (
paul@44 1425
                    set(class_types).intersection([ref.get_origin()]), [], [], True
paul@44 1426
                    )
paul@44 1427
            elif ref.has_kind("<module>"):
paul@44 1428
                return (
paul@44 1429
                    [], [], set(module_types).intersection([ref.get_origin()]), True
paul@44 1430
                    )
paul@44 1431
paul@44 1432
        return class_types, instance_types, module_types, False
paul@44 1433
paul@44 1434
    def get_target_types(self, location, usage):
paul@44 1435
paul@44 1436
        """
paul@44 1437
        Return the class, instance and module types constrained for the name at
paul@44 1438
        the given 'location' exhibiting the given 'usage'. Whether the types
paul@44 1439
        have been constrained using contextual information is also indicated,
paul@44 1440
        plus whether the types have been constrained to a specific kind of type.
paul@44 1441
        """
paul@44 1442
paul@107 1443
        have_assignments = get_assigned_attributes(usage)
paul@44 1444
paul@44 1445
        # Detect any initialised name for the location.
paul@44 1446
paul@791 1447
        if location.name:
paul@742 1448
            refs = self.get_initialised_name(location)
paul@742 1449
            if refs:
paul@44 1450
                (class_types, only_instance_types, module_types,
paul@742 1451
                    _function_types, _var_types) = separate_types(refs)
paul@107 1452
                return class_types, only_instance_types, module_types, True, have_assignments
paul@44 1453
paul@44 1454
        # Retrieve the recorded types for the usage.
paul@44 1455
paul@44 1456
        class_types = self.get_class_types_for_usage(usage)
paul@44 1457
        only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)
paul@44 1458
        module_types = self.get_module_types_for_usage(usage)
paul@44 1459
paul@44 1460
        # Merge usage deductions with observations to obtain reference types
paul@44 1461
        # for names involved with attribute accesses.
paul@44 1462
paul@791 1463
        if not location.name:
paul@107 1464
            return class_types, only_instance_types, module_types, False, have_assignments
paul@44 1465
paul@44 1466
        # Obtain references to known objects.
paul@44 1467
paul@791 1468
        path = get_name_path(location.path, location.name)
paul@44 1469
paul@44 1470
        class_types, only_instance_types, module_types, constrained_specific = \
paul@44 1471
            self.constrain_types(path, class_types, only_instance_types, module_types)
paul@44 1472
paul@44 1473
        if constrained_specific:
paul@107 1474
            return class_types, only_instance_types, module_types, constrained_specific, \
paul@107 1475
                constrained_specific or have_assignments
paul@44 1476
paul@44 1477
        # Constrain "self" references.
paul@44 1478
paul@816 1479
        class_name = self.in_method(location.path)
paul@816 1480
        constrained = False
paul@816 1481
paul@816 1482
        if class_name and location.name == "self":
paul@816 1483
paul@816 1484
            # Constrain the types to the class's hierarchy.
paul@816 1485
paul@816 1486
            class_types, only_instance_types, module_types, constrained = \
paul@816 1487
                self.constrain_to_class(class_name, class_types, only_instance_types)
paul@816 1488
paul@816 1489
            # Without any deduced types, produce an error.
paul@816 1490
paul@816 1491
            if not class_types and not only_instance_types:
paul@350 1492
                raise DeduceError("In %s, usage {%s} is not directly supported by class %s or its instances." %
paul@791 1493
                                  (location.path, encode_usage(usage), class_name))
paul@350 1494
paul@816 1495
            # If the class defining the method does not appear amongst the
paul@816 1496
            # types supporting the usage, remove the constrained status of the
paul@816 1497
            # name.
paul@816 1498
paul@816 1499
            constrained = constrained and (class_name in class_types or class_name in only_instance_types)
paul@816 1500
paul@816 1501
        return class_types, only_instance_types, module_types, constrained, have_assignments
paul@44 1502
paul@44 1503
    def constrain_self_reference(self, unit_path, class_types, only_instance_types):
paul@44 1504
paul@44 1505
        """
paul@44 1506
        Where the name "self" appears in a method, attempt to constrain the
paul@44 1507
        classes involved.
paul@44 1508
paul@44 1509
        Return the class, instance, module types plus whether the types are
paul@44 1510
        constrained.
paul@44 1511
        """
paul@44 1512
paul@44 1513
        class_name = self.in_method(unit_path)
paul@44 1514
paul@44 1515
        if not class_name:
paul@44 1516
            return None
paul@44 1517
paul@816 1518
        return self.constrain_to_class(class_name, class_types, only_instance_types)
paul@816 1519
paul@816 1520
    def constrain_to_class(self, class_name, class_types, only_instance_types):
paul@816 1521
paul@816 1522
        """
paul@816 1523
        Constrain to 'class_name' and its descendants, the given 'class_types'
paul@816 1524
        and 'only_instance_types'.
paul@816 1525
paul@816 1526
        Return the class, instance, module types plus whether the types are
paul@816 1527
        constrained.
paul@816 1528
        """
paul@816 1529
paul@44 1530
        classes = set([class_name])
paul@44 1531
        classes.update(self.get_descendants_for_class(class_name))
paul@44 1532
paul@44 1533
        # Note that only instances will be expected for these references but
paul@44 1534
        # either classes or instances may provide the attributes.
paul@44 1535
paul@44 1536
        return (
paul@44 1537
            set(class_types).intersection(classes),
paul@44 1538
            set(only_instance_types).intersection(classes),
paul@44 1539
            [], True
paul@44 1540
            )
paul@44 1541
paul@44 1542
    def in_method(self, path):
paul@44 1543
paul@44 1544
        "Return whether 'path' refers to a method."
paul@44 1545
paul@816 1546
        t = path.rsplit(".", 1)
paul@816 1547
        if len(t) == 1:
paul@816 1548
            return False
paul@816 1549
paul@816 1550
        class_name, method_name = t
paul@274 1551
        return class_name != "__builtins__.core.type" and self.importer.classes.has_key(class_name) and class_name
paul@44 1552
paul@44 1553
    def init_reference_details(self, location):
paul@44 1554
paul@44 1555
        "Initialise reference-related details for 'location'."
paul@44 1556
paul@44 1557
        self.init_definition_details(location)
paul@44 1558
        self.init_access_details(location)
paul@44 1559
paul@44 1560
    def init_definition_details(self, location):
paul@44 1561
paul@44 1562
        "Initialise name definition details for 'location'."
paul@44 1563
paul@44 1564
        self.accessor_class_types[location] = set()
paul@44 1565
        self.accessor_instance_types[location] = set()
paul@44 1566
        self.accessor_module_types[location] = set()
paul@44 1567
        self.provider_class_types[location] = set()
paul@44 1568
        self.provider_instance_types[location] = set()
paul@44 1569
        self.provider_module_types[location] = set()
paul@44 1570
paul@44 1571
    def init_access_details(self, location):
paul@44 1572
paul@44 1573
        "Initialise access details at 'location'."
paul@44 1574
paul@44 1575
        self.referenced_attrs[location] = {}
paul@44 1576
paul@742 1577
    def record_types_for_access(self, access_location, accessor_locations):
paul@44 1578
paul@44 1579
        """
paul@44 1580
        Define types for the 'access_location' associated with the given
paul@735 1581
        'accessor_locations'. Return whether referenced attributes were updated.
paul@44 1582
        """
paul@44 1583
paul@791 1584
        attrname = access_location.get_attrname()
paul@91 1585
        if not attrname:
paul@735 1586
            return False
paul@44 1587
paul@720 1588
        invocation = access_location in self.reference_invocations
paul@720 1589
        assignment = access_location in self.reference_assignments
paul@720 1590
paul@44 1591
        # Collect all suggested types for the accessors. Accesses may
paul@44 1592
        # require accessors from of a subset of the complete set of types.
paul@44 1593
paul@44 1594
        class_types = set()
paul@44 1595
        module_types = set()
paul@44 1596
        instance_types = set()
paul@44 1597
paul@44 1598
        constrained = True
paul@44 1599
paul@735 1600
        old_referenced_attrs = self.referenced_attrs.get(access_location)
paul@735 1601
paul@44 1602
        for location in accessor_locations:
paul@44 1603
paul@44 1604
            # Use the type information deduced for names from above.
paul@44 1605
paul@44 1606
            if self.accessor_class_types.has_key(location):
paul@44 1607
                class_types.update(self.accessor_class_types[location])
paul@44 1608
                module_types.update(self.accessor_module_types[location])
paul@44 1609
                instance_types.update(self.accessor_instance_types[location])
paul@44 1610
paul@44 1611
            # Where accesses are associated with assignments but where no
paul@44 1612
            # attribute usage observations have caused such an association,
paul@44 1613
            # the attribute name is considered by itself.
paul@44 1614
paul@44 1615
            else:
paul@44 1616
                self.init_definition_details(location)
paul@720 1617
                self.record_types_for_usage(location, [(attrname, invocation, assignment)])
paul@44 1618
paul@67 1619
            constrained = location in self.accessor_constrained and constrained
paul@44 1620
paul@44 1621
        self.init_access_details(access_location)
paul@44 1622
        self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, constrained)
paul@44 1623
paul@735 1624
        # Return whether the referenced attributes have changed.
paul@735 1625
paul@735 1626
        return old_referenced_attrs != self.referenced_attrs.get(access_location)
paul@735 1627
paul@44 1628
    def record_types_for_usage(self, accessor_location, usage):
paul@44 1629
paul@44 1630
        """
paul@44 1631
        Record types for the given 'accessor_location' according to the given
paul@44 1632
        'usage' observations which may be None to indicate an absence of usage.
paul@44 1633
        """
paul@44 1634
paul@44 1635
        (class_types,
paul@44 1636
         instance_types,
paul@44 1637
         module_types,
paul@44 1638
         constrained,
paul@44 1639
         constrained_specific) = self.get_target_types(accessor_location, usage)
paul@44 1640
paul@90 1641
        invocations = get_invoked_attributes(usage)
paul@90 1642
paul@107 1643
        self.record_reference_types(accessor_location, class_types, instance_types,
paul@107 1644
            module_types, constrained, constrained_specific, invocations)
paul@44 1645
paul@44 1646
    def record_types_for_attribute(self, access_location, attrname):
paul@44 1647
paul@44 1648
        """
paul@44 1649
        Record types for the 'access_location' employing only the given
paul@44 1650
        'attrname' for type deduction.
paul@44 1651
        """
paul@44 1652
paul@102 1653
        (class_types,
paul@102 1654
         only_instance_types,
paul@102 1655
         module_types) = self.get_types_for_attribute(attrname)
paul@102 1656
paul@102 1657
        self.init_reference_details(access_location)
paul@102 1658
paul@102 1659
        self.identify_reference_attributes(access_location, attrname, class_types, only_instance_types, module_types, False)
paul@102 1660
        self.record_reference_types(access_location, class_types, only_instance_types, module_types, False)
paul@102 1661
paul@102 1662
    def get_types_for_attribute(self, attrname):
paul@102 1663
paul@102 1664
        "Return class, instance-only and module types supporting 'attrname'."
paul@102 1665
paul@107 1666
        usage = ((attrname, False, False),)
paul@44 1667
paul@44 1668
        class_types = self.get_class_types_for_usage(usage)
paul@44 1669
        only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)
paul@44 1670
        module_types = self.get_module_types_for_usage(usage)
paul@44 1671
paul@102 1672
        return class_types, only_instance_types, module_types
paul@44 1673
paul@44 1674
    def record_types_for_alias(self, accessor_location):
paul@44 1675
paul@44 1676
        """
paul@44 1677
        Define types for the 'accessor_location' not having associated usage.
paul@735 1678
        Return whether the types were updated.
paul@44 1679
        """
paul@44 1680
paul@44 1681
        have_access = self.provider_class_types.has_key(accessor_location)
paul@44 1682
paul@44 1683
        # With an access, attempt to narrow the existing selection of provider
paul@709 1684
        # types. Invocations attempt to find return value information, with
paul@709 1685
        # instance return values also yielding class providers (since attributes
paul@709 1686
        # on instances could be provided by classes).
paul@44 1687
paul@44 1688
        if have_access:
paul@44 1689
            provider_class_types = self.provider_class_types[accessor_location]
paul@44 1690
            provider_instance_types = self.provider_instance_types[accessor_location]
paul@44 1691
            provider_module_types = self.provider_module_types[accessor_location]
paul@44 1692
paul@721 1693
            accessor_class_types = self.accessor_class_types[accessor_location]
paul@721 1694
            accessor_instance_types = self.accessor_instance_types[accessor_location]
paul@721 1695
            accessor_module_types = self.accessor_module_types[accessor_location]
paul@721 1696
paul@44 1697
            # Find details for any corresponding access.
paul@44 1698
paul@721 1699
            new_provider_class_types = set()
paul@721 1700
            new_provider_instance_types = set()
paul@721 1701
            new_provider_module_types = set()
paul@721 1702
paul@721 1703
            new_accessor_class_types = set()
paul@721 1704
            new_accessor_instance_types = set()
paul@721 1705
            new_accessor_module_types = set()
paul@44 1706
paul@742 1707
            refs = set()
paul@742 1708
paul@44 1709
            for access_location in self.alias_index[accessor_location]:
paul@791 1710
                attrnames = access_location.attrnames
paul@791 1711
                invocation = self.reference_invocations.has_key(access_location)
paul@44 1712
paul@715 1713
                attrnames = attrnames and attrnames.split(".")
paul@715 1714
                remaining = attrnames and len(attrnames) > 1
paul@715 1715
paul@715 1716
                # Alias has remaining attributes: reference details do not
paul@715 1717
                # correspond to the accessor; the remaining attributes would
paul@715 1718
                # need to be traversed first.
paul@715 1719
paul@715 1720
                if remaining:
paul@735 1721
                    return False
paul@715 1722
paul@44 1723
                # Alias references an attribute access.
paul@44 1724
paul@44 1725
                if attrnames:
paul@44 1726
paul@709 1727
                    # Obtain references and attribute types for the access.
paul@44 1728
paul@708 1729
                    attrs = self.get_references_for_access(access_location)
paul@721 1730
paul@744 1731
                    if attrs:
paul@744 1732
paul@744 1733
                        # Invocations converting class accessors to instances do
paul@744 1734
                        # not change the nature of class providers.
paul@744 1735
paul@744 1736
                        provider_attrs = self.convert_invocation_providers(attrs, invocation)
paul@744 1737
paul@744 1738
                        # Accessors are updated separately, employing invocation
paul@744 1739
                        # result details.
paul@744 1740
paul@744 1741
                        accessor_attrs = self.convert_invocations(attrs, invocation)
paul@742 1742
paul@44 1743
                # Alias references a name, not an access.
paul@44 1744
paul@44 1745
                else:
paul@742 1746
                    # Attempt to refine the types using initialised names or
paul@742 1747
                    # accessors.
paul@742 1748
paul@791 1749
                    attrs = self.get_initialised_access(access_location)
paul@742 1750
paul@742 1751
                    if attrs:
paul@721 1752
                        provider_attrs = self.convert_invocation_providers(attrs, invocation)
paul@721 1753
                        accessor_attrs = self.convert_invocations(attrs, invocation)
paul@742 1754
                    else:
paul@742 1755
                        provider_attrs = self.get_provider_references(access_location)
paul@742 1756
                        attrs = accessor_attrs = self.get_accessor_references(access_location)
paul@44 1757
paul@744 1758
                # Where no specific attributes are defined, do not attempt
paul@744 1759
                # to refine the alias's types.
paul@744 1760
paul@744 1761
                if not attrs:
paul@744 1762
                    return False
paul@744 1763
paul@744 1764
                (class_types, instance_types, module_types, function_types,
paul@744 1765
                    var_types) = separate_types(provider_attrs)
paul@744 1766
paul@744 1767
                # Where non-accessor types are found, do not attempt to refine
paul@744 1768
                # the defined accessor types.
paul@744 1769
paul@744 1770
                if function_types or var_types:
paul@744 1771
                    return False
paul@744 1772
paul@744 1773
                class_types = set(provider_class_types).intersection(class_types)
paul@744 1774
                instance_types = set(provider_instance_types).intersection(instance_types)
paul@744 1775
                module_types = set(provider_module_types).intersection(module_types)
paul@744 1776
paul@744 1777
                new_provider_class_types.update(class_types)
paul@744 1778
                new_provider_instance_types.update(instance_types)
paul@744 1779
                new_provider_module_types.update(module_types)
paul@744 1780
paul@744 1781
                (class_types, instance_types, module_types, function_types,
paul@744 1782
                    var_types) = separate_types(accessor_attrs)
paul@744 1783
paul@744 1784
                class_types = set(accessor_class_types).intersection(class_types)
paul@744 1785
                instance_types = set(accessor_instance_types).intersection(instance_types)
paul@744 1786
                module_types = set(accessor_module_types).intersection(module_types)
paul@744 1787
paul@744 1788
                new_accessor_class_types.update(class_types)
paul@744 1789
                new_accessor_instance_types.update(instance_types)
paul@744 1790
                new_accessor_module_types.update(module_types)
paul@744 1791
paul@744 1792
                refs.update(accessor_attrs)
paul@742 1793
paul@742 1794
                # Update the alias relationships for invocations.
paul@742 1795
paul@742 1796
                self.update_alias_accesses(access_location, attrs)
paul@742 1797
paul@44 1798
            # Record refined type details for the alias as an accessor.
paul@44 1799
paul@44 1800
            self.init_definition_details(accessor_location)
paul@721 1801
            self.update_provider_types(accessor_location, new_provider_class_types, new_provider_instance_types, new_provider_module_types)
paul@721 1802
            self.update_accessor_types(accessor_location, new_accessor_class_types, new_accessor_instance_types, new_accessor_module_types)
paul@44 1803
paul@742 1804
            # Record reference details for the alias separately from accessors.
paul@742 1805
paul@742 1806
            self.referenced_objects[accessor_location] = refs
paul@742 1807
paul@735 1808
            return new_accessor_class_types != accessor_class_types or \
paul@735 1809
                   new_accessor_instance_types != accessor_instance_types or \
paul@735 1810
                   new_accessor_module_types != accessor_module_types
paul@735 1811
paul@44 1812
        # Without an access, attempt to identify references for the alias.
paul@709 1813
        # Invocations convert classes to instances and also attempt to find
paul@709 1814
        # return value information.
paul@44 1815
paul@44 1816
        else:
paul@44 1817
            refs = set()
paul@44 1818
paul@44 1819
            for access_location in self.alias_index[accessor_location]:
paul@791 1820
                attrnames = access_location.attrnames
paul@791 1821
                invocation = self.reference_invocations.has_key(access_location)
paul@709 1822
paul@683 1823
                attrnames = attrnames and attrnames.split(".")
paul@683 1824
                remaining = attrnames and len(attrnames) > 1
paul@683 1825
paul@683 1826
                # Alias has remaining attributes: reference details do not
paul@683 1827
                # correspond to the accessor; the remaining attributes would
paul@683 1828
                # need to be traversed first.
paul@683 1829
paul@683 1830
                if remaining:
paul@735 1831
                    return False
paul@44 1832
paul@44 1833
                # Alias references an attribute access.
paul@44 1834
paul@721 1835
                if attrnames:
paul@709 1836
paul@709 1837
                    # Obtain references and attribute types for the access.
paul@709 1838
paul@708 1839
                    attrs = self.get_references_for_access(access_location)
paul@742 1840
paul@44 1841
                # Alias references a name, not an access.
paul@44 1842
paul@44 1843
                else:
paul@709 1844
paul@709 1845
                    # Obtain initialiser information.
paul@709 1846
paul@791 1847
                    attrs = self.get_initialised_access(access_location)
paul@742 1848
paul@742 1849
                    if attrs:
paul@742 1850
                        provider_attrs = self.convert_invocation_providers(attrs, invocation)
paul@742 1851
                        accessor_attrs = self.convert_invocations(attrs, invocation)
paul@742 1852
                    else:
paul@742 1853
                        provider_attrs = self.get_provider_references(access_location)
paul@742 1854
                        attrs = accessor_attrs = self.get_accessor_references(access_location)
paul@742 1855
paul@744 1856
                # Where no further information is found, do not attempt to
paul@744 1857
                # refine the defined accessor types.
paul@744 1858
paul@744 1859
                if not attrs:
paul@744 1860
                    return False
paul@744 1861
paul@744 1862
                refs.update(self.convert_invocations(attrs, invocation))
paul@742 1863
paul@742 1864
                # Update the alias relationships for invocations.
paul@742 1865
paul@742 1866
                self.update_alias_accesses(access_location, attrs)
paul@742 1867
paul@742 1868
            # Record refined type details for the alias as an accessor.
paul@742 1869
paul@742 1870
            (class_types, instance_types, module_types, function_types,
paul@742 1871
                var_types) = separate_types(refs)
paul@742 1872
paul@742 1873
            # Where non-accessor types are found, do not attempt to refine
paul@742 1874
            # the defined accessor types.
paul@742 1875
paul@742 1876
            if not function_types and not var_types:
paul@742 1877
                self.init_definition_details(accessor_location)
paul@742 1878
                self.update_provider_types(accessor_location, class_types + instance_types, class_types + instance_types, module_types)
paul@742 1879
                self.update_accessor_types(accessor_location, class_types, instance_types, module_types)
paul@709 1880
paul@44 1881
            # Record reference details for the alias separately from accessors.
paul@44 1882
paul@44 1883
            self.referenced_objects[accessor_location] = refs
paul@44 1884
paul@742 1885
            return True
paul@742 1886
paul@742 1887
    def update_alias_accesses(self, access_location, refs):
paul@742 1888
paul@742 1889
        """
paul@742 1890
        Record 'access_location' as a location affected by the return values of
paul@742 1891
        'refs' if an invocation is involved.
paul@742 1892
        """
paul@742 1893
paul@742 1894
        if not self.reference_invocations.has_key(access_location):
paul@742 1895
            return
paul@742 1896
paul@742 1897
        for ref in refs:
paul@742 1898
paul@742 1899
            # Initialising accesses originate from the return values.
paul@742 1900
paul@742 1901
            key = (ref.get_origin(), "$return")
paul@742 1902
            self._update_alias_accesses(access_location, key, self.importer.all_initialised_names)
paul@742 1903
            self._update_alias_accesses(access_location, key, self.importer.all_aliased_names)
paul@742 1904
paul@742 1905
    def _update_alias_accesses(self, access_location, key, names):
paul@742 1906
paul@742 1907
        """
paul@742 1908
        Make each return value provide information to the given
paul@742 1909
        'access_location', using 'key' to reference the return value and 'names'
paul@742 1910
        as the collection of definitions.
paul@742 1911
        """
paul@742 1912
paul@742 1913
        versions = names.get(key)
paul@742 1914
        if not versions:
paul@742 1915
            return
paul@742 1916
paul@791 1917
        path, name = key
paul@791 1918
paul@742 1919
        for version in versions.keys():
paul@791 1920
            location = Location(path, name, None, version)
paul@742 1921
            l = init_item(self.alias_index_rev, location, set)
paul@742 1922
            l.add(access_location)
paul@742 1923
paul@742 1924
            l = init_item(self.alias_index, access_location, set)
paul@742 1925
            l.add(location)
paul@735 1926
paul@708 1927
    def get_references_for_access(self, access_location):
paul@708 1928
paul@708 1929
        "Return the references identified for 'access_location'."
paul@708 1930
paul@843 1931
        attrs = set()
paul@708 1932
        for attrtype, object_type, attr in self.referenced_attrs[access_location]:
paul@843 1933
            attrs.add(attr)
paul@708 1934
        return attrs
paul@708 1935
paul@709 1936
    def convert_invocation_providers(self, refs, invocation):
paul@709 1937
paul@709 1938
        """
paul@709 1939
        Convert 'refs' to providers corresponding to the results of invoking
paul@709 1940
        each of the given references, if 'invocation' is set to a true value.
paul@709 1941
        """
paul@709 1942
paul@709 1943
        if not invocation:
paul@709 1944
            return refs
paul@709 1945
paul@709 1946
        providers = set()
paul@709 1947
paul@709 1948
        for ref in refs:
paul@742 1949
            invocation_providers = self.convert_accessors_to_providers(self.convert_invocation_provider(ref))
paul@742 1950
            providers.update(invocation_providers)
paul@742 1951
paul@742 1952
        return self.references_or_var(providers)
paul@742 1953
paul@742 1954
    def convert_accessors_to_providers(self, refs):
paul@742 1955
paul@742 1956
        "Convert accessor 'refs' to provider references."
paul@742 1957
paul@742 1958
        providers = set()
paul@742 1959
        for ref in refs:
paul@742 1960
            if ref.has_kind("<instance>"):
paul@742 1961
                providers.add(Reference("<class>", ref.get_origin()))
paul@742 1962
            providers.add(ref)
paul@709 1963
        return providers
paul@709 1964
paul@709 1965
    def convert_invocation_provider(self, ref):
paul@709 1966
paul@709 1967
        "Convert 'ref' to a provider appropriate to its invocation result."
paul@709 1968
paul@712 1969
        if ref:
paul@712 1970
            if ref.has_kind("<class>"):
paul@742 1971
                return [ref]
paul@712 1972
            elif ref.has_kind("<function>"):
paul@731 1973
                return self.convert_function_invocation(ref)
paul@709 1974
paul@742 1975
        return [Reference("<var>")]
paul@709 1976
paul@709 1977
    def convert_invocations(self, refs, invocation):
paul@709 1978
paul@709 1979
        """
paul@709 1980
        Convert 'refs' to invocation results if 'invocation' is set to a true
paul@709 1981
        value.
paul@709 1982
        """
paul@709 1983
paul@739 1984
        if not invocation:
paul@739 1985
            return refs
paul@739 1986
paul@739 1987
        invocation_refs = set()
paul@739 1988
paul@739 1989
        for ref in refs:
paul@739 1990
            invocation_refs.update(self.convert_invocation(ref))
paul@739 1991
paul@742 1992
        return self.references_or_var(invocation_refs)
paul@709 1993
paul@709 1994
    def convert_invocation(self, ref):
paul@709 1995
paul@709 1996
        "Convert 'ref' to its invocation result."
paul@709 1997
paul@712 1998
        if ref:
paul@712 1999
            if ref.has_kind("<class>"):
paul@739 2000
                return [ref.instance_of()]
paul@712 2001
            elif ref.has_kind("<function>"):
paul@731 2002
                return self.convert_function_invocation(ref)
paul@731 2003
paul@739 2004
        return [Reference("<var>")]
paul@731 2005
paul@731 2006
    def convert_function_invocation(self, ref):
paul@731 2007
paul@731 2008
        "Convert the function 'ref' to its return value reference."
paul@731 2009
paul@742 2010
        initialisers = self.importer.all_initialised_names.get((ref.get_origin(), "$return"))
paul@742 2011
        aliases = self.importer.all_aliased_names.get((ref.get_origin(), "$return"))
paul@742 2012
paul@742 2013
        if initialisers and not aliases:
paul@742 2014
            return set(initialisers.values())
paul@739 2015
paul@739 2016
        return [Reference("<var>")]
paul@709 2017
paul@742 2018
    def references_or_var(self, refs):
paul@742 2019
paul@742 2020
        var = Reference("<var>")
paul@742 2021
paul@742 2022
        if var in refs:
paul@742 2023
            return set([var])
paul@742 2024
        else:
paul@742 2025
            return refs
paul@742 2026
paul@791 2027
    def get_initialised_name(self, location):
paul@44 2028
paul@44 2029
        """
paul@791 2030
        Return references for any initialised names at 'location', or None if no
paul@791 2031
        such references exist.
paul@44 2032
        """
paul@44 2033
paul@791 2034
        ref = self.initialised_names.get(location)
paul@791 2035
        return ref and [ref] or None
paul@791 2036
paul@791 2037
    def get_initialised_access(self, location):
paul@791 2038
paul@791 2039
        """
paul@791 2040
        Return references for any initialised names supplying the given access
paul@791 2041
        'location', or None if no such references exist.
paul@791 2042
        """
paul@791 2043
paul@791 2044
        if location.access_number is not None:
paul@791 2045
            return self.initialised_accesses.get(location)
paul@742 2046
        else:
paul@791 2047
            return self.get_initialised_name(location)
paul@742 2048
paul@742 2049
    def get_accessor_references(self, access_location):
paul@742 2050
paul@742 2051
        """
paul@742 2052
        Return references corresponding to accessor details at the given
paul@742 2053
        'access_location'.
paul@742 2054
        """
paul@742 2055
paul@742 2056
        if self.accessor_class_types.has_key(access_location):
paul@742 2057
            class_types = self.accessor_class_types[access_location]
paul@742 2058
            instance_types = self.accessor_instance_types[access_location]
paul@742 2059
            module_types = self.accessor_module_types[access_location]
paul@742 2060
            return combine_types(class_types, instance_types, module_types)
paul@742 2061
        else:
paul@742 2062
            return None
paul@742 2063
paul@742 2064
    def get_provider_references(self, access_location):
paul@742 2065
paul@742 2066
        """
paul@742 2067
        Return references corresponding to provider details at the given
paul@742 2068
        'access_location'.
paul@742 2069
        """
paul@742 2070
paul@742 2071
        if self.provider_class_types.has_key(access_location):
paul@742 2072
            class_types = self.provider_class_types[access_location]
paul@742 2073
            instance_types = self.provider_instance_types[access_location]
paul@742 2074
            module_types = self.provider_module_types[access_location]
paul@742 2075
            return combine_types(class_types, instance_types, module_types)
paul@44 2076
        else:
paul@44 2077
            return None
paul@44 2078
paul@44 2079
    def record_reference_types(self, location, class_types, instance_types,
paul@90 2080
        module_types, constrained, constrained_specific=False, invocations=None):
paul@44 2081
paul@44 2082
        """
paul@44 2083
        Associate attribute provider types with the given 'location', consisting
paul@44 2084
        of the given 'class_types', 'instance_types' and 'module_types'.
paul@44 2085
paul@44 2086
        If 'constrained' is indicated, the constrained nature of the accessor is
paul@44 2087
        recorded for the location.
paul@44 2088
paul@44 2089
        If 'constrained_specific' is indicated using a true value, instance types
paul@44 2090
        will not be added to class types to permit access via instances at the
paul@44 2091
        given location. This is only useful where a specific accessor is known
paul@44 2092
        to be a class.
paul@44 2093
paul@105 2094
        If 'invocations' is given, the given attribute names indicate those
paul@105 2095
        which are involved in invocations. Such invocations, if involving
paul@105 2096
        functions, will employ those functions as bound methods and will
paul@105 2097
        therefore not support classes as accessors, only instances of such
paul@105 2098
        classes.
paul@105 2099
paul@44 2100
        Note that the specified types only indicate the provider types for
paul@44 2101
        attributes, whereas the recorded accessor types indicate the possible
paul@44 2102
        types of the actual objects used to access attributes.
paul@44 2103
        """
paul@44 2104
paul@44 2105
        # Update the type details for the location.
paul@44 2106
paul@721 2107
        self.update_provider_types(location, class_types, instance_types, module_types)
paul@44 2108
paul@44 2109
        # Class types support classes and instances as accessors.
paul@44 2110
        # Instance-only and module types support only their own kinds as
paul@44 2111
        # accessors.
paul@44 2112
paul@791 2113
        path, name = location.path, location.name
paul@90 2114
paul@90 2115
        if invocations:
paul@90 2116
            class_only_types = self.filter_for_invocations(class_types, invocations)
paul@90 2117
        else:
paul@90 2118
            class_only_types = class_types
paul@90 2119
paul@44 2120
        # However, the nature of accessors can be further determined.
paul@44 2121
        # Any self variable may only refer to an instance.
paul@44 2122
paul@44 2123
        if name != "self" or not self.in_method(path):
paul@90 2124
            self.accessor_class_types[location].update(class_only_types)
paul@44 2125
paul@44 2126
        if not constrained_specific:
paul@44 2127
            self.accessor_instance_types[location].update(class_types)
paul@44 2128
paul@44 2129
        self.accessor_instance_types[location].update(instance_types)
paul@44 2130
paul@44 2131
        if name != "self" or not self.in_method(path):
paul@44 2132
            self.accessor_module_types[location].update(module_types)
paul@44 2133
paul@44 2134
        if constrained:
paul@67 2135
            self.accessor_constrained.add(location)
paul@44 2136
paul@840 2137
        # Complain about situations where no types are valid but where a
paul@840 2138
        # specific, known accessor type has been indicated. This absence of
paul@840 2139
        # suitable types is likely to occur when the presence of invocations
paul@840 2140
        # filters out the accessor type.
paul@840 2141
paul@840 2142
        if not class_only_types and not instance_types and not module_types and \
paul@840 2143
           invocations and constrained_specific:
paul@840 2144
paul@840 2145
            raise DeduceError("In %s, methods of class %s cannot be called directly." %
paul@840 2146
                (path, name))
paul@840 2147
paul@721 2148
    def update_provider_types(self, location, class_types, instance_types, module_types):
paul@721 2149
paul@721 2150
        """
paul@721 2151
        Update provider types for the given 'location', adding 'class_types',
paul@721 2152
        'instance_types' and 'module_types' to those already stored.
paul@721 2153
        """
paul@721 2154
paul@721 2155
        self.provider_class_types[location].update(class_types)
paul@721 2156
        self.provider_instance_types[location].update(instance_types)
paul@721 2157
        self.provider_module_types[location].update(module_types)
paul@721 2158
paul@721 2159
    def update_accessor_types(self, location, class_types, instance_types, module_types):
paul@721 2160
paul@721 2161
        """
paul@721 2162
        Update accessor types for the given 'location', adding 'class_types',
paul@721 2163
        'instance_types' and 'module_types' to those already stored.
paul@721 2164
        """
paul@721 2165
paul@721 2166
        self.accessor_class_types[location].update(class_types)
paul@721 2167
        self.accessor_instance_types[location].update(instance_types)
paul@721 2168
        self.accessor_module_types[location].update(module_types)
paul@721 2169
paul@90 2170
    def filter_for_invocations(self, class_types, attrnames):
paul@90 2171
paul@90 2172
        """
paul@90 2173
        From the given 'class_types', identify methods for the given
paul@90 2174
        'attrnames' that are being invoked, returning a filtered collection of
paul@90 2175
        class types.
paul@553 2176
paul@553 2177
        This method may be used to remove class types from consideration where
paul@553 2178
        their attributes are methods that are directly invoked: method
paul@553 2179
        invocations must involve instance accessors.
paul@90 2180
        """
paul@90 2181
paul@90 2182
        to_filter = set()
paul@90 2183
paul@90 2184
        for class_type in class_types:
paul@90 2185
            for attrname in attrnames:
paul@553 2186
paul@553 2187
                # Attempt to obtain a class attribute of the given name. This
paul@553 2188
                # may return an attribute provided by an ancestor class.
paul@553 2189
paul@90 2190
                ref = self.importer.get_class_attribute(class_type, attrname)
paul@90 2191
                parent_class = ref and ref.parent()
paul@90 2192
paul@553 2193
                # If such an attribute is a method and would be available on
paul@553 2194
                # the given class, record the class for filtering.
paul@553 2195
paul@90 2196
                if ref and ref.has_kind("<function>") and (
paul@90 2197
                   parent_class == class_type or
paul@90 2198
                   class_type in self.descendants[parent_class]):
paul@90 2199
paul@90 2200
                    to_filter.add(class_type)
paul@90 2201
                    break
paul@90 2202
paul@90 2203
        return set(class_types).difference(to_filter)
paul@90 2204
paul@44 2205
    def identify_reference_attributes(self, location, attrname, class_types, instance_types, module_types, constrained):
paul@44 2206
paul@44 2207
        """
paul@44 2208
        Identify reference attributes, associating them with the given
paul@44 2209
        'location', identifying the given 'attrname', employing the given
paul@44 2210
        'class_types', 'instance_types' and 'module_types'.
paul@44 2211
paul@44 2212
        If 'constrained' is indicated, the constrained nature of the access is
paul@44 2213
        recorded for the location.
paul@44 2214
        """
paul@44 2215
paul@44 2216
        # Record the referenced objects.
paul@44 2217
paul@44 2218
        self.referenced_attrs[location] = \
paul@555 2219
            self._identify_reference_attribute(location, attrname, class_types, instance_types, module_types)
paul@44 2220
paul@44 2221
        if constrained:
paul@44 2222
            self.access_constrained.add(location)
paul@44 2223
paul@555 2224
    def _identify_reference_attribute(self, location, attrname, class_types, instance_types, module_types):
paul@44 2225
paul@44 2226
        """
paul@555 2227
        Identify the reference attribute at the given access 'location', using
paul@555 2228
        the given 'attrname', and employing the given 'class_types',
paul@555 2229
        'instance_types' and 'module_types'.
paul@44 2230
        """
paul@44 2231
paul@44 2232
        attrs = set()
paul@44 2233
paul@44 2234
        # The class types expose class attributes either directly or via
paul@44 2235
        # instances.
paul@44 2236
paul@44 2237
        for object_type in class_types:
paul@44 2238
            ref = self.importer.get_class_attribute(object_type, attrname)
paul@555 2239
            if ref and self.is_compatible_callable(location, object_type, ref):
paul@44 2240
                attrs.add(("<class>", object_type, ref))
paul@44 2241
paul@44 2242
            # Add any distinct instance attributes that would be provided
paul@44 2243
            # by instances also providing indirect class attribute access.
paul@44 2244
paul@44 2245
            for ref in self.importer.get_instance_attributes(object_type, attrname):
paul@555 2246
                if self.is_compatible_callable(location, object_type, ref):
paul@555 2247
                    attrs.add(("<instance>", object_type, ref))
paul@44 2248
paul@44 2249
        # The instance-only types expose instance attributes, but although
paul@44 2250
        # classes are excluded as potential accessors (since they do not provide
paul@44 2251
        # the instance attributes), the class types may still provide some
paul@44 2252
        # attributes.
paul@44 2253
paul@44 2254
        for object_type in instance_types:
paul@44 2255
            instance_attrs = self.importer.get_instance_attributes(object_type, attrname)
paul@44 2256
paul@44 2257
            if instance_attrs:
paul@44 2258
                for ref in instance_attrs:
paul@555 2259
                    if self.is_compatible_callable(location, object_type, ref):
paul@555 2260
                        attrs.add(("<instance>", object_type, ref))
paul@44 2261
            else:
paul@44 2262
                ref = self.importer.get_class_attribute(object_type, attrname)
paul@555 2263
                if ref and self.is_compatible_callable(location, object_type, ref):
paul@44 2264
                    attrs.add(("<class>", object_type, ref))
paul@44 2265
paul@44 2266
        # Module types expose module attributes for module accessors.
paul@44 2267
paul@44 2268
        for object_type in module_types:
paul@44 2269
            ref = self.importer.get_module_attribute(object_type, attrname)
paul@555 2270
            if ref and self.is_compatible_callable(location, object_type, ref):
paul@44 2271
                attrs.add(("<module>", object_type, ref))
paul@44 2272
paul@44 2273
        return attrs
paul@44 2274
paul@555 2275
    def is_compatible_callable(self, location, object_type, ref):
paul@555 2276
paul@555 2277
        """
paul@555 2278
        Return whether any invocation at 'location' involving an attribute of
paul@555 2279
        'object_type' identified by 'ref' is compatible with any arguments used.
paul@555 2280
        """
paul@555 2281
paul@557 2282
        invocation = self.reference_invocations.get(location)
paul@557 2283
        if invocation is None:
paul@555 2284
            return True
paul@555 2285
paul@555 2286
        objpath = ref.get_origin()
paul@555 2287
        if not objpath:
paul@555 2288
            return True
paul@555 2289
paul@555 2290
        parameters = self.importer.function_parameters.get(objpath)
paul@555 2291
        if not parameters:
paul@555 2292
            return True
paul@555 2293
paul@555 2294
        defaults = self.importer.function_defaults.get(objpath)
paul@557 2295
        arguments, keywords = invocation
paul@557 2296
        names = set(parameters)
paul@555 2297
paul@555 2298
        # Determine whether the specified arguments are
paul@555 2299
        # compatible with the callable signature.
paul@555 2300
paul@555 2301
        if arguments >= len(parameters) - len(defaults) and \
paul@557 2302
           arguments <= len(parameters) and \
paul@557 2303
           names.issuperset(keywords):
paul@555 2304
paul@555 2305
            return True
paul@555 2306
        else:
paul@555 2307
            init_item(self.reference_invocations_unsuitable, location, set)
paul@555 2308
            self.reference_invocations_unsuitable[location].add(ref)
paul@555 2309
            return False
paul@555 2310
paul@553 2311
    # Attribute access plan formulation.
paul@553 2312
paul@67 2313
    class_tests = (
paul@237 2314
        ("guarded", "specific", "type"),
paul@237 2315
        ("guarded", "common", "type"),
paul@237 2316
        ("test", "specific", "type"),
paul@237 2317
        ("test", "common", "type"),
paul@67 2318
        )
paul@67 2319
paul@67 2320
    def get_access_plan(self, location):
paul@65 2321
paul@77 2322
        """
paul@77 2323
        Return details of the access at the given 'location'. The details are as
paul@77 2324
        follows:
paul@77 2325
paul@77 2326
         * the initial accessor (from which accesses will be performed if no
paul@77 2327
           computed static accessor is found)
paul@77 2328
         * details of any test required on the initial accessor
paul@77 2329
         * details of any type employed by the test
paul@77 2330
         * any static accessor (from which accesses will be performed in
paul@77 2331
           preference to the initial accessor)
paul@77 2332
         * attributes needing to be traversed from the base that yield
paul@77 2333
           unambiguous objects
paul@98 2334
         * access modes for each of the unambiguously-traversed attributes
paul@77 2335
         * remaining attributes needing to be tested and traversed
paul@77 2336
         * details of the context
paul@102 2337
         * any test to apply to the context
paul@653 2338
         * the method of obtaining the first attribute
paul@77 2339
         * the method of obtaining the final attribute
paul@77 2340
         * any static final attribute
paul@325 2341
         * the kinds of objects providing the final attribute
paul@77 2342
        """
paul@65 2343
paul@256 2344
        const_access = self.const_accesses_rev.get(location)
paul@65 2345
paul@791 2346
        path, name, attrnames = location.path, location.name, location.attrnames
paul@75 2347
        remaining = attrnames.split(".")
paul@75 2348
        attrname = remaining[0]
paul@65 2349
paul@890 2350
        # Special case for the ubiquitous __class__ attribute.
paul@890 2351
paul@890 2352
        ubiquitous = attrname == "__class__"
paul@890 2353
paul@687 2354
        # Obtain reference, provider and provider kind information.
paul@687 2355
paul@687 2356
        attrs = self.reference_all_attrs[location]
paul@687 2357
        provider_types = self.reference_all_providers[location]
paul@687 2358
        provider_kinds = self.reference_all_provider_kinds[location]
paul@67 2359
paul@67 2360
        # Obtain accessor type and kind information.
paul@67 2361
paul@67 2362
        accessor_types = self.reference_all_accessor_types[location]
paul@67 2363
        accessor_general_types = self.reference_all_accessor_general_types[location]
paul@824 2364
        accessor_kinds = set(get_kinds(accessor_general_types))
paul@67 2365
paul@67 2366
        # Determine any guard or test requirements.
paul@67 2367
paul@67 2368
        constrained = location in self.access_constrained
paul@70 2369
        test = self.reference_test_types[location]
paul@77 2370
        test_type = self.reference_test_accessor_type.get(location)
paul@67 2371
paul@67 2372
        # Determine the accessor and provider properties.
paul@67 2373
paul@67 2374
        class_accessor = "<class>" in accessor_kinds
paul@67 2375
        module_accessor = "<module>" in accessor_kinds
paul@67 2376
        instance_accessor = "<instance>" in accessor_kinds
paul@67 2377
        provided_by_class = "<class>" in provider_kinds
paul@67 2378
        provided_by_instance = "<instance>" in provider_kinds
paul@67 2379
paul@74 2380
        # Determine how attributes may be accessed relative to the accessor.
paul@74 2381
paul@890 2382
        object_relative = ubiquitous or class_accessor or module_accessor or provided_by_instance
paul@890 2383
        class_relative = not ubiquitous and instance_accessor and provided_by_class
paul@74 2384
paul@67 2385
        # Identify the last static attribute for context acquisition.
paul@67 2386
paul@67 2387
        base = None
paul@67 2388
        dynamic_base = None
paul@67 2389
paul@687 2390
        # Constant accesses have static providers.
paul@65 2391
paul@65 2392
        if const_access:
paul@687 2393
            base = len(provider_types) == 1 and first(provider_types)
paul@67 2394
paul@263 2395
        # Name-based accesses.
paul@67 2396
paul@213 2397
        elif name:
paul@65 2398
            ref = self.importer.identify("%s.%s" % (path, name))
paul@263 2399
paul@263 2400
            # Constant accessors are static.
paul@263 2401
paul@263 2402
            if ref and ref.static():
paul@65 2403
                base = ref.get_origin()
paul@65 2404
paul@70 2405
            # Usage of previously-generated guard and test details.
paul@70 2406
paul@237 2407
            elif test[:2] == ("constrained", "specific"):
paul@67 2408
                ref = first(accessor_types)
paul@67 2409
paul@237 2410
            elif test[:2] == ("constrained", "common"):
paul@67 2411
                ref = first(accessor_general_types)
paul@67 2412
paul@237 2413
            elif test[:2] == ("guarded", "specific"):
paul@67 2414
                ref = first(accessor_types)
paul@67 2415
paul@237 2416
            elif test[:2] == ("guarded", "common"):
paul@67 2417
                ref = first(accessor_general_types)
paul@67 2418
paul@70 2419
            # For attribute-based tests, tentatively identify a dynamic base.
paul@70 2420
            # Such tests allow single or multiple kinds of a type.
paul@70 2421
paul@237 2422
            elif test[0] == "test" and test[1] in ("common", "specific"):
paul@77 2423
                dynamic_base = test_type
paul@67 2424
paul@67 2425
            # Static accessors.
paul@67 2426
paul@70 2427
            if not base and test in self.class_tests:
paul@70 2428
                base = ref and ref.get_origin() or dynamic_base
paul@70 2429
paul@70 2430
            # Accessors that are not static but whose nature is determined.
paul@70 2431
paul@70 2432
            elif not base and ref:
paul@67 2433
                dynamic_base = ref.get_origin()
paul@67 2434
paul@102 2435
        # Determine initial accessor details.
paul@102 2436
paul@102 2437
        accessor = base or dynamic_base
paul@102 2438
        accessor_kind = len(accessor_kinds) == 1 and first(accessor_kinds) or None
paul@102 2439
        provider_kind = len(provider_kinds) == 1 and first(provider_kinds) or None
paul@102 2440
paul@102 2441
        # Traverse remaining attributes.
paul@102 2442
paul@65 2443
        traversed = []
paul@96 2444
        traversal_modes = []
paul@65 2445
paul@108 2446
        while len(attrs) == 1 and not first(attrs).has_kind("<var>"):
paul@65 2447
            attr = first(attrs)
paul@65 2448
paul@65 2449
            traversed.append(attrname)
paul@96 2450
            traversal_modes.append(accessor_kind == provider_kind and "object" or "class")
paul@96 2451
paul@102 2452
            # Consume attribute names providing unambiguous attributes.
paul@102 2453
paul@75 2454
            del remaining[0]
paul@75 2455
paul@75 2456
            if not remaining:
paul@65 2457
                break
paul@65 2458
paul@67 2459
            # Update the last static attribute.
paul@67 2460
paul@65 2461
            if attr.static():
paul@65 2462
                base = attr.get_origin()
paul@65 2463
                traversed = []
paul@96 2464
                traversal_modes = []
paul@65 2465
paul@102 2466
            # Get the access details.
paul@67 2467
paul@75 2468
            attrname = remaining[0]
paul@102 2469
            accessor = attr.get_origin()
paul@102 2470
            accessor_kind = attr.get_kind()
paul@102 2471
            provider_kind = self.importer.get_attribute_provider(attr, attrname)
paul@102 2472
            accessor_kinds = [accessor_kind]
paul@102 2473
            provider_kinds = [provider_kind]
paul@102 2474
paul@102 2475
            # Get the next attribute.
paul@102 2476
paul@65 2477
            attrs = self.importer.get_attributes(attr, attrname)
paul@67 2478
paul@67 2479
        # Where many attributes are suggested, no single attribute identity can
paul@67 2480
        # be loaded.
paul@67 2481
paul@65 2482
        else:
paul@65 2483
            attr = None
paul@65 2484
paul@67 2485
        # Determine the method of access.
paul@67 2486
paul@256 2487
        is_assignment = location in self.reference_assignments or const_access in self.reference_assignments
paul@256 2488
        is_invocation = location in self.reference_invocations or const_access in self.reference_invocations
paul@98 2489