rexact-check 0.2.0

//! The checker's own term type, normaliser, derivative and spec parser.
//!
//! Written independently of `rexact-core` on purpose: plain reference-counted
//! trees, string keys, no interning, no caches. Normalisation applies the same
//! documented laws as the engine (flatten/sort/dedup union and intersection,
//! absorb empty and epsilon, right-nest concatenation, `(x*)* = x*`,
//! `!!x = x`) so that a certificate's pairs can be compared by key.

use crate::{malformed, CheckError};
use std::rc::Rc;

pub type Ranges = Vec<(u32, u32)>;

pub enum K {
    Empty,
    Eps,
    Set(Ranges),
    Cat(T, T),
    Alt(Vec<T>),
    Star(T),
    And(Vec<T>),
    Not(T),
    /// Anchor or boundary; the optional sets are the word / line definitions.
    Assert(char, Option<Ranges>, Option<Ranges>),
    /// `(?=x)` / `(?!x)`.
    Ahead(bool, T),
    /// `(?<=x)` / `(?<!x)`; `x` is a context-free body.
    Behind(bool, T),
}

pub struct N {
    pub k: K,
    /// Canonical text of the term; equal keys mean equal normalised terms.
    pub key: String,
    /// Acceptance of the empty string, ignoring context (exact when `!dep`).
    pub nullable: bool,
    /// Contains an assertion or lookaround.
    pub dep: bool,
    /// Contains a lookahead.
    pub look: bool,
}

pub type T = Rc<N>;

fn mk(k: K, key: String, nullable: bool) -> T {
    let dep = match &k {
        K::Empty | K::Eps | K::Set(_) => false,
        K::Cat(a, b) => a.dep || b.dep,
        K::Alt(v) | K::And(v) => v.iter().any(|x| x.dep),
        K::Star(x) | K::Not(x) => x.dep,
        K::Assert(..) | K::Ahead(..) | K::Behind(..) => true,
    };
    let look = match &k {
        K::Ahead(..) => true,
        K::Empty | K::Eps | K::Set(_) | K::Assert(..) | K::Behind(..) => false,
        K::Cat(a, b) => a.look || b.look,
        K::Alt(v) | K::And(v) => v.iter().any(|x| x.look),
        K::Star(x) | K::Not(x) => x.look,
    };
    Rc::new(N {
        k,
        key,
        nullable,
        dep,
        look,
    })
}

/// Can the term match a non-empty string? (Conservative: true when unsure.)
pub fn may_consume(t: &T) -> bool {
    match &t.k {
        K::Empty | K::Eps | K::Assert(..) | K::Ahead(..) | K::Behind(..) => false,
        K::Set(_) | K::And(_) | K::Not(_) => true,
        K::Cat(a, b) => may_consume(a) || may_consume(b),
        K::Alt(v) => v.iter().any(may_consume),
        K::Star(x) => may_consume(x),
    }
}

pub fn empty() -> T {
    mk(K::Empty, "0".into(), false)
}
pub fn eps() -> T {
    mk(K::Eps, "e".into(), true)
}
pub fn is_empty(t: &T) -> bool {
    matches!(t.k, K::Empty)
}
pub fn is_universal(t: &T) -> bool {
    matches!(&t.k, K::Not(x) if is_empty(x))
}

// ------------------------------------------------------------ range sets

pub fn norm_ranges(mut v: Ranges) -> Ranges {
    v.retain(|r| r.0 <= r.1);
    v.sort_unstable();
    let mut out: Ranges = Vec::new();
    for (lo, hi) in v {
        match out.last_mut() {
            Some(last) if lo <= last.1.saturating_add(1) => last.1 = last.1.max(hi),
            _ => out.push((lo, hi)),
        }
    }
    out
}

pub fn ranges_intersect(a: &Ranges, b: &Ranges) -> Ranges {
    let mut out = Vec::new();
    for &(al, ah) in a {
        for &(bl, bh) in b {
            let (lo, hi) = (al.max(bl), ah.min(bh));
            if lo <= hi {
                out.push((lo, hi));
            }
        }
    }
    norm_ranges(out)
}

