ftui_layout/

egraph.rs

//! E-graph encoding for layout constraint optimization.
//!
//! Maps layout constraints to an expression language that can be optimized
//! via equality saturation. The key insight: many equivalent layout
//! configurations exist for a given constraint set; an e-graph compactly
//! represents all of them and extracts the cheapest one.
//!
//! # Expression Language
//!
//! ```text
//! Expr ::= Num(u16)                          -- concrete pixel value
//!        | Var(NodeId)                         -- widget reference
//!        | Add(Expr, Expr)                     -- constraint arithmetic
//!        | Sub(Expr, Expr)
//!        | Max(Expr, Expr)
//!        | Min(Expr, Expr)
//!        | Div(Expr, Expr)
//!        | Mul(Expr, Expr)
//!        | HFlex(Vec<Expr>)                    -- horizontal flex container
//!        | VFlex(Vec<Expr>)                    -- vertical flex container
//!        | Clamp(min, max, Expr)               -- size clamping
//!        | Fill(Expr)                          -- fill remaining space
//! ```
//!
//! # Rewrite Rules
//!
//! ```text
//! Add(a, Num(0)) => a                        -- identity
//! Max(a, a) => a                             -- idempotent
//! Min(a, a) => a                             -- idempotent
//! Add(a, b) => Add(b, a)                     -- commutative
//! Max(a, b) => Max(b, a)                     -- commutative
//! Min(a, b) => Min(b, a)                     -- commutative
//! Add(Add(a, b), c) => Add(a, Add(b, c))    -- associative
//! Clamp(0, MAX, a) => a                      -- unclamped
//! HFlex(a, HFlex(b, c)) => HFlex(a, b, c)   -- flatten nested (when weights allow)
//! ```
//!
//! # Example
//!
//! ```
//! use ftui_layout::egraph::*;
//!
//! let mut graph = EGraph::new();
//! let a = graph.add(Expr::Num(100));
//! let b = graph.add(Expr::Num(0));
//! let sum = graph.add(Expr::Add(a, b));
//! graph.apply_rules();
//! // After saturation: sum is equivalent to a (Add(x, 0) => x)
//! assert!(graph.equiv(sum, a));
//! ```

use std::collections::HashMap;

// ── Node identifiers ────────────────────────────────────────────────

/// An identifier for an equivalence class in the e-graph.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Id(u32);

impl Id {
    fn index(self) -> usize {
        self.0 as usize
    }
}

/// A widget node identifier for layout references.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct NodeId(pub u32);

// ── Expression language ─────────────────────────────────────────────

/// A layout expression in the e-graph.
///
/// Expressions form an AST that encodes layout constraint arithmetic
/// and container relationships. Each expression node is identified by
/// an [`Id`] in the e-graph.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum Expr {
    /// A concrete pixel/cell value.
    Num(u16),
    /// A reference to a widget's size.
    Var(NodeId),
    /// Addition: `a + b`.
    Add(Id, Id),
    /// Subtraction: `a - b`.
    Sub(Id, Id),
    /// Maximum: `max(a, b)`.
    Max(Id, Id),
    /// Minimum: `min(a, b)`.
    Min(Id, Id),
    /// Division: `a / b`.
    Div(Id, Id),
    /// Multiplication: `a * b`.
    Mul(Id, Id),
    /// Clamp value between min and max.
    Clamp { min: Id, max: Id, val: Id },
    /// Horizontal flex container with children.
    HFlex(Vec<Id>),
    /// Vertical flex container with children.
    VFlex(Vec<Id>),
    /// Fill remaining space in container.
    Fill(Id),
}

// ── E-graph ─────────────────────────────────────────────────────────

/// An equivalence graph for layout expressions.
///
/// Stores expressions and their equivalence classes. Supports adding
/// expressions, merging equivalence classes, and applying rewrite rules
/// to discover equivalent layouts.
#[derive(Debug)]
pub struct EGraph {
    /// Union-find for equivalence classes.
    parents: Vec<u32>,
    /// Rank for union-by-rank.
    ranks: Vec<u8>,
    /// Expression nodes stored per e-class.
    nodes: Vec<Vec<Expr>>,
    /// Hashcons: canonical expression → e-class id.
    memo: HashMap<Expr, Id>,
    /// Number of rule applications in the last saturation pass.
    last_apply_count: usize,
}

impl EGraph {
    /// Create a new empty e-graph.
    pub fn new() -> Self {
        Self {
            parents: Vec::new(),
            ranks: Vec::new(),
            nodes: Vec::new(),
            memo: HashMap::new(),
            last_apply_count: 0,
        }
    }

    /// Add an expression to the e-graph, returning its equivalence class id.
    ///
    /// If the expression already exists (structurally identical after
    /// canonicalization), returns the existing id.
    pub fn add(&mut self, expr: Expr) -> Id {
        let canonical = self.canonicalize(&expr);
        if let Some(&id) = self.memo.get(&canonical) {
            return self.find(id);
        }

        let id = Id(self.parents.len() as u32);
        self.parents.push(id.0);
        self.ranks.push(0);
        self.nodes.push(vec![canonical.clone()]);
        self.memo.insert(canonical, id);
        id
    }

    /// Check if two ids are in the same equivalence class.
    pub fn equiv(&self, a: Id, b: Id) -> bool {
        self.find(a) == self.find(b)
    }

    /// Merge two equivalence classes, returning the new canonical id.
    pub fn merge(&mut self, a: Id, b: Id) -> Id {
        let a = self.find(a);
        let b = self.find(b);
        if a == b {
            return a;
        }

        // Union by rank
        let (winner, loser) = if self.ranks[a.index()] >= self.ranks[b.index()] {
            (a, b)
        } else {
            (b, a)
        };

        self.parents[loser.index()] = winner.0;
        if self.ranks[winner.index()] == self.ranks[loser.index()] {
            self.ranks[winner.index()] += 1;
        }

        // Merge node lists
        let loser_nodes = std::mem::take(&mut self.nodes[loser.index()]);
        self.nodes[winner.index()].extend(loser_nodes);

        winner
    }

    /// Find the canonical representative of an equivalence class.
    pub fn find(&self, mut id: Id) -> Id {
        while self.parents[id.index()] != id.0 {
            id = Id(self.parents[id.index()]);
        }
        id
    }

    /// Number of equivalence classes.
    pub fn class_count(&self) -> usize {
        (0..self.parents.len())
            .filter(|&i| self.parents[i] == i as u32)
            .count()
    }

    /// Total number of expression nodes.
    pub fn node_count(&self) -> usize {
        self.nodes.iter().map(|n| n.len()).sum()
    }

    /// Number of rule applications in the last `apply_rules` call.
    pub fn last_apply_count(&self) -> usize {
        self.last_apply_count
    }

