# -*- coding: utf-8 -*-

from typing import (
    Dict,
    Iterator,
    List,
    Optional,
    Sequence,
    Set,
    Tuple,
    TypeVar,
    cast,
)

from ..._utils import OrderedDict, deduplicate, flatten
from ...exc import UnknownType
from ...lang import ast as _ast
from ...schema import (
    Field,
    GraphQLCompositeType,
    GraphQLLeafType,
    GraphQLType,
    InterfaceType,
    ListType,
    NonNullType,
    ObjectType,
    Schema,
    unwrap_type,
)
from ..visitors import ValidationVisitor


T = TypeVar("T")
G = TypeVar("G")

WrappingType = (ListType, NonNullType)

FieldDef = Tuple[Optional[GraphQLType], _ast.Field, Optional[Field]]
FieldMap = Dict[str, List[FieldDef]]
FieldsAndFragments = Tuple[FieldMap, List[str]]

Conflict = Tuple[str, str, Sequence[_ast.Node]]


class Context:
    def __init__(
        self,
        schema: Schema,
        fields_and_fragments: Dict[_ast.SelectionSet, FieldsAndFragments],
        compared_fragment_pairs: Set[Tuple[Tuple[str, str], bool]],
        fragments: Dict[str, _ast.FragmentDefinition],
    ):
        self.schema = schema
        self.fields_and_fragments = fields_and_fragments
        self.compared_fragment_pairs = compared_fragment_pairs
        self.fragments = fragments


def _permutations(lst: Sequence[T]) -> Iterator[Tuple[T, T]]:
    """
    Symmetric permutations of a list

    >>> list(_permutations([1, 2, 3]))
    [(1, 2), (1, 3), (2, 3)]
    """
    for i, item_1 in enumerate(lst):
        for item_2 in lst[i + 1 :]:
            yield item_1, item_2


def _cross(iter_1: Sequence[T], iter_2: Sequence[G]) -> Iterator[Tuple[T, G]]:
    """
    Cross product of 2 sequences

    >>> list(_cross([1, 2, 3], [4, 5, 6]))
    [(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)]
    """
    for a in iter_1:
        for b in iter_2:
            yield a, b


def _at(
    lst: Sequence[T], index: int, default: Optional[T] = None
) -> Optional[T]:
    """
    Safely extract value from a list at a given index.

    >>> _at([], 0) is None
    True
    >>> _at([1], 2) is None
    True
    """
    try:
        return lst[index]
    except IndexError:
        return default


def _type_from_ast(schema, node):
    try:
        return schema.get_type_from_literal(node)
    except UnknownType:
        return None


class OverlappingFieldsCanBeMergedChecker(ValidationVisitor):
    """
    A selection set is only valid if all fields (including spreading any
    fragments) either correspond to distinct response names or can be merged
    without ambiguity.
    """

    def __init__(self, schema, type_info):
        super(OverlappingFieldsCanBeMergedChecker, self).__init__(
            schema, type_info
        )
        self.ctx = Context(self.schema, {}, set(), {})

    def enter_document(self, node):
        # Should happen before visitng any selection set
        self.ctx.fragments.update(
            {
                d.name.value: d
                for d in node.definitions
                if isinstance(d, _ast.FragmentDefinition)
            }
        )

    def enter_selection_set(self, node):
        conflicts = find_conflicts_within_selection_set(
            self.ctx,
            node,
            cast(GraphQLCompositeType, self.type_info.parent_type),
        )  # type: List[Conflict]

        for response_name, reason, locs in conflicts:
            self.add_error(
                'Field(s) "%s" conflict because %s. Use different aliases on '
                "the fields to fetch both if this was intentional."
                % (response_name, reason),
                locs,
            )


