// Ordenamiento por selección que no sabe qué ordena, con la misma firma que qsort.
#include <stdio.h>
#include <string.h>

#define INT_COUNT 6
#define TRIP_COUNT 3

typedef int (*Compare)(const void *, const void *);

typedef struct {
    char route[12];
    int passengers;
} Trip;

void swap_bytes(unsigned char *a, unsigned char *b, size_t size) {
    for (size_t i = 0; i < size; i++) {
        unsigned char saved = a[i];
        a[i] = b[i];
        b[i] = saved;
    }
}

void any_sort(void *base, size_t count, size_t size, Compare compare) {
    unsigned char *bytes = base;
    for (size_t i = 0; i < count; i++) {
        size_t smallest = i;
        for (size_t j = i + 1; j < count; j++) {
            if (compare(bytes + j * size, bytes + smallest * size) < 0) {
                smallest = j;
            }
        }
        if (smallest != i) {
            swap_bytes(bytes + i * size, bytes + smallest * size, size);
        }
    }
}

int compare_ints(const void *first, const void *second) {
    int a = *(const int *) first;
    int b = *(const int *) second;
    return (a > b) - (a < b);
}

int compare_routes(const void *first, const void *second) {
    const Trip *a = first;
    const Trip *b = second;
    return strcmp(a->route, b->route);
}

int main(void) {
    int grades[INT_COUNT] = {14, 9, 20, 11, 9, 17};
    any_sort(grades, INT_COUNT, sizeof(grades[0]), compare_ints);
    for (int i = 0; i < INT_COUNT; i++) {
        printf("%d ", grades[i]);
    }
    printf("\n");

    Trip trips[TRIP_COUNT] = {{"Chosica", 18}, {"Ate", 9}, {"Callao", 25}};
    any_sort(trips, TRIP_COUNT, sizeof(trips[0]), compare_routes);
    for (int i = 0; i < TRIP_COUNT; i++) {
        printf("%s %d\n", trips[i].route, trips[i].passengers);
    }
    return 0;
}

// Una tabla de funciones: elegir la operación es buscar una fila.
#include <stdio.h>
#include <string.h>

typedef int (*BinaryOp)(int, int);

typedef struct {
    const char *name;
    BinaryOp run;
} Operation;

int add(int a, int b) {
    return a + b;
}

int subtract(int a, int b) {
    return a - b;
}

int multiply(int a, int b) {
    return a * b;
}

int larger(int a, int b) {
    return a > b ? a : b;
}

