Lichen (annotate deducer.py in 2989aab1b4f7)

#!/usr/bin/env python

paul@44

2

paul@44

3

"""

paul@44

4

Deduce types for usage observations.

Copyright (C) 2014, 2015, 2016, 2017, 2018 Paul Boddie <paul@boddie.org.uk>

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.

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.

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

"""

from common import first, get_assigned_attributes, get_attrnames, \

paul@90

23

                   get_invoked_attributes, get_name_path, init_item, \

paul@791

24

                   order_dependencies_partial, sorted_output, \

paul@791

25

                   AccessLocation, CommonOutput, Location

paul@789

26

from encoders import encode_access_location, encode_alias_location, \

paul@789

27

                     encode_constrained, encode_instruction, encode_location, \

paul@789

28

                     encode_usage, get_kinds, \

paul@789

29

                     test_label_for_kind, test_label_for_type

paul@71

30

from errors import DeduceError

paul@44

31

from os.path import join

paul@57

32

from referencing import combine_types, is_single_class_type, separate_types, \

paul@57

33

                        Reference

class Deducer(CommonOutput):

    "Deduce types in a program."

    root_class_type = "__builtins__.object"

    def __init__(self, importer, output):

"""

paul@44

44

        Initialise an instance using the given 'importer' that will perform

paul@44

45

        deductions on the program information, writing the results to the given

paul@44

46

        'output' directory.

paul@44

47

"""

        self.importer = importer

paul@44

50

        self.output = output

        # Descendants of classes.

        self.descendants = {}

paul@44

55

        self.init_descendants()

paul@44

56

        self.init_special_attributes()

        # Map locations to usage in order to determine specific types.

        self.location_index = {}

        # Map access locations to definition locations.

        self.access_index = {}

        # Map definition locations to affected accesses.

        self.access_index_rev = {}

        # Map aliases to accesses that define them.

        self.alias_index = {}

        # Map accesses to aliases whose initial values are influenced by them.

        self.alias_index_rev = {}

        # Map definitions and accesses to initialised names.

        self.initialised_names = {}

paul@791

81

        self.initialised_accesses = {}

        # Map constant accesses to redefined accesses.

        self.const_accesses = {}

paul@67

86

        self.const_accesses_rev = {}

        # Map usage observations to assigned attributes.

        self.assigned_attrs = {}

        # Map usage observations to objects.

        self.attr_class_types = {}

paul@44

95

        self.attr_instance_types = {}

paul@44

96

        self.attr_module_types = {}

        # All known attribute names.

        self.all_attrnames = set()

        # Modified attributes from usage observations.

        self.modified_attributes = {}

        # Accesses that are assignments or invocations.

        self.reference_assignments = set()

paul@553

109

        self.reference_invocations = {}

paul@553

110

        self.reference_invocations_unsuitable = {}

        # Map locations to types, constrained indicators and attributes.

        self.accessor_class_types = {}

paul@44

115

        self.accessor_instance_types = {}

paul@44

116

        self.accessor_module_types = {}

paul@44

117

        self.provider_class_types = {}

paul@44

118

        self.provider_instance_types = {}

paul@44

119

        self.provider_module_types = {}

paul@67

120

        self.accessor_constrained = set()

paul@44

121

        self.access_constrained = set()

paul@44

122

        self.referenced_attrs = {}

paul@44

123

        self.referenced_objects = {}

        # Details of access operations.

        self.access_plans = {}

        # Specific attribute access information.

        self.access_instructions = {}

paul@653

132

        self.accessor_kinds = {}

        # Accumulated information about accessors and providers.

        self.accessor_general_class_types = {}

paul@44

137

        self.accessor_general_instance_types = {}

paul@44

138

        self.accessor_general_module_types = {}

paul@44

139

        self.accessor_all_types = {}

paul@44

140

        self.accessor_all_general_types = {}

paul@44

141

        self.provider_all_types = {}

paul@44

142

        self.accessor_guard_tests = {}

        # Accumulated information about accessed attributes and

paul@67

145

        # access/attribute-specific accessor tests.

        self.reference_all_attrs = {}

paul@687

148

        self.reference_all_providers = {}

paul@687

149

        self.reference_all_provider_kinds = {}

paul@67

150

        self.reference_all_accessor_types = {}

paul@67

151

        self.reference_all_accessor_general_types = {}

paul@44

152

        self.reference_test_types = {}

paul@77

153

        self.reference_test_accessor_type = {}

        # The processing workflow itself.

        self.init_usage_index()

paul@501

158

        self.init_attr_type_indexes()

paul@501

159

        self.init_combined_attribute_index()

paul@44

160

        self.init_accessors()

paul@44

161

        self.init_accesses()

paul@44

162

        self.init_aliases()

paul@44

163

        self.modify_mutated_attributes()

paul@44

164

        self.identify_references()

paul@44

165

        self.classify_accessors()

paul@44

166

        self.classify_accesses()

paul@67

167

        self.initialise_access_plans()

paul@653

168

        self.initialise_access_instructions()

paul@411

169

        self.identify_dependencies()

    def to_output(self):

        "Write the output files using deduction information."

        self.check_output()

        self.write_mutations()

paul@44

178

        self.write_accessors()

paul@44

179

        self.write_accesses()

paul@65

180

        self.write_access_plans()

    def write_mutations(self):

"""

paul@44

185

        Write mutation-related output in the following format:

        qualified name " " original object type

        Object type can be "<class>", "<function>" or "<var>".

paul@44

190

"""

        f = open(join(self.output, "mutations"), "w")

paul@44

193

        try:

paul@44

194

            attrs = self.modified_attributes.items()

paul@44

195

            attrs.sort()

            for attr, value in attrs:

paul@44

198

                print >>f, attr, value

paul@44

199

        finally:

paul@44

200

            f.close()

    def write_accessors(self):

"""

paul@44

205

        Write reference-related output in the following format for types:

        location " " ( "constrained" | "deduced" ) " " attribute type " " most general type names " " number of specific types

        Note that multiple lines can be given for each location, one for each

paul@44

210

        attribute type.

        Locations have the following format:

        qualified name of scope ":" local name ":" name version

        The attribute type can be "<class>", "<instance>", "<module>" or "<>",

paul@44

217

        where the latter indicates an absence of suitable references.

        Type names indicate the type providing the attributes, being either a

paul@44

220

        class or module qualified name.

        ----

        A summary of accessor types is formatted as follows:

        location " " ( "constrained" | "deduced" ) " " ( "specific" | "common" | "unguarded" ) " " most general type names " " number of specific types

        This summary groups all attribute types (class, instance, module) into a

paul@44

229

        single line in order to determine the complexity of identifying an

paul@44

230

        accessor.

        ----

        References that cannot be supported by any types are written to a

paul@44

235

        warnings file in the following format:

        location

        ----

        For each location where a guard would be asserted to guarantee the

paul@44

242

        nature of an object, the following format is employed:

        location " " ( "specific" | "common" ) " " object kind " " object types

        Object kind can be "<class>", "<instance>" or "<module>".

        ----

        A summary of aliases is formatted as follows:

        location " " locations

paul@44

253

"""

        f_type_summary = open(join(self.output, "type_summary"), "w")

paul@44

256

        f_types = open(join(self.output, "types"), "w")

paul@44

257

        f_warnings = open(join(self.output, "type_warnings"), "w")

paul@44

258

        f_guards = open(join(self.output, "guards"), "w")

paul@788

259

        f_aliases = open(join(self.output, "aliases"), "w")

        try:

paul@44

262

            locations = self.accessor_class_types.keys()

paul@44

263

            locations.sort()

            for location in locations:

paul@67

266

                constrained = location in self.accessor_constrained

                # Accessor information.

                class_types = self.accessor_class_types[location]

paul@44

271

                instance_types = self.accessor_instance_types[location]

paul@44

272

                module_types = self.accessor_module_types[location]

                general_class_types = self.accessor_general_class_types[location]

paul@44

275

                general_instance_types = self.accessor_general_instance_types[location]

paul@44

276

                general_module_types = self.accessor_general_module_types[location]

                all_types = self.accessor_all_types[location]

paul@44

279

                all_general_types = self.accessor_all_general_types[location]

                if class_types:

paul@44

282

                    print >>f_types, encode_location(location), encode_constrained(constrained), "<class>", \

paul@44

283

                        sorted_output(general_class_types), len(class_types)

                if instance_types:

paul@44

286

                    print >>f_types, encode_location(location), encode_constrained(constrained), "<instance>", \

paul@44

287

                        sorted_output(general_instance_types), len(instance_types)

                if module_types:

paul@44

290

                    print >>f_types, encode_location(location), encode_constrained(constrained), "<module>", \

paul@44

291

                        sorted_output(general_module_types), len(module_types)

                if not all_types:

paul@44

294

                    print >>f_types, encode_location(location), "deduced", "<>", 0

paul@55

295

                    attrnames = list(self.location_index[location])

paul@55

296

                    attrnames.sort()

paul@55

297

                    print >>f_warnings, encode_location(location), "; ".join(map(encode_usage, attrnames))

                guard_test = self.accessor_guard_tests.get(location)

paul@237

300

                if guard_test:

paul@237

301

                    guard_test_type, guard_test_arg = guard_test

                # Write specific type guard details.

                if guard_test and guard_test_type == "specific":

paul@237

306

                    print >>f_guards, encode_location(location), "-".join(guard_test), \

paul@237

307

                        first(get_kinds(all_types)), \

paul@44

308

                        sorted_output(all_types)

                # Write common type guard details.

                elif guard_test and guard_test_type == "common":

paul@237

313

                    print >>f_guards, encode_location(location), "-".join(guard_test), \

paul@237

314

                        first(get_kinds(all_general_types)), \

paul@44

315

                        sorted_output(all_general_types)

                print >>f_type_summary, encode_location(location), encode_constrained(constrained), \

paul@237

318

                    guard_test and "-".join(guard_test) or "unguarded", sorted_output(all_general_types), len(all_types)

            # Aliases are visited separately from accessors, even though they

paul@788

321

            # are often the same thing.

            locations = self.alias_index.keys()

paul@788

324

            locations.sort()

            for location in locations:

paul@788

327

                accesses = []

paul@788

328

                for access_location in self.alias_index[location]:

paul@789

329

                    invocation = access_location in self.reference_invocations

paul@789

330

                    accesses.append(encode_alias_location(access_location, invocation))

paul@789

331

                invocation = location in self.reference_invocations

paul@789

332

                print >>f_aliases, encode_alias_location(location, invocation), ", ".join(accesses)

        finally:

paul@44

335

            f_type_summary.close()

paul@44

336

            f_types.close()

