#!/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_assigned_attributes, \

                   get_attrname_from_location, get_attrnames, \

                   get_invoked_attributes, get_name_path, init_item, \

                   sorted_output, CommonOutput

from encoders import encode_attrnames, encode_access_location, \

                     encode_constrained, encode_location, encode_usage, \

                     get_kinds, test_for_kinds, test_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 = {}

        # Modified attributes from usage observations.

        self.modified_attributes = {}

        # Accesses that are assignments or invocations.

        self.reference_assignments = set()

        self.reference_invocations = set()

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

        self.initialise_access_plans()

    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)

                # Write specific type guard details.

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

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

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

                        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_type.get(location):

                        print >>f_tests, encode_access_location(location), 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 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 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

        """

        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 = self.access_plans[location]

                print >>f_attrs, encode_access_location(location), \

                                 name, test, test_type or "{}", \

                                 base or "{}", \

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

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

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

                                 context, context_test, \

                                 first_method, final_method, attr or "{}"

        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] = test_for_type("specific", 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] = test_for_type("common", 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(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] = test_for_type("constrained-specific", 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] = test_for_type("constrained-common", 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] = test_for_type("guarded-specific", 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] = test_for_type("guarded-common", 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_for_kinds("specific", all_accessor_kinds)

                    else:

                        test_type = "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_for_kinds("common", all_accessor_kinds)

                    else:

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

        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

    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, False, False),))

    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)

                for usage in usages:

                    self.add_usage_term(location, usage)

    def add_usage_term(self, location, usage):

        """

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

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

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

        """

        init_item(self.location_index, location, set)

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

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

                self.add_accessors(all_accesses, path)

    def add_accessors(self, all_accesses, path):

        """

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

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

        for each access.

        """

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