const Operation *find_operation(const Operation *table, int n, const char *name) {
    for (int i = 0; i < n; i++) {
        if (strcmp(table[i].name, name) == 0) {
            return &table[i];
        }
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    const Operation table[] = {
        {"suma", add},
        {"resta", subtract},
        {"producto", multiply},
        {"mayor", larger},
    };
    int rows = sizeof(table) / sizeof(table[0]);
    int a = 12;
    int b = 5;

    if (argc != 2) {
        printf("uso: %s operación\n", argv[0]);
        return 1;
    }
    const Operation *chosen = find_operation(table, rows, argv[1]);
    if (chosen == NULL) {
        printf("no conozco la operación %s\n", argv[1]);
        return 1;
    }
    printf("%s de %d y %d: %d\n", chosen->name, a, b, chosen->run(a, b));
    return 0;
}

// Un callback que recibe, además del dato, un contexto void *.
#include <stdio.h>

#define COUNT 6

typedef void (*Visitor)(int value, void *context);

void for_each(const int *values, int n, Visitor visit, void *context) {
    for (int i = 0; i < n; i++) {
        visit(values[i], context);
    }
}

typedef struct {
    int limit;
    int sum;
    int taken;
} SumAbove;

void add_if_above(int value, void *context) {
    SumAbove *state = context;
    if (value > state->limit) {
        state->sum += value;
        state->taken++;
    }
}

void print_labeled(int value, void *context) {
    const char *label = context;
    printf("%s %d\n", label, value);
}

int main(void) {
    int grades[COUNT] = {14, 9, 20, 11, 17, 13};

    SumAbove strict = {15, 0, 0};
    for_each(grades, COUNT, add_if_above, &strict);
    printf("mayores que %d: %d, suman %d\n", strict.limit, strict.taken, strict.sum);

    SumAbove easy = {10, 0, 0};
    for_each(grades, COUNT, add_if_above, &easy);
    printf("mayores que %d: %d, suman %d\n", easy.limit, easy.taken, easy.sum);

    for_each(grades, 2, print_labeled, "nota:");
    return 0;
}

// Una función tiene dirección, y esa dirección se guarda en una variable.
#include <stdio.h>

int add(int a, int b) {
    return a + b;
}

int multiply(int a, int b) {
    return a * b;
}

// Otro nombre para el tipo "puntero a función que recibe dos int y devuelve un int".
typedef int (*BinaryOp)(int, int);

int apply(BinaryOp op, int a, int b) {
    return op(a, b);
}

int main(void) {
    int (*op)(int, int) = add;
    printf("op(2, 3) = %d\n", op(2, 3));

    op = multiply;
    printf("op(2, 3) = %d\n", op(2, 3));
    printf("(*op)(2, 3) = %d\n", (*op)(2, 3));
    printf("op == multiply: %d\n", op == multiply);

    BinaryOp chosen = add;
    printf("apply(chosen, 2, 3) = %d\n", apply(chosen, 2, 3));
    printf("apply(multiply, 2, 3) = %d\n", apply(multiply, 2, 3));
    return 0;
}

// La búsqueda genera; un callback decide qué se hace con cada resultado.
#include <stdio.h>

#define SHOWN 3
#define COUNTED 5

typedef void (*OnPermutation)(const int *items, int n, void *context);

void swap(int *a, int *b) {
    int saved = *a;
    *a = *b;
    *b = saved;
}

void explore(int *items, int n, int position, OnPermutation visit, void *context) {
    if (position == n) {
        visit(items, n, context);
        return;
    }
    for (int i = position; i < n; i++) {
        swap(&items[position], &items[i]);
        explore(items, n, position + 1, visit, context);
        swap(&items[position], &items[i]);
    }
}

void print_permutation(const int *items, int n, void *context) {
    (void) context;
    for (int i = 0; i < n; i++) {
        printf("%d ", items[i]);
    }
    printf("\n");
}

typedef struct {
    int total;
    int first_is_smaller;
} Tally;

void count_permutation(const int *items, int n, void *context) {
    Tally *tally = context;
    tally->total++;
    if (items[0] < items[n - 1]) {
        tally->first_is_smaller++;
    }
}

int main(void) {
    int few[SHOWN] = {1, 2, 3};
    explore(few, SHOWN, 0, print_permutation, NULL);

    int more[COUNTED] = {1, 2, 3, 4, 5};
    Tally tally = {0, 0};
    explore(more, COUNTED, 0, count_permutation, &tally);
    printf("%d permutaciones, en %d el primero es menor que el último\n",
           tally.total, tally.first_is_smaller);
    return 0;
}

// El ciclo se escribe una vez. Lo que cambia entra como parámetro.
#include <stdio.h>

#define COUNT 4

typedef double (*PriceChange)(double);
typedef double (*PriceFold)(double, double);

double add_tax(double price) {
    return price * 1.18;
}

double half_price(double price) {
    return price / 2.0;
}

void change_all(double *prices, int n, PriceChange change) {
    for (int i = 0; i < n; i++) {
        prices[i] = change(prices[i]);
    }
}

double fold_prices(const double *prices, int n, PriceFold combine, double initial) {
    double result = initial;
    for (int i = 0; i < n; i++) {
        result = combine(result, prices[i]);
    }
    return result;
}

double add_prices(double total, double price) {
    return total + price;
}

double larger_price(double best, double price) {
    return price > best ? price : best;
}

void print_prices(const double *prices, int n) {
    for (int i = 0; i < n; i++) {
        printf("%.2f ", prices[i]);
    }
    printf("\n");
}

int main(void) {
    double prices[COUNT] = {10.0, 25.0, 4.5, 100.0};
    printf("total: %.2f\n", fold_prices(prices, COUNT, add_prices, 0.0));
    printf("mayor: %.2f\n", fold_prices(prices, COUNT, larger_price, prices[0]));
    change_all(prices, COUNT, add_tax);
    print_prices(prices, COUNT);
    change_all(prices, COUNT, half_price);
    print_prices(prices, COUNT);
    return 0;
}

// Dos funciones que repiten el mismo ciclo y solo cambian en una línea.
#include <stdio.h>

#define COUNT 4

void add_tax_all(double *prices, int n) {
    for (int i = 0; i < n; i++) {
        prices[i] = prices[i] * 1.18;
    }
}

void half_price_all(double *prices, int n) {
    for (int i = 0; i < n; i++) {
        prices[i] = prices[i] / 2.0;
    }
}

void print_prices(const double *prices, int n) {
    for (int i = 0; i < n; i++) {
        printf("%.2f ", prices[i]);
    }
    printf("\n");
}

int main(void) {
    double prices[COUNT] = {10.0, 25.0, 4.5, 100.0};
    add_tax_all(prices, COUNT);
    print_prices(prices, COUNT);
    half_price_all(prices, COUNT);
    print_prices(prices, COUNT);
    return 0;
}

// bsearch de la biblioteca, y una versión propia con la misma firma.
#include <stdio.h>
#include <stdlib.h>

#define COUNT 5

typedef int (*Compare)(const void *, const void *);

typedef struct {
    int code;
    int grade;
} Student;

// El primer parámetro es la clave, y el segundo un elemento del arreglo.
int compare_code_with_student(const void *key, const void *element) {
    int code = *(const int *) key;
    const Student *student = element;
    return (code > student->code) - (code < student->code);
}

void *any_search(const void *key, const void *base, size_t count, size_t size, Compare compare) {
    const unsigned char *bytes = base;
    size_t low = 0;
    size_t high = count;
    while (low < high) {
        size_t middle = low + (high - low) / 2;
        const unsigned char *element = bytes + middle * size;
        int order = compare(key, element);
        if (order == 0) {
            return (void *) element;
        }
        if (order < 0) {
            high = middle;
        } else {
            low = middle + 1;
        }
    }
    return NULL;
}

void report(const Student *found, int code) {
    if (found == NULL) {
        printf("%d: no está\n", code);
    } else {
        printf("%d: nota %d\n", code, found->grade);
    }
}

int main(void) {
    // Ordenado por código: bsearch lo exige.
    Student students[COUNT] = {{1040, 14}, {1187, 17}, {1203, 9}, {1311, 12}, {1450, 20}};
    int wanted[2] = {1311, 1312};

    for (int i = 0; i < 2; i++) {
        const Student *from_library =
            bsearch(&wanted[i], students, COUNT, sizeof(students[0]), compare_code_with_student);
        const Student *from_ours =
            any_search(&wanted[i], students, COUNT, sizeof(students[0]), compare_code_with_student);
        report(from_library, wanted[i]);
        report(from_ours, wanted[i]);
    }
    return 0;
}

// Un arreglo de cadenas: cada elemento es un puntero, y qsort pasa su dirección.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define COUNT 4

int compare_names(const void *first, const void *second) {
    const char *const *a = first;
    const char *const *b = second;
    return strcmp(*a, *b);
}

int main(void) {
    const char *names[COUNT] = {"Rosa", "Abel", "Nadia", "Luis"};
    qsort(names, COUNT, sizeof(names[0]), compare_names);
    for (int i = 0; i < COUNT; i++) {
        printf("%s\n", names[i]);
    }
    return 0;
}

// Un mismo arreglo, ordenado con qsort por tres criterios.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define COUNT 5

typedef struct {
    char name[20];
    int grade;
} Student;

int compare_by_name(const void *first, const void *second) {
    const Student *a = first;
    const Student *b = second;
    return strcmp(a->name, b->name);
}

int compare_by_grade_desc(const void *first, const void *second) {
    const Student *a = first;
    const Student *b = second;
    if (a->grade > b->grade) {
        return -1;
    }
    if (a->grade < b->grade) {
        return 1;
    }
    return 0;
}

int compare_by_grade_then_name(const void *first, const void *second) {
    int by_grade = compare_by_grade_desc(first, second);
    if (by_grade != 0) {
        return by_grade;
    }
    return compare_by_name(first, second);
}

void print_students(const char *title, const Student *students, int n) {
    printf("%s:\n", title);
    for (int i = 0; i < n; i++) {
        printf("  %-8s %2d\n", students[i].name, students[i].grade);
    }
}

int main(void) {
    Student students[COUNT] = {
        {"Rosa", 14}, {"Abel", 17}, {"Nadia", 14}, {"Luis", 9}, {"Carmen", 17},
    };

    qsort(students, COUNT, sizeof(students[0]), compare_by_name);
    print_students("por nombre", students, COUNT);

    qsort(students, COUNT, sizeof(students[0]), compare_by_grade_then_name);
    print_students("por nota y luego nombre", students, COUNT);
    return 0;
}

// Error: al restar decimales, el resultado se convierte a int y se pierde la parte decimal.
#include <stdio.h>
#include <stdlib.h>

#define COUNT 4

int compare_fares(const void *first, const void *second) {
    double a = *(const double *) first;
    double b = *(const double *) second;
    return a - b;
}

int main(void) {
    double fares[COUNT] = {2.9, 2.1, 2.5, 1.8};
    qsort(fares, COUNT, sizeof(fares[0]), compare_fares);
    for (int i = 0; i < COUNT; i++) {
        printf("%.1f ", fares[i]);
    }
    printf("\n");
    return 0;
}

// Error: sin paréntesis, esto declara una función, no un puntero a función.
#include <stdio.h>

int add(int a, int b) {
    return a + b;
}

int main(void) {
    int *op(int, int) = add;
    printf("%d\n", op(2, 3));
    return 0;
}

// Una función dentro de otra no es C: es una extensión de gcc.
#include <stdio.h>

int count_above(const int *values, int n, int limit) {
    int above(int value) {
        return value > limit;
    }
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += above(values[i]);
    }
    return total;
}