paul@44

337

            f_warnings.close()

paul@44

338

            f_guards.close()

paul@788

339

            f_aliases.close()

    def write_accesses(self):

"""

paul@44

344

        Specific attribute output is produced in the following format:

        location " " ( "constrained" | "deduced" ) " " attribute type " " attribute references

        Note that multiple lines can be given for each location and attribute

paul@44

349

        name, one for each attribute type.

        Locations have the following format:

        qualified name of scope ":" local name ":" attribute name ":" access number

        The attribute type can be "<class>", "<instance>", "<module>" or "<>",

paul@44

356

        where the latter indicates an absence of suitable references.

        Attribute references have the following format:

        object type ":" qualified name

        Object type can be "<class>", "<function>" or "<var>".

        ----

        A summary of attributes is formatted as follows:

        location " " attribute name " " ( "constrained" | "deduced" ) " " test " " attribute references

        This summary groups all attribute types (class, instance, module) into a

paul@44

371

        single line in order to determine the complexity of each access.

        Tests can be "validate", "specific", "untested", "guarded-validate" or "guarded-specific".

        ----

        For each access where a test would be asserted to guarantee the

paul@44

378

        nature of an attribute, the following formats are employed:

        location " " attribute name " " "validate"

paul@44

381

        location " " attribute name " " "specific" " " attribute type " " object type

        ----

        References that cannot be supported by any types are written to a

paul@44

386

        warnings file in the following format:

        location

paul@44

389

"""

        f_attr_summary = open(join(self.output, "attribute_summary"), "w")

paul@44

392

        f_attrs = open(join(self.output, "attributes"), "w")

paul@44

393

        f_tests = open(join(self.output, "tests"), "w")

paul@44

394

        f_warnings = open(join(self.output, "attribute_warnings"), "w")

paul@553

395

        f_unsuitable = open(join(self.output, "invocation_warnings"), "w")

        try:

paul@44

398

            locations = self.referenced_attrs.keys()

paul@44

399

            locations.sort()

            for location in locations:

paul@44

402

                constrained = location in self.access_constrained

                # Attribute information, both name-based and anonymous.

                referenced_attrs = self.referenced_attrs[location]

                if referenced_attrs:

paul@791

409

                    attrname = location.get_attrname()

                    all_accessed_attrs = list(set(self.reference_all_attrs[location]))

paul@738

412

                    all_accessed_attrs.sort()

                    for attrtype, attrs in self.get_referenced_attrs(location):

paul@44

415

                        print >>f_attrs, encode_access_location(location), encode_constrained(constrained), attrtype, sorted_output(attrs)

                    test_type = self.reference_test_types.get(location)

                    # Write the need to test at run time.

                    if test_type[0] == "validate":

paul@237

422

                        print >>f_tests, encode_access_location(location), "-".join(test_type)

                    # Write any type checks for anonymous accesses.

                    elif test_type and self.reference_test_accessor_type.get(location):

paul@240

427

                        print >>f_tests, encode_access_location(location), "-".join(test_type), \

paul@44

428

                            sorted_output(all_accessed_attrs), \

paul@77

429

                            self.reference_test_accessor_type[location]

                    print >>f_attr_summary, encode_access_location(location), encode_constrained(constrained), \

paul@237

432

                        test_type and "-".join(test_type) or "untested", sorted_output(all_accessed_attrs)

                    # Write details of potentially unsuitable invocation

paul@553

435

                    # occurrences.

                    unsuitable = self.reference_invocations_unsuitable.get(location)

paul@553

438

                    if unsuitable:

paul@553

439

                        unsuitable = map(str, unsuitable)

paul@553

440

                        unsuitable.sort()

paul@553

441

                        print >>f_unsuitable, encode_access_location(location), ", ".join(unsuitable)

                else:

paul@44

444

                    print >>f_warnings, encode_access_location(location)

        finally:

paul@44

447

            f_attr_summary.close()

paul@44

448

            f_attrs.close()

paul@44

449

            f_tests.close()

paul@44

450

            f_warnings.close()

paul@553

451

            f_unsuitable.close()

    def write_access_plans(self):

"""

paul@653

456

        Write access and instruction plans.

        Each attribute access is written out as a plan of the following form:

        location " " name " " test " " test type " " base " " traversed attributes

paul@653

461

                 " " traversal access modes " " attributes to traverse

paul@653

462

                 " " context " " context test " " first access method

paul@653

463

                 " " final access method " " static attribute " " accessor kinds

        Locations have the following format:

        qualified name of scope "." local name ":" name version

        Traversal access modes are either "class" (obtain accessor class to

paul@653

470

        access attribute) or "object" (obtain attribute directly from accessor).

paul@91

471

"""

        f_attrs = open(join(self.output, "attribute_plans"), "w")

        try:

paul@67

476

            locations = self.access_plans.keys()

paul@67

477

            locations.sort()

            for location in locations:

paul@234

480

                name, test, test_type, base, \

paul@234

481

                    traversed, traversal_modes, attrnames, \

paul@102

482

                    context, context_test, \

paul@234

483

                    first_method, final_method, \

paul@234

484

                    attr, accessor_kinds = self.access_plans[location]

                print >>f_attrs, encode_access_location(location), \

paul@213

487

                                 name or "{}", \

paul@237

488

                                 test and "-".join(test) or "{}", \

paul@237

489

                                 test_type or "{}", \

paul@75

490

                                 base or "{}", \

paul@67

491

                                 ".".join(traversed) or "{}", \

paul@96

492

                                 ".".join(traversal_modes) or "{}", \

paul@67

493

                                 ".".join(attrnames) or "{}", \

paul@102

494

                                 context, context_test, \

paul@234

495

                                 first_method, final_method, attr or "{}", \

paul@234

496

                                 ",".join(accessor_kinds)

        finally:

paul@67

499

            f_attrs.close()

        f = open(join(self.output, "instruction_plans"), "w")

paul@653

502

        try:

paul@653

503

            access_instructions = self.access_instructions.items()

paul@653

504

            access_instructions.sort()

            for location, instructions in access_instructions:

paul@653

507

                print >>f, encode_access_location(location), "..."

paul@653

508

                for instruction in instructions:

paul@653

509

                    print >>f, encode_instruction(instruction)

paul@653

510

                print >>f

        finally:

paul@653

513

            f.close()

    def classify_accessors(self):

        "For each program location, classify accessors."

        # Where instance and module types are defined, class types are also

paul@44

520

        # defined. See: init_definition_details

        locations = self.accessor_class_types.keys()

        for location in locations:

paul@67

525

            constrained = location in self.accessor_constrained

            # Provider information.

            class_types = self.provider_class_types[location]

paul@44

530

            instance_types = self.provider_instance_types[location]

paul@44

531

            module_types = self.provider_module_types[location]

            # Collect specific and general type information.

            self.provider_all_types[location] = \

paul@57

536

                combine_types(class_types, instance_types, module_types)

            # Accessor information.

            class_types = self.accessor_class_types[location]

paul@44

541

            self.accessor_general_class_types[location] = \

paul@69

542

                general_class_types = self.get_most_general_class_types(class_types)

            instance_types = self.accessor_instance_types[location]

paul@44

545

            self.accessor_general_instance_types[location] = \

paul@69

546

                general_instance_types = self.get_most_general_class_types(instance_types)

            module_types = self.accessor_module_types[location]

paul@44

549

            self.accessor_general_module_types[location] = \

paul@44

550

                general_module_types = self.get_most_general_module_types(module_types)

            # Collect specific and general type information.

            self.accessor_all_types[location] = all_types = \

paul@57

555

                combine_types(class_types, instance_types, module_types)

            self.accessor_all_general_types[location] = all_general_types = \

paul@57

558

                combine_types(general_class_types, general_instance_types, general_module_types)

            # Record guard information but only for accessors employed by

paul@742

561

            # accesses. There are no attribute accesses to guard, otherwise.

            if not constrained and self.access_index_rev.get(location):

                # Test for self parameters in methods that could not be

paul@816

566

                # constrained, potentially due to usage unsupported by the class

paul@816

567

                # defining the method (such as in mix-in classes).

                if location.name != "self" or self.in_method(location.path):

paul@816

570

                    self.record_guard(location, all_types, all_general_types)

    def record_guard(self, location, all_types, all_general_types):

"""

paul@816

575

        For the accessor 'location', record a guard if 'all_types' or

paul@816

576

        'all_general_types' are appropriate. Where no guard is recorded, access

paul@816

577

        tests will need to be applied.

paul@816

578

"""

        # Record specific type guard details.

        if len(all_types) == 1:

paul@816

583

            self.accessor_guard_tests[location] = ("specific", test_label_for_type(first(all_types)))

paul@816

584

        elif is_single_class_type(all_types):

paul@816

585

            self.accessor_guard_tests[location] = ("specific", "object")

        # Record common type guard details.

        elif len(all_general_types) == 1:

paul@816

590

            self.accessor_guard_tests[location] = ("common", test_label_for_type(first(all_types)))

paul@816

591

        elif is_single_class_type(all_general_types):

paul@816

592

            self.accessor_guard_tests[location] = ("common", "object")

        # Otherwise, no convenient guard can be defined.

    def classify_accesses(self):

        "For each program location, classify accesses."

        # Attribute accesses use potentially different locations to those of

paul@44

601

        # accessors.

        locations = self.referenced_attrs.keys()

        for location in locations:

paul@44

606

            constrained = location in self.access_constrained

            # Combine type information from all accessors supplying the access.

            accessor_locations = self.get_accessors_for_access(location)

            all_provider_types = set()

paul@44

613

            all_accessor_types = set()

paul@44

614

            all_accessor_general_types = set()

            for accessor_location in accessor_locations:

                # Obtain the provider types for guard-related attribute access

paul@44

619

                # checks.

                all_provider_types.update(self.provider_all_types.get(accessor_location))

                # Obtain the accessor guard types (specific and general).

                all_accessor_types.update(self.accessor_all_types.get(accessor_location))

paul@67

626

                all_accessor_general_types.update(self.accessor_all_general_types.get(accessor_location))

            # Obtain basic properties of the types involved in the access.

            single_accessor_type = len(all_accessor_types) == 1

paul@70

631

            single_accessor_class_type = is_single_class_type(all_accessor_types)

paul@70

632

            single_accessor_general_type = len(all_accessor_general_types) == 1

paul@70

