// Pruebas de derivaciones, árboles y ambigüedad (sesión A).
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <set>
#include <string>
#include <vector>

#include "cfg.h"

static std::size_t count_leftmost(const Cfg& g, const std::string& w) {
    DerivationSearch search = leftmost_derivations(g, w, 1000, 100000);
    assert(search.complete);
    return search.found.size();
}

// Cada derivación por la izquierda da un árbol de derivación de w, con tantos nodos internos
// como pasos, y dos derivaciones por la izquierda distintas dan árboles distintos.
static void check_trees(const Cfg& g, const std::string& w) {
    DerivationSearch search = leftmost_derivations(g, w, 1000, 100000);
    assert(search.complete);
    std::set<std::string> seen;
    for (const Derivation& derivation : search.found) {
        Tree tree = tree_of(g, derivation);
        assert(is_parse_tree(g, tree));
        assert(yield_of(tree) == w);
        assert(count_inner(tree) == derivation.size());
        assert(seen.insert(bracket_text(tree)).second);
    }
}

// Toda cadena de L(G) hasta max_length tiene exactamente una derivación por la izquierda.
// No demuestra que la gramática no sea ambigua, pero una cadena corta con dos árboles la delataría.
static std::size_t check_one_tree_each(const Cfg& g, std::size_t max_length) {
    std::set<std::string> generated = generated_strings(g, max_length);
    for (const std::string& w : generated) {
        assert(count_leftmost(g, w) == 1);
    }
    return generated.size();
}

static void test_expressions() {
    Cfg ambiguous = load_cfg("machines/expr_ambiguous.cfg");
    Cfg levels = load_cfg("machines/expr_precedence.cfg");
    // El ejemplo de los apuntes: dos derivaciones por la izquierda contra una.
    assert(count_leftmost(ambiguous, "a+a*a") == 2);
    assert(count_leftmost(levels, "a+a*a") == 1);
    check_trees(ambiguous, "a+a*a");
    check_trees(levels, "a+a*a");
    // Los dos árboles de la gramática ambigua, y las dos derivaciones como salen en los apuntes.
    DerivationSearch search = leftmost_derivations(ambiguous, "a+a*a", 1000);
    assert(bracket_text(tree_of(ambiguous, search.found[0])) == "[E [E a] + [E [E a] * [E a]]]");
    assert(bracket_text(tree_of(ambiguous, search.found[1])) == "[E [E [E a] + [E a]] * [E a]]");
    // El árbol de la gramática con niveles agrupa el producto: a + (a * a).
    search = leftmost_derivations(levels, "a+a*a", 1000);
    assert(search.found[0].size() == 8);
    assert(bracket_text(tree_of(levels, search.found[0])) == "[E [E [T [F a]]] + [T [T [F a]] * [F a]]]");
    // La ambigüedad también aparece con un solo operador: (a+a)+a y a+(a+a).
    assert(count_leftmost(ambiguous, "a+a+a") == 2);
    assert(count_leftmost(ambiguous, "a+a+a+a") == 5);
    assert(count_leftmost(levels, "a+a+a+a") == 1);
    // Las dos gramáticas generan el mismo lenguaje, y en la de niveles cada cadena tiene un solo árbol.
    assert(generated_strings(ambiguous, 7) == generated_strings(levels, 7));
    check_one_tree_each(levels, 7);
}

static void test_dangling_else() {
    Cfg dangling = load_cfg("machines/dangling_else.cfg");
    Cfg fixed = load_cfg("machines/dangling_else_fixed.cfg");
    assert(count_leftmost(dangling, "iiaea") == 2);
    assert(count_leftmost(fixed, "iiaea") == 1);
    check_trees(dangling, "iiaea");
    // En la gramática corregida el else queda con el if de adentro.
    DerivationSearch search = leftmost_derivations(fixed, "iiaea", 1000);
    assert(bracket_text(tree_of(fixed, search.found[0])) == "[S [U i [S [M i [M a] e [M a]]]]]");
    assert(generated_strings(dangling, 10) == generated_strings(fixed, 10));
    check_one_tree_each(fixed, 10);
}

static void test_two_derivations_one_tree() {
    Cfg g = load_cfg("machines/two_derivations.cfg");
    assert(count_leftmost(g, "ab") == 1);
    check_trees(g, "ab");
}

static void test_union() {
    Cfg g = load_cfg("machines/abc_union.cfg");
    // Dos árboles exactamente cuando i = j = k. El caso i = j = k = 0 es ε, que también tiene dos.
    for (const std::string& w : generated_strings(g, 9)) {
        std::size_t a = 0, b = 0, c = 0;
        for (char x : w) {
            a += (x == 'a');
            b += (x == 'b');
            c += (x == 'c');
        }
        assert(count_leftmost(g, w) == ((a == b && b == c) ? 2u : 1u));
    }
}

static void test_other_grammars() {
    // Gramáticas del capítulo en las que cada cadena tiene un solo árbol.
    check_one_tree_each(load_cfg("machines/zeros_ones.cfg"), 12);
    check_one_tree_each(load_cfg("machines/palindromes.cfg"), 10);
    check_one_tree_each(load_cfg("machines/parens.cfg"), 12);
    check_one_tree_each(load_cfg("machines/even_ones.cfg"), 9);
    check_one_tree_each(load_cfg("machines/blocks.cfg"), 12);
    // Con S → SS, la cadena ()()() ya tiene más de un árbol aunque se limite la búsqueda.
    Cfg ss = load_cfg("machines/parens_ss.cfg");
    assert(leftmost_derivations(ss, "()()()", 12, 100000).found.size() >= 2);
}

int main() {
    test_expressions();
    test_dangling_else();
    test_two_derivations_one_tree();
    test_union();
    test_other_grammars();
    std::printf("test_ambiguity: ok\n");
}
