Lichen (annotate deducer.py in c8149a01d932)

#!/usr/bin/env python

paul@44

2

paul@44

3

"""

paul@44

4

Deduce types for usage observations.

Copyright (C) 2014-2018, 2023 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 access_plan import AccessPlan

paul@791

23

from common import first, get_assigned_attributes, get_attrnames, \

paul@90

24

                   get_invoked_attributes, get_name_path, init_item, \

paul@791

25

                   order_dependencies_partial, sorted_output, \

paul@791

26

                   AccessLocation, CommonOutput, Location

paul@789

27

from encoders import encode_access_location, encode_alias_location, \

paul@789

28

                     encode_constrained, encode_instruction, encode_location, \

paul@789

29

                     encode_usage, get_kinds, \

paul@789

30

                     test_label_for_kind, test_label_for_type

paul@71

31

from errors import DeduceError

paul@44

32

from os.path import join

paul@57

33

from referencing import combine_types, is_single_class_type, separate_types, \

paul@57

34

                        Reference

class Deducer(CommonOutput):

    "Deduce types in a program."

    root_class_type = "__builtins__.object"

    def __init__(self, importer, output):

"""

paul@44

45

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

paul@44

46

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

paul@44

47

        'output' directory.

paul@44

48

"""

        self.importer = importer

paul@44

51

        self.output = output

        # Descendants of classes.

        self.descendants = {}

paul@44

56

        self.init_descendants()

paul@44

57

        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

82

        self.initialised_accesses = {}

        # Map constant accesses to redefined accesses.

        self.const_accesses = {}

paul@67

87

        self.const_accesses_rev = {}

        # Map usage observations to assigned attributes.

        self.assigned_attrs = {}

        # Map usage observations to objects.

        self.attr_class_types = {}

paul@44

96

        self.attr_instance_types = {}

paul@44

97

        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

110

        self.reference_invocations = {}

paul@553

111

        self.reference_invocations_unsuitable = {}

        # Map locations to types, constrained indicators and attributes.

        self.accessor_class_types = {}

paul@44

116

        self.accessor_instance_types = {}

paul@44

117

        self.accessor_module_types = {}

paul@44

118

        self.provider_class_types = {}

paul@44

119

        self.provider_instance_types = {}

paul@44

120

        self.provider_module_types = {}

paul@67

121

        self.accessor_constrained = set()

paul@44

122

        self.access_constrained = set()

paul@44

123

        self.referenced_attrs = {}

paul@44

124

        self.referenced_objects = {}

        # Details of access operations.

        self.access_plans = {}

        # Specific attribute access information.

        self.access_instructions = {}

paul@653

133

        self.accessor_kinds = {}

        # Accumulated information about accessors and providers.

        self.accessor_general_class_types = {}

paul@44

138

        self.accessor_general_instance_types = {}

paul@44

139

        self.accessor_general_module_types = {}

paul@44

140

        self.accessor_all_types = {}

paul@44

141

        self.accessor_all_general_types = {}

paul@44

142

        self.provider_all_types = {}

paul@44

143

        self.accessor_guard_tests = {}

        # Accumulated information about accessed attributes and

paul@67

146

        # access/attribute-specific accessor tests.

        self.reference_all_attrs = {}

paul@687

149

        self.reference_all_providers = {}

paul@687

150

        self.reference_all_provider_kinds = {}

paul@67

151

        self.reference_all_accessor_types = {}

paul@67

152

        self.reference_all_accessor_general_types = {}

paul@44

153

        self.reference_test_types = {}

paul@77

154

        self.reference_test_accessor_type = {}

        # The processing workflow itself.

        self.init_usage_index()

paul@501

159

        self.init_attr_type_indexes()

paul@501

160

        self.init_combined_attribute_index()

paul@44

161

        self.init_accessors()

paul@44

162

        self.init_accesses()

paul@44

163

        self.init_aliases()

paul@44

164

        self.modify_mutated_attributes()

paul@44

165

        self.identify_references()

paul@44

166

        self.classify_accessors()

paul@44

167

        self.classify_accesses()

paul@67

168

        self.initialise_access_plans()

paul@653

169

        self.initialise_access_instructions()

paul@411

170

        self.identify_dependencies()

    def to_output(self):

        "Write the output files using deduction information."

        self.check_output()

        self.write_mutations()

paul@44

179

        self.write_accessors()

paul@44

180

        self.write_accesses()

paul@65

181

        self.write_access_plans()

    def write_mutations(self):

"""

paul@44

186

        Write mutation-related output in the following format:

        qualified name " " original object type

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

paul@44

191

"""

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

paul@44

194

        try:

paul@44

195

            attrs = self.modified_attributes.items()

paul@44

196

            attrs.sort()

            for attr, value in attrs:

paul@44

199

                print >>f, attr, value

paul@44

200

        finally:

paul@44

201

            f.close()

    def write_accessors(self):

"""

paul@44

206

        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

211

        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

218

        where the latter indicates an absence of suitable references.

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

paul@44

221

        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

230

        single line in order to determine the complexity of identifying an

paul@44

231

        accessor.

        ----

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

paul@44

236

        warnings file in the following format:

        location

        ----

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

paul@44

243

        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

254

"""

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

paul@44

257

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

paul@44

258

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

paul@44

259

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

paul@788

260

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

        try:

paul@44

263

            locations = self.accessor_class_types.keys()

paul@44

264

            locations.sort()

            for location in locations:

paul@67

267

                constrained = location in self.accessor_constrained

                # Accessor information.

                class_types = self.accessor_class_types[location]

paul@44

272

                instance_types = self.accessor_instance_types[location]

paul@44

273

                module_types = self.accessor_module_types[location]

                general_class_types = self.accessor_general_class_types[location]

paul@44

276

                general_instance_types = self.accessor_general_instance_types[location]

paul@44

277

                general_module_types = self.accessor_general_module_types[location]

                all_types = self.accessor_all_types[location]

paul@44

280

                all_general_types = self.accessor_all_general_types[location]

                if class_types:

paul@44

283

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

paul@44

284

                        sorted_output(general_class_types), len(class_types)

                if instance_types:

paul@44

287

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

paul@44

288

                        sorted_output(general_instance_types), len(instance_types)

                if module_types:

paul@44

291

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

paul@44

292

                        sorted_output(general_module_types), len(module_types)

                if not all_types:

paul@44

295

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

paul@55

296

                    attrnames = list(self.location_index[location])

paul@55

297

                    attrnames.sort()

paul@55

298

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

                guard_test = self.accessor_guard_tests.get(location)

paul@237

301

                if guard_test:

paul@237

302

                    guard_test_type, guard_test_arg = guard_test

                # Write specific type guard details.

                if guard_test and guard_test_type == "specific":

paul@237

307

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

paul@237

308

                        first(get_kinds(all_types)), \

paul@44

309

                        sorted_output(all_types)

                # Write common type guard details.

                elif guard_test and guard_test_type == "common":

paul@237

314

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

paul@237

315

                        first(get_kinds(all_general_types)), \

paul@44

316

                        sorted_output(all_general_types)

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

paul@237

319

                    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

322

            # are often the same thing.

            locations = self.alias_index.keys()

paul@788

325

            locations.sort()

            for location in locations:

paul@788

328

                accesses = []

paul@788

329

                for access_location in self.alias_index[location]:

paul@789

330

                    invocation = access_location in self.reference_invocations

paul@789

331

                    accesses.append(encode_alias_location(access_location, invocation))

paul@789

332

                invocation = location in self.reference_invocations

paul@789

333

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

        finally:

paul@44

336

            f_type_summary.close()

paul@44

337

            f_types.close()

paul@44

338

            f_warnings.close()

paul@44

339

            f_guards.close()

paul@788

340

            f_aliases.close()

    def write_accesses(self):

"""

