#!/usr/bin/env python

"""

Deduce types for usage observations.

Copyright (C) 2014, 2015, 2016 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_attrname_from_location, get_attrnames, \

                   init_item, make_key, sorted_output, \

                   CommonOutput

from encoders import encode_attrnames, encode_access_location, \

                     encode_constrained, encode_location

from os.path import join

from referencing import 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 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 = {}

        # Modified attributes from usage observations.

        self.modified_attributes = {}

        # 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.reference_constrained = set()

        self.access_constrained = set()

        self.referenced_attrs = {}

        self.referenced_objects = {}

        # 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

        # attribute-specific accessor tests.

        self.reference_class_attrs = {}

        self.reference_instance_attrs = {}

        self.reference_module_attrs = {}

        self.reference_all_attrs = {}

        self.reference_all_attrtypes = {}

        self.reference_test_types = {}

        self.reference_test_accessor_types = {}

        # The processing workflow itself.

        self.init_usage_index()

        self.init_accessors()

        self.init_accesses()

        self.init_aliases()

        self.init_attr_type_indexes()

        self.modify_mutated_attributes()

        self.identify_references()

        self.classify_accessors()

        self.classify_accesses()

    def to_output(self):

        "Write the output files using deduction information."

        self.check_output()

        self.write_mutations()

        self.write_accessors()

        self.write_accesses()

    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.reference_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

                    print >>f_warnings, encode_location(location)

                guard_test = self.accessor_guard_tests.get(location)

                # Write specific type guard details.

                if guard_test and guard_test.startswith("specific"):

                    print >>f_guards, encode_location(location), guard_test, \

                        self.get_kinds(all_types)[0], \

                        sorted_output(all_types)

                # Write common type guard details.

                elif guard_test and guard_test.startswith("common"):

                    print >>f_guards, encode_location(location), guard_test, \

                        self.get_kinds(all_general_types)[0], \

                        sorted_output(all_general_types)

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

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

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

                        print >>f_tests, encode_access_location(location), test_type

                    # Write any type checks for anonymous accesses.

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

                        print >>f_tests, encode_access_location(location), test_type, \

                            sorted_output(all_accessed_attrs), \

                            self.reference_test_accessor_types[location]

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

                        test_type or "untested", sorted_output(all_accessed_attrs)

                else:

                    print >>f_warnings, encode_access_location(location)

        finally:

            f_attr_summary.close()

            f_attrs.close()

            f_tests.close()

            f_warnings.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.reference_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] = all_types = \

                self.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_types(class_types)

            instance_types = self.accessor_instance_types[location]

            self.accessor_general_instance_types[location] = \

                general_instance_types = self.get_most_general_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 = \

                self.combine_types(class_types, instance_types, module_types)

            self.accessor_all_general_types[location] = all_general_types = \

                self.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] = self.test_for_types("specific", all_types)

                elif self.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] = self.test_for_types("common", all_types)

                elif self.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

            # Determine whether the attribute access is guarded or not.

            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.

                provider_guard_types = self.provider_all_types.get(accessor_location)

                all_provider_types.update(provider_guard_types)

                # Obtain the accessor types.

                accessor_guard_types = self.accessor_all_types.get(accessor_location)

                accessor_general_guard_types = self.accessor_all_general_types.get(accessor_location)

                all_accessor_types.update(accessor_guard_types)

                all_accessor_general_types.update(accessor_general_guard_types)

            # Determine the basis on which the access has been guarded.

            guarded = (

                len(all_accessor_types) == 1 or

                self.is_single_class_type(all_accessor_types) or

                len(all_accessor_general_types) == 1 or

                self.is_single_class_type(all_accessor_general_types)

                )

            if guarded:

                (guard_class_types, guard_instance_types, guard_module_types,

                    _function_types, _var_types) = self.separate_types(all_provider_types)

            # Attribute information, both name-based and anonymous.

            referenced_attrs = self.referenced_attrs[location]

            if referenced_attrs:

                # Record attribute information for each name used on the

                # accessor.

                attrname = get_attrname_from_location(location)

                all_accessed_attrs = set()

                all_accessed_attrtypes = set()

                all_providers = set()

                all_general_providers = set()

                for attrtype, d, general in [

                    ("<class>", self.reference_class_attrs, self.get_most_general_types),

                    ("<instance>", self.reference_instance_attrs, self.get_most_general_types),

                    ("<module>", self.reference_module_attrs, self.get_most_general_module_types)]:

                    attrs = [attr for _attrtype, object_type, attr in referenced_attrs if _attrtype == attrtype]

                    providers = [object_type for _attrtype, object_type, attr in referenced_attrs if _attrtype == attrtype]

                    general_providers = general(providers)

                    d[location] = set(attrs)

                    if attrs:

                        all_accessed_attrs.update(attrs)

                        all_accessed_attrtypes.add(attrtype)

                        all_providers.update(providers)

                        all_general_providers.update(general_providers)

                # Determine which attributes would be provided by the

                # accessor types upheld by a guard.

                if guarded:

                    guard_attrs = [attr for _attrtype, object_type, attr in

                        self._identify_reference_attribute(attrname, guard_class_types, guard_instance_types, guard_module_types)]

                else:

                    guard_attrs = None

                self.reference_all_attrs[location] = all_accessed_attrs

                self.reference_all_attrtypes[location] = all_accessed_attrtypes

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

                if not constrained:

                    # Provide informational test types.

                    if guarded and all_accessed_attrs.issubset(guard_attrs):

                        if len(all_accessor_types) == 1:

                            self.reference_test_types[location] = self.test_for_types("guarded-specific", all_accessor_types)

                        elif self.is_single_class_type(all_accessor_types):

                            self.reference_test_types[location] = "guarded-specific-object"

                        elif len(all_accessor_general_types) == 1:

                            self.reference_test_types[location] = self.test_for_types("guarded-common", all_accessor_general_types)

                        elif self.is_single_class_type(all_accessor_general_types):

                            self.reference_test_types[location] = "guarded-common-object"

                    # Provide active test types.

                    else:

                        # Record the need to test the type of anonymous and

                        # unconstrained accessors.

                        if len(all_providers) == 1:

                            provider = list(all_providers)[0]

                            if provider != '__builtins__.object':

                                all_accessor_kinds = set(self.get_kinds(all_accessor_types))

                                if len(all_accessor_kinds) == 1:

                                    test_type = self.test_for_kinds("specific", all_accessor_kinds)

                                else:

                                    test_type = "specific-object"

                                self.reference_test_types[location] = test_type

                                self.reference_test_accessor_types[location] = provider

                        elif len(all_general_providers) == 1:

                            provider = list(all_general_providers)[0]

                            if provider != '__builtins__.object':

                                all_accessor_kinds = set(self.get_kinds(all_accessor_general_types))

                                if len(all_accessor_kinds) == 1:

                                    test_type = self.test_for_kinds("common", all_accessor_kinds)

                                else:

                                    test_type = "common-object"

                                self.reference_test_types[location] = test_type

                                self.reference_test_accessor_types[location] = provider

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

                        else:

                            self.reference_test_types[location] = "validate"

    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.

        """

        ca = self.reference_class_attrs[location]

        ia = self.reference_instance_attrs[location]

        ma = self.reference_module_attrs[location]

        l = []

        for attrtype, attrs in (("<class>", ca), ("<instance>", ia), ("<module>", ma)):

            if attrs:

                l.append((attrtype, attrs))

        return l

    # Test generation methods.

    def get_kinds(self, all_types):

        """

        Return object kind details for 'all_types', being a collection of

        references for program types.

        """

        return map(lambda ref: ref.get_kind(), all_types)

    def test_for_types(self, prefix, all_types):

        """

        Return identifiers describing test conditions incorporating the given

        'prefix' and involving 'all_types', being a collection of references to

        program types.

        """

        return self.test_for_kind(prefix, first(all_types).get_kind())

    def test_for_kinds(self, prefix, all_kinds):

        """

        Return identifiers describing test conditions incorporating the given

        'prefix' and involving 'all_kinds', being a collection of object kinds.

        """

        return self.test_for_kind(prefix, first(all_kinds))

    def test_for_kind(self, prefix, kind):

        "Return a test condition identifier featuring 'prefix' and 'kind'."

        return "%s-%s" % (prefix, kind == "<instance>" and "instance" or "type")

    # Type handling methods.

    def is_single_class_type(self, all_types):

        """

        Return whether 'all_types' is a mixture of class and instance kinds for

        a single class type.

        """

        kinds = set()

        types = set()

        for type in all_types:

            kinds.add(type.get_kind())

            types.add(type.get_origin())

        return len(types) == 1 and kinds == set(["<class>", "<instance>"])

    def get_types_for_reference(self, ref):

        "Return class, instance-only and module types for 'ref'."

        class_types = ref.has_kind("<class>") and [ref.get_origin()] or []

        instance_types = []

        module_types = ref.has_kind("<module>") and [ref.get_origin()] or []

        return class_types, instance_types, module_types

    def combine_types(self, class_types, instance_types, module_types):

        """

        Combine 'class_types', 'instance_types', 'module_types' into a single

        list of references.

        """

        all_types = []

        for kind, l in [("<class>", class_types), ("<instance>", instance_types), ("<module>", module_types)]:

            for t in l:

                all_types.append(Reference(kind, t))

        return all_types

    def separate_types(self, refs):

        """

        Separate 'refs' into type-specific lists, returning a tuple containing

        lists of class types, instance types, module types, function types and

        unknown "var" types.

        """

        class_types = []

        instance_types = []

        module_types = []

        function_types = []

        var_types = []

        for kind, l in [

            ("<class>", class_types), ("<instance>", instance_types), ("<module>", module_types),

            ("<function>", function_types), ("<var>", var_types)

            ]:

            for ref in refs:

                if ref.get_kind() == kind:

                    l.append(ref.get_origin())

        return class_types, instance_types, module_types, function_types, var_types

    # 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

    def init_usage_index(self):

        """

        Create indexes for module and function attribute usage and for anonymous

        accesses.

        """

        for module in self.importer.get_modules():

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

                self.add_usage(assignments, path)

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

            for attrnames in all_attrnames:

                attrname = get_attrnames(attrnames)[-1]

                access_location = (location, None, attrnames, 0)

                self.add_usage_term(access_location, [attrname])

    def add_usage(self, assignments, path):

        """

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

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

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

        """

        for name, versions in assignments.items():

            for i, usages in enumerate(versions):

                location = (path, name, None, i)