// Recursión sobre arreglos y cadenas, sin ciclos y sin copiar nada.
#include <stdio.h>

// Cuántos negativos hay en los n elementos que empiezan en a.
static size_t count_negative(const int *a, size_t n) {
    if (n == 0) {
        return 0;
    }
    size_t rest = count_negative(a + 1, n - 1);
    if (a[0] < 0) {
        return rest + 1;
    }
    return rest;
}

// El menor de n elementos. Requiere n >= 1: un arreglo vacío no tiene mínimo.
static int array_min(const int *a, size_t n) {
    if (n == 1) {
        return a[0];
    }
    int rest = array_min(a + 1, n - 1);
    if (a[0] < rest) {
        return a[0];
    }
    return rest;
}

// ¿El arreglo se lee igual desde los dos extremos?
static int is_symmetric(const int *a, size_t n) {
    if (n <= 1) {
        return 1;
    }
    if (a[0] != a[n - 1]) {
        return 0;
    }
    return is_symmetric(a + 1, n - 2);
}

// Cuántos caracteres hay antes del '\0'.
static size_t string_length(const char *s) {
    if (s[0] == '\0') {
        return 0;
    }
    return 1 + string_length(s + 1);
}

int main(void) {
    int data[] = {4, -2, 7, -9, 1};
    int mirror[] = {3, 8, 8, 3};
    size_t data_n = sizeof data / sizeof data[0];
    size_t mirror_n = sizeof mirror / sizeof mirror[0];

    printf("negativos: %zu\n", count_negative(data, data_n));
    printf("mínimo: %d\n", array_min(data, data_n));
    printf("data simétrico: %d\n", is_symmetric(data, data_n));
    printf("mirror simétrico: %d\n", is_symmetric(mirror, mirror_n));
    printf("largo de \"Chosica\": %zu\n", string_length("Chosica"));
    printf("largo de \"\": %zu\n", string_length(""));
    return 0;
}

// El mismo cálculo con recursión y con un ciclo.
#include <stdio.h>

// Algoritmo de Euclides: la llamada recursiva es lo último que se hace.
static int gcd_recursive(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd_recursive(b, a % b);
}

static int gcd_loop(int a, int b) {
    while (b != 0) {
        int next_b = a % b;
        a = b;
        b = next_b;
    }
    return a;
}

// Aquí queda trabajo pendiente después de la llamada: la suma.
static long long sum_recursive(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum_recursive(n - 1);
}

// La misma suma con un acumulador: lo pendiente se hace antes de llamar.
static long long sum_accumulator(int n, long long total) {
    if (n <= 0) {
        return total;
    }
    return sum_accumulator(n - 1, total + n);
}

static long long sum_loop(int n) {
    long long total = 0;
    while (n > 0) {
        total = total + n;
        n = n - 1;
    }
    return total;
}

int main(void) {
    printf("mcd(252, 105): %d y %d\n", gcd_recursive(252, 105), gcd_loop(252, 105));
    printf("suma hasta 100: %lld, %lld y %lld\n", sum_recursive(100),
           sum_accumulator(100, 0), sum_loop(100));
    return 0;
}

// ¿Hasta dónde llega la recursión? Uso: deep_sum recursive N, o deep_sum loop N
#include <stdio.h>
#include <string.h>

static long long sum_recursive(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum_recursive(n - 1);
}

static long long sum_loop(int n) {
    long long total = 0;
    for (int i = 1; i <= n; i++) {
        total = total + i;
    }
    return total;
}

int main(int argc, char *argv[]) {
    int n;
    char extra;
    if (argc != 3 || sscanf(argv[2], "%d %c", &n, &extra) != 1) {
        fprintf(stderr, "uso: %s recursive|loop N\n", argv[0]);
        return 1;
    }
    if (strcmp(argv[1], "recursive") == 0) {
        printf("%lld\n", sum_recursive(n));
    } else if (strcmp(argv[1], "loop") == 0) {
        printf("%lld\n", sum_loop(n));
    } else {
        fprintf(stderr, "uso: %s recursive|loop N\n", argv[0]);
        return 1;
    }
    return 0;
}

// Lo que se hace antes de la llamada ocurre al bajar; lo de después, al volver.
#include <stdio.h>

// Escribe la última cifra primero. Requiere n >= 0.
static void print_backward(int n) {
    printf("%d", n % 10);
    if (n >= 10) {
        print_backward(n / 10);
    }
}

// Escribe las cifras en orden. Requiere n >= 0.
static void print_forward(int n) {
    if (n >= 10) {
        print_forward(n / 10);
    }
    printf("%d", n % 10);
}

int main(void) {
    print_backward(2026);
    printf("\n");
    print_forward(2026);
    printf("\n");
    return 0;
}

// El factorial con un rastro: cada nivel de la recursión escribe con más sangría.
#include <stdio.h>

