"""Pruebas del laboratorio. LAB_DIR dice dónde está el código: lab o solution.

Cada prueba compila un main propio con los archivos de esa carpeta, por separado de las
pruebas de ustedes. Corren con ASan y UBSan: una fuga, o un aviso como un overflow, también
hacen fallar la prueba.
"""
import os
import pathlib
import re
import subprocess
import tempfile
import unittest

HERE = pathlib.Path(__file__).parent
LAB_DIR = os.environ.get("LAB_DIR", "solution")
SOURCE = HERE / LAB_DIR
LAB = HERE / "lab"
DATA = LAB / "data"
FLAGS = ["-Wall", "-Wextra", "-std=c17", "-g", "-fsanitize=address,undefined"]


def source(name):
    """El archivo de la carpeta que se prueba. Si no está ahí, es uno de los ya hechos de lab/."""
    path = SOURCE / name
    return path if path.exists() else LAB / name


def build_and_run(main_source, sources, args=()):
    """Devuelve (salida, código de salida) de un main propio, en una carpeta temporal."""
    with tempfile.TemporaryDirectory() as name:
        folder = pathlib.Path(name)
        binary = folder / "driver"
        inputs = list(map(str, sources))
        if main_source is not None:
            driver = folder / "driver.c"
            driver.write_text(main_source, encoding="utf-8")
            inputs.insert(0, str(driver))
        built = subprocess.run(
            ["gcc", *FLAGS, f"-I{LAB}", *inputs, "-o", str(binary)],
            text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
        )
        if built.returncode != 0:
            raise AssertionError(f"No compila:\n{built.stdout}")
        try:
            done = subprocess.run(
                [str(binary), *map(str, args)], cwd=folder, text=True, encoding="utf-8", errors="replace",
                stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=60,
            )
        except subprocess.TimeoutExpired:
            raise AssertionError("El programa no terminó en 60 segundos.") from None
        return done.stdout, done.returncode


def writable_globals(path):
    """Los símbolos de datos que se pueden escribir: las variables globales del archivo."""
    with tempfile.TemporaryDirectory() as name:
        obj = pathlib.Path(name) / "file.o"
        subprocess.run(["gcc", "-std=c17", "-fno-pic", f"-I{LAB}", "-c", str(path), "-o", str(obj)], check=True)
        done = subprocess.run(["nm", str(obj)], text=True, stdout=subprocess.PIPE, check=True)
    return [line.split()[-1] for line in done.stdout.splitlines() if re.search(r" [bBdD] ", line)]


class LabCase(unittest.TestCase):
    longMessage = False

    def check(self, result, wanted, what):
        out, code = result
        if code != 0:
            self.fail(f"{what}: el programa terminó con error.\n{out}")
        if out.strip() != wanted.strip():
            self.fail(f"{what}\n  se esperaba: {wanted.strip()}\n  se obtuvo:   {out.strip()}")


COMPARE_MAIN = """
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include "compare.h"
static int sign(int x) { return (x > 0) - (x < 0); }
int main(void) {
@BODY@
return 0;
}
"""


