rexact_core/

term.rs

//! Extended regular-expression terms with Brzozowski derivatives
//! (architecture section 3, FR-B01, FR-B02, FR-B07, FR-B08).
//!
//! Contract: terms live in a [`TermStore`] that interns them, so equal terms
//! share one [`TermId`]. Smart constructors keep terms normalised: unions and
//! intersections are flattened, sorted and de-duplicated, concatenation is
//! right-nested, `Empty`/`Epsilon` are absorbed, and `Star(Star(x)) = Star(x)`,
//! `Not(Not(x)) = x`. Derivatives of normalised terms stay inside a finite set,
//! which is what makes the automaton construction terminate.
//!
//! Zero-width constructs (M6):
//! * `Assert` (anchors, word boundaries) are evaluated against a [`Ctx`] that
//!   remembers whether the input just started, which auxiliary character sets
//!   the previous character belonged to, and the state of every lookbehind
//!   tracker. The derivative therefore takes the context and the next
//!   character; at the end of input, acceptance is evaluated with no next
//!   character.
//! * `LookAhead(X)` has no meaning on its own: whatever follows it in the
//!   enclosing pattern decides. Its derivative is therefore computed with an
//!   explicit continuation `k` (everything that follows): `(?=X)·k` has the
//!   language `(X·Σ*) ∩ k` and `(?!X)·k` has `¬(X·Σ*) ∩ k`, so
//!   `d((?=X)·k) = d(X·Σ*) ∩ d(k)`. A lookahead left at the very end of a term
//!   holds iff `X` accepts the empty remainder. Recursion through zero-width
//!   loops is cut with a re-entrancy guard that returns the empty language,
//!   which is the least fixpoint of the (monotone) equations.
//! * `LookBehind(X)` holds iff the consumed input ends with a match of `X`.
//!   It is answered by a tracker automaton for `Σ*·X` kept in the context.
//!
//! Invariants: every `Class` set is non-empty and a subset of the universe;
//! `Not` complements relative to `universe*`; lookbehind bodies contain no
//! context-dependent construct.
//!
//! Failure modes: constructors are total and never panic. Registering more
//! than [`MAX_AUX`] distinct auxiliary sets or [`MAX_TRACKERS`] lookbehinds
//! returns `None` so the caller can report `RX-U005`.

use crate::charset::{refine, refine_all, CharSet};
use std::collections::HashMap;
use std::sync::Arc;

/// Handle to an interned term.
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
pub struct TermId(u32);

impl TermId {
    /// Dense index, for tables keyed by term.
    pub fn index(self) -> usize {
        self.0 as usize
    }
}

/// Marks an unused auxiliary-set slot in an assertion.
pub const NO_AUX: u8 = 255;
/// Most distinct auxiliary sets (word / newline definitions) in one store.
pub const MAX_AUX: usize = 48;
/// Most lookbehind trackers in one store.
pub const MAX_TRACKERS: usize = 16;

/// Zero-width assertions on the neighbouring characters.
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub enum AssertKind {
    /// Start of the input.
    TextStart,
    /// End of the input.
    TextEnd,
    /// Start of input or just after a character of the line set.
    LineStart,
    /// End of input or just before a character of the line set.
    LineEnd,
    /// Previous and next characters differ in membership of the word set.
    WordBoundary,
    /// Previous and next characters agree in membership of the word set.
    NotWordBoundary,
    /// Not after a word character, before a word character.
    WordStart,
    /// After a word character, not before one.
    WordEnd,
}

impl AssertKind {
    /// Letter used in the interchange format.
    pub const fn letter(self) -> char {
        match self {
            AssertKind::TextStart => 'A',
            AssertKind::TextEnd => 'z',
            AssertKind::LineStart => '^',
            AssertKind::LineEnd => '$',
            AssertKind::WordBoundary => 'b',
            AssertKind::NotWordBoundary => 'B',
            AssertKind::WordStart => '<',
            AssertKind::WordEnd => '>',
        }
    }
}

/// Shape of a term.
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub enum TermKind {
    /// The empty language.
    Empty,
    /// Only the empty string.
    Epsilon,
    /// One symbol from a non-empty set.
    Class(CharSet),
    /// Concatenation; the left side is never itself a `Concat`.
    Concat(TermId, TermId),
    /// Union of at least two distinct, sorted, non-`Union` terms.
    Union(Arc<[TermId]>),
    /// Kleene star.
    Star(TermId),
    /// Intersection of at least two distinct, sorted, non-`Inter` terms.
    Inter(Arc<[TermId]>),
    /// Complement relative to all strings over the universe.
    Not(TermId),
    /// A zero-width assertion with the indices of its auxiliary sets.
    Assert {
        /// Which assertion.
        kind: AssertKind,
        /// Index of the word set ([`NO_AUX`] when unused).
        word: u8,
        /// Index of the line-terminator set ([`NO_AUX`] when unused).
        line: u8,
    },
    /// `(?=body)` / `(?!body)`.
    LookAhead {
        /// Negative form.
        neg: bool,
        /// The looked-at pattern, complete in itself.
        body: TermId,
    },
    /// `(?<=body)` / `(?<!body)`, answered by tracker number `tracker`.
    LookBehind {
        /// Negative form.
        neg: bool,
        /// Index into the store's tracker table.
        tracker: u8,
    },
}