static void indent(int depth) {
    for (int i = 0; i < depth; i++) {
        printf("  ");
    }
}

// depth solo sirve para la sangría: no interviene en la cuenta.
static long long factorial(int n, int depth) {
    indent(depth);
    printf("entra factorial(%d)\n", n);
    if (n <= 1) {
        indent(depth);
        printf("caso base: devuelve 1\n");
        return 1;
    }
    long long rest = factorial(n - 1, depth + 1);
    long long result = n * rest;
    indent(depth);
    printf("%d * %lld = %lld\n", n, rest, result);
    return result;
}

int main(void) {
    printf("resultado: %lld\n", factorial(4, 0));
    return 0;
}

// El factorial, sin rastro: para mirar sus marcos en gdb.
#include <stdio.h>

long long factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    long long rest = factorial(n - 1);
    return n * rest;
}

int main(void) {
    printf("factorial(4) = %lld\n", factorial(4));
    return 0;
}

// Cada llamada tiene su propia n: se ve en las direcciones. Cambian de una máquina a otra.
#include <stdio.h>

static int count_down(int n) {
    printf("n = %d está en %p\n", n, (void *) &n);
    if (n == 0) {
        return 0;
    }
    int levels = count_down(n - 1);
    printf("al volver, n sigue siendo %d\n", n);
    return levels + 1;
}

int main(void) {
    printf("niveles: %d\n", count_down(3));
    return 0;
}

// Error a propósito: compila, no se cae y da una respuesta equivocada.
#include <stdio.h>

static int array_min(const int *a, size_t n) {
    if (n == 0) {
        return 0;
    }
    int rest = array_min(a + 1, n - 1);
    if (a[0] < rest) {
        return a[0];
    }
    return rest;
}

int main(void) {
    int one[] = {5};
    int many[] = {4, 2, 7};
    int negative[] = {4, -2, 7};

    printf("{5}: %d\n", array_min(one, 1));
    printf("{4, 2, 7}: %d\n", array_min(many, 3));
    printf("{4, -2, 7}: %d\n", array_min(negative, 3));
    return 0;
}

// Error a propósito: no hay caso base, así que las llamadas no terminan.
#include <stdio.h>

static long long sum_down(int n) {
    return n + sum_down(n - 1);
}

int main(void) {
    printf("%lld\n", sum_down(5));
    return 0;
}

// Error a propósito: 2 elevado a 1024 no cabe en un long long.
#include <stdio.h>

static long long power_slow(long long base, int n) {
    if (n == 0) {
        return 1;
    }
    return base * power_slow(base, n - 1);
}

int main(void) {
    printf("2^62 = %lld\n", power_slow(2, 62));
    printf("2^1024 = %lld\n", power_slow(2, 1024));
    return 0;
}

// Error a propósito: da bien el resultado, pero calcula dos veces la mitad.
#include <stdio.h>

static long long power_twice(long long base, int n, long *calls) {
    *calls = *calls + 1;
    if (n == 0) {
        return 1;
    }
    long long result = power_twice(base, n / 2, calls) * power_twice(base, n / 2, calls);
    if (n % 2 == 1) {
        result = result * base;
    }
    return result;
}

int main(void) {
    // Con base 1 el resultado siempre cabe, y el número de llamadas no depende de la base.
    int sizes[] = {10, 100, 1024};
    for (int i = 0; i < 3; i++) {
        long calls = 0;
        long long result = power_twice(1, sizes[i], &calls);
        printf("power_twice(1, %d) = %lld, llamadas: %ld\n", sizes[i], result, calls);
    }
    return 0;
}

// Error a propósito: hay caso base, pero con 7 nunca se llega a él. gcc no avisa.
#include <stdio.h>

static int half_steps(int n) {
    if (n == 0) {
        return 0;
    }
    return 1 + half_steps(n - 2);
}

int main(void) {
    printf("con 6: %d\n", half_steps(6));
    printf("con 7: %d\n", half_steps(7));
    return 0;
}

"""Comprueba los programas de la clase y lo que los apuntes dicen de ellos."""
import pathlib
import re
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 = ["factorial", "factorial_trace", "frame_addresses", "array_examples", "convert", "digits", "deep_sum"]


def run(command, timeout=60):
    done = subprocess.run(
        command, cwd=HERE, text=True, encoding="utf-8", errors="replace",
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=timeout,
    )
    return done.stdout, done.returncode


class Compiled:
    """Un programa compilado aparte, con sus opciones, en una carpeta temporal."""

    def __init__(self, source, flags):
        self.folder = tempfile.TemporaryDirectory()
        self.binary = str(pathlib.Path(self.folder.name) / "program")
        self.messages, self.code = run(["gcc", *flags, source, "-o", self.binary])

    def __enter__(self):
        return self

    def __exit__(self, *_):
        self.folder.cleanup()


