"""Comprueba los programas de la clase y lo que los apuntes dicen de ellos.""" import pathlib import subprocess import tempfile import unittest HERE = pathlib.Path(__file__).parent BUILD = HERE / "build" SOLUTION = BUILD / "solution" BASE = ["-Wall", "-Wextra", "-std=c17"] FLAGS = [*BASE, "-g", "-fsanitize=address,undefined"] PROGRAMS = ["fib_count", "fib_trace", "fib_memo", "grid_fill", "fill_trace", "count_islands", "maze", "deep_fill", "fill_stack"] # El mismo tamaño de pila que tiene el entorno del curso, para no depender de cómo se abrió la terminal. STACK_KB = 8192 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=60, ) return done.stdout, done.returncode def run_with_stack(kilobytes, program, *args): """Corre el programa con esa pila. Devuelve (salida, código de salida de bash).""" command = f"ulimit -s {kilobytes} && exec {program} " + " ".join(args) done = subprocess.run( ["bash", "-c", command], cwd=HERE, text=True, encoding="utf-8", errors="replace", stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=60, ) return done.stdout, done.returncode def can_raise_stack(kilobytes): done = subprocess.run(["bash", "-c", f"ulimit -s {kilobytes}"], stdout=subprocess.DEVNULL, stderr=subprocess.DEVNULL) return done.returncode == 0 def rows_of(text): return [line.split() for line in text.splitlines()[1:]] class Programs(unittest.TestCase): def test_every_program_compiles_without_warnings(self): for name in PROGRAMS: 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_errors_compile_without_warnings(self): # Los errores de esta semana no los ve el compilador: aparecen al correr. for name in ("fill_no_mark", "fill_same_mark"): with self.subTest(program=name): subprocess.run(["gcc", *FLAGS, "-Werror", "-c", f"errors/{name}.c", "-o", "/dev/null"], cwd=HERE, check=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT) def test_the_lab_compiles_without_warnings(self): for name in ("image", "regions", "board", "fill_demo", "minesweeper", "big_board", "regions_tests", "board_tests"): with self.subTest(file=name): subprocess.run(["gcc", *FLAGS, "-Werror", "-Ilab", "-c", f"lab/{name}.c", "-o", "/dev/null"], cwd=HERE, check=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT) def test_no_program_leaks(self): for name in PROGRAMS: args = ("20",) if name in ("deep_fill", "fill_stack") else () with self.subTest(program=name): out, code = run(BUILD / name, *args) self.assertEqual(code, 0, out) self.assertNotIn("LeakSanitizer", out) class Fibonacci(unittest.TestCase): def test_calls_follow_the_formula(self): # llamadas(n) = 2 * fib(n + 1) - 1 fib = [0, 1] for _ in range(50): fib.append(fib[-1] + fib[-2]) out, _ = run(BUILD / "fib_count") for n, value, calls in rows_of(out): with self.subTest(n=n): self.assertEqual(int(value), fib[int(n)]) self.assertEqual(int(calls), 2 * fib[int(n) + 1] - 1) def test_fib_5_makes_15_calls(self): out, _ = run(BUILD / "fib_count") self.assertIn(["5", "5", "15"], rows_of(out)) def test_trace_has_one_line_per_call(self): out, _ = run(BUILD / "fib_trace") self.assertEqual(sum(line.strip().startswith("fib(") for line in out.splitlines()), 9) def test_memo_calls_are_2n_minus_1(self): out, _ = run(BUILD / "fib_memo") for row in rows_of(out): if len(row) == 4: n, _, plain, memo = row with self.subTest(n=n): self.assertEqual(int(memo), 2 * int(n) - 1) self.assertGreaterEqual(int(plain), int(memo)) self.assertIn("fib(90) = 2880067194370816120, con 179 llamadas", out) class Depth(unittest.TestCase): def test_the_depth_is_n_squared_plus_one(self): for size in (1, 3, 10, 100): with self.subTest(size=size): out, code = run(BUILD / "deep_fill", str(size)) self.assertEqual(code, 0, out) self.assertIn(f"{size * size} celdas pintadas, {size * size + 1} marcos", out) def test_recursion_breaks_at_1000_with_8_mb(self): # Vale en cualquier arquitectura: un millón de marcos no cabe en 8 MB. for name in ("deep_fill", "deep_fill_plain", "deep_fill_o2"): with self.subTest(program=name): out, code = run_with_stack(STACK_KB, BUILD / name, "1000") self.assertNotEqual(code, 0, out) self.assertNotIn("celdas pintadas", out) def test_asan_names_the_stack_overflow(self): # En x86-64 emulado, ASan a veces cae sin escribir el informe: eso se acepta como caída. out, code = run_with_stack(STACK_KB, BUILD / "deep_fill", "1000") self.assertNotEqual(code, 0) if code == 1: self.assertIn("stack-overflow", out) self.assertIn("in fill", out) def test_plain_build_dies_with_a_signal(self): out, code = run_with_stack(STACK_KB, BUILD / "deep_fill_plain", "1000") self.assertEqual(code, -11, out) @unittest.skipUnless(can_raise_stack(200000), "este sistema no deja agrandar la pila") def test_with_more_stack_it_works(self): out, code = run_with_stack(200000, BUILD / "deep_fill_plain", "1000") self.assertEqual(code, 0, out) self.assertIn("1000000 celdas pintadas, 1000001 marcos", out) def test_own_stack_needs_no_big_stack(self): out, code = run_with_stack(STACK_KB, BUILD / "fill_stack", "1000") self.assertEqual(code, 0, out) self.assertIn("1000000 celdas pintadas", out) self.assertNotIn("LeakSanitizer", out) class MarkErrors(unittest.TestCase): def crash_of(self, name): with tempfile.TemporaryDirectory() as folder: binary = pathlib.Path(folder) / name subprocess.run(["gcc", *FLAGS, f"errors/{name}.c", "-o", str(binary)], cwd=HERE, check=True) return run_with_stack(STACK_KB, binary) def test_marking_after_the_calls_never_ends(self): out, code = self.crash_of("fill_no_mark") self.assertNotEqual(code, 0, out) if code == 1: self.assertIn("stack-overflow", out) def test_painting_with_the_same_mark_never_ends(self): out, code = self.crash_of("fill_same_mark") self.assertNotEqual(code, 0, out) if code == 1: self.assertIn("stack-overflow", out) @unittest.skipUnless((HERE / "solution").exists(), "falta la solución") class BigBoard(unittest.TestCase): def test_small_boards_work(self): for name in ("big_board", "big_board_plain", "big_board_o2"): with self.subTest(program=name): out, code = run_with_stack(STACK_KB, SOLUTION / name, "100", "100") self.assertEqual(code, 0, out) self.assertIn("10000 celdas abiertas, juego ganado", out) def test_1000_by_1000_breaks_the_recursive_reveal(self): for name in ("big_board", "big_board_plain", "big_board_o2"): with self.subTest(program=name): out, code = run_with_stack(STACK_KB, SOLUTION / name, "1000", "1000") self.assertNotEqual(code, 0, out) self.assertNotIn("celdas abiertas", out) @unittest.skipUnless(can_raise_stack(400000), "este sistema no deja agrandar la pila") def test_with_more_stack_the_big_board_works(self): out, code = run_with_stack(400000, SOLUTION / "big_board_plain", "1000", "1000") self.assertEqual(code, 0, out) self.assertIn("1000000 celdas abiertas, juego ganado", out) if __name__ == "__main__": unittest.main()