// Pruebas de la sesión A: el formato .cfg, y que cada gramática de machines/ genera exactamente
// su lenguaje. Para cada una se comparan todas las cadenas hasta una longitud con una función
// de predicates.h que decide el mismo lenguaje sin usar la gramática.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

#include "cfg.h"
#include "predicates.h"

static bool throws(const std::function<void()>& action) {
    try {
        action();
    } catch (const std::runtime_error&) {
        return true;
    }
    return false;
}

// L(G) y el predicado coinciden en todas las cadenas de longitud a lo sumo max_length.
// Devuelve cuántas cadenas se revisaron.
static std::size_t check_language(const std::string& path, std::size_t max_length,
                                  const std::function<bool(const std::string&)>& in_language) {
    Cfg g = load_cfg(path);
    std::set<std::string> generated = generated_strings(g, max_length);
    std::vector<std::string> words = all_strings(g.terminals, max_length);
    for (const std::string& w : words) {
        assert((generated.count(w) > 0) == in_language(w));
    }
    return words.size();
}

static void test_format() {
    // El ejemplo de code/formats.md.
    Cfg g = load_cfg("machines/parens.cfg");
    assert(g.variables == std::vector<std::string>{"S"});
    assert((g.terminals == std::vector<char>{'(', ')'}));
    assert(g.start == "S");
    assert(g.rules.size() == 2);
    assert((g.rules[0] == Rule{"S", {"(", "S", ")", "S"}}));
    assert((g.rules[1] == Rule{"S", {}}));

    // Lo que se escribe se vuelve a leer igual.
    for (const char* path : {"machines/expr_precedence.cfg", "machines/abc_union.cfg", "machines/blocks.cfg"}) {
        Cfg original = load_cfg(path);
        std::ostringstream text;
        write_cfg(text, original);
        std::istringstream again(text.str());
        Cfg copy = read_cfg(again);
        assert(copy.variables == original.variables && copy.terminals == original.terminals);
        assert(copy.start == original.start && copy.rules == original.rules);
    }

    // Una variable puede tener varias líneas, y una regla repetida cuenta una vez.
    std::istringstream lines("variables: S\nterminals: a\nstart: S\nrules:\nS -> a S\n# comentario\nS -> eps | a S\n");
    Cfg joined = read_cfg(lines);
    assert(joined.rules.size() == 2);

    // Las tres descripciones de errors/ no son gramáticas.
    assert(throws([] { load_cfg("errors/unknown_symbol.cfg"); }));
    assert(throws([] { load_cfg("errors/start_not_variable.cfg"); }));
    assert(throws([] { load_cfg("errors/glued_symbols.cfg"); }));
    std::istringstream empty_alternative("variables: S\nterminals: a\nstart: S\nrules:\nS -> a |\n");
    assert(throws([&] { read_cfg(empty_alternative); }));
}

static std::size_t test_languages() {
    std::size_t total = 0;
    total += check_language("machines/zeros_ones.cfg", 12, is_zeros_ones);
    total += check_language("machines/palindromes.cfg", 12, is_palindrome);
    total += check_language("machines/parens.cfg", 12, is_balanced);
    total += check_language("machines/parens_ss.cfg", 12, is_balanced);
    total += check_language("machines/equal_ab.cfg", 10, has_equal_ab);
    total += check_language("machines/even_ones.cfg", 10, has_even_ones);
    total += check_language("machines/blocks.cfg", 12, is_block_list);
    total += check_language("machines/abc_union.cfg", 9, is_abc_union);
    total += check_language("machines/expr_ambiguous.cfg", 7, is_expression);
    total += check_language("machines/expr_precedence.cfg", 7, is_expression);
    total += check_language("machines/dangling_else.cfg", 9, is_if_else);
    total += check_language("machines/dangling_else_fixed.cfg", 9, is_if_else);
    return total;
}

// Lo que afirma la demostración de { 0^n 1^n }: la forma después de k pasos es 0^k S 1^k o,
// si ya terminó, 0^(k−1) 1^(k−1). La derivación de 0^n 1^n es una sola y tiene n + 1 pasos.
static void test_zeros_ones_proof() {
    Cfg g = load_cfg("machines/zeros_ones.cfg");
    for (std::size_t n = 0; n <= 8; n++) {
        std::string w = std::string(n, '0') + std::string(n, '1');
        DerivationSearch search = leftmost_derivations(g, w, 100);
        assert(search.complete && search.found.size() == 1);
        assert(search.found[0].size() == n + 1);
        std::vector<std::vector<std::string>> forms = sentential_forms(g, search.found[0]);
        for (std::size_t k = 0; k < forms.size(); k++) {
            std::string text = form_text(g, forms[k]);
            if (k <= n) {
                assert(text == std::string(k, '0') + "S" + std::string(k, '1'));
            } else {
                assert(n == 0 ? text == "ε" : text == w);
            }
        }
    }
}

// La búsqueda de derivaciones por la izquierda y el cálculo de L(G) hasta una longitud
// responden lo mismo. Solo con gramáticas donde la búsqueda termina sola.
static void test_search_agrees() {
    struct Case {
        const char* path;
        std::size_t max_length;
    };
    for (const Case& c : {Case{"machines/zeros_ones.cfg", 10}, Case{"machines/palindromes.cfg", 9},
                          Case{"machines/parens.cfg", 10}, Case{"machines/even_ones.cfg", 8},
                          Case{"machines/blocks.cfg", 10}, Case{"machines/expr_precedence.cfg", 5},
                          Case{"machines/dangling_else.cfg", 7}}) {
        Cfg g = load_cfg(c.path);
        std::set<std::string> generated = generated_strings(g, c.max_length);
        for (const std::string& w : all_strings(g.terminals, c.max_length)) {
            DerivationSearch search = leftmost_derivations(g, w, 1000);
            assert(search.complete);
            assert(!search.found.empty() == (generated.count(w) > 0));
        }
    }
}

// Con S → SS y S → ε la búsqueda no termina: S ⇒ SS ⇒ S ⇒ SS ⇒ … Con cualquier tope de pasos se corta.
static void test_search_can_run_forever() {
    Cfg g = load_cfg("machines/parens_ss.cfg");
    for (std::size_t steps : {5, 10, 15}) {
        DerivationSearch search = leftmost_derivations(g, "()", steps, 1000000);
        assert(!search.complete);
    }
    // Y las derivaciones de () son cada vez más al subir el tope.
    assert(leftmost_derivations(g, "()", 4, 1000000).found.size() <
           leftmost_derivations(g, "()", 8, 1000000).found.size());
}

int main() {
    test_format();
    std::size_t total = test_languages();
    test_zeros_ones_proof();
    test_search_agrees();
    test_search_can_run_forever();
    std::printf("test_cfg: ok (12 gramáticas, %zu cadenas comparadas con su predicado)\n", total);
}