class Programs(unittest.TestCase):
    def test_programs_compile_without_warnings(self):
        for name in PLAIN:
            with self.subTest(program=name):
                with Compiled(f"{name}.c", [*FLAGS, "-Werror"]) as program:
                    self.assertEqual(program.code, 0, program.messages)

    def test_examples_end_without_reports(self):
        for name in ["factorial", "factorial_trace", "array_examples", "convert", "digits"]:
            with self.subTest(program=name):
                out, code = run([str(BUILD / name)])
                self.assertEqual(code, 0, out)
                self.assertNotIn("runtime error", out)

    def test_each_call_has_its_own_n(self):
        with Compiled("frame_addresses.c", [*BASE, "-g", "-O0"]) as program:
            out, _ = run([program.binary])
        addresses = re.findall(r"está en (0x[0-9a-f]+)", out)
        self.assertEqual(len(set(addresses)), 4)
        values = [int(a, 16) for a in addresses]
        self.assertEqual(values, sorted(values, reverse=True), "la pila debería crecer hacia abajo")
        self.assertIn("al volver, n sigue siendo 3", out)


class StackLimit(unittest.TestCase):
    def report(self, binary, *args):
        # En x86_64 emulado, a veces el proceso muere sin dejar el informe: se reintenta.
        out = ""
        for _ in range(5):
            out, code = run([binary, *args])
            self.assertNotEqual(code, 0)
            if "stack-overflow" in out:
                return out
        return out

    def test_gcc_warns_without_a_base_case(self):
        with Compiled("errors/no_base_case.c", BASE) as program:
            self.assertIn("-Winfinite-recursion", program.messages)

    def test_gcc_does_not_warn_about_an_unreached_base_case(self):
        with Compiled("errors/skipped_base.c", BASE) as program:
            self.assertEqual(program.messages, "")

    def test_asan_names_the_overflow(self):
        for source in ["errors/no_base_case.c", "errors/skipped_base.c"]:
            with self.subTest(source=source):
                with Compiled(source, [*FLAGS, "-Wno-infinite-recursion"]) as program:
                    out = self.report(program.binary)
                self.assertIn("AddressSanitizer: stack-overflow", out)

    def test_a_correct_base_case_does_not_save_a_deep_recursion(self):
        with Compiled("deep_sum.c", [*BASE, "-g", "-O0"]) as program:
            self.assertEqual(run([program.binary, "recursive", "1000"])[0].strip(), "500500")
            self.assertNotEqual(run([program.binary, "recursive", "10000000"])[1], 0)
            self.assertEqual(run([program.binary, "loop", "10000000"])[0].strip(), "50000005000000")

    def test_o2_can_remove_the_recursion(self):
        # No es una garantía del lenguaje: es lo que hace este gcc, y lo que dicen los apuntes.
        with Compiled("deep_sum.c", [*BASE, "-O2"]) as program:
            self.assertEqual(run([program.binary, "recursive", "10000000"])[0].strip(), "50000005000000")

    def test_o2_turns_a_missing_base_case_into_a_hang(self):
        with Compiled("errors/no_base_case.c", [*BASE, "-O2", "-Wno-infinite-recursion"]) as program:
            done, code = run(["timeout", "2", program.binary])
        self.assertEqual(code, 124, done)


class WrongButQuiet(unittest.TestCase):
    def test_zero_base_case_breaks_only_some_inputs(self):
        with Compiled("errors/min_base_zero.c", FLAGS) as program:
            out, code = run([program.binary])
        self.assertEqual(code, 0)
        self.assertEqual(out.split("\n")[:3], ["{5}: 0", "{4, 2, 7}: 0", "{4, -2, 7}: -2"])

    def test_power_of_1024_does_not_fit(self):
        with Compiled("errors/power_too_big.c", FLAGS) as program:
            out, _ = run([program.binary])
        self.assertIn("signed integer overflow: 2 * 4611686018427387904", out)
        self.assertIn("2^62 = 4611686018427387904", out)

    def test_two_calls_cost_more_than_the_slow_version(self):
        with Compiled("errors/power_twice.c", BASE) as program:
            out, _ = run([program.binary])
        self.assertIn("power_twice(1, 1024) = 1, llamadas: 4095", out)


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 su código, aparte de sus pruebas. Corren con ASan,
así que una fuga también hace 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
FLAGS = ["-Wall", "-Wextra", "-std=c17", "-g", "-fsanitize=address,undefined"]
INCLUDE = f"-I{HERE / 'lab'}"
HEADERS = '#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n'


def compile_command(args):
    done = subprocess.run(["gcc", *FLAGS, INCLUDE, *map(str, args)], text=True,
                          stdout=subprocess.PIPE, stderr=subprocess.STDOUT)
    if done.returncode != 0:
        raise AssertionError(f"No compila:\n{done.stdout}")


