neberu 0.0.0

// ============================================================
// ENCODING — TRIT-WORD ENCODING OF TRACE OBJECTS
// ============================================================
//
// From the axiom derivation:
//   TraceGen  = Word in Magma<Trit>
//   TraceWalk = Expr in the free algebra over that word
//   KotResult = grade-3 word [minimal, complete, consistent] as Trits
//
// This module is the bridge between the Rust struct world and
// the from-axiom Magma<Trit> world. When Session 004 closes,
// this module becomes .neb governance. Until then, it is Rust.
//
// INV is the separator. The same sentinel that catches invalid
// states also delimits structure in the Trit-word encoding.
// This is not a coincidence.

use crate::expr::Expr;
use crate::gen::Gen;
use crate::governance::{Governance, Relation};
use crate::rat::Rat;
use crate::trace::{KotResult, TraceGen, TraceWalk};
use crate::trit::{Trit, INV, N, P, Z};
use crate::word::Word;

// ── TraceGen → Word in Magma<Trit> ───────────────────────────────────────────

/// Encode a TraceGen as a Word in Magma<Trit>.
///
/// Encoding: [P × rule_idx] INV [P × start] INV [matched generator types]
///
/// The INV sentinel is the separator. It cannot appear in any of the
/// three fields (rule_idx and start use only P; matched uses N/Z/P).
/// Therefore INV is unambiguous as a delimiter.
///
/// This is the from-axiom encoding — no integers, no structs,
/// only Trits and the free monoid over them.
pub fn tracegen_to_word(tg: &TraceGen) -> Word {
    let mut trits: Vec<Trit> = Vec::new();

    // Field 1: rule index as unary count of P-trits
    trits.extend(std::iter::repeat_n(P, tg.rule_idx));

    // Separator 1
    trits.push(INV);

    // Field 2: start position as unary count of P-trits
    trits.extend(std::iter::repeat_n(P, tg.start));

    // Separator 2
    trits.push(INV);

    // Field 3: matched generator types (their Trit signatures)
    for g in tg.matched.generators() {
        trits.push(g.sig);
    }

    // Build a Word over Gen where each Gen encodes a Trit.
    // We use the Trit value as the generator signature,
    // with a fixed index 0. The index is structurally irrelevant here —
    // what matters is the type (sig), not the address (idx).
    let gens: Vec<Gen> = trits.iter().map(|&t| Gen { sig: t, idx: 0 }).collect();
    Word::from_gens(&gens)
}

/// Decode a Trit-word back into a TraceGen.
/// Returns None if the word is malformed (wrong separator structure).
pub fn word_to_tracegen(word: &Word) -> Option<TraceGen> {
    let gens = word.generators();

    // Find the two INV separators
    let sep1 = gens.iter().position(|g| g.sig == INV)?;
    let sep2 = gens[sep1 + 1..]
        .iter()
        .position(|g| g.sig == INV)
        .map(|i| i + sep1 + 1)?;

    // Field 1: P-trits before first separator
    let rule_idx = gens[..sep1].iter().filter(|g| g.sig == P).count();
    if gens[..sep1].iter().any(|g| g.sig != P) {
        return None;
    }

    // Field 2: P-trits between separators
    let start = gens[sep1 + 1..sep2].iter().filter(|g| g.sig == P).count();
    if gens[sep1 + 1..sep2].iter().any(|g| g.sig != P) {
        return None;
    }

    // Field 3: matched generator types after second separator
    let matched_gens: Vec<Gen> = gens[sep2 + 1..]
        .iter()
        .map(|g| Gen { sig: g.sig, idx: 0 })
        .collect();
    let matched = Word::from_gens(&matched_gens);

    Some(TraceGen::new(rule_idx, start, matched))
}

// ── TraceWalk → Expr ─────────────────────────────────────────────────────────

/// Encode a TraceWalk as an Expr in the free algebra over Magma<Trit>.
///
/// Each step becomes one term: coefficient 1, word = tracegen_to_word(step).
/// The walk is a linear combination of step-words.
///
/// An empty walk encodes as Expr::zero() — the additive identity.
/// A one-step walk encodes as a single term.
/// A k-step walk encodes as a sum of k terms.
pub fn tracewalk_to_expr(tw: &TraceWalk) -> Expr {
    let mut result = Expr::zero();
    for step in tw.steps() {
        let word = tracegen_to_word(step);
        result = result.add(&Expr::term(Rat::one(), word));
    }
    result
}

// ── KotResult → Expr ─────────────────────────────────────────────────────────

