# CodeQ: an online programming tutor.
# Copyright (C) 2015 UL FRI
#
# This program is free software: you can redistribute it and/or modify it under
# the terms of the GNU Affero 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 Affero General Public License for more
# details.
#
# You should have received a copy of the GNU Affero General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.

import difflib
from itertools import product
import time

from prolog.util import tokenize, stringify, parse, interesting_ranges, rename_vars_list
from .util import PQueue, startswith, endswith

# Starting from [code], find a sequence of edits that transforms it into a
# correct predicate for [name]. The [test] function is used to test generated
# programs.
# Return (solution, edits, time spent, #programs checked). If no solution is
# found within [timeout] seconds, return solution='' and edits=[].
def fix(code, edits, test, timeout=30, debug=False):
    def step(program, path=None):
        tokens = program.leaves()
        for part, range_path in interesting_ranges(program):
            names = {}
            part_normal = tuple(rename_vars_list(part, names))
            for (path, a, b), (p, uids) in edits.items():
                if path == range_path and a == part_normal:
                    reverse_names = {v: k for k, v in names.items()}
                    b_real = tuple(rename_vars_list(b, reverse_names))
                    new_tokens = []
                    idx = None
                    for i, t in enumerate(tokens):
                        if t.pos >= part[0].pos and t.pos+len(t.val) <= part[-1].pos+len(part[-1].val):
                            if idx is None:
                                idx = i
                                new_tokens.extend(b_real)
                        else:
                            new_tokens.append(t)
                    new_code = stringify(new_tokens)
                    new_program = parse(new_code)
                    new_step = (idx, tuple(part), b_real)
                    if new_program is not None:
                        yield (new_program.freeze(), new_step, p)

    # Main loop: best-first search through generated programs.
    todo = PQueue()  # priority queue of candidate solutions
    done = set()     # programs we have already visited
    n_tested = 0
    start_time = time.monotonic()
    total_time = 0

    # Each program gets a task with the sequence of edits that generated it and
    # the associated cost. First candidate with cost 1 is the initial program.
    program = parse(code)
    if program is None:
        return '', [], total_time, n_tested
    todo.push((program.freeze(), (), 1.0), -1.0)

    while total_time < timeout:
        # Get next candidate.
        task = todo.pop()
        if task == None:
            break
        program, path, path_cost = task

        # If we have already seen this code, skip it.
        code = stringify(program)
        if code in done:
            continue
        done.add(code)

        # Print some info about the current task.
        if debug:
            print('Cost {:.12f}'.format(path_cost))
            for idx, a, b in path:
                print('{}: {} → {}'.format(idx, stringify(a), stringify(b)))

        # If the code is correct, we are done.
        n_correct, n_all = test(code)
        if n_correct == n_all:
            return code, path, total_time, n_tested
        n_tested += 1

        # Otherwise generate new solutions.
        for new_program, new_step, new_cost in step(program, path):
            new_path_cost = path_cost * new_cost
            if len(todo) > 500 and new_path_cost < 0.001:
                continue
            new_path = path + (new_step,)
            todo.push((new_program, new_path, new_path_cost), -new_path_cost)

        total_time = time.monotonic() - start_time

    return '', [], total_time, n_tested

# Find (minimal) token ranges in [a] that are changed in [b].
def min_diff(a, b):
    # Special case: inserting/deleting at beginning/end.
    if endswith(b, a):
        return [('insert', 0, 0, 0, len(b)-len(a))]
    if startswith(b, a):
        return [('insert', len(a), len(a), len(a), len(b))]
    if endswith(a, b):
        return [('delete', 0, len(a)-len(b), 0, 0)]
    if startswith(a, b):
        return [('delete', len(b), len(a), len(b), len(b))]
    return difflib.SequenceMatcher(a=a, b=b, autojunk=False).get_opcodes()

# Return a list of hint objects for the web app.
def fix_hints(code, steps):
    hints = []
    tokens = tokenize(code)
    for idx, a, b in steps:
        for tag, i1, i2, j1, j2 in min_diff(a, b):
            if tag == 'equal':
                continue
            if tag == 'insert':
                hint_id = 'monkey_insert'
                if idx+i1 >= len(tokens):
                    pos_start = len(code)-1
                else:
                    pos_start = tokens[idx+i1].pos
                pos_end = pos_start+1
            elif tag == 'delete':
                hint_id = 'monkey_remove'
                pos_start = tokens[idx+i1].pos
                pos_end = tokens[idx+i2-1].pos + len(tokens[idx+i2-1].val)
            elif tag == 'replace':
                hint_id = 'monkey_change'
                pos_start = tokens[idx+i1].pos
                pos_end = tokens[idx+i2-1].pos + len(tokens[idx+i2-1].val)
            hints += [{'id': hint_id, 'start': pos_start, 'end': pos_end}]
        tokens[idx:idx+len(a)] = [t.clone(pos=tokens[idx].pos) for t in b]

    changed = True
    while changed:
        changed = False
        for h1, h2 in product(hints, hints):
            if h1 is h2 or h2['start'] <= h1['start']:
                continue
            if h1['id'] == h2['id'] == 'monkey_insert' and h2['start'] - h1['start'] < 5:
                hints.remove(h1)
                hints.remove(h2)
                hints.append({'id': 'monkey_change', 'start': h1['start'], 'end': h2['end']-1})
                changed = True
                break

    return hints