def run_binary(binary, args=()):
    try:
        done = subprocess.run([str(binary), *args], text=True, encoding="utf-8", errors="replace",
                              stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=30)
    except subprocess.TimeoutExpired:
        raise AssertionError("El programa no terminó en 30 segundos.") from None
    return done.stdout, done.returncode


def build_and_run(body, header, source):
    with tempfile.TemporaryDirectory() as name:
        driver = pathlib.Path(name) / "driver.c"
        driver.write_text(f'{HEADERS}#include "{header}"\nint main(void) {{\n{body}\nreturn 0;\n}}\n',
                          encoding="utf-8")
        binary = pathlib.Path(name) / "driver"
        compile_command([driver, SOURCE / source, "-o", binary])
        return run_binary(binary)


def without_comments_and_text(path):
    text = path.read_text(encoding="utf-8")
    text = re.sub(r"/\*.*?\*/", " ", text, flags=re.S)
    text = re.sub(r"//[^\n]*", " ", text)
    text = re.sub(r'"(\\.|[^"\\])*"', '""', text)
    return re.sub(r"'(\\.|[^'\\])*'", "' '", text)


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:
            self.fail(f"{what}\n  se esperaba: {wanted}\n  se obtuvo:   {out.strip()}")

    def assert_no_loops(self, path):
        code = without_comments_and_text(path)
        for word in ("for", "while", "goto"):
            if re.search(rf"\b{word}\b", code):
                self.fail(f"{path.name} no puede usar {word}: aquí todo se resuelve con recursión.")


@unittest.skipUnless((SOURCE / "recursion.c").exists(), f"no está {LAB_DIR}/recursion.c")
class SessionOne(LabCase):
    def recursion(self, body):
        return build_and_run(body, "recursion.h", "recursion.c")

    def test_no_loops(self):
        self.assert_no_loops(SOURCE / "recursion.c")

    def test_array_sum(self):
        body = """
        int a[] = {4, -2, 7, 2000000000, 2000000000};
        printf("%lld %lld %lld %lld\\n", array_sum(NULL, 0), array_sum(a, 1), array_sum(a, 3), array_sum(a, 5));
        """
        self.check(self.recursion(body), "0 4 9 4000000009", "array_sum con 0, 1, 3 y 5 elementos")

    def test_array_max(self):
        body = """
        int a[] = {-4, -2, -7, 3, 3, 1};
        printf("%d %d %d %d\\n", array_max(a, 1), array_max(a, 3), array_max(a, 6), array_max(a + 2, 1));
        """
        self.check(self.recursion(body), "-4 -2 3 -7", "array_max con negativos y con repetidos")

    def test_is_palindrome(self):
        cases = {"": 1, "a": 1, "aa": 1, "ab": 0, "abba": 1, "reconocer": 1, "abca": 0, "abcda": 0, "Ana": 0}
        for text, wanted in cases.items():
            with self.subTest(text=text):
                body = f'printf("%d\\n", is_palindrome("{text}") != 0);'
                self.check(self.recursion(body), str(wanted), f'is_palindrome("{text}")')

    def test_count_char(self):
        body = """
        printf("%zu %zu %zu %zu\\n", count_char("", 'a'), count_char("banana", 'a'),
               count_char("banana", 'x'), count_char("Chosica", 'c'));
        """
        self.check(self.recursion(body), "0 3 0 1", "count_char distingue mayúsculas y revisa la cadena completa")

    def test_reverse_string(self):
        for text, wanted in {"": "", "a": "a", "ab": "ba", "abc": "cba", "Lima": "amiL", "recursion": "noisrucer"}.items():
            with self.subTest(text=text):
                body = f'char s[] = "{text}"; reverse_string(s); printf("[%s]\\n", s);'
                self.check(self.recursion(body), f"[{wanted}]", f'reverse_string("{text}")')

    def test_recursion_is_really_used_on_long_input(self):
        body = """
        size_t n = 5000;
        char *s = malloc(n + 1);
        if (s == NULL) { return 1; }
        memset(s, 'x', n); s[n] = '\\0';
        printf("%d %zu\\n", is_palindrome(s) != 0, count_char(s, 'x'));
        s[0] = 'y'; reverse_string(s);
        printf("%c%c\\n", s[0], s[n - 1]);
        free(s);
        """
        self.check(self.recursion(body), "1 5000\nxy", "cadena de 5000 caracteres")

    def test_their_own_tests_cover_every_function(self):
        path = SOURCE / "recursion_tests.c"
        code = path.read_text(encoding="utf-8")
        for name in ["array_max", "is_palindrome", "count_char", "reverse_string"]:
            with self.subTest(function=name):
                if name + "(" not in code:
                    self.fail(f"recursion_tests.c todavía no prueba {name}.")

    def test_their_own_tests_pass(self):
        with tempfile.TemporaryDirectory() as name:
            binary = pathlib.Path(name) / "tests"
            compile_command([SOURCE / "recursion_tests.c", SOURCE / "recursion.c", "-o", binary])
            out, code = run_binary(binary)
        self.assertEqual(code, 0, f"Sus pruebas fallan:\n{out}")