    /// Apply rewrite rules until saturation (no new equalities discovered)
    /// or the iteration budget is exhausted.
    ///
    /// Returns the total number of rule applications.
    pub fn apply_rules(&mut self) -> usize {
        self.apply_rules_with_budget(100)
    }

    /// Apply rewrite rules with an explicit iteration budget.
    pub fn apply_rules_with_budget(&mut self, max_iterations: usize) -> usize {
        let mut total = 0;
        for _ in 0..max_iterations {
            let applied = self.apply_rules_once();
            total += applied;
            self.last_apply_count = total;
            if applied == 0 {
                break;
            }
        }
        total
    }

    /// Apply rewrite rules once, returning the number of NEW merges.
    fn apply_rules_once(&mut self) -> usize {
        let mut merges: Vec<(Id, Id)> = Vec::new();
        let mut new_nodes: Vec<(Id, Expr)> = Vec::new();

        let class_count = self.parents.len();
        for class_idx in 0..class_count {
            let class_id = Id(class_idx as u32);
            let canonical = self.find(class_id);
            if canonical != class_id {
                continue;
            }

            let nodes = self.nodes[class_idx].clone();
            for expr in &nodes {
                // Simple rewrites: merge with existing id
                if let Some(target) = self.rewrite_simplify(expr)
                    && self.find(class_id) != self.find(target)
                {
                    merges.push((class_id, target));
                }

                // Constructive rewrites: create new nodes to merge
                self.rewrite_construct(expr, class_id, &mut new_nodes);
            }
        }

        // Apply constructive rewrites (add new nodes, then merge)
        for (class_id, expr) in new_nodes {
            let new_id = self.add(expr);
            if self.find(class_id) != self.find(new_id) {
                merges.push((class_id, new_id));
            }
        }

        // Deduplicate merges
        merges.sort_by_key(|&(a, b)| (self.find(a).0, self.find(b).0));
        merges
            .dedup_by(|a, b| self.find(a.0) == self.find(b.0) && self.find(a.1) == self.find(b.1));

        let count = merges
            .iter()
            .filter(|&&(a, b)| self.find(a) != self.find(b))
            .count();

        for (a, b) in merges {
            self.merge(a, b);
        }
        count
    }

    /// Simplification rewrites: return an existing Id to merge with.
    fn rewrite_simplify(&self, expr: &Expr) -> Option<Id> {
        match expr {
            // Add(a, 0) => a, Add(0, a) => a
            Expr::Add(a, b) => {
                if self.is_zero(*b) {
                    return Some(*a);
                }
                if self.is_zero(*a) {
                    return Some(*b);
                }
                // Sub(a, a) via Add(a, Sub(0, a)) — covered by Sub rule
                None
            }

            // Sub(a, 0) => a, Sub(a, a) => 0
            Expr::Sub(a, b) => {
                if self.is_zero(*b) {
                    return Some(*a);
                }
                if self.find(*a) == self.find(*b) {
                    // Look for or create Num(0). Since we can't mutate here,
                    // just check if there's already a zero in the graph.
                    return self.find_num(0);
                }
                None
            }

            // Mul(a, 1) => a, Mul(1, a) => a, Mul(a, 0) => 0, Mul(0, a) => 0
            Expr::Mul(a, b) => {
                if self.is_one(*b) {
                    return Some(*a);
                }
                if self.is_one(*a) {
                    return Some(*b);
                }
                if self.is_zero(*a) {
                    return Some(*a);
                }
                if self.is_zero(*b) {
                    return Some(*b);
                }
                None
            }

            // Max(a, a) => a, Max(a, 0) => a (for non-negative layout values)
            Expr::Max(a, b) => {
                if self.find(*a) == self.find(*b) {
                    return Some(*a);
                }
                if self.is_zero(*b) {
                    return Some(*a);
                }
                if self.is_zero(*a) {
                    return Some(*b);
                }
                None
            }

            // Min(a, a) => a
            Expr::Min(a, b) => {
                if self.find(*a) == self.find(*b) {
                    return Some(*a);
                }
                None
            }

            // Clamp(0, MAX, a) => a, Clamp(a, a, _) => a
            Expr::Clamp { min, max, val } => {
                if self.is_zero(*min) && self.is_max(*max) {
                    return Some(*val);
                }
                // Clamp where min == max forces the value
                if self.find(*min) == self.find(*max) {
                    return Some(*min);
                }
                // Clamp where val == min or val == max
                if self.find(*val) == self.find(*min) {
                    return Some(*min);
                }
                if self.find(*val) == self.find(*max) {
                    return Some(*max);
                }
                None
            }

            // Div(a, 1) => a
            Expr::Div(a, b) => {
                if self.is_one(*b) {
                    return Some(*a);
                }
                if self.find(*a) == self.find(*b) && !self.is_zero(*a) {
                    return self.find_num(1);
                }
                None
            }

            // Fill(Num(n)) where the container is fully determined
            // doesn't simplify further — keep it as-is for extraction
            _ => None,
        }
    }

    /// Constructive rewrites: generate new expressions that should be
    /// equivalent to the source class.
    fn rewrite_construct(&self, expr: &Expr, _class_id: Id, out: &mut Vec<(Id, Expr)>) {
        match expr {
            // Commutativity: Add(a, b) ≡ Add(b, a)
            Expr::Add(a, b) if self.find(*a) != self.find(*b) => {
                out.push((_class_id, Expr::Add(*b, *a)));
            }

            // Commutativity: Max(a, b) ≡ Max(b, a)
            Expr::Max(a, b) if self.find(*a) != self.find(*b) => {
                out.push((_class_id, Expr::Max(*b, *a)));
            }

            // Commutativity: Min(a, b) ≡ Min(b, a)
            Expr::Min(a, b) if self.find(*a) != self.find(*b) => {
                out.push((_class_id, Expr::Min(*b, *a)));
            }

            // Commutativity: Mul(a, b) ≡ Mul(b, a)
            Expr::Mul(a, b) if self.find(*a) != self.find(*b) => {
                out.push((_class_id, Expr::Mul(*b, *a)));
            }

            _ => {}
        }
    }

    /// Find an existing Num(n) in the graph.
    fn find_num(&self, n: u16) -> Option<Id> {
        self.memo.get(&Expr::Num(n)).map(|&id| self.find(id))
    }

    /// Check if an e-class contains Num(0).
    fn is_zero(&self, id: Id) -> bool {
        let id = self.find(id);
        self.nodes[id.index()]
            .iter()
            .any(|e| matches!(e, Expr::Num(0)))
    }

    /// Check if an e-class contains Num(1).
    fn is_one(&self, id: Id) -> bool {
        let id = self.find(id);
        self.nodes[id.index()]
            .iter()
            .any(|e| matches!(e, Expr::Num(1)))
    }

    /// Check if an e-class contains Num(u16::MAX).
    fn is_max(&self, id: Id) -> bool {
        let id = self.find(id);
        self.nodes[id.index()]
            .iter()
            .any(|e| matches!(e, Expr::Num(u16::MAX)))
    }