paul@44

345

        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

350

        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

357

        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

372

        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

379

        nature of an attribute, the following formats are employed:

        location " " attribute name " " "validate"

paul@44

382

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

        ----

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

paul@44

387

        warnings file in the following format:

        location

paul@44

390

"""

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

paul@44

393

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

paul@44

394

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

paul@44

395

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

paul@553

396

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

        try:

paul@44

399

            locations = self.referenced_attrs.keys()

paul@44

400

            locations.sort()

            for location in locations:

paul@44

403

                constrained = location in self.access_constrained

                # Attribute information, both name-based and anonymous.

                referenced_attrs = self.referenced_attrs[location]

                if referenced_attrs:

paul@791

410

                    attrname = location.get_attrname()

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

paul@738

413

                    all_accessed_attrs.sort()

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

paul@44

416

                        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

423

                        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

428

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

paul@44

429

                            sorted_output(all_accessed_attrs), \

paul@77

430

                            self.reference_test_accessor_type[location]

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

paul@237

433

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

                    # Write details of potentially unsuitable invocation

paul@553

436

                    # occurrences.

                    unsuitable = self.reference_invocations_unsuitable.get(location)

paul@553

439

                    if unsuitable:

paul@553

440

                        unsuitable = map(str, unsuitable)

paul@553

441

                        unsuitable.sort()

paul@553

442

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

                else:

paul@44

445

                    print >>f_warnings, encode_access_location(location)

        finally:

paul@44

448

            f_attr_summary.close()

paul@44

449

            f_attrs.close()

paul@44

450

            f_tests.close()

paul@44

451

            f_warnings.close()

paul@553

452

            f_unsuitable.close()

    def write_access_plans(self):

"""

paul@653

457

        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

462

                 " " traversal access modes " " attributes to traverse

paul@653

463

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

paul@653

464

                 " " 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

471

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

paul@91

472

"""

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

        try:

paul@67

477

            locations = self.access_plans.keys()

paul@67

478

            locations.sort()

            for location in locations:

paul@1006

481

                self.access_plans[location].write(f_attrs, location)

        finally:

paul@67

484

            f_attrs.close()

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

paul@653

487

        try:

paul@653

488

            access_instructions = self.access_instructions.items()

paul@653

489

            access_instructions.sort()

            for location, instructions in access_instructions:

paul@653

492

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

paul@653

493

                for instruction in instructions:

paul@653

494

                    print >>f, encode_instruction(instruction)

paul@653

495

                print >>f

        finally:

paul@653

498

            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

505

        # defined. See: init_definition_details

        locations = self.accessor_class_types.keys()

        for location in locations:

paul@67

510

            constrained = location in self.accessor_constrained

            # Provider information.

            class_types = self.provider_class_types[location]

paul@44

515

            instance_types = self.provider_instance_types[location]

paul@44

516

            module_types = self.provider_module_types[location]

            # Collect specific and general type information.

            self.provider_all_types[location] = \

paul@57

521

                combine_types(class_types, instance_types, module_types)

            # Accessor information.

            class_types = self.accessor_class_types[location]

paul@44

526

            self.accessor_general_class_types[location] = \

paul@69

527

                general_class_types = self.get_most_general_class_types(class_types)

            instance_types = self.accessor_instance_types[location]

paul@44

530

            self.accessor_general_instance_types[location] = \

paul@69

531

                general_instance_types = self.get_most_general_class_types(instance_types)

            module_types = self.accessor_module_types[location]

paul@44

534

            self.accessor_general_module_types[location] = \

paul@44

535

                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

540

                combine_types(class_types, instance_types, module_types)

            self.accessor_all_general_types[location] = all_general_types = \

paul@57

543

                combine_types(general_class_types, general_instance_types, general_module_types)

            # Record guard information but only for accessors employed by

paul@742

546

            # 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

551

                # constrained, potentially due to usage unsupported by the class

paul@816

552

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

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

paul@816

555

                    self.record_guard(location, all_types, all_general_types)

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

"""

paul@816

560

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

paul@816

561

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

paul@816

562

        tests will need to be applied.

paul@816

563

