neberu 0.0.0

// ============================================================
// GOVERNANCE — DIRECTED REWRITE RULES
// ============================================================
//
// A Governance is a set of rewrite rules: Word → Expr.
// Canonicalization applies these rules to a fixed point.
// Evaluation IS canonicalization. No other mechanism.
//
// Key property: signature(gen) = gen.sig — O(1), one field access.
// The type IS the generator. No lookup. No scan.
//
// Clifford algebra construction: given a set of Gen (already typed),
// generate anticommutativity rules from their types.
// The square rule is DERIVED from gen.sig, not stored separately.

use crate::expr::Expr;
use crate::gen::Gen;
use crate::rat::Rat;
use crate::trit::{Trit, N, P, Z};
use crate::word::Word;
use std::collections::BTreeMap;

/// A single rewrite rule: source word → target expression.
#[derive(Clone, PartialEq, Eq, Hash)]
pub struct Relation {
    pub source: Word,
    pub target: Expr,
}

impl Relation {
    pub fn new(source: Word, target: Expr) -> Relation {
        Relation { source, target }
    }
}

impl std::fmt::Debug for Relation {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{} → {}", self.source, self.target)
    }
}

/// A governance: directed rewrite rules over Words.
#[derive(Clone, PartialEq, Eq)]
pub struct Governance {
    relations: Vec<Relation>,
    /// Fast lookup: (gen_a, gen_b) index → relation index.
    pair_index: BTreeMap<(u64, u64), usize>,
}

/// Encode a Gen as a u64 key for pair_index.
fn gen_key(g: Gen) -> u64 {
    ((g.sig.bits() as u64) << 32) | (g.idx as u64)
}

impl Governance {
    /// The free algebra — no constraints.
    pub fn free() -> Governance {
        Governance {
            relations: vec![],
            pair_index: BTreeMap::new(),
        }
    }

    /// Add a relation.
    pub fn with_relation(mut self, rel: Relation) -> Governance {
        if rel.source.grade() == 2 {
            let gens = rel.source.generators();
            let key = (gen_key(gens[0]), gen_key(gens[1]));
            self.pair_index.insert(key, self.relations.len());
        }
        self.relations.push(rel);
        self
    }

    pub fn relations(&self) -> &[Relation] {
        &self.relations
    }
    pub fn num_relations(&self) -> usize {
        self.relations.len()
    }

    /// The square signature of generator g: g.sig. O(1). One field access.
    /// This is the entire point of Gen = (Trit, u32).
    /// No lookup. No scan. The type IS the generator.
    #[inline]
    pub fn signature(&self, g: Gen) -> Trit {
        g.sig
    }

    /// Pair rule lookup: what does (a · b) rewrite to?
    pub fn pair_rule(&self, a: Gen, b: Gen) -> Option<&Expr> {
        self.pair_index
            .get(&(gen_key(a), gen_key(b)))
            .map(|&idx| &self.relations[idx].target)
    }

    /// Build a Clifford algebra from a list of typed generators.
    /// Signature ordering: (i,d,h) — the Gen types carry this directly.
    /// Square rules: derived from gen.sig.
    /// Anticommutativity: for all pairs (a,b) with a < b.
    pub fn clifford(gens: &[Gen]) -> Governance {
        let mut gov = Governance::free();

        // Square rules: derived from gen.sig.
        for &g in gens {
            let square_val = match g.sig {
                N => Expr::int(-1), // imaginary: x²=-1
                Z => Expr::zero(),  // degenerate: x²=0
                P => Expr::int(1),  // hyperbolic: x²=+1
                _ => continue,
            };
            gov = gov.with_relation(Relation::new(Word::from_gens(&[g, g]), square_val));
        }

        // Anticommutativity: b·a = -a·b for all pairs a < b.
        for i in 0..gens.len() {
            for j in (i + 1)..gens.len() {
                let (a, b) = (gens[i], gens[j]);
                // b·a → -a·b
                gov = gov.with_relation(Relation::new(
                    Word::from_gens(&[b, a]),
                    Expr::term(Rat::neg_one(), Word::from_gens(&[a, b])),
                ));
            }
        }

        gov
    }