@unittest.skipUnless((SOURCE / "counted.c").exists(), f"no está {LAB_DIR}/counted.c")
class Counting(LabCase):
    def counted(self, body):
        return build_and_run(body, "counted.h", "counted.c")

    def test_no_loops(self):
        self.assert_no_loops(SOURCE / "counted.c")

    def test_power_fast_values(self):
        body = """
        long c = 0;
        printf("%lld %lld %lld %lld %lld %lld\\n", power_fast(5, 0, &c), power_fast(2, 1, &c), power_fast(2, 10, &c),
               power_fast(3, 13, &c), power_fast(-3, 3, &c), power_fast(2, 62, &c));
        """
        self.check(self.counted(body), "1 2 1024 1594323 -27 4611686018427387904", "valores de power_fast")

    def test_power_fast_calls(self):
        for n, wanted in {0: 1, 1: 2, 10: 5, 62: 7, 1024: 12}.items():
            with self.subTest(n=n):
                body = f'long c = 0; power_fast(1, {n}, &c); printf("%ld\\n", c);'
                self.check(self.counted(body), str(wanted), f"llamadas de power_fast(1, {n})")

    def test_binary_search_finds_each_position(self):
        body = """
        int a[] = {1, 3, 5, 7, 9, 11, 13, 15};
        long c = 0;
        for (size_t n = 1; n <= 8; n++) {
            for (size_t i = 0; i < n; i++) {
                if (binary_search(a, n, a[i], &c) != (long) i) { printf("mal: n=%zu i=%zu\\n", n, i); }
            }
        }
        printf("listo\\n");
        """
        self.check(self.counted(body), "listo", "binary_search con cada posición y cada tamaño")

    def test_binary_search_when_absent(self):
        body = """
        int a[] = {1, 3, 5, 7};
        long c = 0;
        printf("%ld %ld %ld %ld %ld\\n", binary_search(NULL, 0, 1, &c), binary_search(a, 4, 0, &c),
               binary_search(a, 4, 4, &c), binary_search(a, 4, 8, &c), binary_search(a, 1, 3, &c));
        """
        self.check(self.counted(body), "-1 -1 -1 -1 -1", "binary_search de un valor que no está")

    def test_binary_search_with_repeated_values(self):
        body = """
        int a[] = {2, 2, 2, 2, 5};
        long c = 0;
        long i = binary_search(a, 5, 2, &c);
        printf("%d %ld\\n", i >= 0 && i <= 3, binary_search(a, 5, 5, &c));
        """
        self.check(self.counted(body), "1 4", "binary_search con repetidos")

    def test_binary_search_really_halves(self):
        body = """
        size_t n = 1000000;
        int *a = malloc(n * sizeof *a);
        if (a == NULL) { return 1; }
        for (size_t i = 0; i < n; i++) { a[i] = 2 * (int) i; }
        long found = 0, absent = 0;
        long i = binary_search(a, n, 1999998, &found);
        long j = binary_search(a, n, 7, &absent);
        printf("%ld %ld %d %d\\n", i, j, found >= 1 && found <= 22, absent >= 1 && absent <= 22);
        free(a);
        """
        self.check(self.counted(body), "999999 -1 1 1", "binary_search en un millón de elementos, con 22 llamadas o menos")


