mod pattern;
mod x64;
pub(crate) use pattern::Pattern;
#[derive(Debug, thiserror::Error)]
#[error("native regex compilation failed: {0}")]
pub(crate) struct CompileError(String);
impl CompileError {
fn from_display(error: impl std::fmt::Display) -> Self {
Self(error.to_string())
}
}
type MatchFn = unsafe extern "C" fn(*const u8, usize, usize, *mut usize) -> u32;
pub(crate) struct NativeRegex {
_module: CodeOwner,
matcher: MatchFn,
prefix: Option<Vec<u8>>,
code_bytes: usize,
}
enum CodeOwner {
#[cfg(all(target_os = "linux", target_arch = "x86_64"))]
Direct {
_buffer: dynasmrt::ExecutableBuffer,
_classes: Vec<std::sync::Arc<[regex_syntax::hir::ClassUnicodeRange]>>,
},
}
type Emit = Box<dyn FnOnce() -> Option<NativeRegex> + Send + std::panic::UnwindSafe>;
pub(crate) struct LazyNative(std::sync::LazyLock<Option<NativeRegex>, Emit>);
impl LazyNative {
pub(crate) fn new(pattern: pattern::Pattern) -> Self {
Self(std::sync::LazyLock::new(Box::new(move || {
x64::compile(pattern).ok().flatten()
})))
}
pub(crate) fn get(&self) -> Option<&NativeRegex> {
std::sync::LazyLock::force(&self.0).as_ref()
}
}
impl NativeRegex {
pub fn is_match(&self, text: &str) -> Option<bool> {
let mut fuel = 100_000;
if let Some(prefix) = self.prefix.as_deref() {
let mut start = 0;
while start < text.len() {
let bytes = &text.as_bytes()[start..];
let relative = prefix
.chunks(3)
.filter_map(|chunk| match chunk {
[a] => memchr::memchr(*a, bytes),
[a, b] => memchr::memchr2(*a, *b, bytes),
[a, b, c] => memchr::memchr3(*a, *b, *c, bytes),
_ => None,
})
.min();
let Some(relative) = relative else {
return Some(false);
};
start += relative;
match self.at(text, start, &mut fuel)? {
true => return Some(true),
false => start += 1,
}
}
Some(false)
} else {
for (start, _) in text.char_indices() {
if self.at(text, start, &mut fuel)? {
return Some(true);
}
}
self.at(text, text.len(), &mut fuel)
}
}
fn at(&self, text: &str, start: usize, fuel: &mut usize) -> Option<bool> {
*fuel = fuel.checked_sub(1)?;
match unsafe { (self.matcher)(text.as_ptr(), text.len(), start, fuel) } {
0 => Some(false),
1 => Some(true),
_ => None,
}
}
pub fn code_bytes(&self) -> usize {
self.code_bytes
}
}
extern "C" fn word_boundary(text: *const u8, len: usize, position: usize) -> u32 {
let text = unsafe { std::str::from_utf8_unchecked(std::slice::from_raw_parts(text, len)) };
let (Some(left), Some(right)) = (text.get(..position), text.get(position..)) else {
return 2;
};
let word = |character| match character {
Some(character) => regex_syntax::try_is_word_character(character).ok(),
None => Some(false),
};
match (word(left.chars().next_back()), word(right.chars().next())) {
(Some(left), Some(right)) => u32::from(left != right),
_ => 2,
}
}
extern "C" fn unicode_class(
text: *const u8,
len: usize,
position: usize,
ranges: *const regex_syntax::hir::ClassUnicodeRange,
count: usize,
) -> usize {
let text = unsafe { std::str::from_utf8_unchecked(std::slice::from_raw_parts(text, len)) };
let ranges = unsafe { std::slice::from_raw_parts(ranges, count) };
let Some(character) = text.get(position..).and_then(|tail| tail.chars().next()) else {
return usize::MAX;
};
let index = ranges.partition_point(|range| range.end() < character);
if ranges
.get(index)
.is_some_and(|range| range.start() <= character)
{
position + character.len_utf8()
} else {
usize::MAX
}
}
extern "C" fn unicode_backref(
text: *const u8,
len: usize,
position: usize,
capture: usize,
width: usize,
) -> u32 {
let text = unsafe { std::str::from_utf8_unchecked(std::slice::from_raw_parts(text, len)) };
let (Some(left), Some(right)) = (
text.get(capture..capture + width),
text.get(position..position + width),
) else {
return 0;
};
let mut left = left.chars();
let mut right = right.chars();
loop {
match (left.next(), right.next()) {
(None, None) => return 1,
(Some(a), Some(b)) if a == b => {}
(Some(a), Some(b)) if a.is_ascii() && b.is_ascii() => {
if !a.eq_ignore_ascii_case(&b) {
return 0;
}
}
(Some(a), Some(b)) => {
let mut class = regex_syntax::hir::ClassUnicode::new([
regex_syntax::hir::ClassUnicodeRange::new(a, a),
]);
if class.try_case_fold_simple().is_err()
|| !class
.ranges()
.iter()
.any(|range| range.start() <= b && b <= range.end())
{
return 0;
}
}
_ => return 0,
}
}
}
extern "C" fn scan_any(text: *const u8, len: usize, start: usize, crlf: usize) -> usize {
if start > len {
return len;
}
let bytes = unsafe { std::slice::from_raw_parts(text, len) };
let tail = &bytes[start..];
let newline = if crlf == 0 {
memchr::memchr(b'\n', tail)
} else {
memchr::memchr2(b'\n', b'\r', tail)
};
start + newline.unwrap_or(tail.len())
}
#[cfg(test)]
mod tests {
use crate::Regex;
#[test]
fn native_decisions_match_oracle_without_hidden_portable_fallback() {
let patterns = [
r"(a|ab)\1",
r"(?i:(é)\1)",
r"(?i:(Σ)\1)",
r"(?<=a)b",
r"a(?!b)",
r"(?>a|ab)c",
r"(a)?(?(1)b|c)",
];
let mut texts = alloc::vec![alloc::string::String::new()];
let mut previous = texts.clone();
for _ in 0..3 {
let mut next = alloc::vec::Vec::new();
for prefix in previous {
for suffix in ["a", "b", "c", "é", "É", "Σ", "σ", "ς", " "] {
next.push(alloc::format!("{prefix}{suffix}"));
}
}
texts.extend(next.iter().cloned());
previous = next;
}
for pattern in patterns {
let regex = Regex::new(pattern).unwrap();
let native = regex
.native
.as_ref()
.and_then(|native| native.get())
.expect("pattern should be accelerated");
let oracle = oracle::Regex::new(pattern).unwrap();
for text in &texts {
assert_eq!(
native.is_match(text),
Some(oracle.is_match(text).unwrap()),
"{pattern} {text:?}"
);
}
}
}
#[test]
fn exhausted_native_work_returns_deferral_not_a_false_nonmatch() {
let regex = Regex::new(r"\A(a+)\1\z").unwrap();
let native = regex
.native
.as_ref()
.and_then(|native| native.get())
.unwrap();
let input = "a".repeat(100_002);
assert_eq!(native.is_match(&input), None);
assert!(regex.is_match(&input).unwrap());
}
}