import difflib

from collections import namedtuple
from six.moves import zip_longest

_BLANK = object()


class Conflict(object):
    def __init__(self, mine, other, base):
        self.mine = [mine] if mine is not _BLANK else None
        self.other = [other] if other is not _BLANK else None
        self.base = [base] if base is not _BLANK else None

    @classmethod
    def from_prepared(cls, mine, other, base):
        m = mine[0] if mine else _BLANK
        o = other[0] if other else _BLANK
        b = base[0] if base else _BLANK
        conflict = cls(m, o, b)
        for m, o, b in zip_longest(mine[1:], other[1:], base[1:],
                                   fillvalue=_BLANK):
            conflict.update(m, o, b)
        return conflict

    @classmethod
    def resolve_sub_conflict(cls, mine, other):
        c = cls.from_prepared(mine, other, [])
        return c.resolve_conflict()

    def update(self, m, o, b):
        if m is not _BLANK:
            self.mine.append(m)
        if o is not _BLANK:
            self.other.append(o)
        if b is not _BLANK:
            self.base.append(b)

    def resolve_conflict(self):
        if self.mine is None and self.other is not None:
            return self.other
        if self.other is None and self.mine is not None:
            return self.mine
        if self.other == self.mine:
            return self.mine
        combined = set(self.mine or []) | set(self.other or [])
        if (self.base is not None and
                not any(i in combined for i in self.base)):
            return [self]
        mine = self.mine if self.mine else []
        other = self.other if self.other else []
        i_mine, i_other = iter(mine), iter(other)
        result, new_mine, new_other = [], [], []
        for diff in difflib.Differ().compare([str(i) for i in other],
                                             [str(i) for i in mine]):
            if ((diff.startswith('+') and (new_other or result)) or
                    (diff.startswith('-') and (new_mine or result)) or
                    (result and (new_other or new_mine))):
                if new_mine or new_other:
                    result.insert(0, Conflict.from_prepared(new_mine,
                                                            new_other,
                                                            []))
                result.extend(Conflict.resolve_sub_conflict(
                              [i for i in i_mine],
                              [i for i in i_other]))
                break
            elif diff.startswith('-'):
                new_other.append(next(i_other))
            elif diff.startswith('+'):
                new_mine.append(next(i_mine))
            else:
                next(i_other)
                result.append(next(i_mine))
        return result

    def _asdict(self):
        return {
            'my_op': 'CHANGED',
            'my_val': self.mine,
            'other_op': 'CHANGED',
            'other_val': self.other,
            'base_val': self.base
        }

    def __eq__(self, other):
        return (self.mine == other.mine and self.other == other.other and
                self.base == other.base)

    def __str__(self):
        return 'Conflict{}'.format(str((self.mine, self.other, self.base)))

    def __repr__(self):
        return str(self)


def merge_lists(base, mine, other):
    if mine == other:
        return mine
    if other == base:
        return mine
    if mine == base:
        return other
    result = []
    last_conflict = False
    for i, (m, o, b) in enumerate(zip_longest(mine, other, base,
                                              fillvalue=_BLANK)):
        if (m == o and _BLANK not in (m, o) or
                isinstance(m, dict) and isinstance(o, dict)):
            result.append(m)
        else:  # Conflict
            if last_conflict:
                c = result[-1]
                c.update(m, o, b)
            else:
                c = Conflict(m, o, b)
                result.append(c)
            last_conflict = True
            continue
        last_conflict = False
    offset = 0
    for i, r in enumerate(result[:]):
        if isinstance(r, Conflict):
            c = r.resolve_conflict()
            result = result[:i + offset] + c + result[i + offset + 1:]
            offset += len(c) - 1
    return result


class JsonDiff(object):
    """
    Compares two json objects and stores the differences.
    Only the outermost objects are considered, the comparison does not recurse
    into nested objects.
    """
    def __init__(self, old, new):
        set_new, set_old = set(new), set(old)
        common = set_new & set_old
        self.added = list(set_new - common)
        self.removed = list(set_old - common)
        self.changed = [k for k in common if new[k] != old[k]]
        self.unchanged = [k for k in common if new[k] == old[k]]

    def op_for_field(self, field_name):
        for operation in ('ADDED', 'UNCHANGED', 'CHANGED', 'REMOVED'):
            if field_name in getattr(self, operation.lower()):
                return operation
        return None