pub fn contains(r: &Ranges, c: u32) -> bool {
    r.iter().any(|&(lo, hi)| lo <= c && c <= hi)
}

fn ranges_key(r: &Ranges) -> String {
    let parts: Vec<String> = r
        .iter()
        .map(|&(lo, hi)| {
            if lo == hi {
                format!("{lo:X}")
            } else {
                format!("{lo:X}-{hi:X}")
            }
        })
        .collect();
    format!("[{}]", parts.join(","))
}

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

pub fn set(r: Ranges) -> T {
    let r = norm_ranges(r);
    if r.is_empty() {
        return empty();
    }
    let key = ranges_key(&r);
    mk(K::Set(r), key, false)
}

pub fn cat(a: T, b: T) -> T {
    if is_empty(&a) || is_empty(&b) {
        return empty();
    }
    if matches!(a.k, K::Eps) {
        return b;
    }
    if matches!(b.k, K::Eps) {
        return a;
    }
    if let K::Cat(x, y) = &a.k {
        return cat(x.clone(), cat(y.clone(), b));
    }
    let key = format!("(. {} {})", a.key, b.key);
    let nullable = a.nullable && b.nullable;
    mk(K::Cat(a, b), key, nullable)
}

fn join(tag: &str, items: &[T]) -> String {
    let mut s = format!("({tag}");
    for i in items {
        s.push(' ');
        s.push_str(&i.key);
    }
    s.push(')');
    s
}

pub fn alt(items: Vec<T>) -> T {
    let mut flat: Vec<T> = Vec::new();
    let mut merged: Ranges = Vec::new();
    let mut stack: Vec<T> = items;
    stack.reverse();
    while let Some(t) = stack.pop() {
        match &t.k {
            K::Empty => {}
            K::Alt(v) => stack.extend(v.iter().rev().cloned()),
            K::Set(r) => merged.extend(r.iter().copied()),
            _ => flat.push(t),
        }
    }
    if flat.iter().any(is_universal) {
        return not(empty());
    }
    if !merged.is_empty() {
        flat.push(set(merged));
    }
    flat.sort_by(|a, b| a.key.cmp(&b.key));
    flat.dedup_by(|a, b| a.key == b.key);
    match flat.len() {
        0 => empty(),
        1 => flat.remove(0),
        _ => {
            let key = join("|", &flat);
            let nullable = flat.iter().any(|t| t.nullable);
            mk(K::Alt(flat), key, nullable)
        }
    }
}

pub fn and(items: Vec<T>) -> T {
    let mut flat: Vec<T> = Vec::new();
    let mut merged: Option<Ranges> = None;
    let mut stack: Vec<T> = items;
    stack.reverse();
    while let Some(t) = stack.pop() {
        match &t.k {
            K::Empty => return empty(),
            K::And(v) => stack.extend(v.iter().rev().cloned()),
            K::Set(r) => {
                merged = Some(match merged.take() {
                    Some(m) => ranges_intersect(&m, r),
                    None => r.clone(),
                })
            }
            _ if is_universal(&t) => {}
            _ => flat.push(t),
        }
    }
    if let Some(m) = merged {
        if m.is_empty() {
            return empty();
        }
        flat.push(set(m));
    }
    flat.sort_by(|a, b| a.key.cmp(&b.key));
    flat.dedup_by(|a, b| a.key == b.key);
    for t in &flat {
        if let K::Not(y) = &t.k {
            if flat.iter().any(|z| z.key == y.key) {
                return empty();
            }
        }
    }
    match flat.len() {
        0 => not(empty()),
        1 => flat.remove(0),
        _ => {
            let key = join("&", &flat);
            let nullable = flat.iter().all(|t| t.nullable);
            mk(K::And(flat), key, nullable)
        }
    }
}

pub fn star(a: T) -> T {
    match &a.k {
        K::Empty | K::Eps => eps(),
        K::Star(_) => a,
        _ if !may_consume(&a) => eps(),
        K::Alt(v) if v.iter().any(|x| matches!(x.k, K::Eps)) => {
            let rest: Vec<T> = v
                .iter()
                .filter(|x| !matches!(x.k, K::Eps))
                .cloned()
                .collect();
            star(alt(rest))
        }
        _ => {
            let key = format!("(* {})", a.key);
            mk(K::Star(a), key, true)
        }
    }
}