int main(void) {
    int grades[3] = {14, 9, 20};
    printf("%d\n", count_above(grades, 3, 10));
    return 0;
}

// Error: un comparador que resta. La resta puede no caber en un int.
#include <limits.h>
#include <stdio.h>

int compare_by_subtracting(const void *first, const void *second) {
    int a = *(const int *) first;
    int b = *(const int *) second;
    return a - b;
}

int compare_safely(const void *first, const void *second) {
    int a = *(const int *) first;
    int b = *(const int *) second;
    return (a > b) - (a < b);
}

int main(void) {
    int low = INT_MIN;
    int one = 1;
    printf("con resta: %d\n", compare_by_subtracting(&low, &one));
    printf("sin resta: %d\n", compare_safely(&low, &one));
    return 0;
}

// Error: qsort con un comparador que resta, sobre datos que hacen overflow.
#include <stdio.h>
#include <stdlib.h>

#define COUNT 5

int compare_by_subtracting(const void *first, const void *second) {
    int a = *(const int *) first;
    int b = *(const int *) second;
    return a - b;
}

int main(void) {
    int values[COUNT] = {2000000000, -2000000000, 5, 1500000000, -1500000000};
    qsort(values, COUNT, sizeof(values[0]), compare_by_subtracting);
    for (int i = 0; i < COUNT; i++) {
        printf("%d\n", values[i]);
    }
    return 0;
}