"""

        # Record specific type guard details.

        if len(all_types) == 1:

paul@816

568

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

paul@816

569

        elif is_single_class_type(all_types):

paul@816

570

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

        # Record common type guard details.

        elif len(all_general_types) == 1:

paul@816

575

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

paul@816

576

        elif is_single_class_type(all_general_types):

paul@816

577

            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

586

        # accessors.

        locations = self.referenced_attrs.keys()

        for location in locations:

paul@44

591

            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

598

            all_accessor_types = set()

paul@44

599

            all_accessor_general_types = set()

            for accessor_location in accessor_locations:

                # Obtain the provider types for guard-related attribute access

paul@44

604

                # 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

611

                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

616

            single_accessor_class_type = is_single_class_type(all_accessor_types)

paul@70

617

            single_accessor_general_type = len(all_accessor_general_types) == 1

paul@70

618

            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

623

                single_accessor_type or single_accessor_class_type or

paul@70

624

                single_accessor_general_type or single_accessor_general_class_type

            if guarded:

paul@44

628

                (guard_class_types, guard_instance_types, guard_module_types,

paul@57

629

                    _function_types, _var_types) = separate_types(all_provider_types)

            self.reference_all_accessor_types[location] = all_accessor_types

paul@67

632

            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

639

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

paul@839

640

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

            # Record attribute information for each name used on the

paul@71

643

            # accessor.

            attrname = location.get_attrname()

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

paul@843

648

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

paul@687

649

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

            # Obtain provider and attribute details for this kind of

paul@71

652

            # object.

            for attrtype, object_type, attr in referenced_attrs:

paul@843

655

                all_accessed_attrs.add(attr)

paul@843

656

                all_providers.add(object_type)

paul@687

657

                all_provider_kinds.add(attrtype)

            # Obtain reference and provider information as sets for the

paul@687

660

            # operations below, retaining the list forms for use with

paul@687

661

            # instruction plan preparation.

            all_general_providers = self.get_most_general_types(all_providers)

            # Determine which attributes would be provided by the

paul@71

666

            # accessor types upheld by a guard.

            if guarded:

paul@71

669

                guard_attrs = set()

                for _attrtype, object_type, attr in \

paul@555

672

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

                    guard_attrs.add(attr)

paul@71

675

            else:

paul@71

676

                guard_attrs = None

            # Constrained accesses guarantee the nature of the accessor.

paul@71

679

            # However, there may still be many types involved.

            if constrained:

paul@71

682

                if single_accessor_type:

paul@237

683

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

paul@71

684

                elif single_accessor_class_type:

paul@237

685

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

paul@71

686

                elif single_accessor_general_type:

paul@237

687

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

paul@71

688

                elif single_accessor_general_class_type:

paul@237

689

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

paul@44

690

                else:

paul@237

691

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

            # Suitably guarded accesses, where the nature of the

paul@71

694

            # accessor can be guaranteed, do not require the attribute

paul@71

695

            # involved to be validated. Otherwise, for unguarded

paul@71

696

            # accesses, access-level tests are required.

            elif guarded and all_accessed_attrs.issubset(guard_attrs):

paul@71

699

                if single_accessor_type:

paul@237

700

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

paul@71

701

                elif single_accessor_class_type:

paul@237

702

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

paul@71

703

                elif single_accessor_general_type:

paul@237

704

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

paul@71

705

                elif single_accessor_general_class_type:

paul@237

706

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

            # Record the need to test the type of anonymous and

paul@71

709

            # unconstrained accessors.

            elif len(all_providers) == 1:

paul@71

712

                provider = first(all_providers)

paul@654

713

                if provider != self.root_class_type:

paul@71

714

                    all_accessor_kinds = set(get_kinds(all_accessor_types))

paul@71

715

                    if len(all_accessor_kinds) == 1:

paul@385

716

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

paul@70

717

                    else:

paul@237

718

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

paul@71

719

                    self.reference_test_types[location] = test_type

paul@77

720

                    self.reference_test_accessor_type[location] = provider

            elif len(all_general_providers) == 1:

paul@71

723

                provider = first(all_general_providers)

paul@654

724

                if provider != self.root_class_type:

paul@71

725

                    all_accessor_kinds = set(get_kinds(all_accessor_general_types))

paul@71

726

                    if len(all_accessor_kinds) == 1:

paul@385

727

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

paul@71

728

                    else:

paul@237

729

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

paul@71

730

                    self.reference_test_types[location] = test_type

paul@77

731

                    self.reference_test_accessor_type[location] = provider

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

            else:

paul@237

736

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

    def initialise_access_plans(self):

        "Define attribute access plans."

        for location in self.referenced_attrs.keys():

paul@76

743

            original_location = self.const_accesses_rev.get(location)

paul@76

744

            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

755

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

    def get_referenced_attrs(self, location):

"""

paul@44

760

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

paul@44

761

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

paul@44

762

"""

        d = {}

paul@69

765

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

paul@69

766

            init_item(d, attrtype, set)

paul@246

767

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

paul@69

768

        l = d.items()

paul@69

769

        l.sort() # class, module, instance

paul@44

770

        return l

    # Initialisation methods.

    def init_descendants(self):

        "Identify descendants of each class."

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

paul@44

779

            self.get_descendants_for_class(name)

    def get_descendants_for_class(self, name):

"""

paul@44

784

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

paul@44

785

        given 'name'.

paul@44

786

"""

        if not self.descendants.has_key(name):

paul@44

789

            descendants = set()

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

paul@44

792

                descendants.update(self.get_descendants_for_class(subclass))

paul@44

793

                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

806

            for descendant in descendants:

paul@44

807

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

        for name in all_class_attrs.keys():

paul@44

810

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

    def init_usage_index(self):

"""

paul@44

815

        Create indexes for module and function attribute usage and for anonymous

paul@44

816

        accesses.

paul@44

817

"""

        for module in self.importer.get_modules():

paul@44

820

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

paul@44

821

                self.add_usage(assignments, path)

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

paul@44

824

            for attrnames in all_attrnames:

paul@44

825

                attrname = get_attrnames(attrnames)[-1]

paul@791

826

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

paul@107

827

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

    def add_usage(self, assignments, path):

"""

paul@44

832

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

paul@44

833

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

paul@44

834

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

paul@44

835

"""

        for name, versions in assignments.items():

paul@44

838

            for i, usages in enumerate(versions):

paul@791

839

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

                for usage in usages:

paul@88

842

                    self.add_usage_term(location, usage)

    def add_usage_term(self, location, usage):

"""

paul@88

847

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

paul@44

848

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

paul@44

849

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

paul@44

850

"""

        init_item(self.location_index, location, set)

paul@88

853

        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

860

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

paul@44

861

                self.add_accessors(all_accesses, path)

    def add_accessors(self, all_accesses, path):

"""

paul@44

866

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

paul@44

867

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

paul@44

868

        for each access.

paul@44

869

"""

        # 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

878

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

paul@44

879

                locations = []

                for version in versions:

paul@791

882

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

paul@44

883

                    locations.append(location)

                    # Map accessors to affected accesses.

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

paul@742

888

                    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

899

            return self.access_index[access_location]

paul@44

900

        except KeyError:

paul@44

901

            return [access_location]

    def init_accesses(self):

"""

paul@501

906

        Check that attributes used in accesses are actually defined on some

paul@501

907

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

paul@501

908

        attribute chains.

        Initialise collections for accesses involving assignments.

paul@44

911