@unittest.skipUnless((SOURCE / "merge_sort.c").exists(), f"no está {LAB_DIR}/merge_sort.c")
class MergeSort(LabCase):
    def sorted_ok(self, data):
        values = ", ".join(map(str, data))
        wanted = " ".join(map(str, sorted(data)))
        body = f"""
        int a[] = {{{values}}};
        size_t n = sizeof a / sizeof a[0];
        if (!merge_sort(a, n)) {{ printf("devolvió 0\\n"); return 0; }}
        for (size_t i = 0; i < n; i++) {{ printf(i ? " %d" : "%d", a[i]); }}
        printf("\\n");
        """
        return build_and_run(body, "merge_sort.h", "merge_sort.c"), wanted

    def test_small_arrays(self):
        for data in ([1], [2, 1], [1, 2], [3, 1, 2], [5, 5, 5], [9, -1, 4, -1, 0], [31, 18, 25, 9, 22, 7, 14],
                     [8, 7, 6, 5, 4, 3, 2, 1], [1, 2, 3, 4, 5, 6, 7, 8]):
            with self.subTest(data=data):
                result, wanted = self.sorted_ok(data)
                self.check(result, wanted, f"merge_sort de {data}")

    def test_empty_and_one_element(self):
        body = """
        int one[] = {7};
        printf("%d %d %d\\n", merge_sort(NULL, 0) != 0, merge_sort(one, 1) != 0, one[0]);
        """
        self.check(build_and_run(body, "merge_sort.h", "merge_sort.c"), "1 1 7", "merge_sort de 0 y 1 elementos")

    def test_large_array(self):
        body = """
        size_t n = 200000;
        int *a = malloc(n * sizeof *a);
        if (a == NULL) { return 1; }
        unsigned int x = 12345;
        long long total = 0, after = 0;
        for (size_t i = 0; i < n; i++) {
            x = x * 1103515245u + 12345u;
            a[i] = (int) (x % 100000) - 50000;
            total += a[i];
        }
        printf("%d\\n", merge_sort(a, n) != 0);
        int good = 1;
        for (size_t i = 0; i < n; i++) {
            after += a[i];
            if (i > 0 && a[i - 1] > a[i]) { good = 0; }
        }
        printf("%d %d\\n", good, total == after);
        free(a);
        """
        self.check(build_and_run(body, "merge_sort.h", "merge_sort.c"), "1\n1 1", "merge_sort de 200000 elementos")

    def memory_case(self, fail_at):
        """Falla el pedido número fail_at; merge_sort se compila aparte para interceptar malloc."""
        driver = HEADERS + f"""#include "merge_sort.h"
        static int requests = 0;
        void *test_malloc(size_t size) {{
            requests++;
            return requests == {fail_at} ? NULL : malloc(size);
        }}
        void *test_calloc(size_t count, size_t size) {{
            requests++;
            return requests == {fail_at} ? NULL : calloc(count, size);
        }}
        int main(void) {{
            int a[] = {{5, 3, 8, 1, 9, 2, 7, 4, 6, 0}};
            int ok = merge_sort(a, 10);
            int one[] = {{1}};
            requests = 0;
            int small = merge_sort(one, 1) != 0 && merge_sort(NULL, 0) != 0;
            printf("%d %d %d\\n", ok != 0, requests == 0, small);
            return 0;
        }}
        """
        with tempfile.TemporaryDirectory() as name:
            folder = pathlib.Path(name)
            (folder / "driver.c").write_text(driver, encoding="utf-8")
            compile_command(["-c", SOURCE / "merge_sort.c", "-Dmalloc=test_malloc", "-Dcalloc=test_calloc",
                             "-o", folder / "merge_sort.o"])
            compile_command([folder / "driver.c", folder / "merge_sort.o", "-o", folder / "driver"])
            return run_binary(folder / "driver")

    def test_without_memory_returns_zero_and_does_not_leak(self):
        self.check(self.memory_case(1), "0 1 1", "merge_sort sin memoria debe devolver 0, sin fugas")

    def test_a_later_failure_does_not_leak(self):
        # Si reservan más de una vez, un pedido que falla más adelante tampoco deja fugas.
        out, code = self.memory_case(2)
        if code != 0:
            self.fail(f"merge_sort, cuando falla el segundo pedido de memoria: el programa terminó con error.\n{out}")


@unittest.skipUnless((SOURCE / "overflow.c").exists(), f"no está {LAB_DIR}/overflow.c")
class Overflow(LabCase):
    def built(self, folder):
        source = SOURCE / "overflow.c"
        binary = pathlib.Path(folder) / "overflow"
        compile_command([source, "-o", binary])
        return binary

    def test_sum_by_twos_ends_with_odd_numbers(self):
        with tempfile.TemporaryDirectory() as name:
            binary = self.built(name)
            for n, wanted in {0: "0", 10: "30", 11: "36", 1: "1", -3: "0", -4: "0"}.items():
                with self.subTest(n=n):
                    self.check(run_binary(binary, ["twos", str(n)]), wanted, f"overflow twos {n}")

    def test_sum_stays_correct(self):
        with tempfile.TemporaryDirectory() as name:
            binary = self.built(name)
            self.check(run_binary(binary, ["sum", "1000"]), "500500", "overflow sum 1000")


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

"""Vuelve a correr los comandos que aparecen en los apuntes y en las diapositivas
y comprueba que el código citado existe de verdad en esta carpeta."""
import os
import platform
import pathlib
import re
import select
import subprocess
import unittest

try:
    import pty
except ImportError:
    pty = None