@unittest.skipUnless((SOURCE / "compare.c").exists(), f"no está {LAB_DIR}/compare.c")
class Comparators(LabCase):
    def run_body(self, body):
        return build_and_run(COMPARE_MAIN.replace("@BODY@", body), [source("compare.c")])

    def test_passengers_ascending(self):
        body = """
        Trip a = {"Ate", 9, 1.0}; Trip b = {"Ate", 12, 1.0};
        printf("%d %d %d\\n", sign(compare_by_passengers(&a, &b)), sign(compare_by_passengers(&b, &a)),
               sign(compare_by_passengers(&a, &a)));
        """
        self.check(self.run_body(body), "-1 1 0", "compare_by_passengers no ordena de menos a más.")

    def test_passengers_with_extreme_values(self):
        body = """
        Trip low = {"Ate", INT_MIN, 1.0}; Trip one = {"Ate", 1, 1.0}; Trip top = {"Ate", INT_MAX, 1.0};
        printf("%d %d %d %d\\n", sign(compare_by_passengers(&low, &one)), sign(compare_by_passengers(&one, &low)),
               sign(compare_by_passengers(&low, &top)), sign(compare_by_passengers(&top, &low)));
        """
        self.check(self.run_body(body), "-1 1 -1 1",
                   "compare_by_passengers falla con INT_MIN e INT_MAX. ¿Está restando?")

    def test_fare_sees_small_differences(self):
        body = """
        Trip a = {"Ate", 1, 2.9}; Trip b = {"Ate", 1, 2.5};
        printf("%d %d %d\\n", sign(compare_by_fare_desc(&a, &b)), sign(compare_by_fare_desc(&b, &a)),
               sign(compare_by_fare_desc(&a, &a)));
        """
        self.check(self.run_body(body), "-1 1 0",
                   "compare_by_fare_desc debe poner primero 2.9 y distinguirlo de 2.5. ¿La resta se volvió int?")

    def test_route_then_passengers(self):
        body = """
        Trip a = {"Ate", 9, 1.0}; Trip b = {"Callao", 50, 1.0}; Trip c = {"Ate", 12, 1.0};
        printf("%d %d %d %d %d\\n", sign(compare_by_route_then_passengers(&a, &b)),
               sign(compare_by_route_then_passengers(&b, &a)), sign(compare_by_route_then_passengers(&c, &a)),
               sign(compare_by_route_then_passengers(&a, &c)), sign(compare_by_route_then_passengers(&a, &a)));
        """
        self.check(self.run_body(body), "-1 1 -1 1 0",
                   "compare_by_route_then_passengers: primero la ruta; en la misma ruta, más pasajeros primero.")

    def test_sort_trips_program(self):
        sources = [LAB / "sort_trips.c", source("compare.c")]
        wanted = {
            "pasajeros": ["Ate 9", "Ate 12", "Chosica 18", "Chosica 22", "Callao 25", "Callao 31"],
            "tarifa": ["Callao 31", "Callao 25", "Chosica 22", "Chosica 18", "Ate 9", "Ate 12"],
            "ruta": ["Ate 12", "Ate 9", "Callao 31", "Callao 25", "Chosica 22", "Chosica 18"],
        }
        for criterion, order in wanted.items():
            with self.subTest(criterion=criterion):
                out, code = build_and_run(None, sources, [criterion])
                self.assertEqual(code, 0, out)
                got = [" ".join(line.split()[:2]) for line in out.splitlines()]
                if got != order:
                    self.fail(f"sort_trips {criterion}\n  se esperaba: {order}\n  se obtuvo:   {got}")


OPS_MAIN = """
#include <stdio.h>
#include <stdlib.h>
#include "array_ops.h"
static int plus_one(int x) { return x + 1; }
static int is_odd(int x) { return x % 2 != 0; }
static int digits(int acc, int x) { return acc * 10 + x; }
typedef struct { int low; int high; int calls; } Range;
static int in_range(int x, void *context) {
    Range *r = context;
    r->calls++;
    return x >= r->low && x <= r->high;
}
int main(void) {
@BODY@
return 0;
}
"""


