Lichen

Annotated deducer.py

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