// Pruebas de la conversión a forma normal de Chomsky (sesión B).
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#include "cfg.h"
#include "chomsky.h"

// Las reglas de g como texto, para comparar con lo que muestran los apuntes.
static std::set<std::string> rule_set(const Cfg& g) {
    std::set<std::string> rules;
    for (const Rule& rule : g.rules) {
        rules.insert(rule.head + " -> " + body_text(rule.body));
    }
    return rules;
}

static bool has_epsilon_rule(const Cfg& g, bool also_start) {
    for (const Rule& rule : g.rules) {
        if (rule.body.empty() && (also_start || rule.head != g.start)) {
            return true;
        }
    }
    return false;
}

static bool has_unit_rule(const Cfg& g) {
    for (const Rule& rule : g.rules) {
        if (is_unit(g, rule)) {
            return true;
        }
    }
    return false;
}

static bool start_on_right(const Cfg& g) {
    for (const Rule& rule : g.rules) {
        for (const std::string& symbol : rule.body) {
            if (symbol == g.start) {
                return true;
            }
        }
    }
    return false;
}

struct Case {
    const char* path;
    std::size_t max_length;
};

static const std::vector<Case> GRAMMARS = {
    {"machines/zeros_ones.cfg", 12},     {"machines/palindromes.cfg", 10},    {"machines/parens.cfg", 12},
    {"machines/parens_ss.cfg", 10},      {"machines/equal_ab.cfg", 8},        {"machines/even_ones.cfg", 9},
    {"machines/blocks.cfg", 12},         {"machines/abc_union.cfg", 9},       {"machines/expr_ambiguous.cfg", 7},
    {"machines/expr_precedence.cfg", 7}, {"machines/dangling_else.cfg", 9},   {"machines/dangling_else_fixed.cfg", 9},
    {"machines/two_derivations.cfg", 4}, {"machines/unit_order.cfg", 4},
};

// Cada paso conserva el lenguaje y deja lo que promete. Al final, forma normal de Chomsky.
static void test_each_step() {
    for (const Case& c : GRAMMARS) {
        Cfg g = load_cfg(c.path);
        std::set<std::string> language = generated_strings(g, c.max_length);

        Cfg step1 = with_new_start(g);
        assert(generated_strings(step1, c.max_length) == language);
        assert(!start_on_right(step1));

        Cfg step2 = without_epsilon_rules(step1);
        assert(generated_strings(step2, c.max_length) == language);
        assert(!has_epsilon_rule(step2, false) && !start_on_right(step2));
        // La inicial conserva S0 → ε exactamente cuando ε está en el lenguaje.
        assert(has_epsilon_rule(step2, true) == (language.count("") > 0));

        Cfg step3 = without_unit_rules(step2);
        assert(generated_strings(step3, c.max_length) == language);
        assert(!has_unit_rule(step3) && !has_epsilon_rule(step3, false) && !start_on_right(step3));

        Cfg step4 = with_short_rules(step3);
        assert(generated_strings(step4, c.max_length) == language);
        assert(is_chomsky(step4));
        check_cfg(step4);
        assert(rule_set(step4) == rule_set(to_chomsky(g)));

        // Convertir una gramática que ya está en forma normal solo le agrega la variable inicial nueva.
        assert(is_chomsky(to_chomsky(step4)));
    }
}

// El ejemplo completo de los apuntes: machines/blocks.cfg, paso por paso.
static void test_blocks_example() {
    Cfg g = load_cfg("machines/blocks.cfg");
    Cfg step1 = with_new_start(g);
    assert(step1.start == "S0");
    assert((rule_set(step1) ==
            std::set<std::string>{"S0 -> S", "S -> B S", "S -> eps", "B -> 0 B 1", "B -> 0 1"}));
    assert((nullable_variables(step1) == std::set<std::string>{"S0", "S"}));
    Cfg step2 = without_epsilon_rules(step1);
    assert((rule_set(step2) ==
            std::set<std::string>{"S0 -> S", "S0 -> eps", "S -> B S", "S -> B", "B -> 0 B 1", "B -> 0 1"}));
    // Los pares unitarios, además de los (A, A): S0 llega a S y a B, y S llega a B.
    std::set<std::pair<std::string, std::string>> pairs = unit_pairs(step2);
    assert((pairs == std::set<std::pair<std::string, std::string>>{
                         {"S0", "S0"}, {"S", "S"}, {"B", "B"}, {"S0", "S"}, {"S0", "B"}, {"S", "B"}}));
    Cfg step3 = without_unit_rules(step2);
    assert((rule_set(step3) == std::set<std::string>{"S0 -> eps", "S0 -> B S", "S0 -> 0 B 1", "S0 -> 0 1",
                                                     "S -> B S", "S -> 0 B 1", "S -> 0 1", "B -> 0 B 1",
                                                     "B -> 0 1"}));
    Cfg step4 = with_short_rules(step3);
    assert((rule_set(step4) ==
            std::set<std::string>{"S0 -> eps", "S0 -> B S", "S0 -> U_0 S0_1", "S0 -> U_0 U_1", "S -> B S",
                                  "S -> U_0 S_1", "S -> U_0 U_1", "B -> U_0 B_1", "B -> U_0 U_1", "S0_1 -> B U_1",
                                  "S_1 -> B U_1", "B_1 -> B U_1", "U_0 -> 0", "U_1 -> 1"}));
    assert(step4.rules.size() == 14 && step4.variables.size() == 8);
}

