#![doc = include_str!("../docs/main.md")]
#![doc = include_str!("../docs/features.md")]
#![doc = include_str!("../docs/syntax.md")]
#![doc = include_str!("../docs/subroutines/1_intro.md")]
#![doc = include_str!("../docs/subroutines/2_flags.md")]
#![doc = include_str!("../docs/subroutines/3_left_recursion.md")]
#![doc = include_str!("../docs/subroutines/4_recursion.md")]
#![doc = include_str!("../docs/absent.md")]
#![deny(missing_docs)]
#![deny(missing_debug_implementations)]
#![cfg_attr(not(feature = "std"), no_std)]
extern crate alloc;
use alloc::borrow::Cow;
use alloc::boxed::Box;
use alloc::string::{String, ToString};
use alloc::sync::Arc;
use alloc::vec;
use alloc::vec::Vec;
use core::convert::TryFrom;
use core::fmt;
use core::fmt::{Debug, Formatter};
use core::ops::{Index, Range};
use core::str::FromStr;
use regex_automata::Anchored as RaAnchored;
use regex_automata::Input as RaInput;
use regex_automata::meta::Regex as RaRegex;
use regex_automata::util::captures::Captures as RaCaptures;
use regex_automata::util::primitives::NonMaxUsize;
use regex_automata::util::syntax::Config as SyntaxConfig;
mod analyze;
mod bytes;
mod compile;
mod error;
mod expand;
mod input;
#[cfg(all(feature = "native", target_os = "linux", target_arch = "x86_64"))]
mod native;
mod optimize;
mod parse;
mod parse_flags;
mod plan;
mod regexset;
mod regular;
mod regular_route;
mod replacer;
mod searcher;
mod seek;
mod start;
mod to_hir;
mod vm;
use crate::analyze::can_compile_as_anchored;
use crate::analyze::{AnalyzeContext, analyze};
use crate::compile::{CompileOptions, compile};
use crate::optimize::optimize;
use crate::parse::{ExprTree, NamedGroups, Parser};
use crate::parse_flags::*;
use crate::plan::{NFA_UNIT_BUDGET, Plan, PlanInput};
use crate::regular_route::{Automata, RegularRoute, RouteEngine};
use crate::start::StartFilter;
use crate::vm::{OPTION_FIND_NOT_EMPTY, OPTION_NOT_CONTINUED_FROM_PREVIOUS_MATCH, Prog};
pub use crate::bytes::MatchBytes;
pub use crate::error::{CompileError, Error, ParseError, Result, RuntimeError};
pub use crate::expand::Expander;
pub use crate::input::{Input, RegexInput};
pub use crate::regexset::{RegexSet, RegexSetMatch, RegexSetOptions};
pub use crate::regular::{RegularCaptureMatches, RegularMatches, RegularRegex};
pub use crate::replacer::{NoExpand, Replacer, ReplacerRef};
pub use crate::searcher::Searcher;
pub use crate::seek::seek_pattern_is_useful;
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub enum BytesMode {
#[default]
Unicode,
Ascii,
UnicodeBytes,
}
const MAX_RECURSION: usize = 64;
#[derive(Debug)]
pub struct RegexBuilder {
pattern: String,
options: RegexOptionsBuilder,
}
#[derive(Debug)]
pub struct RegexOptionsBuilder {
options: RegexOptions,
}
#[derive(Clone)]
pub struct Regex {
inner: RegexImpl,
named_groups: Arc<NamedGroups>,
#[cfg(all(feature = "native", target_os = "linux", target_arch = "x86_64"))]
native: Option<Arc<native::LazyNative>>,
}
#[derive(Clone)]
enum RegexImpl {
Wrap {
engine: WrapEngine,
pattern: String,
explicit_capture_group_0: bool,
delegated_pattern: String,
},
Fancy {
prog: Arc<Prog>,
n_groups: usize,
pattern: String,
flags: u32,
options: HardRegexRuntimeOptions,
regular: Option<Arc<RegularRoute>>,
},
}
#[derive(Clone)]
pub(crate) enum WrapEngine {
Meta(RaRegex),
Plan(Arc<Plan>),
}
impl WrapEngine {
pub(crate) fn new(
hir: Option<®ex_syntax::hir::Hir>,
options: &CompileOptions,
usage: compile::DelegateUsage,
build: impl FnOnce() -> Result<RaRegex>,
) -> Result<WrapEngine> {
let Some(plan) = hir.and_then(|hir| Plan::new(hir, usage.prefilter())) else {
return build().map(WrapEngine::Meta);
};
let default_limits =
options.delegate_size_limit.is_none() && options.delegate_dfa_size_limit.is_none();
if !default_limits || plan.nfa_units() > NFA_UNIT_BUDGET {
build()?;
}
Ok(WrapEngine::Plan(Arc::new(plan)))
}
fn captures_len(&self) -> usize {
match self {
WrapEngine::Meta(inner) => inner.captures_len(),
WrapEngine::Plan(plan) => plan.captures_len(),
}
}
fn create_captures(&self) -> RaCaptures {
match self {
WrapEngine::Meta(inner) => inner.create_captures(),
WrapEngine::Plan(plan) => plan.create_captures(),
}
}
}
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub struct Match<'t> {
text: &'t str,
start: usize,
end: usize,
}
#[derive(Debug)]
pub struct Matches<'r, 't, S: input::Input + ?Sized> {
re: &'r Regex,
state: IterState<'t, S>,
cache: Option<&'r mut searcher::Cache>,
}
impl<'r, 't, S: input::Input + ?Sized> Matches<'r, 't, S> {
fn new(
re: &'r Regex,
input: RegexInput<'t, S>,
cache: Option<&'r mut searcher::Cache>,
) -> Self {
Matches {
re,
state: IterState::new(input),
cache,
}
}
pub fn regex(&self) -> &'r Regex {
self.re
}
pub fn text(&self) -> &'t S {
self.state.input.haystack()
}
pub fn input(&self) -> &RegexInput<'t, S> {
&self.state.input
}
}
#[derive(Debug)]
struct IterState<'t, S: input::Input + ?Sized> {
input: RegexInput<'t, S>,
last_match: Option<usize>,
last_skipped_empty: bool,
}
impl<'t, S: input::Input + ?Sized> IterState<'t, S> {
fn new(input: RegexInput<'t, S>) -> Self {
IterState {
input,
last_match: None,
last_skipped_empty: false,
}
}
fn next_with<F, R, E>(&mut self, mut search: F) -> Option<core::result::Result<R, E>>
where
F: FnMut(&RegexInput<'t, S>, u32) -> core::result::Result<Option<(R, (usize, usize))>, E>,
{
if self.input.is_done() {
return None;
}
let option_flags = if self.last_skipped_empty {
OPTION_NOT_CONTINUED_FROM_PREVIOUS_MATCH
} else {
0
};
let pos = self.input.effective_start();
let (result, (match_start, match_end)) = match search(&self.input, option_flags) {
Err(error) => {
self.input
.set_start(self.input.get_range().end.saturating_add(1));
return Some(Err(error));
}
Ok(None) => return None,
Ok(Some(pair)) => pair,
};
if match_start == match_end {
self.input
.set_start(self.input.haystack().advance_position(match_end));
self.last_skipped_empty = match_end == pos;
if Some(match_end) == self.last_match {
return self.next_with(search);
}
} else {
self.input.set_start(match_end);
self.last_skipped_empty = false;
}
self.last_match = Some(match_end);
Some(Ok(result))
}
}
impl<'r, 't, S: input::Input + ?Sized> Iterator for Matches<'r, 't, S> {
type Item = Result<S::Match<'t>>;
fn next(&mut self) -> Option<Self::Item> {
let Matches { re, state, cache } = self;
let text = state.input.haystack();
state.next_with(|input, flags| {
re.find_input_raw_cached(input, flags, cache.as_deref_mut())
.map(|opt| opt.map(|(s, e)| (text.make_match(s, e), (s, e))))
})
}
}
#[derive(Debug)]
pub struct CaptureMatches<'r, 't, S: input::Input + ?Sized>(Matches<'r, 't, S>);
impl<'r, 't, S: input::Input + ?Sized> CaptureMatches<'r, 't, S> {
pub fn text(&self) -> &'t S {
self.0.text()
}
pub fn regex(&self) -> &'r Regex {
self.0.re
}
}
impl<'r, 't, S: input::Input + ?Sized> Iterator for CaptureMatches<'r, 't, S> {
type Item = Result<Captures<'t, S>>;
fn next(&mut self) -> Option<Self::Item> {
let Matches { re, state, cache } = &mut self.0;
state.next_with(|input, flags| {
let captures = re.captures_input_cached(input, flags, cache.as_deref_mut())?;
Ok(captures.map(|c| {
let (start, end) = c
.inner
.get_span(0)
.expect("`Captures` is expected to have entire match at 0th position");
(c, (start, end))
}))
})
}
}
#[derive(Debug)]
pub struct Captures<'t, S: input::Input + ?Sized = str> {
inner: CapturesImpl,
named_groups: Arc<NamedGroups>,
input: &'t S,
}
#[derive(Clone, Debug)]
enum CapturesImpl {
Wrap {
locations: RaCaptures,
explicit_capture_group_0: bool,
},
Fancy {
saves: Vec<usize>,
},
}
impl CapturesImpl {
fn get_span(&self, i: usize) -> Option<(usize, usize)> {
match self {
CapturesImpl::Wrap {
locations,
explicit_capture_group_0,
} => locations
.get_group(i + if *explicit_capture_group_0 { 1 } else { 0 })
.map(|span| (span.start, span.end)),
CapturesImpl::Fancy { saves } => {
let slot = i * 2;
if slot >= saves.len() {
return None;
}
let lo = saves[slot];
if lo == usize::MAX {
return None;
}
let hi = saves[slot + 1];
Some((lo, hi))
}
}
}
fn len(&self) -> usize {
match self {
CapturesImpl::Wrap {
locations,
explicit_capture_group_0,
} => locations.group_len() - if *explicit_capture_group_0 { 1 } else { 0 },
CapturesImpl::Fancy { saves } => saves.len() / 2,
}
}
}
#[derive(Debug)]
pub struct SubCaptureMatches<'c, 't, S: input::Input + ?Sized> {
data: &'c Captures<'t, S>,
i: usize,
}
#[derive(Clone, Debug)]
pub struct CaptureLocations {
slots: CapturesImpl,
groups: usize,
named_groups: Arc<NamedGroups>,
}
#[allow(clippy::len_without_is_empty)] impl CaptureLocations {
pub fn get(&self, i: usize) -> Option<(usize, usize)> {
if i < self.groups {
self.slots.get_span(i)
} else {
None
}
}
pub fn name(&self, name: &str) -> Option<(usize, usize)> {
self.named_groups.get(name).and_then(|&i| self.get(i))
}
pub fn len(&self) -> usize {
self.groups
}
fn clear(&mut self) {
match &mut self.slots {
CapturesImpl::Wrap { locations, .. } => locations.set_pattern(None),
CapturesImpl::Fancy { saves } => saves.clear(),
}
}
}
#[derive(Debug)]
pub struct Split<'r, 'h> {
matches: Matches<'r, 'h, str>,
next_start: usize,
target: &'h str,
}
impl<'r, 'h> Iterator for Split<'r, 'h> {
type Item = Result<&'h str>;
fn next(&mut self) -> Option<Result<&'h str>> {
match self.matches.next() {
None => {
let len = self.target.len();
if self.next_start > len {
None
} else {
let part = &self.target[self.next_start..len];
self.next_start = len + 1;
Some(Ok(part))
}
}
Some(Ok(m)) => {
let part = &self.target[self.next_start..m.start()];
self.next_start = m.end();
Some(Ok(part))
}
Some(Err(e)) => Some(Err(e)),
}
}
}
impl<'r, 'h> core::iter::FusedIterator for Split<'r, 'h> {}
#[derive(Debug)]
pub struct SplitN<'r, 'h> {
splits: Split<'r, 'h>,
limit: usize,
}
impl<'r, 'h> Iterator for SplitN<'r, 'h> {
type Item = Result<&'h str>;
fn next(&mut self) -> Option<Result<&'h str>> {
if self.limit == 0 {
return None;
}
self.limit -= 1;
if self.limit > 0 {
return self.splits.next();
}
let len = self.splits.target.len();
if self.splits.next_start > len {
None
} else {
let start = self.splits.next_start;
self.splits.next_start = len + 1;
Some(Ok(&self.splits.target[start..len]))
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(0, Some(self.limit))
}
}
impl<'r, 'h> core::iter::FusedIterator for SplitN<'r, 'h> {}
#[derive(Clone)]
struct RegexOptions {
syntaxc: SyntaxConfig,
delegate_size_limit: Option<usize>,
delegate_dfa_size_limit: Option<usize>,
oniguruma_mode: bool,
ignore_numbered_groups_when_named_groups_exist: bool,
hard_regex_runtime_options: HardRegexRuntimeOptions,
bytes_mode: BytesMode,
seek_filter: Option<fn(&str) -> bool>,
delegate_prefilter: bool,
#[cfg(feature = "native")]
native_enabled: bool,
explicit_backtrack_limit: bool,
}
impl fmt::Debug for RegexOptions {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let seek_filter_desc = match self.seek_filter {
None => "None",
Some(f_ptr) if (f_ptr as *const ()) == (seek_pattern_is_useful as *const ()) => {
"Some(seek_pattern_is_useful)"
}
Some(_) => "Some(<custom>)",
};
f.debug_struct("RegexOptions")
.field("syntaxc", &self.syntaxc)
.field("delegate_size_limit", &self.delegate_size_limit)
.field("delegate_dfa_size_limit", &self.delegate_dfa_size_limit)
.field("oniguruma_mode", &self.oniguruma_mode)
.field(
"ignore_numbered_groups_when_named_groups_exist",
&self.ignore_numbered_groups_when_named_groups_exist,
)
.field(
"hard_regex_runtime_options",
&self.hard_regex_runtime_options,
)
.field("seek_filter", &seek_filter_desc)
.field("delegate_prefilter", &self.delegate_prefilter)
.finish()
}
}
impl Default for RegexOptions {
fn default() -> Self {
RegexOptions {
syntaxc: SyntaxConfig::new().unicode(true),
delegate_size_limit: None,
delegate_dfa_size_limit: None,
oniguruma_mode: false,
ignore_numbered_groups_when_named_groups_exist: false,
hard_regex_runtime_options: HardRegexRuntimeOptions::default(),
bytes_mode: BytesMode::default(),
seek_filter: None, delegate_prefilter: true,
#[cfg(feature = "native")]
native_enabled: true,
explicit_backtrack_limit: false,
}
}
}
#[derive(Copy, Clone, Debug)]
struct HardRegexRuntimeOptions {
backtrack_limit: usize,
find_not_empty: bool,
disallow_empty_match_at_eof_after_newline: bool,
allow_input_assertion_overrides: bool,
}
impl RegexOptions {
fn get_flag_value(flag_value: bool, enum_value: u32) -> u32 {
if flag_value { enum_value } else { 0 }
}
fn compute_flags(&self) -> u32 {
let insensitive = Self::get_flag_value(self.syntaxc.get_case_insensitive(), FLAG_CASEI);
let multiline = Self::get_flag_value(self.syntaxc.get_multi_line(), FLAG_MULTI);
let whitespace =
Self::get_flag_value(self.syntaxc.get_ignore_whitespace(), FLAG_IGNORE_SPACE);
let dotnl = Self::get_flag_value(self.syntaxc.get_dot_matches_new_line(), FLAG_DOTNL);
let unicode = Self::get_flag_value(
self.syntaxc.get_unicode() && !matches!(self.bytes_mode, BytesMode::Ascii),
FLAG_UNICODE,
);
let oniguruma_mode = Self::get_flag_value(self.oniguruma_mode, FLAG_ONIGURUMA_MODE);
let crlf = Self::get_flag_value(self.syntaxc.get_crlf(), FLAG_CRLF);
let named_groups_only = Self::get_flag_value(
self.ignore_numbered_groups_when_named_groups_exist,
FLAG_IGNORE_NUMBERED_GROUPS_WHEN_NAMED_GROUPS_EXIST,
);
insensitive
| multiline
| whitespace
| dotnl
| unicode
| oniguruma_mode
| crlf
| named_groups_only
}
}
impl Default for HardRegexRuntimeOptions {
fn default() -> Self {
HardRegexRuntimeOptions {
backtrack_limit: 1_000_000,
find_not_empty: false,
disallow_empty_match_at_eof_after_newline: false,
allow_input_assertion_overrides: false,
}
}
}
impl Default for RegexOptionsBuilder {
fn default() -> Self {
Self::new()
}
}
impl RegexOptionsBuilder {
pub fn native(&mut self, enabled: bool) -> &mut Self {
#[cfg(feature = "native")]
{
self.options.native_enabled = enabled;
}
#[cfg(not(feature = "native"))]
let _ = enabled;
self
}
pub fn new() -> Self {
RegexOptionsBuilder {
options: RegexOptions::default(),
}
}
pub fn build(&self, pattern: String) -> Result<Regex> {
Regex::new_options(pattern, &self.options)
}
pub fn build_regular(&self, pattern: String) -> Result<RegularRegex> {
RegularRegex::new_options(pattern, &self.options)
}
fn set_config(&mut self, func: impl Fn(SyntaxConfig) -> SyntaxConfig) -> &mut Self {
self.options.syntaxc = func(self.options.syntaxc);
self
}
pub fn case_insensitive(&mut self, yes: bool) -> &mut Self {
self.set_config(|x| x.case_insensitive(yes))
}
pub fn multi_line(&mut self, yes: bool) -> &mut Self {
self.set_config(|x| x.multi_line(yes))
}
pub fn ignore_whitespace(&mut self, yes: bool) -> &mut Self {
self.set_config(|x| x.ignore_whitespace(yes))
}
pub fn dot_matches_new_line(&mut self, yes: bool) -> &mut Self {
self.set_config(|x| x.dot_matches_new_line(yes))
}
pub fn crlf(&mut self, yes: bool) -> &mut Self {
self.set_config(|x| x.crlf(yes))
}
pub fn verbose_mode(&mut self, yes: bool) -> &mut Self {
self.set_config(|x| x.ignore_whitespace(yes))
}
pub fn unicode_mode(&mut self, yes: bool) -> &mut Self {
self.set_config(|x| x.unicode(yes))
}
pub fn backtrack_limit(&mut self, limit: usize) -> &mut Self {
self.options.hard_regex_runtime_options.backtrack_limit = limit;
self.options.explicit_backtrack_limit = true;
self
}
pub fn delegate_size_limit(&mut self, limit: usize) -> &mut Self {
self.options.delegate_size_limit = Some(limit);
self
}
pub fn delegate_dfa_size_limit(&mut self, limit: usize) -> &mut Self {
self.options.delegate_dfa_size_limit = Some(limit);
self
}
pub fn find_not_empty(&mut self, yes: bool) -> &mut Self {
self.options.hard_regex_runtime_options.find_not_empty = yes;
self
}
pub fn ignore_numbered_groups_when_named_groups_exist(&mut self, yes: bool) -> &mut Self {
self.options.ignore_numbered_groups_when_named_groups_exist = yes;
self
}
pub fn seek(&mut self, yes: bool) -> &mut Self {
self.options.seek_filter = if yes {
Some(seek_pattern_is_useful)
} else {
None
};
self
}
pub fn seek_filter(&mut self, filter: fn(&str) -> bool) -> &mut Self {
self.options.seek_filter = Some(filter);
self
}
pub fn oniguruma_mode(&mut self, yes: bool) -> &mut Self {
self.options.oniguruma_mode = yes;
self
}
pub fn bytes_mode(&mut self, mode: BytesMode) -> &mut Self {
self.options.bytes_mode = mode;
self
}
pub fn disallow_empty_match_at_eof_after_newline(&mut self, yes: bool) -> &mut Self {
self.options
.hard_regex_runtime_options
.disallow_empty_match_at_eof_after_newline = yes;
self
}
pub fn allow_input_assertion_overrides(&mut self, yes: bool) -> &mut Self {
self.options
.hard_regex_runtime_options
.allow_input_assertion_overrides = yes;
self
}
}
impl RegexBuilder {
pub fn native(&mut self, enabled: bool) -> &mut Self {
self.options.native(enabled);
self
}
pub fn new(pattern: &str) -> Self {
RegexBuilder {
pattern: pattern.to_string(),
options: RegexOptionsBuilder::new(),
}
}
pub fn build(&self) -> Result<Regex> {
self.options.build(self.pattern.clone())
}
pub fn build_regular(&self) -> Result<RegularRegex> {
self.options.build_regular(self.pattern.clone())
}
pub fn pattern(&mut self, pattern: String) -> &mut Self {
self.pattern = pattern;
self
}
pub fn case_insensitive(&mut self, yes: bool) -> &mut Self {
self.options.case_insensitive(yes);
self
}
pub fn multi_line(&mut self, yes: bool) -> &mut Self {
self.options.multi_line(yes);
self
}
pub fn ignore_whitespace(&mut self, yes: bool) -> &mut Self {
self.options.ignore_whitespace(yes);
self
}
pub fn dot_matches_new_line(&mut self, yes: bool) -> &mut Self {
self.options.dot_matches_new_line(yes);
self
}
pub fn verbose_mode(&mut self, yes: bool) -> &mut Self {
self.options.ignore_whitespace(yes);
self
}
pub fn unicode_mode(&mut self, yes: bool) -> &mut Self {
self.options.unicode_mode(yes);
self
}
pub fn backtrack_limit(&mut self, limit: usize) -> &mut Self {
self.options.backtrack_limit(limit);
self
}
pub fn delegate_size_limit(&mut self, limit: usize) -> &mut Self {
self.options.delegate_size_limit(limit);
self
}
pub fn delegate_dfa_size_limit(&mut self, limit: usize) -> &mut Self {
self.options.delegate_dfa_size_limit(limit);
self
}
pub fn oniguruma_mode(&mut self, yes: bool) -> &mut Self {
self.options.oniguruma_mode(yes);
self
}
pub fn bytes_mode(&mut self, mode: BytesMode) -> &mut Self {
self.options.bytes_mode(mode);
self
}
pub fn crlf(&mut self, yes: bool) -> &mut Self {
self.options.crlf(yes);
self
}
pub fn find_not_empty(&mut self, yes: bool) -> &mut Self {
self.options.find_not_empty(yes);
self
}
pub fn ignore_numbered_groups_when_named_groups_exist(&mut self, yes: bool) -> &mut Self {
self.options
.ignore_numbered_groups_when_named_groups_exist(yes);
self
}
pub fn seek(&mut self, yes: bool) -> &mut Self {
self.options.seek(yes);
self
}
pub fn seek_filter(&mut self, filter: fn(&str) -> bool) -> &mut Self {
self.options.seek_filter(filter);
self
}
pub fn disallow_empty_match_at_eof_after_newline(&mut self, yes: bool) -> &mut Self {
self.options.disallow_empty_match_at_eof_after_newline(yes);
self
}
pub fn allow_input_assertion_overrides(&mut self, yes: bool) -> &mut Self {
self.options.allow_input_assertion_overrides(yes);
self
}
}
impl fmt::Debug for Regex {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.as_str())
}
}
impl fmt::Display for Regex {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.as_str())
}
}
impl FromStr for Regex {
type Err = Error;
fn from_str(s: &str) -> Result<Regex> {
Regex::new(s)
}
}
impl Regex {
pub fn searcher(&self) -> Searcher<'_> {
Searcher::new(self)
}
pub fn new(re: &str) -> Result<Regex> {
Self::new_options(re.to_string(), &RegexOptions::default())
}
pub(crate) fn new_options(pattern: String, options: &RegexOptions) -> Result<Regex> {
let flags = options.compute_flags();
let mut tree = Expr::parse_tree_with_flags(&pattern, flags)?;
let edged = edge_lookarounds(&tree.expr).then(|| tree.expr.clone());
#[cfg(all(feature = "native", target_os = "linux", target_arch = "x86_64"))]
let native_pattern = if options.native_enabled
&& options.delegate_prefilter
&& !options.explicit_backtrack_limit
&& options.syntaxc.get_unicode()
&& matches!(options.bytes_mode, BytesMode::Unicode)
&& !options.oniguruma_mode
&& !options.ignore_numbered_groups_when_named_groups_exist
&& !options.hard_regex_runtime_options.find_not_empty
&& !options
.hard_regex_runtime_options
.allow_input_assertion_overrides
&& !options
.hard_regex_runtime_options
.disallow_empty_match_at_eof_after_newline
&& pattern.len() <= 4096
{
native::Pattern::from_expr(&tree.expr).filter(|pattern| pattern.rich)
} else {
None
};
let runtime = &options.hard_regex_runtime_options;
let find_not_empty = runtime.find_not_empty;
let disallow_empty_match_at_eof_after_newline =
runtime.disallow_empty_match_at_eof_after_newline;
let (requires_capture_group_fixup, context) = prepare_tree(&mut tree, runtime);
let info = analyze(&tree, context)?;
if find_not_empty && info.const_size && info.min_size == 0 {
return Err(CompileError::PatternCanNeverMatch.into());
}
if !info.hard {
let mut re_cooked = String::with_capacity(pattern.len() + pattern.len() / 2);
tree.expr.to_str(&mut re_cooked, 0);
let compile_options = CompileOptions {
bytes_mode: options.bytes_mode,
unicode: options.syntaxc.get_unicode()
&& !matches!(options.bytes_mode, BytesMode::Ascii),
delegate_size_limit: options.delegate_size_limit,
delegate_dfa_size_limit: options.delegate_dfa_size_limit,
..CompileOptions::default()
};
let usage = if options.delegate_prefilter {
compile::DelegateUsage::unanchored()
} else {
compile::DelegateUsage::unanchored_no_prefilter()
};
let utf8 = matches!(compile_options.bytes_mode, BytesMode::Unicode);
let mut hir_ctx = to_hir::HirCtx::new(compile_options.unicode, utf8);
let hir = to_hir::expr_to_hir(&tree.expr, &mut hir_ctx);
let planned = hir.as_ref().filter(|hir| {
!requires_capture_group_fixup
|| 2 * (hir.properties().explicit_captures_len() + 1) <= FIXUP_SLOTS
});
let engine = WrapEngine::new(planned, &compile_options, usage, || match &hir {
Some(hir) => compile::compile_inner_from_hir(hir, &compile_options, usage),
None => compile::compile_inner(&re_cooked, &compile_options, usage),
})?;
return Ok(Regex {
inner: RegexImpl::Wrap {
engine,
pattern,
explicit_capture_group_0: requires_capture_group_fixup,
delegated_pattern: re_cooked,
},
named_groups: Arc::new(tree.named_groups),
#[cfg(all(feature = "native", target_os = "linux", target_arch = "x86_64"))]
native: None,
});
}
let prog = compile(
&info,
CompileOptions {
anchored: can_compile_as_anchored(&tree.expr),
contains_subroutines: tree.contains_subroutines,
seek_filter: options.seek_filter,
disallow_empty_match_at_eof_after_newline,
bytes_mode: options.bytes_mode,
unicode: options.syntaxc.get_unicode()
&& !matches!(options.bytes_mode, BytesMode::Ascii),
delegate_size_limit: options.delegate_size_limit,
delegate_dfa_size_limit: options.delegate_dfa_size_limit,
explicit_backtrack_limit: options.explicit_backtrack_limit,
},
)?;
let n_groups = info.end_group();
let regular = if options.explicit_backtrack_limit || prog.repeats_empty_matches() {
None
} else if requires_capture_group_fixup {
edged
.as_ref()
.and_then(|expr| assertion_route(expr, &prog, options, n_groups))
.map(Arc::new)
} else {
word_boundary_automata(&tree.expr, options, n_groups)
.or_else(|| {
let expr = edged.as_ref()?;
assertion_route(expr, &prog, options, n_groups)
})
.map(Arc::new)
};
Ok(Regex {
#[cfg(all(feature = "native", target_os = "linux", target_arch = "x86_64"))]
native: native_pattern.map(|pattern| Arc::new(native::LazyNative::new(pattern))),
inner: RegexImpl::Fancy {
prog: Arc::new(prog),
n_groups,
options: options.hard_regex_runtime_options,
pattern,
flags,
regular,
},
named_groups: Arc::new(tree.named_groups),
})
}
pub fn as_str(&self) -> &str {
match &self.inner {
RegexImpl::Wrap { pattern, .. } => pattern,
RegexImpl::Fancy { pattern, .. } => pattern,
}
}
pub fn is_match<S: input::Input + ?Sized>(&self, input: &S) -> Result<bool> {
match &self.inner {
RegexImpl::Wrap { .. } => self.is_match_input(RegexInput::new(input)),
RegexImpl::Fancy { .. } => self.fancy_is_match(&RegexInput::new(input), true, None),
}
}
pub(crate) fn native_match<S: input::Input + ?Sized>(&self, input: &S) -> Option<bool> {
#[cfg(all(feature = "native", target_os = "linux", target_arch = "x86_64"))]
{
let text = input.as_utf8()?;
self.native.as_ref()?.get()?.is_match(text)
}
#[cfg(not(all(feature = "native", target_os = "linux", target_arch = "x86_64")))]
{
let _ = input;
None
}
}
pub fn has_native_code(&self) -> bool {
self.native_code_bytes() != 0
}
pub fn native_code_bytes(&self) -> usize {
#[cfg(all(feature = "native", target_os = "linux", target_arch = "x86_64"))]
{
self.native
.as_ref()
.and_then(|native| native.get())
.map_or(0, native::NativeRegex::code_bytes)
}
#[cfg(not(all(feature = "native", target_os = "linux", target_arch = "x86_64")))]
{
0
}
}
pub fn is_match_input<S: input::Input + ?Sized>(
&self,
input: RegexInput<'_, S>,
) -> Result<bool> {
match &self.inner {
RegexImpl::Wrap { engine, .. } => Ok(!input.is_done()
&& match engine {
WrapEngine::Plan(plan) => plan_is_match(plan, &input),
WrapEngine::Meta(inner) => inner.is_match(ra_input(&input)),
}),
RegexImpl::Fancy { .. } => self.fancy_is_match(&input, false, None),
}
}
pub(crate) fn fancy_is_match<S: input::Input + ?Sized>(
&self,
input: &RegexInput<'_, S>,
whole_text: bool,
mut cache: Option<&mut searcher::Cache>,
) -> Result<bool> {
if input.is_done() {
return Ok(false);
}
if let Some(route) = self.regular_route(input) {
if let Some(found) = route
.plan()
.and_then(|plan| plan.is_match(&plan_input(input)))
{
return Ok(found);
}
if let Some(automata) = route.automata()
&& let Ok(found) = automata.is_match(
&ra_input(input),
cache.as_deref_mut().and_then(|cache| cache.route(automata)),
)
{
return Ok(found);
}
}
if whole_text && let Some(found) = self.native_match(input.haystack()) {
return Ok(found);
}
Ok(self.find_on_vm(input, 0, cache)?.is_some())
}
pub(crate) fn regular_route<S: input::Input + ?Sized>(
&self,
input: &RegexInput<'_, S>,
) -> Option<&RouteEngine> {
let RegexImpl::Fancy {
regular: Some(route),
..
} = &self.inner
else {
return None;
};
let haystack = input.haystack();
let eligible = input.get_range().end == haystack.len()
&& (route.ascii
|| haystack
.as_utf8()
.is_some_and(|text| text.is_char_boundary(input.effective_start())));
eligible.then(|| route.engine())
}
pub fn find_iter<'r, 't, S: input::Input + ?Sized>(
&'r self,
text: &'t S,
) -> Matches<'r, 't, S> {
self.find_iter_input(RegexInput::new(text))
}
pub fn find_iter_input<'r, 't, S: input::Input + ?Sized>(
&'r self,
input: RegexInput<'t, S>,
) -> Matches<'r, 't, S> {
Matches::new(self, input, None)
}
pub fn find<'t, S: input::Input + ?Sized>(&self, input: &'t S) -> Result<Option<S::Match<'t>>> {
self.find_input(RegexInput::new(input))
}
pub fn find_input<'t, S: input::Input + ?Sized>(
&self,
input: RegexInput<'t, S>,
) -> Result<Option<S::Match<'t>>> {
Ok(self
.find_input_raw(&input, 0)?
.map(|(s, e)| input.haystack().make_match(s, e)))
}
pub fn find_from_pos<'t, S: input::Input + ?Sized>(
&self,
input: &'t S,
pos: usize,
) -> Result<Option<S::Match<'t>>> {
self.find_input(RegexInput::new(input).from_pos(pos))
}
pub(crate) fn find_input_raw<S: input::Input + ?Sized>(
&self,
input: &RegexInput<'_, S>,
option_flags: u32,
) -> Result<Option<(usize, usize)>> {
self.find_input_raw_cached(input, option_flags, None)
}
pub(crate) fn find_input_raw_cached<S: input::Input + ?Sized>(
&self,
input: &RegexInput<'_, S>,
option_flags: u32,
mut cache: Option<&mut searcher::Cache>,
) -> Result<Option<(usize, usize)>> {
if input.is_done() {
return Ok(None);
}
if let Some(route) = self.regular_route(input) {
if let Some(found) = route
.plan()
.and_then(|plan| plan.find::<[usize]>(&plan_input(input), None))
{
return Ok(found);
}
if let Some(automata) = route.automata()
&& let Ok(found) = automata.find(
&ra_input(input),
cache.as_deref_mut().and_then(|cache| cache.route(automata)),
)
{
return Ok(found);
}
}
self.find_on_vm(input, option_flags, cache)
}
pub(crate) fn find_on_vm<S: input::Input + ?Sized>(
&self,
input: &RegexInput<'_, S>,
option_flags: u32,
mut cache: Option<&mut searcher::Cache>,
) -> Result<Option<(usize, usize)>> {
match &self.inner {
RegexImpl::Wrap {
engine: WrapEngine::Plan(plan),
explicit_capture_group_0,
..
} => {
if !*explicit_capture_group_0 {
return Ok(plan_find(plan, input, None));
}
Ok(plan_find_rewritten(plan, input))
}
RegexImpl::Wrap {
engine: WrapEngine::Meta(inner),
explicit_capture_group_0,
..
} => {
let delegated_input = ra_input(input);
let result = if !*explicit_capture_group_0 {
regular_find(
inner,
&delegated_input,
cache.and_then(searcher::Cache::regular),
)
} else {
let mut slots = [None; 4];
let result = match cache.and_then(searcher::Cache::regular) {
Some((cache, _)) => {
inner.search_slots_with(cache, &delegated_input, &mut slots)
}
None => inner.search_slots(&delegated_input, &mut slots),
};
if result.is_some() {
slots[2]
.zip(slots[3])
.map(|(start, end)| (start.get(), end.get()))
} else {
None
}
};
Ok(result)
}
RegexImpl::Fancy { prog, options, .. } => {
let option_flags = option_flags
| if options.find_not_empty {
OPTION_FIND_NOT_EMPTY
} else {
0
};
let found = match cache.as_deref_mut().and_then(searcher::Cache::rich) {
Some(scratch) => {
vm::run_spans_cached(prog, input, option_flags, options, scratch)
}
None => vm::run_spans(prog, input, option_flags, options),
};
match found {
Err(error) => match limit_recovery(
self.regular_route(input).and_then(RouteEngine::automata),
&error,
) {
Some((route, regex)) => Ok(regular_find(
regex,
&ra_input(input),
cache.and_then(|cache| cache.route_meta(route)),
)),
None => Err(error),
},
found => found,
}
}
}
}
pub(crate) fn captures_for_span<'t, S: input::Input + ?Sized>(
&self,
input: &'t S,
start: usize,
end: usize,
) -> Captures<'t, S> {
Captures {
inner: CapturesImpl::Fancy {
saves: vec![start, end],
},
named_groups: self.named_groups.clone(),
input,
}
}
pub fn captures_iter<'r, 't, S: input::Input + ?Sized>(
&'r self,
text: &'t S,
) -> CaptureMatches<'r, 't, S> {
self.captures_iter_input(RegexInput::new(text))
}
pub fn captures_iter_input<'r, 't, S: input::Input + ?Sized>(
&'r self,
input: RegexInput<'t, S>,
) -> CaptureMatches<'r, 't, S> {
CaptureMatches(self.find_iter_input(input))
}
pub fn captures<'t, S: input::Input + ?Sized>(
&self,
text: &'t S,
) -> Result<Option<Captures<'t, S>>> {
self.captures_input(RegexInput::new(text))
}
pub fn captures_input<'t, S: input::Input + ?Sized>(
&self,
input: RegexInput<'t, S>,
) -> Result<Option<Captures<'t, S>>> {
self.captures_input_with_option_flags(&input, 0)
}
pub fn captures_from_pos<'t, S: input::Input + ?Sized>(
&self,
text: &'t S,
pos: usize,
) -> Result<Option<Captures<'t, S>>> {
self.captures_input(RegexInput::new(text).from_pos(pos))
}
pub(crate) fn captures_input_with_option_flags<'t, S: input::Input + ?Sized>(
&self,
input: &RegexInput<'t, S>,
option_flags: u32,
) -> Result<Option<Captures<'t, S>>> {
self.captures_input_cached(input, option_flags, None)
}
pub(crate) fn captures_input_cached<'t, S: input::Input + ?Sized>(
&self,
input: &RegexInput<'t, S>,
option_flags: u32,
mut cache: Option<&mut searcher::Cache>,
) -> Result<Option<Captures<'t, S>>> {
if input.is_done() {
return Ok(None);
}
let named_groups = self.named_groups.clone();
let haystack = input.haystack();
let route = self.regular_route(input);
let routed = |locations: Option<RaCaptures>| {
locations.map(|locations| Captures {
inner: CapturesImpl::Wrap {
locations,
explicit_capture_group_0: false,
},
named_groups: named_groups.clone(),
input: haystack,
})
};
if let Some(locations) = route
.and_then(RouteEngine::plan)
.and_then(|plan| plan.captures(&plan_input(input)))
{
return Ok(routed(locations));
}
let route = route.and_then(RouteEngine::automata);
if let Some(route) = route
&& let Some(regex) = route.regex()
&& let Ok(found) = route.find(
&ra_input(input),
cache.as_deref_mut().and_then(|cache| cache.route(route)),
)
{
let locations = found.and_then(|(start, end)| {
let span = ra_input(input).span(start..end).anchored(RaAnchored::Yes);
regular_captures(
regex,
&span,
cache.and_then(|cache| cache.route_meta(route)),
)
});
return Ok(routed(locations));
}
match &self.inner {
RegexImpl::Wrap {
engine: WrapEngine::Plan(plan),
explicit_capture_group_0,
..
} => {
let mut locations = plan.create_captures();
plan_captures_into(plan, input, &mut locations);
Ok(locations.is_match().then_some(Captures {
inner: CapturesImpl::Wrap {
locations,
explicit_capture_group_0: *explicit_capture_group_0,
},
named_groups,
input: haystack,
}))
}
RegexImpl::Wrap {
engine: WrapEngine::Meta(inner),
explicit_capture_group_0,
..
} => {
let explicit = *explicit_capture_group_0;
let locations = regular_captures(
inner,
&ra_input(input),
cache.and_then(searcher::Cache::regular),
);
Ok(locations.map(|locations| Captures {
inner: CapturesImpl::Wrap {
locations,
explicit_capture_group_0: explicit,
},
named_groups,
input: haystack,
}))
}
RegexImpl::Fancy {
prog,
n_groups,
options,
..
} => {
let option_flags = option_flags
| if options.find_not_empty {
OPTION_FIND_NOT_EMPTY
} else {
0
};
let result = match cache.as_deref_mut().and_then(searcher::Cache::rich) {
Some(scratch) => vm::run_cached(prog, input, option_flags, options, scratch),
None => vm::run(prog, input, option_flags, options),
};
let result = match result {
Err(error) => match limit_recovery(route, &error) {
Some((route, regex)) => {
let meta = cache.and_then(|cache| cache.route_meta(route));
return Ok(routed(regular_captures(regex, &ra_input(input), meta)));
}
None => return Err(error),
},
Ok(result) => result,
};
Ok(result.map(|mut saves| {
saves.truncate(n_groups * 2);
Captures {
inner: CapturesImpl::Fancy { saves },
named_groups,
input: haystack,
}
}))
}
}
}
pub(crate) fn seek_pattern(&self) -> Result<Cow<'_, str>> {
match &self.inner {
RegexImpl::Wrap {
delegated_pattern, ..
} => Ok(Cow::Borrowed(delegated_pattern)),
RegexImpl::Fancy {
prog,
pattern,
flags,
options,
..
} => match prog.seek_pattern() {
Some(seek_pattern) => Ok(Cow::Borrowed(seek_pattern)),
None => {
let mut tree = Expr::parse_tree_with_flags(pattern, *flags)?;
let (_, context) = prepare_tree(&mut tree, options);
let info = analyze(&tree, context)?;
Ok(Cow::Owned(compile::seek_pattern_of(&info)))
}
},
}
}
pub fn captures_len(&self) -> usize {
match &self.inner {
RegexImpl::Wrap {
engine,
explicit_capture_group_0,
..
} => engine.captures_len() - if *explicit_capture_group_0 { 1 } else { 0 },
RegexImpl::Fancy { n_groups, .. } => *n_groups,
}
}
pub fn capture_locations(&self) -> CaptureLocations {
let slots = match &self.inner {
RegexImpl::Wrap {
engine,
explicit_capture_group_0,
..
} => CapturesImpl::Wrap {
locations: engine.create_captures(),
explicit_capture_group_0: *explicit_capture_group_0,
},
RegexImpl::Fancy { n_groups, .. } => CapturesImpl::Fancy {
saves: Vec::with_capacity(n_groups * 2),
},
};
CaptureLocations {
slots,
groups: self.captures_len(),
named_groups: Arc::clone(&self.named_groups),
}
}
pub(crate) fn captures_read_cached<S: input::Input + ?Sized>(
&self,
input: &RegexInput<'_, S>,
locations: &mut CaptureLocations,
cache: Option<&mut searcher::Cache>,
) -> Result<bool> {
if !Arc::ptr_eq(&locations.named_groups, &self.named_groups) {
*locations = self.capture_locations();
}
if input.is_done() {
locations.clear();
return Ok(false);
}
self.captures_into(input, 0, &mut locations.slots, cache)
}
fn captures_into<S: input::Input + ?Sized>(
&self,
input: &RegexInput<'_, S>,
option_flags: u32,
slots: &mut CapturesImpl,
mut cache: Option<&mut searcher::Cache>,
) -> Result<bool> {
let route = self.regular_route(input);
if let (Some(plan), CapturesImpl::Fancy { saves }) =
(route.and_then(RouteEngine::plan), &mut *slots)
{
saves.clear();
saves.resize(plan.slot_len(), usize::MAX);
match plan.find(&plan_input(input), Some(&mut saves[..])) {
Some(Some(_)) => return Ok(true),
Some(None) => {
saves.clear();
return Ok(false);
}
None => {}
}
}
let route = route.and_then(RouteEngine::automata);
if let (Some(route), CapturesImpl::Fancy { saves }) = (route, &mut *slots)
&& let Some(regex) = route.regex()
&& let Ok(found) = route.find(
&ra_input(input),
cache.as_deref_mut().and_then(|cache| cache.route(route)),
)
{
let Some((start, end)) = found else {
saves.clear();
return Ok(false);
};
let span = ra_input(input).span(start..end).anchored(RaAnchored::Yes);
let meta = cache.and_then(|cache| cache.route_meta(route));
return Ok(regular_captures_into(regex, &span, meta, saves));
}
match (&self.inner, slots) {
(
RegexImpl::Wrap {
engine: WrapEngine::Plan(plan),
..
},
CapturesImpl::Wrap { locations, .. },
) => {
plan_captures_into(plan, input, locations);
Ok(locations.is_match())
}
(
RegexImpl::Wrap {
engine: WrapEngine::Meta(inner),
..
},
CapturesImpl::Wrap { locations, .. },
) => {
let delegated_input = ra_input(input);
match cache.and_then(searcher::Cache::regular) {
Some((cache, _)) => {
inner.search_captures_with(cache, &delegated_input, locations)
}
None => inner.search_captures(&delegated_input, locations),
}
Ok(locations.is_match())
}
(
RegexImpl::Fancy {
prog,
n_groups,
options,
..
},
CapturesImpl::Fancy { saves },
) => {
let option_flags = option_flags
| if options.find_not_empty {
OPTION_FIND_NOT_EMPTY
} else {
0
};
let scratch = cache.as_deref_mut().and_then(searcher::Cache::rich);
let found = vm::run_into(
prog,
input,
option_flags,
options,
scratch,
(n_groups * 2, saves),
);
match found {
Err(error) => match limit_recovery(route, &error) {
Some((route, regex)) => {
let meta = cache.and_then(|cache| cache.route_meta(route));
Ok(regular_captures_into(regex, &ra_input(input), meta, saves))
}
None => Err(error),
},
found => found,
}
}
_ => unreachable!("capture locations belong to this regex"),
}
}
pub fn capture_names(&self) -> CaptureNames<'_> {
capture_names_of(&self.named_groups, self.captures_len())
}
#[doc(hidden)]
pub fn planned(&self) -> bool {
match &self.inner {
RegexImpl::Wrap { engine, .. } => matches!(engine, WrapEngine::Plan(_)),
RegexImpl::Fancy {
regular: Some(route),
..
} => route.engine().plan().is_some(),
RegexImpl::Fancy { .. } => false,
}
}
#[doc(hidden)]
pub fn debug_print(&self, writer: &mut Formatter<'_>) -> fmt::Result {
match &self.inner {
RegexImpl::Wrap {
delegated_pattern,
explicit_capture_group_0,
..
} => {
write!(
writer,
"wrapped Regex {:?}, explicit_capture_group_0: {:}",
delegated_pattern, *explicit_capture_group_0
)
}
RegexImpl::Fancy { prog, .. } => prog.debug_print(writer),
}
}
pub fn replace<'t, R: Replacer>(&self, text: &'t str, rep: R) -> Cow<'t, str> {
self.replacen(text, 1, rep)
}
pub fn try_replace<'t, R: Replacer>(&self, text: &'t str, rep: R) -> Result<Cow<'t, str>> {
self.try_replacen(text, 1, rep)
}
pub fn replace_all<'t, R: Replacer>(&self, text: &'t str, rep: R) -> Cow<'t, str> {
self.replacen(text, 0, rep)
}
pub fn try_replace_all<'t, R: Replacer>(&self, text: &'t str, rep: R) -> Result<Cow<'t, str>> {
self.try_replacen(text, 0, rep)
}
pub fn replacen<'t, R: Replacer>(&self, text: &'t str, limit: usize, rep: R) -> Cow<'t, str> {
self.try_replacen(text, limit, rep).unwrap()
}
pub fn try_replacen<'t, R: Replacer>(
&self,
text: &'t str,
limit: usize,
rep: R,
) -> Result<Cow<'t, str>> {
replacen_with(
text,
limit,
rep,
|| self.find_iter(text),
|| Captures {
inner: self.capture_locations().slots,
named_groups: Arc::clone(&self.named_groups),
input: text,
},
|input, flags, slots| self.captures_into(input, flags, slots, None),
)
}
pub fn split<'r, 'h>(&'r self, target: &'h str) -> Split<'r, 'h> {
Split {
matches: self.find_iter(target),
next_start: 0,
target,
}
}
pub fn splitn<'r, 'h>(&'r self, target: &'h str, limit: usize) -> SplitN<'r, 'h> {
SplitN {
splits: self.split(target),
limit,
}
}
}
#[doc(hidden)]
#[derive(Debug)]
#[allow(dead_code)]
pub struct DebugRegex<'a>(pub &'a Regex);
impl fmt::Display for DebugRegex<'_> {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
self.0.debug_print(f)
}
}
fn prepare_tree(tree: &mut ExprTree, runtime: &HardRegexRuntimeOptions) -> (bool, AnalyzeContext) {
let requires_capture_group_fixup = if runtime.find_not_empty {
false
} else {
optimize(tree)
};
let context = AnalyzeContext {
explicit_capture_group_0: requires_capture_group_fixup,
find_not_empty: runtime.find_not_empty,
disallow_empty_match_at_eof_after_newline: runtime
.disallow_empty_match_at_eof_after_newline,
allow_input_assertion_overrides: runtime.allow_input_assertion_overrides,
};
(requires_capture_group_fixup, context)
}
fn word_boundary_automata(
expr: &Expr,
options: &RegexOptions,
n_groups: usize,
) -> Option<RegularRoute> {
if regular::rich_option(options).is_some() || regular::rich_construct(expr).is_some() {
return None;
}
let unicode = options.syntaxc.get_unicode() && !matches!(options.bytes_mode, BytesMode::Ascii);
let utf8 = matches!(options.bytes_mode, BytesMode::Unicode);
let hir = to_hir::expr_to_hir(expr, &mut to_hir::HirCtx::new(unicode, utf8))
.filter(|hir| hir.properties().explicit_captures_len() + 1 == n_groups)?;
let compile_options = CompileOptions {
bytes_mode: options.bytes_mode,
unicode,
delegate_size_limit: options.delegate_size_limit,
delegate_dfa_size_limit: options.delegate_dfa_size_limit,
..CompileOptions::default()
};
let usage = if options.delegate_prefilter {
compile::DelegateUsage::unanchored()
} else {
compile::DelegateUsage::unanchored_no_prefilter()
};
let ascii = matches!(options.bytes_mode, BytesMode::Ascii);
Some(RegularRoute::new(hir, compile_options, usage, ascii, None))
}
fn edge_lookarounds(expr: &Expr) -> bool {
let Expr::Concat(children) = expr else {
return false;
};
let edge = |child: &Expr| match child {
Expr::LookAround(..) => Some(true),
Expr::Assertion(_) => None,
_ => Some(false),
};
children.iter().find_map(edge) == Some(true)
|| children.iter().rev().find_map(edge) == Some(true)
}
fn assertion_route(
expr: &Expr,
prog: &Prog,
options: &RegexOptions,
n_groups: usize,
) -> Option<RegularRoute> {
if regular::rich_option(options).is_some() {
return None;
}
let Expr::Concat(children) = expr else {
return None;
};
let edge = |child: &&Expr, kinds: [LookAround; 2]| match child {
Expr::LookAround(_, kind) => kinds.contains(kind),
Expr::Assertion(_) => true,
_ => false,
};
let front = children
.iter()
.take_while(|child| edge(child, [LookAround::LookBehind, LookAround::LookBehindNeg]))
.count();
let back = children[front..]
.iter()
.rev()
.take_while(|child| edge(child, [LookAround::LookAhead, LookAround::LookAheadNeg]))
.count();
let is_lookaround = |child: &&Expr| matches!(child, Expr::LookAround(..));
let (behind, ahead): (Vec<&Expr>, Vec<&Expr>) = (
children[..front].iter().filter(is_lookaround).collect(),
children[children.len() - back..]
.iter()
.filter(is_lookaround)
.collect(),
);
if behind.len() + ahead.len() == 0 || front + back == children.len() {
return None;
}
let middle = &children[front..children.len() - back];
let core = Expr::Concat(
children[..front]
.iter()
.filter(|child| !is_lookaround(child))
.chain(middle)
.chain(
children[children.len() - back..]
.iter()
.filter(|child| !is_lookaround(child)),
)
.cloned()
.collect(),
);
if regular::rich_construct(&core).is_some() {
return None;
}
let unicode = options.syntaxc.get_unicode() && !matches!(options.bytes_mode, BytesMode::Ascii);
let utf8 = matches!(options.bytes_mode, BytesMode::Unicode);
let hir = to_hir::expr_to_hir(&core, &mut to_hir::HirCtx::new(unicode, utf8))
.filter(|hir| hir.properties().explicit_captures_len() + 1 == n_groups)?;
let lookaround = |child: &Expr| {
let Expr::LookAround(body, kind) = child else {
return None;
};
let negated = matches!(kind, LookAround::LookAheadNeg | LookAround::LookBehindNeg);
let body = to_hir::expr_to_hir(body, &mut to_hir::HirCtx::new(unicode, utf8))?;
plan::Edge::new(&body, negated)
};
let edges = plan::Edges {
behind: behind.into_iter().map(lookaround).collect::<Option<_>>()?,
ahead: ahead.into_iter().map(lookaround).collect::<Option<_>>()?,
prefilter: prog
.start_filter()
.and_then(StartFilter::behind_prefilter)
.map(|(literals, prefilter)| (literals.to_vec(), prefilter.clone())),
};
let compile_options = CompileOptions {
bytes_mode: options.bytes_mode,
unicode,
delegate_size_limit: options.delegate_size_limit,
delegate_dfa_size_limit: options.delegate_dfa_size_limit,
..CompileOptions::default()
};
let usage = if options.delegate_prefilter {
compile::DelegateUsage::unanchored()
} else {
compile::DelegateUsage::unanchored_no_prefilter()
};
let ascii = matches!(options.bytes_mode, BytesMode::Ascii);
Some(RegularRoute::new(
hir,
compile_options,
usage,
ascii,
Some(edges),
))
}
fn limit_recovery<'r>(
route: Option<&'r Automata>,
error: &Error,
) -> Option<(&'r Automata, &'r RaRegex)> {
if !matches!(
error,
Error::RuntimeError(RuntimeError::BacktrackLimitExceeded)
) {
return None;
}
let route = route?;
Some((route, route.regex()?))
}
type RegularCache<'c> = Option<(&'c mut regex_automata::meta::Cache, &'c mut RaCaptures)>;
#[inline]
fn regular_find(
regex: &RaRegex,
input: &RaInput<'_>,
cache: RegularCache<'_>,
) -> Option<(usize, usize)> {
match cache {
Some((cache, _)) => regex.search_with(cache, input),
None => regex.search(input),
}
.map(|found| (found.start(), found.end()))
}
fn regular_captures_into(
regex: &RaRegex,
input: &RaInput<'_>,
cache: RegularCache<'_>,
saves: &mut Vec<usize>,
) -> bool {
let fill = |locations: &RaCaptures, saves: &mut Vec<usize>| {
saves.clear();
if locations.is_match() {
for group in 0..locations.group_len() {
let span = locations.get_group(group);
saves.push(span.map_or(usize::MAX, |span| span.start));
saves.push(span.map_or(usize::MAX, |span| span.end));
}
}
};
match cache {
Some((cache, locations)) => {
regex.search_captures_with(cache, input, locations);
fill(locations, saves);
}
None => {
let mut locations = regex.create_captures();
regex.search_captures(input, &mut locations);
fill(&locations, saves);
}
}
!saves.is_empty()
}
fn regular_captures(
regex: &RaRegex,
input: &RaInput<'_>,
cache: RegularCache<'_>,
) -> Option<RaCaptures> {
match cache {
Some((cache, locations)) => {
regex.search_captures_with(cache, input, locations);
locations.is_match().then(|| locations.clone())
}
None => {
let mut locations = regex.create_captures();
regex.search_captures(input, &mut locations);
locations.is_match().then_some(locations)
}
}
}
fn capture_names_of(named_groups: &NamedGroups, len: usize) -> CaptureNames<'_> {
let mut names = Vec::new();
names.resize(len, None);
for (name, &i) in named_groups.iter() {
names[i] = Some(name.as_str());
}
CaptureNames(names.into_iter())
}
fn replacen_with<'t, R, E, M>(
text: &'t str,
limit: usize,
mut rep: R,
matches: impl FnOnce() -> M,
captures: impl FnOnce() -> Captures<'t, str>,
mut fill: impl FnMut(&RegexInput<'t, str>, u32, &mut CapturesImpl) -> core::result::Result<bool, E>,
) -> core::result::Result<Cow<'t, str>, E>
where
R: Replacer,
M: Iterator<Item = core::result::Result<Match<'t>, E>>,
{
if let Some(rep) = rep.no_expansion() {
let mut it = matches().enumerate().peekable();
if it.peek().is_none() {
return Ok(Cow::Borrowed(text));
}
let mut new = String::with_capacity(text.len());
let mut last_match = 0;
for (i, m) in it {
let m = m?;
if limit > 0 && i >= limit {
break;
}
new.push_str(&text[last_match..m.start()]);
new.push_str(&rep);
last_match = m.end();
}
new.push_str(&text[last_match..]);
return Ok(Cow::Owned(new));
}
let mut captures = captures();
let mut state = IterState::new(RegexInput::new(text));
let mut new = None;
let mut last_match = 0;
for i in 0.. {
let found = state.next_with(|input, flags| {
let matched = fill(input, flags, &mut captures.inner)?;
Ok(matched.then(|| {
let span = captures.inner.get_span(0);
let span = span.expect("captures only report matches");
(span, span)
}))
});
let Some(found) = found else {
break;
};
let (start, end) = found?;
if limit > 0 && i >= limit {
break;
}
let new = new.get_or_insert_with(|| String::with_capacity(text.len()));
new.push_str(&text[last_match..start]);
rep.replace_append(&captures, new);
last_match = end;
}
Ok(match new {
Some(mut new) => {
new.push_str(&text[last_match..]);
Cow::Owned(new)
}
None => Cow::Borrowed(text),
})
}
#[inline]
fn ra_input<'a, S: input::Input + ?Sized>(input: &'a RegexInput<'a, S>) -> RaInput<'a> {
let mut ra_input = RaInput::new(input.haystack().as_bytes()).range(input.get_range());
ra_input.set_start(input.effective_start());
if input.is_anchored() {
ra_input.set_anchored(RaAnchored::Yes);
}
ra_input
}
const FIXUP_SLOTS: usize = 32;
fn plan_input<'h, S: input::Input + ?Sized>(input: &RegexInput<'h, S>) -> PlanInput<'h> {
let haystack = input.haystack();
PlanInput {
haystack: haystack.as_bytes(),
start: input.effective_start(),
end: input.get_range().end,
anchored: input.is_anchored(),
utf8: haystack.as_utf8().is_some(),
}
}
fn plan_find<S: input::Input + ?Sized>(
plan: &Plan,
input: &RegexInput<'_, S>,
slots: Option<&mut [Option<NonMaxUsize>]>,
) -> Option<(usize, usize)> {
plan.find(&plan_input(input), slots)
}
#[inline(never)]
fn plan_find_rewritten<S: input::Input + ?Sized>(
plan: &Plan,
input: &RegexInput<'_, S>,
) -> Option<(usize, usize)> {
let mut slots = [usize::MAX; FIXUP_SLOTS];
let found = plan.find(&plan_input(input), Some(&mut slots[..plan.slot_len()]));
found.and((slots[2] != usize::MAX).then_some((slots[2], slots[3])))
}
fn plan_is_match<S: input::Input + ?Sized>(plan: &Plan, input: &RegexInput<'_, S>) -> bool {
plan.is_match(&plan_input(input))
}
fn plan_captures_into<S: input::Input + ?Sized>(
plan: &Plan,
input: &RegexInput<'_, S>,
locations: &mut RaCaptures,
) {
let found = plan_find(plan, input, Some(locations.slots_mut())).is_some();
locations.set_pattern(found.then_some(regex_automata::PatternID::ZERO));
}
impl TryFrom<&str> for Regex {
type Error = Error;
fn try_from(s: &str) -> Result<Self> {
Self::new(s)
}
}
impl TryFrom<String> for Regex {
type Error = Error;
fn try_from(s: String) -> Result<Self> {
Self::new(&s)
}
}
impl<'t> Match<'t> {
#[inline]
pub fn start(&self) -> usize {
self.start
}
#[inline]
pub fn end(&self) -> usize {
self.end
}
#[inline]
pub fn range(&self) -> Range<usize> {
self.start..self.end
}
#[inline]
pub fn as_str(&self) -> &'t str {
&self.text[self.start..self.end]
}
pub(crate) fn new(text: &'t str, start: usize, end: usize) -> Match<'t> {
Match { text, start, end }
}
}
impl<'t> From<Match<'t>> for &'t str {
fn from(m: Match<'t>) -> &'t str {
m.as_str()
}
}
impl<'t> From<Match<'t>> for Range<usize> {
fn from(m: Match<'t>) -> Range<usize> {
m.range()
}
}
#[allow(clippy::len_without_is_empty)] impl<'t, S: input::Input + ?Sized> Captures<'t, S> {
pub(crate) fn get_span(&self, i: usize) -> Option<(usize, usize)> {
self.inner.get_span(i)
}
pub fn get(&self, i: usize) -> Option<S::Match<'t>> {
self.inner
.get_span(i)
.map(|(start, end)| self.input.make_match(start, end))
}
pub fn name(&self, name: &str) -> Option<S::Match<'t>> {
self.named_groups.get(name).and_then(|i| self.get(*i))
}
pub fn iter<'c>(&'c self) -> SubCaptureMatches<'c, 't, S> {
SubCaptureMatches { data: self, i: 0 }
}
pub fn len(&self) -> usize {
self.inner.len()
}
pub fn input_as_bytes(&self) -> &'t [u8] {
self.input.as_bytes()
}
}
impl<'t> Captures<'t, str> {
pub fn expand(&self, replacement: &str, dst: &mut String) {
Expander::default().append_expansion(dst, replacement, self);
}
}
impl<'t> Index<usize> for Captures<'t, str> {
type Output = str;
fn index(&self, i: usize) -> &str {
self.get(i)
.map(|m| m.as_str())
.unwrap_or_else(|| panic!("no group at index '{}'", i))
}
}
impl<'t, 'i> Index<&'i str> for Captures<'t, str> {
type Output = str;
fn index<'a>(&'a self, name: &'i str) -> &'a str {
self.name(name)
.map(|m| m.as_str())
.unwrap_or_else(|| panic!("no group named '{}'", name))
}
}
impl<'c, 't, S: input::Input + ?Sized> Iterator for SubCaptureMatches<'c, 't, S> {
type Item = Option<S::Match<'t>>;
fn next(&mut self) -> Option<Option<S::Match<'t>>> {
if self.i < self.data.len() {
let result = self.data.get(self.i);
self.i += 1;
Some(result)
} else {
None
}
}
}
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum Expr {
Empty,
Any {
newline: bool,
crlf: bool,
},
Assertion(Assertion),
GeneralNewline {
unicode: bool,
},
Literal {
val: String,
casei: bool,
},
Concat(Vec<Expr>),
Alt(Vec<Expr>),
Group(Arc<Expr>),
LookAround(Box<Expr>, LookAround),
Repeat {
child: Box<Expr>,
lo: usize,
hi: usize,
greedy: bool,
},
Delegate {
inner: String,
casei: bool,
},
Backref {
group: usize,
casei: bool,
},
BackrefWithRelativeRecursionLevel {
group: usize,
relative_level: isize,
casei: bool,
},
AtomicGroup(Box<Expr>),
KeepOut,
ContinueFromPreviousMatchEnd,
BackrefExistsCondition {
group: usize,
relative_recursion_level: Option<isize>,
},
Conditional {
condition: Box<Expr>,
true_branch: Box<Expr>,
false_branch: Box<Expr>,
},
SubroutineCall(usize),
BacktrackingControlVerb(BacktrackingControlVerb),
Absent(Absent),
DefineGroup {
definitions: Box<Expr>,
},
AstNode(AstNode, usize),
}
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum CaptureGroupTarget {
ByNumber(usize),
ByName(String),
Relative(isize),
}
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum AstNode {
AstGroup {
name: Option<String>,
inner: Box<Expr>,
},
Backref {
target: CaptureGroupTarget,
casei: bool,
relative_recursion_level: Option<isize>,
},
SubroutineCall(CaptureGroupTarget),
BackrefExistsCondition {
target: CaptureGroupTarget,
relative_recursion_level: Option<isize>,
},
}
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum LookAround {
LookAhead,
LookAheadNeg,
LookBehind,
LookBehindNeg,
}
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum Absent {
Repeater(Box<Expr>),
Expression {
absent: Box<Expr>,
exp: Box<Expr>,
},
Stopper(Box<Expr>),
Clear,
}
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum BacktrackingControlVerb {
Fail,
Accept,
Commit,
Skip,
Prune,
}
pub struct CaptureNames<'r>(vec::IntoIter<Option<&'r str>>);
impl Debug for CaptureNames<'_> {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.write_str("<CaptureNames>")
}
}
impl<'r> Iterator for CaptureNames<'r> {
type Item = Option<&'r str>;
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
}
}
fn push_usize(s: &mut String, x: usize) {
if x >= 10 {
push_usize(s, x / 10);
s.push((b'0' + (x % 10) as u8) as char);
} else {
s.push((b'0' + (x as u8)) as char);
}
}
pub(crate) fn write_quantifier(buf: &mut String, lo: usize, hi: usize, greedy: bool) {
match (lo, hi) {
(0, 1) => buf.push('?'),
(0, usize::MAX) => buf.push('*'),
(1, usize::MAX) => buf.push('+'),
(lo, hi) => {
buf.push('{');
push_usize(buf, lo);
if lo != hi {
buf.push(',');
if hi != usize::MAX {
push_usize(buf, hi);
}
}
buf.push('}');
}
}
if !greedy {
buf.push('?');
}
}
fn is_special(c: char) -> bool {
matches!(
c,
'\\' | '.' | '+' | '*' | '?' | '(' | ')' | '|' | '[' | ']' | '{' | '}' | '^' | '$' | '#'
)
}
pub(crate) fn push_quoted(buf: &mut String, s: &str) {
if !s.bytes().any(|b| {
b == b'\\'
|| b == b'\n'
|| b == b'\t'
|| b == b'\r'
|| matches!(
b,
b'.' | b'+'
| b'*'
| b'?'
| b'('
| b')'
| b'|'
| b'['
| b']'
| b'{'
| b'}'
| b'^'
| b'$'
| b'#'
)
}) {
buf.push_str(s);
return;
}
for c in s.chars() {
match c {
'\\' => buf.push_str("\\\\"),
'\n' => buf.push_str("\\n"),
'\t' => buf.push_str("\\t"),
'\r' => buf.push_str("\\r"),
_ => {
if is_special(c) {
buf.push('\\');
}
buf.push(c);
}
}
}
}
pub fn escape(text: &str) -> Cow<'_, str> {
match text.bytes().filter(|&b| is_special(b as char)).count() {
0 => Cow::Borrowed(text),
n => {
let mut buf = String::with_capacity(text.len() + n);
push_quoted(&mut buf, text);
Cow::Owned(buf)
}
}
}
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum Assertion {
StartText,
EndText,
EndTextIgnoreTrailingNewlines {
crlf: bool,
},
StartLine {
crlf: bool,
},
StartLineOniguruma {
crlf: bool,
},
EndLine {
crlf: bool,
},
LeftWordBoundary,
LeftWordHalfBoundary,
RightWordBoundary,
RightWordHalfBoundary,
WordBoundary,
NotWordBoundary,
}
impl Assertion {
pub(crate) fn is_always_hard(&self) -> bool {
use Assertion::*;
matches!(
self,
LeftWordBoundary
| LeftWordHalfBoundary
| RightWordBoundary
| RightWordHalfBoundary
| WordBoundary
| NotWordBoundary
| EndTextIgnoreTrailingNewlines { .. }
)
}
}
#[derive(Debug)]
pub enum ExprChildrenIter<'a> {
Empty,
Single(Option<&'a Expr>),
Vec(alloc::slice::Iter<'a, Expr>),
Triple {
first: Option<&'a Expr>,
second: Option<&'a Expr>,
third: Option<&'a Expr>,
},
}
#[derive(Debug)]
pub enum ExprChildrenIterMut<'a> {
Empty,
Single(Option<&'a mut Expr>),
Vec(alloc::slice::IterMut<'a, Expr>),
Triple {
first: Option<&'a mut Expr>,
second: Option<&'a mut Expr>,
third: Option<&'a mut Expr>,
},
}
impl<'a> Iterator for ExprChildrenIter<'a> {
type Item = &'a Expr;
fn next(&mut self) -> Option<Self::Item> {
match self {
ExprChildrenIter::Empty => None,
ExprChildrenIter::Single(child) => child.take(),
ExprChildrenIter::Vec(iter) => iter.next(),
ExprChildrenIter::Triple {
first,
second,
third,
} => first
.take()
.or_else(|| second.take())
.or_else(|| third.take()),
}
}
}
impl<'a> Iterator for ExprChildrenIterMut<'a> {
type Item = &'a mut Expr;
fn next(&mut self) -> Option<Self::Item> {
match self {
ExprChildrenIterMut::Empty => None,
ExprChildrenIterMut::Single(child) => child.take(),
ExprChildrenIterMut::Vec(iter) => iter.next(),
ExprChildrenIterMut::Triple {
first,
second,
third,
} => first
.take()
.or_else(|| second.take())
.or_else(|| third.take()),
}
}
}
macro_rules! children_iter_match {
($self:expr, $iter:ident, $vec_method:ident, $single_method:ident, $group_method:ident) => {
match $self {
Expr::Concat(children) | Expr::Alt(children) => $iter::Vec(children.$vec_method()),
Expr::Group(child) => $iter::Single(Some(Arc::$group_method(child))),
Expr::Absent(Absent::Repeater(child))
| Expr::Absent(Absent::Stopper(child))
| Expr::LookAround(child, _)
| Expr::AtomicGroup(child)
| Expr::Repeat { child, .. } => $iter::Single(Some(child.$single_method())),
Expr::Conditional {
condition,
true_branch,
false_branch,
} => $iter::Triple {
first: Some(condition.$single_method()),
second: Some(true_branch.$single_method()),
third: Some(false_branch.$single_method()),
},
Expr::Absent(Absent::Expression { absent, exp }) => $iter::Triple {
first: Some(absent.$single_method()),
second: Some(exp.$single_method()),
third: None,
},
Expr::DefineGroup { definitions } => $iter::Single(Some(definitions.$single_method())),
_ if $self.is_leaf_node() => $iter::Empty,
_ => unimplemented!(),
}
};
}
impl Expr {
pub fn parse_tree(re: &str) -> Result<ExprTree> {
Expr::parse_tree_with_flags(re, RegexOptions::default().compute_flags())
}
pub fn parse_tree_with_flags(re: &str, flags: u32) -> Result<ExprTree> {
Parser::parse_with_flags(re, flags)
}
pub fn is_leaf_node(&self) -> bool {
matches!(
self,
Expr::Empty
| Expr::Any { .. }
| Expr::Assertion(_)
| Expr::GeneralNewline { .. }
| Expr::Literal { .. }
| Expr::Delegate { .. }
| Expr::Backref { .. }
| Expr::BackrefWithRelativeRecursionLevel { .. }
| Expr::KeepOut
| Expr::ContinueFromPreviousMatchEnd
| Expr::BackrefExistsCondition { .. }
| Expr::BacktrackingControlVerb(_)
| Expr::SubroutineCall(_)
| Expr::Absent(Absent::Clear)
| Expr::AstNode(..),
)
}
pub fn has_descendant(&self, predicate: impl Fn(&Expr) -> bool) -> bool {
let mut stack: Vec<&Expr> = self.children_iter().collect();
while let Some(expr) = stack.pop() {
if predicate(expr) {
return true;
}
stack.extend(expr.children_iter());
}
false
}
pub fn children_iter(&self) -> ExprChildrenIter<'_> {
children_iter_match!(self, ExprChildrenIter, iter, as_ref, as_ref)
}
pub fn children_iter_mut(&mut self) -> ExprChildrenIterMut<'_> {
children_iter_match!(self, ExprChildrenIterMut, iter_mut, as_mut, make_mut)
}
pub fn to_str(&self, buf: &mut String, precedence: u8) {
match *self {
Expr::Empty => (),
Expr::Any { newline, crlf } => buf.push_str(match (newline, crlf) {
(true, _) => "(?s:.)",
(false, true) => "(?R-s:.)",
(false, false) => ".",
}),
Expr::Literal { ref val, casei } => {
if casei {
buf.push_str("(?i:");
}
push_quoted(buf, val);
if casei {
buf.push(')');
}
}
Expr::Assertion(Assertion::StartText) => buf.push('^'),
Expr::Assertion(Assertion::EndText) => buf.push('$'),
Expr::Assertion(
Assertion::StartLine { crlf: false }
| Assertion::StartLineOniguruma { crlf: false },
) => buf.push_str("(?m:^)"),
Expr::Assertion(Assertion::EndLine { crlf: false }) => buf.push_str("(?m:$)"),
Expr::Assertion(
Assertion::StartLine { crlf: true } | Assertion::StartLineOniguruma { crlf: true },
) => buf.push_str("(?Rm:^)"),
Expr::Assertion(Assertion::EndLine { crlf: true }) => buf.push_str("(?Rm:$)"),
Expr::Concat(ref children) => {
if precedence > 1 {
buf.push_str("(?:");
}
for child in children {
child.to_str(buf, 2);
}
if precedence > 1 {
buf.push(')')
}
}
Expr::Alt(_) => {
if precedence > 0 {
buf.push_str("(?:");
}
let mut children = self.children_iter();
if let Some(first) = children.next() {
first.to_str(buf, 1);
for child in children {
buf.push('|');
child.to_str(buf, 1);
}
}
if precedence > 0 {
buf.push(')');
}
}
Expr::Group(ref child) => {
buf.push('(');
child.to_str(buf, 0);
buf.push(')');
}
Expr::Repeat {
ref child,
lo,
hi,
greedy,
} => {
if precedence > 2 {
buf.push_str("(?:");
}
child.to_str(buf, 3);
write_quantifier(buf, lo, hi, greedy);
if precedence > 2 {
buf.push(')');
}
}
Expr::Delegate {
ref inner, casei, ..
} => {
if casei {
buf.push_str("(?i:");
}
buf.push_str(inner);
if casei {
buf.push(')');
}
}
Expr::DefineGroup { .. } => {
}
_ => panic!("attempting to format hard expr {:?}", self),
}
}
}
fn prev_codepoint_ix(s: &str, mut ix: usize) -> usize {
let bytes = s.as_bytes();
loop {
ix -= 1;
if (bytes[ix] as i8) >= -0x40 {
break;
}
}
ix
}
fn codepoint_len(b: u8) -> usize {
match b {
b if b < 0x80 => 1,
b if b < 0xe0 => 2,
b if b < 0xf0 => 3,
_ => 4,
}
}
#[doc(hidden)]
pub mod internal {
pub use crate::analyze::{AnalyzeContext, Info, analyze, can_compile_as_anchored};
pub use crate::compile::{CompileOptions, compile};
pub use crate::optimize::optimize;
pub use crate::parse_flags::{
FLAG_CASEI, FLAG_CRLF, FLAG_DOTNL, FLAG_IGNORE_NUMBERED_GROUPS_WHEN_NAMED_GROUPS_EXIST,
FLAG_IGNORE_SPACE, FLAG_MULTI, FLAG_ONIGURUMA_MODE, FLAG_UNICODE,
};
pub use crate::vm::{Insn, Prog, Seek, run_default, run_trace};
}
#[cfg(test)]
mod tests {
use alloc::borrow::Cow;
use alloc::boxed::Box;
use alloc::string::{String, ToString};
use alloc::sync::Arc;
use alloc::vec::Vec;
use alloc::{format, vec};
use crate::parse::{make_group, make_literal};
use crate::{Absent, Expr, Regex, RegexBuilder, RegexImpl, RegexInput};
fn to_str(e: Expr) -> String {
let mut s = String::new();
e.to_str(&mut s, 0);
s
}
#[test]
fn to_str_concat_alt() {
let e = Expr::Concat(vec![
Expr::Alt(vec![make_literal("a"), make_literal("b")]),
make_literal("c"),
]);
assert_eq!(to_str(e), "(?:a|b)c");
}
#[test]
fn to_str_rep_concat() {
let e = Expr::Repeat {
child: Box::new(Expr::Concat(vec![make_literal("a"), make_literal("b")])),
lo: 2,
hi: 3,
greedy: true,
};
assert_eq!(to_str(e), "(?:ab){2,3}");
}
#[test]
fn to_str_group_alt() {
let e = Expr::Group(Arc::new(Expr::Alt(vec![
make_literal("a"),
make_literal("b"),
])));
assert_eq!(to_str(e), "(a|b)");
}
#[test]
fn to_str_literal_special_chars() {
assert_eq!(to_str(make_literal("\n")), "\\n");
assert_eq!(to_str(make_literal("\t")), "\\t");
assert_eq!(to_str(make_literal("\r")), "\\r");
assert_eq!(to_str(make_literal("\\")), "\\\\");
assert_eq!(to_str(make_literal(".")), "\\.");
}
#[test]
fn as_str_debug() {
let s = r"(a+)b\1";
let regex = Regex::new(s).unwrap();
assert_eq!(s, regex.as_str());
assert_eq!(s, format!("{:?}", regex));
}
#[test]
fn display() {
let s = r"(a+)b\1";
let regex = Regex::new(s).unwrap();
assert_eq!(s, format!("{}", regex));
}
#[test]
fn from_str() {
let s = r"(a+)b\1";
let regex = s.parse::<Regex>().unwrap();
assert_eq!(regex.as_str(), s);
}
#[test]
fn to_str_repeat() {
fn repeat(lo: usize, hi: usize, greedy: bool) -> Expr {
Expr::Repeat {
child: Box::new(make_literal("a")),
lo,
hi,
greedy,
}
}
assert_eq!(to_str(repeat(2, 2, true)), "a{2}");
assert_eq!(to_str(repeat(2, 2, false)), "a{2}?");
assert_eq!(to_str(repeat(2, 3, true)), "a{2,3}");
assert_eq!(to_str(repeat(2, 3, false)), "a{2,3}?");
assert_eq!(to_str(repeat(2, usize::MAX, true)), "a{2,}");
assert_eq!(to_str(repeat(2, usize::MAX, false)), "a{2,}?");
assert_eq!(to_str(repeat(0, 1, true)), "a?");
assert_eq!(to_str(repeat(0, 1, false)), "a??");
assert_eq!(to_str(repeat(0, usize::MAX, true)), "a*");
assert_eq!(to_str(repeat(0, usize::MAX, false)), "a*?");
assert_eq!(to_str(repeat(1, usize::MAX, true)), "a+");
assert_eq!(to_str(repeat(1, usize::MAX, false)), "a+?");
}
#[test]
fn escape() {
match crate::escape("@foo") {
Cow::Borrowed(s) => assert_eq!(s, "@foo"),
_ => panic!("Value should be borrowed."),
}
assert_eq!(crate::escape("fo*o").into_owned(), "fo\\*o");
assert_eq!(crate::escape("fø*ø").into_owned(), "fø\\*ø");
}
#[test]
fn push_quoted_special_chars() {
fn pq(s: &str) -> String {
let mut buf = String::new();
crate::push_quoted(&mut buf, s);
buf
}
assert_eq!(pq("\n"), "\\n");
assert_eq!(pq("\t"), "\\t");
assert_eq!(pq("\r"), "\\r");
assert_eq!(pq("\\"), "\\\\");
assert_eq!(pq("."), "\\.");
assert_eq!(pq("hello"), "hello");
assert_eq!(pq("a.b"), "a\\.b");
assert_eq!(pq("fø*ø"), "fø\\*ø");
}
#[test]
fn trailing_positive_lookahead_wrap_capture_group_fixup() {
let s = r"a+(?=c)";
let regex = s.parse::<Regex>().unwrap();
assert!(
matches!(
regex.inner,
RegexImpl::Wrap {
explicit_capture_group_0: true,
..
}
),
"trailing positive lookahead for an otherwise easy pattern should avoid going through the VM"
);
assert_eq!(s, regex.as_str());
assert_eq!(s, format!("{:?}", regex));
}
#[test]
fn easy_regex() {
let s = r"(a+)b";
let regex = s.parse::<Regex>().unwrap();
assert!(
matches!(
regex.inner,
RegexImpl::Wrap {
explicit_capture_group_0: false,
..
}
),
"easy pattern should avoid going through the VM, and capture group 0 should be implicit"
);
assert_eq!(s, regex.as_str());
assert_eq!(s, format!("{:?}", regex));
}
#[test]
fn hard_regex() {
let s = r"(a+)(?>c)";
let regex = s.parse::<Regex>().unwrap();
assert!(
matches!(regex.inner, RegexImpl::Fancy { .. }),
"hard regex should be compiled into a VM"
);
assert_eq!(s, regex.as_str());
assert_eq!(s, format!("{:?}", regex));
}
#[test]
fn start_end_text_assertions_can_stay_wrap_without_override_opt_in() {
let regex = Regex::new(r"\Afoo\z").unwrap();
assert!(
matches!(regex.inner, RegexImpl::Wrap { .. }),
r"\A...\z should stay on the wrap path unless input assertion overrides are enabled"
);
}
#[test]
fn start_end_text_assertions_become_fancy_with_override_opt_in() {
let regex = RegexBuilder::new(r"\Afoo\z")
.allow_input_assertion_overrides(true)
.build()
.unwrap();
assert!(
matches!(regex.inner, RegexImpl::Fancy { .. }),
r"\A...\z should use the VM when input assertion overrides are enabled"
);
}
fn has_regular_route(regex: &Regex) -> bool {
match ®ex.inner {
RegexImpl::Fancy {
regular: Some(route),
..
} => route.engine().automata().is_some(),
_ => false,
}
}
fn fancy_prog(regex: &Regex) -> &crate::vm::Prog {
match ®ex.inner {
RegexImpl::Fancy { prog, .. } => prog,
RegexImpl::Wrap { .. } => unreachable!("expected a VM program"),
}
}
#[test]
fn seek_approximation_is_only_built_for_a_seek() {
for (pattern, released) in [
(r"(abc)\1", "(?:abc)(?:abc)"),
(r"(?<=Mr\. |Dr\. )[A-Z]\w+", r"[A-Z]\w+"),
(r"\g<1>-(a+)\1", "a+-a+a+"),
(r"(?i)(?<n>a+)\k<n>(?=b)", "(?:(?i:a)+(?i:(?i:a)+))(?i:b)"),
(r"(?m)(x)\1$", "xx(?m:$)"),
(r"(a)?(?(1)b|c)\1", "a?(?:b|c)a"),
(r"(?(DEFINE)(?<d>\d))\g<d>(\w)\1", r"\d\w\d"),
(r"(?x) ( a ) \1 # comment", "aa"),
] {
let plain = Regex::new(pattern).unwrap();
let seeking = RegexBuilder::new(pattern)
.seek_filter(|_| true)
.build()
.unwrap();
assert_eq!(fancy_prog(&plain).seek_pattern(), None, "{pattern}");
assert_eq!(
fancy_prog(&seeking).seek_pattern(),
Some(released),
"{pattern}"
);
assert_eq!(plain.seek_pattern().unwrap(), released, "{pattern}");
assert_eq!(seeking.seek_pattern().unwrap(), released, "{pattern}");
}
let anchored = RegexBuilder::new(r"^(a)\1").seek(true).build().unwrap();
assert_eq!(fancy_prog(&anchored).seek_pattern(), None);
assert_eq!(anchored.seek_pattern().unwrap(), "^aa");
let declined = RegexBuilder::new(r"(abc)\1")
.seek_filter(|_| false)
.build()
.unwrap();
assert_eq!(fancy_prog(&declined).seek_pattern(), None);
assert_eq!(declined.seek_pattern().unwrap(), "(?:abc)(?:abc)");
}
#[test]
fn lookbehind_literals_lead_seek_without_an_explicit_limit() {
let plan = |builder: &mut RegexBuilder| {
let regex = builder.build().unwrap();
let prog = fancy_prog(®ex);
(
prog.seek_pattern().is_some(),
prog.start_filter().is_some(),
prog.filter_leads_seek(),
)
};
let titled = r"(?<=Mr\. )[A-Z]\w+";
assert_eq!(
plan(RegexBuilder::new(titled).seek(true)),
(true, true, true)
);
assert_eq!(
plan(RegexBuilder::new(titled).seek(true).backtrack_limit(1000)),
(true, true, false)
);
assert_eq!(plan(&mut RegexBuilder::new(titled)), (false, true, false));
assert_eq!(
plan(RegexBuilder::new(r"#(\d)\1").seek(true)),
(true, true, false)
);
}
#[test]
fn word_boundary_patterns_get_a_regular_route() {
for pattern in [
r"\bfn\b",
r"\B\w+",
r"(?i)\<k(\w)\>",
r"\b\d+\b|\w",
r"\b{start-half}a",
r"\b(a|){2,3}",
r"\b(?:a|){0,4}b*",
] {
let regex = Regex::new(pattern).unwrap();
assert!(has_regular_route(®ex), "{pattern}");
}
for pattern in [
r"(a|)*\bb",
r"(?:\b|a)+b",
r"(\b\w*)*",
r"\b(\w+) \1\b",
r"\b(?=a)",
r"\bfoo\Kbar\b",
r"\bfoo(?=bar)",
r"(?>\b\w)",
r"\b\w++",
r"\Gab\b",
] {
let regex = Regex::new(pattern).unwrap();
assert!(matches!(regex.inner, RegexImpl::Fancy { .. }), "{pattern}");
assert!(!has_regular_route(®ex), "{pattern}");
}
let configured = |configure: fn(&mut RegexBuilder) -> &mut RegexBuilder| {
let mut builder = RegexBuilder::new(r"\bab\b");
configure(&mut builder);
has_regular_route(&builder.build().unwrap())
};
assert!(configured(|b| b.case_insensitive(true)));
assert!(configured(|b| b.bytes_mode(crate::BytesMode::Ascii)));
assert!(!configured(|b| b.backtrack_limit(1_000_000)));
assert!(!configured(|b| b.find_not_empty(true)));
assert!(!configured(|b| b.allow_input_assertion_overrides(true)));
}
#[cfg(all(feature = "native", target_os = "linux", target_arch = "x86_64"))]
#[test]
fn native_code_backs_the_regular_route_on_non_ascii_text() {
let regex = Regex::new(r"\b(?:fn|let|é)\b").unwrap();
assert!(has_regular_route(®ex));
assert!(regex.native.is_some());
assert!(regex.is_match("let x").unwrap());
assert!(!regex.is_match("fnord").unwrap());
assert!(regex.is_match("é x").unwrap());
assert!(!regex.is_match("éfn").unwrap());
}
#[test]
fn regular_route_dfa_gives_up_on_non_ascii_text() {
let regex = Regex::new(r"\b(?:a|a)+\b!").unwrap();
let find = |text: &str| {
let input = RegexInput::new(text);
let route = regex.regular_route(&input).unwrap().automata().unwrap();
(
route.find(&crate::ra_input(&input), None).is_err(),
route.is_match(&crate::ra_input(&input), None).is_err(),
)
};
assert_eq!(find("aaaa a!"), (false, false));
assert_eq!(find("aaaaé"), (true, true));
}
#[test]
fn regular_route_plan_answers_on_utf8_and_defers_in_ascii_mode() {
let answered = |pattern: &str, text: &str| {
let regex = Regex::new(pattern).unwrap();
let input = RegexInput::new(text);
let plan = regex.regular_route(&input).unwrap().plan().unwrap();
plan.find::<[usize]>(&crate::plan_input(&input), None)
};
assert_eq!(answered(r"\b\w+\b", "ab cd"), Some(Some((0, 2))));
assert_eq!(answered(r"\b\w+\b", "ab é"), Some(Some((0, 2))));
assert_eq!(answered(r"\b\w+\b", "ab\u{e9}"), Some(Some((0, 4))));
assert_eq!(answered(r"\b\w+\b", "\u{e9}\u{e9} x"), Some(Some((0, 4))));
assert_eq!(answered(r"\b\w+!", "\u{e9}\u{e9}"), Some(None));
assert_eq!(answered(r"\b(?:fn|let)\b", "é let"), Some(Some((3, 6))));
let ascii = |pattern: &str, text: &[u8]| {
let regex = RegexBuilder::new(pattern)
.bytes_mode(crate::BytesMode::Ascii)
.build()
.unwrap();
let input = RegexInput::new(text);
let plan = regex.regular_route(&input).unwrap().plan().unwrap();
plan.find::<[usize]>(&crate::plan_input(&input), None)
};
assert_eq!(ascii(r"\bfn\b", b"x fn \xFF"), Some(Some((2, 4))));
assert_eq!(ascii(r"\bfn\b", b"x fn \xFF"), None);
assert_eq!(ascii(r"\bfn\b", b"\xFF fn"), None);
assert_eq!(ascii(r"\b(?:fn|let)\b", b"x fn "), None);
}
#[test]
fn regular_route_is_chosen_per_search() {
let regex = Regex::new(r"\b\w+\b").unwrap();
let text = "é ab";
let routed = |input: RegexInput<'_, str>| regex.regular_route(&input).is_some();
assert!(routed(RegexInput::new(text)));
assert!(routed(RegexInput::new(text).from_pos(2)));
assert!(routed(RegexInput::new(text).range(3..5).anchored(true)));
assert!(!routed(RegexInput::new(text).from_pos(1)));
assert!(!routed(RegexInput::new(text).range(0..4)));
assert!(
regex
.regular_route(&RegexInput::new(text.as_bytes()))
.is_none()
);
let ascii = RegexBuilder::new(r"\b\w+\b")
.bytes_mode(crate::BytesMode::Ascii)
.build()
.unwrap();
let bytes: &[u8] = b"\xFF ab";
assert!(
ascii
.regular_route(&RegexInput::new(bytes).from_pos(1))
.is_some()
);
assert!(
ascii
.regular_route(&RegexInput::new(bytes).range(0..3))
.is_none()
);
}
#[test]
fn test_is_leaf_node_leaf_nodes() {
assert!(Expr::Empty.is_leaf_node());
assert!(
Expr::Any {
newline: false,
crlf: false
}
.is_leaf_node()
);
assert!(
Expr::Any {
newline: true,
crlf: false
}
.is_leaf_node()
);
assert!(Expr::Assertion(crate::Assertion::StartText).is_leaf_node());
assert!(
Expr::Literal {
val: "test".to_string(),
casei: false
}
.is_leaf_node()
);
assert!(
Expr::Delegate {
inner: "[0-9]".to_string(),
casei: false,
}
.is_leaf_node()
);
assert!(
Expr::Backref {
group: 1,
casei: false
}
.is_leaf_node()
);
assert!(
Expr::BackrefWithRelativeRecursionLevel {
group: 1,
relative_level: -1,
casei: false
}
.is_leaf_node()
);
assert!(Expr::KeepOut.is_leaf_node());
assert!(Expr::ContinueFromPreviousMatchEnd.is_leaf_node());
assert!(
Expr::BackrefExistsCondition {
group: 1,
relative_recursion_level: None
}
.is_leaf_node()
);
assert!(Expr::BacktrackingControlVerb(crate::BacktrackingControlVerb::Fail).is_leaf_node());
assert!(Expr::SubroutineCall(1).is_leaf_node());
assert!(Expr::Absent(Absent::Clear).is_leaf_node());
}
#[test]
fn test_is_leaf_node_non_leaf_nodes() {
assert!(!Expr::Concat(vec![make_literal("a")]).is_leaf_node());
assert!(!Expr::Alt(vec![make_literal("a"), make_literal("b")]).is_leaf_node());
assert!(!make_group(make_literal("a")).is_leaf_node());
assert!(
!Expr::LookAround(Box::new(make_literal("a")), crate::LookAround::LookAhead)
.is_leaf_node()
);
assert!(
!Expr::Repeat {
child: Box::new(make_literal("a")),
lo: 0,
hi: 1,
greedy: true
}
.is_leaf_node()
);
assert!(!Expr::AtomicGroup(Box::new(make_literal("a"))).is_leaf_node());
assert!(
!Expr::Conditional {
condition: Box::new(Expr::BackrefExistsCondition {
group: 1,
relative_recursion_level: None
}),
true_branch: Box::new(make_literal("a")),
false_branch: Box::new(Expr::Empty)
}
.is_leaf_node()
);
assert!(!Expr::Absent(Absent::Repeater(Box::new(make_literal("a")))).is_leaf_node());
assert!(
!Expr::Absent(Absent::Expression {
absent: Box::new(make_literal("/*")),
exp: Box::new(Expr::Repeat {
child: Box::new(Expr::Any {
newline: true,
crlf: false
}),
lo: 0,
hi: usize::MAX,
greedy: true
})
})
.is_leaf_node()
);
assert!(!Expr::Absent(Absent::Stopper(Box::new(make_literal("/*")))).is_leaf_node());
}
#[test]
fn test_children_iter_empty() {
let expr = Expr::Empty;
let mut iter = expr.children_iter();
assert!(iter.next().is_none());
let expr = make_literal("test");
let mut iter = expr.children_iter();
assert!(iter.next().is_none());
}
#[test]
fn test_children_iter_single() {
let child = make_literal("a");
let expr = make_group(child.clone());
let children: Vec<_> = expr.children_iter().collect();
assert_eq!(children.len(), 1);
let expr = Expr::Repeat {
child: Box::new(child.clone()),
lo: 0,
hi: 1,
greedy: true,
};
let children: Vec<_> = expr.children_iter().collect();
assert_eq!(children.len(), 1);
}
#[test]
fn test_children_iter_vec() {
let children_vec = vec![make_literal("a"), make_literal("b"), make_literal("c")];
let expr = Expr::Concat(children_vec.clone());
let children: Vec<_> = expr.children_iter().collect();
assert_eq!(children.len(), 3);
let expr = Expr::Alt(children_vec);
let children: Vec<_> = expr.children_iter().collect();
assert_eq!(children.len(), 3);
}
#[test]
fn test_children_iter_triple() {
let expr = Expr::Conditional {
condition: Box::new(Expr::BackrefExistsCondition {
group: 1,
relative_recursion_level: None,
}),
true_branch: Box::new(make_literal("a")),
false_branch: Box::new(make_literal("b")),
};
let children: Vec<_> = expr.children_iter().collect();
assert_eq!(children.len(), 3);
let expr = Expr::Absent(Absent::Expression {
absent: Box::new(make_literal("/*")),
exp: Box::new(Expr::Repeat {
child: Box::new(Expr::Any {
newline: true,
crlf: false,
}),
lo: 0,
hi: usize::MAX,
greedy: true,
}),
});
let children: Vec<_> = expr.children_iter().collect();
assert_eq!(children.len(), 2);
}
#[test]
fn find_input_raw_honors_anchored_flag_for_wrapped_regex() {
let regex = Regex::new("abc").unwrap();
let input = RegexInput::new("zabc");
assert_eq!(
Some((1, 4)),
regex
.find_input(input)
.unwrap()
.map(|m| (m.start(), m.end()))
);
let anchored_at_start = RegexInput::new("zabc").anchored(true);
assert!(regex.find_input(anchored_at_start).unwrap().is_none());
let anchored_at_match = RegexInput::new("zabc").from_pos(1).anchored(true);
assert_eq!(
regex
.find_input(anchored_at_match)
.unwrap()
.map(|m| (m.start(), m.end())),
Some((1, 4))
);
}
}