def find_conflicts_within_selection_set(
    ctx: Context, selection_set: _ast.SelectionSet, parent_type: GraphQLType
) -> List[Conflict]:
    """
    Find all conflicts found "within" a selection set, including those found
    via spreading in fragments. Called when visiting each SelectionSet in the
    GraphQL Document.


    Algorithm:
    ==========

    Conflicts occur when two fields exist in a query which will produce the same
    response name, but represent differing values, thus creating a conflict.
    The algorithm below finds all conflicts via making a series of comparisons
    between fields. In order to compare as few fields as possible, this makes a
    series of comparisons "within" sets of fields and "between" sets of fields.

    Given any selection set, a collection produces both a set of fields by
    also including all inline fragments, as well as a list of fragments
    referenced by fragment spreads.

    A) Each selection set represented in the document first compares "within"
       its collected set of fields, finding any conflicts between every pair of
       overlapping fields.
       Note: This is the *only time* that a the fields "within" a set are
       compared to each other. After this only fields "between" sets are
       compared.

    B) Also, if any fragment is referenced in a selection set, then a
       comparison is made "between" the original set of fields and the
       referenced fragment.

    C) Also, if multiple fragments are referenced, then comparisons
       are made "between" each referenced fragment.

    D) When comparing "between" a set of fields and a referenced fragment, first
       a comparison is made between each field in the original set of fields and
       each field in the the referenced set of fields.

    E) Also, if any fragment is referenced in the referenced selection set,
       then a comparison is made "between" the original set of fields and the
       referenced fragment (recursively referring to step D).

    F) When comparing "between" two fragments, first a comparison is made
       between each field in the first referenced set of fields and each field
       in the the second referenced set of fields.

    G) Also, any fragments referenced by the first must be compared to the
       second, and any fragments referenced by the second must be compared to
       the first (recursively referring to step F).

    H) When comparing two fields, if both have selection sets, then a comparison
       is made "between" both selection sets, first comparing the set of fields
       in the first selection set with the set of fields in the second.

    I) Also, if any fragment is referenced in either selection set, then a
       comparison is made "between" the other set of fields and the
       referenced fragment.

    J) Also, if two fragments are referenced in both selection sets, then a
       comparison is made "between" the two fragments.
    """
    # Implementation note: all functions detecting conflicts are generators
    # to keep the code simple and only this one collects the generators into a
    # list.
    conflicts = []  # type: List[Conflict]

    field_map, fragment_names = _fields_and_fragments(
        ctx, parent_type, selection_set
    )

    # (A) Find find all conflicts "within" the fields of this selection set.
    for conflict in _conflicts_within(ctx, field_map):
        conflicts.append(conflict)

    compared_fragments = set()  # type: Set[str]
    for fragment_name in fragment_names:
        # (B) Then collect conflicts between these fields and those represented
        # by each spread fragment name found.
        for conflict in _conflicts_between_fields_and_fragment(
            ctx, False, field_map, fragment_name, compared_fragments
        ):
            conflicts.append(conflict)

    # (C) Then compare this fragment with all other fragments found in this
    # selection set to collect conflicts between fragments spread together.
    # This compares each item in the list of fragment names to every other
    # item in that same list (except for itself).
    for frag_1, frag_2 in _permutations(fragment_names):
        for conflict in _conflicts_between_fragments(
            ctx, False, frag_1, frag_2
        ):
            conflicts.append(conflict)

    return conflicts


def _fields_and_fragments(
    ctx: Context,
    parent_type: Optional[GraphQLType],
    selection_set: _ast.SelectionSet,
) -> FieldsAndFragments:
    """
    Given a selection set, return the collection of fields (a mapping
    of response name to field nodes and definitions) as well as a list of
    fragment names referenced via fragment spreads.
    """
    cached = ctx.fields_and_fragments.get(selection_set)
    if cached is not None:
        return cached

    # A field map is an ordered keyed collection, where each key represents a
    # response name and the value at that key is a list of all fields which
    # provide that response name. For every response name, if there are
    # multiple fields, they must be compared to find a potential conflict.
    field_map, fragment_names = _collect_fields_and_fragments(
        ctx, parent_type, selection_set
    )

    ctx.fields_and_fragments[selection_set] = (field_map, fragment_names)
    return field_map, list(deduplicate(fragment_names))


