rexact-core 0.2.0

//! Engine properties (layers L1, L2, L4): hand-verified known answers, random
//! terms checked against a naive definition-level evaluator, algebraic laws,
//! limits, and hostile sizes. Expectations come from the mathematical
//! definition of the operators or from hand derivation (RULE-13), never from
//! recording what the engine returned.

#![allow(clippy::expect_used, clippy::unwrap_used, clippy::panic)]

use rexact_core::charset::CharSet;
use rexact_core::term::{TermId, TermStore};
use rexact_core::{fingerprint_term, Alphabet, Language, Limits, Mode};
use rexact_syntax::{Dialect, Flags, Pattern};
use std::time::Duration;

// ----------------------------------------------------- naive reference model

/// Expression tree evaluated straight from the definition of each operator.
#[derive(Clone, Debug)]
enum E {
    Empty,
    Eps,
    Set(Vec<u32>),
    Cat(Box<E>, Box<E>),
    Alt(Box<E>, Box<E>),
    Star(Box<E>),
    And(Box<E>, Box<E>),
    Not(Box<E>),
}

fn member(e: &E, w: &[u32]) -> bool {
    match e {
        E::Empty => false,
        E::Eps => w.is_empty(),
        E::Set(s) => w.len() == 1 && s.contains(&w[0]),
        E::Cat(a, b) => (0..=w.len()).any(|i| member(a, &w[..i]) && member(b, &w[i..])),
        E::Alt(a, b) => member(a, w) || member(b, w),
        E::And(a, b) => member(a, w) && member(b, w),
        E::Not(a) => !member(a, w),
        E::Star(a) => {
            w.is_empty() || (1..=w.len()).any(|i| member(a, &w[..i]) && member(e, &w[i..]))
        }
    }
}

fn build(store: &mut TermStore, e: &E) -> TermId {
    match e {
        E::Empty => store.empty(),
        E::Eps => store.epsilon(),
        E::Set(s) => store.class(&CharSet::from_ranges(s.iter().map(|&c| (c, c)))),
        E::Cat(a, b) => {
            let (x, y) = (build(store, a), build(store, b));
            store.concat(x, y)
        }
        E::Alt(a, b) => {
            let (x, y) = (build(store, a), build(store, b));
            store.union(&[x, y])
        }
        E::And(a, b) => {
            let (x, y) = (build(store, a), build(store, b));
            store.inter(&[x, y])
        }
        E::Star(a) => {
            let x = build(store, a);
            store.star(x)
        }
        E::Not(a) => {
            let x = build(store, a);
            store.not(x)
        }
    }
}

struct Rng(u64);
impl Rng {
    fn next(&mut self) -> u64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        self.0
    }
    fn below(&mut self, n: u64) -> u64 {
        self.next() % n
    }
}

/// Symbols a,b,c plus d (which some sets contain, so complements matter).
const SYM: [u32; 4] = [97, 98, 99, 100];

fn gen(r: &mut Rng, depth: u32) -> E {
    let pick = if depth == 0 { r.below(4) } else { r.below(13) };
    let sub = |r: &mut Rng| Box::new(gen(r, depth - 1));
    match pick {
        0 => E::Empty,
        1 => E::Eps,
        2 | 3 => {
            let mut s: Vec<u32> = SYM.iter().copied().filter(|_| r.below(2) == 0).collect();
            if s.is_empty() {
                s.push(97);
            }
            E::Set(s)
        }
        4..=6 => E::Cat(sub(r), sub(r)),
        7 | 8 => E::Alt(sub(r), sub(r)),
        9 | 10 => E::Star(sub(r)),
        11 => E::And(sub(r), sub(r)),
        _ => E::Not(sub(r)),
    }
}

fn all_strings(max: usize) -> Vec<Vec<u32>> {
    let mut out = vec![vec![]];
    let mut layer = vec![vec![]];
    for _ in 0..max {
        let mut next = Vec::new();
        for s in &layer {
            for &c in &SYM {
                let mut t = s.clone();
                t.push(c);
                next.push(t);
            }
        }
        out.extend(next.iter().cloned());
        layer = next;
    }
    out
}

fn store() -> TermStore {
    TermStore::new(Alphabet::Bytes.universe())
}
fn fp(s: &mut TermStore, t: TermId) -> String {
    fingerprint_term(s, t, Alphabet::Bytes, &Limits::default()).expect("fingerprint")
}