    /// Convenience: build Cl(i imaginary, d degenerate, h hyperbolic).
    /// Generators are assigned indices 0..n in order (i, d, h).
    pub fn cl(i: u32, d: u32, h: u32) -> Governance {
        let mut gens = Vec::new();
        for k in 0..i {
            gens.push(Gen::imaginary(k));
        }
        for k in 0..d {
            gens.push(Gen::degenerate(k));
        }
        for k in 0..h {
            gens.push(Gen::hyperbolic(k));
        }
        Governance::clifford(&gens)
    }

    /// All (relation_index, position) pairs where a rule applies to `word`.
    pub fn applicable(&self, word: &Word) -> Vec<(usize, usize)> {
        let gens = word.generators();
        let mut result = Vec::new();
        for (ri, rel) in self.relations.iter().enumerate() {
            let src = rel.source.generators();
            if src.is_empty() || src.len() > gens.len() {
                continue;
            }
            for start in 0..=(gens.len() - src.len()) {
                if &gens[start..start + src.len()] == src {
                    result.push((ri, start));
                }
            }
        }
        result
    }

    /// Apply a specific rule at a specific position.
    pub fn apply_at(&self, expr: &Expr, rule_idx: usize, start: usize) -> Expr {
        if rule_idx >= self.relations.len() {
            return expr.clone();
        }
        let rel = &self.relations[rule_idx];
        let src = rel.source.generators();
        let mut result = Expr::zero();
        for (word, coeff) in expr.terms() {
            let gens = word.generators();
            if !src.is_empty()
                && start + src.len() <= gens.len()
                && &gens[start..start + src.len()] == src
            {
                let prefix = Word::from_gens(&gens[..start]);
                let suffix = Word::from_gens(&gens[start + src.len()..]);
                let pre = Expr::term(*coeff, prefix);
                let suf = Expr::term(Rat::one(), suffix);
                result = result.add(&pre.mul_free(&rel.target).mul_free(&suf));
            } else {
                result = result.add(&Expr::term(*coeff, word.clone()));
            }
        }
        result
    }

    /// Rewrite one term: returns (result, Option<(rule_idx, position)>).
    fn rewrite_word(&self, word: &Word, coeff: Rat) -> (Expr, Option<(usize, usize)>) {
        let gens = word.generators();

        // Fast path: pair index.
        if gens.len() >= 2 {
            for i in 0..gens.len() - 1 {
                let key = (gen_key(gens[i]), gen_key(gens[i + 1]));
                if let Some(&ri) = self.pair_index.get(&key) {
                    let replacement = &self.relations[ri].target;
                    let prefix = Expr::term(coeff, Word::from_gens(&gens[..i]));
                    let suffix = Expr::term(Rat::one(), Word::from_gens(&gens[i + 2..]));
                    return (
                        prefix.mul_free(replacement).mul_free(&suffix),
                        Some((ri, i)),
                    );
                }
            }
        }

        // General path.
        for (ri, rel) in self.relations.iter().enumerate() {
            if rel.source.grade() > gens.len() {
                continue;
            }
            if let Some(pos) = word.find_subword(&rel.source) {
                let src_len = rel.source.grade();
                let prefix = Expr::term(coeff, Word::from_gens(&gens[..pos]));
                let suffix = Expr::term(Rat::one(), Word::from_gens(&gens[pos + src_len..]));
                return (
                    prefix.mul_free(&rel.target).mul_free(&suffix),
                    Some((ri, pos)),
                );
            }
        }

        (Expr::term(coeff, word.clone()), None)
    }