633

            single_accessor_general_class_type = is_single_class_type(all_accessor_general_types)

            # Determine whether the attribute access is guarded or not.

            guarded = (

paul@70

638

                single_accessor_type or single_accessor_class_type or

paul@70

639

                single_accessor_general_type or single_accessor_general_class_type

            if guarded:

paul@44

643

                (guard_class_types, guard_instance_types, guard_module_types,

paul@57

644

                    _function_types, _var_types) = separate_types(all_provider_types)

            self.reference_all_accessor_types[location] = all_accessor_types

paul@67

647

            self.reference_all_accessor_general_types[location] = all_accessor_general_types

            # Attribute information, both name-based and anonymous.

            referenced_attrs = self.referenced_attrs[location]

            if not referenced_attrs:

paul@839

654

                raise DeduceError("In %s, access via %s to attribute %s (occurrence %d) cannot be identified." %

paul@839

655

                    (location.path, location.name, location.get_attrname(), location.access_number))

            # Record attribute information for each name used on the

paul@71

658

            # accessor.

            attrname = location.get_attrname()

            self.reference_all_attrs[location] = all_accessed_attrs = set()

paul@843

663

            self.reference_all_providers[location] = all_providers = set()

paul@687

664

            self.reference_all_provider_kinds[location] = all_provider_kinds = set()

            # Obtain provider and attribute details for this kind of

paul@71

667

            # object.

            for attrtype, object_type, attr in referenced_attrs:

paul@843

670

                all_accessed_attrs.add(attr)

paul@843

671

                all_providers.add(object_type)

paul@687

672

                all_provider_kinds.add(attrtype)

            # Obtain reference and provider information as sets for the

paul@687

675

            # operations below, retaining the list forms for use with

paul@687

676

            # instruction plan preparation.

            all_general_providers = self.get_most_general_types(all_providers)

            # Determine which attributes would be provided by the

paul@71

681

            # accessor types upheld by a guard.

            if guarded:

paul@71

684

                guard_attrs = set()

                for _attrtype, object_type, attr in \

paul@555

687

                    self._identify_reference_attribute(location, attrname, guard_class_types, guard_instance_types, guard_module_types):

                    guard_attrs.add(attr)

paul@71

690

            else:

paul@71

691

                guard_attrs = None

            # Constrained accesses guarantee the nature of the accessor.

paul@71

694

            # However, there may still be many types involved.

            if constrained:

paul@71

697

                if single_accessor_type:

paul@237

698

                    self.reference_test_types[location] = ("constrained", "specific", test_label_for_type(first(all_accessor_types)))

paul@71

699

                elif single_accessor_class_type:

paul@237

700

                    self.reference_test_types[location] = ("constrained", "specific", "object")

paul@71

701

                elif single_accessor_general_type:

paul@237

702

                    self.reference_test_types[location] = ("constrained", "common", test_label_for_type(first(all_accessor_general_types)))

paul@71

703

                elif single_accessor_general_class_type:

paul@237

704

                    self.reference_test_types[location] = ("constrained", "common", "object")

paul@44

705

                else:

paul@237

706

                    self.reference_test_types[location] = ("constrained", "many")

            # Suitably guarded accesses, where the nature of the

paul@71

709

            # accessor can be guaranteed, do not require the attribute

paul@71

710

            # involved to be validated. Otherwise, for unguarded

paul@71

711

            # accesses, access-level tests are required.

            elif guarded and all_accessed_attrs.issubset(guard_attrs):

paul@71

714

                if single_accessor_type:

paul@237

715

                    self.reference_test_types[location] = ("guarded", "specific", test_label_for_type(first(all_accessor_types)))

paul@71

716

                elif single_accessor_class_type:

paul@237

717

                    self.reference_test_types[location] = ("guarded", "specific", "object")

paul@71

718

                elif single_accessor_general_type:

paul@237

719

                    self.reference_test_types[location] = ("guarded", "common", test_label_for_type(first(all_accessor_general_types)))

paul@71

720

                elif single_accessor_general_class_type:

paul@237

721

                    self.reference_test_types[location] = ("guarded", "common", "object")

            # Record the need to test the type of anonymous and

paul@71

724

            # unconstrained accessors.

            elif len(all_providers) == 1:

paul@71

727

                provider = first(all_providers)

paul@654

728

                if provider != self.root_class_type:

paul@71

729

                    all_accessor_kinds = set(get_kinds(all_accessor_types))

paul@71

730

                    if len(all_accessor_kinds) == 1:

paul@385

731

                        test_type = ("test", "specific", test_label_for_kind(first(all_accessor_kinds)))

paul@70

732

                    else:

paul@237

733

                        test_type = ("test", "specific", "object")

paul@71

734

                    self.reference_test_types[location] = test_type

paul@77

735

                    self.reference_test_accessor_type[location] = provider

            elif len(all_general_providers) == 1:

paul@71

738

                provider = first(all_general_providers)

paul@654

739

                if provider != self.root_class_type:

paul@71

740

                    all_accessor_kinds = set(get_kinds(all_accessor_general_types))

paul@71

741

                    if len(all_accessor_kinds) == 1:

paul@385

742

                        test_type = ("test", "common", test_label_for_kind(first(all_accessor_kinds)))

paul@71

743

                    else:

paul@237

744

                        test_type = ("test", "common", "object")

paul@71

745

                    self.reference_test_types[location] = test_type

paul@77

746

                    self.reference_test_accessor_type[location] = provider

            # Record the need to test the identity of the attribute.

            else:

paul@237

751

                self.reference_test_types[location] = ("validate",)

    def initialise_access_plans(self):

        "Define attribute access plans."

        for location in self.referenced_attrs.keys():

paul@76

758

            original_location = self.const_accesses_rev.get(location)

paul@76

759

            self.access_plans[original_location or location] = self.get_access_plan(location)

    def identify_dependencies(self):

        "Introduce more module dependencies to the importer."

        for location, referenced_attrs in self.referenced_attrs.items():

            # Identify references providing dependencies.

            for attrtype, objtype, attr in referenced_attrs:

paul@791

770

                self.importer.add_dependency(location.path, attr.get_origin())

    def get_referenced_attrs(self, location):

"""

paul@44

775

        Return attributes referenced at the given access 'location' by the given

paul@44

776

        'attrname' as a list of (attribute type, attribute set) tuples.

paul@44

777

"""

        d = {}

paul@69

780

        for attrtype, objtype, attr in self.referenced_attrs[location]:

paul@69

781

            init_item(d, attrtype, set)

paul@246

782

            d[attrtype].add(attr.unaliased())

paul@69

783

        l = d.items()

paul@69

784

        l.sort() # class, module, instance

paul@44

785

        return l

    # Initialisation methods.

    def init_descendants(self):

        "Identify descendants of each class."

        for name in self.importer.classes.keys():

paul@44

794

            self.get_descendants_for_class(name)

    def get_descendants_for_class(self, name):

"""

paul@44

799

        Use subclass information to deduce the descendants for the class of the

paul@44

800

        given 'name'.

paul@44

801

"""

        if not self.descendants.has_key(name):

paul@44

804

            descendants = set()

            for subclass in self.importer.subclasses[name]:

paul@44

807

                descendants.update(self.get_descendants_for_class(subclass))

paul@44

808

                descendants.add(subclass)

            self.descendants[name] = descendants

        return self.descendants[name]

    def init_special_attributes(self):

        "Add special attributes to the classes for inheritance-related tests."

        all_class_attrs = self.importer.all_class_attrs

        for name, descendants in self.descendants.items():

paul@44

821

            for descendant in descendants:

paul@44

822

                all_class_attrs[descendant]["#%s" % name] = name

        for name in all_class_attrs.keys():

paul@44

825

            all_class_attrs[name]["#%s" % name] = name

    def init_usage_index(self):

"""

paul@44

830

        Create indexes for module and function attribute usage and for anonymous

paul@44

831

        accesses.

paul@44

832

"""

        for module in self.importer.get_modules():

paul@44

835

            for path, assignments in module.attr_usage.items():

paul@44

836

                self.add_usage(assignments, path)

        for path, all_attrnames in self.importer.all_attr_accesses.items():

paul@44

839

            for attrnames in all_attrnames:

paul@44

840

                attrname = get_attrnames(attrnames)[-1]

paul@791

841

                access_location = AccessLocation(path, None, attrnames, 0)

paul@107

842

                self.add_usage_term(access_location, ((attrname, False, False),))

    def add_usage(self, assignments, path):

"""

paul@44

847

        Collect usage from the given 'assignments', adding 'path' details to

paul@44

848

        each record if specified. Add the usage to an index mapping to location

paul@44

849

        information, as well as to an index mapping locations to usages.

paul@44

850

"""

        for name, versions in assignments.items():

paul@44

853

            for i, usages in enumerate(versions):

paul@791

854

                location = Location(path, name, None, i)

                for usage in usages:

paul@88

857

                    self.add_usage_term(location, usage)

    def add_usage_term(self, location, usage):

"""

paul@88

862

        For 'location' and using 'usage' as a description of usage, record

paul@44

863

        in the usage index a mapping from the usage to 'location', and record in

paul@44

864

        the location index a mapping from 'location' to the usage.

paul@44

865

"""

        init_item(self.location_index, location, set)

paul@88

868

        self.location_index[location].add(usage)

    def init_accessors(self):

        "Create indexes for module and function accessor information."

        for module in self.importer.get_modules():

paul@44

875

            for path, all_accesses in module.attr_accessors.items():

paul@44

876

                self.add_accessors(all_accesses, path)

    def add_accessors(self, all_accesses, path):

"""

paul@44

881

        For attribute accesses described by the mapping of 'all_accesses' from

paul@44

882

        name details to accessor details, record the locations of the accessors

paul@44

883

        for each access.

paul@44

884

"""

        # Get details for each access combining the given name and attribute.

        for (name, attrnames), accesses in all_accesses.items():

            # Obtain the usage details using the access information.

            for access_number, versions in enumerate(accesses):

paul@791

893

                access_location = AccessLocation(path, name, attrnames, access_number)

paul@44

894

                locations = []

                for version in versions:

paul@791

897

                    location = Location(path, name, None, version)

paul@44

898

                    locations.append(location)

                    # Map accessors to affected accesses.

                    l = init_item(self.access_index_rev, location, set)

paul@742

903

                    l.add(access_location)

                # Map accesses to supplying accessors.

                self.access_index[access_location] = locations

    def get_accessors_for_access(self, access_location):

        "Find a definition providing accessor details, if necessary."

        try:

paul@44

914

            return self.access_index[access_location]

paul@44

915

        except KeyError:

paul@44

916

            return [access_location]

    def init_accesses(self):

"""

paul@501

921

        Check that attributes used in accesses are actually defined on some

paul@501

922

        object. This can be overlooked if unknown attributes are employed in

paul@501

923

        attribute chains.

        Initialise collections for accesses involving assignments.

paul@44

926

"""

        # For each scope, obtain access details.

        for path, all_accesses in self.importer.all_attr_access_modifiers.items():

            # For each combination of name and attribute names, obtain

paul@44

933

            # applicable modifiers.

            for (name, attrname_str), modifiers in all_accesses.items():

                # For each access, determine the name versions affected by

paul@44

938

                # assignments.

                for access_number, (assignment, invocation) in enumerate(modifiers):

                    if name:

paul@791

943

                        access_location = AccessLocation(path, name, attrname_str, access_number)

paul@44

944

                    else:

paul@791

945

                        access_location = AccessLocation(path, None, attrname_str, 0)

                    # Plain name accesses do not employ attributes and are

paul@717

948

                    # ignored. Whether they are invoked is of interest, however.

                    if not attrname_str:

paul@717

951

                        if invocation:

paul@717

952

                            self.reference_invocations[access_location] = invocation

paul@501

953

                        continue

                    attrnames = get_attrnames(attrname_str)

                    # Check the attribute names.

                    for attrname in attrnames:

paul@501

960

                        if not attrname in self.all_attrnames:

paul@501

961

                            raise DeduceError("In %s, attribute %s is not defined in the program." % (path, attrname))

                    # Now only process assignments and invocations.

                    if invocation:

paul@553

966

                        self.reference_invocations[access_location] = invocation

paul@117

967

                        continue

paul@501

968

                    elif not assignment:

paul@501

969

                        continue

                    # Associate assignments with usage.

                    self.reference_assignments.add(access_location)

                    # Assignment occurs for the only attribute.

                    if len(attrnames) == 1:

paul@112

978

                        accessor_locations = self.get_accessors_for_access(access_location)

                        for location in accessor_locations:

paul@112

981

                            for usage in self.location_index[location]:

paul@88

982

                                init_item(self.assigned_attrs, usage, set)

paul@112

983

                                self.assigned_attrs[usage].add((path, name, attrnames[0]))

                    # Assignment occurs for the final attribute.

                    else:

paul@112

988

                        usage = ((attrnames[-1], False, False),)

paul@112

989

                        init_item(self.assigned_attrs, usage, set)

paul@112

990

                        self.assigned_attrs[usage].add((path, name, attrnames[-1]))

    def init_aliases(self):

        "Expand aliases so that alias-based accesses can be resolved."

        # Get aliased names with details of their accesses.

        for (path, name), all_aliases in self.importer.all_aliased_names.items():

            # For each version of the name, obtain the access locations.

            for version, aliases in all_aliases.items():

paul@742

1003

                for (original_path, original_name, attrnames, access_number) in aliases:

paul@791

1004

                    accessor_location = Location(path, name, None, version)

paul@791

1005

                    access_location = AccessLocation(original_path, original_name, attrnames, access_number)

paul@742

1006

                    init_item(self.alias_index, accessor_location, list)

paul@742

1007

                    self.alias_index[accessor_location].append(access_location)

        # Get initialised name information for accessors and accesses.

        for (path, name), versions in self.importer.all_initialised_names.items():

paul@791

1012

            for version, ref in versions.items():

paul@791

1013

                location = Location(path, name, None, version)

                self.initialised_names[location] = ref

                access_locations = self.access_index_rev.get(location)

paul@791

1018

                if access_locations:

paul@791

1019

                    for access_location in access_locations:

paul@791

1020

                        init_item(self.initialised_accesses, access_location, set)

paul@791

1021

                        self.initialised_accesses[access_location].add(ref)

        # Get a mapping from accesses to affected aliases.

        for accessor_location, access_locations in self.alias_index.items():

paul@735

1026

            for access_location in access_locations:

paul@735

1027

                init_item(self.alias_index_rev, access_location, set)

paul@735

1028

                self.alias_index_rev[access_location].add(accessor_location)

    # Attribute mutation for types.

    def modify_mutated_attributes(self):

        "Identify known, mutated attributes and change their state."

        # Usage-based accesses.

        for usage, all_attrnames in self.assigned_attrs.items():

paul@44

1039

            if not usage:

paul@44

1040

                continue

            for path, name, attrname in all_attrnames:

paul@44

1043

                class_types = self.get_class_types_for_usage(usage)

paul@44

1044

                only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)

