use proptest::prelude::*;
use regast::{Backend, PtKind, Regast};
use regex::Regex;
#[derive(Clone, Debug)]
enum GeneratedAst {
Empty,
Literal(char),
Class,
Alt(Box<Self>, Box<Self>),
Seq(Box<Self>, Box<Self>),
Optional(Box<Self>),
Star(Box<Self>),
Plus(Box<Self>),
Range(Box<Self>, u8, u8),
}
impl GeneratedAst {
fn pattern(&self) -> String {
match self {
Self::Empty => String::new(),
Self::Literal(c) => c.to_string(),
Self::Class => "[ab]".into(),
Self::Alt(left, right) => {
format!("(?:{}|{})", left.pattern(), right.pattern())
}
Self::Seq(left, right) => format!("(?:{}{})", left.pattern(), right.pattern()),
Self::Optional(inner) => format!("(?:{})?", inner.pattern()),
Self::Star(inner) => format!("(?:{})*", inner.pattern()),
Self::Plus(inner) => format!("(?:{})+", inner.pattern()),
Self::Range(inner, min, max) => format!("(?:{}){{{min},{max}}}", inner.pattern()),
}
}
fn sample(&self, choices: &mut Choices) -> String {
match self {
Self::Empty => String::new(),
Self::Literal(c) => c.to_string(),
Self::Class => if choices.next(2) == 0 { "a" } else { "b" }.into(),
Self::Alt(left, right) => {
if choices.next(2) == 0 {
left.sample(choices)
} else {
right.sample(choices)
}
}
Self::Seq(left, right) => left.sample(choices) + &right.sample(choices),
Self::Optional(inner) => {
if choices.next(2) == 0 {
String::new()
} else {
inner.sample(choices)
}
}
Self::Star(inner) => {
let count = choices.next(4);
sample_repetitions(inner, choices, count)
}
Self::Plus(inner) => {
let count = choices.next(3) + 1;
sample_repetitions(inner, choices, count)
}
Self::Range(inner, min, max) => {
let count = usize::from(*min) + choices.next(usize::from(max - min + 1));
sample_repetitions(inner, choices, count)
}
}
}
}
fn sample_repetitions(ast: &GeneratedAst, choices: &mut Choices, count: usize) -> String {
(0..count).map(|_| ast.sample(choices)).collect()
}
struct Choices(u64);
impl Choices {
const fn new(seed: u64) -> Self {
Self(seed)
}
fn next(&mut self, modulo: usize) -> usize {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
usize::try_from(self.0 % modulo as u64).expect("choice fits usize")
}
}
fn generated_ast() -> impl Strategy<Value = GeneratedAst> {
let leaf = prop_oneof![
Just(GeneratedAst::Empty),
prop::sample::select(vec!['a', 'b']).prop_map(GeneratedAst::Literal),
Just(GeneratedAst::Class),
];
leaf.prop_recursive(3, 32, 2, |inner| {
prop_oneof![
(inner.clone(), inner.clone())
.prop_map(|(left, right)| GeneratedAst::Alt(Box::new(left), Box::new(right))),
(inner.clone(), inner.clone())
.prop_map(|(left, right)| GeneratedAst::Seq(Box::new(left), Box::new(right))),
inner
.clone()
.prop_map(|ast| GeneratedAst::Optional(Box::new(ast))),
inner
.clone()
.prop_map(|ast| GeneratedAst::Star(Box::new(ast))),
inner
.clone()
.prop_map(|ast| GeneratedAst::Plus(Box::new(ast))),
(inner, 0_u8..3, 0_u8..3).prop_filter_map(
"ordered repetition bounds",
|(ast, min, extra)| min.checked_add(extra).map(|max| GeneratedAst::Range(
Box::new(ast),
min,
max
)),
),
]
})
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(256))]
#[test]
fn generated_language_members_parse_soundly_and_consistently(
ast in generated_ast(),
seed in any::<u64>(),
) {
let pattern = ast.pattern();
let input = ast.sample(&mut Choices::new(seed));
let regex = Regast::new(&pattern).unwrap();
let tree = regex.parse(&input).unwrap();
prop_assert_eq!(tree.flatten(), input.as_str());
prop_assert!(regex.is_match(&input));
for backend in [Backend::Antimirov, Backend::TaggedNfa] {
let alternate = Regast::builder(&pattern).backend(backend).build().unwrap();
let alternate_tree = alternate.parse(&input).unwrap();
prop_assert_eq!(alternate_tree.to_json(), tree.to_json());
}
let greedy = Regast::builder(&pattern).greedy().build().unwrap();
let greedy_tree = greedy.parse(&input).unwrap();
for backend in [Backend::Antimirov, Backend::TaggedNfa] {
let alternate = Regast::builder(&pattern)
.greedy()
.backend(backend)
.build()
.unwrap();
prop_assert_eq!(alternate.parse(&input).unwrap().to_json(), greedy_tree.to_json());
}
for node in tree.walk() {
if let PtKind::Repeat { .. } = node.kind {
let ast_kind = &tree.pattern().node(node.ast).kind;
let first_star_iteration = match ast_kind {
regast::AstKind::Repeat { kind: regast::RepKind::ZeroOrMore, .. } => 0,
regast::AstKind::Repeat { kind: regast::RepKind::OneOrMore, .. } => 1,
_ => continue,
};
for iteration in node.children.iter().skip(first_star_iteration) {
prop_assert!(!input[iteration.span.start as usize..iteration.span.end as usize].is_empty());
}
}
}
}
#[test]
fn generated_patterns_agree_with_reference_membership(
ast in generated_ast(),
chars in prop::collection::vec(prop::sample::select(vec!['a', 'b', 'c']), 0..7),
) {
let pattern = ast.pattern();
let input: String = chars.into_iter().collect();
let regast = Regast::new(&pattern).unwrap();
let antimirov = Regast::builder(&pattern).backend(Backend::Antimirov).build().unwrap();
let tagged_nfa = Regast::builder(&pattern).backend(Backend::TaggedNfa).build().unwrap();
let reference = Regex::new(&format!(r"\A(?:{pattern})\z")).unwrap();
let expected = reference.is_match(&input);
prop_assert_eq!(regast.is_match(&input), expected);
prop_assert_eq!(antimirov.is_match(&input), expected);
prop_assert_eq!(tagged_nfa.is_match(&input), expected);
}
}