struct Node {
    kind: TermKind,
    /// Accepts the empty string, ignoring context (only meaningful when `!ctx_dep`).
    nullable: bool,
    /// Contains an assertion or lookaround, so its behaviour depends on context.
    ctx_dep: bool,
    /// Contains a lookahead (continuation must be distributed over it).
    has_look: bool,
}

/// What the matcher has seen before the current position.
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub struct Ctx {
    /// No character consumed yet.
    pub start: bool,
    /// Bit `i` set when the previous character belongs to auxiliary set `i`.
    pub bits: u64,
    /// State of each lookbehind tracker (derivative of `Σ*·body`).
    pub tracks: Vec<TermId>,
}

/// A lookbehind tracker: the body and the root of its `Σ*·body` automaton.
#[derive(Clone, Copy, Debug)]
struct Tracker {
    body: TermId,
    root: TermId,
}

/// Interning store and derivative engine.
pub struct TermStore {
    nodes: Vec<Node>,
    index: HashMap<TermKind, TermId>,
    universe: CharSet,
    empty: TermId,
    epsilon: TermId,
    universal: TermId,
    deriv_cache: HashMap<(TermId, u32, u32), TermId>,
    part_cache: HashMap<TermId, Arc<Vec<CharSet>>>,
    look_cache: HashMap<(TermId, u32, u32), TermId>,
    aux_sets: Vec<CharSet>,
    trackers: Vec<Tracker>,
    ctxs: Vec<Ctx>,
    ctx_index: HashMap<Ctx, u32>,
    node_bytes: u64,
}

/// Id of the context used for terms that do not depend on context.
pub const NO_CTX: u32 = 0;

impl TermStore {
    /// New store over the given universe of symbols.
    pub fn new(universe: CharSet) -> Self {
        let mut s = TermStore {
            nodes: Vec::new(),
            index: HashMap::new(),
            universe,
            empty: TermId(0),
            epsilon: TermId(0),
            universal: TermId(0),
            deriv_cache: HashMap::new(),
            part_cache: HashMap::new(),
            look_cache: HashMap::new(),
            aux_sets: Vec::new(),
            trackers: Vec::new(),
            ctxs: Vec::new(),
            ctx_index: HashMap::new(),
            node_bytes: 0,
        };
        s.empty = s.intern(TermKind::Empty);
        s.epsilon = s.intern(TermKind::Epsilon);
        s.universal = s.intern(TermKind::Not(s.empty));
        // Placeholder for terms that do not depend on context: a value no real context can have.
        s.intern_ctx(Ctx {
            start: false,
            bits: u64::MAX,
            tracks: Vec::new(),
        });
        s
    }

    /// The universe of symbols.
    pub fn universe(&self) -> &CharSet {
        &self.universe
    }
    /// Number of interned terms (used for memory estimates).
    pub fn len(&self) -> usize {
        self.nodes.len()
    }
    /// Estimated heap bytes held by terms and memo tables (for the memory limit).
    pub fn approx_bytes(&self) -> u64 {
        self.node_bytes
            + 64 * (self.deriv_cache.len() + self.part_cache.len() + self.look_cache.len()) as u64
    }
    /// True when only the three built-in terms exist.
    pub fn is_empty(&self) -> bool {
        self.nodes.len() <= 3
    }
    /// The empty language.
    pub fn empty(&self) -> TermId {
        self.empty
    }
    /// The language containing only the empty string.
    pub fn epsilon(&self) -> TermId {
        self.epsilon
    }
    /// All strings over the universe.
    pub fn universal(&self) -> TermId {
        self.universal
    }
    /// Shape of a term.
    pub fn kind(&self, t: TermId) -> &TermKind {
        &self.nodes[t.index()].kind
    }
    /// Does the term accept the empty string, ignoring context? Exact only when
    /// [`TermStore::ctx_dep`] is false; use [`TermStore::accepting`] otherwise.
    pub fn nullable(&self, t: TermId) -> bool {
        self.nodes[t.index()].nullable
    }
    /// Does the term contain an assertion or lookaround?
    pub fn ctx_dep(&self, t: TermId) -> bool {
        self.nodes[t.index()].ctx_dep
    }
    /// The auxiliary sets referenced by assertions, by index.
    pub fn aux_sets(&self) -> &[CharSet] {
        &self.aux_sets
    }
    /// Body of lookbehind tracker `i`.
    pub fn tracker_body(&self, i: u8) -> Option<TermId> {
        self.trackers.get(i as usize).map(|t| t.body)
    }