    /// Canonicalize to fixed point.
    /// NOTE: trace.converged means "fixed point under current firing strategy."
    /// Uniqueness requires confluence verification — see explore_confluence.
    pub fn canonicalize(&self, expr: &Expr) -> Expr {
        let mut current = expr.clone();
        let mut changed = true;
        let mut iters = 0usize;
        const MAX: usize = 1000;
        while changed && iters < MAX {
            changed = false;
            iters += 1;
            let mut next = Expr::zero();
            for (word, coeff) in current.terms() {
                let (r, fired) = self.rewrite_word(word, *coeff);
                next = next.add(&r);
                if fired.is_some() {
                    changed = true;
                }
            }
            current = next;
        }
        current
    }

    /// Canonicalize with full trace recording.
    pub fn canonicalize_traced(&self, expr: &Expr) -> (Expr, Trace) {
        let mut current = expr.clone();
        let mut steps = Vec::new();
        let mut changed = true;
        let mut iters = 0usize;
        const MAX: usize = 1000;

        while changed && iters < MAX {
            changed = false;
            iters += 1;
            let mut next = Expr::zero();
            let mut applicable_all: Vec<(usize, usize)> = Vec::new();
            let mut fired_this: Option<(usize, usize)> = None;

            for (word, coeff) in current.terms() {
                for p in self.applicable(word) {
                    if !applicable_all.contains(&p) {
                        applicable_all.push(p);
                    }
                }
                let (r, fired) = self.rewrite_word(word, *coeff);
                if fired.is_some() && fired_this.is_none() {
                    fired_this = fired;
                }
                next = next.add(&r);
            }

            if next != current {
                steps.push(TraceStep {
                    iteration: iters,
                    before: current.clone(),
                    after: next.clone(),
                    applicable: applicable_all,
                    fired: fired_this,
                });
                changed = true;
                current = next;
            }
        }

        let trace = Trace {
            steps,
            input: expr.clone(),
            output: current.clone(),
            iterations: iters,
            converged: !changed,
        };
        (current, trace)
    }

    /// The governed product: free product then canonicalize.
    pub fn mul(&self, a: &Expr, b: &Expr) -> Expr {
        self.canonicalize(&a.mul_free(b))
    }
}

/// One step in a canonicalization trace.
#[derive(Clone, PartialEq, Eq)]
pub struct TraceStep {
    pub iteration: usize,
    pub before: Expr,
    pub after: Expr,
    pub applicable: Vec<(usize, usize)>,
    pub fired: Option<(usize, usize)>,
}

impl std::fmt::Debug for TraceStep {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "[{}] {} → {} (fired:{:?}, {}app)",
            self.iteration,
            self.before,
            self.after,
            self.fired,
            self.applicable.len()
        )
    }
}

/// The complete canonicalization trace.
#[derive(Clone, PartialEq, Eq)]
pub struct Trace {
    pub steps: Vec<TraceStep>,
    pub input: Expr,
    pub output: Expr,
    pub iterations: usize,
    pub converged: bool,
}

impl Trace {
    pub fn num_steps(&self) -> usize {
        self.steps.len()
    }
    pub fn is_trivial(&self) -> bool {
        self.steps.is_empty()
    }
}

impl std::fmt::Debug for Trace {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "Trace({} steps, {})",
            self.steps.len(),
            if self.converged {
                "converged"
            } else {
                "hit MAX_ITER"
            }
        )
    }
}

impl std::fmt::Debug for Governance {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "Governance({} relations)", self.relations.len())
    }
}