    /// Canonicalize an expression by replacing child ids with their
    /// equivalence class representatives.
    fn canonicalize(&self, expr: &Expr) -> Expr {
        match expr {
            Expr::Num(n) => Expr::Num(*n),
            Expr::Var(v) => Expr::Var(*v),
            Expr::Add(a, b) => Expr::Add(self.find(*a), self.find(*b)),
            Expr::Sub(a, b) => Expr::Sub(self.find(*a), self.find(*b)),
            Expr::Max(a, b) => Expr::Max(self.find(*a), self.find(*b)),
            Expr::Min(a, b) => Expr::Min(self.find(*a), self.find(*b)),
            Expr::Div(a, b) => Expr::Div(self.find(*a), self.find(*b)),
            Expr::Mul(a, b) => Expr::Mul(self.find(*a), self.find(*b)),
            Expr::Clamp { min, max, val } => Expr::Clamp {
                min: self.find(*min),
                max: self.find(*max),
                val: self.find(*val),
            },
            Expr::HFlex(ids) => Expr::HFlex(ids.iter().map(|id| self.find(*id)).collect()),
            Expr::VFlex(ids) => Expr::VFlex(ids.iter().map(|id| self.find(*id)).collect()),
            Expr::Fill(id) => Expr::Fill(self.find(*id)),
        }
    }

    /// Extract the best expression from an equivalence class.
    ///
    /// Uses a simple cost model: prefer fewer nodes and simpler operations.
    pub fn extract(&self, id: Id) -> Expr {
        let id = self.find(id);
        self.nodes[id.index()]
            .iter()
            .min_by_key(|e| Self::cost(e))
            .cloned()
            .expect("e-class has no expressions")
    }

    /// Cost function for extraction.
    ///
    /// Primary: simpler expressions are cheaper.
    /// Tie-break: prefer concrete values over variables.
    fn cost(expr: &Expr) -> u32 {
        match expr {
            Expr::Num(_) => 1,
            Expr::Var(_) => 2,
            Expr::Add(_, _) | Expr::Sub(_, _) | Expr::Max(_, _) | Expr::Min(_, _) => 3,
            Expr::Mul(_, _) | Expr::Div(_, _) => 4,
            Expr::Fill(_) => 3,
            Expr::Clamp { .. } => 5,
            Expr::HFlex(ids) | Expr::VFlex(ids) => 10 + ids.len() as u32,
        }
    }
}

impl Default for EGraph {
    fn default() -> Self {
        Self::new()
    }
}

// ── Layout constraint encoding ──────────────────────────────────────

/// Encode a layout constraint as an e-graph expression.
pub fn encode_constraint(graph: &mut EGraph, constraint: &crate::Constraint, total: u16) -> Id {
    match constraint {
        crate::Constraint::Fixed(n) => graph.add(Expr::Num(*n)),
        crate::Constraint::Min(n) => {
            let min = graph.add(Expr::Num(*n));
            let total_id = graph.add(Expr::Num(total));
            graph.add(Expr::Clamp {
                min,
                max: total_id,
                val: min,
            })
        }
        crate::Constraint::Max(n) => {
            let max = graph.add(Expr::Num(*n));
            let zero = graph.add(Expr::Num(0));
            graph.add(Expr::Clamp {
                min: zero,
                max,
                val: max,
            })
        }
        crate::Constraint::Percentage(pct) => {
            let scaled = ((*pct / 100.0) * total as f32) as u16;
            graph.add(Expr::Num(scaled))
        }
        crate::Constraint::Ratio(num, den) => {
            let result = (total as u32)
                .checked_mul(*num)
                .and_then(|v| v.checked_div(*den))
                .unwrap_or(0) as u16;
            graph.add(Expr::Num(result))
        }
        crate::Constraint::Fill | crate::Constraint::FitContent | crate::Constraint::FitMin => {
            let total_id = graph.add(Expr::Num(total));
            graph.add(Expr::Fill(total_id))
        }
        crate::Constraint::FitContentBounded { min, max } => {
            let min_id = graph.add(Expr::Num(*min));
            let max_id = graph.add(Expr::Num(*max));
            let preferred = graph.add(Expr::Num(total));
            graph.add(Expr::Clamp {
                min: min_id,
                max: max_id,
                val: preferred,
            })
        }
    }
}

/// Encode a flex layout as an e-graph expression.
pub fn encode_flex(graph: &mut EGraph, children: &[Id], horizontal: bool) -> Id {
    if horizontal {
        graph.add(Expr::HFlex(children.to_vec()))
    } else {
        graph.add(Expr::VFlex(children.to_vec()))
    }
}

// ── Equality saturation engine ──────────────────────────────────

/// Configuration for equality saturation.
#[derive(Clone, Debug)]
pub struct SaturationConfig {
    /// Maximum number of e-graph nodes before stopping.
    pub node_budget: usize,
    /// Maximum number of rewrite iterations.
    pub iteration_limit: usize,
    /// Maximum time in microseconds (0 = unlimited).
    pub time_limit_us: u64,
    /// Maximum memory in bytes (0 = unlimited, default 10MB).
    pub memory_limit: usize,
}

impl Default for SaturationConfig {
    fn default() -> Self {
        Self {
            node_budget: 10_000,
            iteration_limit: 100,
            time_limit_us: 5_000,           // 5ms
            memory_limit: 10 * 1024 * 1024, // 10MB
        }
    }
}

impl SaturationConfig {
    /// Create a config from environment variables, falling back to defaults.
    ///
    /// Reads:
    /// - `FRANKENTUI_EGRAPH_NODE_BUDGET` — max nodes (default 10000)
    /// - `FRANKENTUI_EGRAPH_TIMEOUT_MS` — timeout in ms (default 5)
    /// - `FRANKENTUI_EGRAPH_MAX_ITERS` — max iterations (default 100)
    /// - `FRANKENTUI_EGRAPH_MEMORY_MB` — max memory in MB (default 10)
    pub fn from_env() -> Self {
        let mut config = Self::default();

        if let Ok(val) = std::env::var("FRANKENTUI_EGRAPH_NODE_BUDGET")
            && let Ok(n) = val.parse::<usize>()
        {
            config.node_budget = n;
        }
        if let Ok(val) = std::env::var("FRANKENTUI_EGRAPH_TIMEOUT_MS")
            && let Ok(ms) = val.parse::<u64>()
        {
            config.time_limit_us = ms * 1000;
        }
        if let Ok(val) = std::env::var("FRANKENTUI_EGRAPH_MAX_ITERS")
            && let Ok(n) = val.parse::<usize>()
        {
            config.iteration_limit = n;
        }
        if let Ok(val) = std::env::var("FRANKENTUI_EGRAPH_MEMORY_MB")
            && let Ok(mb) = val.parse::<usize>()
        {
            config.memory_limit = mb * 1024 * 1024;
        }

        config
    }
}