// Error: se agregó una etiqueta al enum y la tabla no se actualizó.
#include <stdio.h>

typedef int (*BinaryOp)(int, int);

enum op_kind { OP_ADD, OP_SUBTRACT, OP_LARGER, OP_COUNT };

int add(int a, int b) {
    return a + b;
}

int subtract(int a, int b) {
    return a - b;
}

int main(void) {
    const BinaryOp table[OP_COUNT] = {add, subtract};
    for (int kind = 0; kind < OP_COUNT; kind++) {
        printf("operación %d: %d\n", kind, table[kind](12, 5));
    }
    return 0;
}

// Error: el cast calla al compilador, pero el comparador sigue sin tener la forma pedida.
#include <stdio.h>
#include <stdlib.h>

typedef int (*Compare)(const void *, const void *);

int compare_ints(const int *a, const int *b) {
    return (*a > *b) - (*a < *b);
}

int main(void) {
    int grades[3] = {14, 9, 20};
    qsort(grades, 3, sizeof(grades[0]), (Compare) compare_ints);
    printf("%d %d %d\n", grades[0], grades[1], grades[2]);
    return 0;
}

// Error: un comparador con parámetros int * no es lo que qsort pide.
#include <stdio.h>
#include <stdlib.h>

int compare_ints(const int *a, const int *b) {
    return (*a > *b) - (*a < *b);
}

int main(void) {
    int grades[3] = {14, 9, 20};
    qsort(grades, 3, sizeof(grades[0]), compare_ints);
    printf("%d\n", grades[0]);
    return 0;
}