#[test]
fn random_terms_agree_with_the_definition_of_each_operator() {
    let mut r = Rng(0x9E3779B97F4A7C15);
    let strs = all_strings(5);
    let mut checked = 0u64;
    for _ in 0..300 {
        let e = gen(&mut r, 4);
        let mut st = store();
        let t = build(&mut st, &e);
        let mut lang =
            Language::from_parts(st, t, Alphabet::Bytes, &Limits::default()).expect("lang");
        let min = lang.minimal().expect("min");
        for w in &strs {
            let want = member(&e, w);
            assert_eq!(
                lang.matches_units(w).unwrap(),
                want,
                "lazy dfa: {e:?} on {w:?}"
            );
            assert_eq!(min.accepts(w), want, "minimal dfa: {e:?} on {w:?}");
            checked += 2;
        }
    }
    assert!(checked > 600_000);
}

#[test]
fn algebraic_laws_hold_as_equal_fingerprints() {
    let mut r = Rng(0xDEADBEEFCAFEF00D);
    for _ in 0..120 {
        let (ea, eb, ec) = (gen(&mut r, 3), gen(&mut r, 3), gen(&mut r, 3));
        let mut s = store();
        let (a, b, c) = (build(&mut s, &ea), build(&mut s, &eb), build(&mut s, &ec));
        let (e, z) = (s.epsilon(), s.empty());

        let aa = s.union(&[a, a]);
        assert_eq!(fp(&mut s, aa), fp(&mut s, a), "A|A = A");
        let (ab, ba) = (s.union(&[a, b]), s.union(&[b, a]));
        assert_eq!(fp(&mut s, ab), fp(&mut s, ba), "A|B = B|A");
        let (abc1, bc, abc2) = {
            let abc1 = s.union(&[ab, c]);
            let bc = s.union(&[b, c]);
            (abc1, bc, s.union(&[a, bc]))
        };
        let _ = bc;
        assert_eq!(fp(&mut s, abc1), fp(&mut s, abc2), "(A|B)|C = A|(B|C)");
        let (sa, ssa) = {
            let sa = s.star(a);
            (sa, s.star(sa))
        };
        assert_eq!(fp(&mut s, sa), fp(&mut s, ssa), "A* = (A*)*");
        let ae = s.concat(a, e);
        assert_eq!(fp(&mut s, ae), fp(&mut s, a), "A.eps = A");
        let az = s.concat(a, z);
        assert_eq!(fp(&mut s, az), fp(&mut s, z), "A.empty = empty");
        let (na, nna) = {
            let na = s.not(a);
            (na, s.not(na))
        };
        let _ = na;
        assert_eq!(fp(&mut s, nna), fp(&mut s, a), "not not A = A");
        // De Morgan: A & B = not(not A | not B)
        let inter = s.inter(&[a, b]);
        let (nb, na2) = (s.not(b), s.not(a));
        let dm = {
            let u = s.union(&[na2, nb]);
            s.not(u)
        };
        assert_eq!(fp(&mut s, inter), fp(&mut s, dm), "De Morgan");
        // Absorption: A | (A & B) = A  and  A | (A | B) = A | B
        let absorb = s.union(&[a, inter]);
        assert_eq!(fp(&mut s, absorb), fp(&mut s, a), "A & B is contained in A");
        let sup = s.union(&[a, ab]);
        assert_eq!(fp(&mut s, sup), fp(&mut s, ab), "A is contained in A|B");
        // Distributivity of concatenation over union.
        let left = {
            let u = s.union(&[b, c]);
            s.concat(a, u)
        };
        let right = {
            let (x, y) = (s.concat(a, b), s.concat(a, c));
            s.union(&[x, y])
        };
        assert_eq!(fp(&mut s, left), fp(&mut s, right), "A(B|C) = AB|AC");
    }
}

#[test]
fn fingerprints_separate_languages_exactly() {
    // Soundness in both directions against brute force on short strings:
    // equal fingerprints must never hide a difference, and a difference on a
    // short string must always show in the fingerprint.
    let mut r = Rng(0x1234_5678_9ABC_DEF1);
    let strs = all_strings(5);
    let (mut equal_pairs, mut diff_pairs) = (0, 0);
    for _ in 0..400 {
        let (ea, eb) = (gen(&mut r, 3), gen(&mut r, 3));
        let mut s = store();
        let (a, b) = (build(&mut s, &ea), build(&mut s, &eb));
        let differ_short = strs.iter().any(|w| member(&ea, w) != member(&eb, w));
        let same_fp = fp(&mut s, a) == fp(&mut s, b);
        if differ_short {
            assert!(
                !same_fp,
                "{ea:?} vs {eb:?} differ on a short string but share a fingerprint"
            );
            diff_pairs += 1;
        }
        if same_fp {
            assert!(!differ_short);
            equal_pairs += 1;
        }
    }
    assert!(
        diff_pairs > 100 && equal_pairs > 5,
        "weak coverage: {diff_pairs}/{equal_pairs}"
    );
}

// ----------------------------------------------------------- known answers