/// Encode a KotResult as an Expr in Magma<Trit>.
///
/// The certificate is a grade-3 word of Trits encoding the three properties:
///   [minimal_trit, complete_trit, consistent_trit]
///
/// Where: P = property holds, N = property fails, Z = not checked.
///
/// The coefficient of the term:
///   +1 (Rat::one())  if the overall verdict is P (optimal)
///   -1 (Rat::neg_one()) if the verdict is N (not optimal)
///
/// This encoding makes the certificate a single term in Magma<Trit>.
/// Running KOT on this term (as an Expr) under the Q₂ governance
/// checks that all three Trits are P — that the certificate is valid.
pub fn kot_result_to_expr(kr: &KotResult) -> Expr {
    let minimal_trit = if kr.minimal { P } else { N };
    let complete_trit = if kr.complete { P } else { N };
    let consistent_trit = if kr.consistent { P } else { N };

    let gens = vec![
        Gen {
            sig: minimal_trit,
            idx: 0,
        },
        Gen {
            sig: complete_trit,
            idx: 1,
        },
        Gen {
            sig: consistent_trit,
            idx: 2,
        },
    ];

    // Always coefficient +1. The verdict is encoded in the Trits themselves:
    // [P,P,P] = optimal, any N = failure. Q₂ governance reads the word.
    // Using verdict as coefficient caused double-negation (N·N=P), wrong.
    Expr::term(Rat::one(), Word::from_gens(&gens))
}

// ── Q₂ Governance ────────────────────────────────────────────────────────────

/// Build the Q₂ governance: checks that a KOT certificate word is all-P.
///
/// The governance has one relation:
///   Word([P, P, P]) → Expr::scalar(P_trit_as_rat)
///
/// Under this governance, a certificate of [P, P, P] rewrites to the
/// scalar 1 (positive). A certificate with any N reduces differently.
///
/// The Q₂ verdict: if the certificate expr canonicalizes to a positive
/// scalar under this governance, Q₂ = P (the certificate is correctly certified).
///
/// SELF-HOSTING BOUNDARY:
/// This governance will be expressed in std/kot.neb (Session 004).
/// The relation "all-P grade-3 word → P" is the KOT optimality rule.
pub fn q2_governance() -> Governance {
    // The passing certificate: [P, P, P] → +1 (P as scalar)
    let passing_cert = Word::from_gens(&[
        Gen { sig: P, idx: 0 },
        Gen { sig: P, idx: 1 },
        Gen { sig: P, idx: 2 },
    ]);
    // Any certificate with a failing property maps to -1 (N as scalar).
    // We enumerate all 2³=8 combinations, only [P,P,P] maps to +1.
    let mut gov = Governance::free().with_relation(Relation::new(passing_cert, Expr::int(1)));

    // All other grade-3 combinations with at least one N → map to -1.
    for m in [P, N] {
        for c in [P, N] {
            for s in [P, N] {
                if m == P && c == P && s == P {
                    continue;
                } // already handled
                let word = Word::from_gens(&[
                    Gen { sig: m, idx: 0 },
                    Gen { sig: c, idx: 1 },
                    Gen { sig: s, idx: 2 },
                ]);
                gov = gov.with_relation(Relation::new(word, Expr::int(-1)));
            }
        }
    }
    gov
}

/// Compute Q₂: run the Q₂ governance on a KotResult.
/// Returns P if the certificate is correctly certified, N if not.
pub fn compute_q2(kr: &KotResult) -> Trit {
    let cert_expr = kot_result_to_expr(kr);
    let gov = q2_governance();
    let canonical = gov.canonicalize(&cert_expr);
    match canonical.as_scalar() {
        Some(r) => r.sign(),
        None => Z, // indeterminate
    }
}

// ── Exact integer packing ─────────────────────────────────────────────────────

/// Pack a Word of Trit-typed generators into a u128.
/// Trit i occupies bits [2i+1 : 2i].  Same layout as Tern.
pub fn pack_word(word: &Word) -> u128 {
    let mut result = 0u128;
    for (i, g) in word.generators().iter().enumerate() {
        result |= (g.sig.bits() as u128) << (i * 2);
    }
    result
}

/// Pack all TraceGen words in a walk into one u128 (concatenated).
/// Returns (packed_value, total_bits).
pub fn pack_walk(walk: &TraceWalk) -> (u128, usize) {
    let mut result = 0u128;
    let mut offset = 0usize;
    for step in walk.steps() {
        let word = tracegen_to_word(step);
        let val = pack_word(&word);
        let bits = word.grade() * 2;
        result |= val << offset;
        offset += bits;
    }
    (result, offset)
}