pub fn not(a: T) -> T {
    if let K::Not(x) = &a.k {
        return x.clone();
    }
    let key = format!("(! {})", a.key);
    let nullable = !a.nullable;
    mk(K::Not(a), key, nullable)
}

// ------------------------------------------------------------ derivative

/// Brzozowski derivative by the textbook equations, normalised.
pub fn deriv(t: &T, c: u32) -> T {
    match &t.k {
        K::Empty | K::Eps => empty(),
        K::Set(r) => {
            if contains(r, c) {
                eps()
            } else {
                empty()
            }
        }
        K::Cat(a, b) => {
            let left = cat(deriv(a, c), b.clone());
            if a.nullable {
                alt(vec![left, deriv(b, c)])
            } else {
                left
            }
        }
        K::Alt(v) => alt(v.iter().map(|x| deriv(x, c)).collect()),
        K::And(v) => and(v.iter().map(|x| deriv(x, c)).collect()),
        K::Star(x) => cat(deriv(x, c), t.clone()),
        K::Not(x) => not(deriv(x, c)),
        K::Assert(..) | K::Ahead(..) | K::Behind(..) => empty(),
    }
}

pub fn assert_t(k: char, w: Option<Ranges>, l: Option<Ranges>) -> T {
    let show = |o: &Option<Ranges>| o.as_ref().map_or("_".to_string(), ranges_key);
    let key = format!("(#{} {} {})", k, show(&w), show(&l));
    mk(K::Assert(k, w, l), key, false)
}
pub fn ahead(neg: bool, b: T) -> T {
    let key = format!("({} {})", if neg { "?!" } else { "?=" }, b.key);
    mk(K::Ahead(neg, b), key, false)
}
pub fn behind(neg: bool, b: T) -> T {
    let key = format!("({} {})", if neg { "<!" } else { "<=" }, b.key);
    mk(K::Behind(neg, b), key, false)
}

// ----------------------------------------------------- context semantics

/// The input consumed so far, as far as zero-width constructs can see it.
#[derive(Clone)]
pub struct Ctx {
    pub start: bool,
    /// Bit i: the previous character belongs to `World::aux[i]`.
    pub bits: u64,
    /// One state per tracker body: the derivative of `Sigma*` followed by the body.
    pub tracks: Vec<T>,
}

impl Ctx {
    pub fn key(&self) -> String {
        let t: Vec<&str> = self.tracks.iter().map(|x| x.key.as_str()).collect();
        format!("{}|{}|{}", self.start, self.bits, t.join(";"))
    }
}

/// Definitions shared by a whole certificate.
pub struct World {
    pub universe: Ranges,
    pub aux: Vec<Ranges>,
    pub trackers: Vec<T>,
}

impl World {
    fn aux_index(&self, r: &Ranges) -> Option<usize> {
        self.aux.iter().position(|a| a == r)
    }
    fn tracker_index(&self, b: &T) -> Option<usize> {
        self.trackers.iter().position(|t| t.key == b.key)
    }
    pub fn sigma_star(&self) -> T {
        star(set(self.universe.clone()))
    }
    pub fn advance(&self, ctx: &Ctx, c: u32) -> Ctx {
        let mut bits = 0u64;
        for (i, a) in self.aux.iter().enumerate() {
            if contains(a, c) {
                bits |= 1 << i;
            }
        }
        Ctx {
            start: false,
            bits,
            tracks: ctx.tracks.iter().map(|t| deriv(t, c)).collect(),
        }
    }
    /// Every assertion set and lookbehind body of `t` is declared in this world.
    pub fn declares(&self, t: &T) -> bool {
        match &t.k {
            K::Assert(_, w, l) => [w, l]
                .iter()
                .all(|o| o.as_ref().map_or(true, |r| self.aux_index(r).is_some())),
            K::Behind(_, b) => self.tracker_index(b).is_some(),
            K::Ahead(_, x) | K::Star(x) | K::Not(x) => self.declares(x),
            K::Cat(a, b) => self.declares(a) && self.declares(b),
            K::Alt(v) | K::And(v) => v.iter().all(|x| self.declares(x)),
            _ => true,
        }
    }