def _referenced_fields_and_fragments(
    ctx: Context, fragment: _ast.FragmentDefinition
) -> FieldsAndFragments:
    """
    Given a fragment definition, return the represented collection of
    fields as well as a list of nested fragment names referenced via
    fragment spreads.
    """
    cached = ctx.fields_and_fragments.get(fragment.selection_set)
    if cached is not None:
        return cached

    fragment_type = _type_from_ast(ctx.schema, fragment.type_condition)
    return _fields_and_fragments(ctx, fragment_type, fragment.selection_set)


def _collect_fields_and_fragments(
    ctx: Context,
    parent_type: Optional[GraphQLType],
    selection_set: _ast.SelectionSet,
    node_and_defs: Optional[FieldMap] = None,
    fragment_names: Optional[List[str]] = None,
) -> FieldsAndFragments:

    if node_and_defs is None:
        node_and_defs = OrderedDict()
    if fragment_names is None:
        fragment_names = []

    for selection in selection_set.selections:
        if isinstance(selection, _ast.Field):
            fieldname = selection.name.value

            fielddef = (
                parent_type.field_map.get(fieldname, None)
                if isinstance(parent_type, (ObjectType, InterfaceType))
                else None
            )

            response_name = (
                selection.alias.value
                if selection.alias and selection.alias.value
                else fieldname
            )

            if response_name not in node_and_defs:
                node_and_defs[response_name] = []

            node_and_defs[response_name].append(
                (parent_type, selection, fielddef)
            )

        elif isinstance(selection, _ast.FragmentSpread):
            fragment_names.append(selection.name.value)

        elif isinstance(selection, _ast.InlineFragment):
            type_condition = selection.type_condition

            inline_fragment_type = (
                _type_from_ast(ctx.schema, type_condition)
                if type_condition
                else parent_type
            )

            _collect_fields_and_fragments(
                ctx,
                inline_fragment_type,
                selection.selection_set,
                node_and_defs=node_and_defs,
                fragment_names=fragment_names,
            )

    return node_and_defs, fragment_names


def _conflicts_within(ctx: Context, field_map: FieldMap) -> Iterator[Conflict]:
    """
    Collect all Conflicts "within" one collection of fields.
    """
    for response_name, fields in field_map.items():
        # This compares every field in the list to every other field in this
        # list (except to itself). If the list only has one item, nothing
        # needs to be compared.
        for field_1, field_2 in _permutations(fields):
            conflict = _find_conflict(
                ctx,
                False,  # within one collection is never mutually exclusive
                response_name,
                field_1,
                field_2,
            )
            if conflict:
                yield conflict


def _conflicts_between(
    ctx: Context,
    parents_mutually_exclusive: bool,
    field_map_1: FieldMap,
    field_map_2: FieldMap,
) -> Iterator[Conflict]:
    """
    Collect all Conflicts between two collections of fields. This is
    similar to, but different from the `collectConflictsWithin` function above.
    This check assumes that `collectConflictsWithin` has already been called
    on each provided collection of fields. This is true because this
    validator traverses each individual selection set.
    """
    for response_name, fields_1 in field_map_1.items():
        fields_2 = field_map_2.get(response_name)
        if fields_2 is None:
            continue

        for field_1 in fields_1:
            for field_2 in fields_2:
                conflict = _find_conflict(
                    ctx,
                    parents_mutually_exclusive,
                    response_name,
                    field_1,
                    field_2,
                )
                if conflict:
                    yield conflict


def _conflicts_between_fields_and_fragment(
    ctx: Context,
    mutually_exclusive: bool,
    field_map: FieldMap,
    fragment_name: str,
    compared_fragments: Set[str],
) -> Iterator[Conflict]:
    """
    Collect all conflicts found between a set of fields and a fragment
    reference including via spreading in any nested fragments.
    """
    # Memoize so a fragment is not compared for conflicts more than once.
    if fragment_name in compared_fragments:
        return

    compared_fragments.add(fragment_name)
    fragment_def = ctx.fragments.get(fragment_name)
    if not fragment_def:
        return

    ff = _referenced_fields_and_fragments(ctx, fragment_def)
    fragment_field_map, fragment_fragment_names = ff

    # ??
    # Do not compare a fragment's fieldMap to itself.
    if field_map is fragment_field_map:
        return

    # (D) First collect any conflicts between the provided collection of fields
    # and the collection of fields represented by the given fragment.
    for c in _conflicts_between(
        ctx, mutually_exclusive, field_map, fragment_field_map
    ):
        yield c

    # (E) Then collect any conflicts between the provided collection of fields
    # and any fragment names found in the given fragment.
    for fragment in fragment_fragment_names:
        for c in _conflicts_between_fields_and_fragment(
            ctx, mutually_exclusive, field_map, fragment, compared_fragments
        ):
            yield c