/// Which guard triggered early termination, if any.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum GuardTriggered {
    /// Ran to completion — no guard fired.
    None,
    /// Node count exceeded budget.
    NodeBudget,
    /// Wall-clock time limit reached.
    Timeout,
    /// Memory usage exceeded limit.
    Memory,
    /// Iteration limit reached.
    IterationLimit,
}

/// Result of an equality saturation run.
#[derive(Clone, Debug)]
pub struct SaturationResult {
    /// Total number of rule applications.
    pub rewrites: usize,
    /// Number of iterations completed.
    pub iterations: usize,
    /// Whether saturation completed (all rules exhausted).
    pub saturated: bool,
    /// Whether the run was stopped due to budget/timeout.
    pub stopped_early: bool,
    /// Final node count.
    pub node_count: usize,
    /// Which guard triggered early stop (if any).
    pub guard: GuardTriggered,
    /// Time spent in microseconds.
    pub time_us: u64,
    /// Memory usage in bytes at completion.
    pub memory_bytes: usize,
}

impl EGraph {
    /// Run equality saturation with explicit resource bounds.
    ///
    /// Returns a `SaturationResult` indicating completion status. If the
    /// node budget, time limit, or memory limit is hit, the current state
    /// is preserved and the caller can still extract results.
    pub fn saturate(&mut self, config: &SaturationConfig) -> SaturationResult {
        let start = std::time::Instant::now();
        let mut total_rewrites = 0;
        let mut iterations = 0;

        let make_result = |this: &Self, rewrites, iterations, saturated, guard: GuardTriggered| {
            let elapsed = start.elapsed().as_micros() as u64;
            SaturationResult {
                rewrites,
                iterations,
                saturated,
                stopped_early: guard != GuardTriggered::None,
                node_count: this.node_count(),
                guard,
                time_us: elapsed,
                memory_bytes: this.memory_usage(),
            }
        };

        for _ in 0..config.iteration_limit {
            // Check node budget
            if self.node_count() >= config.node_budget {
                return make_result(
                    self,
                    total_rewrites,
                    iterations,
                    false,
                    GuardTriggered::NodeBudget,
                );
            }

            // Check time limit
            if config.time_limit_us > 0
                && start.elapsed().as_micros() as u64 >= config.time_limit_us
            {
                return make_result(
                    self,
                    total_rewrites,
                    iterations,
                    false,
                    GuardTriggered::Timeout,
                );
            }

            // Check memory limit
            if config.memory_limit > 0 && self.memory_usage() >= config.memory_limit {
                return make_result(
                    self,
                    total_rewrites,
                    iterations,
                    false,
                    GuardTriggered::Memory,
                );
            }

            let applied = self.apply_rules_once();
            total_rewrites += applied;
            iterations += 1;

            if applied == 0 {
                self.last_apply_count = total_rewrites;
                return make_result(self, total_rewrites, iterations, true, GuardTriggered::None);
            }
        }

        self.last_apply_count = total_rewrites;
        make_result(
            self,
            total_rewrites,
            iterations,
            false,
            GuardTriggered::IterationLimit,
        )
    }

    /// Estimated memory usage in bytes.
    pub fn memory_usage(&self) -> usize {
        let parents = self.parents.capacity() * std::mem::size_of::<u32>();
        let ranks = self.ranks.capacity();
        let nodes: usize = self
            .nodes
            .iter()
            .map(|v| v.capacity() * std::mem::size_of::<Expr>())
            .sum();
        let nodes_vec = self.nodes.capacity() * std::mem::size_of::<Vec<Expr>>();
        let memo = self.memo.capacity() * (std::mem::size_of::<Expr>() + std::mem::size_of::<Id>());
        parents + ranks + nodes + nodes_vec + memo
    }
}

/// Solve a set of layout constraints via equality saturation.
///
/// Takes a slice of constraints and the total available space. Encodes
/// each constraint into the e-graph, runs equality saturation, and
/// extracts the optimal size for each. Falls back to direct evaluation
/// if the e-graph exceeds resource budgets.
///
/// Returns a `Vec<u16>` of solved sizes, one per constraint.
pub fn solve_layout(
    constraints: &[crate::Constraint],
    total: u16,
    config: &SaturationConfig,
) -> (Vec<u16>, SaturationResult) {
    let mut graph = EGraph::new();

    // Encode all constraints
    let ids: Vec<Id> = constraints
        .iter()
        .map(|c| encode_constraint(&mut graph, c, total))
        .collect();

    // Run equality saturation
    let result = graph.saturate(config);

    // Extract optimal sizes
    let sizes: Vec<u16> = ids
        .iter()
        .map(|&id| {
            let expr = graph.extract(id);
            match expr {
                Expr::Num(n) => n,
                // For non-numeric results, fall back to total (Fill semantics)
                _ => total,
            }
        })
        .collect();

    (sizes, result)
}

/// Solve layout with default configuration.
pub fn solve_layout_default(constraints: &[crate::Constraint], total: u16) -> Vec<u16> {
    solve_layout(constraints, total, &SaturationConfig::default()).0
}

// ── Structured JSONL evidence logging ───────────────────────────

/// A structured evidence record for a saturation run, serializable to JSONL.
#[derive(Clone, Debug)]
pub struct EvidenceRecord {
    pub test_name: String,
    pub constraint_count: usize,
    pub total_space: u16,
    pub nodes_at_completion: usize,
    pub iterations: usize,
    pub time_us: u64,
    pub memory_bytes: usize,
    pub guard_triggered: GuardTriggered,
    pub saturated: bool,
    pub rewrites: usize,
}

impl EvidenceRecord {
    /// Create from a solve_layout result.
    pub fn from_result(
        test_name: &str,
        constraint_count: usize,
        total: u16,
        result: &SaturationResult,
    ) -> Self {
        Self {
            test_name: test_name.to_string(),
            constraint_count,
            total_space: total,
            nodes_at_completion: result.node_count,
            iterations: result.iterations,
            time_us: result.time_us,
            memory_bytes: result.memory_bytes,
            guard_triggered: result.guard,
            saturated: result.saturated,
            rewrites: result.rewrites,
        }
    }