    fn intern(&mut self, kind: TermKind) -> TermId {
        if let Some(&id) = self.index.get(&kind) {
            return id;
        }
        self.node_bytes += 128
            + match &kind {
                TermKind::Union(v) | TermKind::Inter(v) => 8 * v.len() as u64,
                _ => 0,
            };
        let n = |s: &Self, x: TermId| (s.nullable(x), s.ctx_dep(x), s.nodes[x.index()].has_look);
        let (nullable, ctx_dep, has_look) = match &kind {
            TermKind::Empty | TermKind::Class(_) => (false, false, false),
            TermKind::Epsilon | TermKind::Star(_) => {
                let child = if let TermKind::Star(x) = &kind {
                    n(self, *x)
                } else {
                    (true, false, false)
                };
                (true, child.1, child.2)
            }
            TermKind::Concat(a, b) => {
                let (x, y) = (n(self, *a), n(self, *b));
                (x.0 && y.0, x.1 || y.1, x.2 || y.2)
            }
            TermKind::Union(v) => {
                let cs: Vec<_> = v.iter().map(|&x| n(self, x)).collect();
                (
                    cs.iter().any(|c| c.0),
                    cs.iter().any(|c| c.1),
                    cs.iter().any(|c| c.2),
                )
            }
            TermKind::Inter(v) => {
                let cs: Vec<_> = v.iter().map(|&x| n(self, x)).collect();
                (
                    cs.iter().all(|c| c.0),
                    cs.iter().any(|c| c.1),
                    cs.iter().any(|c| c.2),
                )
            }
            TermKind::Not(x) => {
                let c = n(self, *x);
                (!c.0, c.1, c.2)
            }
            TermKind::Assert { .. } | TermKind::LookBehind { .. } => (false, true, false),
            TermKind::LookAhead { .. } => (false, true, true),
        };
        let id = TermId(self.nodes.len() as u32);
        self.nodes.push(Node {
            kind: kind.clone(),
            nullable,
            ctx_dep,
            has_look,
        });
        self.index.insert(kind, id);
        id
    }

    fn intern_ctx(&mut self, c: Ctx) -> u32 {
        if let Some(&id) = self.ctx_index.get(&c) {
            return id;
        }
        let id = self.ctxs.len() as u32;
        self.ctxs.push(c.clone());
        self.ctx_index.insert(c, id);
        id
    }

    // ------------------------------------------------------- constructors

    /// One symbol from `set` (restricted to the universe).
    pub fn class(&mut self, set: &CharSet) -> TermId {
        let s = set.intersect(&self.universe);
        if s.is_empty() {
            self.empty
        } else {
            self.intern(TermKind::Class(s))
        }
    }

    /// Any one symbol of the universe.
    pub fn any_symbol(&mut self) -> TermId {
        let u = self.universe.clone();
        self.class(&u)
    }

    /// Concatenation of `factors`, right-nested and normalised. Iterative along
    /// the sequence, so long chains cannot overflow the stack.
    pub fn concat_all(&mut self, factors: &[TermId]) -> TermId {
        let mut acc = self.epsilon;
        for &f in factors.iter().rev() {
            acc = self.prepend(f, acc);
        }
        acc
    }

    /// `f · acc`, expanding `f`'s own concatenation chain.
    fn prepend(&mut self, f: TermId, acc: TermId) -> TermId {
        if f == self.empty || acc == self.empty {
            return self.empty;
        }
        let mut items = Vec::new();
        let mut cur = f;
        loop {
            match self.kind(cur) {
                TermKind::Concat(a, b) => {
                    items.push(*a);
                    cur = *b;
                }
                TermKind::Epsilon => break,
                _ => {
                    items.push(cur);
                    break;
                }
            }
        }
        let mut acc = acc;
        for &item in items.iter().rev() {
            acc = self.cons(item, acc);
        }
        acc
    }

    /// One factor in front of a continuation (no rewriting: lookaheads are
    /// resolved by the continuation-passing derivative).
    fn cons(&mut self, f: TermId, acc: TermId) -> TermId {
        if acc == self.empty || f == self.empty {
            return self.empty;
        }
        if acc == self.epsilon {
            return f;
        }
        self.intern(TermKind::Concat(f, acc))
    }

    /// Binary concatenation.
    pub fn concat(&mut self, a: TermId, b: TermId) -> TermId {
        self.prepend(a, b)
    }

    /// Union, flattened, sorted and de-duplicated; classes are merged.
    pub fn union(&mut self, items: &[TermId]) -> TermId {
        let mut flat: Vec<TermId> = Vec::new();
        let mut merged = CharSet::empty();
        for &t in items {
            self.collect_union(t, &mut flat, &mut merged);
        }
        if flat.contains(&self.universal) {
            return self.universal;
        }
        if !merged.is_empty() {
            let c = self.class(&merged);
            flat.push(c);
        }
        flat.sort_unstable();
        flat.dedup();
        match flat.len() {
            0 => self.empty,
            1 => flat[0],
            _ => self.intern(TermKind::Union(flat.into())),
        }
    }

    fn collect_union(&self, t: TermId, flat: &mut Vec<TermId>, merged: &mut CharSet) {
        match self.kind(t) {
            TermKind::Empty => {}
            TermKind::Union(v) => {
                for &x in v.iter() {
                    self.collect_union(x, flat, merged);
                }
            }
            TermKind::Class(s) => *merged = merged.union(s),
            _ => flat.push(t),
        }
    }

    /// Intersection, flattened, sorted and de-duplicated; classes are merged.
    pub fn inter(&mut self, items: &[TermId]) -> TermId {
        let mut flat: Vec<TermId> = Vec::new();
        let mut merged: Option<CharSet> = None;
        for &t in items {
            if !self.collect_inter(t, &mut flat, &mut merged) {
                return self.empty;
            }
        }
        if let Some(m) = merged {
            let c = self.class(&m);
            if c == self.empty {
                return self.empty;
            }
            flat.push(c);
        }
        flat.sort_unstable();
        flat.dedup();
        // x & !x is empty.
        for &t in &flat {
            if let TermKind::Not(y) = self.kind(t) {
                if flat.contains(y) {
                    return self.empty;
                }
            }
        }
        match flat.len() {
            0 => self.universal,
            1 => flat[0],
            _ => self.intern(TermKind::Inter(flat.into())),
        }
    }