paul@44

1045

                module_types = self.get_module_types_for_usage(usage)

                # Detect self usage within methods in order to narrow the scope

paul@44

1048

                # of the mutation.

                t = name == "self" and self.constrain_self_reference(path, class_types, only_instance_types)

paul@44

1051

                if t:

paul@44

1052

                    class_types, only_instance_types, module_types, constrained = t

paul@44

1053

                objects = set(class_types).union(only_instance_types).union(module_types)

                self.mutate_attribute(objects, attrname)

    def mutate_attribute(self, objects, attrname):

        "Mutate static 'objects' with the given 'attrname'."

        for name in objects:

paul@112

1062

            attr = "%s.%s" % (name, attrname)

paul@44

1063

            value = self.importer.get_object(attr)

            # If the value is None, the attribute is

paul@44

1066

            # inherited and need not be set explicitly on

paul@44

1067

            # the class concerned.

            if value:

paul@44

1070

                self.modified_attributes[attr] = value

paul@44

1071

                self.importer.set_object(attr, value.as_var())

    # Simplification of types.

    def get_most_general_types(self, types):

        "Return the most general types for the given 'types'."

        module_types = set()

paul@69

1080

        class_types = set()

        for type in types:

paul@69

1083

            ref = self.importer.identify(type)

paul@69

1084

            if ref.has_kind("<module>"):

paul@69

1085

                module_types.add(type)

paul@69

1086

            else:

paul@69

1087

                class_types.add(type)

        types = set(self.get_most_general_module_types(module_types))

paul@69

1090

        types.update(self.get_most_general_class_types(class_types))

paul@69

1091

        return types

    def get_most_general_class_types(self, class_types):

        "Return the most general types for the given 'class_types'."

        class_types = set(class_types)

paul@44

1098

        to_remove = set()

        for class_type in class_types:

paul@44

1101

            for base in self.importer.classes[class_type]:

paul@44

1102

                base = base.get_origin()

paul@44

1103

                descendants = self.descendants[base]

paul@44

1104

                if base in class_types and descendants.issubset(class_types):

paul@44

1105

                    to_remove.update(descendants)

        class_types.difference_update(to_remove)

paul@44

1108

        return class_types

    def get_most_general_module_types(self, module_types):

        "Return the most general type for the given 'module_types'."

        # Where all modules are provided, an object would provide the same

paul@44

1115

        # attributes.

        if len(module_types) == len(self.importer.modules):

paul@654

1118

            return [self.root_class_type]

paul@44

1119

        else:

paul@44

1120

            return module_types

    # More efficient usage-to-type indexing and retrieval.

    def init_attr_type_indexes(self):

        "Identify the types that can support each attribute name."

        self._init_attr_type_index(self.attr_class_types, self.importer.all_class_attrs)

paul@107

1129

        self._init_attr_type_index(self.attr_instance_types, self.importer.all_instance_attrs, True)

paul@107

1130

        self._init_attr_type_index(self.attr_instance_types, self.importer.all_combined_attrs, False)

paul@44

1131

        self._init_attr_type_index(self.attr_module_types, self.importer.all_module_attrs)

    def _init_attr_type_index(self, attr_types, attrs, assignment=None):

"""

paul@44

1136

        Initialise the 'attr_types' attribute-to-types mapping using the given

paul@44

1137

        'attrs' type-to-attributes mapping.

paul@44

1138

"""

        for name, attrnames in attrs.items():

paul@44

1141

            for attrname in attrnames:

                # Permit general access for certain kinds of object.

                if assignment is None:

paul@107

1146

                    init_item(attr_types, (attrname, False), set)

paul@107

1147

                    init_item(attr_types, (attrname, True), set)

paul@107

1148

                    attr_types[(attrname, False)].add(name)

paul@107

1149

                    attr_types[(attrname, True)].add(name)

                # Restrict attribute assignment for instances.

                else:

paul@107

1154

                    init_item(attr_types, (attrname, assignment), set)

paul@107

1155

                    attr_types[(attrname, assignment)].add(name)

    def get_class_types_for_usage(self, usage):

        "Return names of classes supporting the given 'usage'."

        return self._get_types_for_usage(usage, self.attr_class_types, self.importer.all_class_attrs)

    def get_instance_types_for_usage(self, usage):

"""

paul@88

1166

        Return names of classes whose instances support the given 'usage'

paul@44

1167

        (as either class or instance attributes).

paul@44

1168

"""

        return self._get_types_for_usage(usage, self.attr_instance_types, self.importer.all_combined_attrs)

    def get_module_types_for_usage(self, usage):

        "Return names of modules supporting the given 'usage'."

        return self._get_types_for_usage(usage, self.attr_module_types, self.importer.all_module_attrs)

    def _get_types_for_usage(self, usage, attr_types, attrs):

"""

paul@88

1181

        For the given 'usage' representing attribute usage, return types

paul@44

1182

        recorded in the 'attr_types' attribute-to-types mapping that support

paul@44

1183

        such usage, with the given 'attrs' type-to-attributes mapping used to

paul@44

1184

        quickly assess whether a type supports all of the stated attributes.

paul@44

1185

"""

        # Where no attributes are used, any type would be acceptable.

        if not usage:

paul@44

1190

            return attrs.keys()

        keys = []

paul@107

1193

        for attrname, invocation, assignment in usage:

paul@107

1194

            keys.append((attrname, assignment))

        # Obtain types supporting the first (attribute name, assignment) key...

        types = set(attr_types.get(keys[0]) or [])

        for key in keys[1:]:

            # Record types that support all of the other attributes as well.

            types.intersection_update(attr_types.get(key) or [])

        return types

    def init_combined_attribute_index(self):

        "Initialise a combined index for the detection of invalid attributes."

        self.all_attrnames = set()

paul@501

1213

        for attrs in (self.importer.all_combined_attrs, self.importer.all_module_attrs):

paul@501

1214

            for name, attrnames in attrs.items():

paul@501

1215

                self.all_attrnames.update(attrnames)

    # Reference identification.

    def identify_references(self):

        "Identify references using usage and name reference information."

        # Names with associated attribute usage.

        for location, usages in self.location_index.items():

            # Obtain attribute usage associated with a name, deducing the nature

paul@44

1228

            # of the name. Obtain types only for branches involving attribute

paul@44

1229

            # usage. (In the absence of usage, any type could be involved, but

paul@44

1230

            # then no accesses exist to require knowledge of the type.)

            have_usage = False

paul@44

1233

            have_no_usage_branch = False

            for usage in usages:

paul@44

1236

                if not usage:

paul@44

1237

                    have_no_usage_branch = True

paul@44

1238

                    continue

paul@44

1239

                elif not have_usage:

paul@44

1240

                    self.init_definition_details(location)

paul@44

1241

                    have_usage = True

paul@44

1242

                self.record_types_for_usage(location, usage)

            # Where some usage occurs, but where branches without usage also

paul@44

1245

            # occur, record the types for those branches anyway.

            if have_usage and have_no_usage_branch:

paul@44

1248

                self.init_definition_details(location)

paul@44

1249

                self.record_types_for_usage(location, None)

        # Specific name-based attribute accesses.

        for access_location, accessor_locations in self.access_index.items():

paul@742

1254

            self.record_types_for_access(access_location, accessor_locations)

        # Anonymous references with attribute chains.

        for path, accesses in self.importer.all_attr_accesses.items():

            # Get distinct attribute names.

            all_attrnames = set()

            for attrnames in accesses:

paul@44

1265

                all_attrnames.update(get_attrnames(attrnames))

            # Get attribute and accessor details for each attribute name.

            for attrname in all_attrnames:

paul@791

1270

                access_location = AccessLocation(path, None, attrname, 0)

paul@44

1271

                self.record_types_for_attribute(access_location, attrname)

        # References via constant/identified objects.

        for path, name_accesses in self.importer.all_const_accesses.items():

            # A mapping from the original name and attributes to resolved access

paul@44

1278

            # details.

            for original_access, access in name_accesses.items():

paul@44

1281

                original_name, original_attrnames = original_access

paul@44

1282

                objpath, ref, attrnames = access

                # Build an accessor combining the name and attribute names used.

                original_accessor = tuple([original_name] + original_attrnames.split("."))

                # Direct accesses to attributes.

                if not attrnames:

                    # Build a descriptive location based on the original

paul@44

1293

                    # details, exposing the final attribute name.

                    oa, attrname = original_accessor[:-1], original_accessor[-1]

paul@44

1296

                    oa = ".".join(oa)

                    access_location = AccessLocation(path, oa, attrname, 0)

paul@791

1299

                    accessor_location = Location(path, oa, None, 0)

paul@44

1300

                    self.access_index[access_location] = [accessor_location]

                    self.init_access_details(access_location)

paul@44

1303

                    self.init_definition_details(accessor_location)

                    # Obtain a reference for the accessor in order to properly

paul@44

1306

                    # determine its type.

                    if ref.get_kind() != "<instance>":

paul@44

1309

                        objpath = ref.get_origin()

                    objpath = objpath.rsplit(".", 1)[0]

                    # Where the object name conflicts with the module

paul@44

1314

                    # providing it, obtain the module details.

                    if objpath in self.importer.modules:

paul@44

1317

                        accessor = Reference("<module>", objpath)

paul@44

1318

                    else:

paul@44

1319

                        accessor = self.importer.get_object(objpath)

                    self.referenced_attrs[access_location] = [(accessor.get_kind(), accessor.get_origin(), ref)]

paul@44

1322

                    self.access_constrained.add(access_location)

                    class_types, instance_types, module_types = accessor.get_types()

paul@44

1325

                    self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True)

                else:

                    # Build a descriptive location based on the original

paul@64

1330

                    # details, employing the first remaining attribute name.

                    l = get_attrnames(attrnames)

paul@64

1333

                    attrname = l[0]

                    oa = original_accessor[:-len(l)]

paul@64

1336

                    oa = ".".join(oa)

                    access_location = AccessLocation(path, oa, attrnames, 0)

paul@791

1339

                    accessor_location = Location(path, oa, None, 0)

paul@64

1340

                    self.access_index[access_location] = [accessor_location]

                    self.init_access_details(access_location)

paul@64

1343

                    self.init_definition_details(accessor_location)

                    class_types, instance_types, module_types = ref.get_types()

                    self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, True)

paul@64

1348

                    self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True)

                # Define mappings between the original and access locations

paul@679

1351

                # so that translation can work from the source details.

                original_location = AccessLocation(path, original_name, original_attrnames, 0)

                if original_location != access_location:

paul@64

1356

                    self.const_accesses[original_location] = access_location

paul@67

1357

                    self.const_accesses_rev[access_location] = original_location

        # Propagate alias-related information.

        affected_aliases = set(self.alias_index.keys())

        while True:

            # Aliased name definitions. All aliases with usage will have been

paul@735

1366

            # defined, but they may be refined according to referenced accesses.

            updated_aliases = set()

            for location in affected_aliases:

paul@735

1371

                if self.record_types_for_alias(location):

paul@735

1372

                    updated_aliases.add(location)

            # Define accesses employing aliases.

            alias_accesses = set()

paul@742

1377

            affected_aliases = set()

            for alias in updated_aliases:

                # Access affected by the alias.

                if self.access_index_rev.has_key(alias):

paul@742

1384

                    alias_accesses.update(self.access_index_rev[alias])

                # Another alias affected by the alias.

                elif self.alias_index_rev.has_key(alias):

paul@742

1389

                    affected_aliases.update(self.alias_index_rev[alias])

            # Update accesses employing aliases.

            updated_accesses = set()

            for access_location in alias_accesses:

paul@735

1396

                if self.record_types_for_access(access_location, self.access_index[access_location]):

paul@735

1397

                    updated_accesses.add(access_location)

            # Determine which aliases are affected by the updated accesses.

            for access_location in updated_accesses:

paul@735

1402

                if self.alias_index_rev.has_key(access_location):

paul@735

1403

                    affected_aliases.update(self.alias_index_rev[access_location])

            if not affected_aliases:

paul@735

1406

                break

    def constrain_types(self, path, class_types, instance_types, module_types):

"""

paul@44

1411

        Using the given 'path' to an object, constrain the given 'class_types',

paul@44

1412

        'instance_types' and 'module_types'.

        Return the class, instance, module types plus whether the types are

paul@44

1415

        constrained to a specific kind of type.

paul@44

1416

"""

        ref = self.importer.identify(path)

paul@44

1419

        if ref:

            # Constrain usage suggestions using the identified object.

            if ref.has_kind("<class>"):

paul@44

1424

                return (

paul@44

1425

                    set(class_types).intersection([ref.get_origin()]), [], [], True

            elif ref.has_kind("<module>"):

paul@44

1428

                return (

paul@44

1429

                    [], [], set(module_types).intersection([ref.get_origin()]), True

        return class_types, instance_types, module_types, False

    def get_target_types(self, location, usage):

"""

paul@44

1437

        Return the class, instance and module types constrained for the name at

paul@44

1438

        the given 'location' exhibiting the given 'usage'. Whether the types

paul@44

1439

        have been constrained using contextual information is also indicated,

paul@44

1440

        plus whether the types have been constrained to a specific kind of type.

paul@44

1441

"""

        have_assignments = get_assigned_attributes(usage)

        # Detect any initialised name for the location.

        if location.name:

paul@742

1448

            refs = self.get_initialised_name(location)

paul@742

1449

            if refs:

paul@44

1450

                (class_types, only_instance_types, module_types,

paul@742

1451

                    _function_types, _var_types) = separate_types(refs)

paul@107

1452

                return class_types, only_instance_types, module_types, True, have_assignments

        # Retrieve the recorded types for the usage.

        class_types = self.get_class_types_for_usage(usage)

paul@44

1457

        only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)

paul@44

1458

        module_types = self.get_module_types_for_usage(usage)

        # Merge usage deductions with observations to obtain reference types

paul@44

1461

        # for names involved with attribute accesses.

        if not location.name:

paul@107

1464

            return class_types, only_instance_types, module_types, False, have_assignments

        # Obtain references to known objects.

        path = get_name_path(location.path, location.name)

        class_types, only_instance_types, module_types, constrained_specific = \

paul@44

1471

            self.constrain_types(path, class_types, only_instance_types, module_types)

        if constrained_specific:

paul@107

1474

            return class_types, only_instance_types, module_types, constrained_specific, \

paul@107

1475

                constrained_specific or have_assignments

        # Constrain "self" references.

        class_name = self.in_method(location.path)

paul@816

1480

        constrained = False

        if class_name and location.name == "self":

            # Constrain the types to the class's hierarchy.

            class_types, only_instance_types, module_types, constrained = \

paul@816

1487

                self.constrain_to_class(class_name, class_types, only_instance_types)

            # Without any deduced types, produce an error.

            if not class_types and not only_instance_types:

paul@350

1492

                raise DeduceError("In %s, usage {%s} is not directly supported by class %s or its instances." %

paul@791

1493

                                  (location.path, encode_usage(usage), class_name))

            # If the class defining the method does not appear amongst the

paul@816

1496

            # types supporting the usage, remove the constrained status of the

paul@816

1497

            # name.

            constrained = constrained and (class_name in class_types or class_name in only_instance_types)

        return class_types, only_instance_types, module_types, constrained, have_assignments

    def constrain_self_reference(self, unit_path, class_types, only_instance_types):

"""

paul@44

1506

        Where the name "self" appears in a method, attempt to constrain the

paul@44

1507

        classes involved.

        Return the class, instance, module types plus whether the types are

paul@44

1510

        constrained.

paul@44

1511

"""

        class_name = self.in_method(unit_path)

        if not class_name:

paul@44

1516

            return None

        return self.constrain_to_class(class_name, class_types, only_instance_types)

    def constrain_to_class(self, class_name, class_types, only_instance_types):

"""

paul@816

1523

        Constrain to 'class_name' and its descendants, the given 'class_types'

paul@816

1524

        and 'only_instance_types'.

        Return the class, instance, module types plus whether the types are

paul@816

1527

        constrained.

paul@816

1528

"""

        classes = set([class_name])

paul@44

1531

        classes.update(self.get_descendants_for_class(class_name))

        # Note that only instances will be expected for these references but

paul@44

1534

        # either classes or instances may provide the attributes.

        return (

paul@44

1537

            set(class_types).intersection(classes),

paul@44

1538

            set(only_instance_types).intersection(classes),

paul@44

1539

            [], True

    def in_method(self, path):

        "Return whether 'path' refers to a method."

        t = path.rsplit(".", 1)

paul@816

1547

        if len(t) == 1:

paul@816

1548

            return False

        class_name, method_name = t

paul@274

1551

        return class_name != "__builtins__.core.type" and self.importer.classes.has_key(class_name) and class_name

    def init_reference_details(self, location):

        "Initialise reference-related details for 'location'."

        self.init_definition_details(location)

paul@44

1558

        self.init_access_details(location)

    def init_definition_details(self, location):

        "Initialise name definition details for 'location'."

        self.accessor_class_types[location] = set()

paul@44

1565

        self.accessor_instance_types[location] = set()

paul@44

1566

        self.accessor_module_types[location] = set()

paul@44

1567

        self.provider_class_types[location] = set()

paul@44

1568

        self.provider_instance_types[location] = set()

paul@44

1569

        self.provider_module_types[location] = set()

    def init_access_details(self, location):

        "Initialise access details at 'location'."

        self.referenced_attrs[location] = {}

    def record_types_for_access(self, access_location, accessor_locations):

"""

paul@44

1580

        Define types for the 'access_location' associated with the given

paul@735

1581

        'accessor_locations'. Return whether referenced attributes were updated.

paul@44

1582

"""

        attrname = access_location.get_attrname()

paul@91

1585

        if not attrname:

paul@735

1586

            return False

        invocation = access_location in self.reference_invocations

paul@720

1589

        assignment = access_location in self.reference_assignments

        # Collect all suggested types for the accessors. Accesses may

paul@44

1592

        # require accessors from of a subset of the complete set of types.

        class_types = set()

paul@44

1595

        module_types = set()

paul@44

1596

        instance_types = set()

        constrained = True

        old_referenced_attrs = self.referenced_attrs.get(access_location)

        for location in accessor_locations:

            # Use the type information deduced for names from above.

            if self.accessor_class_types.has_key(location):

paul@44

1607

                class_types.update(self.accessor_class_types[location])

paul@44

1608

                module_types.update(self.accessor_module_types[location])

paul@44

1609

                instance_types.update(self.accessor_instance_types[location])

            # Where accesses are associated with assignments but where no

paul@44

1612

            # attribute usage observations have caused such an association,

paul@44

1613

            # the attribute name is considered by itself.

            else:

paul@44

1616

                self.init_definition_details(location)

paul@720

1617

                self.record_types_for_usage(location, [(attrname, invocation, assignment)])

            constrained = location in self.accessor_constrained and constrained

        self.init_access_details(access_location)

paul@44

1622

        self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, constrained)

        # Return whether the referenced attributes have changed.

        return old_referenced_attrs != self.referenced_attrs.get(access_location)

    def record_types_for_usage(self, accessor_location, usage):

"""

paul@44

1631

        Record types for the given 'accessor_location' according to the given

paul@44

1632

        'usage' observations which may be None to indicate an absence of usage.

paul@44

1633

"""

        (class_types,

paul@44

1636

         instance_types,

paul@44

1637

         module_types,

paul@44

1638

         constrained,

paul@44

1639

         constrained_specific) = self.get_target_types(accessor_location, usage)

        invocations = get_invoked_attributes(usage)

        self.record_reference_types(accessor_location, class_types, instance_types,

paul@107

1644

            module_types, constrained, constrained_specific, invocations)

    def record_types_for_attribute(self, access_location, attrname):

"""

paul@44

1649

        Record types for the 'access_location' employing only the given

paul@44

1650

        'attrname' for type deduction.

paul@44

1651

"""

        (class_types,

paul@102

1654

         only_instance_types,

paul@102

1655

         module_types) = self.get_types_for_attribute(attrname)

        self.init_reference_details(access_location)

        self.identify_reference_attributes(access_location, attrname, class_types, only_instance_types, module_types, False)

paul@102

1660

        self.record_reference_types(access_location, class_types, only_instance_types, module_types, False)

    def get_types_for_attribute(self, attrname):

        "Return class, instance-only and module types supporting 'attrname'."

        usage = ((attrname, False, False),)

        class_types = self.get_class_types_for_usage(usage)

paul@44

1669

        only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)

