use fancy_regex::RegexBuilder as FancyRegexBuilder;
use regex::{Regex, RegexBuilder};
const BACKTRACK_LIMIT: usize = 1_000_000;
#[derive(Debug)]
pub enum CompiledPattern {
Fast(Regex),
Fancy(fancy_regex::Regex),
}
#[derive(Debug)]
pub struct PatternError {
pub fast: regex::Error,
pub fancy: fancy_regex::Error,
}
impl std::fmt::Display for PatternError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"rejected by the linear engine ({}) and the backtracking engine ({})",
self.fast, self.fancy
)
}
}
#[allow(dead_code)]
pub struct PatternMatch {
pub version: Option<String>,
pub match_len: usize,
pub captures: Option<Vec<String>>,
}
pub fn compile(pattern: &str, size_limit: usize) -> Result<CompiledPattern, PatternError> {
let fast = match RegexBuilder::new(&ascii_classes(pattern, Boundaries::Flagged))
.size_limit(size_limit)
.build()
{
Ok(regex) => return Ok(CompiledPattern::Fast(regex)),
Err(err) => err,
};
match FancyRegexBuilder::new(&ascii_classes(pattern, Boundaries::LookedAround))
.backtrack_limit(BACKTRACK_LIMIT)
.delegate_size_limit(size_limit)
.build()
{
Ok(regex) => Ok(CompiledPattern::Fancy(regex)),
Err(fancy) => Err(PatternError { fast, fancy }),
}
}
#[derive(Debug, Clone, Copy)]
enum Boundaries {
Flagged,
LookedAround,
}
fn ascii_classes(pattern: &str, boundaries: Boundaries) -> String {
let mut out = String::with_capacity(pattern.len());
let mut chars = pattern.char_indices().peekable();
let mut depth = 0usize;
while let Some((at, c)) = chars.next() {
match c {
'\\' => {
let Some((_, escaped)) = chars.next() else {
out.push(c);
break;
};
let class = match escaped.to_ascii_lowercase() {
'd' => Some("digit"),
'w' => Some("word"),
's' => Some("space"),
_ => None,
};
match class {
Some(name) => {
let negated = if escaped.is_ascii_uppercase() {
"^"
} else {
""
};
if depth == 0 {
out.push_str(&format!("[[:{negated}{name}:]]"));
} else {
out.push_str(&format!("[:{negated}{name}:]"));
}
}
None if depth == 0 && matches!(escaped, 'b' | 'B') => {
out.push_str(match (boundaries, escaped) {
(Boundaries::Flagged, 'b') => r"(?-u:\b)",
(Boundaries::Flagged, _) => r"(?-u:\B)",
(Boundaries::LookedAround, 'b') => {
r"(?:(?<=[[:word:]])(?![[:word:]])|(?<![[:word:]])(?=[[:word:]]))"
}
(Boundaries::LookedAround, _) => {
r"(?:(?<=[[:word:]])(?=[[:word:]])|(?<![[:word:]])(?![[:word:]]))"
}
});
}
None => {
out.push(c);
out.push(escaped);
}
}
}
'[' if depth > 0 && pattern[at..].starts_with("[:") => {
match pattern[at..].find(":]") {
Some(end) => {
out.push_str(&pattern[at..at + end + 2]);
while chars.peek().is_some_and(|&(next, _)| next < at + end + 2) {
chars.next();
}
}
None => out.push(c),
}
}
'[' => {
depth += 1;
out.push(c);
if let Some(&(_, '^')) = chars.peek() {
out.push('^');
chars.next();
}
if let Some(&(_, ']')) = chars.peek() {
out.push(']');
chars.next();
}
}
']' if depth > 0 => {
depth -= 1;
out.push(c);
}
_ => out.push(c),
}
}
out
}
impl CompiledPattern {
#[allow(dead_code)]
pub fn captures_len(&self) -> usize {
match self {
CompiledPattern::Fast(regex) => regex.captures_len(),
CompiledPattern::Fancy(regex) => regex.captures_len(),
}
}
#[allow(dead_code)]
pub fn capture_names(&self) -> Vec<String> {
match self {
CompiledPattern::Fast(regex) => {
regex.capture_names().flatten().map(String::from).collect()
}
CompiledPattern::Fancy(regex) => {
regex.capture_names().flatten().map(String::from).collect()
}
}
}
#[allow(dead_code)]
pub fn capture(&self, text: &str, name: &str) -> Option<String> {
match self {
CompiledPattern::Fast(regex) => regex
.captures(text)
.and_then(|captures| captures.name(name))
.map(|group| group.as_str().to_string()),
CompiledPattern::Fancy(regex) => regex
.captures(text)
.ok()
.flatten()
.and_then(|captures| captures.name(name))
.map(|group| group.as_str().to_string()),
}
}
#[allow(dead_code)]
pub fn identify(&self, text: &str, version_group: Option<u8>) -> Option<PatternMatch> {
self.identify_with_captures(text, version_group, false)
}
pub fn identify_with_captures(
&self,
text: &str,
version_group: Option<u8>,
keep_captures: bool,
) -> Option<PatternMatch> {
macro_rules! extract {
($captures:expr) => {{
let captures = $captures;
let match_len = captures.get(0).map_or(0, |m| m.as_str().chars().count());
let version = version_group
.and_then(|group| captures.get(group as usize))
.map(|m| m.as_str().to_string());
let groups = keep_captures.then(|| {
(0..captures.len())
.map(|index| {
captures
.get(index)
.map(|m| m.as_str().to_string())
.unwrap_or_default()
})
.collect::<Vec<String>>()
});
(version, groups, match_len)
}};
}
let (version, captures, match_len) = match self {
CompiledPattern::Fast(regex) => extract!(regex.captures(text)?),
CompiledPattern::Fancy(regex) => extract!(regex.captures(text).ok()??),
};
Some(PatternMatch {
version,
captures,
match_len,
})
}
}
#[cfg(test)]
mod tests {
use super::*;
const LIMIT: usize = 32 * 1024 * 1024;
#[test]
fn plain_pattern_takes_the_linear_engine() {
let compiled = compile(r"^SSH-2\.0-OpenSSH_([\w.]+)", LIMIT).expect("compiles");
assert!(matches!(compiled, CompiledPattern::Fast(_)));
let m = compiled
.identify("SSH-2.0-OpenSSH_9.6p1", Some(1))
.expect("matches");
assert_eq!(m.version.as_deref(), Some("9.6p1"));
assert!(compiled.identify("HTTP/1.1 200 OK", Some(1)).is_none());
}
#[test]
fn backreference_pattern_falls_back_to_the_fancy_engine() {
let compiled = compile(r"^(\w+)\s+\1$", LIMIT).expect("compiles via fancy");
assert!(matches!(compiled, CompiledPattern::Fancy(_)));
assert!(compiled.identify("abc abc", None).is_some());
assert!(compiled.identify("abc def", None).is_none());
}
#[test]
fn lookahead_pattern_falls_back_to_the_fancy_engine() {
let compiled = compile(r"foo(?=bar)", LIMIT).expect("compiles via fancy");
assert!(matches!(compiled, CompiledPattern::Fancy(_)));
assert!(compiled.identify("foobar", None).is_some());
assert!(compiled.identify("foobaz", None).is_none());
}
#[test]
fn fancy_pattern_can_still_capture_a_version_group() {
let compiled = compile(r"^(\w+)-\1/([\d.]+)$", LIMIT).expect("compiles via fancy");
let m = compiled
.identify("srv-srv/1.2.3", Some(2))
.expect("matches");
assert_eq!(m.version.as_deref(), Some("1.2.3"));
}
#[test]
fn catastrophic_backtracking_is_bounded_not_a_hang() {
let compiled = compile(r"(a+)+\1c", LIMIT).expect("compiles via fancy");
assert!(matches!(compiled, CompiledPattern::Fancy(_)));
let adversarial = "a".repeat(40);
assert!(compiled.identify(&adversarial, None).is_none());
}
#[test]
fn a_pattern_no_engine_can_compile_is_an_error() {
let err = compile("(", LIMIT).expect_err("neither engine compiles it");
let msg = err.to_string();
assert!(msg.contains("linear engine") && msg.contains("backtracking engine"));
}
#[test]
fn captures_len_counts_the_whole_match_group() {
assert_eq!(compile(r"^ab$", LIMIT).unwrap().captures_len(), 1); assert_eq!(compile(r"^(a)(b)$", LIMIT).unwrap().captures_len(), 3); assert_eq!(compile(r"^(\w+)\s+\1$", LIMIT).unwrap().captures_len(), 2); }
#[test]
fn capture_names_lists_the_named_groups_only() {
assert_eq!(
compile(r"v(?<version>[0-9.]+) \((\w+)\)", LIMIT)
.unwrap()
.capture_names(),
vec!["version".to_string()]
);
assert!(
compile(r"^\+PONG", LIMIT)
.unwrap()
.capture_names()
.is_empty()
);
assert_eq!(
compile(r"(?<w>\w+)\s+\k<w>", LIMIT)
.unwrap()
.capture_names(),
vec!["w".to_string()]
);
}
#[test]
fn perl_classes_and_word_boundaries_read_as_ascii_on_both_engines() {
for (pattern, fancy) in [(r"^\w+\s\d+\b", false), (r"^(\w+)\s\d+\b(?!\1)", true)] {
let compiled = compile(pattern, LIMIT).expect("compiles");
assert_eq!(matches!(compiled, CompiledPattern::Fancy(_)), fancy);
assert!(compiled.identify("abc_1 42", None).is_some(), "{pattern}");
for text in ["caf\u{e9} 42", "abc \u{663}", "abc\u{a0}42"] {
assert!(
compiled.identify(text, None).is_none(),
"{pattern} on {text:?}"
);
}
}
let bounded = compile(r"\bfoo\b", LIMIT).expect("compiles");
assert!(bounded.identify("\u{e9}foo\u{e9}", None).is_some());
assert!(bounded.identify("afoo", None).is_none());
}
#[test]
fn the_rewrite_leaves_everything_else_as_written() {
let cases: &[(&str, &str, bool)] = &[
(r"^\\d$", r"\d", true),
(r"^\\d$", "1", false),
(r"^[\d.]+$", "1.2.3", true),
(r"^[^\s]+$", "a\u{a0}b", true),
(r"^[\S]+$", "a b", false),
(r"^[]\w]+$", "]a]", true),
(r"^[^]\d]+$", "ab", true),
(r"^[^]\d]+$", "a]", false),
(r"^[[:alpha:]\d]+$", "a1", true),
(r"^[a-z&&[^\d]]+$", "ab", true),
(r"^\p{L}+$", "caf\u{e9}", true),
(r"^\x41\u{42}$", "AB", true),
];
for &(pattern, text, matches) in cases {
let compiled = compile(pattern, LIMIT).expect(pattern);
assert_eq!(
compiled.identify(text, None).is_some(),
matches,
"{pattern} on {text:?}"
);
}
}
#[test]
fn a_long_repetition_of_a_class_compiles_small() {
let pattern = r"^([\w.-]{1,512}) X2 WS_FTP Server ([\d.]{3,6}\s?\(\d+\))$";
compile(pattern, 1024 * 1024).expect("compiles under a megabyte");
}
}