def _conflicts_between_fragments(
    ctx: Context,
    mutually_exclusive: bool,
    fragment_1: Optional[str],
    fragment_2: Optional[str],
) -> Iterator[Conflict]:
    """
    Collect all conflicts found between two fragments, including via
    spreading in any nested fragments.
    """
    if (not fragment_1) or (not fragment_2) or fragment_1 == fragment_2:
        return

    # Avoid comparing fragments twice and double reporting
    # The comparison order doesn't matter, hence the weird cache key
    cache_key = (tuple(sorted([fragment_1, fragment_2])), mutually_exclusive)
    if cache_key in ctx.compared_fragment_pairs:
        return

    ctx.compared_fragment_pairs.add(cache_key)  # type: ignore

    def_1 = ctx.fragments.get(fragment_1)
    def_2 = ctx.fragments.get(fragment_2)

    if def_1 is None or def_2 is None:
        return

    fields_1, fragments_1 = _referenced_fields_and_fragments(ctx, def_1)
    fields_2, fragments_2 = _referenced_fields_and_fragments(ctx, def_2)

    # (F) First, collect all conflicts between these two collections of fields
    # (not including any nested fragments).
    for c in _conflicts_between(ctx, mutually_exclusive, fields_1, fields_2):
        yield c

    # (G) Then collect conflicts between the first fragment and any nested
    # fragments spread in the second fragment.
    for i, fragment in enumerate(fragments_1):
        for c in _conflicts_between_fragments(
            ctx, mutually_exclusive, fragment, _at(fragment_2, i)
        ):
            yield c

    # (G) Then collect conflicts between the second fragment and any nested
    # fragments spread in the first fragment.
    for i, fragment in enumerate(fragments_2):
        for c in _conflicts_between_fragments(
            ctx, mutually_exclusive, _at(fragment_1, i), fragment
        ):
            yield c


def _find_conflict(
    ctx: Context,
    parents_mutually_exclusive: bool,
    response_name: str,
    field_1: FieldDef,
    field_2: FieldDef,
) -> Optional[Conflict]:
    """
    Determine if there is a conflict between two particular fields,
    including comparing their sub-fields.
    """
    parent_1, node_1, def_1 = field_1
    parent_2, node_2, def_2 = field_2

    # If it is known that two fields could not possibly apply at the same
    # time, due to the parent types, then it is safe to permit them to diverge
    # in aliased field or arguments used as they will not present any ambiguity
    # by differing.
    # It is known that two parent types could never overlap if they are
    # different Object types. Interface or Union types might overlap - if not
    # in the current state of the schema, then perhaps in some future version,
    # thus may not safely diverge.
    mutually_exclusive = parents_mutually_exclusive or (
        parent_1 != parent_2
        and isinstance(parent_1, ObjectType)
        and isinstance(parent_2, ObjectType)
    )

    # The return type for each field.
    type_1 = def_1.type if def_1 else None
    type_2 = def_2.type if def_2 else None
    name_1 = node_1.name.value
    name_2 = node_2.name.value

    if not mutually_exclusive:
        # Two aliases must refer to the same field.
        if name_1 != name_2:
            reason = '"%s" and "%s" are different fields' % (name_1, name_2)
            return response_name, reason, (node_1, node_2)

        # Two field calls must have the same arguments.
        if not _same_arguments(node_1.arguments or [], node_2.arguments or []):
            reason = '"%s" and "%s" have different arguments' % (name_1, name_2)
            return response_name, reason, (node_1, node_2)

    if type_1 and type_2 and _types_conflict(type_1, type_2):
        reason = "they return conflicting types %s and %s" % (type_1, type_2)
        return response_name, reason, (node_1, node_2)

    # Collect and compare sub-fields. Use the same "visited fragment names" list
    # for both collections so fields in a fragment reference are never
    # compared to themselves.
    if node_1.selection_set and node_2.selection_set:
        subconflicts = list(
            _conflicts_between_subselections(
                ctx,
                mutually_exclusive,
                unwrap_type(type_1) if type_1 else None,
                node_1.selection_set,
                unwrap_type(type_2) if type_2 else None,
                node_2.selection_set,
            )
        )
        if subconflicts:
            reason = " and ".join(
                [
                    'subfields "%s" conflict (%s)' % (name, reason_)
                    for name, reason_, _ in subconflicts
                ]
            )
            nodes = sorted(
                [node_1, node_2]
                + list(flatten(nodes for _, _, nodes in subconflicts)),
                key=lambda n: n.loc,
            )
            return response_name, reason, nodes

    return None