    /// Returns false when the intersection is certainly empty.
    fn collect_inter(
        &self,
        t: TermId,
        flat: &mut Vec<TermId>,
        merged: &mut Option<CharSet>,
    ) -> bool {
        match self.kind(t) {
            TermKind::Empty => return false,
            TermKind::Inter(v) => {
                for &x in v.iter() {
                    if !self.collect_inter(x, flat, merged) {
                        return false;
                    }
                }
            }
            TermKind::Class(s) => {
                *merged = Some(match merged.take() {
                    Some(m) => m.intersect(s),
                    None => s.clone(),
                });
            }
            _ if t == self.universal => {}
            _ => flat.push(t),
        }
        true
    }

    /// Kleene star.
    pub fn star(&mut self, t: TermId) -> TermId {
        match self.kind(t).clone() {
            TermKind::Empty | TermKind::Epsilon => self.epsilon,
            TermKind::Star(_) => t,
            // Repeating something that cannot consume input adds nothing to the
            // language: zero repetitions are always allowed.
            _ if !self.may_consume(t) => self.epsilon,
            // (e|x)* = x*: drop epsilon from a union body.
            TermKind::Union(v) if v.contains(&self.epsilon) => {
                let rest: Vec<TermId> = v.iter().copied().filter(|&x| x != self.epsilon).collect();
                let u = self.union(&rest);
                self.star(u)
            }
            _ => self.intern(TermKind::Star(t)),
        }
    }

    /// Complement.
    pub fn not(&mut self, t: TermId) -> TermId {
        match self.kind(t) {
            TermKind::Not(x) => *x,
            _ => self.intern(TermKind::Not(t)),
        }
    }

    /// `x?`
    pub fn opt(&mut self, t: TermId) -> TermId {
        let e = self.epsilon;
        self.union(&[e, t])
    }

    // --------------------------------------------------- zero-width terms

    fn aux_set(&mut self, set: &CharSet) -> Option<u8> {
        if let Some(i) = self.aux_sets.iter().position(|s| s == set) {
            return Some(i as u8);
        }
        if self.aux_sets.len() >= MAX_AUX {
            return None;
        }
        self.aux_sets.push(set.clone());
        Some((self.aux_sets.len() - 1) as u8)
    }

    /// An assertion. `word` is the word-character set for word assertions,
    /// `line` the line-terminator set for line assertions. `None` when too many
    /// distinct sets are in use.
    pub fn assertion(
        &mut self,
        kind: AssertKind,
        word: Option<&CharSet>,
        line: Option<&CharSet>,
    ) -> Option<TermId> {
        let w = match (kind, word) {
            (
                AssertKind::WordBoundary
                | AssertKind::NotWordBoundary
                | AssertKind::WordStart
                | AssertKind::WordEnd,
                Some(s),
            ) => self.aux_set(s)?,
            _ => NO_AUX,
        };
        let l = match (kind, line) {
            (AssertKind::LineStart | AssertKind::LineEnd, Some(s)) => self.aux_set(s)?,
            _ => NO_AUX,
        };
        Some(self.intern(TermKind::Assert {
            kind,
            word: w,
            line: l,
        }))
    }

    /// `(?=body)` or `(?!body)`; the body is a complete pattern.
    pub fn look_ahead(&mut self, neg: bool, body: TermId) -> TermId {
        self.intern(TermKind::LookAhead { neg, body })
    }

    /// `(?<=body)` or `(?<!body)`. `None` when the body is context-dependent or
    /// too many trackers are in use.
    pub fn look_behind(&mut self, neg: bool, body: TermId) -> Option<TermId> {
        if self.ctx_dep(body) {
            return None;
        }
        let tracker = match self.trackers.iter().position(|t| t.body == body) {
            Some(i) => i,
            None => {
                if self.trackers.len() >= MAX_TRACKERS {
                    return None;
                }
                let any = self.any_symbol();
                let sigma = self.star(any);
                let root = self.concat_all(&[sigma, body]);
                self.trackers.push(Tracker { body, root });
                self.trackers.len() - 1
            }
        };
        Some(self.intern(TermKind::LookBehind {
            neg,
            tracker: tracker as u8,
        }))
    }

    // ------------------------------------------------------------ context

    /// Context before any input has been consumed.
    pub fn ctx_start(&mut self) -> u32 {
        let tracks = self.trackers.iter().map(|t| t.root).collect();
        self.intern_ctx(Ctx {
            start: true,
            bits: 0,
            tracks,
        })
    }

    /// The context object for an id.
    pub fn ctx(&self, id: u32) -> &Ctx {
        &self.ctxs[id as usize]
    }

    /// Context after consuming symbol `c` in context `id`.
    pub fn advance_ctx(&mut self, id: u32, c: u32) -> u32 {
        let cur = self.ctxs[id as usize].clone();
        let mut bits = 0u64;
        for (i, s) in self.aux_sets.iter().enumerate() {
            if s.contains(c) {
                bits |= 1 << i;
            }
        }
        let tracks: Vec<TermId> = cur
            .tracks
            .iter()
            .map(|&t| self.deriv_in(t, c, NO_CTX))
            .collect();
        self.intern_ctx(Ctx {
            start: false,
            bits,
            tracks,
        })
    }

