E-Graph Layout Optimizer

The e-graph optimizer, living in crates/ftui-layout/src/egraph.rs (~1,700 lines), is a layout-level optimizer that discovers equivalent-but-cheaper constraint expressions by equality saturation. The idea is borrowed directly from the compiler world (e.g., egg in Rust), applied to a tiny arithmetic language over layout sizes.

It is not on the hot path for every frame. You reach for it when building a layout solver component that wants to pick between many equivalent constraint formulations and choose the smallest cost.

A 60-second primer on e-graphs

An e-graph is a data structure that stores many expressions and the equivalence classes between them. Conceptually:

• E-class: a set of expressions known to be equal (e.g. {a + 0, a, a * 1}).
• E-node: one concrete expression inside an e-class (a + 0).
• Rewrite rule: a pattern-and-replacement that declares two things equal (Add(a, Num(0)) ≡ a).
• Saturation: keep applying rewrites until nothing new is discovered.
• Extraction: pick the lowest-cost representative from each final e-class.

An e-graph lets you explore an exponential space of equivalent expressions in near-linear time, because equivalences are stored in shared state rather than enumerated.

The Expr language

pub enum Expr {
    Num(u16),                       // concrete cell value
    Var(NodeId),                    // reference to a widget
    Add(Id, Id),
    Sub(Id, Id),
    Max(Id, Id),
    Min(Id, Id),
    Div(Id, Id),
    Mul(Id, Id),
    Clamp { min: Id, max: Id, val: Id },
    HFlex(Vec<Id>),                 // horizontal flex container
    VFlex(Vec<Id>),                 // vertical flex container
    Fill(Id),                       // fill remaining space
}

Id is an opaque handle into the e-graph; NodeId is an external widget identifier.

Representative rewrite rules

A small sample of the ~30 rules that ship; each one says “these two expressions are equal”:

Each rule produces zero or more new merge() calls; the saturator keeps applying them until a fixed point is reached (or a budget is exhausted).

Architecture

pub struct EGraph {
    parents: Vec<u32>,              // union-find parent pointers
    ranks: Vec<u8>,                 // union-by-rank
    nodes: Vec<Vec<Expr>>,          // e-nodes grouped by e-class
    memo: HashMap<Expr, Id>,        // hashcons: canonical expr → e-class
    last_apply_count: usize,
}

• Union-find (parents, ranks) stores the partition of ids into e-classes.
• nodes stores, per class, the concrete e-nodes that live there.
• memo is the hashcons: the same Expr shape always maps to the same class. When you add() an expression, canonicalization follows every Id to its class representative before doing the lookup.

Six methods are load-bearing:

EGraph::new() -> Self
EGraph::add(expr)     -> Id             // intern + canonicalize
EGraph::merge(a, b)   -> Id             // union-find
EGraph::find(id)      -> Id             // path-compressed lookup
EGraph::equiv(a, b)   -> bool           // same e-class?
EGraph::apply_rules() -> usize          // saturate
EGraph::extract(id)   -> Expr           // lowest-cost from the class

The extraction cost model

After saturation, extract(id) walks the e-class and picks the cheapest e-node. A simple model weights each variant:

where $c_{\text{shape}}$ is a small per-variant constant:

• Num / Var — cheapest (leaves).
• Add / Sub — small constant.
• Max / Min / Div / Mul — larger.
• Clamp — larger still (three children).
• HFlex / VFlex — proportional to arity.
• Fill — discount because it’s the “already solved” form.

The recursion terminates because every Id strictly reduces when you take the min over its e-class.

Worked example

use ftui_layout::egraph::{EGraph, Expr, NodeId};
 
let mut g = EGraph::new();
 
let a = g.add(Expr::Var(NodeId(0)));
let b = g.add(Expr::Var(NodeId(1)));
let c = g.add(Expr::Var(NodeId(2)));
 
// HFlex(a, HFlex(b, c))
let inner = g.add(Expr::HFlex(vec![b, c]));
let nested = g.add(Expr::HFlex(vec![a, inner]));
 
g.apply_rules();
 
// After the flatten rule fires, HFlex(a, HFlex(b, c))
// is in the same e-class as HFlex(a, b, c).
let flat = g.add(Expr::HFlex(vec![a, b, c]));
assert!(g.equiv(nested, flat));
 
// Extraction picks the flatter form (lower cost than the nested one).
let best = g.extract(nested);
// best is Expr::HFlex([a, b, c])

solve_layout — the production entry point

For real use, you wrap the e-graph in solve_layout which encodes constraints, saturates, extracts, and reifies sizes:

pub fn solve_layout(
    constraints: &[Constraint],
    total: u16,
    config: &SaturationConfig,
) -> Vec<u16>;
 
pub fn solve_layout_default(constraints: &[Constraint], total: u16)
    -> Vec<u16>;

SaturationConfig exposes the saturation budget (max_iterations), memory watchdog (max_memory_bytes), and other guards. On overflow SaturationResult::guard_triggered tells you which guard fired.

When to reach for this

Pitfalls

Where to go next