// gcc acepta aritmética con void *, pero C no la define.
#include <stdio.h>

int main(void) {
    int grades[3] = {14, 9, 20};
    void *base = grades;
    void *next = base + sizeof(grades[0]);
    printf("%d\n", *(int *) next);
    return 0;
}

// Error: un contexto de otro tipo, del mismo tamaño o mayor. Nadie lo detecta.
#include <stdio.h>

#define COUNT 3

typedef void (*Visitor)(int value, void *context);

void print_if_above(int value, void *context) {
    int *limit = context;
    if (value > *limit) {
        printf("%d pasa\n", value);
    }
}

void for_each(const int *values, int n, Visitor visit, void *context) {
    for (int i = 0; i < n; i++) {
        visit(values[i], context);
    }
}

int main(void) {
    int grades[COUNT] = {14, 9, 20};
    double limit = 15.0;
    for_each(grades, COUNT, print_if_above, &limit);
    printf("fin\n");
    return 0;
}

// Error: el contexto no es del tipo que el callback supone.
#include <stdio.h>

#define COUNT 3

typedef void (*Visitor)(int value, void *context);

typedef struct {
    int limit;
    int sum;
    int taken;
} SumAbove;

void add_if_above(int value, void *context) {
    SumAbove *state = context;
    if (value > state->limit) {
        state->sum += value;
        state->taken++;
    }
}

void for_each(const int *values, int n, Visitor visit, void *context) {
    for (int i = 0; i < n; i++) {
        visit(values[i], context);
    }
}

int main(void) {
    int grades[COUNT] = {14, 9, 20};
    int limit = 10;
    for_each(grades, COUNT, add_if_above, &limit);
    printf("limit = %d\n", limit);
    return 0;
}

// Error: cada elemento es un char *, y el comparador recibe la dirección de ese puntero.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define COUNT 4

int compare_names(const void *first, const void *second) {
    return strcmp(first, second);
}

int main(void) {
    const char *names[COUNT] = {"Rosa", "Abel", "Nadia", "Luis"};
    qsort(names, COUNT, sizeof(names[0]), compare_names);
    for (int i = 0; i < COUNT; i++) {
        printf("%s\n", names[i]);
    }
    return 0;
}

// Error: la función no tiene la forma que pide el puntero.
#include <stdio.h>

typedef int (*BinaryOp)(int, int);

int negate(int a) {
    return -a;
}

int main(void) {
    BinaryOp op = negate;
    printf("%d\n", op(2, 3));
    return 0;
}

"""Comprueba los programas de la clase y lo que los apuntes dicen de las herramientas."""
import pathlib
import subprocess
import tempfile
import unittest

HERE = pathlib.Path(__file__).parent
BUILD = HERE / "build"
BASE = ["-Wall", "-Wextra", "-std=c17"]
FLAGS = [*BASE, "-g", "-fsanitize=address,undefined"]
PLAIN = ["function_pointer", "repeated_loops", "prices", "sort_students", "sort_names", "any_sort",
         "search_students", "for_each", "calculator", "permutations"]


def run(program, *args):
    done = subprocess.run(
        [str(program), *args], cwd=HERE, text=True, encoding="utf-8", errors="replace",
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=30,
    )
    return done.stdout, done.returncode


def build(source, flags):
    """Compila y devuelve (ruta del ejecutable, carpeta temporal, mensajes de gcc, código)."""
    folder = tempfile.TemporaryDirectory()
    binary = pathlib.Path(folder.name) / "program"
    done = subprocess.run(
        ["gcc", *flags, source, "-o", str(binary)], cwd=HERE, text=True,
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
    )
    return binary, folder, done.stdout, done.returncode


class Programs(unittest.TestCase):
    def test_every_program_compiles_without_warnings(self):
        for name in PLAIN:
            with self.subTest(program=name):
                subprocess.run(
                    ["gcc", *FLAGS, "-Werror", "-c", f"{name}.c", "-o", "/dev/null"],
                    cwd=HERE, check=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
                )

    def test_every_program_ends_without_reports(self):
        for name in PLAIN:
            args = ["suma"] if name == "calculator" else []
            with self.subTest(program=name):
                out, code = run(BUILD / name, *args)
                self.assertEqual(code, 0, out)
                self.assertNotIn("runtime error", out)

    def test_loops_and_callback_agree(self):
        repeated = run(BUILD / "repeated_loops")[0].splitlines()
        with_callback = run(BUILD / "prices")[0].splitlines()
        self.assertEqual(repeated, with_callback[2:])

    def test_our_search_agrees_with_bsearch(self):
        lines = run(BUILD / "search_students")[0].splitlines()
        self.assertEqual(lines[0], lines[1])
        self.assertEqual(lines[2], lines[3])

    def test_table_rejects_unknown_operation(self):
        out, code = run(BUILD / "calculator", "potencia")
        self.assertEqual(code, 1)
        self.assertIn("no conozco", out)