paul@44

1670

        module_types = self.get_module_types_for_usage(usage)

        return class_types, only_instance_types, module_types

    def record_types_for_alias(self, accessor_location):

"""

paul@44

1677

        Define types for the 'accessor_location' not having associated usage.

paul@735

1678

        Return whether the types were updated.

paul@44

1679

"""

        have_access = self.provider_class_types.has_key(accessor_location)

        # With an access, attempt to narrow the existing selection of provider

paul@709

1684

        # types. Invocations attempt to find return value information, with

paul@709

1685

        # instance return values also yielding class providers (since attributes

paul@709

1686

        # on instances could be provided by classes).

        if have_access:

paul@44

1689

            provider_class_types = self.provider_class_types[accessor_location]

paul@44

1690

            provider_instance_types = self.provider_instance_types[accessor_location]

paul@44

1691

            provider_module_types = self.provider_module_types[accessor_location]

            accessor_class_types = self.accessor_class_types[accessor_location]

paul@721

1694

            accessor_instance_types = self.accessor_instance_types[accessor_location]

paul@721

1695

            accessor_module_types = self.accessor_module_types[accessor_location]

            # Find details for any corresponding access.

            new_provider_class_types = set()

paul@721

1700

            new_provider_instance_types = set()

paul@721

1701

            new_provider_module_types = set()

            new_accessor_class_types = set()

paul@721

1704

            new_accessor_instance_types = set()

paul@721

1705

            new_accessor_module_types = set()

            refs = set()

            for access_location in self.alias_index[accessor_location]:

paul@791

1710

                attrnames = access_location.attrnames

paul@791

1711

                invocation = self.reference_invocations.has_key(access_location)

                attrnames = attrnames and attrnames.split(".")

paul@715

1714

                remaining = attrnames and len(attrnames) > 1

                # Alias has remaining attributes: reference details do not

paul@715

1717

                # correspond to the accessor; the remaining attributes would

paul@715

1718

                # need to be traversed first.

                if remaining:

paul@735

1721

                    return False

                # Alias references an attribute access.

                if attrnames:

                    # Obtain references and attribute types for the access.

                    attrs = self.get_references_for_access(access_location)

                    if attrs:

                        # Invocations converting class accessors to instances do

paul@744

1734

                        # not change the nature of class providers.

                        provider_attrs = self.convert_invocation_providers(attrs, invocation)

                        # Accessors are updated separately, employing invocation

paul@744

1739

                        # result details.

                        accessor_attrs = self.convert_invocations(attrs, invocation)

                # Alias references a name, not an access.

                else:

paul@742

1746

                    # Attempt to refine the types using initialised names or

paul@742

1747

                    # accessors.

                    attrs = self.get_initialised_access(access_location)

                    if attrs:

paul@721

1752

                        provider_attrs = self.convert_invocation_providers(attrs, invocation)

paul@721

1753

                        accessor_attrs = self.convert_invocations(attrs, invocation)

paul@742

1754

                    else:

paul@742

1755

                        provider_attrs = self.get_provider_references(access_location)

paul@742

1756

                        attrs = accessor_attrs = self.get_accessor_references(access_location)

                # Where no specific attributes are defined, do not attempt

paul@744

1759

                # to refine the alias's types.

                if not attrs:

paul@744

1762

                    return False

                (class_types, instance_types, module_types, function_types,

paul@744

1765

                    var_types) = separate_types(provider_attrs)

                # Where non-accessor types are found, do not attempt to refine

paul@744

1768

                # the defined accessor types.

                if function_types or var_types:

paul@744

1771

                    return False

                class_types = set(provider_class_types).intersection(class_types)

paul@744

1774

                instance_types = set(provider_instance_types).intersection(instance_types)

paul@744

1775

                module_types = set(provider_module_types).intersection(module_types)

                new_provider_class_types.update(class_types)

paul@744

1778

                new_provider_instance_types.update(instance_types)

paul@744

1779

                new_provider_module_types.update(module_types)

                (class_types, instance_types, module_types, function_types,

paul@744

1782

                    var_types) = separate_types(accessor_attrs)

                class_types = set(accessor_class_types).intersection(class_types)

paul@744

1785

                instance_types = set(accessor_instance_types).intersection(instance_types)

paul@744

1786

                module_types = set(accessor_module_types).intersection(module_types)

                new_accessor_class_types.update(class_types)

paul@744

1789

                new_accessor_instance_types.update(instance_types)

paul@744

1790

                new_accessor_module_types.update(module_types)

                refs.update(accessor_attrs)

                # Update the alias relationships for invocations.

                self.update_alias_accesses(access_location, attrs)

            # Record refined type details for the alias as an accessor.

            self.init_definition_details(accessor_location)

paul@721

1801

            self.update_provider_types(accessor_location, new_provider_class_types, new_provider_instance_types, new_provider_module_types)

paul@721

1802

            self.update_accessor_types(accessor_location, new_accessor_class_types, new_accessor_instance_types, new_accessor_module_types)

            # Record reference details for the alias separately from accessors.

            self.referenced_objects[accessor_location] = refs

            return new_accessor_class_types != accessor_class_types or \

paul@735

1809

                   new_accessor_instance_types != accessor_instance_types or \

paul@735

1810

                   new_accessor_module_types != accessor_module_types

        # Without an access, attempt to identify references for the alias.

paul@709

1813

        # Invocations convert classes to instances and also attempt to find

paul@709

1814

        # return value information.

        else:

paul@44

1817

            refs = set()

            for access_location in self.alias_index[accessor_location]:

paul@791

1820

                attrnames = access_location.attrnames

paul@791

1821

                invocation = self.reference_invocations.has_key(access_location)

                attrnames = attrnames and attrnames.split(".")

paul@683

1824

                remaining = attrnames and len(attrnames) > 1

                # Alias has remaining attributes: reference details do not

paul@683

1827

                # correspond to the accessor; the remaining attributes would

paul@683

1828

                # need to be traversed first.

                if remaining:

paul@735

1831

                    return False

                # Alias references an attribute access.

                if attrnames:

                    # Obtain references and attribute types for the access.

                    attrs = self.get_references_for_access(access_location)

                # Alias references a name, not an access.

                else:

                    # Obtain initialiser information.

                    attrs = self.get_initialised_access(access_location)

                    if attrs:

paul@742

1850

                        provider_attrs = self.convert_invocation_providers(attrs, invocation)

paul@742

1851

                        accessor_attrs = self.convert_invocations(attrs, invocation)

paul@742

1852

                    else:

paul@742

1853

                        provider_attrs = self.get_provider_references(access_location)

paul@742

1854

                        attrs = accessor_attrs = self.get_accessor_references(access_location)

                # Where no further information is found, do not attempt to

paul@744

1857

                # refine the defined accessor types.

                if not attrs:

paul@744

1860

                    return False

                refs.update(self.convert_invocations(attrs, invocation))

                # Update the alias relationships for invocations.

                self.update_alias_accesses(access_location, attrs)

            # Record refined type details for the alias as an accessor.

            (class_types, instance_types, module_types, function_types,

paul@742

1871

                var_types) = separate_types(refs)

            # Where non-accessor types are found, do not attempt to refine

paul@742