    fn eval_assert(&self, kind: AssertKind, w: u8, l: u8, ctx: &Ctx, next: Option<u32>) -> bool {
        let in_next =
            |id: u8| id != NO_AUX && next.is_some_and(|c| self.aux_sets[id as usize].contains(c));
        let in_prev = |id: u8| id != NO_AUX && (ctx.bits >> id) & 1 == 1;
        match kind {
            AssertKind::TextStart => ctx.start,
            AssertKind::TextEnd => next.is_none(),
            AssertKind::LineStart => ctx.start || in_prev(l),
            AssertKind::LineEnd => next.is_none() || in_next(l),
            AssertKind::WordBoundary => in_prev(w) != in_next(w),
            AssertKind::NotWordBoundary => in_prev(w) == in_next(w),
            AssertKind::WordStart => !in_prev(w) && in_next(w),
            AssertKind::WordEnd => in_prev(w) && !in_next(w),
        }
    }

    /// Does `t` accept the empty remainder at a position described by `ctx`,
    /// when the next input symbol is `next` (`None` = end of input)?
    pub fn nullable_in(&self, t: TermId, ctx: &Ctx, next: Option<u32>) -> bool {
        let mut cur = t;
        loop {
            let node = &self.nodes[cur.index()];
            if !node.ctx_dep {
                return node.nullable;
            }
            return match &node.kind {
                TermKind::Concat(a, b) => {
                    if !self.nullable_in(*a, ctx, next) {
                        return false;
                    }
                    cur = *b;
                    continue;
                }
                TermKind::Union(v) => v.iter().any(|&x| self.nullable_in(x, ctx, next)),
                TermKind::Inter(v) => v.iter().all(|&x| self.nullable_in(x, ctx, next)),
                TermKind::Not(x) => !self.nullable_in(*x, ctx, next),
                TermKind::Star(_) => true,
                TermKind::Assert { kind, word, line } => {
                    self.eval_assert(*kind, *word, *line, ctx, next)
                }
                // A lookahead with nothing after it needs the remainder to be empty.
                TermKind::LookAhead { neg, body } => {
                    next.is_none() && (self.nullable_in(*body, ctx, None) != *neg)
                }
                TermKind::LookBehind { neg, tracker } => {
                    let holds = ctx
                        .tracks
                        .get(*tracker as usize)
                        .is_some_and(|&t| self.nodes[t.index()].nullable);
                    holds != *neg
                }
                TermKind::Empty | TermKind::Class(_) => false,
                TermKind::Epsilon => true,
            };
        }
    }

    /// Acceptance at the end of input in context `ctx_id`.
    pub fn accepting(&self, t: TermId, ctx_id: u32) -> bool {
        self.nullable_in(t, &self.ctxs[ctx_id as usize], None)
    }

    // --------------------------------------------------------- derivatives

    /// Derivative of `t` with respect to `c`, for terms that do not depend on
    /// context. For general terms use [`TermStore::deriv_in`].
    pub fn deriv(&mut self, t: TermId, c: u32) -> TermId {
        self.deriv_in(t, c, NO_CTX)
    }

    /// Brzozowski derivative of `t` with respect to the symbol `c`, where the
    /// input so far is described by context `ctx_id`.
    ///
    /// Iterative (explicit work stack): terms from counted repetition are
    /// thousands of levels deep, and recursion would overflow the stack
    /// (NFR-R01).
    pub fn deriv_in(&mut self, t: TermId, c: u32, ctx_id: u32) -> TermId {
        enum Step {
            Enter(TermId),
            Exit(TermId),
        }
        if self.nodes[t.index()].has_look {
            return self.deriv_look(t, c, ctx_id);
        }
        let ctx = self.ctxs[ctx_id as usize].clone();
        let key = |s: &Self, x: TermId| (x, c, if s.ctx_dep(x) { ctx_id } else { NO_CTX });
        let mut stack = vec![Step::Enter(t)];
        while let Some(step) = stack.pop() {
            match step {
                Step::Enter(x) => {
                    if self.deriv_cache.contains_key(&key(self, x)) {
                        continue;
                    }
                    match self.kind(x).clone() {
                        TermKind::Empty
                        | TermKind::Epsilon
                        | TermKind::Assert { .. }
                        | TermKind::LookAhead { .. }
                        | TermKind::LookBehind { .. } => {
                            let k = key(self, x);
                            self.deriv_cache.insert(k, self.empty);
                        }
                        TermKind::Class(s) => {
                            let r = if s.contains(c) {
                                self.epsilon
                            } else {
                                self.empty
                            };
                            let k = key(self, x);
                            self.deriv_cache.insert(k, r);
                        }
                        TermKind::Concat(a, b) => {
                            stack.push(Step::Exit(x));
                            stack.push(Step::Enter(a));
                            if self.nullable_in(a, &ctx, Some(c)) {
                                stack.push(Step::Enter(b));
                            }
                        }
                        TermKind::Union(v) | TermKind::Inter(v) => {
                            stack.push(Step::Exit(x));
                            stack.extend(v.iter().map(|&y| Step::Enter(y)));
                        }
                        TermKind::Star(y) | TermKind::Not(y) => {
                            stack.push(Step::Exit(x));
                            stack.push(Step::Enter(y));
                        }
                    }
                }
                Step::Exit(x) => {
                    // Every child was resolved before this frame ran.
                    let d = |s: &Self, y: TermId| s.deriv_cache[&key(s, y)];
                    let r = match self.kind(x).clone() {
                        TermKind::Concat(a, b) => {
                            let left = self.concat(d(self, a), b);
                            if self.nullable_in(a, &ctx, Some(c)) {
                                let db = d(self, b);
                                self.union(&[left, db])
                            } else {
                                left
                            }
                        }
                        TermKind::Union(v) => {
                            let ds: Vec<TermId> = v.iter().map(|&y| d(self, y)).collect();
                            self.union(&ds)
                        }
                        TermKind::Inter(v) => {
                            let ds: Vec<TermId> = v.iter().map(|&y| d(self, y)).collect();
                            self.inter(&ds)
                        }
                        TermKind::Star(y) => self.concat(d(self, y), x),
                        TermKind::Not(y) => self.not(d(self, y)),
                        // Leaves never push an Exit frame.
                        _ => self.empty,
                    };
                    let k = key(self, x);
                    self.deriv_cache.insert(k, r);
                }
            }
        }
        self.deriv_cache[&key(self, t)]
    }