class CompilerClaims(unittest.TestCase):
    def messages(self, source, flags=BASE):
        _, folder, text, code = build(source, flags)
        folder.cleanup()
        return text, code

    def test_these_do_not_compile(self):
        for source, phrase in (("errors/missing_parens.c", "initialized like a variable"),
                               ("errors/wrong_signature.c", "incompatible pointer type"),
                               ("errors/typed_compare.c", "incompatible pointer type")):
            with self.subTest(source=source):
                text, code = self.messages(source)
                self.assertNotEqual(code, 0)
                self.assertIn(phrase, text)

    def test_these_errors_give_no_warning(self):
        for source in ("errors/void_arithmetic.c", "errors/subtract_compare.c", "errors/subtract_sort.c",
                       "errors/double_compare.c", "errors/wrong_level.c", "errors/wrong_context.c",
                       "errors/wrong_context_silent.c", "errors/nested_function.c", "errors/table_gap.c",
                       "errors/typed_compare_cast.c"):
            with self.subTest(source=source):
                self.assertEqual(self.messages(source)[0], "")

    def test_extra_flags_show_the_extensions(self):
        self.assertIn("-Wpointer-arith", self.messages("errors/void_arithmetic.c", [*BASE, "-Wpointer-arith"])[0])
        self.assertIn("ISO C forbids nested functions", self.messages("errors/nested_function.c", [*BASE, "-pedantic"])[0])


class RunClaims(unittest.TestCase):
    def output(self, source):
        binary, folder, _, _ = build(source, FLAGS)
        out, code = run(binary)
        folder.cleanup()
        return out, code

    def test_subtracting_gets_the_sign_wrong(self):
        out, _ = self.output("errors/subtract_compare.c")
        self.assertIn("signed integer overflow", out)
        self.assertIn("sin resta: -1", out)

    def test_sort_by_subtracting_overflows(self):
        self.assertIn("signed integer overflow", self.output("errors/subtract_sort.c")[0])

    def test_double_compare_does_not_sort(self):
        out, code = self.output("errors/double_compare.c")
        self.assertEqual(code, 0, out)
        values = [float(x) for x in out.split()]
        self.assertNotEqual(values, sorted(values))
        self.assertNotIn("runtime error", out)

    def test_wrong_level_is_silent_and_wrong(self):
        out, code = self.output("errors/wrong_level.c")
        self.assertEqual(code, 0, out)
        self.assertNotIn("runtime error", out)

    def test_wrong_context_is_caught_when_it_goes_outside(self):
        out, code = self.output("errors/wrong_context.c")
        self.assertNotEqual(code, 0)
        self.assertIn("stack-buffer-overflow", out)
        self.assertIn("add_if_above", out)

    def test_wrong_context_can_be_silent(self):
        out, code = self.output("errors/wrong_context_silent.c")
        self.assertEqual(code, 0, out)
        self.assertNotIn("runtime error", out)
        self.assertNotIn("AddressSanitizer", out)
        self.assertIn("fin", out)

    def test_table_gap_jumps_to_address_zero(self):
        out, code = self.output("errors/table_gap.c")
        self.assertNotEqual(code, 0)
        self.assertIn("SEGV", out)

    def test_gdb_knows_the_type_of_a_function(self):
        with tempfile.TemporaryDirectory() as name:
            binary = pathlib.Path(name) / "program"
            subprocess.run(["gcc", *BASE, "-g", "-O0", "function_pointer.c", "-o", str(binary)], cwd=HERE, check=True)
            done = subprocess.run(
                ["gdb", "-q", "-batch", "-ex", "print add", "-ex", "whatis add", str(binary)],
                text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
            )
        self.assertIn("{int (int, int)}", done.stdout)
        self.assertIn("<add>", done.stdout)


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

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