use regex_automata::meta::Regex as Meta;
use regex_automata::{Anchored, Input};
use regexrs::{BytesMode, Regex, RegexBuilder, RegexInput, RegularRegex};
type Groups = Vec<Option<(usize, usize)>>;
struct Rng(u64);
impl Rng {
fn below(&mut self, n: usize) -> usize {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
(self.0 % n as u64) as usize
}
fn pick<'a>(&mut self, items: &[&'a str]) -> &'a str {
items[self.below(items.len())]
}
}
const LITERALS: &[&str] = &["a", "b", "c", "x", "é", "-", r"\.", "k", "1"];
const CLASSES: &[&str] = &[
"[ab]", "[^a]", r"\d", r"\w", "[a-c]", "é", "(?i:k)", "[^ab]", "[é-ê]", ".", r"\s", "[x-]",
];
const QUANTIFIERS: &[&str] = &[
"", "", "", "", "?", "*", "+", "??", "*?", "+?", "{1,3}", "{2}", "{0,2}?", "{2,}",
];
fn pattern(rng: &mut Rng, ascii: bool) -> String {
let mut out = String::new();
if rng.below(10) == 0 {
out.push_str("(?i)");
}
out.push_str(rng.pick(&["", "", "", "", "", "^", r"\b", "(?m)^"]));
if rng.below(2) == 0 {
decided(rng, &mut out, 0, ascii);
} else {
sequence(rng, &mut out, 0, ascii);
}
out.push_str(rng.pick(&["", "", "", "", "", "$", r"\b", "(?m)$"]));
out
}
fn decided(rng: &mut Rng, out: &mut String, depth: usize, ascii: bool) {
for _ in 0..1 + rng.below(3) {
match rng.below(if depth >= 2 { 2 } else { 4 }) {
0 => out.push_str(rng.pick(&["a", "b", "x", "-", "k1", "ab", "é"])),
1 => {
out.push_str(rng.pick(CLASSES));
out.push_str(rng.pick(&["", "", "+", "*", "?", "{2}", "+?"]));
}
kind => {
out.push_str(if kind == 2 { "(" } else { "(?:" });
let mut firsts = vec!["a", "b", "x", "-", "1", "é"];
for branch in 0..1 + rng.below(3) {
if branch > 0 {
out.push('|');
}
let first = firsts.remove(rng.below(firsts.len()));
out.push_str(if ascii && first == "é" { "e" } else { first });
if rng.below(2) == 0 {
decided(rng, out, depth + 1, ascii);
}
}
out.push(')');
out.push_str(rng.pick(&["", "?", "*", "+", "??", "{1,3}", "*?", "{2}"]));
}
}
}
}
fn sequence(rng: &mut Rng, out: &mut String, depth: usize, ascii: bool) {
for _ in 0..1 + rng.below(3) {
atom(rng, out, depth, ascii);
out.push_str(rng.pick(QUANTIFIERS));
}
}
fn atom(rng: &mut Rng, out: &mut String, depth: usize, ascii: bool) {
let choice = if depth >= 2 {
rng.below(2)
} else {
rng.below(6)
};
match choice {
0 => {
for _ in 0..1 + rng.below(3) {
let literal = rng.pick(LITERALS);
out.push_str(if ascii && literal == "é" {
"e"
} else {
literal
});
}
}
1 => {
let class = rng.pick(CLASSES);
out.push_str(if ascii && class.contains('é') {
"[e-f]"
} else {
class
});
}
2 => {
out.push('(');
sequence(rng, out, depth + 1, ascii);
out.push(')');
}
open => {
out.push_str(if open == 3 { "(?:" } else { "(" });
for branch in 0..2 + rng.below(2) {
if branch > 0 {
out.push('|');
}
sequence(rng, out, depth + 1, ascii);
}
out.push(')');
}
}
}
fn text(rng: &mut Rng) -> String {
const PIECES: &[&str] = &[
"a", "b", "c", "x", "é", "ê", "-", ".", " ", "k", "K", "\u{212A}", "\n", "1", "ab", "ba",
];
(0..rng.below(14)).map(|_| rng.pick(PIECES)).collect()
}
fn groups(c: ®exrs::Captures<'_>) -> Groups {
c.iter().map(|m| m.map(|m| (m.start(), m.end()))).collect()
}
fn byte_groups(c: ®exrs::Captures<'_, [u8]>) -> Groups {
(0..c.len())
.map(|i| c.get(i).map(|m| (m.start(), m.end())))
.collect()
}
fn oracle_groups(caps: ®ex::Captures<'_>) -> Groups {
caps.iter()
.map(|m| m.map(|m| (m.start(), m.end())))
.collect()
}
fn meta_captures(
meta: &Meta,
text: &str,
start: usize,
end: usize,
anchored: bool,
) -> Option<Groups> {
let anchored = if anchored {
Anchored::Yes
} else {
Anchored::No
};
let input = Input::new(text).span(start..end).anchored(anchored);
let mut caps = meta.create_captures();
meta.search_captures(&input, &mut caps);
caps.is_match().then(|| {
(0..caps.group_len())
.map(|i| caps.get_group(i).map(|s| (s.start, s.end)))
.collect()
})
}
#[test]
fn generated_patterns_equal_the_regex_crate() {
let mut rng = Rng(0x9E37_79B9_7F4A_7C15);
let (mut compared, mut planned_regular, mut planned_regex) = (0, 0, 0);
let texts: Vec<String> = (0..12).map(|_| text(&mut rng)).collect();
for _ in 0..2500 {
let pattern = pattern(&mut rng, false);
let Ok(oracle) = regex::Regex::new(&pattern) else {
continue;
};
let meta = Meta::new(&pattern).unwrap();
let ordinary = Regex::new(&pattern).unwrap_or_else(|e| panic!("{pattern:?}: {e}"));
let regular = RegularRegex::new(&pattern).unwrap_or_else(|e| panic!("{pattern:?}: {e}"));
compared += 1;
let (regular_planned, regex_planned) = (regular.planned(), ordinary.planned());
planned_regular += usize::from(regular_planned);
planned_regex += usize::from(regex_planned);
if !regular_planned && !regex_planned {
continue;
}
let word_boundaries = pattern.contains(r"\b");
let mut search = ordinary.searcher();
let mut locations = ordinary.capture_locations();
let fresh: Vec<String> = (0..4).map(|_| text(&mut rng)).collect();
for text in texts.iter().chain(&fresh) {
let text = text.as_str();
let context = format!("{pattern:?} {text:?}");
let expected: Vec<Groups> = oracle
.captures_iter(text)
.map(|c| oracle_groups(&c))
.collect();
let spans: Vec<(usize, usize)> = expected.iter().map(|g| g[0].unwrap()).collect();
let first = oracle.captures(text).map(|c| oracle_groups(&c));
if regular_planned {
let found: Vec<Groups> = regular.captures_iter(text).map(|c| groups(&c)).collect();
assert_eq!(found, expected, "RegularRegex::captures_iter {context}");
assert_eq!(regular.is_match(text), oracle.is_match(text), "{context}");
assert_eq!(
regular.replace_all(text, "<$0>"),
oracle.replace_all(text, "<$0>"),
"{context}"
);
}
if regex_planned {
let found: Vec<Groups> = ordinary
.captures_iter(text)
.map(|c| groups(&c.unwrap()))
.collect();
assert_eq!(found, expected, "Regex::captures_iter {context}");
let found: Vec<(usize, usize)> = search
.find_iter(text)
.map(|m| m.map(|m| (m.start(), m.end())).unwrap())
.collect();
assert_eq!(found, spans, "Searcher::find_iter {context}");
assert_eq!(
ordinary.is_match(text).unwrap(),
oracle.is_match(text),
"{context}"
);
let found = search.captures_read(&mut locations, text).unwrap();
assert_eq!(found.is_some(), first.is_some(), "captures_read {context}");
if let Some(first) = &first {
let read: Groups = (0..locations.len()).map(|i| locations.get(i)).collect();
assert_eq!(&read, first, "captures_read {context}");
}
}
let len = text.len();
for (start, end) in [
(0, len),
(1.min(len), len),
(0, len / 2),
(len / 3, len - len / 4),
] {
for anchored in [false, true] {
let expected = meta_captures(&meta, text, start, end, anchored);
let input = || RegexInput::new(text).range(start..end).anchored(anchored);
let at = format!("{context} {start}..{end} anchored={anchored}");
let span = expected.as_ref().map(|g| g[0].unwrap());
if regular_planned {
let found = regular.captures_input(input()).map(|c| groups(&c));
assert_eq!(found, expected, "RegularRegex::captures_input {at}");
let found = regular.find_input(input()).map(|m| (m.start(), m.end()));
assert_eq!(found, span, "RegularRegex::find_input {at}");
assert_eq!(regular.is_match_input(input()), span.is_some(), "{at}");
}
let inside = !text.is_char_boundary(start) || !text.is_char_boundary(end);
if !regex_planned || word_boundaries && (end < len || inside) {
continue;
}
let found = ordinary
.captures_input(input())
.unwrap()
.map(|c| groups(&c));
assert_eq!(found, expected, "Regex::captures_input {at}");
assert_eq!(
ordinary.is_match_input(input()).unwrap(),
span.is_some(),
"Regex::is_match_input {at}"
);
}
}
}
}
eprintln!(
"compared {compared}, planned: RegularRegex {planned_regular}, Regex {planned_regex}"
);
assert!(compared > 2000, "{compared}");
assert!(
planned_regular * 4 > compared,
"{planned_regular} of {compared}"
);
assert!(
planned_regex * 4 > compared,
"{planned_regex} of {compared}"
);
}
#[test]
fn generated_patterns_follow_byte_modes() {
let mut rng = Rng(0xD1B5_4A32_D192_ED03);
const BYTES: &[&[u8]] = &[
b"a",
b"b",
b"c",
b"x",
b"-",
b".",
b" ",
b"k",
b"1",
b"\xFF",
b"\xC3",
b"\xC3\xA9",
b"\x80",
b"\n",
b"ab",
];
let (mut planned, mut nullable) = (0, 0);
for _ in 0..2500 {
let unicode = rng.below(2) == 0;
let pattern = pattern(&mut rng, !unicode);
let oracle_pattern = pattern.replace(r"\b", r"(?u:\b)");
let Ok(oracle) = regex::bytes::RegexBuilder::new(&oracle_pattern)
.unicode(unicode)
.build()
else {
continue;
};
let mode = if unicode {
BytesMode::UnicodeBytes
} else {
BytesMode::Ascii
};
let Ok(regular) = RegexBuilder::new(&pattern).bytes_mode(mode).build_regular() else {
continue;
};
let ordinary = RegexBuilder::new(&pattern)
.bytes_mode(mode)
.build()
.unwrap();
if !regular.planned() {
continue;
}
planned += 1;
let can_be_empty = regex_syntax::ParserBuilder::new()
.unicode(unicode)
.utf8(false)
.build()
.parse(&oracle_pattern)
.is_ok_and(|hir| hir.properties().minimum_len() == Some(0));
nullable += usize::from(can_be_empty);
for _ in 0..8 {
let text: Vec<u8> = (0..rng.below(12))
.flat_map(|_| BYTES[rng.below(BYTES.len())].iter().copied())
.collect();
let context = format!("{pattern:?} {mode:?} {text:?}");
let inside = |at: usize| text.get(at).is_some_and(|&b| b & 0xC0 == 0x80);
let expected: Vec<Groups> = oracle
.captures_iter(&text)
.map(|c| {
c.iter()
.map(|m| m.map(|m| (m.start(), m.end())))
.collect::<Groups>()
})
.filter(|groups| {
let (start, end) = groups[0].unwrap();
!(can_be_empty && start == end && inside(start))
})
.collect();
let found: Vec<Groups> = regular
.captures_iter(text.as_slice())
.map(|c| byte_groups(&c))
.collect();
assert_eq!(found, expected, "RegularRegex {context}");
if ordinary.planned() && !(unicode && pattern.contains(r"\b")) {
let found: Vec<Groups> = ordinary
.captures_iter(text.as_slice())
.map(|c| byte_groups(&c.unwrap()))
.collect();
assert_eq!(found, expected, "Regex {context}");
}
}
}
eprintln!("byte modes: planned {planned}, of which can be empty {nullable}");
assert!(planned > 300, "{planned}");
}