    fn assert_holds(
        &self,
        k: char,
        w: &Option<Ranges>,
        l: &Option<Ranges>,
        ctx: &Ctx,
        next: Option<u32>,
    ) -> bool {
        let prev_in = |r: &Option<Ranges>| {
            r.as_ref()
                .and_then(|r| self.aux_index(r))
                .is_some_and(|i| (ctx.bits >> i) & 1 == 1)
        };
        let next_in = |r: &Option<Ranges>| match (r, next) {
            (Some(r), Some(c)) => contains(r, c),
            _ => false,
        };
        match k {
            'A' => ctx.start,
            'z' => next.is_none(),
            '^' => ctx.start || prev_in(l),
            '$' => next.is_none() || next_in(l),
            'b' => prev_in(w) != next_in(w),
            'B' => prev_in(w) == next_in(w),
            '<' => !prev_in(w) && next_in(w),
            '>' => prev_in(w) && !next_in(w),
            _ => false,
        }
    }

    /// Does `t` accept the empty remainder here, given the next symbol (None = end)?
    pub fn nullable_in(&self, t: &T, ctx: &Ctx, next: Option<u32>) -> bool {
        if !t.dep {
            return t.nullable;
        }
        match &t.k {
            K::Cat(a, b) => self.nullable_in(a, ctx, next) && self.nullable_in(b, ctx, next),
            K::Alt(v) => v.iter().any(|x| self.nullable_in(x, ctx, next)),
            K::And(v) => v.iter().all(|x| self.nullable_in(x, ctx, next)),
            K::Not(x) => !self.nullable_in(x, ctx, next),
            K::Star(_) | K::Eps => true,
            K::Assert(k, w, l) => self.assert_holds(*k, w, l, ctx, next),
            K::Ahead(neg, b) => next.is_none() && (self.nullable_in(b, ctx, None) != *neg),
            K::Behind(neg, b) => {
                let holds = self
                    .tracker_index(b)
                    .and_then(|i| ctx.tracks.get(i))
                    .is_some_and(|t| t.nullable);
                holds != *neg
            }
            K::Empty | K::Set(_) => false,
        }
    }

    pub fn accepting(&self, t: &T, ctx: &Ctx) -> bool {
        self.nullable_in(t, ctx, None)
    }

    /// Derivative of `t` followed by `k`, by `c`, in context `ctx`.
    pub fn dk(&self, t: &T, k: &T, c: u32, ctx: &Ctx, guard: &mut Vec<(String, String)>) -> T {
        if !t.look && !k.look {
            return self.plain(&cat(t.clone(), k.clone()), c, ctx);
        }
        let id = (t.key.clone(), k.key.clone());
        if guard.contains(&id) {
            return empty(); // zero-width cycle: least fixpoint
        }
        guard.push(id);
        let e = eps();
        let r = match &t.k {
            K::Empty | K::Eps | K::Assert(..) | K::Behind(..) => empty(),
            K::Set(s) => {
                if contains(s, c) {
                    k.clone()
                } else {
                    empty()
                }
            }
            K::Cat(a, b) => {
                let left = self.dk(a, &cat(b.clone(), k.clone()), c, ctx, guard);
                if self.nullable_in(a, ctx, Some(c)) {
                    alt(vec![left, self.dk(b, k, c, ctx, guard)])
                } else {
                    left
                }
            }
            K::Alt(v) => alt(v.iter().map(|x| self.dk(x, k, c, ctx, guard)).collect()),
            K::Star(x) => self.dk(x, &cat(t.clone(), k.clone()), c, ctx, guard),
            K::And(v) => cat(
                and(v.iter().map(|x| self.dk(x, &e, c, ctx, guard)).collect()),
                k.clone(),
            ),
            K::Not(x) => cat(not(self.dk(x, &e, c, ctx, guard)), k.clone()),
            K::Ahead(neg, body) => {
                let reach = cat(body.clone(), self.sigma_star());
                let d = self.dk(&reach, &e, c, ctx, guard);
                let cond = if *neg { not(d) } else { d };
                and(vec![cond, self.dk(k, &e, c, ctx, guard)])
            }
        };
        guard.pop();
        r
    }