    /// Can the term match a non-empty string? (Conservative: `true` when unsure.)
    pub fn may_consume(&self, t: TermId) -> bool {
        match self.kind(t) {
            TermKind::Empty
            | TermKind::Epsilon
            | TermKind::Assert { .. }
            | TermKind::LookAhead { .. }
            | TermKind::LookBehind { .. } => false,
            TermKind::Class(_) | TermKind::Inter(_) | TermKind::Not(_) => true,
            TermKind::Concat(a, b) => self.may_consume(*a) || self.may_consume(*b),
            TermKind::Union(v) => v.iter().any(|&x| self.may_consume(x)),
            TermKind::Star(x) => self.may_consume(*x),
        }
    }

    /// Derivative of a term that contains lookaheads (see the module notes).
    fn deriv_look(&mut self, t: TermId, c: u32, ctx_id: u32) -> TermId {
        let key = (t, c, ctx_id);
        if let Some(&r) = self.look_cache.get(&key) {
            return r;
        }
        let ctx = self.ctxs[ctx_id as usize].clone();
        let mut guard = std::collections::HashSet::new();
        let eps = self.epsilon;
        let r = self.dk(t, eps, c, &ctx, ctx_id, &mut guard);
        self.look_cache.insert(key, r);
        r
    }

    /// Derivative of `t · k` with respect to `c`.
    fn dk(
        &mut self,
        t: TermId,
        k: TermId,
        c: u32,
        ctx: &Ctx,
        ctx_id: u32,
        guard: &mut std::collections::HashSet<(TermId, TermId)>,
    ) -> TermId {
        // Without lookaheads on either side the ordinary derivative applies.
        if !self.nodes[t.index()].has_look && !self.nodes[k.index()].has_look {
            let tk = self.concat(t, k);
            return self.deriv_in(tk, c, ctx_id);
        }
        if !guard.insert((t, k)) {
            return self.empty; // zero-width cycle: least fixpoint
        }
        let eps = self.epsilon;
        let r = match self.kind(t).clone() {
            TermKind::Class(s) => {
                if s.contains(c) {
                    k
                } else {
                    self.empty
                }
            }
            TermKind::Empty
            | TermKind::Epsilon
            | TermKind::Assert { .. }
            | TermKind::LookBehind { .. } => self.empty,
            TermKind::Concat(a, b) => {
                let bk = self.concat(b, k);
                let left = self.dk(a, bk, c, ctx, ctx_id, guard);
                if self.nullable_in(a, ctx, Some(c)) {
                    let right = self.dk(b, k, c, ctx, ctx_id, guard);
                    self.union(&[left, right])
                } else {
                    left
                }
            }
            TermKind::Union(v) => {
                let ds: Vec<TermId> = v
                    .iter()
                    .map(|&x| self.dk(x, k, c, ctx, ctx_id, guard))
                    .collect();
                self.union(&ds)
            }
            TermKind::Star(x) => {
                let tk = self.concat(t, k);
                self.dk(x, tk, c, ctx, ctx_id, guard)
            }
            TermKind::Inter(v) => {
                let ds: Vec<TermId> = v
                    .iter()
                    .map(|&x| self.dk(x, eps, c, ctx, ctx_id, guard))
                    .collect();
                let inner = self.inter(&ds);
                self.concat(inner, k)
            }
            TermKind::Not(x) => {
                let d = self.dk(x, eps, c, ctx, ctx_id, guard);
                let inner = self.not(d);
                self.concat(inner, k)
            }
            TermKind::LookAhead { neg, body } => {
                // (?=X)·k = (X·Σ*) ∩ k  and  (?!X)·k = ¬(X·Σ*) ∩ k
                let any = self.any_symbol();
                let sigma = self.star(any);
                let reach = self.concat_all(&[body, sigma]);
                let dreach = self.dk(reach, eps, c, ctx, ctx_id, guard);
                let dcond = if neg { self.not(dreach) } else { dreach };
                let dk_ = self.dk(k, eps, c, ctx, ctx_id, guard);
                self.inter(&[dcond, dk_])
            }
        };
        guard.remove(&(t, k));
        r
    }

