#!/usr/bin/env python

"""

Deduce types for usage observations.

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

This program is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free Software

Foundation; either version 3 of the License, or (at your option) any later

version.

This program is distributed in the hope that it will be useful, but WITHOUT

ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more

details.

You should have received a copy of the GNU General Public License along with

this program.  If not, see <http://www.gnu.org/licenses/>.

"""

from common import first, get_assigned_attributes, \

                   get_attrname_from_location, get_attrnames, \

                   get_invoked_attributes, get_name_path, init_item, \

                   sorted_output, CommonOutput

from encoders import encode_access_location, \

                     encode_constrained, encode_location, encode_usage, \

                     get_kinds, test_label_for_kind, test_label_for_type

from errors import DeduceError

from os.path import join

from referencing import combine_types, is_single_class_type, separate_types, \

                        Reference

class Deducer(CommonOutput):

    "Deduce types in a program."

    def __init__(self, importer, output):

        """

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

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

        'output' directory.

        """

        self.importer = importer

        self.output = output

        # Descendants of classes.

        self.descendants = {}

        self.init_descendants()

        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 aliases to accesses that define them.

        self.alias_index = {}

        # Map constant accesses to redefined accesses.

        self.const_accesses = {}

        self.const_accesses_rev = {}

        # Map usage observations to assigned attributes.

        self.assigned_attrs = {}

        # Map usage observations to objects.

        self.attr_class_types = {}

        self.attr_instance_types = {}

        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()

        self.reference_invocations = {}

        self.reference_invocations_unsuitable = {}

        # Map locations to types, constrained indicators and attributes.

        self.accessor_class_types = {}

        self.accessor_instance_types = {}

        self.accessor_module_types = {}

        self.provider_class_types = {}

        self.provider_instance_types = {}

        self.provider_module_types = {}

        self.accessor_constrained = set()

        self.access_constrained = set()

        self.referenced_attrs = {}

        self.referenced_objects = {}

        # Details of access operations.

        self.access_plans = {}

        # Accumulated information about accessors and providers.

        self.accessor_general_class_types = {}

        self.accessor_general_instance_types = {}

        self.accessor_general_module_types = {}

        self.accessor_all_types = {}

        self.accessor_all_general_types = {}

        self.provider_all_types = {}

        self.accessor_guard_tests = {}

        # Accumulated information about accessed attributes and

        # access/attribute-specific accessor tests.

        self.reference_all_attrs = {}

        self.reference_all_attrtypes = {}

        self.reference_all_accessor_types = {}

        self.reference_all_accessor_general_types = {}

        self.reference_test_types = {}

        self.reference_test_accessor_type = {}

        # The processing workflow itself.

        self.init_usage_index()

        self.init_attr_type_indexes()

        self.init_combined_attribute_index()

        self.init_accessors()

        self.init_accesses()

        self.init_aliases()

        self.modify_mutated_attributes()

        self.identify_references()

        self.classify_accessors()

        self.classify_accesses()

        self.initialise_access_plans()

        self.identify_dependencies()

    def to_output(self):

        "Write the output files using deduction information."

        self.check_output()

        self.write_mutations()

        self.write_accessors()

        self.write_accesses()

        self.write_access_plans()

    def write_mutations(self):

        """

        Write mutation-related output in the following format:

        qualified name " " original object type

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

        """

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

        try:

            attrs = self.modified_attributes.items()

            attrs.sort()

            for attr, value in attrs:

                print >>f, attr, value

        finally:

            f.close()

    def write_accessors(self):

        """

        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

        attribute type.

        Locations have the following format:

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

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

        where the latter indicates an absence of suitable references.

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

        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

        single line in order to determine the complexity of identifying an

        accessor.

        ----

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

        warnings file in the following format:

        location

        ----

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

        nature of an object, the following format is employed:

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

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

        """

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

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

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

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

        try:

            locations = self.accessor_class_types.keys()

            locations.sort()

            for location in locations:

                constrained = location in self.accessor_constrained

                # Accessor information.

                class_types = self.accessor_class_types[location]

                instance_types = self.accessor_instance_types[location]

                module_types = self.accessor_module_types[location]

                general_class_types = self.accessor_general_class_types[location]

                general_instance_types = self.accessor_general_instance_types[location]

                general_module_types = self.accessor_general_module_types[location]

                all_types = self.accessor_all_types[location]

                all_general_types = self.accessor_all_general_types[location]

                if class_types:

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

                        sorted_output(general_class_types), len(class_types)

                if instance_types:

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

                        sorted_output(general_instance_types), len(instance_types)

                if module_types:

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

                        sorted_output(general_module_types), len(module_types)

                if not all_types:

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

                    attrnames = list(self.location_index[location])

                    attrnames.sort()

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

                guard_test = self.accessor_guard_tests.get(location)

                if guard_test:

                    guard_test_type, guard_test_arg = guard_test

                # Write specific type guard details.

                if guard_test and guard_test_type == "specific":

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

                        first(get_kinds(all_types)), \

                        sorted_output(all_types)

                # Write common type guard details.

                elif guard_test and guard_test_type == "common":

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

                        first(get_kinds(all_general_types)), \

                        sorted_output(all_general_types)

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

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

        finally:

            f_type_summary.close()

            f_types.close()

            f_warnings.close()

            f_guards.close()

    def write_accesses(self):

        """

        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

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

        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

        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

        nature of an attribute, the following formats are employed:

        location " " attribute name " " "validate"

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

        ----

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

        warnings file in the following format:

        location

        """

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

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

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

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

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

        try:

            locations = self.referenced_attrs.keys()

            locations.sort()

            for location in locations:

                constrained = location in self.access_constrained

                # Attribute information, both name-based and anonymous.

                referenced_attrs = self.referenced_attrs[location]

                if referenced_attrs:

                    attrname = get_attrname_from_location(location)

                    all_accessed_attrs = self.reference_all_attrs[location]

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

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

                        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):

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

                            sorted_output(all_accessed_attrs), \

                            self.reference_test_accessor_type[location]

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

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

                    # Write details of potentially unsuitable invocation

                    # occurrences.

                    unsuitable = self.reference_invocations_unsuitable.get(location)

                    if unsuitable:

                        unsuitable = map(str, unsuitable)

                        unsuitable.sort()

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

                else:

                    print >>f_warnings, encode_access_location(location)

        finally:

            f_attr_summary.close()

            f_attrs.close()

            f_tests.close()

            f_warnings.close()

            f_unsuitable.close()

    def write_access_plans(self):

        """

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

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

                 " " attributes to traverse " " context " " access method

                 " " static attribute " " accessor kinds

        """

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

        try:

            locations = self.access_plans.keys()

            locations.sort()

            for location in locations:

                name, test, test_type, base, \

                    traversed, traversal_modes, attrnames, \

                    context, context_test, \

                    first_method, final_method, \

                    attr, accessor_kinds = self.access_plans[location]

                print >>f_attrs, encode_access_location(location), \

                                 name or "{}", \

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

                                 test_type or "{}", \

                                 base or "{}", \

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

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

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

                                 context, context_test, \

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

                                 ",".join(accessor_kinds)

        finally:

            f_attrs.close()

    def classify_accessors(self):

        "For each program location, classify accessors."

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

        # defined. See: init_definition_details

        locations = self.accessor_class_types.keys()

        for location in locations:

            constrained = location in self.accessor_constrained

            # Provider information.

            class_types = self.provider_class_types[location]

            instance_types = self.provider_instance_types[location]

            module_types = self.provider_module_types[location]

            # Collect specific and general type information.

            self.provider_all_types[location] = \

                combine_types(class_types, instance_types, module_types)

            # Accessor information.

            class_types = self.accessor_class_types[location]

            self.accessor_general_class_types[location] = \

                general_class_types = self.get_most_general_class_types(class_types)

            instance_types = self.accessor_instance_types[location]

            self.accessor_general_instance_types[location] = \

                general_instance_types = self.get_most_general_class_types(instance_types)

            module_types = self.accessor_module_types[location]

            self.accessor_general_module_types[location] = \

                general_module_types = self.get_most_general_module_types(module_types)

            # Collect specific and general type information.

            self.accessor_all_types[location] = all_types = \

                combine_types(class_types, instance_types, module_types)

            self.accessor_all_general_types[location] = all_general_types = \

                combine_types(general_class_types, general_instance_types, general_module_types)

            # Record guard information.

            if not constrained:

                # Record specific type guard details.

                if len(all_types) == 1:

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

                elif is_single_class_type(all_types):

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

                # Record common type guard details.

                elif len(all_general_types) == 1:

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

                elif is_single_class_type(all_general_types):

                    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

        # accessors.

        locations = self.referenced_attrs.keys()

        for location in locations:

            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()

            all_accessor_types = set()

            all_accessor_general_types = set()

            for accessor_location in accessor_locations:

                # Obtain the provider types for guard-related attribute access

                # 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))

                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

            single_accessor_class_type = is_single_class_type(all_accessor_types)

            single_accessor_general_type = len(all_accessor_general_types) == 1

            single_accessor_general_class_type = is_single_class_type(all_accessor_general_types)

            # Determine whether the attribute access is guarded or not.

            guarded = (

                single_accessor_type or single_accessor_class_type or

                single_accessor_general_type or single_accessor_general_class_type

                )

            if guarded:

                (guard_class_types, guard_instance_types, guard_module_types,

                    _function_types, _var_types) = separate_types(all_provider_types)

            self.reference_all_accessor_types[location] = all_accessor_types

            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:

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

            # Record attribute information for each name used on the

            # accessor.

            attrname = get_attrname_from_location(location)

            all_accessed_attrs = set()

            all_providers = set()

            # Obtain provider and attribute details for this kind of

            # object.

            for attrtype, object_type, attr in referenced_attrs:

                all_accessed_attrs.add(attr)

                all_providers.add(object_type)

            all_general_providers = self.get_most_general_types(all_providers)

            # Determine which attributes would be provided by the

            # accessor types upheld by a guard.

            if guarded:

                guard_attrs = set()

                for _attrtype, object_type, attr in \

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

                    guard_attrs.add(attr)

            else:

                guard_attrs = None

            self.reference_all_attrs[location] = all_accessed_attrs

            # Constrained accesses guarantee the nature of the accessor.

            # However, there may still be many types involved.

            if constrained:

                if single_accessor_type:

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

                elif single_accessor_class_type:

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

                elif single_accessor_general_type:

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

                elif single_accessor_general_class_type:

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

                else:

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

            # Suitably guarded accesses, where the nature of the

            # accessor can be guaranteed, do not require the attribute

            # involved to be validated. Otherwise, for unguarded

            # accesses, access-level tests are required.

            elif guarded and all_accessed_attrs.issubset(guard_attrs):

                if single_accessor_type:

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

                elif single_accessor_class_type:

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

                elif single_accessor_general_type:

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

                elif single_accessor_general_class_type:

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

            # Record the need to test the type of anonymous and

            # unconstrained accessors.

            elif len(all_providers) == 1:

                provider = first(all_providers)

                if provider != '__builtins__.object':

                    all_accessor_kinds = set(get_kinds(all_accessor_types))

                    if len(all_accessor_kinds) == 1:

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

                    else:

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

                    self.reference_test_types[location] = test_type

                    self.reference_test_accessor_type[location] = provider

            elif len(all_general_providers) == 1:

                provider = first(all_general_providers)

                if provider != '__builtins__.object':

                    all_accessor_kinds = set(get_kinds(all_accessor_general_types))

                    if len(all_accessor_kinds) == 1:

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

                    else:

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

                    self.reference_test_types[location] = test_type

                    self.reference_test_accessor_type[location] = provider

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

            else:

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

    def initialise_access_plans(self):

        "Define attribute access plans."

        for location in self.referenced_attrs.keys():

            original_location = self.const_accesses_rev.get(location)

            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():

            path, name, attrnames, version = location

            # Identify module-level paths.

            if self.importer.modules.has_key(path):

                module_name = path

            # Identify the module containing other paths.

            else:

                ref = self.importer.identify(path)

                for objpath in ref.ancestors():

                    if self.importer.modules.has_key(objpath):

                        module_name = objpath

                        break

                else:

                    raise DeduceError("Cannot find module for path %s." % path)

            # Identify references providing dependencies.

            for attrtype, objtype, attr in referenced_attrs:

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

    def get_referenced_attrs(self, location):

        """

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

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

        """

        d = {}

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

            init_item(d, attrtype, set)

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

        l = d.items()

        l.sort() # class, module, instance

        return l

    # Initialisation methods.

    def init_descendants(self):

        "Identify descendants of each class."

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

            self.get_descendants_for_class(name)

    def get_descendants_for_class(self, name):

        """

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

        given 'name'.

        """

        if not self.descendants.has_key(name):

            descendants = set()

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

                descendants.update(self.get_descendants_for_class(subclass))

                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():

            for descendant in descendants:

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

        for name in all_class_attrs.keys():

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