    /// The textbook derivative for terms without lookahead.
    fn plain(&self, t: &T, c: u32, ctx: &Ctx) -> T {
        match &t.k {
            K::Empty | K::Eps | K::Assert(..) | K::Behind(..) | K::Ahead(..) => empty(),
            K::Set(s) => {
                if contains(s, c) {
                    eps()
                } else {
                    empty()
                }
            }
            K::Cat(a, b) => {
                let left = cat(self.plain(a, c, ctx), b.clone());
                if self.nullable_in(a, ctx, Some(c)) {
                    alt(vec![left, self.plain(b, c, ctx)])
                } else {
                    left
                }
            }
            K::Alt(v) => alt(v.iter().map(|x| self.plain(x, c, ctx)).collect()),
            K::And(v) => and(v.iter().map(|x| self.plain(x, c, ctx)).collect()),
            K::Star(x) => cat(self.plain(x, c, ctx), t.clone()),
            K::Not(x) => not(self.plain(x, c, ctx)),
        }
    }

    pub fn derive(&self, t: &T, c: u32, ctx: &Ctx) -> T {
        if !t.look {
            return self.plain(t, c, ctx);
        }
        self.dk(t, &eps(), c, ctx, &mut Vec::new())
    }
}

/// Collect every symbol set mentioned in a term.
pub fn leaf_sets(t: &T, out: &mut Vec<Ranges>) {
    match &t.k {
        K::Empty | K::Eps => {}
        K::Set(r) => out.push(r.clone()),
        K::Cat(a, b) => {
            leaf_sets(a, out);
            leaf_sets(b, out);
        }
        K::Alt(v) | K::And(v) => v.iter().for_each(|x| leaf_sets(x, out)),
        K::Star(x) | K::Not(x) | K::Ahead(_, x) | K::Behind(_, x) => leaf_sets(x, out),
        K::Assert(_, w, l) => {
            for r in [w, l].into_iter().flatten() {
                out.push(r.clone());
            }
        }
    }
}

// ----------------------------------------------------------- spec parser

struct Parser<'a> {
    b: &'a [u8],
    i: usize,
}

/// Parse a term spec (see `TermStore::to_spec`), normalising as it builds.
pub fn parse_spec(s: &str) -> Result<T, CheckError> {
    let mut p = Parser {
        b: s.as_bytes(),
        i: 0,
    };
    let t = p.term()?;
    if p.i != p.b.len() {
        return Err(malformed("trailing characters after term"));
    }
    Ok(t)
}