1874

            # the defined accessor types.

            if not function_types and not var_types:

paul@742

1877

                self.init_definition_details(accessor_location)

paul@742

1878

                self.update_provider_types(accessor_location, class_types + instance_types, class_types + instance_types, module_types)

paul@742

1879

                self.update_accessor_types(accessor_location, class_types, instance_types, module_types)

            # Record reference details for the alias separately from accessors.

            self.referenced_objects[accessor_location] = refs

            return True

    def update_alias_accesses(self, access_location, refs):

"""

paul@742

1890

        Record 'access_location' as a location affected by the return values of

paul@742

1891

        'refs' if an invocation is involved.

paul@742

1892

"""

        if not self.reference_invocations.has_key(access_location):

paul@742

1895

            return

        for ref in refs:

            # Initialising accesses originate from the return values.

            key = (ref.get_origin(), "$return")

paul@742

1902

            self._update_alias_accesses(access_location, key, self.importer.all_initialised_names)

paul@742

1903

            self._update_alias_accesses(access_location, key, self.importer.all_aliased_names)

    def _update_alias_accesses(self, access_location, key, names):

"""

paul@742

1908

        Make each return value provide information to the given

paul@742

1909

        'access_location', using 'key' to reference the return value and 'names'

paul@742

1910

        as the collection of definitions.

paul@742

1911

"""

        versions = names.get(key)

paul@742

1914

        if not versions:

paul@742

1915

            return

        path, name = key

        for version in versions.keys():

paul@791

1920

            location = Location(path, name, None, version)

paul@742

1921

            l = init_item(self.alias_index_rev, location, set)

paul@742

1922

            l.add(access_location)

            l = init_item(self.alias_index, access_location, set)

paul@742

1925

            l.add(location)

    def get_references_for_access(self, access_location):

        "Return the references identified for 'access_location'."

        attrs = set()

paul@708

1932

        for attrtype, object_type, attr in self.referenced_attrs[access_location]:

paul@843

1933

            attrs.add(attr)

paul@708

1934

        return attrs

    def convert_invocation_providers(self, refs, invocation):

"""

paul@709

1939

        Convert 'refs' to providers corresponding to the results of invoking

paul@709

1940

        each of the given references, if 'invocation' is set to a true value.

paul@709

1941

"""

        if not invocation:

paul@709

1944

            return refs

        providers = set()

        for ref in refs:

paul@742

1949

            invocation_providers = self.convert_accessors_to_providers(self.convert_invocation_provider(ref))

paul@742

1950

            providers.update(invocation_providers)

        return self.references_or_var(providers)

    def convert_accessors_to_providers(self, refs):

        "Convert accessor 'refs' to provider references."

        providers = set()

paul@742

1959

        for ref in refs:

paul@742

1960

            if ref.has_kind("<instance>"):

paul@742

1961

                providers.add(Reference("<class>", ref.get_origin()))

paul@742

1962

            providers.add(ref)

paul@709

1963

        return providers

    def convert_invocation_provider(self, ref):

        "Convert 'ref' to a provider appropriate to its invocation result."

        if ref:

paul@712

1970

            if ref.has_kind("<class>"):

paul@742

1971

                return [ref]

paul@712

1972

            elif ref.has_kind("<function>"):

paul@731

1973

                return self.convert_function_invocation(ref)

        return [Reference("<var>")]

    def convert_invocations(self, refs, invocation):

"""

paul@709

1980

        Convert 'refs' to invocation results if 'invocation' is set to a true

paul@709

1981

        value.

paul@709

1982

"""

        if not invocation:

paul@739

1985

            return refs

        invocation_refs = set()

        for ref in refs:

paul@739

1990

            invocation_refs.update(self.convert_invocation(ref))

        return self.references_or_var(invocation_refs)

    def convert_invocation(self, ref):

        "Convert 'ref' to its invocation result."

        if ref:

paul@712

1999

            if ref.has_kind("<class>"):

paul@739

2000

                return [ref.instance_of()]

paul@712

2001

            elif ref.has_kind("<function>"):

paul@731

2002

                return self.convert_function_invocation(ref)

        return [Reference("<var>")]

    def convert_function_invocation(self, ref):

        "Convert the function 'ref' to its return value reference."

        initialisers = self.importer.all_initialised_names.get((ref.get_origin(), "$return"))

paul@742

2011

        aliases = self.importer.all_aliased_names.get((ref.get_origin(), "$return"))

        if initialisers and not aliases:

paul@742

2014

            return set(initialisers.values())

        return [Reference("<var>")]

    def references_or_var(self, refs):

        var = Reference("<var>")

        if var in refs:

paul@742

2023

            return set([var])

paul@742

2024

        else:

paul@742

2025

            return refs

    def get_initialised_name(self, location):

"""

paul@791

2030

        Return references for any initialised names at 'location', or None if no

paul@791

2031

        such references exist.

paul@44

2032

"""

        ref = self.initialised_names.get(location)

paul@791

2035

        return ref and [ref] or None

    def get_initialised_access(self, location):

"""

paul@791

2040

        Return references for any initialised names supplying the given access

paul@791

2041

        'location', or None if no such references exist.

paul@791

2042

"""

        if location.access_number is not None:

paul@791

2045

            return self.initialised_accesses.get(location)

paul@742

2046

        else:

paul@791

2047

            return self.get_initialised_name(location)

    def get_accessor_references(self, access_location):

"""

paul@742

2052

        Return references corresponding to accessor details at the given

paul@742

2053

        'access_location'.

paul@742

2054

"""

        if self.accessor_class_types.has_key(access_location):

paul@742

2057

            class_types = self.accessor_class_types[access_location]

paul@742

2058

            instance_types = self.accessor_instance_types[access_location]

paul@742

2059

            module_types = self.accessor_module_types[access_location]

paul@742

2060

            return combine_types(class_types, instance_types, module_types)

paul@742

2061

        else:

paul@742

2062

            return None

    def get_provider_references(self, access_location):

"""

paul@742

2067

        Return references corresponding to provider details at the given

paul@742

2068

        'access_location'.

paul@742

2069

"""

        if self.provider_class_types.has_key(access_location):

paul@742

2072

            class_types = self.provider_class_types[access_location]

paul@742

2073

            instance_types = self.provider_instance_types[access_location]

paul@742

2074

            module_types = self.provider_module_types[access_location]

paul@742

2075

            return combine_types(class_types, instance_types, module_types)

paul@44

2076

        else:

paul@44

2077

            return None

    def record_reference_types(self, location, class_types, instance_types,

paul@90

2080

        module_types, constrained, constrained_specific=False, invocations=None):

"""

paul@44

2083

        Associate attribute provider types with the given 'location', consisting

paul@44

2084

        of the given 'class_types', 'instance_types' and 'module_types'.

        If 'constrained' is indicated, the constrained nature of the accessor is

paul@44

2087

        recorded for the location.

        If 'constrained_specific' is indicated using a true value, instance types

paul@44

2090

        will not be added to class types to permit access via instances at the

paul@44

2091

        given location. This is only useful where a specific accessor is known

paul@44

2092

        to be a class.

        If 'invocations' is given, the given attribute names indicate those

paul@105

2095

        which are involved in invocations. Such invocations, if involving

paul@105

2096

        functions, will employ those functions as bound methods and will

paul@105

2097

        therefore not support classes as accessors, only instances of such

paul@105

2098

        classes.

        Note that the specified types only indicate the provider types for

paul@44

2101

        attributes, whereas the recorded accessor types indicate the possible

paul@44

2102

        types of the actual objects used to access attributes.

paul@44

2103

"""

        # Update the type details for the location.

        self.update_provider_types(location, class_types, instance_types, module_types)

        # Class types support classes and instances as accessors.

paul@44

2110

        # Instance-only and module types support only their own kinds as

paul@44

2111

        # accessors.

        path, name = location.path, location.name

        if invocations:

paul@90

2116

            class_only_types = self.filter_for_invocations(class_types, invocations)

paul@90

2117

        else:

paul@90

2118

            class_only_types = class_types

        # However, the nature of accessors can be further determined.

paul@44

2121

        # Any self variable may only refer to an instance.

        if name != "self" or not self.in_method(path):

paul@90

2124

            self.accessor_class_types[location].update(class_only_types)

        if not constrained_specific:

paul@44

2127

            self.accessor_instance_types[location].update(class_types)

        self.accessor_instance_types[location].update(instance_types)

        if name != "self" or not self.in_method(path):

paul@44

2132

            self.accessor_module_types[location].update(module_types)

        if constrained:

paul@67

2135

            self.accessor_constrained.add(location)

        # Complain about situations where no types are valid but where a

paul@840

2138

        # specific, known accessor type has been indicated. This absence of

paul@840

2139

        # suitable types is likely to occur when the presence of invocations

paul@840

2140

        # filters out the accessor type.

        if not class_only_types and not instance_types and not module_types and \

paul@840

2143

           invocations and constrained_specific:

            raise DeduceError("In %s, methods of class %s cannot be called directly." %

paul@840

2146

                (path, name))

    def update_provider_types(self, location, class_types, instance_types, module_types):

"""

paul@721

2151

        Update provider types for the given 'location', adding 'class_types',

paul@721

2152

        'instance_types' and 'module_types' to those already stored.

paul@721

2153

"""

        self.provider_class_types[location].update(class_types)

paul@721

2156

        self.provider_instance_types[location].update(instance_types)

paul@721

2157

        self.provider_module_types[location].update(module_types)

    def update_accessor_types(self, location, class_types, instance_types, module_types):

"""

paul@721

2162

        Update accessor types for the given 'location', adding 'class_types',

paul@721

2163

        'instance_types' and 'module_types' to those already stored.

paul@721

2164

"""

        self.accessor_class_types[location].update(class_types)

paul@721

2167

        self.accessor_instance_types[location].update(instance_types)

paul@721

2168

        self.accessor_module_types[location].update(module_types)

    def filter_for_invocations(self, class_types, attrnames):

"""

paul@90

2173

        From the given 'class_types', identify methods for the given

paul@90

2174

        'attrnames' that are being invoked, returning a filtered collection of

paul@90

2175

        class types.

        This method may be used to remove class types from consideration where

paul@553

2178

        their attributes are methods that are directly invoked: method

paul@553

2179

        invocations must involve instance accessors.

paul@90

2180

"""

        to_filter = set()

        for class_type in class_types:

paul@90

2185

            for attrname in attrnames:

                # Attempt to obtain a class attribute of the given name. This

paul@553

2188

                # may return an attribute provided by an ancestor class.

                ref = self.importer.get_class_attribute(class_type, attrname)

paul@90

2191

                parent_class = ref and ref.parent()

                # If such an attribute is a method and would be available on

