regast 0.1.0

//! Whole-match cases converted from Christopher Kuklewicz's BSD-licensed
//! `regex-posix-unittest-1.1`, plus the Okui–Suzuki ambiguity example.

use regast::{Backend, Regast, Span};

struct Case {
    pattern: &'static str,
    input: &'static str,
    captures: &'static [Option<(usize, usize)>],
}

const KUKLEWICZ_CASES: &[Case] = &[
    Case {
        pattern: "(ab|a)(bc|c)",
        input: "abc",
        captures: &[Some((0, 3)), Some((0, 2)), Some((2, 3))],
    },
    Case {
        pattern: "((a|a)|a)",
        input: "a",
        captures: &[Some((0, 1)), Some((0, 1)), Some((0, 1))],
    },
    Case {
        pattern: "(a*)(a|aa)",
        input: "aaaa",
        captures: &[Some((0, 4)), Some((0, 3)), Some((3, 4))],
    },
    Case {
        pattern: "a*(a.|aa)",
        input: "aaaa",
        captures: &[Some((0, 4)), Some((2, 4))],
    },
    Case {
        pattern: "(a|b)?.*",
        input: "b",
        captures: &[Some((0, 1)), Some((0, 1))],
    },
    Case {
        pattern: "(a|b)c|a(b|c)",
        input: "ac",
        captures: &[Some((0, 2)), Some((0, 1)), None],
    },
    Case {
        pattern: "(a|b)c|a(b|c)",
        input: "ab",
        captures: &[Some((0, 2)), None, Some((1, 2))],
    },
    Case {
        pattern: "(a|b)*c|(a|ab)*c",
        input: "abc",
        captures: &[Some((0, 3)), Some((1, 2)), None],
    },
    Case {
        pattern: "(.a|.b).*|.*(.a|.b)",
        input: "xa",
        captures: &[Some((0, 2)), Some((0, 2)), None],
    },
    Case {
        pattern: "a?(ab|ba)ab",
        input: "abab",
        captures: &[Some((0, 4)), Some((0, 2))],
    },
    Case {
        pattern: "(aa|aaa)*|(a|aaaaa)",
        input: "aa",
        captures: &[Some((0, 2)), Some((0, 2)), None],
    },
    Case {
        pattern: "([abc])*d",
        input: "abbbcd",
        captures: &[Some((0, 6)), Some((4, 5))],
    },
    Case {
        pattern: "([abc])*bcd",
        input: "abcd",
        captures: &[Some((0, 4)), Some((0, 1))],
    },
    Case {
        pattern: "(ab|ab*)bc",
        input: "abc",
        captures: &[Some((0, 3)), Some((0, 1))],
    },
    Case {
        pattern: "a([bc]*)(c*d)",
        input: "abcd",
        captures: &[Some((0, 4)), Some((1, 3)), Some((3, 4))],
    },
    Case {
        pattern: "a([bc]*)(c+d)",
        input: "abcd",
        captures: &[Some((0, 4)), Some((1, 2)), Some((2, 4))],
    },
    Case {
        pattern: "(ab|a)b*c",
        input: "abc",
        captures: &[Some((0, 3)), Some((0, 2))],
    },
    Case {
        pattern: "((a)(b)c)(d)",
        input: "abcd",
        captures: &[
            Some((0, 4)),
            Some((0, 3)),
            Some((0, 1)),
            Some((1, 2)),
            Some((3, 4)),
        ],
    },
    Case {
        pattern: "(.*)c(.*)",
        input: "abcde",
        captures: &[Some((0, 5)), Some((0, 2)), Some((3, 5))],
    },
    Case {
        pattern: "((a?)((ab)?))(b?)",
        input: "ab",
        captures: &[
            Some((0, 2)),
            Some((0, 2)),
            Some((0, 0)),
            Some((0, 2)),
            Some((0, 2)),
            Some((2, 2)),
        ],
    },
    Case {
        pattern: "(.?)*",
        input: "x",
        captures: &[Some((0, 1)), Some((0, 1))],
    },
    Case {
        pattern: "(()|.)(b)",
        input: "ab",
        captures: &[Some((0, 2)), Some((0, 1)), None, Some((1, 2))],
    },
    Case {
        pattern: "(()|[ab])+b",
        input: "aaab",
        captures: &[Some((0, 4)), Some((2, 3)), None],
    },
    Case {
        pattern: "(aba|ab|a)*",
        input: "ababa",
        captures: &[Some((0, 5)), Some((2, 5))],
    },
];

#[test]
fn kuklewicz_v01_compatible_cases() {
    for case in KUKLEWICZ_CASES {
        assert_case(case);
    }
}

#[test]
fn okui_suzuki_prefers_one_long_iteration() {
    let cases = [
        Case {
            pattern: "(x|y|xy)*",
            input: "xy",
            captures: &[Some((0, 2)), Some((0, 2))],
        },
        Case {
            pattern: "(ab|a*)*",
            input: "abab",
            captures: &[Some((0, 4)), Some((2, 4))],
        },
    ];
    for case in cases {
        assert_case(&case);
    }
}

fn assert_case(case: &Case) {
    let expected: Vec<_> = case
        .captures
        .iter()
        .map(|span| span.map(|(start, end)| Span::new(start, end)))
        .collect();
    for backend in [Backend::Derivative, Backend::Antimirov, Backend::TaggedNfa] {
        let tree = Regast::builder(case.pattern)
            .backend(backend)
            .build()
            .unwrap()
            .parse(case.input)
            .unwrap();
        assert_eq!(
            tree.captures_compat(),
            expected,
            "pattern {}, backend {backend:?}",
            case.pattern
        );
    }
}