impl Parser<'_> {
    fn ws(&mut self) {
        while self.b.get(self.i) == Some(&b' ') {
            self.i += 1;
        }
    }
    fn hex(&mut self) -> Result<u32, CheckError> {
        let start = self.i;
        let mut v: u32 = 0;
        while let Some(d) = self.b.get(self.i).and_then(|&c| (c as char).to_digit(16)) {
            v = v
                .checked_mul(16)
                .and_then(|x| x.checked_add(d))
                .ok_or_else(|| malformed("code point too large"))?;
            self.i += 1;
        }
        if self.i == start || v > 0x10FFFF {
            return Err(malformed("bad code point in set"));
        }
        Ok(v)
    }
    fn opt_set(&mut self) -> Result<Option<Ranges>, CheckError> {
        self.ws();
        if self.b.get(self.i) == Some(&b'_') {
            self.i += 1;
            return Ok(None);
        }
        if self.b.get(self.i) != Some(&b'[') {
            return Err(malformed("expected a set or '_'"));
        }
        self.i += 1;
        let mut r = Vec::new();
        loop {
            let lo = self.hex()?;
            let hi = if self.b.get(self.i) == Some(&b'-') {
                self.i += 1;
                self.hex()?
            } else {
                lo
            };
            if lo > hi {
                return Err(malformed("reversed range in set"));
            }
            r.push((lo, hi));
            match self.b.get(self.i) {
                Some(b',') => self.i += 1,
                Some(b']') => {
                    self.i += 1;
                    break;
                }
                _ => return Err(malformed("unterminated set")),
            }
        }
        Ok(Some(norm_ranges(r)))
    }

    fn term(&mut self) -> Result<T, CheckError> {
        self.ws();
        match self.b.get(self.i).copied() {
            Some(b'0') => {
                self.i += 1;
                Ok(empty())
            }
            Some(b'e') => {
                self.i += 1;
                Ok(eps())
            }
            Some(b'[') => {
                self.i += 1;
                let mut r = Vec::new();
                loop {
                    let lo = self.hex()?;
                    let hi = if self.b.get(self.i) == Some(&b'-') {
                        self.i += 1;
                        self.hex()?
                    } else {
                        lo
                    };
                    if lo > hi {
                        return Err(malformed("reversed range in set"));
                    }
                    r.push((lo, hi));
                    match self.b.get(self.i) {
                        Some(b',') => self.i += 1,
                        Some(b']') => {
                            self.i += 1;
                            break;
                        }
                        _ => return Err(malformed("unterminated set")),
                    }
                }
                Ok(set(r))
            }
            Some(b'(') => {
                self.i += 1;
                let op = self
                    .b
                    .get(self.i)
                    .copied()
                    .ok_or_else(|| malformed("truncated term"))?;
                self.i += 1;
                if op == b'#' {
                    let k = self
                        .b
                        .get(self.i)
                        .copied()
                        .ok_or_else(|| malformed("truncated assertion"))?
                        as char;
                    self.i += 1;
                    let w = self.opt_set()?;
                    let l = self.opt_set()?;
                    self.ws();
                    if self.b.get(self.i) != Some(&b')') {
                        return Err(malformed("unterminated assertion"));
                    }
                    self.i += 1;
                    if !"Az^$bB<>".contains(k) {
                        return Err(malformed("unknown assertion"));
                    }
                    return Ok(assert_t(k, w, l));
                }
                let op = if op == b'?' || op == b'<' {
                    let c2 = self
                        .b
                        .get(self.i)
                        .copied()
                        .ok_or_else(|| malformed("truncated look"))?;
                    self.i += 1;
                    match (op, c2) {
                        (b'?', b'=') => b'a',
                        (b'?', b'!') => b'n',
                        (b'<', b'=') => b'b',
                        (b'<', b'!') => b'c',
                        _ => return Err(malformed("unknown group operator")),
                    }
                } else {
                    op
                };
                let mut args = Vec::new();
                loop {
                    self.ws();
                    match self.b.get(self.i) {
                        Some(b')') => {
                            self.i += 1;
                            break;
                        }
                        None => return Err(malformed("unterminated term")),
                        _ => args.push(self.term()?),
                    }
                }
                match (op, args.len()) {
                    (b'.', 2) => {
                        let b = args.pop().ok_or_else(|| malformed("arity"))?;
                        let a = args.pop().ok_or_else(|| malformed("arity"))?;
                        Ok(cat(a, b))
                    }
                    (b'|', n) if n >= 2 => Ok(alt(args)),
                    (b'&', n) if n >= 2 => Ok(and(args)),
                    (b'*', 1) => Ok(star(args.remove(0))),
                    (b'!', 1) => Ok(not(args.remove(0))),
                    (b'a', 1) => Ok(ahead(false, args.remove(0))),
                    (b'n', 1) => Ok(ahead(true, args.remove(0))),
                    (b'b' | b'c', 1) => {
                        let x = args.remove(0);
                        if x.dep {
                            return Err(malformed("lookbehind body must be context-free"));
                        }
                        Ok(behind(op == b'c', x))
                    }
                    _ => Err(malformed("unknown operator or wrong arity")),
                }
            }
            _ => Err(malformed("unexpected character in term")),
        }
    }
}