@unittest.skipUnless((SOURCE / "array_ops.c").exists(), f"no está {LAB_DIR}/array_ops.c")
class ArrayOps(LabCase):
    def run_body(self, body):
        return build_and_run(OPS_MAIN.replace("@BODY@", body), [source("array_ops.c")])

    def test_map(self):
        body = """
        int in[3] = {1, 2, 3}; int out[3] = {0, 0, 0};
        array_map(in, 3, plus_one, out);
        printf("%d %d %d %d\\n", out[0], out[1], out[2], in[0]);
        """
        self.check(self.run_body(body), "2 3 4 1", "array_map no guarda transform(in[i]) en out[i], o cambia in.")

    def test_map_on_the_same_array(self):
        body = """
        int a[3] = {1, 2, 3};
        array_map(a, 3, plus_one, a);
        printf("%d %d %d\\n", a[0], a[1], a[2]);
        """
        self.check(self.run_body(body), "2 3 4", "array_map debe servir si in y out son el mismo arreglo.")

    def test_filter_keeps_order_and_counts(self):
        body = """
        int in[5] = {1, 2, 3, 4, 5}; int out[5] = {0, 0, 0, 0, 0};
        int kept = array_filter(in, 5, is_odd, out);
        printf("%d: %d %d %d %d\\n", kept, out[0], out[1], out[2], out[3]);
        """
        self.check(self.run_body(body), "3: 1 3 5 0", "array_filter no copia en orden, o no devuelve cuántos.")

    def test_filter_on_the_same_array(self):
        body = """
        int a[4] = {2, 3, 4, 5};
        int kept = array_filter(a, 4, is_odd, a);
        printf("%d: %d %d\\n", kept, a[0], a[1]);
        """
        self.check(self.run_body(body), "2: 3 5", "array_filter debe servir si in y out son el mismo arreglo.")

    def test_filter_stays_inside_the_array(self):
        body = """
        int *in = malloc(3 * sizeof(int)); int *out = malloc(3 * sizeof(int));
        if (in == NULL || out == NULL) { return 1; }
        in[0] = 1; in[1] = 3; in[2] = 5;
        printf("%d\\n", array_filter(in, 3, is_odd, out));
        free(in); free(out);
        """
        self.check(self.run_body(body), "3", "array_filter se sale del arreglo, o no cuenta todos.")

    def test_fold_goes_left_to_right(self):
        body = """
        int in[3] = {1, 2, 3};
        printf("%d %d\\n", array_fold(in, 3, digits, 0), array_fold(in, 3, digits, 9));
        """
        self.check(self.run_body(body), "123 9123", "array_fold no combina de izquierda a derecha desde initial.")

    def test_empty_arrays(self):
        body = """
        int a[1] = {7}; int out[1] = {8};
        array_map(a, 0, plus_one, out);
        int kept = array_filter(a, 0, is_odd, out);
        Range r = {0, 10, 0};
        printf("%d %d %d %d %d\\n", out[0], kept, array_fold(a, 0, digits, 5),
               array_count_if(a, 0, in_range, &r), count_above(a, 0, 1));
        """
        self.check(self.run_body(body), "8 0 5 0 0", "Con n igual a 0 no se debe tocar nada.")

    def test_count_if_passes_the_context(self):
        body = """
        int a[5] = {1, 5, 10, 15, 20};
        Range r = {5, 15, 0};
        int count = array_count_if(a, 5, in_range, &r);
        printf("%d %d\\n", count, r.calls);
        """
        self.check(self.run_body(body), "3 5", "array_count_if debe llamar a accept una vez por elemento, con el contexto.")

    def test_count_above(self):
        body = """
        int a[5] = {14, 9, 20, 11, 15};
        printf("%d %d %d\\n", count_above(a, 5, 14), count_above(a, 5, 8), count_above(a, 5, 20));
        """
        self.check(self.run_body(body), "2 5 0", "count_above no cuenta los mayores que el umbral.")

    def test_count_above_uses_the_callback_without_globals(self):
        path = source("array_ops.c")
        names = writable_globals(path)
        if names:
            self.fail(f"array_ops.c no debe tener variables globales. Encontré: {names}")
        body = re.search(r"int count_above\(.*?\n}", path.read_text(encoding="utf-8"), re.S).group(0)
        if "array_count_if" not in body:
            self.fail("count_above debe usar array_count_if.")

    def test_their_tests_pass(self):
        path = SOURCE / "ops_tests.c"
        text = re.sub(r"//.*", "", path.read_text(encoding="utf-8"))
        for name in ("array_filter", "array_fold", "count_above"):
            if name + "(" not in text:
                self.fail(f"ops_tests.c todavía no prueba {name}.")
        out, code = build_and_run(None, [path, source("array_ops.c")])
        self.assertEqual(code, 0, out)


