Lichen

Annotated deducer.py

336:8c75cdf1a764
2016-12-06 Paul Boddie Introduced stream classes employing C-level FILE pointers, changing the sys stdin, stdout and stderr objects to be instances of these stream classes. Added fread and fwrite support to the native functions. Added support for raising EOFError.
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