"""

        # 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

918

            # applicable modifiers.

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

                # For each access, determine the name versions affected by

paul@44

923

                # assignments.

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

                    if name:

paul@791

928

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

paul@44

929

                    else:

paul@791

930

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

                    # Plain name accesses do not employ attributes and are

paul@717

933

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

                    if not attrname_str:

paul@717

936

                        if invocation:

paul@717

937

                            self.reference_invocations[access_location] = invocation

paul@501

938

                        continue

                    attrnames = get_attrnames(attrname_str)

                    # Check the attribute names.

                    for attrname in attrnames:

paul@501

945

                        if not attrname in self.all_attrnames:

paul@501

946

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

                    # Now only process assignments and invocations.

                    if invocation:

paul@553

951

                        self.reference_invocations[access_location] = invocation

paul@117

952

                        continue

paul@501

953

                    elif not assignment:

paul@501

954

                        continue

                    # Associate assignments with usage.

                    self.reference_assignments.add(access_location)

                    # Assignment occurs for the only attribute.

                    if len(attrnames) == 1:

paul@112

963

                        accessor_locations = self.get_accessors_for_access(access_location)

                        for location in accessor_locations:

paul@112

966

                            for usage in self.location_index[location]:

paul@88

967

                                init_item(self.assigned_attrs, usage, set)

paul@112

968

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

                    # Assignment occurs for the final attribute.

                    else:

paul@112

973

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

paul@112

974

                        init_item(self.assigned_attrs, usage, set)

paul@112

975

                        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

988

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

paul@791

989

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

paul@791

990

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

paul@742

991

                    init_item(self.alias_index, accessor_location, list)

paul@742

992

                    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

997

            for version, ref in versions.items():

paul@791

998

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

                self.initialised_names[location] = ref

                access_locations = self.access_index_rev.get(location)

paul@791

1003

                if access_locations:

paul@791

1004

                    for access_location in access_locations:

paul@791

1005

                        init_item(self.initialised_accesses, access_location, set)

paul@791

1006

                        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

1011

            for access_location in access_locations:

paul@735

1012

                init_item(self.alias_index_rev, access_location, set)

paul@735

1013

                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

1024

            if not usage:

paul@44

1025

                continue

            for path, name, attrname in all_attrnames:

paul@44

1028

                class_types = self.get_class_types_for_usage(usage)

paul@44

1029

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

paul@44

1030

                module_types = self.get_module_types_for_usage(usage)

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

paul@44

1033

                # of the mutation.

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

paul@44

1036

                if t:

paul@44

1037

                    class_types, only_instance_types, module_types, constrained = t

paul@44

1038

                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

1047

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

paul@44

1048

            value = self.importer.get_object(attr)

            # If the value is None, the attribute is

paul@44

1051

            # inherited and need not be set explicitly on

paul@44

1052

            # the class concerned.

            if value:

paul@44

1055

                self.modified_attributes[attr] = value

paul@44

1056

                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

1065

        class_types = set()

        for type in types:

paul@69

1068

            ref = self.importer.identify(type)

paul@69

1069

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

paul@69

1070

                module_types.add(type)

paul@69

1071

            else:

paul@69

1072

                class_types.add(type)

        types = set(self.get_most_general_module_types(module_types))

paul@69

1075

        types.update(self.get_most_general_class_types(class_types))

paul@69

1076

        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

1083

        to_remove = set()

        for class_type in class_types:

paul@44

1086

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

paul@44

1087

                base = base.get_origin()

paul@44

1088

                descendants = self.descendants[base]

paul@44

1089

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

paul@44

1090

                    to_remove.update(descendants)

        class_types.difference_update(to_remove)

paul@44

1093

        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

1100

        # attributes.

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

paul@654

1103

            return [self.root_class_type]

paul@44

1104

        else:

paul@44

1105

            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

1114

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

paul@107

1115

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

paul@44

1116

        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

1121

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

paul@44

1122

        'attrs' type-to-attributes mapping.

paul@44

1123

"""

        for name, attrnames in attrs.items():

paul@44

1126

            for attrname in attrnames:

                # Permit general access for certain kinds of object.

                if assignment is None:

paul@107

1131

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

paul@107

1132

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

paul@107

1133

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

paul@107

1134

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

                # Restrict attribute assignment for instances.

                else:

paul@107

1139

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

paul@107

1140

                    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

1151

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

paul@44

1152

        (as either class or instance attributes).

paul@44

1153

"""

        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

1166

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

paul@44

1167

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

paul@44

1168

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

paul@44

1169

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

paul@44

1170

"""

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

        if not usage:

paul@44

1175

            return attrs.keys()

        keys = []

paul@107

1178

        for attrname, invocation, assignment in usage:

paul@107

1179

            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

1198

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

paul@501

1199

            for name, attrnames in attrs.items():

paul@501

1200

                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

1213

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

paul@44

1214

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

paul@44

1215

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

            have_usage = False

paul@44

1218

            have_no_usage_branch = False

            for usage in usages:

paul@44

1221

                if not usage:

paul@44

1222

                    have_no_usage_branch = True

paul@44

1223

                    continue

paul@44

1224

                elif not have_usage:

paul@44

1225

                    self.init_definition_details(location)

paul@44

1226

                    have_usage = True

paul@44

1227

                self.record_types_for_usage(location, usage)

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

paul@44

1230

            # occur, record the types for those branches anyway.

            if have_usage and have_no_usage_branch:

paul@44

1233

                self.init_definition_details(location)

paul@44

1234

                self.record_types_for_usage(location, None)

        # Specific name-based attribute accesses.

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

paul@742

1239

            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

1250

                all_attrnames.update(get_attrnames(attrnames))

            # Get attribute and accessor details for each attribute name.

            for attrname in all_attrnames:

paul@791

1255

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

paul@44

1256

                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

1263

            # details.

            for original_access, access in name_accesses.items():

paul@44

1266

                original_name, original_attrnames = original_access

paul@44

1267

                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

1278

                    # details, exposing the final attribute name.

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

paul@44

1281

                    oa = ".".join(oa)

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

paul@791

1284

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

paul@44

1285

                    self.access_index[access_location] = [accessor_location]

                    self.init_access_details(access_location)

paul@44

1288

                    self.init_definition_details(accessor_location)

                    # Obtain a reference for the accessor in order to properly

paul@44

1291

                    # determine its type.

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

paul@44

1294

                        objpath = ref.get_origin()

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

                    # Where the object name conflicts with the module

paul@44

1299

                    # providing it, obtain the module details.

                    if objpath in self.importer.modules:

paul@44

1302

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

paul@44

1303

                    else:

paul@44

1304

                        accessor = self.importer.get_object(objpath)

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

paul@44

1307

                    self.access_constrained.add(access_location)

                    class_types, instance_types, module_types = accessor.get_types()

paul@44

1310

                    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

1315

                    # details, employing the first remaining attribute name.

                    l = get_attrnames(attrnames)

paul@64

1318

                    attrname = l[0]

                    oa = original_accessor[:-len(l)]

paul@64

1321

                    oa = ".".join(oa)

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

paul@791

1324

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

paul@64

1325

                    self.access_index[access_location] = [accessor_location]

                    self.init_access_details(access_location)

paul@64

1328

                    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

1333

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

                # Define mappings between the original and access locations

paul@679

1336

                # 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

1341

                    self.const_accesses[original_location] = access_location

paul@67

1342

                    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

1351

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

            updated_aliases = set()

            for location in affected_aliases:

paul@735

1356

                if self.record_types_for_alias(location):

paul@735

1357

                    updated_aliases.add(location)

            # Define accesses employing aliases.

            alias_accesses = set()

paul@742

1362

            affected_aliases = set()

            for alias in updated_aliases:

                # Access affected by the alias.

                if self.access_index_rev.has_key(alias):

paul@742

1369

                    alias_accesses.update(self.access_index_rev[alias])

                # Another alias affected by the alias.

                elif self.alias_index_rev.has_key(alias):

paul@742

1374

                    affected_aliases.update(self.alias_index_rev[alias])

            # Update accesses employing aliases.

            updated_accesses = set()

            for access_location in alias_accesses:

paul@735

1381

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

paul@735

1382

                    updated_accesses.add(access_location)

            # Determine which aliases are affected by the updated accesses.

            for access_location in updated_accesses:

paul@735

1387

                if self.alias_index_rev.has_key(access_location):

paul@735

1388

                    affected_aliases.update(self.alias_index_rev[access_location])

            if not affected_aliases:

paul@735

1391

                break

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

"""

paul@44

1396

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

paul@44

1397

        'instance_types' and 'module_types'.

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

paul@44

1400

        constrained to a specific kind of type.

paul@44

1401

"""

        ref = self.importer.identify(path)

paul@44

1404

        if ref:

            # Constrain usage suggestions using the identified object.

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

paul@44

