pub trait SyntaxLookup {
fn ranges(&self, class: char) -> Vec<(u32, u32)>;
fn category_ranges(&self, _category: u8) -> Vec<(u32, u32)> {
Vec::new()
}
fn available(&self) -> bool {
true
}
fn at_dot(&self) -> String {
r"\G".to_string()
}
}
pub struct NoSyntax;
impl SyntaxLookup for NoSyntax {
fn ranges(&self, _class: char) -> Vec<(u32, u32)> {
Vec::new()
}
fn available(&self) -> bool {
false
}
}
pub fn translate(pat: &str) -> Result<String, String> {
translate_with(pat, &NoSyntax)
}
pub fn translate_with(pat: &str, syn: &dyn SyntaxLookup) -> Result<String, String> {
translate_groups(pat, syn).map(|(re, _)| re)
}
pub fn translate_groups(pat: &str, syn: &dyn SyntaxLookup) -> Result<(String, Vec<u32>), String> {
let mut out = String::with_capacity(pat.len() + 8);
let mut it = pat.chars().peekable();
let mut depth: i32 = 0;
let mut groups = Groups::default();
let mut can_repeat = false;
let mut laststart: usize = 0;
let mut group_starts: Vec<usize> = Vec::new();
let mut repeated = false;
let mut at_begline = true;
while let Some(c) = it.next() {
let tok_start = out.len();
let begline = std::mem::replace(&mut at_begline, false);
match c {
'\\' => {
let e = it.peek().copied();
if e == Some('{') {
let save = it.clone();
let mut scratch = String::new();
translate_escape(
&mut it,
&mut scratch,
&mut depth,
&mut can_repeat.clone(),
syn,
&mut groups,
)?;
if !can_repeat {
it = save;
it.next();
out.push_str(r"\{");
can_repeat = true;
laststart = tok_start;
repeated = false;
continue;
}
if repeated {
wrap_group(&mut out, laststart);
}
out.push_str(&scratch);
repeated = true;
continue;
}
translate_escape(
&mut it,
&mut out,
&mut depth,
&mut can_repeat,
syn,
&mut groups,
)?;
match e {
Some('(') => {
group_starts.push(tok_start);
at_begline = true;
}
Some(')') => {
laststart = group_starts.pop().unwrap_or(tok_start);
repeated = false;
}
Some('|') => at_begline = true,
_ => {
laststart = tok_start;
repeated = false;
}
}
}
'(' | ')' | '{' | '}' | '|' => {
out.push('\\');
out.push(c);
can_repeat = true;
laststart = tok_start;
repeated = false;
}
'[' => {
copy_class(&mut it, &mut out, syn)?;
can_repeat = true;
laststart = tok_start;
repeated = false;
}
'*' | '+' | '?' if can_repeat => {
let (mut zero, mut many, mut greedy) = (false, false, true);
let mut op = c;
loop {
if op == '?' && (zero || many) {
greedy = false;
} else {
zero |= op != '+';
many |= op != '?';
}
match it.peek() {
Some(&n @ ('*' | '+' | '?')) => {
it.next();
op = n;
}
_ => break,
}
}
if repeated {
wrap_group(&mut out, laststart);
}
out.push(match (zero, many) {
(true, true) => '*',
(false, true) => '+',
_ => '?',
});
if !greedy {
out.push('?');
}
repeated = true;
}
'*' | '+' | '?' => {
out.push('\\');
out.push(c);
can_repeat = true;
laststart = tok_start;
repeated = false;
}
'^' if begline => {
out.push('^');
can_repeat = false;
}
'$' if {
let mut ahead = it.clone();
match ahead.next() {
None => true,
Some('\\') => matches!(ahead.next(), Some(')' | '|')),
Some(_) => false,
}
} =>
{
out.push('$');
can_repeat = true;
laststart = tok_start;
repeated = false;
}
'^' | '$' | '.' => {
if c == '.' {
out.push('.');
} else {
out.push('\\');
out.push(c);
}
can_repeat = true;
laststart = tok_start;
repeated = false;
}
_ => {
out.push(c);
can_repeat = true;
laststart = tok_start;
repeated = false;
}
}
}
if depth > 0 {
return Err(UNMATCHED_OPEN.into());
}
Ok((out, groups.emitted))
}
fn wrap_group(out: &mut String, start: usize) {
out.insert_str(start, "(?:");
out.push(')');
}
#[derive(Default)]
struct Groups {
nsub: u32,
emitted: Vec<u32>,
open: Vec<u32>,
}
const MAX_SCALAR: u32 = 0x10FFFF;
fn char_class(ranges: &[(u32, u32)], neg: bool) -> String {
let mut body = ranges_body(ranges);
if body.is_empty() {
body = "\\x{0}-\\x{10FFFF}".to_string();
return format!("(?-i:[{}{body}])", if neg { "" } else { "^" });
}
format!("(?-i:[{}{body}])", if neg { "^" } else { "" })
}
fn ranges_body(ranges: &[(u32, u32)]) -> String {
let mut body = String::new();
for &(lo, hi) in ranges {
if lo > MAX_SCALAR {
continue;
}
let hi = hi.min(MAX_SCALAR);
for (a, b) in [(lo, hi.min(0xD7FF)), (lo.max(0xE000), hi)] {
if a > b || a > MAX_SCALAR {
continue;
}
if a == b {
body.push_str(&format!("\\x{{{a:X}}}"));
} else {
body.push_str(&format!("\\x{{{a:X}}}-\\x{{{b:X}}}"));
}
}
}
body
}
const UNMATCHED_OPEN: &str = "Unmatched ( or \\(";
const UNMATCHED_CLOSE: &str = "Unmatched ) or \\)";
const UNMATCHED_BRACKET: &str = "Unmatched [ or [^";
const UNMATCHED_BRACE: &str = "Unmatched \\{";
const INVALID_BRACE_CONTENT: &str = "Invalid content of \\{\\}";
const TRAILING_BACKSLASH: &str = "Trailing backslash";
const INVALID_REGEXP: &str = "Invalid regular expression";
const INVALID_BACKREF: &str = "Invalid back reference";
const PREMATURE_END: &str = "Premature end of regular expression";
const INVALID_CLASS_NAME: &str = "Invalid character class name";
pub(crate) const NEVER_MATCHES: &str = "[^\\s\\S]";
const CLASS_NAMES: [&str; 17] = [
"alnum",
"alpha",
"ascii",
"blank",
"cntrl",
"digit",
"graph",
"lower",
"multibyte",
"nonascii",
"print",
"punct",
"space",
"unibyte",
"upper",
"word",
"xdigit",
];
pub(crate) fn is_class_name(name: &str) -> bool {
CLASS_NAMES.contains(&name)
}
fn translate_escape(
it: &mut std::iter::Peekable<std::str::Chars>,
out: &mut String,
depth: &mut i32,
can_repeat: &mut bool,
syn: &dyn SyntaxLookup,
groups: &mut Groups,
) -> Result<(), String> {
let Some(e) = it.next() else {
return Err(TRAILING_BACKSLASH.into());
};
*can_repeat = !matches!(e, '(' | '|');
match e {
'(' => {
if it.peek() == Some(&'?') {
it.next(); if matches!(it.peek(), Some(d) if d.is_ascii_digit()) {
let mut n: u32 = 0;
while let Some(&d) = it.peek() {
if !d.is_ascii_digit() {
break;
}
it.next();
n = n
.saturating_mul(10)
.saturating_add(d as u32 - '0' as u32)
.min(u32::MAX / 16);
}
if n == 0 || it.peek() != Some(&':') {
return Err(INVALID_REGEXP.into());
}
it.next(); if n > groups.nsub {
groups.nsub = n;
}
groups.emitted.push(n);
groups.open.push(n);
out.push('(');
} else {
if it.peek() != Some(&':') {
return Err(INVALID_REGEXP.into());
}
it.next();
out.push_str("(?:");
groups.open.push(0);
}
} else {
out.push('(');
groups.nsub += 1;
groups.emitted.push(groups.nsub);
groups.open.push(groups.nsub);
}
*depth += 1;
}
')' => {
if *depth == 0 {
return Err(UNMATCHED_CLOSE.into());
}
*depth -= 1;
groups.open.pop();
out.push(')');
}
'|' => out.push('|'),
'{' => {
let mut body = String::new();
let mut closed = false;
while let Some(c) = it.next() {
if c == '\\' {
match it.next() {
Some('}') => {
closed = true;
break;
}
Some(_) => return Err(INVALID_BRACE_CONTENT.into()),
None => return Err(TRAILING_BACKSLASH.into()),
}
} else if c.is_ascii_digit() || (c == ',' && !body.contains(',')) {
body.push(c);
} else {
return Err(INVALID_BRACE_CONTENT.into());
}
}
if !closed {
return Err(UNMATCHED_BRACE.into());
}
if !valid_brace_body(&body) {
return Err(INVALID_BRACE_CONTENT.into());
}
out.push('{');
if body.is_empty() || body.starts_with(',') {
out.push('0');
}
out.push_str(&body);
out.push('}');
}
'}' => out.push_str(r"\}"),
'`' => out.push_str(r"\A"),
'\'' => out.push_str(r"\z"),
'<' | '>' | 'b' | 'B' if syn.available() => {
let w = char_class(&syn.ranges('w'), false);
out.push_str(&match e {
'<' => format!("(?={w})(?<!{w})"),
'>' => format!("(?<={w})(?!{w})"),
'b' => format!(r"(?:\A|\z|(?<={w})(?!{w})|(?<!{w})(?={w}))"),
_ => format!(r"(?!\A)(?!\z)(?:(?<={w})(?={w})|(?<!{w})(?!{w}))"),
});
}
'_' if syn.available() && matches!(it.peek(), Some('<') | Some('>')) => {
let mut ranges = syn.ranges('w');
ranges.extend(syn.ranges('_'));
let s = char_class(&ranges, false);
out.push_str(&if it.next() == Some('<') {
format!("(?={s})(?<!{s})")
} else {
format!("(?<={s})(?!{s})")
});
}
'<' | '>' => out.push_str(r"\b"),
'_' => {
match it.next() {
Some('<') | Some('>') => out.push_str(r"\b"),
Some(o) => {
out.push('_');
out.push(o);
}
None => out.push('_'),
}
}
'=' => out.push_str(&syn.at_dot()),
'w' | 'W' => {
if syn.available() {
out.push_str(&char_class(&syn.ranges('w'), e == 'W'));
} else {
out.push_str(if e == 'W' { r"\W" } else { r"\w" });
}
}
'b' => out.push_str(r"\b"),
'B' => out.push_str(r"\B"),
's' | 'S' => {
let neg = e == 'S';
let class = it.peek().copied();
let class = class.map(|c| if c == '-' { ' ' } else { c });
if let (true, Some(class)) = (syn.available(), class) {
it.next();
out.push_str(&char_class(&syn.ranges(class), neg));
return Ok(());
}
match it.next() {
Some('-') | Some(' ') => out.push_str(if neg { WS_SYNTAX_NEG } else { WS_SYNTAX }),
Some('w') => out.push_str(if neg { r"\W" } else { r"\w" }),
Some(_) | None => out.push_str(if neg { WS_SYNTAX_NEG } else { WS_SYNTAX }),
}
}
'1'..='9' => {
let reg = e as u32 - '0' as u32;
if reg > groups.nsub || groups.open.contains(®) {
return Err(INVALID_BACKREF.into());
}
match groups.emitted.iter().rposition(|&g| g == reg) {
Some(i) => {
out.push('\\');
out.push_str(&(i + 1).to_string());
}
None => out.push_str(NEVER_MATCHES),
}
}
'c' | 'C' => {
let Some(cat) = it.next() else {
return Err(PREMATURE_END.into());
};
let ranges = if cat.is_ascii() {
syn.category_ranges(cat as u8)
} else {
Vec::new()
};
out.push_str(&char_class(&ranges, e == 'C'));
}
other => {
out.push('\\');
out.push(other);
}
}
Ok(())
}
fn valid_brace_body(body: &str) -> bool {
let parse = |s: &str| -> Option<u64> { s.parse().ok() };
match body.split_once(',') {
None => body.chars().all(|c| c.is_ascii_digit()),
Some((lo, hi)) => {
let lo_v = if lo.is_empty() { Some(0) } else { parse(lo) };
match (lo_v, hi.is_empty()) {
(Some(_), true) => true,
(Some(l), false) => matches!(parse(hi), Some(h) if l <= h),
_ => false,
}
}
}
}
const WS_SYNTAX: &str = "[\\t\\x0C\\x{A0} ]";
const WS_SYNTAX_NEG: &str = "[^\\t\\x0C\\x{A0} ]";
fn posix_class(name: &str, syn: &dyn SyntaxLookup) -> Option<std::borrow::Cow<'static, str>> {
use std::borrow::Cow;
if syn.available() {
if let Some(body) = syntax_class_body(name, syn) {
return Some(Cow::Owned(body));
}
}
Some(Cow::Borrowed(match name {
"alpha" => r"\p{Alphabetic}\p{M}",
"alnum" => r"\p{Alphabetic}\p{M}\p{Nd}",
"space" => r"\p{White_Space}",
"upper" => case_class_body(true),
"lower" => case_class_body(false),
"punct" => r"\p{P}\p{S}",
"word" => r"\p{Alphabetic}\p{Nd}\p{M}",
"blank" => "\t\\p{Zs}",
"cntrl" => r"\x00-\x1F",
"ascii" | "unibyte" => "[:ascii:]",
"nonascii" | "multibyte" => "[:^ascii:]",
"graph" => r"\p{L}\p{M}\p{N}\p{P}\p{S}\p{Co}\p{Cf}",
"print" => r"\p{L}\p{M}\p{N}\p{P}\p{S}\p{Co}\p{Cf}\p{Z}",
_ => return None,
}))
}
fn case_class_body(upper: bool) -> &'static str {
use std::sync::OnceLock;
static BODIES: OnceLock<[String; 2]> = OnceLock::new();
let bodies = BODIES.get_or_init(|| {
let simple = |mut m: Box<dyn Iterator<Item = char>>, c: char| match (m.next(), m.next()) {
(Some(x), None) => x != c,
_ => false,
};
let mut up: Vec<(u32, u32)> = Vec::new();
let mut lo: Vec<(u32, u32)> = Vec::new();
let push = |v: &mut Vec<(u32, u32)>, c: u32| match v.last_mut() {
Some(last) if last.1 + 1 == c => last.1 = c,
_ => v.push((c, c)),
};
for c in (0..=MAX_SCALAR).filter_map(char::from_u32) {
if simple(Box::new(c.to_lowercase()), c) {
push(&mut up, c as u32);
} else if simple(Box::new(c.to_uppercase()), c) {
push(&mut lo, c as u32);
}
}
[ranges_body(&lo), ranges_body(&up)]
});
&bodies[upper as usize]
}
fn syntax_class_body(name: &str, syn: &dyn SyntaxLookup) -> Option<String> {
match name {
"space" => Some(ranges_body(&syn.ranges(' '))),
"word" => Some(ranges_body(&syn.ranges('w'))),
"punct" => {
let mut ranges = vec![(0x21, 0x2F), (0x3A, 0x40), (0x5B, 0x60), (0x7B, 0x7E)];
let mut next = 0x80;
for (lo, hi) in syn.ranges('w') {
if hi < 0x80 {
continue;
}
let lo = lo.max(0x80);
if lo > next {
ranges.push((next, lo - 1));
}
next = next.max(hi + 1);
}
if next <= MAX_SCALAR {
ranges.push((next, MAX_SCALAR));
}
Some(ranges_body(&ranges))
}
_ => None,
}
}
fn copy_class(
it: &mut std::iter::Peekable<std::str::Chars>,
out: &mut String,
syn: &dyn SyntaxLookup,
) -> Result<(), String> {
let mut buf = String::new();
let mut closed = false;
let out_start = out.len();
out.push('[');
if it.peek() == Some(&'^') {
out.push('^');
it.next();
}
if it.peek() == Some(&']') {
push_member(']', out, &mut buf);
it.next();
copy_range(it, out, &mut buf)?;
}
while let Some(c) = it.next() {
match c {
'\\' => {
push_member('\\', out, &mut buf);
copy_range(it, out, &mut buf)?;
}
'[' => match wctype_at(it) {
Some(name) => {
if !CLASS_NAMES.contains(&name.as_str()) {
return Err(INVALID_CLASS_NAME.into());
}
match posix_class(&name, syn) {
Some(repl) => out.push_str(&repl),
None => out.push_str(&format!("[:{name}:]")),
}
}
None => {
push_member('[', out, &mut buf);
copy_range(it, out, &mut buf)?;
}
},
']' => {
out.push(']');
closed = true;
break;
}
_ => {
push_member(c, out, &mut buf);
copy_range(it, out, &mut buf)?;
}
}
}
if !closed {
return Err(UNMATCHED_BRACKET.into());
}
if has_reversed_range(&buf) {
out.truncate(out_start);
out.push_str(NEVER_MATCHES);
}
Ok(())
}
fn push_member(c: char, out: &mut String, buf: &mut String) {
match c {
'\\' => out.push_str("\\\\"),
'[' => out.push_str("\\["),
']' => out.push_str("\\]"),
_ => out.push(c),
}
buf.push(c);
}
fn copy_range(
it: &mut std::iter::Peekable<std::str::Chars>,
out: &mut String,
buf: &mut String,
) -> Result<(), String> {
let mut la = it.clone();
if la.next() != Some('-') {
return Ok(());
}
match la.next() {
Some(']') => Ok(()),
None => Err(PREMATURE_END.into()),
Some(end) => {
it.next();
it.next();
out.push('-');
buf.push('-');
push_member(end, out, buf);
Ok(())
}
}
}
fn wctype_at(it: &mut std::iter::Peekable<std::str::Chars>) -> Option<String> {
let rest: Vec<char> = std::iter::once('[').chain(it.clone()).collect();
if rest.len() < 4 || rest[1] != ':' {
return None;
}
let mut limit = rest.len() - 3;
let mut i = 2;
while !(rest.get(i) == Some(&':') && rest.get(i + 1) == Some(&']')) {
limit -= 1;
if limit == 0 {
return None;
}
i += 1;
}
for _ in 0..i + 1 {
it.next();
}
Some(rest[2..i].iter().collect())
}
fn has_reversed_range(body: &str) -> bool {
let cs: Vec<char> = body.chars().collect();
let mut i = 0;
while i + 2 < cs.len() {
if cs[i + 1] == '-' && cs[i + 2] != ']' && cs[i] > cs[i + 2] {
return true;
}
i += 1;
}
false
}
#[cfg(test)]
mod tests {
use super::translate;
fn t(p: &str) -> String {
translate(p).unwrap()
}
#[test]
fn grouping_and_alternation_invert() {
assert_eq!(t(r"\(ab\|cd\)+"), "(ab|cd)+");
assert_eq!(t(r"a(b)c"), r"a\(b\)c");
assert_eq!(t(r"\(?:foo\)"), "(?:foo)");
assert_eq!(t(r"\(?1:foo\)"), "(foo)");
assert_eq!(t(r"\(?1:a\)-\(?2:b\)"), "(a)-(b)");
assert_eq!(t(r"\(?:x\)\(?1:y\)"), "(?:x)(y)");
}
#[test]
fn bounds_and_anchors() {
assert_eq!(t(r"a\{2,3\}"), "a{2,3}");
assert_eq!(t(r"\`foo\'"), r"\Afoo\z");
assert_eq!(t(r"\<word\>"), r"\bword\b");
}
#[test]
fn classes_pass_through() {
assert_eq!(t(r"[a-z]+"), "[a-z]+");
assert_eq!(t(r"[]ab]"), r"[\]ab]");
assert_eq!(t(r"[]-a]"), r"[\]-a]");
assert_eq!(t(r"[[:alpha:]]"), r"[\p{Alphabetic}\p{M}]");
assert_eq!(t(r"[^()]"), "[^()]");
assert_eq!(t(r"[{[]"), r"[{\[]");
assert_eq!(t(r"\\[{[]"), r"\\[{\[]");
}
#[test]
fn syntax_and_word_escapes() {
assert_eq!(t(r"\w+\s-\sw"), "\\w+[\\t\\x0C\\x{A0} ]\\w");
}
#[test]
fn whitespace_syntax_class_excludes_line_terminators() {
let re = fancy_regex::Regex::new(&t(r"\s-")).expect("compiles");
for yes in ["\t", "\u{0C}", " ", "\u{A0}"] {
assert!(re.is_match(yes).unwrap(), "\\s- must match {yes:?}");
}
for no in ["\n", "\r", "\u{0B}", "a"] {
assert!(!re.is_match(no).unwrap(), "\\s- must not match {no:?}");
}
}
#[test]
fn backreference_maps_to_the_emitted_group() {
assert_eq!(t(r"\(a\)\1"), r"(a)\1");
assert_eq!(t(r"\(?3:a\)\3"), r"(a)\1");
assert_eq!(t(r"\(?2:a\)\1"), r"(a)[^\s\S]");
}
#[test]
fn out_of_range_and_self_referential_backreferences_are_rejected() {
for pat in [
r"\1",
r"x\2",
r"\(a\)\2",
r"\(?:a\)\1",
r"\(a\1\)",
r"\(\1\)",
] {
assert_eq!(
translate(pat).unwrap_err(),
"Invalid back reference",
"{pat} must not compile"
);
}
}
#[test]
fn character_alternative_diagnostics() {
assert_eq!(
translate(r"[a-").unwrap_err(),
"Premature end of regular expression"
);
assert_eq!(translate(r"[a-b-").unwrap_err(), "Unmatched [ or [^");
assert_eq!(
translate(r"[[:foo:]]").unwrap_err(),
"Invalid character class name"
);
assert_eq!(t(r"[[:]"), r"[\[:]");
assert_eq!(t(r"[[:a]b]"), r"[\[:a]b]");
}
}