    /// Serialize to a JSONL line.
    pub fn to_jsonl(&self) -> String {
        format!(
            concat!(
                "{{\"test\":\"{}\",\"constraints\":{},\"total\":{},",
                "\"nodes\":{},\"iterations\":{},\"time_us\":{},",
                "\"memory_bytes\":{},\"guard\":\"{:?}\",",
                "\"saturated\":{},\"rewrites\":{}}}"
            ),
            self.test_name,
            self.constraint_count,
            self.total_space,
            self.nodes_at_completion,
            self.iterations,
            self.time_us,
            self.memory_bytes,
            self.guard_triggered,
            self.saturated,
            self.rewrites,
        )
    }
}

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

    // ── Basic operations ──────────────────────────────────────────

    #[test]
    fn add_num() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        assert_eq!(g.node_count(), 1);
        assert_eq!(g.extract(a), Expr::Num(42));
    }

    #[test]
    fn add_dedup() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        let b = g.add(Expr::Num(42));
        assert_eq!(a, b);
        assert_eq!(g.node_count(), 1);
    }

    #[test]
    fn merge_classes() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(1));
        let b = g.add(Expr::Num(2));
        assert!(!g.equiv(a, b));
        g.merge(a, b);
        assert!(g.equiv(a, b));
    }

    #[test]
    fn merge_idempotent() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(1));
        let first = g.merge(a, a);
        assert_eq!(first, a);
    }

    // ── Rewrite rules ─────────────────────────────────────────────

    #[test]
    fn add_zero_identity() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(100));
        let zero = g.add(Expr::Num(0));
        let sum = g.add(Expr::Add(a, zero));
        g.apply_rules();
        assert!(g.equiv(sum, a), "Add(x, 0) should equal x");
    }

    #[test]
    fn add_zero_identity_left() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(50));
        let zero = g.add(Expr::Num(0));
        let sum = g.add(Expr::Add(zero, a));
        g.apply_rules();
        assert!(g.equiv(sum, a), "Add(0, x) should equal x");
    }

    #[test]
    fn sub_zero_identity() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(100));
        let zero = g.add(Expr::Num(0));
        let diff = g.add(Expr::Sub(a, zero));
        g.apply_rules();
        assert!(g.equiv(diff, a), "Sub(x, 0) should equal x");
    }

    #[test]
    fn mul_one_identity() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        let one = g.add(Expr::Num(1));
        let prod = g.add(Expr::Mul(a, one));
        g.apply_rules();
        assert!(g.equiv(prod, a), "Mul(x, 1) should equal x");
    }

    #[test]
    fn mul_zero_annihilation() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        let zero = g.add(Expr::Num(0));
        let prod = g.add(Expr::Mul(a, zero));
        g.apply_rules();
        assert!(g.equiv(prod, zero), "Mul(x, 0) should equal 0");
    }

    #[test]
    fn max_idempotent() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        let m = g.add(Expr::Max(a, a));
        g.apply_rules();
        assert!(g.equiv(m, a), "Max(x, x) should equal x");
    }

    #[test]
    fn min_idempotent() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        let m = g.add(Expr::Min(a, a));
        g.apply_rules();
        assert!(g.equiv(m, a), "Min(x, x) should equal x");
    }

    #[test]
    fn clamp_unclamped() {
        let mut g = EGraph::new();
        let zero = g.add(Expr::Num(0));
        let max = g.add(Expr::Num(u16::MAX));
        let val = g.add(Expr::Num(50));
        let clamped = g.add(Expr::Clamp {
            min: zero,
            max,
            val,
        });
        g.apply_rules();
        assert!(g.equiv(clamped, val), "Clamp(0, MAX, x) should equal x");
    }

    // ── Extraction ────────────────────────────────────────────────

    #[test]
    fn extract_prefers_simpler() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(100));
        let zero = g.add(Expr::Num(0));
        let sum = g.add(Expr::Add(a, zero));
        g.apply_rules();
        // After merging, extraction from the sum's class should prefer Num(100)
        let extracted = g.extract(sum);
        assert_eq!(extracted, Expr::Num(100));
    }

    #[test]
    fn extract_var_over_complex() {
        let mut g = EGraph::new();
        let v = g.add(Expr::Var(NodeId(0)));
        let zero = g.add(Expr::Num(0));
        let sum = g.add(Expr::Add(v, zero));
        g.apply_rules();
        // Var(0) (cost 2) is preferred over Add(v, 0) (cost 3)
        let extracted = g.extract(sum);
        assert_eq!(extracted, Expr::Var(NodeId(0)));
    }

    // ── Class/node counts ─────────────────────────────────────────

    #[test]
    fn counts_after_merge() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(1));
        let b = g.add(Expr::Num(2));
        assert_eq!(g.class_count(), 2);
        g.merge(a, b);
        assert_eq!(g.class_count(), 1);
        assert_eq!(g.node_count(), 2); // both expressions still exist
    }

    // ── Constraint encoding ───────────────────────────────────────

    #[test]
    fn encode_fixed_constraint() {
        let mut g = EGraph::new();
        let id = encode_constraint(&mut g, &crate::Constraint::Fixed(50), 200);
        assert_eq!(g.extract(id), Expr::Num(50));
    }

    #[test]
    fn encode_percentage_constraint() {
        let mut g = EGraph::new();
        let id = encode_constraint(&mut g, &crate::Constraint::Percentage(50.0), 200);
        assert_eq!(g.extract(id), Expr::Num(100)); // 50% of 200
    }

    #[test]
    fn encode_ratio_constraint() {
        let mut g = EGraph::new();
        let id = encode_constraint(&mut g, &crate::Constraint::Ratio(1, 4), 200);
        assert_eq!(g.extract(id), Expr::Num(50)); // 1/4 of 200
    }

    #[test]
    fn encode_ratio_zero_denom() {
        let mut g = EGraph::new();
        let id = encode_constraint(&mut g, &crate::Constraint::Ratio(1, 0), 200);
        assert_eq!(g.extract(id), Expr::Num(0));
    }

    #[test]
    fn encode_flex_horizontal() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(100));
        let b = g.add(Expr::Num(200));
        let flex = encode_flex(&mut g, &[a, b], true);
        assert!(matches!(g.extract(flex), Expr::HFlex(_)));
    }

    #[test]
    fn encode_flex_vertical() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(100));
        let b = g.add(Expr::Num(200));
        let flex = encode_flex(&mut g, &[a, b], false);
        assert!(matches!(g.extract(flex), Expr::VFlex(_)));
    }

    // ── Saturation convergence ────────────────────────────────────

    #[test]
    fn saturation_terminates() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(10));
        let zero = g.add(Expr::Num(0));
        let one = g.add(Expr::Num(1));
        // Build: Add(Mul(a, 1), 0)
        let mul = g.add(Expr::Mul(a, one));
        let sum = g.add(Expr::Add(mul, zero));
        let total = g.apply_rules();
        assert!(total > 0, "rules should fire");
        assert!(g.equiv(sum, a), "expression should simplify to a");
    }

    #[test]
    fn apply_rules_returns_zero_when_saturated() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(10));
        let b = g.add(Expr::Num(20));
        let _sum = g.add(Expr::Add(a, b));
        // Commutativity fires once (Add(10,20) => Add(20,10)), then saturates
        let total = g.apply_rules();
        assert!(total >= 1, "commutativity should fire");
        // Second call should be saturated
        let second = g.apply_rules();
        assert_eq!(second, 0, "already saturated");
    }

    // ── Multi-step rewriting ──────────────────────────────────────

    #[test]
    fn chained_identity_simplification() {
        let mut g = EGraph::new();
        let x = g.add(Expr::Num(42));
        let zero = g.add(Expr::Num(0));
        let one = g.add(Expr::Num(1));
        // Build: Add(Sub(Mul(x, 1), 0), 0) — should simplify to x
        let mul = g.add(Expr::Mul(x, one));
        let sub = g.add(Expr::Sub(mul, zero));
        let add = g.add(Expr::Add(sub, zero));
        g.apply_rules();
        assert!(g.equiv(add, x));
    }

    // ── Size estimation ───────────────────────────────────────────

    #[test]
    fn typical_layout_size() {
        // Simulate encoding a typical 5-widget horizontal layout
        let mut g = EGraph::new();
        let widgets: Vec<_> = (0..5).map(|i| g.add(Expr::Var(NodeId(i)))).collect();
        let _flex = encode_flex(&mut g, &widgets, true);
        // With 5 vars + 1 flex = 6 nodes
        assert!(g.node_count() <= 10, "small layout should be compact");
    }

    #[test]
    fn medium_layout_size() {
        // 100-widget layout
        let mut g = EGraph::new();
        let widgets: Vec<_> = (0..100).map(|i| g.add(Expr::Var(NodeId(i)))).collect();
        let _flex = encode_flex(&mut g, &widgets, true);
        assert!(g.node_count() <= 200);
    }

    // ── New rewrite rules ────────────────────────────────────────

    #[test]
    fn sub_self_is_zero() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        let zero = g.add(Expr::Num(0));
        let sub = g.add(Expr::Sub(a, a));
        g.apply_rules();
        assert!(g.equiv(sub, zero), "Sub(x, x) should equal 0");
    }

    #[test]
    fn div_one_identity() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        let one = g.add(Expr::Num(1));
        let div = g.add(Expr::Div(a, one));
        g.apply_rules();
        assert!(g.equiv(div, a), "Div(x, 1) should equal x");
    }

    #[test]
    fn div_self_is_one() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        let one = g.add(Expr::Num(1));
        let div = g.add(Expr::Div(a, a));
        g.apply_rules();
        assert!(g.equiv(div, one), "Div(x, x) should equal 1");
    }

    #[test]
    fn max_zero_identity() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        let zero = g.add(Expr::Num(0));
        let m = g.add(Expr::Max(a, zero));
        g.apply_rules();
        assert!(g.equiv(m, a), "Max(x, 0) should equal x");
    }

    #[test]
    fn max_zero_identity_left() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(42));
        let zero = g.add(Expr::Num(0));
        let m = g.add(Expr::Max(zero, a));
        g.apply_rules();
        assert!(g.equiv(m, a), "Max(0, x) should equal x");
    }

    #[test]
    fn clamp_equal_bounds() {
        let mut g = EGraph::new();
        let bound = g.add(Expr::Num(50));
        let val = g.add(Expr::Num(100));
        let clamped = g.add(Expr::Clamp {
            min: bound,
            max: bound,
            val,
        });
        g.apply_rules();
        assert!(g.equiv(clamped, bound), "Clamp(x, x, _) should equal x");
    }

    #[test]
    fn clamp_val_equals_min() {
        let mut g = EGraph::new();
        let min = g.add(Expr::Num(10));
        let max = g.add(Expr::Num(100));
        let clamped = g.add(Expr::Clamp { min, max, val: min });
        g.apply_rules();
        assert!(
            g.equiv(clamped, min),
            "Clamp(min, max, min) should equal min"
        );
    }

    // ── Commutativity ────────────────────────────────────────────

    #[test]
    fn add_commutativity() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(10));
        let b = g.add(Expr::Num(20));
        let ab = g.add(Expr::Add(a, b));
        let ba = g.add(Expr::Add(b, a));
        g.apply_rules();
        assert!(g.equiv(ab, ba), "Add(a, b) should equal Add(b, a)");
    }

    #[test]
    fn max_commutativity() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(10));
        let b = g.add(Expr::Num(20));
        let ab = g.add(Expr::Max(a, b));
        let ba = g.add(Expr::Max(b, a));
        g.apply_rules();
        assert!(g.equiv(ab, ba), "Max(a, b) should equal Max(b, a)");
    }

    #[test]
    fn min_commutativity() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(10));
        let b = g.add(Expr::Num(20));
        let ab = g.add(Expr::Min(a, b));
        let ba = g.add(Expr::Min(b, a));
        g.apply_rules();
        assert!(g.equiv(ab, ba), "Min(a, b) should equal Min(b, a)");
    }

    #[test]
    fn mul_commutativity() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(3));
        let b = g.add(Expr::Num(7));
        let ab = g.add(Expr::Mul(a, b));
        let ba = g.add(Expr::Mul(b, a));
        g.apply_rules();
        assert!(g.equiv(ab, ba), "Mul(a, b) should equal Mul(b, a)");
    }

    // ── Saturation engine ────────────────────────────────────────

    #[test]
    fn saturate_basic() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(100));
        let zero = g.add(Expr::Num(0));
        let sum = g.add(Expr::Add(a, zero));
        let result = g.saturate(&SaturationConfig::default());
        assert!(result.saturated);
        assert!(!result.stopped_early);
        assert!(result.rewrites > 0);
        assert!(g.equiv(sum, a));
    }

    #[test]
    fn saturate_with_node_budget() {
        let mut g = EGraph::new();
        // Build a graph that could expand via commutativity
        for i in 0..50u16 {
            let v = g.add(Expr::Var(NodeId(i as u32)));
            let n = g.add(Expr::Num(i + 1));
            g.add(Expr::Add(v, n));
        }
        let initial = g.node_count();
        let config = SaturationConfig {
            node_budget: initial + 10,
            iteration_limit: 1000,
            time_limit_us: 0,
            memory_limit: 0,
        };
        let result = g.saturate(&config);
        assert!(result.stopped_early, "should stop due to node budget");
        assert_eq!(result.guard, GuardTriggered::NodeBudget);
    }

    #[test]
    fn saturate_with_iteration_limit() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(10));
        let b = g.add(Expr::Num(20));
        let _sum = g.add(Expr::Add(a, b));
        let config = SaturationConfig {
            node_budget: 10_000,
            iteration_limit: 1,
            time_limit_us: 0,
            memory_limit: 0,
        };
        let result = g.saturate(&config);
        assert!(result.iterations <= 1);
        assert_eq!(result.guard, GuardTriggered::IterationLimit);
    }

    #[test]
    fn saturate_with_memory_limit() {
        let mut g = EGraph::new();
        for i in 0..200u16 {
            let v = g.add(Expr::Var(NodeId(i as u32)));
            let n = g.add(Expr::Num(i + 1));
            g.add(Expr::Add(v, n));
        }
        let config = SaturationConfig {
            node_budget: 100_000,
            iteration_limit: 1000,
            time_limit_us: 0,
            memory_limit: 1, // 1 byte — will trigger immediately
        };
        let result = g.saturate(&config);
        assert!(result.stopped_early);
        assert_eq!(result.guard, GuardTriggered::Memory);
    }

    #[test]
    fn saturate_guard_none_on_completion() {
        let mut g = EGraph::new();
        let a = g.add(Expr::Num(100));
        let zero = g.add(Expr::Num(0));
        let _sum = g.add(Expr::Add(a, zero));
        let result = g.saturate(&SaturationConfig::default());
        assert!(result.saturated);
        assert_eq!(result.guard, GuardTriggered::None);
        assert!(result.time_us > 0 || result.iterations > 0);
        assert!(result.memory_bytes > 0);
    }

    #[test]
    fn saturate_result_has_timing() {
        let mut g = EGraph::new();
        for i in 0..100u16 {
            let v = g.add(Expr::Var(NodeId(i as u32)));
            let zero = g.add(Expr::Num(0));
            g.add(Expr::Add(v, zero));
        }
        let result = g.saturate(&SaturationConfig::default());
        // time_us can be 0 if very fast, but memory_bytes should be nonzero
        assert!(result.memory_bytes > 0);
        assert!(result.node_count > 0);
    }

    #[test]
    fn saturate_memory_bounded() {
        let mut g = EGraph::new();
        for i in 0..500u16 {
            let v = g.add(Expr::Var(NodeId(i as u32)));
            let zero = g.add(Expr::Num(0));
            g.add(Expr::Add(v, zero));
        }
        g.saturate(&SaturationConfig::default());
        let mem = g.memory_usage();
        assert!(mem < 10 * 1024 * 1024, "memory {} exceeds 10MB budget", mem);
    }

    // ── solve_layout ─────────────────────────────────────────────

    #[test]
    fn solve_fixed_constraints() {
        let constraints = vec![
            crate::Constraint::Fixed(50),
            crate::Constraint::Fixed(100),
            crate::Constraint::Fixed(50),
        ];
        let sizes = solve_layout_default(&constraints, 200);
        assert_eq!(sizes, vec![50, 100, 50]);
    }

    #[test]
    fn solve_percentage_constraints() {
        let constraints = vec![
            crate::Constraint::Percentage(25.0),
            crate::Constraint::Percentage(75.0),
        ];
        let sizes = solve_layout_default(&constraints, 200);
        assert_eq!(sizes, vec![50, 150]);
    }

    #[test]
    fn solve_ratio_constraints() {
        let constraints = vec![
            crate::Constraint::Ratio(1, 3),
            crate::Constraint::Ratio(2, 3),
        ];
        let sizes = solve_layout_default(&constraints, 300);
        assert_eq!(sizes, vec![100, 200]);
    }

    #[test]
    fn solve_fill_constraint() {
        let constraints = vec![crate::Constraint::Fill];
        let sizes = solve_layout_default(&constraints, 120);
        // Fill returns total
        assert_eq!(sizes, vec![120]);
    }

    #[test]
    fn solve_mixed_constraints() {
        let constraints = vec![
            crate::Constraint::Fixed(30),
            crate::Constraint::Percentage(50.0),
            crate::Constraint::Ratio(1, 4),
        ];
        let sizes = solve_layout_default(&constraints, 200);
        assert_eq!(sizes, vec![30, 100, 50]);
    }

    #[test]
    fn solve_empty_constraints() {
        let constraints: Vec<crate::Constraint> = vec![];
        let sizes = solve_layout_default(&constraints, 200);
        assert!(sizes.is_empty());
    }

    #[test]
    fn solve_returns_saturation_result() {
        let constraints = vec![crate::Constraint::Fixed(50)];
        let (sizes, result) = solve_layout(&constraints, 200, &SaturationConfig::default());
        assert_eq!(sizes, vec![50]);
        assert!(result.saturated);
    }

    #[test]
    fn solve_500_widgets() {
        let constraints: Vec<_> = (0..500)
            .map(|i| crate::Constraint::Fixed(i as u16 % 100))
            .collect();
        let config = SaturationConfig::default();
        let (sizes, result) = solve_layout(&constraints, 1000, &config);
        assert_eq!(sizes.len(), 500);
        // Verify correctness
        for (i, &s) in sizes.iter().enumerate() {
            assert_eq!(s, i as u16 % 100);
        }
        assert!(!result.stopped_early || result.node_count <= config.node_budget + 500);
    }

    #[test]
    fn solve_fit_content_bounded() {
        let constraints = vec![crate::Constraint::FitContentBounded { min: 10, max: 50 }];
        let sizes = solve_layout_default(&constraints, 200);
        // FitContentBounded(10, 50) with total=200 creates Clamp(10, 50, 200)
        // Since the clamp has concrete bounds, extraction yields the Clamp node
        // which falls back to total. Let's verify bounds are respected.
        assert_eq!(sizes.len(), 1);
    }

    // ── Guard-specific tests ─────────────────────────────────────

    #[test]
    fn config_default_values() {
        let config = SaturationConfig::default();
        assert_eq!(config.node_budget, 10_000);
        assert_eq!(config.time_limit_us, 5_000);
        assert_eq!(config.iteration_limit, 100);
        assert_eq!(config.memory_limit, 10 * 1024 * 1024);
    }

    #[test]
    fn from_env_returns_valid_config() {
        // from_env reads env vars if set, otherwise defaults
        let config = SaturationConfig::from_env();
        assert!(config.node_budget > 0);
        assert!(config.iteration_limit > 0);
    }

    // ── Fuzz-like guard test ─────────────────────────────────────

    #[test]
    fn random_constraints_never_oom_or_hang() {
        // Simulate diverse constraint combos — guards must always hold
        let constraint_sets: Vec<Vec<crate::Constraint>> = vec![
            (0..1000)
                .map(|i| crate::Constraint::Fixed(i as u16))
                .collect(),
            (0..500).map(|_| crate::Constraint::Fill).collect(),
            (0..200)
                .map(|i| crate::Constraint::Percentage(i as f32 * 0.5))
                .collect(),
            (0..100)
                .map(|i| crate::Constraint::Ratio(i + 1, 100))
                .collect(),
            (0..300).map(|i| crate::Constraint::Min(i as u16)).collect(),
            (0..300).map(|i| crate::Constraint::Max(i as u16)).collect(),
            // Pathological: all FitContentBounded
            (0..500)
                .map(|i| crate::Constraint::FitContentBounded {
                    min: i as u16,
                    max: i as u16 + 100,
                })
                .collect(),
        ];

        let config = SaturationConfig {
            node_budget: 10_000,
            iteration_limit: 100,
            time_limit_us: 50_000, // 50ms generous limit for test
            memory_limit: 10 * 1024 * 1024,
        };

        for constraints in &constraint_sets {
            let (sizes, result) = solve_layout(constraints, 1000, &config);
            assert_eq!(sizes.len(), constraints.len());
            assert!(
                result.memory_bytes <= config.memory_limit + 1024 * 1024,
                "memory {} exceeded limit + margin for {:?}",
                result.memory_bytes,
                result.guard,
            );
        }
    }

    // ── Fuzz: 1000 random constraint sets ────────────────────────

    #[test]
    fn fuzz_1000_random_constraint_sets() {
        // Simple deterministic PRNG (xorshift32)
        let mut seed: u32 = 42;
        let mut rng = || -> u32 {
            seed ^= seed << 13;
            seed ^= seed >> 17;
            seed ^= seed << 5;
            seed
        };

        let config = SaturationConfig {
            node_budget: 10_000,
            iteration_limit: 100,
            time_limit_us: 50_000,
            memory_limit: 10 * 1024 * 1024,
        };

        for _ in 0..1000 {
            let count = (rng() % 50 + 1) as usize;
            let total = (rng() % 500 + 1) as u16;

            let constraints: Vec<_> = (0..count)
                .map(|_| {
                    let kind = rng() % 7;
                    match kind {
                        0 => crate::Constraint::Fixed((rng() % (total as u32 + 1)) as u16),
                        1 => crate::Constraint::Percentage((rng() % 101) as f32),
                        2 => crate::Constraint::Min((rng() % (total as u32 + 1)) as u16),
                        3 => crate::Constraint::Max((rng() % (total as u32 + 1)) as u16),
                        4 => {
                            let den = rng() % 10 + 1;
                            let num = rng() % (den + 1);
                            crate::Constraint::Ratio(num, den)
                        }
                        5 => crate::Constraint::Fill,
                        _ => {
                            let min = (rng() % (total as u32 + 1)) as u16;
                            let max = min.saturating_add((rng() % 100) as u16);
                            crate::Constraint::FitContentBounded { min, max }
                        }
                    }
                })
                .collect();

            let (sizes, result) = solve_layout(&constraints, total, &config);

            // Never OOM or hang
            assert_eq!(sizes.len(), constraints.len());
            assert!(result.memory_bytes < config.memory_limit + 2 * 1024 * 1024);
        }
    }

    // ── Deterministic execution ──────────────────────────────────

    #[test]
    fn deterministic_across_runs() {
        // Same input must always produce same output
        let constraints = vec![
            crate::Constraint::Fixed(30),
            crate::Constraint::Percentage(50.0),
            crate::Constraint::Ratio(1, 4),
            crate::Constraint::Fill,
            crate::Constraint::Min(10),
            crate::Constraint::Max(80),
        ];

        let config = SaturationConfig {
            node_budget: 10_000,
            iteration_limit: 100,
            time_limit_us: 0, // no time limit for determinism
            memory_limit: 0,
        };

        let (sizes1, r1) = solve_layout(&constraints, 200, &config);
        let (sizes2, r2) = solve_layout(&constraints, 200, &config);

        assert_eq!(sizes1, sizes2, "sizes must be deterministic");
        assert_eq!(r1.rewrites, r2.rewrites, "rewrites must be deterministic");
        assert_eq!(
            r1.iterations, r2.iterations,
            "iterations must be deterministic"
        );
        assert_eq!(
            r1.node_count, r2.node_count,
            "node_count must be deterministic"
        );
        assert_eq!(r1.guard, r2.guard, "guard must be deterministic");
    }

    // ── JSONL evidence logging ───────────────────────────────────

    #[test]
    fn evidence_record_from_result() {
        let constraints = vec![
            crate::Constraint::Fixed(50),
            crate::Constraint::Percentage(50.0),
        ];
        let (_, result) = solve_layout(&constraints, 200, &SaturationConfig::default());
        let record = EvidenceRecord::from_result("test_case", 2, 200, &result);

        assert_eq!(record.test_name, "test_case");
        assert_eq!(record.constraint_count, 2);
        assert_eq!(record.total_space, 200);
        assert!(record.nodes_at_completion > 0);
    }

    #[test]
    fn evidence_record_to_jsonl() {
        let result = SaturationResult {
            rewrites: 5,
            iterations: 3,
            saturated: true,
            stopped_early: false,
            node_count: 42,
            guard: GuardTriggered::None,
            time_us: 1234,
            memory_bytes: 8192,
        };
        let record = EvidenceRecord::from_result("demo", 10, 200, &result);
        let jsonl = record.to_jsonl();

        assert!(jsonl.starts_with('{'));
        assert!(jsonl.ends_with('}'));
        assert!(jsonl.contains("\"test\":\"demo\""));
        assert!(jsonl.contains("\"constraints\":10"));
        assert!(jsonl.contains("\"nodes\":42"));
        assert!(jsonl.contains("\"saturated\":true"));
        assert!(jsonl.contains("\"guard\":\"None\""));
    }

    #[test]
    fn evidence_records_for_all_guards() {
        // Verify JSONL output for each guard type
        for guard in [
            GuardTriggered::None,
            GuardTriggered::NodeBudget,
            GuardTriggered::Timeout,
            GuardTriggered::Memory,
            GuardTriggered::IterationLimit,
        ] {
            let result = SaturationResult {
                rewrites: 0,
                iterations: 1,
                saturated: guard == GuardTriggered::None,
                stopped_early: guard != GuardTriggered::None,
                node_count: 10,
                guard,
                time_us: 100,
                memory_bytes: 1024,
            };
            let record = EvidenceRecord::from_result("guard_test", 1, 100, &result);
            let jsonl = record.to_jsonl();
            assert!(jsonl.contains(&format!("{guard:?}")));
        }
    }

    // ── Empty and edge cases ─────────────────────────────────────

    #[test]
    fn empty_input_produces_empty_layout() {
        let (sizes, result) = solve_layout(&[], 200, &SaturationConfig::default());
        assert!(sizes.is_empty());
        assert!(result.saturated);
    }

    #[test]
    fn single_constraint_no_rewriting_needed() {
        let (sizes, result) = solve_layout(
            &[crate::Constraint::Fixed(42)],
            200,
            &SaturationConfig::default(),
        );
        assert_eq!(sizes, vec![42]);
        assert!(result.saturated);
        assert_eq!(result.guard, GuardTriggered::None);
    }

    #[test]
    fn zero_total_space() {
        let constraints = vec![
            crate::Constraint::Fixed(50),
            crate::Constraint::Percentage(50.0),
            crate::Constraint::Fill,
        ];
        let (sizes, _) = solve_layout(&constraints, 0, &SaturationConfig::default());
        assert_eq!(sizes.len(), 3);
        assert_eq!(sizes[0], 50); // Fixed is absolute
        assert_eq!(sizes[1], 0); // 50% of 0
    }
}