def _conflicts_between_subselections(
    ctx: Context,
    mutually_exclusive: bool,
    parent_type_1: Optional[GraphQLType],
    node_1: _ast.SelectionSet,
    parent_type_2: Optional[GraphQLType],
    node_2: _ast.SelectionSet,
) -> Iterator[Conflict]:
    """
    Find all conflicts found between two selection sets, including those
    found via spreading in fragments. Called when determining if conflicts
    exist between the sub-fields of two overlapping fields.
    """
    field_map_1, fragments_1 = _fields_and_fragments(ctx, parent_type_1, node_1)
    field_map_2, fragments_2 = _fields_and_fragments(ctx, parent_type_2, node_2)

    # (H) First, collect all conflicts between these two collections of field.
    for c in _conflicts_between(
        ctx, mutually_exclusive, field_map_1, field_map_2
    ):
        yield c

    # (I) Then collect conflicts between the first collection of fields and
    # those referenced by each fragment name associated with the second.
    for fragment in fragments_2:
        for c in _conflicts_between_fields_and_fragment(
            ctx, mutually_exclusive, field_map_1, fragment, set()
        ):
            yield c

    # (I) Then collect conflicts between the second collection of fields and
    # those referenced by each fragment name associated with the first.
    for fragment in fragments_1:
        for c in _conflicts_between_fields_and_fragment(
            ctx, mutually_exclusive, field_map_2, fragment, set()
        ):
            yield c

    # (J) Also collect conflicts between any fragment names by the first and
    # fragment names by the second. This compares each item in the first set of
    # names to each item in the second set of names.
    for fragment_1, fragment_2 in _cross(fragments_1, fragments_2):
        for c in _conflicts_between_fragments(
            ctx, mutually_exclusive, fragment_1, fragment_2
        ):
            yield c


def _same_arguments(
    args_1: List[_ast.Argument], args_2: List[_ast.Argument]
) -> bool:
    """
    Given two lists of arguments, check all arguments have the same name
    and values with no extra / missing argument.
    """
    if len(args_1) != len(args_2):
        return False

    s1 = sorted(args_1, key=lambda a: a.name.value)
    s2 = sorted(args_2, key=lambda a: a.name.value)

    return all(
        (
            (
                a1.name.value == a2.name.value
                and type(a1.value) == type(a2.value)  # noqa: E721
                and a1.value.value == a2.value.value  # type: ignore
            )
            for a1, a2 in zip(s1, s2)
        )
    )


def _types_conflict(type_1: GraphQLType, type_2: GraphQLType) -> bool:
    """
    Two types conflict if both types could not apply to a value
    simultaneously. Composite types are ignored as their individual field
    types will be compared later recursively. However List and Non-Null types
    must match.
    """
    if isinstance(type_1, WrappingType) or isinstance(type_2, WrappingType):
        return type(type_1) != type(type_2) or _types_conflict(
            type_1.type, type_2.type  # type: ignore
        )

    if isinstance(type_1, GraphQLLeafType) or isinstance(
        type_2, GraphQLLeafType
    ):
        return type_1 != type_2

    return False
