regast-core 0.1.0

use proptest::prelude::*;

use super::*;
use crate::{deriv::deriv, inj::inj, mkeps::mkeps};

fn matcher(pattern: &str) -> Matcher {
    Matcher::new(
        Pattern::parse(pattern).unwrap(),
        Disambiguation::Posix,
        100_000,
    )
}

fn parse_without_simplification(pattern: &str, input: &str) -> Value {
    let mut raw = matcher(pattern);
    let mut root = raw.lowering.root;
    let mut trace = Vec::new();
    for c in input.chars() {
        trace.push((root, c));
        root = deriv(&mut raw.pool, root, c);
    }
    assert!(raw.pool.nullable(root));
    let mut value = mkeps(&mut raw.pool, root);
    for (previous, c) in trace.into_iter().rev() {
        value = inj(&mut raw.pool, previous, c, value);
    }
    value
}

fn matching_case() -> impl Strategy<Value = (String, String)> {
    let leaf = prop_oneof![
        Just((String::new(), String::new())),
        Just(("a".into(), "a".into())),
        Just(("b".into(), "b".into())),
        Just(("[ab]".into(), "a".into())),
    ];
    leaf.prop_recursive(3, 48, 2, |inner| {
        prop_oneof![
            (inner.clone(), inner.clone()).prop_map(|((left, left_input), (right, _))| (
                format!("(?:{left}|{right})"),
                left_input,
            )),
            (inner.clone(), inner.clone()).prop_map(
                |((left, left_input), (right, right_input))| (
                    format!("(?:{left}{right})"),
                    left_input + &right_input,
                ),
            ),
            inner
                .clone()
                .prop_map(|(pattern, input)| (format!("(?:{pattern})?"), input,)),
            inner
                .clone()
                .prop_map(|(pattern, input)| (format!("(?:{pattern})*"), input.repeat(2),)),
            inner
                .clone()
                .prop_map(|(pattern, input)| (format!("(?:{pattern})+"), input.repeat(2),)),
            inner.prop_map(|(pattern, input)| (format!("(?:{pattern}){{2,3}}"), input.repeat(2),)),
        ]
    })
}

#[test]
fn parses_and_reconstructs_input() {
    for (pattern, input) in [
        ("", ""),
        ("a", "a"),
        ("a|b", "b"),
        ("ab", "ab"),
        ("(a|b)*c", "abac"),
        ("a{2,4}", "aaa"),
        ("(a?)*", "aa"),
    ] {
        let value = matcher(pattern).parse_value(input).unwrap();
        assert_eq!(value.flatten(), input, "pattern {pattern}");
    }
}

#[test]
fn rejects_non_matches() {
    assert!(!matcher("a+b").is_match("abx"));
    assert!(matcher("a+b").is_match("aaab"));
}

#[test]
fn resolves_start_and_end_anchors_against_the_whole_input() {
    assert!(matcher("^a$").is_match("a"));
    assert!(!matcher("^a$").is_match("aa"));
    assert!(matcher("^$").is_match(""));
    let tree = matcher("^(a)$").parse("a").unwrap();
    assert_eq!(tree.flatten(), "a");
    assert_eq!(tree.group_all(1)[0].span, regast_syntax::Span::new(0, 1));
}

#[test]
fn rectifies_simplified_star_elements() {
    for (pattern, input) in [("(()a)*", "aa"), ("((?:)a)*", "aaa")] {
        let value = matcher(pattern).parse_value(input).unwrap();
        assert_eq!(value.flatten(), input);
    }
}

#[test]
fn reports_size_limit_separately_from_non_match() {
    let mut matcher = Matcher::new(Pattern::parse("(a|b)*c").unwrap(), Disambiguation::Posix, 2);
    assert!(matches!(
        matcher.parse_value("abc"),
        Err(MatchError::SizeLimitExceeded { limit: 2, .. })
    ));
}

#[test]
fn alternate_parsers_do_not_invoke_brzozowski_derivatives() {
    for backend in [Backend::Antimirov, Backend::TaggedNfa] {
        let mut matcher = Matcher::new_with_backend(
            Pattern::parse("((a|aa)*)(a?)").unwrap(),
            Disambiguation::Posix,
            100_000,
            backend,
        );
        let value = matcher.parse_value("aaa").unwrap();
        assert_eq!(value.flatten(), "aaa");
        assert!(matcher.pool.deriv_memo.is_empty(), "backend {backend:?}");
    }
}

#[test]
fn alternate_value_reconstruction_obeys_the_state_limit() {
    for backend in [Backend::Antimirov, Backend::TaggedNfa] {
        let mut matcher = Matcher::new_with_backend(
            Pattern::parse("a*").unwrap(),
            Disambiguation::Posix,
            10,
            backend,
        );
        assert!(matches!(
            matcher.parse_value("aaaa"),
            Err(MatchError::SizeLimitExceeded { limit: 10, .. })
        ));
    }
}

#[test]
fn rectification_matches_unsimplified_derivation() {
    for (pattern, input) in [
        ("ab", "ab"),
        ("a|b", "b"),
        ("(a|b)*c", "abac"),
        ("a{1,3}b", "aaab"),
    ] {
        let simplified = matcher(pattern).parse_value(input).unwrap();
        let raw = parse_without_simplification(pattern, input);
        assert_eq!(simplified, raw, "pattern {pattern}");
    }
}

#[test]
fn duplicate_alternatives_rectify_into_the_left_branch() {
    let tree = matcher("a|a").parse("a").unwrap();
    assert!(matches!(
        tree.root().kind,
        crate::PtKind::AltTaken { arm: 0 }
    ));
}

proptest! {
    #![proptest_config(ProptestConfig::with_cases(256))]

    #[test]
    fn generated_rectification_matches_unsimplified((pattern, input) in matching_case()) {
        let simplified = matcher(&pattern).parse_value(&input).unwrap();
        let raw = parse_without_simplification(&pattern, &input);
        prop_assert_eq!(simplified, raw);
    }
}