// ── Tests ─────────────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::*;

    fn ei(i: u32) -> Gen {
        Gen::imaginary(i)
    }
    fn ed(i: u32) -> Gen {
        Gen::degenerate(i)
    }
    fn eh(i: u32) -> Gen {
        Gen::hyperbolic(i)
    }

    #[test]
    fn signature_is_one_field_access() {
        let gov = Governance::free();
        // signature() = gen.sig. No lookup. Always correct.
        assert_eq!(gov.signature(ei(0)), N);
        assert_eq!(gov.signature(ed(0)), Z);
        assert_eq!(gov.signature(eh(0)), P);
    }

    #[test]
    fn signature_relational() {
        // Same index, different type → different signature.
        // Type is in Gen, not in the governance lookup.
        let gov = Governance::free();
        assert_ne!(gov.signature(ei(0)), gov.signature(eh(0)));
    }

    #[test]
    fn cl100_imaginary_square() {
        let gov = Governance::cl(1, 0, 0);
        let e1 = Expr::gen(ei(0));
        assert_eq!(gov.mul(&e1, &e1), Expr::int(-1));
    }

    #[test]
    fn cl010_degenerate_square() {
        let gov = Governance::cl(0, 1, 0);
        let e1 = Expr::gen(ed(0));
        assert!(gov.mul(&e1, &e1).is_zero());
    }

    #[test]
    fn cl001_hyperbolic_square() {
        let gov = Governance::cl(0, 0, 1);
        let e1 = Expr::gen(eh(0));
        assert_eq!(gov.mul(&e1, &e1), Expr::int(1));
    }

    #[test]
    fn cl200_anticommute() {
        let gov = Governance::cl(2, 0, 0);
        let e1 = Expr::gen(ei(0));
        let e2 = Expr::gen(ei(1));
        // e2·e1 → -e1·e2
        let e2e1 = gov.mul(&e2, &e1);
        assert_eq!(
            e2e1.coeff(&Word::from_gens(&[ei(0), ei(1)])),
            Rat::neg_one()
        );
    }

    #[test]
    fn cl200_vector_square() {
        let gov = Governance::cl(2, 0, 0);
        let v = Expr::gen(ei(0)).add(&Expr::gen(ei(1)));
        assert_eq!(gov.mul(&v, &v), Expr::int(-2));
    }

    #[test]
    fn cl300_pseudoscalar_square() {
        // In Cl(3,0,0): I = e1·e2·e3, I² = +1
        let gov = Governance::cl(3, 0, 0);
        let e1 = Expr::gen(ei(0));
        let e2 = Expr::gen(ei(1));
        let e3 = Expr::gen(ei(2));
        let i = gov.mul(&gov.mul(&e1, &e2), &e3);
        assert_eq!(gov.mul(&i, &i), Expr::int(1));
    }

    #[test]
    fn trace_records_fired() {
        let gov = Governance::cl(1, 0, 0);
        let e1e1 = Expr::term(Rat::one(), Word::from_gens(&[ei(0), ei(0)]));
        let (result, trace) = gov.canonicalize_traced(&e1e1);
        assert_eq!(result, Expr::int(-1));
        assert!(!trace.steps.is_empty());
        assert!(trace.steps[0].fired.is_some());
    }

    #[test]
    fn trace_applicable_superset_of_fired() {
        let gov = Governance::cl(2, 0, 0);
        let w = Expr::term(Rat::one(), Word::from_gens(&[ei(1), ei(0), ei(0)]));
        let (_, trace) = gov.canonicalize_traced(&w);
        if let Some(step) = trace.steps.first() {
            if let Some(fired) = step.fired {
                assert!(step.applicable.contains(&fired));
            }
        }
    }

    #[test]
    fn clifford_typed_generators() {
        // Build a mixed algebra directly from typed generators.
        let gens = vec![Gen::imaginary(0), Gen::degenerate(0), Gen::hyperbolic(0)];
        let gov = Governance::clifford(&gens);
        assert_eq!(gov.mul(&Expr::gen(ei(0)), &Expr::gen(ei(0))), Expr::int(-1));
        assert!(gov.mul(&Expr::gen(ed(0)), &Expr::gen(ed(0))).is_zero());
        assert_eq!(gov.mul(&Expr::gen(eh(0)), &Expr::gen(eh(0))), Expr::int(1));
    }
}