/// Pack all governance source words (concatenated) into a u128.
/// Returns (packed_value, total_bits).
pub fn pack_governance_sources(gov: &Governance) -> (u128, usize) {
    let mut result = 0u128;
    let mut offset = 0usize;
    for rel in gov.relations() {
        let val = pack_word(&rel.source);
        let bits = rel.source.grade() * 2;
        result |= val << offset;
        offset += bits;
    }
    (result, offset)
}

/// Concatenate N₁ and N₂ into the complete N₃ certificate as bytes.
pub fn certificate_bytes(n1_val: u128, n1_bits: usize, n2_val: u128, n2_bits: usize) -> Vec<u8> {
    let total_bits = n1_bits + n2_bits;
    let total_bytes = total_bits.div_ceil(8);
    let combined: u128 = n1_val | (n2_val << n1_bits);
    let mut bytes = Vec::with_capacity(total_bytes);
    for i in 0..total_bytes {
        bytes.push(((combined >> (i * 8)) & 0xFF) as u8);
    }
    bytes
}

/// Format a u128 as a hex string with the exact number of bytes.
pub fn fmt_hex(val: u128, bits: usize) -> String {
    let bytes = bits.div_ceil(8);
    format!(
        "0x{:0>width$X}",
        val & ((1u128 << bits) - 1),
        width = bytes * 2
    )
}

/// Format a u128 as a bit string, space-separated pairs.
pub fn fmt_bits(val: u128, bits: usize) -> String {
    // LSB-first: trit 0 on the left, matching the logical Trit ordering.
    // Each pair of bits is one trit: trit 0 shown first.
    (0..bits)
        .step_by(2)
        .map(|i| format!("{:02b}", (val >> i) & 0b11))
        .collect::<Vec<_>>()
        .join(" ")
}

// ── Trit-word display ─────────────────────────────────────────────────────────

/// Display a Word of Trit-typed generators as their Trit symbols.
/// `[P·P·P]` not `e1·e1·e1·e1`.
/// Reveals the Trit structure rather than the generator address.
pub fn trit_word_display(word: &Word) -> String {
    if word.is_scalar() {
        return "1".to_string();
    }
    let syms: Vec<&str> = word
        .generators()
        .iter()
        .map(|g| match g.sig {
            P => "P",
            N => "N",
            Z => "Z",
            INV => "INV",
            _ => "?",
        })
        .collect();
    format!("[{}]", syms.join("·"))
}

/// Display an Expr where each Word is shown as a Trit-word.
pub fn trit_expr_display(expr: &Expr) -> String {
    if expr.is_zero() {
        return "0".to_string();
    }
    let mut parts = Vec::new();
    for (word, coeff) in expr.terms() {
        let word_str = trit_word_display(word);
        if coeff.is_one() {
            parts.push(word_str);
        } else if *coeff == crate::rat::Rat::neg_one() {
            parts.push(format!("-{}", word_str));
        } else {
            parts.push(format!("{}·{}", coeff, word_str));
        }
    }
    parts.join(" + ")
}

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

#[cfg(test)]
mod tests {
    use super::*;
    use crate::governance::Governance;
    use crate::trace::{verify_kot, walk_from_trace};

    fn ei(i: u32) -> Gen {
        Gen::imaginary(i)
    }

    #[test]
    fn tracegen_roundtrip_zero_zero_matched_nn() {
        // Rule 0, start 0, matched=[N,N]
        let tg = TraceGen::new(0, 0, Word::from_gens(&[ei(0), ei(0)]));
        let word = tracegen_to_word(&tg);
        // Expected: INV INV N N (rule=empty, sep, start=empty, sep, matched=[N,N])
        assert_eq!(word.grade(), 4);
        let gens = word.generators();
        assert_eq!(gens[0].sig, INV); // sep 1
        assert_eq!(gens[1].sig, INV); // sep 2
        assert_eq!(gens[2].sig, N); // matched[0]
        assert_eq!(gens[3].sig, N); // matched[1]
    }

    #[test]
    fn tracegen_encode_decode_roundtrip() {
        let tg_orig = TraceGen::new(2, 3, Word::from_gens(&[ei(0), Gen::hyperbolic(0)]));
        let word = tracegen_to_word(&tg_orig);
        let tg_decoded = word_to_tracegen(&word).unwrap();
        assert_eq!(tg_decoded.rule_idx, 2);
        assert_eq!(tg_decoded.start, 3);
        assert_eq!(tg_decoded.matched.grade(), 2);
        assert_eq!(tg_decoded.matched.generators()[0].sig, N);
        assert_eq!(tg_decoded.matched.generators()[1].sig, P);
    }