    // ------------------------------------------------------- serialisation

    fn ranges_text(s: &CharSet) -> String {
        let mut out = String::from("[");
        for (i, &(lo, hi)) in s.ranges().iter().enumerate() {
            if i > 0 {
                out.push(',');
            }
            if lo == hi {
                out.push_str(&format!("{lo:X}"));
            } else {
                out.push_str(&format!("{lo:X}-{hi:X}"));
            }
        }
        out.push(']');
        out
    }

    /// Serialise a term in the documented interchange format shared with the
    /// independent checker: `0` empty, `e` epsilon, `[lo-hi,lo]` hex ranges,
    /// `(. a b)` concatenation, `(| ...)` union, `(& ...)` intersection,
    /// `(* a)` star, `(! a)` complement, `(#K w l)` assertion (`_` for an
    /// unused set), `(?= x)` / `(?! x)` lookahead and `(<= x)` / `(<! x)`
    /// lookbehind. Iterative, so deep terms are fine.
    pub fn to_spec(&self, t: TermId) -> String {
        enum Item {
            T(TermId),
            S(&'static str),
        }
        let mut out = String::new();
        let mut stack = vec![Item::T(t)];
        while let Some(item) = stack.pop() {
            match item {
                Item::S(s) => out.push_str(s),
                Item::T(x) => match self.kind(x) {
                    TermKind::Empty => out.push('0'),
                    TermKind::Epsilon => out.push('e'),
                    TermKind::Class(s) => out.push_str(&Self::ranges_text(s)),
                    TermKind::Concat(a, b) => {
                        out.push_str("(. ");
                        stack.push(Item::S(")"));
                        stack.push(Item::T(*b));
                        stack.push(Item::S(" "));
                        stack.push(Item::T(*a));
                    }
                    TermKind::Union(v) | TermKind::Inter(v) => {
                        out.push_str(if matches!(self.kind(x), TermKind::Union(_)) {
                            "(|"
                        } else {
                            "(&"
                        });
                        stack.push(Item::S(")"));
                        for &y in v.iter().rev() {
                            stack.push(Item::T(y));
                            stack.push(Item::S(" "));
                        }
                    }
                    TermKind::Star(y) => {
                        out.push_str("(* ");
                        stack.push(Item::S(")"));
                        stack.push(Item::T(*y));
                    }
                    TermKind::Not(y) => {
                        out.push_str("(! ");
                        stack.push(Item::S(")"));
                        stack.push(Item::T(*y));
                    }
                    TermKind::Assert { kind, word, line } => {
                        let set = |i: u8| {
                            if i == NO_AUX {
                                "_".to_string()
                            } else {
                                Self::ranges_text(&self.aux_sets[i as usize])
                            }
                        };
                        out.push_str(&format!(
                            "(#{} {} {})",
                            kind.letter(),
                            set(*word),
                            set(*line)
                        ));
                    }
                    TermKind::LookAhead { neg, body } => {
                        out.push_str(if *neg { "(?! " } else { "(?= " });
                        stack.push(Item::S(")"));
                        stack.push(Item::T(*body));
                    }
                    TermKind::LookBehind { neg, tracker } => {
                        out.push_str(if *neg { "(<! " } else { "(<= " });
                        stack.push(Item::S(")"));
                        if let Some(b) = self.tracker_body(*tracker) {
                            stack.push(Item::T(b));
                        }
                    }
                },
            }
        }
        out
    }

    // ----------------------------------------------------------- partition

    /// Coarsest partition of the universe such that every class set occurring
    /// in `t` (including the sets used by assertions) is a union of blocks (the
    /// term's symbol classes, FR-B02). Blocks are ordered by smallest member.
    /// Derivatives never introduce new sets, so the partition of the start term
    /// serves for the whole automaton. Iterative for the same reason as
    /// [`TermStore::deriv_in`].
    pub fn partition(&mut self, t: TermId) -> Arc<Vec<CharSet>> {
        enum Step {
            Enter(TermId),
            Exit(TermId),
        }
        let mut stack = vec![Step::Enter(t)];
        while let Some(step) = stack.pop() {
            match step {
                Step::Enter(x) => {
                    if self.part_cache.contains_key(&x) {
                        continue;
                    }
                    match self.kind(x).clone() {
                        TermKind::Empty | TermKind::Epsilon => {
                            let whole = Arc::new(vec![self.universe.clone()]);
                            self.part_cache.insert(x, whole);
                        }
                        TermKind::Class(s) => {
                            let rest = self.universe.difference(&s);
                            let mut v = vec![s];
                            if !rest.is_empty() {
                                v.push(rest);
                            }
                            v.sort_by_key(|b| b.smallest());
                            self.part_cache.insert(x, Arc::new(v));
                        }
                        TermKind::Assert { word, line, .. } => {
                            let mut p = vec![self.universe.clone()];
                            for id in [word, line] {
                                if id != NO_AUX {
                                    p = refine(&p, &self.aux_sets[id as usize]);
                                }
                            }
                            p.sort_by_key(|b| b.smallest());
                            self.part_cache.insert(x, Arc::new(p));
                        }
                        TermKind::Concat(a, b) => {
                            stack.push(Step::Exit(x));
                            stack.push(Step::Enter(a));
                            stack.push(Step::Enter(b));
                        }
                        TermKind::Union(v) | TermKind::Inter(v) => {
                            stack.push(Step::Exit(x));
                            stack.extend(v.iter().map(|&y| Step::Enter(y)));
                        }
                        TermKind::Star(y)
                        | TermKind::Not(y)
                        | TermKind::LookAhead { body: y, .. } => {
                            stack.push(Step::Exit(x));
                            stack.push(Step::Enter(y));
                        }
                        TermKind::LookBehind { tracker, .. } => {
                            stack.push(Step::Exit(x));
                            if let Some(b) = self.tracker_body(tracker) {
                                stack.push(Step::Enter(b));
                            }
                        }
                    }
                }
                Step::Exit(x) => {
                    let p: Vec<CharSet> = match self.kind(x).clone() {
                        TermKind::Concat(a, b) => {
                            refine_all(&self.part_cache[&a], &self.part_cache[&b])
                        }
                        TermKind::Union(v) | TermKind::Inter(v) => {
                            let mut acc = vec![self.universe.clone()];
                            for y in v.iter() {
                                acc = refine_all(&acc, &self.part_cache[y]);
                            }
                            acc
                        }
                        TermKind::Star(y)
                        | TermKind::Not(y)
                        | TermKind::LookAhead { body: y, .. } => (*self.part_cache[&y]).clone(),
                        TermKind::LookBehind { tracker, .. } => match self.tracker_body(tracker) {
                            Some(b) => (*self.part_cache[&b]).clone(),
                            None => vec![self.universe.clone()],
                        },
                        _ => vec![self.universe.clone()],
                    };
                    self.part_cache.insert(x, Arc::new(p));
                }
            }
        }
        self.part_cache[&t].clone()
    }
}

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