fn lang(d: Dialect, flags: &str, p: &str) -> Language {
    let f = Flags::from_letters(d, flags).unwrap().0;
    let pat = Pattern::parse(p, d, f).unwrap();
    Language::compile(&pat, None, Mode::Full, &Limits::default()).unwrap()
}
fn es(p: &str) -> Language {
    lang(Dialect::Ecma, "", p)
}
fn fpr(mut l: Language) -> String {
    l.fingerprint().unwrap()
}

#[test]
fn classic_equivalences_share_a_fingerprint() {
    // docs/08 section 3.1 and AC-01, AC-03, AC-04.
    assert_eq!(fpr(es("(a|b)*")), fpr(es("(a*b*)*")));
    assert_eq!(fpr(es("(a+)+")), fpr(es("a+")));
    assert_eq!(fpr(es("[ab]{2,3}")), fpr(es("[ab][ab][ab]?")));
    assert_eq!(fpr(es("a|b")), fpr(es("[ab]")));
    assert_eq!(fpr(es("a|b")), fpr(es("b|a")));
    assert_eq!(fpr(es("\\d+")), fpr(es("[0-9]+"))); // AC-28 in ECMAScript
    assert_eq!(fpr(es("a{0}")), fpr(es("(?:)")));
    assert_eq!(fpr(es("[]")), fpr(es("[^\\s\\S]")));
    assert_eq!(fpr(es("[^]")), fpr(es("[\\s\\S]")));
}

#[test]
fn classic_non_equivalences_differ() {
    assert_ne!(fpr(es("(ab|a)(c|bc)")), fpr(es("a(bc|c)"))); // AC-02
    assert_ne!(fpr(es("a*")), fpr(es("a+"))); // AC-05
    assert_ne!(fpr(es("a")), fpr(es("b")));
    assert_ne!(fpr(es("[ab]{2,3}")), fpr(es("[ab]{2,4}")));
    // Same text, different dialect semantics: ECMAScript \s includes NBSP, Python-ASCII does not.
    assert_ne!(fpr(es("\\s")), fpr(lang(Dialect::Python, "a", "\\s")));
}

#[test]
fn fingerprint_depends_on_the_alphabet_mode() {
    let p = Pattern::parse(".", Dialect::Ecma, Flags::none()).unwrap();
    let utf16 =
        Language::compile(&p, Some(Alphabet::Utf16), Mode::Full, &Limits::default()).unwrap();
    let uni =
        Language::compile(&p, Some(Alphabet::Unicode), Mode::Full, &Limits::default()).unwrap();
    assert_ne!(fpr(utf16), fpr(uni));
}

#[test]
fn minimal_automaton_sizes_match_hand_derivation() {
    // (a|b)*abb over {a, b, other}: the classic 4-state DFA plus one dead
    // state, with three symbol classes.
    let m = es("(a|b)*abb").minimal().unwrap();
    assert_eq!((m.num_states(), m.num_classes()), (5, 3));
    // a* : accepting loop + dead; classes {a} and the rest.
    let m = es("a*").minimal().unwrap();
    assert_eq!((m.num_states(), m.num_classes()), (2, 2));
    // a : start, accept, dead.
    let m = es("a").minimal().unwrap();
    assert_eq!((m.num_states(), m.num_classes()), (3, 2));
    // Everything: one state, one class.
    let m = es("[\\s\\S]*").minimal().unwrap();
    assert_eq!((m.num_states(), m.num_classes()), (1, 1));
    // Nothing: one dead state.
    let m = es("[]").minimal().unwrap();
    assert_eq!((m.num_states(), m.num_classes()), (1, 1));
    // [ab]*a[ab]{3}: 2^4 = 16 live states + dead, classes {a}, {b}, other.
    let m = es("[ab]*a[ab]{3}").minimal().unwrap();
    assert_eq!((m.num_states(), m.num_classes()), (17, 3));
}

#[test]
fn indistinguishable_symbols_merge_into_one_class() {
    // The term mentions {a} and {a,b} separately, but the language only
    // distinguishes a|b from everything else: after minimisation, 2 classes.
    let m = es("a|[ab]").minimal().unwrap();
    assert_eq!(m.num_classes(), 2);
}

#[test]
fn search_mode_matches_anywhere() {
    let p = Pattern::parse("ab", Dialect::Ecma, Flags::none()).unwrap();
    let mut l = Language::compile(&p, None, Mode::Search, &Limits::default()).unwrap();
    assert!(l.matches("xxabyy").unwrap() && l.matches("ab").unwrap());
    assert!(!l.matches("axb").unwrap() && !l.matches("").unwrap());
}

#[test]
fn utf16_and_unicode_modes_split_astral_characters() {
    let p = Pattern::parse("^", Dialect::Ecma, Flags::none());
    assert!(p.is_ok()); // parses; lowering rejects anchors until M6
    let dot = |flags: &str| lang(Dialect::Ecma, flags, ".");
    assert!(!dot("").matches("😀").unwrap()); // two UTF-16 units
    assert!(dot("u").matches("😀").unwrap()); // one scalar
    assert!(lang(Dialect::Ecma, "", "..").matches("😀").unwrap());
    assert!(lang(Dialect::Ecma, "", "😀").matches("😀").unwrap());
}

