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 fn compile(pattern: &str, size_limit: usize) -> Result<CompiledPattern, PatternError> {
let fast = match RegexBuilder::new(pattern).size_limit(size_limit).build() {
Ok(regex) => return Ok(CompiledPattern::Fast(regex)),
Err(err) => err,
};
match FancyRegexBuilder::new(pattern)
.backtrack_limit(BACKTRACK_LIMIT)
.delegate_size_limit(size_limit)
.build()
{
Ok(regex) => Ok(CompiledPattern::Fancy(regex)),
Err(fancy) => Err(PatternError { fast, fancy }),
}
}
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 identify(&self, text: &str, version_group: Option<u8>) -> Option<PatternMatch> {
let version = match self {
CompiledPattern::Fast(regex) => {
let captures = regex.captures(text)?;
version_group
.and_then(|group| captures.get(group as usize))
.map(|m| m.as_str().to_string())
}
CompiledPattern::Fancy(regex) => {
let captures = regex.captures(text).ok()??;
version_group
.and_then(|group| captures.get(group as usize))
.map(|m| m.as_str().to_string())
}
};
Some(PatternMatch { version })
}
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
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); }
proptest! {
#[test]
fn fancy_engine_matching_terminates_on_any_input(input in "(?s).*") {
let compiled = compile(r"^(\w+)\s+\1$", LIMIT).unwrap();
let _ = compiled.identify(&input, None);
}
#[test]
fn catastrophic_pattern_stays_bounded(len in 0usize..64) {
let compiled = compile(r"(a+)+\1c", LIMIT).unwrap();
let _ = compiled.identify(&"a".repeat(len), None);
}
}
}