1409

                return (

paul@44

1410

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

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

paul@44

1413

                return (

paul@44

1414

                    [], [], 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

1422

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

paul@44

1423

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

paul@44

1424

        have been constrained using contextual information is also indicated,

paul@44

1425

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

paul@44

1426

"""

        have_assignments = get_assigned_attributes(usage)

        # Detect any initialised name for the location.

        if location.name:

paul@742

1433

            refs = self.get_initialised_name(location)

paul@742

1434

            if refs:

paul@44

1435

                (class_types, only_instance_types, module_types,

paul@742

1436

                    _function_types, _var_types) = separate_types(refs)

paul@107

1437

                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

1442

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

paul@44

1443

        module_types = self.get_module_types_for_usage(usage)

        # Merge usage deductions with observations to obtain reference types

paul@44

1446

        # for names involved with attribute accesses.

        if not location.name:

paul@107

1449

            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

1456

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

        if constrained_specific:

paul@107

1459

            return class_types, only_instance_types, module_types, constrained_specific, \

paul@107

1460

                constrained_specific or have_assignments

        # Constrain "self" references.

        class_name = self.in_method(location.path)

paul@816

1465

        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

1472

                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

1477

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

paul@791

1478

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

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

paul@816

1481

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

paul@816

1482

            # 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

1491

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

paul@44

1492

        classes involved.

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

paul@44

1495

        constrained.

paul@44

1496

"""

        class_name = self.in_method(unit_path)

        if not class_name:

paul@44

1501

            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

1508

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

paul@816

1509

        and 'only_instance_types'.

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

paul@816

1512

        constrained.

paul@816

1513

"""

        classes = set([class_name])

paul@44

1516

        classes.update(self.get_descendants_for_class(class_name))

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

paul@44

1519

        # either classes or instances may provide the attributes.

        return (

paul@44

1522

            set(class_types).intersection(classes),

paul@44

1523

            set(only_instance_types).intersection(classes),

paul@44

1524

            [], True

    def in_method(self, path):

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

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

paul@816

1532

        if len(t) == 1:

paul@816

1533

            return False

        class_name, method_name = t

paul@274

1536

        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

1543

        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

1550

        self.accessor_instance_types[location] = set()

paul@44

1551

        self.accessor_module_types[location] = set()

paul@44

1552

        self.provider_class_types[location] = set()

paul@44

1553

        self.provider_instance_types[location] = set()

paul@44

1554

        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

1565

        Define types for the 'access_location' associated with the given

paul@735

1566

        'accessor_locations'. Return whether referenced attributes were updated.

paul@44

1567

"""

        attrname = access_location.get_attrname()

paul@91

1570

        if not attrname:

paul@735

1571

            return False

        invocation = access_location in self.reference_invocations

paul@720

1574

        assignment = access_location in self.reference_assignments

        # Collect all suggested types for the accessors. Accesses may

paul@44

1577

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

        class_types = set()

paul@44

1580

        module_types = set()

paul@44

1581

        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

1592

                class_types.update(self.accessor_class_types[location])

paul@44

1593

                module_types.update(self.accessor_module_types[location])

paul@44

1594

                instance_types.update(self.accessor_instance_types[location])

            # Where accesses are associated with assignments but where no

paul@44

1597

            # attribute usage observations have caused such an association,

paul@44

1598

            # the attribute name is considered by itself.

            else:

paul@44

1601

                self.init_definition_details(location)

paul@720

1602

                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

1607

        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

1616

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

paul@44

1617

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

paul@44

1618

"""

        (class_types,

paul@44

1621

         instance_types,

paul@44

1622

         module_types,

paul@44

1623

         constrained,

paul@44

1624

         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

1629

            module_types, constrained, constrained_specific, invocations)

    def record_types_for_attribute(self, access_location, attrname):

"""

paul@44

1634

        Record types for the 'access_location' employing only the given

paul@44

1635

        'attrname' for type deduction.

paul@44

1636

"""

        (class_types,

paul@102

1639

         only_instance_types,

paul@102

1640

         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

1645

        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

1654

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

paul@44

1655

        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

1662

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

paul@735

1663

        Return whether the types were updated.

paul@44

1664

"""

        have_access = self.provider_class_types.has_key(accessor_location)

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

paul@709

1669

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

paul@709

1670

        # instance return values also yielding class providers (since attributes

paul@709

1671

        # on instances could be provided by classes).

        if have_access:

paul@44

1674

            provider_class_types = self.provider_class_types[accessor_location]

paul@44

1675

            provider_instance_types = self.provider_instance_types[accessor_location]

paul@44

1676

            provider_module_types = self.provider_module_types[accessor_location]

            accessor_class_types = self.accessor_class_types[accessor_location]

paul@721

1679

            accessor_instance_types = self.accessor_instance_types[accessor_location]

paul@721

1680

            accessor_module_types = self.accessor_module_types[accessor_location]

            # Find details for any corresponding access.

            new_provider_class_types = set()

paul@721

1685

            new_provider_instance_types = set()

paul@721

1686

            new_provider_module_types = set()

            new_accessor_class_types = set()

paul@721

1689

            new_accessor_instance_types = set()

paul@721

1690

            new_accessor_module_types = set()

            refs = set()

            for access_location in self.alias_index[accessor_location]:

paul@791

1695

                attrnames = access_location.attrnames

paul@791

1696

                invocation = self.reference_invocations.has_key(access_location)

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

paul@715

1699

                remaining = attrnames and len(attrnames) > 1

                # Alias has remaining attributes: reference details do not

paul@715

1702

                # correspond to the accessor; the remaining attributes would

paul@715

1703

                # need to be traversed first.

                if remaining:

paul@735

1706

                    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

1719

                        # not change the nature of class providers.

                        provider_attrs = self.convert_invocation_providers(attrs, invocation)

                        # Accessors are updated separately, employing invocation

paul@744

1724

                        # result details.

                        accessor_attrs = self.convert_invocations(attrs, invocation)

                # Alias references a name, not an access.

                else:

paul@742

1731

                    # Attempt to refine the types using initialised names or

paul@742

1732

                    # accessors.

                    attrs = self.get_initialised_access(access_location)

                    if attrs:

paul@721

1737

                        provider_attrs = self.convert_invocation_providers(attrs, invocation)

paul@721

1738

                        accessor_attrs = self.convert_invocations(attrs, invocation)

paul@742

1739

                    else:

paul@742

1740

                        provider_attrs = self.get_provider_references(access_location)

paul@742

1741

                        attrs = accessor_attrs = self.get_accessor_references(access_location)

                # Where no specific attributes are defined, do not attempt

paul@744

1744

                # to refine the alias's types.

                if not attrs:

paul@744

1747

                    return False

                (class_types, instance_types, module_types, function_types,

paul@744

1750

                    var_types) = separate_types(provider_attrs)

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

paul@744

1753

                # the defined accessor types.

                if function_types or var_types:

paul@744

1756

                    return False

                class_types = set(provider_class_types).intersection(class_types)

paul@744

1759

                instance_types = set(provider_instance_types).intersection(instance_types)

paul@744

1760

                module_types = set(provider_module_types).intersection(module_types)

                new_provider_class_types.update(class_types)

paul@744

1763

                new_provider_instance_types.update(instance_types)

paul@744

1764

                new_provider_module_types.update(module_types)

                (class_types, instance_types, module_types, function_types,

paul@744

1767

                    var_types) = separate_types(accessor_attrs)

                class_types = set(accessor_class_types).intersection(class_types)

paul@744

1770

                instance_types = set(accessor_instance_types).intersection(instance_types)

paul@744

1771

                module_types = set(accessor_module_types).intersection(module_types)

                new_accessor_class_types.update(class_types)

paul@744

1774

                new_accessor_instance_types.update(instance_types)

paul@744

1775

                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

1786

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

paul@721

1787

            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

1794

                   new_accessor_instance_types != accessor_instance_types or \

paul@735

1795

                   new_accessor_module_types != accessor_module_types

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

paul@709

1798

        # Invocations convert classes to instances and also attempt to find

paul@709

1799

        # return value information.

        else:

paul@44

1802

            refs = set()

            for access_location in self.alias_index[accessor_location]:

paul@791

1805

                attrnames = access_location.attrnames

paul@791

1806

                invocation = self.reference_invocations.has_key(access_location)

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

paul@683

1809

                remaining = attrnames and len(attrnames) > 1

                # Alias has remaining attributes: reference details do not

paul@683

1812

                # correspond to the accessor; the remaining attributes would

paul@683

1813

                # need to be traversed first.

                if remaining:

paul@735

1816

                    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

1835

                        provider_attrs = self.convert_invocation_providers(attrs, invocation)

paul@742

1836

                        accessor_attrs = self.convert_invocations(attrs, invocation)

paul@742

1837

                    else:

paul@742

1838

                        provider_attrs = self.get_provider_references(access_location)

paul@742

1839

                        attrs = accessor_attrs = self.get_accessor_references(access_location)

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

paul@744

1842

                # refine the defined accessor types.

                if not attrs:

paul@744

1845

                    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

1856

                var_types) = separate_types(refs)

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

paul@742

1859

            # the defined accessor types.

            if not function_types and not var_types:

paul@742

1862

                self.init_definition_details(accessor_location)

paul@742

1863

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

paul@742

1864

                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

1875

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

paul@742

1876

        'refs' if an invocation is involved.

paul@742

1877

"""

        if not self.reference_invocations.has_key(access_location):

paul@742

1880

            return

        for ref in refs:

            # Initialising accesses originate from the return values.

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

paul@742

1887

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

paul@742

1888

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

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

"""

paul@742

1893

        Make each return value provide information to the given

paul@742

1894

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

paul@742

1895

        as the collection of definitions.

paul@742

1896

"""

        versions = names.get(key)

paul@742

1899

        if not versions:

paul@742

1900

            return

        path, name = key

        for version in versions.keys():

paul@791

1905

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

paul@742

1906

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

paul@742

1907

            l.add(access_location)

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

paul@742

1910

            l.add(location)

    def get_references_for_access(self, access_location):

        "Return the references identified for 'access_location'."

        attrs = set()

paul@708

1917

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

paul@843

1918

            attrs.add(attr)

paul@708

1919

        return attrs

    def convert_invocation_providers(self, refs, invocation):

"""

paul@709

1924

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

paul@709

1925

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

paul@709

1926

"""

        if not invocation:

paul@709

1929

            return refs

        providers = set()

        for ref in refs:

paul@742

1934

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

paul@742

1935

            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

1944

        for ref in refs:

paul@742

1945

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

paul@742

1946

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

paul@742

1947

            providers.add(ref)

paul@709

1948

        return providers

    def convert_invocation_provider(self, ref):

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

        if ref:

paul@712

1955

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

paul@742

1956

                return [ref]

paul@712

1957

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

paul@731

1958

                return self.convert_function_invocation(ref)

        return [Reference("<var>")]

    def convert_invocations(self, refs, invocation):

"""

paul@709

1965

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

paul@709

1966

        value.

paul@709

1967

"""

        if not invocation:

paul@739

1970

            return refs

        invocation_refs = set()

        for ref in refs:

paul@739

1975

            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

1984

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

paul@739

1985

                return [ref.instance_of()]

paul@712

1986

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

paul@731

1987

                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

1996

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

        if initialisers and not aliases:

paul@742

1999

            return set(initialisers.values())

        return [Reference("<var>")]

    def references_or_var(self, refs):

        var = Reference("<var>")

        if var in refs:

paul@742

2008

            return set([var])

paul@742

2009

        else:

paul@742

2010

            return refs

    def get_initialised_name(self, location):

"""

paul@791

2015

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

paul@791

2016

        such references exist.

paul@44

2017

"""

        ref = self.initialised_names.get(location)

paul@791

2020

        return ref and [ref] or None

    def get_initialised_access(self, location):

"""

paul@791

2025

        Return references for any initialised names supplying the given access

paul@791

2026

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

paul@791

2027

"""

        if location.access_number is not None:

paul@791

2030

            return self.initialised_accesses.get(location)

paul@742

2031

        else:

paul@791

2032

            return self.get_initialised_name(location)

    def get_accessor_references(self, access_location):

"""

paul@742

2037

        Return references corresponding to accessor details at the given

paul@742

2038

        'access_location'.

paul@742

2039

"""

        if self.accessor_class_types.has_key(access_location):

paul@742

2042

            class_types = self.accessor_class_types[access_location]

paul@742

2043

            instance_types = self.accessor_instance_types[access_location]

paul@742

2044

            module_types = self.accessor_module_types[access_location]

paul@742

2045

            return combine_types(class_types, instance_types, module_types)

paul@742

2046

        else:

paul@742

2047

            return None

    def get_provider_references(self, access_location):

"""

paul@742

2052

        Return references corresponding to provider details at the given

paul@742

2053

        'access_location'.

paul@742

2054

"""

        if self.provider_class_types.has_key(access_location):

paul@742

2057

            class_types = self.provider_class_types[access_location]

paul@742

2058

            instance_types = self.provider_instance_types[access_location]

paul@742

2059

            module_types = self.provider_module_types[access_location]

paul@742

2060

            return combine_types(class_types, instance_types, module_types)

paul@44

2061

        else:

paul@44

2062

            return None

    def record_reference_types(self, location, class_types, instance_types,

paul@90

2065

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

"""

paul@44

2068

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

paul@44

2069

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

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

paul@44

2072

        recorded for the location.

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

paul@44

2075

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

paul@44

2076

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

paul@44

2077

        to be a class.

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

paul@105

2080

        which are involved in invocations. Such invocations, if involving

paul@105

2081

        functions, will employ those functions as bound methods and will

paul@105

2082

        therefore not support classes as accessors, only instances of such

paul@105

2083

        classes.

        Note that the specified types only indicate the provider types for

paul@44

2086

        attributes, whereas the recorded accessor types indicate the possible

paul@44

2087

        types of the actual objects used to access attributes.

paul@44

2088

"""

        # 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

2095

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

paul@44

2096

        # accessors.

        path, name = location.path, location.name

        if invocations:

paul@90

2101

            class_only_types = self.filter_for_invocations(class_types, invocations)

paul@90

2102

        else:

paul@90

2103

            class_only_types = class_types

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

paul@44

2106

        # Any self variable may only refer to an instance.

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

paul@90

2109

            self.accessor_class_types[location].update(class_only_types)

        if not constrained_specific:

paul@44

2112

            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

2117

            self.accessor_module_types[location].update(module_types)

        if constrained:

paul@67

2120

            self.accessor_constrained.add(location)

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

paul@840

2123

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

paul@840

2124

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

paul@840

2125

        # filters out the accessor type.

        if not class_only_types and not instance_types and not module_types and \

paul@840

2128

           invocations and constrained_specific:

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

paul@840

2131

                (path, name))

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

"""

paul@721

2136

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

paul@721

2137

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

paul@721

2138

"""

        self.provider_class_types[location].update(class_types)

paul@721

2141

        self.provider_instance_types[location].update(instance_types)

paul@721

2142

        self.provider_module_types[location].update(module_types)

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

"""

paul@721

2147

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

paul@721

2148

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

paul@721

2149

"""

        self.accessor_class_types[location].update(class_types)

paul@721

2152

        self.accessor_instance_types[location].update(instance_types)

paul@721

2153

        self.accessor_module_types[location].update(module_types)

    def filter_for_invocations(self, class_types, attrnames):

"""

paul@90

2158

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

paul@90

2159

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

paul@90

2160

        class types.

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

paul@553

2163

        their attributes are methods that are directly invoked: method

paul@553

2164

        invocations must involve instance accessors.

paul@90

2165

"""

        to_filter = set()

        for class_type in class_types:

paul@90

2170

            for attrname in attrnames:

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

paul@553

2173

                # may return an attribute provided by an ancestor class.

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

paul@90

2176

                parent_class = ref and ref.parent()

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

paul@553

2179

                # the given class, record the class for filtering.

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

paul@90

2182

                   parent_class == class_type or

paul@90

2183

                   class_type in self.descendants[parent_class]):

                    to_filter.add(class_type)

paul@90

2186

                    break

        return set(class_types).difference(to_filter)

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

"""

paul@44

2193

        Identify reference attributes, associating them with the given

paul@44

2194

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

paul@44

2195

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

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

paul@44

2198

        recorded for the location.

paul@44

2199

"""

        # Record the referenced objects.

        self.referenced_attrs[location] = \

paul@555

2204

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

        if constrained:

paul@44

2207

            self.access_constrained.add(location)

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

"""

paul@555

2212

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

paul@555

2213

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

paul@555

2214

        'instance_types' and 'module_types'.

paul@44

2215

"""

        attrs = set()

        # The class types expose class attributes either directly or via

paul@44

2220

        # instances.

        for object_type in class_types:

paul@44

2223

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

paul@555

2224

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

paul@44

2225

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

            # Add any distinct instance attributes that would be provided

paul@44

2228

            # by instances also providing indirect class attribute access.

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

paul@555

2231

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

paul@555

2232

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

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

paul@44

2235

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

paul@44

2236

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

paul@44

2237

        # attributes.

        for object_type in instance_types:

paul@44

2240

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

            if instance_attrs:

paul@44

2243

                for ref in instance_attrs:

paul@555

2244

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

paul@555

2245

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

paul@44

2246

            else:

paul@44

2247

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

paul@555

2248

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

paul@44

2249

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

        # Module types expose module attributes for module accessors.

        for object_type in module_types:

paul@44

2254

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

paul@555

2255

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

paul@44

2256

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

        return attrs

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

"""

paul@555

2263

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

paul@555

2264

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

paul@555

2265

"""

        invocation = self.reference_invocations.get(location)

paul@557

2268

        if invocation is None:

paul@555

2269

            return True

        objpath = ref.get_origin()

paul@555

2272

        if not objpath:

paul@555

2273

            return True

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

paul@555

2276

        if not parameters:

paul@555

2277

            return True

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

paul@557

2280

        arguments, keywords = invocation

paul@557

2281

        names = set(parameters)

        # Determine whether the specified arguments are

paul@555

2284

        # compatible with the callable signature.

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

paul@557

2287

           arguments <= len(parameters) and \

paul@557

2288

           names.issuperset(keywords):

            return True

paul@555

2291

        else:

paul@555

2292

            init_item(self.reference_invocations_unsuitable, location, set)

paul@555

2293

            self.reference_invocations_unsuitable[location].add(ref)

paul@555

2294

            return False

    # Attribute access plan formulation.

    class_tests = (

paul@237

2299

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

paul@237

2300

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

paul@237

2301

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

paul@237

2302

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

    def get_access_plan(self, location):

"""

paul@77

2308

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

paul@77

2309

        follows:

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

paul@77

2312

           computed static accessor is found)