# Un problema que el backtracker no conoce: cadenas de bits, con la opción de prohibir el bit 1
# en un paso, y de detenerse en la solución número stop_at. Lleva la cuenta de todo lo que ocurre.
ENGINE_MAIN = """
#include <stdio.h>
#include "backtrack.h"
#define MAX_STEPS 8
typedef struct {
    int steps; int bits[MAX_STEPS]; int forbid_one_at; int stop_at; int solutions;
    int places; int undos; int wrong_undos; int checks; int wrong_context; int depth; int max_depth;
} State;
static int bits_options(void *context, int step) { (void) context; (void) step; return 2; }
static int bits_is_valid(void *context, int step, int option) {
    State *s = context;
    s->checks++;
    return !(option == 1 && step == s->forbid_one_at);
}
static void bits_place(void *context, int step, int option) {
    State *s = context;
    s->bits[step] = option; s->places++; s->depth++;
    if (s->depth > s->max_depth) { s->max_depth = s->depth; }
}
static void bits_undo(void *context, int step, int option) {
    State *s = context;
    if (s->bits[step] != option) { s->wrong_undos++; }
    s->bits[step] = -1; s->undos++; s->depth--;
}
static int bits_on_solution(void *context) {
    State *s = context;
    s->solutions++;
    return s->solutions == s->stop_at;
}
static State search(int steps, int forbid, int stop_at, long *nodes) {
    State s = {.steps = steps, .forbid_one_at = forbid, .stop_at = stop_at};
    for (int i = 0; i < MAX_STEPS; i++) { s.bits[i] = -1; }
    Problem p = {steps, bits_options, bits_is_valid, bits_place, bits_undo, bits_on_solution};
    *nodes = backtrack(&p, &s);
    return s;
}
int main(void) {
    long nodes = 0;
@BODY@
    return 0;
}
"""


@unittest.skipUnless((SOURCE / "backtrack.c").exists(), f"no está {LAB_DIR}/backtrack.c")
class Engine(LabCase):
    def run_body(self, body):
        return build_and_run(ENGINE_MAIN.replace("@BODY@", body), [source("backtrack.c")])

    def test_visits_the_whole_tree(self):
        body = """
        State s = search(3, -1, 0, &nodes);
        printf("%d soluciones, %ld nodos\\n", s.solutions, nodes);
        """
        self.check(self.run_body(body), "8 soluciones, 15 nodos",
                   "Con 3 pasos de 2 opciones, el árbol tiene 8 hojas y 15 nodos, contando la raíz.")

    def test_every_place_has_its_undo(self):
        body = """
        State s = search(3, -1, 0, &nodes);
        printf("%d %d %d %d\\n", s.places, s.undos, s.wrong_undos, s.depth);
        """
        self.check(self.run_body(body), "14 14 0 0", "Cada place debe tener su undo, con los mismos argumentos.")

    def test_stops_when_told_and_still_undoes(self):
        body = """
        State s = search(3, -1, 1, &nodes);
        printf("%d soluciones, %ld nodos, %d %d\\n", s.solutions, nodes, s.places, s.undos);
        """
        self.check(self.run_body(body), "1 soluciones, 4 nodos, 3 3",
                   "Si on_solution devuelve 1 hay que detenerse, y deshacer lo que estaba puesto.")

    def test_invalid_options_are_not_taken(self):
        body = """
        State s = search(3, 1, 0, &nodes);
        printf("%d soluciones, %ld nodos, %d %d\\n", s.solutions, nodes, s.places, s.checks);
        """
        self.check(self.run_body(body), "4 soluciones, 9 nodos, 8 10",
                   "Una opción inválida no se toma, y no se explora lo que hay debajo.")

    def test_zero_steps_is_already_a_solution(self):
        body = """
        State s = search(0, -1, 0, &nodes);
        printf("%d soluciones, %ld nodos, %d\\n", s.solutions, nodes, s.places);
        """
        self.check(self.run_body(body), "1 soluciones, 1 nodos, 0",
                   "Con 0 pasos no hay nada que decidir: es una solución, y un nodo.")

    def test_does_not_know_any_problem(self):
        path = source("backtrack.c")
        text = re.sub(r"//.*", "", path.read_text(encoding="utf-8")).lower()
        includes = re.findall(r'#include\s*"([^"]+)"', text)
        for word in ("queen", "reina", "sudoku", "board", "coloring", "digit"):
            if word in text:
                self.fail(f"backtrack.c no debe saber de ningún problema, y menciona '{word}'.")
        if set(includes) != {"backtrack.h"}:
            self.fail(f"backtrack.c solo debe incluir backtrack.h de este proyecto. Incluye: {includes}")
        names = writable_globals(path)
        if names:
            self.fail(f"backtrack.c no debe tener variables globales. Encontré: {names}")