paul@553

2194

                # the given class, record the class for filtering.

                if ref and ref.has_kind("<function>") and (

paul@90

2197

                   parent_class == class_type or

paul@90

2198

                   class_type in self.descendants[parent_class]):

                    to_filter.add(class_type)

paul@90

2201

                    break

        return set(class_types).difference(to_filter)

    def identify_reference_attributes(self, location, attrname, class_types, instance_types, module_types, constrained):

"""

paul@44

2208

        Identify reference attributes, associating them with the given

paul@44

2209

        'location', identifying the given 'attrname', employing the given

paul@44

2210

        'class_types', 'instance_types' and 'module_types'.

        If 'constrained' is indicated, the constrained nature of the access is

paul@44

2213

        recorded for the location.

paul@44

2214

"""

        # Record the referenced objects.

        self.referenced_attrs[location] = \

paul@555

2219

            self._identify_reference_attribute(location, attrname, class_types, instance_types, module_types)

        if constrained:

paul@44

2222

            self.access_constrained.add(location)

    def _identify_reference_attribute(self, location, attrname, class_types, instance_types, module_types):

"""

paul@555

2227

        Identify the reference attribute at the given access 'location', using

paul@555

2228

        the given 'attrname', and employing the given 'class_types',

paul@555

2229

        'instance_types' and 'module_types'.

paul@44

2230

"""

        attrs = set()

        # The class types expose class attributes either directly or via

paul@44

2235

        # instances.

        for object_type in class_types:

paul@44

2238

            ref = self.importer.get_class_attribute(object_type, attrname)

paul@555

2239

            if ref and self.is_compatible_callable(location, object_type, ref):

paul@44

2240

                attrs.add(("<class>", object_type, ref))

            # Add any distinct instance attributes that would be provided

paul@44

2243

            # by instances also providing indirect class attribute access.

            for ref in self.importer.get_instance_attributes(object_type, attrname):

paul@555

2246

                if self.is_compatible_callable(location, object_type, ref):

paul@555

2247

                    attrs.add(("<instance>", object_type, ref))

        # The instance-only types expose instance attributes, but although

paul@44

2250

        # classes are excluded as potential accessors (since they do not provide

paul@44

2251

        # the instance attributes), the class types may still provide some

paul@44

2252

        # attributes.

        for object_type in instance_types:

paul@44

2255

            instance_attrs = self.importer.get_instance_attributes(object_type, attrname)

            if instance_attrs:

paul@44

2258

                for ref in instance_attrs:

paul@555

2259

                    if self.is_compatible_callable(location, object_type, ref):

paul@555

2260

                        attrs.add(("<instance>", object_type, ref))

paul@44

2261

            else:

paul@44

2262

                ref = self.importer.get_class_attribute(object_type, attrname)

paul@555

2263

                if ref and self.is_compatible_callable(location, object_type, ref):

paul@44

2264

                    attrs.add(("<class>", object_type, ref))

        # Module types expose module attributes for module accessors.

        for object_type in module_types:

paul@44

2269

            ref = self.importer.get_module_attribute(object_type, attrname)

paul@555

2270

            if ref and self.is_compatible_callable(location, object_type, ref):

paul@44

2271

                attrs.add(("<module>", object_type, ref))

        return attrs

    def is_compatible_callable(self, location, object_type, ref):

"""

paul@555

2278

        Return whether any invocation at 'location' involving an attribute of

paul@555

2279

        'object_type' identified by 'ref' is compatible with any arguments used.

paul@555

2280

"""

        invocation = self.reference_invocations.get(location)

paul@557

2283

        if invocation is None:

paul@555

2284

            return True

        objpath = ref.get_origin()

paul@555

2287

        if not objpath:

paul@555

2288

            return True

        parameters = self.importer.function_parameters.get(objpath)

paul@555

2291

        if not parameters:

paul@555

2292

            return True

        defaults = self.importer.function_defaults.get(objpath)

paul@557

2295

        arguments, keywords = invocation

paul@557

2296

        names = set(parameters)

        # Determine whether the specified arguments are

paul@555

2299

        # compatible with the callable signature.

        if arguments >= len(parameters) - len(defaults) and \

paul@557

2302

           arguments <= len(parameters) and \

paul@557

2303

           names.issuperset(keywords):

            return True

paul@555

2306

        else:

paul@555

2307

            init_item(self.reference_invocations_unsuitable, location, set)

paul@555

2308

            self.reference_invocations_unsuitable[location].add(ref)

paul@555

2309

            return False

    # Attribute access plan formulation.

    class_tests = (

paul@237

2314

        ("guarded", "specific", "type"),

paul@237

2315

        ("guarded", "common", "type"),

paul@237

2316

        ("test", "specific", "type"),

paul@237

2317

        ("test", "common", "type"),

    def get_access_plan(self, location):

"""

paul@77

2323

        Return details of the access at the given 'location'. The details are as

paul@77

2324

        follows:

         * the initial accessor (from which accesses will be performed if no

paul@77

2327

           computed static accessor is found)

paul@77

2328

         * details of any test required on the initial accessor

paul@77

2329

         * details of any type employed by the test

paul@77

2330

         * any static accessor (from which accesses will be performed in

paul@77

2331

           preference to the initial accessor)

paul@77

2332

         * attributes needing to be traversed from the base that yield

paul@77

2333

           unambiguous objects

paul@98

2334

         * access modes for each of the unambiguously-traversed attributes

paul@77

2335

         * remaining attributes needing to be tested and traversed

paul@77

2336

         * details of the context

paul@102

2337

         * any test to apply to the context

paul@653

2338

         * the method of obtaining the first attribute

paul@77

2339

         * the method of obtaining the final attribute

paul@77

2340

         * any static final attribute

paul@325

2341

         * the kinds of objects providing the final attribute

paul@77

2342

"""

        const_access = self.const_accesses_rev.get(location)

        path, name, attrnames = location.path, location.name, location.attrnames

paul@75

2347

        remaining = attrnames.split(".")

paul@75

2348

        attrname = remaining[0]

        # Special case for the ubiquitous __class__ attribute.

        ubiquitous = attrname == "__class__"

        # Obtain reference, provider and provider kind information.

        attrs = self.reference_all_attrs[location]

paul@687

2357

        provider_types = self.reference_all_providers[location]

paul@687

2358

        provider_kinds = self.reference_all_provider_kinds[location]

        # Obtain accessor type and kind information.

        accessor_types = self.reference_all_accessor_types[location]

paul@67

2363

        accessor_general_types = self.reference_all_accessor_general_types[location]

paul@824

2364

        accessor_kinds = set(get_kinds(accessor_general_types))

        # Determine any guard or test requirements.

        constrained = location in self.access_constrained

paul@70

2369

        test = self.reference_test_types[location]

paul@77

2370

        test_type = self.reference_test_accessor_type.get(location)

        # Determine the accessor and provider properties.

        class_accessor = "<class>" in accessor_kinds

paul@67

2375

        module_accessor = "<module>" in accessor_kinds

paul@67

2376

        instance_accessor = "<instance>" in accessor_kinds

paul@67

2377

        provided_by_class = "<class>" in provider_kinds

paul@67

2378

        provided_by_instance = "<instance>" in provider_kinds

        # Determine how attributes may be accessed relative to the accessor.

        object_relative = ubiquitous or class_accessor or module_accessor or provided_by_instance

paul@890

2383

        class_relative = not ubiquitous and instance_accessor and provided_by_class

        # Identify the last static attribute for context acquisition.

        base = None

paul@67

2388

        dynamic_base = None

        # Constant accesses have static providers.

        if const_access:

paul@687

2393

            base = len(provider_types) == 1 and first(provider_types)

        # Name-based accesses.

        elif name:

paul@65

2398

            ref = self.importer.identify("%s.%s" % (path, name))

            # Constant accessors are static.

            if ref and ref.static():

paul@65

2403

                base = ref.get_origin()

            # Usage of previously-generated guard and test details.

            elif test[:2] == ("constrained", "specific"):

paul@67

2408

                ref = first(accessor_types)

            elif test[:2] == ("constrained", "common"):

paul@67

2411

                ref = first(accessor_general_types)

            elif test[:2] == ("guarded", "specific"):

paul@67

2414

                ref = first(accessor_types)

            elif test[:2] == ("guarded", "common"):

paul@67

2417

                ref = first(accessor_general_types)

            # For attribute-based tests, tentatively identify a dynamic base.

paul@70

2420

            # Such tests allow single or multiple kinds of a type.

            elif test[0] == "test" and test[1] in ("common", "specific"):

paul@77

2423

                dynamic_base = test_type

            # Static accessors.

            if not base and test in self.class_tests:

paul@70

2428

                base = ref and ref.get_origin() or dynamic_base

            # Accessors that are not static but whose nature is determined.

            elif not base and ref:

paul@67

2433

                dynamic_base = ref.get_origin()

        # Determine initial accessor details.

        accessor = base or dynamic_base

paul@102

2438

        accessor_kind = len(accessor_kinds) == 1 and first(accessor_kinds) or None

paul@102

2439

        provider_kind = len(provider_kinds) == 1 and first(provider_kinds) or None

        # Traverse remaining attributes.

        traversed = []

paul@96

2444

        traversal_modes = []

        while len(attrs) == 1 and not first(attrs).has_kind("<var>"):

paul@65

2447

            attr = first(attrs)

            traversed.append(attrname)

paul@96

2450

            traversal_modes.append(accessor_kind == provider_kind and "object" or "class")

            # Consume attribute names providing unambiguous attributes.

            del remaining[0]

            if not remaining:

paul@65

2457

                break

            # Update the last static attribute.

            if attr.static():

paul@65

2462

                base = attr.get_origin()

paul@65

2463

                traversed = []

paul@96

2464

                traversal_modes = []

            # Get the access details.

            attrname = remaining[0]

paul@102

2469

            accessor = attr.get_origin()

paul@102

2470

            accessor_kind = attr.get_kind()

paul@102

2471

            provider_kind = self.importer.get_attribute_provider(attr, attrname)

paul@102

2472

            accessor_kinds = [accessor_kind]

paul@102

2473

            provider_kinds = [provider_kind]

            # Get the next attribute.

            attrs = self.importer.get_attributes(attr, attrname)

        # Where many attributes are suggested, no single attribute identity can

paul@67

2480

        # be loaded.

        else:

paul@65

2483

            attr = None

        # Determine the method of access.

        is_assignment = location in self.reference_assignments or const_access in self.reference_assignments

paul@256

2488

        is_invocation = location in self.reference_invocations or const_access in self.reference_invocations

Lichen

Annotated deducer.py