    #[test]
    fn tracegen_rule3_start2_encodes_correctly() {
        // Rule 3 → [P P P], start 2 → [P P], matched=[P] (hyperbolic)
        // Full: [P P P] INV [P P] INV [P] = 8 trits
        let tg = TraceGen::new(3, 2, Word::from_gens(&[Gen::hyperbolic(0)]));
        let word = tracegen_to_word(&tg);
        assert_eq!(word.grade(), 8);
        let g = word.generators();
        // First 3 are P (rule index)
        assert!(g[..3].iter().all(|x| x.sig == P));
        assert_eq!(g[3].sig, INV); // sep 1
                                   // Next 2 are P (start)
        assert!(g[4..6].iter().all(|x| x.sig == P));
        assert_eq!(g[6].sig, INV); // sep 2
                                   // Last is P (hyperbolic)
        assert_eq!(g[7].sig, P);
    }

    #[test]
    fn tracewalk_empty_encodes_as_zero() {
        use crate::trace::TraceWalk;
        let walk = TraceWalk::empty();
        let expr = tracewalk_to_expr(&walk);
        assert!(expr.is_zero());
    }

    #[test]
    fn tracewalk_one_step_encodes_as_one_term() {
        use crate::trace::TraceWalk;
        let tg = TraceGen::new(0, 0, Word::from_gens(&[ei(0), ei(0)]));
        let walk = TraceWalk::singleton(tg);
        let expr = tracewalk_to_expr(&walk);
        assert_eq!(expr.num_terms(), 1);
        // The term has coefficient 1
        let (_, coeff) = expr.terms().next().unwrap();
        assert_eq!(*coeff, Rat::one());
    }

    #[test]
    fn kot_passing_encodes_as_ppp() {
        let kr = KotResult {
            minimal: true,
            complete: true,
            consistent: true,
            witnesses: vec![],
        };
        let expr = kot_result_to_expr(&kr);
        assert_eq!(expr.num_terms(), 1);
        let (word, coeff) = expr.terms().next().unwrap();
        assert_eq!(*coeff, Rat::one());
        assert_eq!(word.grade(), 3);
        assert!(word.generators().iter().all(|g| g.sig == P));
    }

    #[test]
    fn kot_failing_consistency_encodes_with_n() {
        let kr = KotResult {
            minimal: true,
            complete: true,
            consistent: false,
            witnesses: vec!["test".to_string()],
        };
        let expr = kot_result_to_expr(&kr);
        let (word, coeff) = expr.terms().next().unwrap();
        // Coefficient is always +1 — the verdict is in the Trits, not the coefficient.
        assert_eq!(*coeff, Rat::one());
        // The consistent trit (position 2) should be N (failed)
        assert_eq!(word.generators()[2].sig, N);
    }

    #[test]
    fn q2_passing_cert_gives_p() {
        // A passing KotResult should produce Q₂ = P
        let kr = KotResult {
            minimal: true,
            complete: true,
            consistent: true,
            witnesses: vec![],
        };
        assert_eq!(compute_q2(&kr), P);
    }

    #[test]
    fn q2_failing_cert_gives_n() {
        // A failing KotResult should produce Q₂ = N
        let kr = KotResult {
            minimal: false,
            complete: true,
            consistent: true,
            witnesses: vec![],
        };
        assert_eq!(compute_q2(&kr), N);
    }

    #[test]
    fn q2_for_cl100_e1e1_gives_p() {
        // Full integration: e1*e1 in Cl(1,0,0)
        // Q₁ = P (optimal canonicalization)
        // Q₂ = P (the certificate is correctly certified)
        let gov = Governance::cl(1, 0, 0);
        let source = Expr::term(Rat::one(), Word::from_gens(&[ei(0), ei(0)]));
        let (_, trace) = gov.canonicalize_traced(&source);
        let walk = walk_from_trace(&trace, &gov);
        let kr = verify_kot(&walk, &source, &gov);
        assert_eq!(kr.as_trit(), P, "Q₁ must be P");
        assert_eq!(compute_q2(&kr), P, "Q₂ must be P");
    }

    #[test]
    fn q2_self_reference_fixed_point() {
        // Q₁ = P and Q₂ = P — the fixed point of self-certification.
        // Applying Q once more should still give P.
        let kr = KotResult {
            minimal: true,
            complete: true,
            consistent: true,
            witnesses: vec![],
        };
        let q2 = compute_q2(&kr);
        // Build a KotResult for Q₂ itself (it's just another passing cert)
        let kr2 = KotResult {
            minimal: true,
            complete: true,
            consistent: (q2 == P),
            witnesses: vec![],
        };
        let q3 = compute_q2(&kr2);
        assert_eq!(q2, P);
        assert_eq!(q3, P);
        // Fixed point confirmed: P → P → P ...
    }
}