QUEENS_MAIN = """
#include <stdio.h>
#include "queens.h"
int main(void) {
@BODY@
    return 0;
}
"""


def queens_ok(columns):
    n = len(columns)
    return sorted(columns) == list(range(n)) and all(
        abs(columns[a] - columns[b]) != b - a for a in range(n) for b in range(a + 1, n))


@unittest.skipUnless((SOURCE / "queens.c").exists() and source("backtrack.c").exists(), f"no está {LAB_DIR}/queens.c")
class Queens(LabCase):
    def run_body(self, body):
        return build_and_run(QUEENS_MAIN.replace("@BODY@", body), [source("queens.c"), source("backtrack.c")])

    def test_counts(self):
        body = """
        long nodes = 0;
        for (int n = 1; n <= 8; n++) {
            printf("%ld ", queens_count(n, &nodes));
        }
        printf("%ld\\n", nodes);
        """
        self.check(self.run_body(body), "1 0 0 2 10 4 40 92 2057",
                   "Las soluciones de N reinas para n de 1 a 8, y los nodos de n = 8, no son los esperados.")

    def test_nodes_for_each_size(self):
        body = """
        int columns[8];
        for (int n = 4; n <= 8; n++) {
            long all = 0;
            long first = 0;
            queens_count(n, &all);
            queens_first(n, columns, &first);
            printf("%ld/%ld ", all, first);
        }
        printf("\\n");
        """
        self.check(self.run_body(body), "17/9 54/6 153/32 552/10 2057/114",
                   "Los nodos de N reinas, contándolas todas y hasta la primera, no son los esperados.")

    def test_first_solution_is_valid_and_stops(self):
        body = """
        int columns[8];
        long nodes = 0;
        int found = queens_first(8, columns, &nodes);
        printf("%d %ld", found, nodes);
        for (int i = 0; i < 8; i++) { printf(" %d", columns[i]); }
        printf("\\n");
        """
        out, code = self.run_body(body)
        self.assertEqual(code, 0, out)
        parts = out.split()
        self.assertEqual(parts[0], "1", "queens_first debe devolver 1 con n = 8.")
        self.assertEqual(parts[1], "114", "queens_first debe detenerse en la primera solución, tras 114 nodos.")
        self.assertTrue(queens_ok(list(map(int, parts[2:]))), f"Esas reinas se atacan: {parts[2:]}")

    def test_first_without_solution(self):
        body = """
        int columns[3];
        long nodes = 0;
        printf("%d\\n", queens_first(3, columns, &nodes));
        """
        self.check(self.run_body(body), "0", "Con n = 3 no hay solución.")


def board_lines(text):
    return [line for line in text.splitlines() if re.fullmatch(r"[1-9]{9}", line)]


def valid_solution(puzzle, lines):
    if len(lines) != 9:
        return False
    wanted = set("123456789")
    rows = [list(line) for line in lines]
    for i in range(9):
        if set(rows[i]) != wanted or {row[i] for row in rows} != wanted:
            return False
    for r in range(0, 9, 3):
        for c in range(0, 9, 3):
            if {rows[x][y] for x in range(r, r + 3) for y in range(c, c + 3)} != wanted:
                return False
    return all(puzzle[r][c] in ("0", rows[r][c]) for r in range(9) for c in range(9))