HERE = pathlib.Path(__file__).parent
ROOT = HERE.parent.parent
NOTES = ROOT / "notes" / "week-09.md"
SLIDES = ROOT / "slides" / "week-09.tex"
# Antes de un bloque cuya salida cambia con el sistema. No se compara.
SYSTEM_DEPENDENT = "<!-- depende del sistema -->"
# Antes de un extracto de un informe de ASan, UBSan o valgrind: sus líneas deben aparecer
# en la salida real y en ese orden, sin contar direcciones, números de proceso ni rutas.
REPORT = "<!-- extracto de un informe -->"
# Antes de una sesión de gdb. Las direcciones y los números de proceso no se comparan.
GDB_SESSION = "<!-- sesión de gdb -->"
# Antes de lo que escribe demo con la solución.
DEMO_OUTPUT = "<!-- salida de demo -->"
# Las sesiones se capturaron en esta arquitectura: en otra pueden cambiar algunas líneas.
GDB_MACHINE = "aarch64"
GDB_FLAGS = ["-Wall", "-Wextra", "-std=c17", "-g", "-O0"]
GDB_SOURCES = {"factorial": ["factorial.c"], "no_base_case": ["errors/no_base_case.c"]}


def normalize(text):
    # Según el idioma del entorno, gcc usa comillas tipográficas o rectas.
    return text.replace("‘", "'").replace("’", "'")


def run_shell(command):
    done = subprocess.run(
        ["bash", "-c", command], cwd=HERE, text=True, encoding="utf-8", errors="replace",
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=60,
    )
    return normalize(done.stdout)


def clean_lines(text):
    return [line.rstrip() for line in text.splitlines()]


def split_commands(lines):
    """Parte un bloque de terminal en pares (comando, líneas de salida)."""
    pairs = []
    for line in lines:
        if line.startswith("$ "):
            pairs.append((line[2:], []))
        elif pairs:
            pairs[-1][1].append(normalize(line.rstrip()))
    return pairs


def note_blocks(language):
    """Devuelve (líneas, marca) de cada bloque de los apuntes."""
    blocks, current, mark, previous = [], None, "", ""
    for raw in NOTES.read_text(encoding="utf-8").splitlines():
        line = re.sub(r"^> ?", "", raw)
        if current is None:
            if line.strip() == "```" + language:
                current, mark = [], previous.strip()
            elif line.strip():
                previous = line
        elif line.strip() == "```":
            blocks.append((current, mark))
            current = None
        else:
            current.append(line)
    return blocks


def slide_blocks(environments):
    text = SLIDES.read_text(encoding="utf-8")
    pattern = r"\\begin\{(?:%s)\}[^\n]*\n(.*?)\\end\{(?:%s)\}" % (environments, environments)
    return [match.group(1).splitlines() for match in re.finditer(pattern, text, re.S)]


def known_code_lines():
    lines = set()
    sources = list(HERE.glob("*.c")) + list(HERE.glob("*.h")) + list((HERE / "errors").glob("*.c"))
    sources += list((HERE / "lab").glob("*.c")) + list((HERE / "lab").glob("*.h"))
    for source in sources:
        lines.update(line.strip() for line in source.read_text(encoding="utf-8").splitlines())
    return lines


def stable_report_line(line):
    line = normalize(line).rstrip()
    line = line.replace(str(HERE.resolve()) + "/", "")
    line = re.sub(r"0x[0-9a-fA-F]+", "ADDR", line)
    line = re.sub(r"==\d+==", "==N==", line)
    return line.strip()


def assert_in_order(case, wanted, got, label):
    position = 0
    for line in wanted:
        if not line.strip() or line.strip() == "...":
            continue
        with case.subTest(label=label, line=line):
            found = [i for i in range(position, len(got)) if line in got[i]]
            case.assertTrue(found, f"no aparece en la salida real: {line}")
            if found:
                position = found[0] + 1


def real_gdb_session(program, commands):
    """Corre gdb en una terminal de verdad: cada comando espera al prompt anterior."""
    os.environ["TERM"] = "dumb"
    pid, fd = pty.fork()
    if pid == 0:
        os.execvp("gdb", ["gdb", "-q", program])

    def read_until_prompt():
        data = b""
        while not data.endswith(b"(gdb) "):
            ready, _, _ = select.select([fd], [], [], 120)
            if not ready:
                break
            try:
                chunk = os.read(fd, 4096)
            except OSError:
                break
            if not chunk:
                break
            data += chunk
        return data

    output = read_until_prompt()
    for command in commands:
        os.write(fd, (command + "\n").encode())
        output += read_until_prompt()
    os.close(fd)
    os.waitpid(pid, 0)
    return output.decode("utf-8", errors="replace").replace("\r", "")