paul@77

2313

         * details of any test required on the initial accessor

paul@77

2314

         * details of any type employed by the test

paul@77

2315

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

paul@77

2316

           preference to the initial accessor)

paul@77

2317

         * attributes needing to be traversed from the base that yield

paul@77

2318

           unambiguous objects

paul@98

2319

         * access modes for each of the unambiguously-traversed attributes

paul@77

2320

         * remaining attributes needing to be tested and traversed

paul@77

2321

         * details of the context

paul@102

2322

         * any test to apply to the context

paul@653

2323

         * the method of obtaining the first attribute

paul@77

2324

         * the method of obtaining the final attribute

paul@77

2325

         * any static final attribute

paul@325

2326

         * the kinds of objects providing the final attribute

paul@77

2327

"""

        const_access = self.const_accesses_rev.get(location)

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

paul@75

2332

        remaining = attrnames.split(".")

paul@75

2333

        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

2342

        provider_types = self.reference_all_providers[location]

paul@687

2343

        provider_kinds = self.reference_all_provider_kinds[location]

        # Obtain accessor type and kind information.

        accessor_types = self.reference_all_accessor_types[location]

paul@67

2348

        accessor_general_types = self.reference_all_accessor_general_types[location]

paul@824

2349

        accessor_kinds = set(get_kinds(accessor_general_types))

        # Determine any guard or test requirements.

        constrained = location in self.access_constrained

paul@70

2354

        test = self.reference_test_types[location]

paul@77

2355

        test_type = self.reference_test_accessor_type.get(location)

        # Determine the accessor and provider properties.

        class_accessor = "<class>" in accessor_kinds

paul@67

2360

        module_accessor = "<module>" in accessor_kinds

paul@67

2361

        instance_accessor = "<instance>" in accessor_kinds

paul@67

2362

        provided_by_class = "<class>" in provider_kinds

paul@67

2363

        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

2368

        class_relative = not ubiquitous and instance_accessor and provided_by_class

        # Identify the last static attribute for context acquisition.

        base = None

paul@67

2373

        dynamic_base = None

        # Constant accesses have static providers.

        if const_access:

paul@687

2378

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

        # Name-based accesses.

        elif name:

paul@65

2383

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

            # Constant accessors are static.

            if ref and ref.static():

paul@65

2388

                base = ref.get_origin()

            # Usage of previously-generated guard and test details.

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

paul@67

2393

                ref = first(accessor_types)

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

paul@67

2396

                ref = first(accessor_general_types)

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

paul@67

2399

                ref = first(accessor_types)

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

paul@67

2402

                ref = first(accessor_general_types)

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

paul@70

2405

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

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

paul@77

2408

                dynamic_base = test_type

            # Static accessors.

            if not base and test in self.class_tests:

paul@70

2413

                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

2418

                dynamic_base = ref.get_origin()

        # Determine initial accessor details.

        accessor = base or dynamic_base

paul@102

2423

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

paul@102

2424

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

        # Traverse remaining attributes.

        traversed = []

paul@96

2429

        traversal_modes = []

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

paul@65

2432

            attr = first(attrs)

            traversed.append(attrname)

paul@96

2435

            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

2442

                break

            # Update the last static attribute.

            if attr.static():

paul@65

2447

                base = attr.get_origin()

paul@65

2448

                traversed = []

paul@96

2449

                traversal_modes = []

            # Get the access details.

            attrname = remaining[0]

paul@102

2454

            accessor = attr.get_origin()

paul@102

2455

            accessor_kind = attr.get_kind()

paul@102

2456

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

paul@102

2457

            accessor_kinds = [accessor_kind]

paul@102

2458

            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

2465

        # be loaded.

        else:

paul@65

2468

            attr = None

        # Determine the method of access.

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

paul@256

2473

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

        # Identified attribute that must be accessed via its parent.

        if attr and attr.get_name() and is_assignment:

paul@98

2478

            final_method = "static-assign"; origin = attr.get_name()

        # Static, identified attribute.

        elif attr and attr.static():

paul@117

2483

            final_method = is_assignment and "static-assign" or \

paul@117

2484

                           is_invocation and "static-invoke" or \

paul@117

2485

                           "static"

paul@98

2486

            origin = attr.final()

        # All other methods of access involve traversal.

        else:

paul@587

2491

            final_method = is_assignment and "assign" or \

paul@587

2492

                           is_invocation and "access-invoke" or \

paul@587

2493

                           "access"

paul@98

2494

            origin = None

        # First attribute accessed at a known position via the accessor.

        # Static bases support object-relative accesses only.

        if base:

paul@495

2501

            first_method = "relative-object"

        # Dynamic bases support either object- or class-relative accesses.

        elif dynamic_base:

paul@94

2506

            first_method = "relative" + (object_relative and "-object" or "") + \

paul@94

2507

                                        (class_relative and "-class" or "")

        # Special case for the ubiquitous __class__ attribute.

        elif ubiquitous:

paul@890

2512

            first_method = "relative-object"

        # The fallback case is always run-time testing and access.

        else:

paul@94

2517

            first_method = "check" + (object_relative and "-object" or "") + \

paul@94

2518

                                     (class_relative and "-class" or "")

        # Determine whether an unbound method is being accessed via an instance,

paul@102

2521

        # requiring a context test.

        context_test = "ignore"

        # Assignments do not employ the context.

        if is_assignment:

paul@102

2528

            pass

        # Obtain a selection of possible attributes if no unambiguous attribute

paul@102

2531

        # was identified.

        elif not attr:

            # Use previously-deduced attributes for a simple ambiguous access.

paul@102

2536

            # Otherwise, use the final attribute name to obtain possible

paul@102

2537

            # attributes.

            if len(remaining) > 1:

paul@102

2540

                attrname = remaining[-1]

                (class_types,

paul@102

2543

                 only_instance_types,

paul@102

2544

                 module_types) = self.get_types_for_attribute(attrname)

                accessor_kinds = set()

paul@212

2547

                provider_kinds = set()

                if class_types:

paul@212

2550

                    accessor_kinds.add("<class>")

paul@212

2551

                    accessor_kinds.add("<instance>")

paul@212

2552

                    provider_kinds.add("<class>")

paul@102

2553

                if only_instance_types:

paul@212

2554

                    accessor_kinds.add("<instance>")

paul@212

2555

                    provider_kinds.add("<instance>")

paul@102

2556

                if module_types:

paul@212

2557

                    accessor_kinds.add("<module>")

paul@212

2558

                    provider_kinds.add("<module>")

                attrs = set()

paul@102

2561

                for type in combine_types(class_types, only_instance_types, module_types):

paul@102

2562

                    attrs.update(self.importer.get_attributes(type, attrname))

            always_unbound = True

paul@102

2565

            have_function = False

paul@102

2566

            have_var = False

            # Determine whether all attributes are unbound methods and whether

paul@102

2569

            # functions or unidentified attributes occur.

            for attr in attrs:

paul@102

2572

                always_unbound = always_unbound and attr.has_kind("<function>") and attr.name_parent() == attr.parent()

paul@102

2573

                have_function = have_function or attr.has_kind("<function>")

paul@102

2574

                have_var = have_var or attr.has_kind("<var>")

            # Test for class-via-instance accesses.

            if accessor_kind == "<instance>" and \

paul@102

2579

               provider_kind == "<class>":

                if always_unbound:

paul@102

2582

                    context_test = "replace"

paul@102

2583

                else:

paul@102

2584

                    context_test = "test"

            # Test for the presence of class-via-instance accesses.

            elif "<instance>" in accessor_kinds and \

paul@102

2589

                 "<class>" in provider_kinds and \

paul@102

2590

                 (have_function or have_var):

                context_test = "test"

        # With an unambiguous attribute, determine whether a test is needed.

        elif accessor_kind == "<instance>" and \

paul@102

2597

             provider_kind == "<class>" and \

paul@102

2598

             (attr.has_kind("<var>") or

paul@102

2599

              attr.has_kind("<function>") and

paul@102

2600

              attr.name_parent() == attr.parent()):

            if attr.has_kind("<var>"):

paul@102

2603

                context_test = "test"

paul@102

2604

            else:

paul@102

2605

                context_test = "replace"

        # With an unambiguous attribute with ambiguity in the access method,

paul@102

2608

        # generate a test.

        elif "<instance>" in accessor_kinds and \

paul@102

2611

             "<class>" in provider_kinds and \

paul@102

2612

             (attr.has_kind("<var>") or

paul@102

2613

              attr.has_kind("<function>") and

paul@102

2614

              attr.name_parent() == attr.parent()):

            context_test = "test"

        # Determine the nature of the context.

        context = context_test == "ignore" and "unset" or \

paul@100

2621

                  len(traversed + remaining) == 1 and \

paul@100

2622

                      (base and "base" or "original-accessor") or \

paul@100

2623

                  "final-accessor"

        return AccessPlan(name, test, test_type, base,

paul@1006

2626

                          traversed, traversal_modes, remaining,

paul@1006

2627

                          context, context_test,

paul@1006

2628

                          first_method, final_method,

paul@1006

2629

                          origin, accessor_kinds)

    def initialise_access_instructions(self):

        "Expand access plans into instruction sequences."

        for access_location, access_plan in self.access_plans.items():

paul@1007

2636

            self.access_instructions[access_location] = access_plan.get_instructions()

paul@1007

2637

            self.accessor_kinds[access_location] = access_plan.accessor_kinds

# vim: tabstop=4 expandtab shiftwidth=4

Lichen

Annotated deducer.py