@unittest.skipUnless((SOURCE / "sudoku.c").exists() and source("backtrack.c").exists(), f"no está {LAB_DIR}/sudoku.c")
class Sudoku(LabCase):
    def solve(self, name):
        sources = [LAB / "sudoku_main.c", source("sudoku.c"), LAB / "board.c", source("backtrack.c")]
        return build_and_run(None, sources, [DATA / name])

    def test_boards_with_one_solution(self):
        for name, nodes in (("facil.txt", 69), ("medio.txt", 848), ("dificil.txt", 26019)):
            with self.subTest(board=name):
                out, code = self.solve(name)
                self.assertEqual(code, 0, out)
                puzzle = (DATA / name).read_text(encoding="utf-8").split()
                if not valid_solution(puzzle, board_lines(out)):
                    self.fail(f"{name}: la salida no es una solución válida de ese tablero.\n{out}")
                last = out.strip().splitlines()[-1]
                self.assertEqual(last, f"solución única, {nodes} nodos", f"{name}: se obtuvo {last}")

    def test_no_solution(self):
        out, code = self.solve("sin_solucion.txt")
        self.assertEqual(code, 0, out)
        self.assertEqual(out.strip(), "sin solución, 689 nodos")

    def test_inconsistent_board_is_not_searched(self):
        out, code = self.solve("repetido.txt")
        self.assertEqual(code, 0, out)
        self.assertEqual(out.strip(), "sin solución, 0 nodos")

    def test_limit_stops_the_search(self):
        body = """
        #include <stdio.h>
        #include "sudoku.h"
        int main(void) {
            Board empty = {0};
            Board solution;
            long nodes = 0;
            Board other;
            printf("%ld ", sudoku_search(&empty, 1, &solution, &nodes));
            printf("%ld ", sudoku_search(&empty, 3, &other, &nodes));
            int same = 1;
            for (int r = 0; r < BOARD_SIZE; r++) {
                for (int c = 0; c < BOARD_SIZE; c++) {
                    same = same && solution.cells[r][c] == other.cells[r][c];
                }
            }
            printf("%d\\n", same);
            return 0;
        }
        """
        sources = [source("sudoku.c"), LAB / "board.c", source("backtrack.c")]
        self.check(build_and_run(body, sources), "1 3 1", "sudoku_search debe detenerse al llegar a limit, y guardar la primera solución.")


class GivenFiles(LabCase):
    def test_reader_rejects_bad_files(self):
        body = r"""
        #include <stdio.h>
        #include "board.h"
        static void write_file(const char *text) {
            FILE *f = fopen("in.txt", "w");
            if (f == NULL) { return; }
            fputs(text, f);
            fclose(f);
        }
        int main(void) {
            const char *good = "123456789\n123456789\n123456789\n123456789\n123456789\n"
                               "123456789\n123456789\n123456789\n123456789\n";
            const char *short_file = "123456789\n";
            const char *bad_digit = "12345678x\n123456789\n123456789\n123456789\n123456789\n"
                                    "123456789\n123456789\n123456789\n123456789\n";
            const char *long_line = "1234567890\n123456789\n123456789\n123456789\n123456789\n"
                                    "123456789\n123456789\n123456789\n123456789\n";
            const char *extra = "123456789\n123456789\n123456789\n123456789\n123456789\n"
                                "123456789\n123456789\n123456789\n123456789\n1\n";
            Board b;
            write_file(good); printf("%d ", board_load("in.txt", &b));
            write_file(short_file); printf("%d ", board_load("in.txt", &b));
            write_file(bad_digit); printf("%d ", board_load("in.txt", &b));
            write_file(long_line); printf("%d ", board_load("in.txt", &b));
            write_file(extra); printf("%d ", board_load("in.txt", &b));
            printf("%d\n", board_load("no_existe.txt", &b));
            return 0;
        }
        """
        self.check(build_and_run(body, [LAB / "board.c"]), "1 0 0 0 0 0", "board_load debe rechazar lo mal formado.")


if __name__ == "__main__":
    unittest.main()