#[test]
fn unmodelled_features_are_rejected_not_approximated() {
    let compile = |d: Dialect, fl: &str, p: &str| {
        let f = Flags::from_letters(d, fl).unwrap().0;
        Language::compile(
            &Pattern::parse(p, d, f).unwrap(),
            None,
            Mode::Full,
            &Limits::default(),
        )
        .err()
    };
    // Lookbehind bodies may not contain anchors or lookaround: rejected with RX-U005.
    for (d, fl, p) in [
        (Dialect::Ecma, "", "(?<=^)a"),
        (Dialect::Python, "", "(?<=\\b)a"),
        (Dialect::Ecma, "", "(?<!(?=a)a)b"),
    ] {
        let e = compile(d, fl, p).unwrap_or_else(|| panic!("{p} should be rejected"));
        assert_eq!(e.code(), "RX-U005", "{p}");
        assert!(e.position.is_some());
    }
}

// ------------------------------------------------------ limits and hostility

fn compile_err(p: &str, limits: &Limits) -> String {
    let pat = Pattern::parse(p, Dialect::Ecma, Flags::none()).unwrap();
    match Language::compile(&pat, None, Mode::Full, limits) {
        Err(e) => e.code().to_string(),
        Ok(mut l) => match l.fingerprint() {
            Err(e) => e.code().to_string(),
            Ok(_) => "ok".into(),
        },
    }
}

#[test]
fn repetition_expansion_is_bounded() {
    let d = Limits::default();
    assert_eq!(compile_err("(a{1000}){1000}", &d), "RX-L004"); // AC-37
    assert_eq!(compile_err("a{10001}", &d), "RX-L004");
    assert_eq!(compile_err("a{70000}", &d), "RX-L004"); // DV-12
    assert_eq!(compile_err("a{2}", &d), "ok");
    assert_eq!(
        compile_err(
            "a{0,5}",
            &Limits {
                repeat: 4,
                ..d.clone()
            }
        ),
        "RX-L004"
    );
    assert_eq!(compile_err("a{0,4}", &Limits { repeat: 4, ..d }), "ok");
}

#[test]
fn state_time_and_memory_limits_stop_the_computation() {
    let blowup = "[ab]*a[ab]{12}"; // 2^13 minimal states
    let d = Limits::default();
    assert_eq!(
        compile_err(
            blowup,
            &Limits {
                states: 10,
                ..d.clone()
            }
        ),
        "RX-L001"
    ); // AC-08
    assert_eq!(
        compile_err(
            blowup,
            &Limits {
                memory_bytes: 20_000,
                ..d.clone()
            }
        ),
        "RX-L003"
    );
    assert_eq!(
        compile_err(
            blowup,
            &Limits {
                time: Duration::ZERO,
                ..d.clone()
            }
        ),
        "RX-L002"
    );
    assert_eq!(
        compile_err(
            "a",
            &Limits {
                length: 0,
                ..d.clone()
            }
        ),
        "RX-L005"
    );
    assert_eq!(compile_err(blowup, &d), "ok");
}

#[test]
fn large_but_allowed_repetition_does_not_overflow_the_stack() {
    // Runs on the default 2 MiB test-thread stack in a debug build.
    let d = Limits::default();
    let mut l = es("a{0,5000}");
    assert!(l.matches(&"a".repeat(5000)).unwrap());
    assert!(!l.matches(&"a".repeat(5001)).unwrap());
    let mut l = es("(a|b){3000}");
    assert!(l.matches(&"ab".repeat(1500)).unwrap());
    assert_eq!(compile_err("a{0,9999}", &d), "ok");
}

#[test]
fn matching_is_linear_after_construction() {
    // 4 MB of input through a cached automaton; a regression to backtracking
    // behaviour would not finish. (Throughput targets belong to the bench suite.)
    let mut l = es("(a+)+b");
    let input = "a".repeat(4_000_000);
    assert!(!l.matches(&input).unwrap());
    assert!(l.matches(&(input + "b")).unwrap());
}

/// NFR-P03: a 10,000-state minimal automaton in under 2 s. Release builds only;
/// debug builds are not held to a release budget.
#[test]
#[cfg(not(debug_assertions))]
fn ten_thousand_state_automaton_minimises_within_budget() {
    let start = std::time::Instant::now();
    let mut l = es("a{0,9999}");
    let m = l.minimal().unwrap();
    assert_eq!(m.num_states(), 10_001); // counts 0..=9999 plus the dead state
    assert!(
        start.elapsed() < Duration::from_secs(2),
        "took {:?}",
        start.elapsed()
    );
}