fn plain_class_char(c: char) -> bool {
c.is_ascii_graphic() && !"\\^-[]&~".contains(c) || c == ' '
}
const META: &str = ".^$*+?()[]{}|\\";
fn literal(p: &str) -> Option<String> {
let mut out = String::new();
let mut it = p.chars();
while let Some(c) = it.next() {
if c == '\\' {
let n = it.next()?;
if !META.contains(n) {
return None;
}
out.push(n);
} else if META.contains(c) {
return None;
} else {
out.push(c);
}
}
(!out.is_empty()).then_some(out)
}
#[derive(Debug, Clone)]
pub(crate) enum CharSet {
One(char),
Ascii(Vec<u8>),
}
impl CharSet {
fn rfind_end(&self, text: &str) -> Option<usize> {
match self {
CharSet::One(c) => text.rfind(*c).map(|i| i + c.len_utf8()),
CharSet::Ascii(set) => text
.as_bytes()
.iter()
.rposition(|b| set.contains(b))
.map(|i| i + 1),
}
}
}
#[derive(Debug, Clone)]
pub(crate) enum Fast {
Contains(String),
Prefix(String),
Suffix(String),
Tail(CharSet),
Head(CharSet),
}
impl Fast {
pub(crate) fn parse(pattern: &str, flags: &str) -> Option<Fast> {
if !flags.is_empty() {
return None;
}
if let Some(rest) = pattern.strip_prefix("^.*") {
if let Some(body) = rest.strip_prefix('[').and_then(|r| r.strip_suffix(']')) {
return plain_set(body).map(Fast::Head);
}
let l = literal(rest)?;
let mut cs = l.chars();
return match (cs.next(), cs.next()) {
(Some(c), None) => Some(Fast::Head(CharSet::One(c))),
_ => None,
};
}
if let Some(body) = pattern
.strip_prefix("[^")
.and_then(|r| r.strip_suffix("]*$"))
{
return plain_set(body).map(Fast::Tail);
}
if let Some(rest) = pattern.strip_prefix('^') {
return literal(rest).map(Fast::Prefix);
}
if let Some(rest) = pattern.strip_suffix('$') {
if let Some(l) = literal(rest) {
return Some(Fast::Suffix(l));
}
}
literal(pattern).map(Fast::Contains)
}
pub(crate) fn is_match(&self, text: &str) -> Option<bool> {
Some(match self {
Fast::Contains(l) => text.contains(l.as_str()),
Fast::Prefix(l) => text.starts_with(l.as_str()),
Fast::Suffix(l) => text.ends_with(l.as_str()),
Fast::Tail(_) => true,
Fast::Head(set) => {
if text.contains('\n') {
return None;
}
set.rfind_end(text).is_some()
}
})
}
pub(crate) fn replace(&self, text: &str, rep: &str) -> Option<String> {
if rep.bytes().any(|b| b == b'$' || b == b'\\') {
return None;
}
Some(match self {
Fast::Contains(l) => text.replace(l.as_str(), rep),
Fast::Prefix(l) => match text.strip_prefix(l.as_str()) {
Some(rest) => [rep, rest].concat(),
None => text.to_string(),
},
Fast::Suffix(l) => match text.strip_suffix(l.as_str()) {
Some(head) => [head, rep].concat(),
None => text.to_string(),
},
Fast::Tail(set) => {
let at = set.rfind_end(text).unwrap_or(0);
[&text[..at], rep].concat()
}
Fast::Head(set) => {
if text.contains('\n') {
return None;
}
match set.rfind_end(text) {
Some(at) => [rep, &text[at..]].concat(),
None => text.to_string(),
}
}
})
}
}
fn plain_set(body: &str) -> Option<CharSet> {
if body.is_empty() || !body.chars().all(plain_class_char) {
return None;
}
let mut bytes: Vec<u8> = body.bytes().collect();
bytes.sort_unstable();
bytes.dedup();
Some(CharSet::Ascii(bytes))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::row::Regex;
use proptest::prelude::*;
fn text() -> impl Strategy<Value = String> {
proptest::collection::vec(
prop_oneof![
4 => proptest::sample::select(vec!['/', '#', 'a', 'b', '.', '$', ' ', ':']),
1 => proptest::sample::select(vec!['\n', '\r', 'é', 'ß', '日', '😀', '\u{301}']),
2 => any::<char>(),
],
0..14,
)
.prop_map(|v| v.into_iter().collect())
}
fn set_chars() -> impl Strategy<Value = Vec<char>> {
proptest::collection::vec(
prop_oneof![
4 => proptest::sample::select(vec!['/', '#', 'a', ':', '.', '$', ' ', '?', '*', '|', '(', '{']),
1 => proptest::char::range(' ', '~'),
],
1..4,
)
.prop_map(|v| v.into_iter().filter(|c| plain_class_char(*c)).collect::<Vec<_>>())
.prop_filter("non-empty", |v| !v.is_empty())
}
fn lit_text() -> impl Strategy<Value = String> {
proptest::collection::vec(
proptest::sample::select(vec![
'a', 'b', '/', '.', '$', '^', '(', 'é', '日', '\\', ' ', '-', '\n',
]),
1..4,
)
.prop_map(|v| v.into_iter().collect())
}
fn escape(l: &str) -> String {
l.chars()
.flat_map(|c| {
if META.contains(c) {
vec!['\\', c]
} else {
vec![c]
}
})
.collect()
}
fn pattern() -> impl Strategy<Value = String> {
prop_oneof![
lit_text().prop_map(|l| escape(&l)),
lit_text().prop_map(|l| format!("^{}", escape(&l))),
lit_text().prop_map(|l| format!("{}$", escape(&l))),
set_chars().prop_map(|s| format!("[^{}]*$", s.iter().collect::<String>())),
set_chars().prop_map(|s| format!("^.*[{}]", s.iter().collect::<String>())),
lit_text()
.prop_map(|l| format!("^.*{}", escape(&l.chars().take(1).collect::<String>()))),
]
}
fn rep() -> impl Strategy<Value = String> {
proptest::sample::select(vec!["", "X", "-", "é日", "$1", "a$", "\\", "$0$0", "[$]"])
.prop_map(String::from)
}
fn check(pat: &str, text: &str, rep: &str) -> Result<(), TestCaseError> {
let re = Regex::new(pat).expect("valid");
let fast = Fast::parse(pat, "");
prop_assert!(fast.is_some(), "shape not recognised: {pat:?}");
let f = fast.unwrap();
if let Some(m) = f.is_match(text) {
prop_assert_eq!(m, re.is_match(text), "REGEX {:?} on {:?}", pat, text);
}
if let Some(out) = f.replace(text, rep) {
prop_assert_eq!(
out,
re.replace_all(text, rep).into_owned(),
"REPLACE {:?} on {:?} with {:?}",
pat,
text,
rep
);
} else {
prop_assert!(
rep.contains(['$', '\\']) || text.contains('\n'),
"declined {pat:?} on {text:?}"
);
}
Ok(())
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(5000))]
#[test]
fn fast_paths_match_the_engine(pat in pattern(), t in text(), r in rep()) {
check(&pat, &t, &r)?;
}
#[test]
fn dense_texts(set in set_chars(), t in proptest::collection::vec(0usize..5, 0..10), r in rep()) {
let alphabet: Vec<char> = set.iter().copied().chain(['x', 'é']).collect();
let text: String = t.iter().map(|i| alphabet[i % alphabet.len()]).collect();
let s: String = set.iter().collect();
for pat in [format!("[^{s}]*$"), format!("^.*[{s}]")] {
check(&pat, &text, &r)?;
}
let l = escape(&s);
for pat in [l.clone(), format!("^{l}"), format!("{l}$")] {
check(&pat, &text, &r)?;
}
}
}
#[test]
fn declines_what_it_does_not_handle() {
for (p, f) in [
("a", "i"),
("[^/]*$", "s"),
("", ""),
("^", ""),
("$", ""),
("a|b", ""),
("(a)", ""),
("a.b", ""),
("a+", ""),
("\\d", ""),
("\\.", "x"),
("[^/]+$", ""),
("[^\\/]*$", ""),
("[^a-z]*$", ""),
("[^]*$", ""),
("[^^]*$", ""),
("[a-z]", ""),
("^.*[a-z]", ""),
("^.*[]", ""),
("^.*ab", ""),
("^.*", ""),
("a\\", ""),
("\\p{L}", ""),
("^a$", ""),
("^^a", ""),
("^.*[é]", ""),
("[^é]*$", ""),
("[^a&&b]*$", ""),
] {
assert!(Fast::parse(p, f).is_none(), "{p:?} {f:?}");
}
}
#[test]
fn known_cases() {
let f = Fast::parse("[^/]*$", "").unwrap();
assert_eq!(f.replace("a/b/c", "X").unwrap(), "a/b/X");
assert_eq!(f.replace("a/", "X").unwrap(), "a/X");
assert_eq!(f.replace("", "X").unwrap(), "X");
let g = Fast::parse("^.*[/#]", "").unwrap();
assert_eq!(g.replace("http://x/y#z", "").unwrap(), "z");
assert_eq!(g.replace("a\nb/c", ""), None);
assert_eq!(g.is_match("nothing"), Some(false));
}
}