FieldDiff = namedtuple(
    'DiffOp', ['my_op', 'my_val', 'other_op', 'other_val', 'base_val'])


def merge_jsons(base, mine, other):
    """
    Performs a 3-way merge of mine and other using base as the common ancestor.

    Some conflicts are automatically resolved, e.g. mine and other both delete
    the same field.
    Conflicts that can't be automatically resolved (e.g. mine and other assign
    different values to the same field) are serialized into the merged json in
    a way that can be used for a later manual resolve:

        field: { __CONFLICT:
                    base_val: X,  # the original value of the field
                    my_val: Y,    # the value assigned by mine json
                    my_op: Z,     # the operation performed by mine json
                    other_val: U, # the value assigned by other json
                    other_op: W,  # the operation performed by other json
                }

        my_op and other_op can take any of this values: 'ADDED', 'REMOVED',
        'CHANGED', 'UNCHAGED'. If my_op == 'DELETED' then my_value == None
        (the same applies to other_op and other_val respectively).

    The merge recurses into dictionaries but considers lists as atomic values.
    Returns a tuple of the form (merged, had_conflict).
    """
    def build_merge_dict(base, mine, other):
        my_diff = JsonDiff(base, mine)
        other_diff = JsonDiff(base, other)
        base, mine, other = (j if isinstance(j, dict) else {}
                             for j in (base, mine, other))
        all_fields = set(base.keys()).union(mine.keys()).union(other.keys())
        merge_dict = {}
        for k in all_fields:
            base_val, my_val, other_val = (
                base.get(k, {}), mine.get(k), other.get(k))
            if isinstance(my_val, dict) and isinstance(other_val, dict):
                merge_dict[k] = build_merge_dict(base_val, my_val, other_val)
            if isinstance(my_val, list) and isinstance(other_val, list):
                merge_dict[k] = merge_lists(base_val, my_val, other_val)
            else:
                merge_dict[k] = FieldDiff(base_val=base.get(k),
                                          my_val=my_val,
                                          my_op=my_diff.op_for_field(k),
                                          other_val=other_val,
                                          other_op=other_diff.op_for_field(k))
        return merge_dict

    def eq_vals(diff):
        return diff.other_val == diff.my_val

    def conflict(diff):
        return {'__CONFLICT': diff._asdict()}

    def resolve_json(merge_dict):
        out_json = {}
        had_conflict = False
        for key, diff in merge_dict.items():
            if isinstance(diff, dict):
                out_json[key], rconflict = resolve_json(diff)
                had_conflict = had_conflict or rconflict
            if isinstance(diff, list):
                for i, item in enumerate(diff):
                    if isinstance(item, Conflict):
                        if (item.mine and isinstance(item.mine[0], dict) and
                                '__CONFLICT' in item.mine[0]):
                            diff[i] = item.mine[0]
                        else:
                            diff[i] = conflict(item)
                        had_conflict = True
                out_json[key] = diff
            elif diff.my_op in ('UNCHANGED', None):
                if diff.other_op != 'REMOVED':
                    out_json[key] = diff.other_val
            elif diff.my_op == 'ADDED':
                if diff.other_op != 'ADDED' or eq_vals(diff):
                    out_json[key] = diff.my_val
                else:
                    out_json[key] = conflict(diff)
                    had_conflict = True
            elif diff.my_op == 'REMOVED':
                if diff.other_op == 'CHANGED':
                    out_json[key] = conflict(diff)
                    had_conflict = True
            elif diff.my_op == 'CHANGED':
                if diff.other_op == 'UNCHANGED' or eq_vals(diff):
                    out_json[key] = diff.my_val
                else:
                    out_json[key] = conflict(diff)
                    had_conflict = True
        return out_json, had_conflict

    return resolve_json(build_merge_dict(base, mine, other))