// El error común: quitar las unitarias antes que las reglas ε vuelve a crear unitarias.
static void test_wrong_order() {
    Cfg g = load_cfg("machines/unit_order.cfg");
    Cfg wrong = with_short_rules(without_epsilon_rules(without_unit_rules(with_new_start(g))));
    assert(!is_chomsky(wrong));
    assert(has_unit_rule(wrong));
    assert(why_not_chomsky(wrong) == "S0 -> B: es una regla unitaria");
    // El lenguaje sigue siendo el mismo: lo que se pierde es la forma, no la equivalencia.
    assert(generated_strings(wrong, 6) == generated_strings(g, 6));
    assert(is_chomsky(to_chomsky(g)));
    // Lo mismo pasa con el ejemplo completo: S → BS con S anulable deja S → B.
    Cfg blocks = load_cfg("machines/blocks.cfg");
    assert(!is_chomsky(with_short_rules(without_epsilon_rules(without_unit_rules(with_new_start(blocks))))));
}

// Sin el paso 1, la regla ε de la variable inicial puede seguir usándose en medio de una derivación.
static void test_why_new_start() {
    Cfg g = load_cfg("machines/parens_ss.cfg");
    Cfg skipped = with_short_rules(without_unit_rules(without_epsilon_rules(g)));
    assert(generated_strings(skipped, 8) == generated_strings(g, 8));
    assert(!is_chomsky(skipped));
}

// Una regla con k apariciones de variables anulables se convierte en hasta 2^k reglas.
static void test_epsilon_blowup() {
    std::istringstream text("variables: S A\nterminals: a\nstart: S\nrules:\nS -> A A A A A A\nA -> a | eps\n");
    Cfg g = read_cfg(text);
    Cfg step2 = without_epsilon_rules(with_new_start(g));
    std::size_t rules_of_s = 0;
    for (const Rule& rule : step2.rules) {
        rules_of_s += (rule.head == "S");
    }
    // Borrar apariciones distintas de A da el mismo lado derecho: quedan A, AA, …, AAAAAA.
    assert(rules_of_s == 6);
    std::istringstream other(
        "variables: S A B C\nterminals: a\nstart: S\nrules:\nS -> A B C A B C\nA -> a | eps\nB -> a | eps\nC -> a | eps\n");
    Cfg h = read_cfg(other);
    Cfg h2 = without_epsilon_rules(with_new_start(h));
    rules_of_s = 0;
    for (const Rule& rule : h2.rules) {
        rules_of_s += (rule.head == "S");
    }
    // Las subsecuencias no vacías y distintas de ABCABC.
    assert(rules_of_s == 51);
}

// En forma normal de Chomsky, toda derivación de una cadena de longitud n ≥ 1 tiene 2n − 1 pasos.
static std::size_t test_derivation_length() {
    std::size_t checked = 0;
    for (const Case& c : GRAMMARS) {
        Cfg g = to_chomsky(load_cfg(c.path));
        std::size_t max_length = std::string(c.path).find("expr") != std::string::npos ? 5 : 6;
        for (const std::string& w : generated_strings(g, max_length)) {
            DerivationSearch search = leftmost_derivations(g, w, 1000, 100000);
            assert(search.complete && !search.found.empty());
            for (const Derivation& derivation : search.found) {
                assert(derivation.size() == (w.empty() ? 1 : 2 * w.size() - 1));
                checked++;
            }
        }
    }
    return checked;
}

int main() {
    test_each_step();
    test_blocks_example();
    test_wrong_order();
    test_why_new_start();
    test_epsilon_blowup();
    std::size_t checked = test_derivation_length();
    std::printf("test_chomsky: ok (14 gramáticas convertidas, %zu derivaciones de 2n − 1 pasos)\n", checked);
}