def stable_gdb_lines(lines):
    """Quita lo que cambia entre corridas y deja el resto, sin las direcciones."""
    stable = []
    for line in lines:
        line = line.rstrip()
        if not line or line.startswith(("Starting program", "(gdb)", "[Thread", "Using host")):
            continue
        line = re.sub(r"0x[0-9a-f]+", "ADDR", line)
        line = re.sub(r"process \d+", "process N", line)
        # Cuántos marcos caben depende de la corrida: no se comparan esos números.
        line = re.sub(r"#\d{3,}", "#N", line)
        line = re.sub(r"n=-\d+", "n=M", line)
        # Lo que gdb muestra del marco que cayó depende de hasta dónde llegó a escribir.
        if re.match(r"(#0\s+)?sum_down \(|\s+n=<error|\s+at errors/", line):
            continue
        stable.append(line)
    return stable


class NotesAreTrue(unittest.TestCase):
    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    def test_terminal_blocks_in_notes(self):
        checked = 0
        for lines, mark in note_blocks("text"):
            if not lines or not lines[0].startswith("$ ") or mark in (GDB_SESSION, DEMO_OUTPUT):
                continue
            for command, expected in split_commands(lines):
                actual = clean_lines(run_shell(command))
                checked += 1
                if mark == REPORT:
                    # El detalle de un stack overflow cambia con la arquitectura.
                    if platform.machine() != GDB_MACHINE:
                        continue
                    assert_in_order(self, [stable_report_line(line) for line in expected],
                                    [stable_report_line(line) for line in actual], command)
                elif mark != SYSTEM_DEPENDENT:
                    with self.subTest(command=command):
                        self.assertEqual(actual, expected)
        self.assertGreater(checked, 10)

    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    def test_code_blocks_in_notes_exist(self):
        known = known_code_lines()
        for lines, _ in note_blocks("c"):
            for line in lines:
                if line.strip() and line.strip() != "...":
                    with self.subTest(line=line):
                        self.assertIn(line.strip(), known)

    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    @unittest.skipUnless(pty and platform.machine() == GDB_MACHINE, "las sesiones son de aarch64")
    def test_gdb_sessions_in_notes(self):
        probe = subprocess.run(
            ["gdb", "-q", "-batch", "-ex", "run", "/bin/true"], text=True,
            stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
        )
        if "exited normally" not in probe.stdout:
            self.skipTest("gdb no puede correr programas aquí")
        checked = 0
        for lines, mark in note_blocks("text"):
            if mark != GDB_SESSION:
                continue
            program = lines[0].split()[-1]
            name = pathlib.Path(program).name.removesuffix("_gdb")
            sources = GDB_SOURCES.get(name, [name + ".c"])
            subprocess.run(["gcc", *GDB_FLAGS, *sources, "-o", program], cwd=HERE, check=True,
                           stdout=subprocess.DEVNULL, stderr=subprocess.DEVNULL)
            commands = [line[6:].strip() for line in lines if line.startswith("(gdb) ")]
            cwd = os.getcwd()
            os.chdir(HERE)
            try:
                actual = real_gdb_session(program, commands)
            finally:
                os.chdir(cwd)
            wanted = stable_gdb_lines(lines[1:])
            got = stable_gdb_lines(actual.splitlines())
            position = 0
            for line in wanted:
                with self.subTest(program=program, line=line):
                    found = [i for i in range(position, len(got)) if got[i] == line]
                    self.assertTrue(found, f"no aparece en la sesión real: {line}")
                    if found:
                        position = found[0] + 1
            checked += 1
        self.assertGreater(checked, 1)

    @unittest.skipUnless(NOTES.exists() and (HERE / "solution").exists(), "falta la solución")
    def test_demo_output_in_notes(self):
        checked = 0
        for lines, mark in note_blocks("text"):
            if mark == DEMO_OUTPUT:
                self.assertEqual(lines[0], "$ build/lab/demo")
                actual = clean_lines(run_shell("build/solution/demo"))
                self.assertEqual(actual, [line.rstrip() for line in lines[1:]])
                checked += 1
        self.assertGreater(checked, 0)


class SlidesAreTrue(unittest.TestCase):
    @unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
    def test_terminal_blocks_in_slides(self):
        # Las sesiones de gdb y los informes van en otro entorno, sesiongdb, que no se compara.
        for block in slide_blocks("terminal|salida|salidalarga"):
            for command, expected in split_commands(block):
                actual = clean_lines(run_shell(command))
                position = 0
                # Una diapositiva puede omitir líneas, pero no cambiarlas ni reordenarlas.
                for line in expected:
                    line = line.strip()
                    if not line:
                        continue
                    with self.subTest(command=command, line=line):
                        found = [i for i in range(position, len(actual)) if actual[i].strip() == line]
                        self.assertTrue(found, f"no aparece en la salida real: {line}")
                        if found:
                            position = found[0] + 1

    @unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
    def test_code_blocks_in_slides_exist(self):
        known = known_code_lines()
        for block in slide_blocks("codigo|codigochico|codigomini"):
            for line in block:
                if line.strip() and line.strip() != "...":
                    with self.subTest(line=line):
                        self.assertIn(line.strip(), known)


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