    fn store() -> TermStore {
        TermStore::new(CharSet::range(0, 0x7F))
    }
    fn ch(s: &mut TermStore, c: char) -> TermId {
        s.class(&CharSet::single(c as u32))
    }

    #[test]
    fn interning_gives_one_id_per_term() {
        let mut s = store();
        let (a1, a2) = (ch(&mut s, 'a'), ch(&mut s, 'a'));
        assert_eq!(a1, a2);
    }

    #[test]
    fn normalisation_laws() {
        let mut s = store();
        let (a, b, c) = (ch(&mut s, 'a'), ch(&mut s, 'b'), ch(&mut s, 'c'));
        let (e, z) = (s.epsilon(), s.empty());
        // union: idempotent, commutative, associative, absorbs Empty
        assert_eq!(s.union(&[a, a]), a);
        assert_eq!(s.union(&[a, b]), s.union(&[b, a]));
        let ab = s.union(&[a, b]);
        let bc = s.union(&[b, c]);
        assert_eq!(s.union(&[ab, c]), s.union(&[a, bc]));
        assert_eq!(s.union(&[a, z]), a);
        // concat: identity, annihilator, associativity
        assert_eq!(s.concat(a, e), a);
        assert_eq!(s.concat(e, a), a);
        assert_eq!(s.concat(a, z), z);
        let (x, y) = (s.concat(a, b), s.concat(b, c));
        assert_eq!(s.concat(x, c), s.concat(a, y));
        // star, not
        let sa = s.star(a);
        assert_eq!(s.star(sa), sa);
        assert_eq!(s.star(z), e);
        let na = s.not(a);
        assert_eq!(s.not(na), a);
        let u = s.universal();
        assert_eq!(s.union(&[a, u]), u);
        assert_eq!(s.inter(&[a, u]), a);
        assert_eq!(s.inter(&[a, na]), z);
        // classes merge: a|b is the single class [ab]
        assert!(matches!(s.kind(ab), TermKind::Class(set) if set.count() == 2));
    }

    #[test]
    fn nullable_follows_the_definitions() {
        let mut s = store();
        let a = ch(&mut s, 'a');
        let (e, z) = (s.epsilon(), s.empty());
        let sa = s.star(a);
        let na = s.not(a);
        assert!(!s.nullable(a) && s.nullable(e) && !s.nullable(z) && s.nullable(sa));
        assert!(s.nullable(na)); // "" is not 'a'
        let u = s.universal();
        assert!(s.nullable(u));
    }

    #[test]
    fn derivative_of_a_star_b() {
        let mut s = store();
        let (a, b) = (ch(&mut s, 'a'), ch(&mut s, 'b'));
        let sa = s.star(a);
        let t = s.concat(sa, b); // a*b
        assert_eq!(s.deriv(t, 'a' as u32), t);
        assert_eq!(s.deriv(t, 'b' as u32), s.epsilon());
        assert_eq!(s.deriv(t, 'c' as u32), s.empty());
    }

    #[test]
    fn partition_separates_exactly_what_the_term_distinguishes() {
        let mut s = store();
        let (a, b) = (ch(&mut s, 'a'), ch(&mut s, 'b'));
        let t = s.concat(a, b);
        let p = s.partition(t);
        // {a}, {b}, everything else
        assert_eq!(p.len(), 3);
        assert_eq!(p.iter().map(|x| x.count()).sum::<u64>(), 128);
    }

    #[test]
    fn long_concat_chain_does_not_recurse() {
        let mut s = store();
        let a = ch(&mut s, 'a');
        let t = s.concat_all(&vec![a; 100_000]);
        assert!(!s.nullable(t));
    }
}