use alloc::borrow::Cow;
use alloc::boxed::Box;
use alloc::vec::Vec;
use regex_automata::util::captures::{Captures as RaCaptures, GroupInfo};
use regex_automata::util::look::{Look, LookMatcher, LookSet};
use regex_automata::util::prefilter::Prefilter;
use regex_automata::util::primitives::NonMaxUsize;
use regex_automata::{MatchKind, PatternID, Span};
use regex_syntax::hir::{self, Hir, HirKind, literal};
use crate::vm::char_at;
mod class;
use class::{
ByteRanges, Class, Stops, WORD_BYTE, bit128, bytes_in, char_boundary, class_units, has_byte,
};
#[derive(Clone, Debug)]
pub(crate) struct Plan {
steps: Box<[Step]>,
leading: Box<[Look]>,
trailing: Box<[Look]>,
edges: Option<Box<Edges>>,
checks_start: bool,
checks_end: bool,
candidates: Candidates,
required: Option<Box<memchr::memmem::Finder<'static>>>,
start_only: bool,
whole: Whole,
skip_first_run: bool,
first: usize,
look_skip: bool,
window: bool,
decisive: usize,
conditional: Box<[usize]>,
branching: bool,
look_matcher: LookMatcher,
group_info: GroupInfo,
nfa_units: usize,
run_bytes: Option<Box<[bool; 256]>>,
}
#[derive(Clone, Debug)]
enum Step {
Literal(Box<[u8]>),
Run(Run),
Save(usize),
Alt(Box<Alt>),
Group(Box<Group>),
}
#[derive(Clone, Debug)]
struct Run {
class: Class,
min: usize,
max: usize,
lazy: bool,
shortest: bool,
stops: Option<Stops>,
}
#[derive(Clone, Debug)]
struct Alt {
branches: Box<[Box<[Step]>]>,
firsts: Box<[Class]>,
by_byte: Option<Box<[u8; 256]>>,
first: Class,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Whole {
Attempts,
Empty,
Literals,
Run,
}
const NO_BRANCH: u8 = u8::MAX;
#[derive(Clone, Debug)]
struct Group {
body: Box<[Step]>,
min: usize,
max: usize,
greedy: bool,
first: Class,
tail: bool,
snapshot: Box<[usize]>,
completion: Box<[usize]>,
}
pub(crate) const NFA_UNIT_BUDGET: usize = 8192;
const RESCAN_BOUND: usize = 64;
const SNAPSHOT: usize = 16;
#[derive(Clone, Debug)]
enum Candidates {
Literal(Box<memchr::memmem::Finder<'static>>),
Prefilter(Prefilter),
Bytes(Stops),
Ranges(ByteRanges, Class),
Offset(Box<memchr::memmem::Finder<'static>>, usize),
Inner(
Box<memchr::memmem::Finder<'static>>,
usize,
usize,
Box<Candidates>,
),
Lines(bool, [u64; 4]),
Class(Class),
Behind(Prefilter, usize),
Suffix(Box<memchr::memmem::Finder<'static>>, Class),
}
#[derive(Clone, Debug)]
pub(crate) struct Edge {
negated: bool,
alternatives: Box<[Box<[Class]>]>,
}
const EDGE_CHARS: usize = 256;
#[derive(Clone, Debug, Default)]
pub(crate) struct Edges {
pub(crate) behind: Vec<Edge>,
pub(crate) ahead: Vec<Edge>,
pub(crate) prefilter: Option<(Vec<Vec<u8>>, Prefilter)>,
}
impl Edge {
pub(crate) fn new(body: &Hir, negated: bool) -> Option<Edge> {
let branches = match body.kind() {
HirKind::Alternation(subs) => subs.iter().collect(),
_ => Vec::from([body]),
};
let mut total = 0;
let alternatives = branches
.into_iter()
.map(|branch| {
let mut nodes = Vec::new();
let mut names = Vec::new();
flatten(branch, &mut nodes, &mut names)?;
let mut classes = Vec::new();
for node in nodes {
match node {
Node::Literal(bytes) => {
let mut at = 0;
while at < bytes.len() {
let len = char_at(&bytes, at).map_or(1, |(_, len)| len);
classes.push(Class::from_literal(&bytes[at..at + len])?);
at += len;
}
}
Node::Run(run) if run.min == run.max && run.min <= EDGE_CHARS => {
classes.extend(core::iter::repeat_n(run.class, run.min));
}
_ => return None,
}
}
total += classes.len();
Some(classes.into_boxed_slice())
})
.collect::<Option<Vec<_>>>()?;
(total <= EDGE_CHARS).then(|| Edge {
negated,
alternatives: alternatives.into_boxed_slice(),
})
}
#[inline]
fn behind(&self, haystack: &[u8], at: usize) -> bool {
let found = self.alternatives.iter().any(|alternative| {
let mut pos = at;
alternative.iter().rev().all(|class| {
class
.len_before(haystack, pos)
.map(|len| pos -= len)
.is_some()
})
});
found != self.negated
}
#[inline]
fn ahead(&self, haystack: &[u8], at: usize) -> bool {
let found = self.alternatives.iter().any(|alternative| {
let mut pos = at;
alternative.iter().all(|class| {
class
.match_len(haystack, pos, haystack.len())
.map(|len| pos += len)
.is_some()
})
});
found != self.negated
}
fn last_classes(&self) -> Option<Class> {
if self.negated {
return None;
}
let mut lasts = self
.alternatives
.iter()
.map(|alternative| alternative.last());
let first = lasts.next()??.clone();
lasts.try_fold(first, |union, last| union.union(last?))
}
fn literals(&self) -> Option<(Vec<Vec<u8>>, usize)> {
if self.negated {
return None;
}
let literals = self
.alternatives
.iter()
.map(|alternative| {
alternative
.iter()
.try_fold(Vec::new(), |mut literal, class| {
literal.extend(class.single()?);
Some(literal)
})
})
.collect::<Option<Vec<_>>>()?;
let len = literals.first()?.len();
(len > 0 && literals.iter().all(|literal| literal.len() == len)).then_some((literals, len))
}
}
pub(crate) fn nfa_bound(hir: &Hir) -> usize {
let own = match hir.kind() {
HirKind::Empty | HirKind::Look(_) | HirKind::Concat(_) | HirKind::Alternation(_) => 1,
HirKind::Literal(hir::Literal(bytes)) => bytes.len(),
HirKind::Class(class) => class_units(class),
HirKind::Capture(_) => 2,
HirKind::Repetition(repetition) => {
let copies = repetition.max.unwrap_or(repetition.min).max(1) as usize;
return nfa_bound(&repetition.sub)
.saturating_add(1)
.saturating_mul(copies);
}
};
hir.kind()
.subs()
.iter()
.map(nfa_bound)
.fold(own, usize::saturating_add)
}
enum Node {
Look(Look),
Literal(Vec<u8>),
Run(Run),
Save(usize),
Alt(Vec<Vec<Node>>),
Group {
body: Vec<Node>,
min: usize,
max: usize,
greedy: bool,
},
}
impl Run {
fn new(class: Class, min: usize, max: usize, greedy: bool) -> Run {
let stops = if max == usize::MAX {
class.stops()
} else {
None
};
Run {
class,
min,
max,
lazy: !greedy,
shortest: min == max,
stops,
}
}
}
impl Step {
fn from_node(node: Node) -> Option<Step> {
Some(match node {
Node::Look(_) => return None,
Node::Literal(bytes) => Step::Literal(bytes.into_boxed_slice()),
Node::Run(run) => Step::Run(run),
Node::Save(slot) => Step::Save(slot),
Node::Alt(branches) => {
let branches = branches
.into_iter()
.map(|branch| Some(Step::sequence(branch)?.into_boxed_slice()))
.collect::<Option<Vec<_>>>()?;
Step::Alt(Box::new(Alt::new(branches.into_boxed_slice())?))
}
Node::Group {
body,
min,
max,
greedy,
} => {
let body = Step::sequence(body)?;
let (Some(first), false) = starts(&body)? else {
return None;
};
Step::Group(Box::new(Group {
body: body.into_boxed_slice(),
min,
max,
greedy,
first,
tail: false,
snapshot: Box::new([]),
completion: Box::new([]),
}))
}
})
}
fn sequence(nodes: Vec<Node>) -> Option<Vec<Step>> {
nodes.into_iter().map(Step::from_node).collect()
}
fn first(&self) -> Option<Cow<'_, Class>> {
match self {
Step::Literal(bytes) => {
let len = char_at(bytes, 0).map_or(1, |(_, len)| len);
Class::from_literal(&bytes[..len]).map(Cow::Owned)
}
Step::Run(run) => Some(Cow::Borrowed(&run.class)),
Step::Save(_) => None,
Step::Alt(alt) => Some(Cow::Borrowed(&alt.first)),
Step::Group(group) => Some(Cow::Borrowed(&group.first)),
}
}
fn consumes(&self) -> bool {
match self {
Step::Literal(_) | Step::Alt(_) => true,
Step::Run(run) => run.min > 0,
Step::Save(_) => false,
Step::Group(group) => group.min > 0,
}
}
}
fn starts(steps: &[Step]) -> Option<(Option<Class>, bool)> {
let mut first: Option<Class> = None;
for step in steps {
if let Some(class) = step.first() {
first = Some(match first {
Some(first) => first.union(&class)?,
None => class.into_owned(),
});
}
if step.consumes() {
return Some((first, false));
}
}
Some((first, true))
}
fn saves(steps: &[Step], slots: &mut Vec<usize>) {
for step in steps {
match step {
Step::Save(slot) => slots.push(*slot),
Step::Alt(alt) => {
for branch in &*alt.branches {
saves(branch, slots);
}
}
Step::Group(group) => saves(&group.body, slots),
Step::Literal(_) | Step::Run(_) => {}
}
}
}
impl Alt {
fn new(branches: Box<[Box<[Step]>]>) -> Option<Alt> {
let firsts = branches
.iter()
.map(|branch| match starts(branch)? {
(Some(first), false) => Some(first),
_ => None,
})
.collect::<Option<Vec<_>>>()?;
let mut table = Box::new([NO_BRANCH; 256]);
let mut by_byte = branches.len() < usize::from(NO_BRANCH);
for (index, first) in firsts.iter().enumerate() {
for b in bytes_in(first.first_bytes()) {
by_byte &= table[usize::from(b)] == NO_BRANCH;
table[usize::from(b)] = index as u8;
}
}
if !by_byte {
if firsts.len() > 32 {
return None;
}
for (index, first) in firsts.iter().enumerate() {
if firsts[index + 1..]
.iter()
.any(|other| other.overlaps(first))
{
return None;
}
}
}
let (head, rest) = firsts.split_first()?;
let first = rest
.iter()
.try_fold(head.clone(), |first, class| first.union(class))?;
Some(Alt {
branches,
firsts: firsts.into_boxed_slice(),
by_byte: by_byte.then_some(table),
first,
})
}
#[inline]
fn branch(&self, haystack: &[u8], at: usize, end: usize) -> Option<&[Step]> {
let index = match &self.by_byte {
Some(table) => match table[usize::from(*haystack[..end].get(at)?)] {
NO_BRANCH => return None,
index => usize::from(index),
},
None => self
.firsts
.iter()
.position(|first| first.match_len(haystack, at, end).is_some())?,
};
Some(&self.branches[index])
}
}
fn look(look: hir::Look) -> Look {
match look {
hir::Look::Start => Look::Start,
hir::Look::End => Look::End,
hir::Look::StartLF => Look::StartLF,
hir::Look::EndLF => Look::EndLF,
hir::Look::StartCRLF => Look::StartCRLF,
hir::Look::EndCRLF => Look::EndCRLF,
hir::Look::WordAscii => Look::WordAscii,
hir::Look::WordAsciiNegate => Look::WordAsciiNegate,
hir::Look::WordUnicode => Look::WordUnicode,
hir::Look::WordUnicodeNegate => Look::WordUnicodeNegate,
hir::Look::WordStartAscii => Look::WordStartAscii,
hir::Look::WordEndAscii => Look::WordEndAscii,
hir::Look::WordStartUnicode => Look::WordStartUnicode,
hir::Look::WordEndUnicode => Look::WordEndUnicode,
hir::Look::WordStartHalfAscii => Look::WordStartHalfAscii,
hir::Look::WordEndHalfAscii => Look::WordEndHalfAscii,
hir::Look::WordStartHalfUnicode => Look::WordStartHalfUnicode,
hir::Look::WordEndHalfUnicode => Look::WordEndHalfUnicode,
}
}
fn ends_run(look: Look, run: &Run) -> bool {
match look {
Look::End => true,
Look::EndLF => !run.class.has_ascii(b'\n'),
Look::EndCRLF => !run.class.has_ascii(b'\n') && !run.class.has_ascii(b'\r'),
Look::WordAscii
| Look::WordStartAscii
| Look::WordEndAscii
| Look::WordStartHalfAscii
| Look::WordEndHalfAscii => run.min > 0 && run.class.is_word(false),
Look::WordUnicode
| Look::WordStartUnicode
| Look::WordEndUnicode
| Look::WordStartHalfUnicode
| Look::WordEndHalfUnicode => run.min > 0 && run.class.is_word(true),
_ => false,
}
}
fn flatten(
hir: &Hir,
nodes: &mut Vec<Node>,
names: &mut Vec<(usize, Option<Box<str>>)>,
) -> Option<()> {
match hir.kind() {
HirKind::Empty => {}
HirKind::Literal(hir::Literal(bytes)) => match nodes.last_mut() {
Some(Node::Literal(previous)) => previous.extend_from_slice(bytes),
_ => nodes.push(Node::Literal(bytes.to_vec())),
},
HirKind::Class(class) => {
nodes.push(Node::Run(Run::new(Class::from_hir(class), 1, 1, true)));
}
HirKind::Look(hir_look) => nodes.push(Node::Look(look(*hir_look))),
HirKind::Repetition(repetition) => {
let max = repetition.max.map_or(usize::MAX, |max| max as usize);
if max == 0 {
return None;
}
let (min, greedy) = (repetition.min as usize, repetition.greedy);
let class = match repetition.sub.kind() {
HirKind::Class(class) => Some(Class::from_hir(class)),
HirKind::Literal(hir::Literal(bytes)) => Class::from_literal(bytes),
_ => None,
};
match class {
Some(class) => nodes.push(Node::Run(Run::new(class, min, max, greedy))),
None => {
let mut body = Vec::new();
flatten(&repetition.sub, &mut body, names)?;
nodes.push(Node::Group {
body,
min,
max,
greedy,
});
}
}
}
HirKind::Capture(capture) => {
let index = capture.index as usize;
names.push((index, capture.name.clone()));
nodes.push(Node::Save(2 * index));
flatten(&capture.sub, nodes, names)?;
nodes.push(Node::Save(2 * index + 1));
}
HirKind::Concat(subs) => {
for sub in subs {
flatten(sub, nodes, names)?;
}
}
HirKind::Alternation(subs) => {
let mut branches = Vec::with_capacity(subs.len());
for sub in subs {
let mut branch = Vec::new();
flatten(sub, &mut branch, names)?;
branches.push(branch);
}
nodes.push(Node::Alt(branches));
}
}
Some(())
}
#[derive(Clone)]
struct Follow<'a> {
next: Option<Cow<'a, Class>>,
end: Option<bool>,
completion: Option<Vec<usize>>,
later: Option<Vec<usize>>,
}
impl<'a> Follow<'a> {
fn overlaps(&self, class: &Class) -> bool {
self.next.as_ref().is_some_and(|next| next.overlaps(class))
}
fn add(&mut self, class: Cow<'a, Class>) -> Option<()> {
self.next = Some(match self.next.take() {
Some(next) => Cow::Owned(next.union(&class)?),
None => class,
});
Some(())
}
fn into_owned(self) -> Follow<'static> {
Follow {
next: self.next.map(|next| Cow::Owned(next.into_owned())),
end: self.end,
completion: self.completion,
later: self.later,
}
}
}
fn extend(list: &mut Option<Vec<usize>>, slots: impl IntoIterator<Item = usize>) {
if let Some(vec) = list {
vec.extend(slots);
if vec.len() > SNAPSHOT {
*list = None;
}
}
}
fn admit<'a>(
steps: &'a mut [Step],
outer: &Follow<'a>,
trailing: &[Look],
want: Option<usize>,
) -> Option<Option<Follow<'static>>> {
let mut wanted = None;
let mut follow = outer.clone();
let mut rest = steps;
while let Some((step, before)) = rest.split_last_mut() {
if want == Some(before.len()) {
wanted = Some(follow.clone().into_owned());
}
admit_step(step, &follow, trailing)?;
let step: &'a Step = step;
rest = before;
match step {
Step::Save(slot) => {
extend(&mut follow.completion, [*slot]);
continue;
}
Step::Alt(_) | Step::Group(_) => {
let mut nested = Vec::new();
saves(core::slice::from_ref(step), &mut nested);
extend(&mut follow.later, nested);
}
Step::Literal(_) | Step::Run(_) => {}
}
let first = step.first()?;
if step.consumes() {
follow = Follow {
next: Some(first),
end: Some(false),
completion: Some(Vec::new()),
later: Some(Vec::new()),
};
} else {
follow.add(first)?;
}
}
Some(wanted)
}
fn admit_step(step: &mut Step, follow: &Follow<'_>, trailing: &[Look]) -> Option<()> {
match step {
Step::Literal(_) | Step::Save(_) => {}
Step::Run(run) => {
if run.min != run.max {
if follow.overlaps(&run.class) {
return None;
}
match follow.end {
Some(true) => {
if !trailing.is_empty() && !trailing.iter().any(|&look| ends_run(look, run))
{
return None;
}
run.shortest = run.lazy && trailing.is_empty();
}
None if run.lazy || !trailing.is_empty() => return None,
_ => {}
}
}
}
Step::Alt(alt) => {
for branch in alt.branches.iter_mut() {
admit(branch, follow, trailing, None)?;
}
}
Step::Group(group) => {
let choice = group.min != group.max;
if choice && follow.overlaps(&group.first) {
return None;
}
let mut inner = follow.clone();
if group.max > 1 {
inner.add(Cow::Borrowed(&group.first))?;
}
let mut nested = Vec::new();
saves(&group.body, &mut nested);
extend(&mut inner.later, nested);
inner.end = match follow.end {
Some(true) if group.min <= 1 => Some(true),
Some(false) => Some(false),
_ => None,
};
let later = inner.later.clone();
admit(&mut group.body, &inner, trailing, None)?;
if choice {
match follow.end {
Some(true) => {
if !group.greedy && !trailing.is_empty() {
return None;
}
group.tail = true;
group.snapshot = later?.into_boxed_slice();
group.completion = follow.completion.clone()?.into_boxed_slice();
}
None => return None,
Some(false) => {}
}
}
}
}
Some(())
}
#[derive(Clone, Copy)]
struct Exposure {
add: usize,
floor: usize,
limit: usize,
}
impl Exposure {
const NONE: Exposure = Exposure {
add: 0,
floor: 0,
limit: usize::MAX,
};
fn read(add: usize, fails_after: Option<usize>) -> Option<Exposure> {
let limit = match fails_after {
Some(read) => RESCAN_BOUND.checked_sub(read)?,
None => usize::MAX,
};
Some(Exposure {
add,
floor: 0,
limit,
})
}
fn then(self, next: Exposure) -> Option<Exposure> {
let limit = if next.limit == usize::MAX {
self.limit
} else if self.floor > next.limit {
return None;
} else {
self.limit.min(next.limit.checked_sub(self.add)?)
};
Some(Exposure {
add: self.add.saturating_add(next.add),
floor: self.floor.saturating_add(next.add).max(next.floor),
limit,
})
}
fn or(self, other: Exposure) -> Exposure {
Exposure {
add: self.add.max(other.add),
floor: self.floor.max(other.floor),
limit: self.limit.min(other.limit),
}
}
fn times(self, count: usize) -> Option<Exposure> {
let Some(more) = count.checked_sub(1) else {
return Some(Exposure::NONE);
};
let limit = if self.limit == usize::MAX {
usize::MAX
} else {
if more > 0 && self.floor.saturating_add(self.add.saturating_mul(more - 1)) > self.limit
{
return None;
}
self.limit.checked_sub(self.add.saturating_mul(more))?
};
Some(Exposure {
add: self.add.saturating_mul(count),
floor: self.floor.saturating_add(self.add.saturating_mul(more)),
limit,
})
}
fn repeated(self) -> Option<Exposure> {
if self.add == 0 {
return self.times(2);
}
Some(Exposure {
add: usize::MAX,
floor: usize::MAX,
limit: usize::MAX,
})
}
}
struct Rescan<'a> {
first: &'a Class,
trailing: bool,
skip: Option<usize>,
confirmed: Option<usize>,
before: Option<Class>,
}
impl Rescan<'_> {
fn sequence(&self, steps: &[Step], top: bool) -> Option<Exposure> {
steps
.iter()
.enumerate()
.try_fold(Exposure::NONE, |exposure, (index, step)| {
exposure.then(self.step(step, top.then_some(index))?)
})
}
fn step(&self, step: &Step, index: Option<usize>) -> Option<Exposure> {
match step {
Step::Save(_) => Some(Exposure::NONE),
Step::Literal(bytes) => {
let held = (0..bytes.len())
.any(|at| self.first.match_len(bytes, at, bytes.len()).is_some());
let held = if held { bytes.len() } else { 0 };
let fails = index.is_none() || index != self.confirmed;
Exposure::read(held, fails.then_some(held))
}
Step::Run(run) => {
let held = run.class.overlaps(self.first)
&& self
.before
.as_ref()
.is_none_or(|before| before.overlaps(&run.class));
let width = if held { run.class.max_len() } else { 0 };
let fails_after = (run.min > 0).then(|| run.min.saturating_mul(width));
let add = if run.max != usize::MAX {
run.max.saturating_mul(width)
} else if !held || index.is_some() && index == self.skip {
0
} else {
usize::MAX
};
Exposure::read(add, fails_after)
}
Step::Alt(alt) => {
let mut branches: Option<Exposure> = None;
for branch in &*alt.branches {
let exposure = self.sequence(branch, false)?;
branches = Some(branches.map_or(exposure, |other| other.or(exposure)));
}
Exposure::read(0, Some(0))?.then(branches?)
}
Step::Group(group) => {
let body = self.sequence(&group.body, false)?;
let further = if group.max == group.min {
Exposure::NONE
} else if group.tail && !self.trailing {
Exposure {
add: 0,
floor: body.add.max(body.floor),
limit: usize::MAX,
}
} else if group.max == usize::MAX {
body.repeated()?
} else {
body.times(group.max - group.min)?
};
body.times(group.min)?.then(further)
}
}
}
}
fn suffix(steps: &[Step], first: usize, unasserted: bool) -> Option<(Box<[u8]>, Class)> {
let Step::Run(run) = &steps[first] else {
return None;
};
if !unasserted || run.max != usize::MAX || run.min == 0 {
return None;
}
match steps[first + 1..]
.iter()
.find(|step| !matches!(step, Step::Save(_)))?
{
step @ Step::Literal(bytes) if !step.first()?.overlaps(&run.class) => {
Some((bytes.clone(), run.class.clone()))
}
_ => None,
}
}
fn may_be_exact(hir: &Hir) -> bool {
let properties = hir.properties();
properties.maximum_len().is_some()
&& properties.minimum_len().is_some_and(|len| len > 0)
&& properties.explicit_captures_len() == 0
&& properties.look_set().is_empty()
}
fn prefixes(hir: &Hir) -> literal::Seq {
let mut extractor = literal::Extractor::new();
extractor.kind(literal::ExtractKind::Prefix);
let mut prefixes = extractor.extract(hir);
prefixes.optimize_for_prefix_by_preference();
prefixes
}
impl Plan {
pub(crate) fn new(hir: &Hir, prefilter: bool) -> Option<Plan> {
Plan::with_edges(hir, prefilter, &Edges::default())
}
pub(crate) fn with_edges(hir: &Hir, prefilter: bool, edges: &Edges) -> Option<Plan> {
if hir.properties().look_set().contains_word_unicode() {
LookSet::singleton(Look::WordUnicode).available().ok()?;
}
let mut extracted = None;
if prefilter && edges.behind.is_empty() && edges.ahead.is_empty() && may_be_exact(hir) {
let prefixes = match hir.kind() {
HirKind::Literal(hir::Literal(bytes)) => literal::Seq::new([bytes]),
_ => prefixes(hir),
};
if let Some(plan) = Plan::literals(hir, &prefixes) {
return Some(plan);
}
extracted = Some(prefixes);
}
let mut nodes = Vec::new();
let mut names = Vec::new();
flatten(hir, &mut nodes, &mut names)?;
let consuming = |node: &Node| !matches!(node, Node::Look(_) | Node::Save(_));
let first_node = nodes.iter().position(consuming)?;
let last_node = nodes.iter().rposition(consuming)?;
let mut leading = Vec::new();
let mut trailing = Vec::new();
let mut steps = Vec::new();
for (index, node) in nodes.into_iter().enumerate() {
match node {
Node::Look(look) if index < first_node => leading.push(look),
Node::Look(look) if index > last_node => trailing.push(look),
node => steps.push(Step::from_node(node)?),
}
}
let start_only = leading.contains(&Look::Start);
if trailing.contains(&Look::End) && !start_only {
return None;
}
let first = steps
.iter()
.position(|step| !matches!(step, Step::Save(_)))?;
let (first_class, nullable) = starts(&steps)?;
let first_class = first_class?;
let edged = !edges.behind.is_empty() || !edges.ahead.is_empty();
if nullable && (!leading.is_empty() || !trailing.is_empty() || edged) {
return None;
}
let mut outer = Follow {
next: None,
end: Some(true),
completion: Some(Vec::new()),
later: Some(Vec::new()),
};
for edge in edges.ahead.iter().filter(|edge| !edge.negated) {
if edge
.alternatives
.iter()
.any(|alternative| alternative.is_empty())
{
continue;
}
outer.end = Some(false);
for alternative in &*edge.alternatives {
outer.add(Cow::Borrowed(&alternative[0]))?;
}
}
let first_follow = admit(&mut steps, &outer, &trailing, Some(first))??;
if edges.ahead.iter().any(|edge| edge.negated) {
let last = steps
.iter()
.rposition(|step| !matches!(step, Step::Save(_)))?;
match &steps[last] {
Step::Literal(_) => {}
Step::Run(run) if run.min == run.max => {}
_ => return None,
}
}
let checks_end = !trailing.is_empty() || !edges.ahead.is_empty();
let decisive = if !checks_end {
steps
.iter()
.rposition(Step::consumes)
.map_or(0, |index| index + 1)
} else {
steps.len()
};
let required = steps[first + 1..]
.iter()
.filter_map(|step| match step {
Step::Literal(bytes) => Some(bytes),
_ => None,
})
.max_by_key(|bytes| bytes.len())
.map(|bytes| Box::new(memchr::memmem::Finder::new(bytes).into_owned()));
let mut offset = 0;
let mut fixed = true;
let mut runs: Vec<&Class> = Vec::new();
let mut at_offset: Option<(usize, &[u8])> = None;
let mut inner: Option<(usize, usize, &[u8])> = None;
for (index, step) in steps.iter().enumerate().skip(first) {
match step {
Step::Literal(bytes) if index != first => {
if fixed && at_offset.is_none_or(|(_, best)| bytes.len() > best.len()) {
at_offset = Some((offset, bytes));
}
if !fixed
&& offset <= RESCAN_BOUND
&& runs
.iter()
.all(|class| class.match_len(bytes, 0, bytes.len()).is_none())
&& inner.is_none_or(|(.., best)| bytes.len() > best.len())
{
inner = Some((index, offset, bytes));
}
offset += bytes.len();
}
Step::Literal(bytes) => offset += bytes.len(),
Step::Run(run) if run.min == run.max => {
fixed &= run.class.max_len() == 1;
offset += run.min;
runs.push(&run.class);
}
Step::Save(_) => {}
_ => break,
}
}
let candidates = match (&steps[first], at_offset) {
(Step::Run(_), Some((offset, bytes))) => Candidates::Offset(
Box::new(memchr::memmem::Finder::new(bytes).into_owned()),
offset,
),
(Step::Literal(bytes), _) => {
Candidates::Literal(Box::new(memchr::memmem::Finder::new(bytes).into_owned()))
}
(step, _) => {
let short = match step {
Step::Run(run) => run.min == run.max,
_ => true,
};
let prefilter = (prefilter && short && !nullable)
.then(|| extracted.unwrap_or_else(|| prefixes(hir)))
.as_ref()
.and_then(literal::Seq::literals)
.and_then(|literals| Prefilter::new(MatchKind::LeftmostFirst, literals));
let first_bytes = first_class.first_bytes();
let stops = Stops::of(&mut bytes_in(first_bytes));
match (prefilter, stops) {
(Some(prefilter), _) if prefilter.is_fast() => Candidates::Prefilter(prefilter),
(_, Some(stops)) => Candidates::Bytes(stops),
(prefilter, None) => match (ByteRanges::of(&first_bytes), prefilter) {
(Some(ranges), _) => Candidates::Ranges(ranges, first_class.clone()),
(None, Some(prefilter)) if !matches!(step, Step::Run(_)) => {
Candidates::Prefilter(prefilter)
}
(None, _) => Candidates::Class(first_class.clone()),
},
}
}
};
let skip_first_run = matches!(&steps[first], Step::Run(run) if run.max == usize::MAX);
let candidates = match candidates {
candidates @ (Candidates::Literal(_) | Candidates::Offset(..)) => candidates,
Candidates::Prefilter(prefilter) if prefilter.is_fast() => {
Candidates::Prefilter(prefilter)
}
weaker => match (
edges.behind.iter().find_map(Edge::literals),
suffix(&steps, first, leading.is_empty() && edges.behind.is_empty()),
) {
(Some((literals, len)), _) => edges
.prefilter
.as_ref()
.filter(|(built, _)| *built == literals)
.map(|(_, prefilter)| prefilter.clone())
.or_else(|| Prefilter::new(MatchKind::LeftmostFirst, &literals))
.map_or(weaker, |prefilter| Candidates::Behind(prefilter, len)),
(None, Some((literal, class))) => Candidates::Suffix(
Box::new(memchr::memmem::Finder::new(&literal).into_owned()),
class,
),
(None, None) => weaker,
},
};
let line_start = leading
.iter()
.any(|&look| matches!(look, Look::StartLF | Look::StartCRLF));
let candidates = match (candidates, inner) {
(Candidates::Ranges(..) | Candidates::Class(_), _) if line_start => {
Candidates::Lines(!leading.contains(&Look::StartLF), first_class.first_bytes())
}
(
scan @ (Candidates::Ranges(..) | Candidates::Class(_)),
Some((index, offset, bytes)),
) => Candidates::Inner(
Box::new(memchr::memmem::Finder::new(bytes).into_owned()),
index,
offset,
Box::new(scan),
),
(candidates, _) => candidates,
};
let look_skip = skip_first_run
&& leading.is_empty()
&& !edges.behind.is_empty()
&& match &steps[first] {
Step::Run(run) => edges.behind.iter().all(|edge| {
!edge.negated
&& edge.alternatives.iter().all(|alternative| {
alternative
.last()
.is_some_and(|class| !class.overlaps(&run.class))
})
}),
_ => false,
};
let rescan = Rescan {
first: &first_class,
trailing: checks_end,
skip: skip_first_run.then_some(first),
confirmed: matches!(candidates, Candidates::Literal(_)).then_some(first),
before: edges.behind.iter().find_map(Edge::last_classes),
};
if !start_only {
let exposure = rescan.sequence(&steps, true)?;
if checks_end {
exposure.then(Exposure::read(0, Some(0))?)?;
}
}
let window = !edged
&& !matches!(candidates, Candidates::Offset(..))
&& match &steps[first] {
Step::Run(run)
if run.max != usize::MAX
&& run.max > 2
&& run.min > 0
&& (run.min == run.max || !run.shortest) =>
{
let can_end = first_follow.end == Some(true);
(!can_end || !trailing.is_empty())
&& !first_follow.overlaps(&run.class)
&& (!can_end || trailing.iter().any(|&look| ends_run(look, run)))
}
_ => false,
};
let mut conditional = Vec::new();
let mut branching = false;
for step in &steps {
if matches!(step, Step::Alt(_) | Step::Group(_)) {
branching = true;
saves(core::slice::from_ref(step), &mut conditional);
}
}
let nfa_units = nfa_bound(hir);
let mut group_names = Vec::new();
group_names.resize(hir.properties().explicit_captures_len() + 1, None);
for (index, name) in names {
*group_names.get_mut(index)? = name;
}
let group_info = GroupInfo::new([group_names]).ok()?;
let checks_start = !leading.is_empty() || !edges.behind.is_empty();
let single_run = !checks_start
&& !checks_end
&& !start_only
&& matches!(&*steps, [Step::Run(run)] if run.max == usize::MAX && run.min > 0);
let run_bytes = match &*steps {
[Step::Run(run)]
if single_run && run.min == 1 && !run.shortest && run.stops.is_none() =>
{
Some(Box::new(core::array::from_fn(|b| {
run.class.has_single_byte(b as u8)
})))
}
_ => None,
};
Some(Plan {
steps: steps.into_boxed_slice(),
leading: leading.into_boxed_slice(),
trailing: trailing.into_boxed_slice(),
checks_start,
checks_end,
edges: edged.then(|| Box::new(edges.clone())),
candidates,
required,
start_only,
whole: if nullable {
Whole::Empty
} else if single_run {
Whole::Run
} else {
Whole::Attempts
},
skip_first_run,
look_skip,
first,
window,
decisive,
conditional: conditional.into_boxed_slice(),
branching,
look_matcher: LookMatcher::new(),
group_info,
nfa_units,
run_bytes,
})
}
fn literals(hir: &Hir, prefixes: &literal::Seq) -> Option<Plan> {
if !prefixes.is_exact() {
return None;
}
let prefilter = Prefilter::new(MatchKind::LeftmostFirst, prefixes.literals()?)?;
Some(Plan {
steps: Box::new([]),
leading: Box::new([]),
trailing: Box::new([]),
edges: None,
checks_start: false,
checks_end: false,
candidates: Candidates::Prefilter(prefilter),
required: None,
start_only: false,
whole: Whole::Literals,
skip_first_run: false,
first: 0,
look_skip: false,
window: false,
decisive: 0,
conditional: Box::new([]),
branching: false,
look_matcher: LookMatcher::new(),
group_info: GroupInfo::new([[None::<&str>]]).ok()?,
nfa_units: nfa_bound(hir),
run_bytes: None,
})
}
pub(crate) fn nfa_units(&self) -> usize {
self.nfa_units
}
pub(crate) fn branching(&self) -> bool {
self.branching
}
pub(crate) fn create_captures(&self) -> RaCaptures {
RaCaptures::all(self.group_info.clone())
}
pub(crate) fn captures_len(&self) -> usize {
self.group_info.group_len(PatternID::ZERO)
}
pub(crate) fn slot_len(&self) -> usize {
self.group_info.slot_len()
}
#[inline]
fn next_candidate(&self, input: &PlanInput<'_>, from: usize) -> Option<usize> {
let (haystack, end) = (input.haystack, input.end);
let found = match &self.candidates {
Candidates::Literal(finder) => finder.find(&haystack[from..end]),
Candidates::Prefilter(prefilter) => {
return prefilter
.find(haystack, Span { start: from, end })
.map(|span| span.start);
}
Candidates::Bytes(bytes) => bytes.find(&haystack[from..end]),
Candidates::Offset(finder, offset) => {
let begin = from + offset;
return haystack
.get(begin..end)
.and_then(|rest| finder.find(rest))
.map(|at| from + at);
}
Candidates::Inner(..) => return self.inner_candidate(input, from),
Candidates::Lines(..) => return self.line_candidate(input, from),
Candidates::Ranges(ranges, class) => {
return Plan::range_candidate(ranges, class, haystack, from, end);
}
Candidates::Class(class) => return Plan::class_candidate(class, haystack, from, end),
Candidates::Behind(prefilter, len) => {
let start = from.saturating_sub(*len);
return prefilter
.find(haystack, Span { start, end })
.map(|found| found.start + len);
}
Candidates::Suffix(finder, class) => {
if !input.utf8 && matches!(class, Class::Chars(_)) {
return Plan::find_class(class, haystack, from, end);
}
let mut at = from;
while let Some(offset) = finder.find(&haystack[at..end]) {
let suffix = at + offset;
let mut start = suffix;
while let Some(len) = class.len_before(haystack, start)
&& start - len >= from
{
start -= len;
}
if start < suffix {
return Some(start);
}
at = suffix + 1;
}
return None;
}
};
found.map(|offset| from + offset)
}
#[inline(never)]
fn inner_candidate(&self, input: &PlanInput<'_>, from: usize) -> Option<usize> {
let Candidates::Inner(finder, index, min, scan) = &self.candidates else {
unreachable!("only inner-literal candidates are searched here");
};
let (haystack, end) = (input.haystack, input.end);
if !input.utf8 {
return match &**scan {
Candidates::Ranges(ranges, class) => {
Plan::range_candidate(ranges, class, haystack, from, end)
}
Candidates::Class(class) => Plan::class_candidate(class, haystack, from, end),
_ => unreachable!("an inner literal replaces only a scan of each byte"),
};
}
let before = &self.steps[self.first..*index];
let mut at = from + min;
while let Some(offset) = haystack.get(at..end).and_then(|rest| finder.find(rest)) {
let found = at + offset;
if let Some(start) = Plan::start_before(before, haystack, found)
&& start >= from
{
return Some(start);
}
at = found + 1;
}
None
}
#[inline(never)]
fn line_candidate(&self, input: &PlanInput<'_>, from: usize) -> Option<usize> {
let Candidates::Lines(crlf, firsts) = &self.candidates else {
unreachable!("only line-start candidates are searched here");
};
let (haystack, end) = (input.haystack, input.end);
let ends_line = |b: u8| b == b'\n' || (*crlf && b == b'\r');
let mut at = from;
while at < end {
if (at == 0 || ends_line(haystack[at - 1])) && has_byte(firsts, haystack[at]) {
return Some(at);
}
if ends_line(haystack[at]) {
at += 1;
continue;
}
let rest = &haystack[at..end];
let found = if *crlf {
memchr::memchr2(b'\n', b'\r', rest)
} else {
memchr::memchr(b'\n', rest)
};
at += found? + 1;
}
None
}
#[inline]
fn start_before(steps: &[Step], haystack: &[u8], mut at: usize) -> Option<usize> {
for step in steps.iter().rev() {
match step {
Step::Literal(bytes) => {
let start = at.checked_sub(bytes.len())?;
if haystack[start..at] != **bytes {
return None;
}
at = start;
}
Step::Run(run) => {
for _ in 0..run.min {
#[cfg(all(test, feature = "std"))]
tests::SCANNED.with(|scanned| scanned.set(scanned.get() + 1));
at -= run.class.len_before(haystack, at)?;
}
}
Step::Save(_) => {}
Step::Alt(_) | Step::Group(_) => {
unreachable!("only fixed steps come before an inner literal")
}
}
}
Some(at)
}
#[inline(never)]
fn find_class(class: &Class, haystack: &[u8], from: usize, end: usize) -> Option<usize> {
Plan::class_candidate(class, haystack, from, end)
}
#[inline(always)]
fn range_candidate(
ranges: &ByteRanges,
class: &Class,
haystack: &[u8],
from: usize,
end: usize,
) -> Option<usize> {
let mut at = from;
while let Some(found) = ranges.find(haystack, at, end) {
if haystack[found] < 0x80 || class.match_len(haystack, found, end).is_some() {
return Some(found);
}
at = found + 1;
}
None
}
#[inline(always)]
fn class_candidate(class: &Class, haystack: &[u8], from: usize, end: usize) -> Option<usize> {
match class {
Class::Bytes(set) => haystack[from..end]
.iter()
.position(|&b| has_byte(set, b))
.map(|offset| from + offset),
Class::Chars(set) => {
let mut at = from;
while at < end {
let b = haystack[at];
if b < 0x80 {
if bit128(set.ascii, b) {
return Some(at);
}
} else if class.match_len(haystack, at, end).is_some() {
return Some(at);
}
at += 1;
}
None
}
}
}
#[inline(always)]
fn run_end(run: &Run, input: &PlanInput<'_>, pos: &mut usize, decided: bool) -> bool {
if run.max == 1 && run.min == 1 {
let Some(len) = run.class.match_len(input.haystack, *pos, input.end) else {
return false;
};
*pos += len;
return true;
}
let (stop, count) = if run.shortest || decided {
Plan::take(run, input.haystack, *pos, input.end, run.min)
} else {
Plan::scan(run, input.haystack, *pos, input.end, input.utf8)
};
*pos = stop;
count >= run.min
}
#[inline]
fn scan(run: &Run, haystack: &[u8], at: usize, end: usize, utf8: bool) -> (usize, usize) {
if let Some(stops) = run.stops
&& utf8
&& run.max == usize::MAX
&& run.min <= 1
&& char_boundary(haystack, at)
&& char_boundary(haystack, end)
{
let stop = stops
.find(&haystack[at..end])
.map_or(end, |offset| at + offset);
#[cfg(all(test, feature = "std"))]
tests::SCANNED.with(|scanned| scanned.set(scanned.get() + stop - at));
return (stop, usize::from(stop > at));
}
Plan::take(run, haystack, at, end, run.max)
}
#[inline]
fn take(run: &Run, haystack: &[u8], at: usize, end: usize, limit: usize) -> (usize, usize) {
let haystack = &haystack[..end];
let mut pos = at;
let mut count = 0;
match &run.class {
Class::Bytes(set) => {
while count < limit
&& let Some(&b) = haystack.get(pos)
&& has_byte(set, b)
{
pos += 1;
count += 1;
}
}
Class::Chars(set) => {
while count < limit
&& let Some(&b) = haystack.get(pos)
{
if b < 0x80 {
if !bit128(set.ascii, b) {
break;
}
pos += 1;
} else {
match set.non_ascii_len(haystack, pos, end) {
Some(len) => pos += len,
None => break,
}
}
count += 1;
}
}
}
#[cfg(all(test, feature = "std"))]
tests::SCANNED.with(|scanned| scanned.set(scanned.get() + pos - at));
(pos, count)
}
#[inline]
fn look_at(&self, look: Look, haystack: &[u8], at: usize) -> bool {
let before = if at == 0 { 0 } else { haystack[at - 1] };
let after = haystack.get(at).copied().unwrap_or(0);
let word = |b: u8| WORD_BYTE[usize::from(b)];
let (before, after) = match look {
Look::Start => return at == 0,
Look::End => return at == haystack.len(),
Look::StartLF => return at == 0 || before == b'\n',
Look::EndLF => return at == haystack.len() || after == b'\n',
Look::WordAscii
| Look::WordAsciiNegate
| Look::WordStartAscii
| Look::WordEndAscii
| Look::WordStartHalfAscii
| Look::WordEndHalfAscii => (word(before), word(after)),
Look::WordUnicode
| Look::WordUnicodeNegate
| Look::WordStartUnicode
| Look::WordEndUnicode
| Look::WordStartHalfUnicode
| Look::WordEndHalfUnicode => {
if (before | after) >= 0x80 {
return self.look_decoded(look, haystack, at);
}
(word(before), word(after))
}
Look::StartCRLF | Look::EndCRLF => return self.look_decoded(look, haystack, at),
};
match look {
Look::WordAscii | Look::WordUnicode => before != after,
Look::WordAsciiNegate | Look::WordUnicodeNegate => before == after,
Look::WordStartAscii | Look::WordStartUnicode => !before && after,
Look::WordEndAscii | Look::WordEndUnicode => before && !after,
Look::WordStartHalfAscii | Look::WordStartHalfUnicode => !before,
Look::WordEndHalfAscii | Look::WordEndHalfUnicode => !after,
_ => unreachable!("only word assertions reach here"),
}
}
#[cold]
#[inline(never)]
fn look_decoded(&self, look: Look, haystack: &[u8], at: usize) -> bool {
self.look_matcher.matches(look, haystack, at)
}
#[inline(always)]
fn trailing_hold(&self, haystack: &[u8], at: usize) -> bool {
!self.checks_end || self.end_holds(haystack, at)
}
#[inline]
fn end_holds(&self, haystack: &[u8], at: usize) -> bool {
self.trailing
.iter()
.all(|&look| self.look_at(look, haystack, at))
&& self
.edges
.as_ref()
.is_none_or(|edges| Plan::ahead_holds(edges, haystack, at))
}
#[inline]
fn start_holds(&self, haystack: &[u8], at: usize) -> bool {
self.leading
.iter()
.all(|&look| self.look_at(look, haystack, at))
&& self
.edges
.as_ref()
.is_none_or(|edges| Plan::behind_holds(edges, haystack, at))
}
#[inline(never)]
fn ahead_holds(edges: &Edges, haystack: &[u8], at: usize) -> bool {
edges.ahead.iter().all(|edge| edge.ahead(haystack, at))
}
#[inline(never)]
fn behind_holds(edges: &Edges, haystack: &[u8], at: usize) -> bool {
edges.behind.iter().all(|edge| edge.behind(haystack, at))
}
#[inline]
fn sequence<'p, S: Slots + ?Sized>(
&'p self,
steps: &'p [Step],
input: &PlanInput<'_>,
state: &mut State<'p, '_, S>,
earliest: bool,
) -> Result<(), Stop> {
let (haystack, end) = (input.haystack, input.end);
for step in steps {
match step {
Step::Literal(bytes) => {
if !literal_at(haystack, state.pos, end, bytes) {
return Err(Stop::Fail);
}
state.pos += bytes.len();
}
Step::Run(run) => {
if !Plan::run_end(run, input, &mut state.pos, false) {
return Err(Stop::Fail);
}
}
Step::Save(slot) => {
if let Some(slots) = state.slots.as_deref_mut() {
slots.set(*slot, state.pos);
}
}
Step::Alt(alt) => {
let branch = alt.branch(haystack, state.pos, end).ok_or(Stop::Fail)?;
self.sequence(branch, input, state, earliest)?;
}
Step::Group(group) => self.group(group, input, state, earliest, false)?,
}
}
Ok(())
}
fn group<'p, S: Slots + ?Sized>(
&'p self,
group: &'p Group,
input: &PlanInput<'_>,
state: &mut State<'p, '_, S>,
earliest: bool,
decided: bool,
) -> Result<(), Stop> {
let (haystack, end) = (input.haystack, input.end);
let limit = if decided { group.min } else { group.max };
let mut count = 0;
while count < limit {
if count >= group.min {
if group.tail {
if !group.greedy {
break;
}
let ends = self.trailing_hold(haystack, state.pos);
if ends && earliest {
return Err(Stop::Found(state.pos));
}
if group.first.match_len(haystack, state.pos, end).is_none() {
break;
}
if ends {
state.record(group);
}
} else if group.first.match_len(haystack, state.pos, end).is_none() {
break;
}
}
self.sequence(&group.body, input, state, earliest)?;
count += 1;
}
Ok(())
}
#[inline]
fn attempt<S: Slots + ?Sized>(
&self,
input: &PlanInput<'_>,
start: usize,
earliest: bool,
slots: Option<&mut S>,
) -> Result<usize, usize> {
if self.branching {
self.attempt_program::<true, S>(input, start, earliest, false, slots)
} else {
self.attempt_program::<false, S>(input, start, earliest, false, slots)
}
}
#[inline]
fn attempt_program<const BRANCHING: bool, S: Slots + ?Sized>(
&self,
input: &PlanInput<'_>,
start: usize,
earliest: bool,
confirmed: bool,
mut slots: Option<&mut S>,
) -> Result<usize, usize> {
let (haystack, end) = (input.haystack, input.end);
if self.checks_start && !self.start_holds(haystack, start) {
return Err(LOOK_MISS);
}
if let Some(slots) = slots.as_deref_mut() {
for &slot in &*self.conditional {
slots.clear(slot);
}
}
let steps = if earliest {
&self.steps[..self.decisive]
} else {
&self.steps[..]
};
let mut state = State {
pos: start,
slots,
accept: None,
saved: None,
};
let mut first_run_end = start;
let outcome = 'program: {
for (index, step) in steps.iter().enumerate() {
match step {
Step::Literal(bytes) => {
if !(confirmed && index == self.first)
&& !literal_at(haystack, state.pos, end, bytes)
{
break 'program Err(Stop::Fail);
}
state.pos += bytes.len();
}
Step::Run(run) => {
let decided =
earliest && index + 1 == self.decisive && self.trailing.is_empty();
let mut stop = state.pos;
let found = Plan::run_end(run, input, &mut stop, decided);
if index == self.first {
first_run_end = stop;
}
state.pos = stop;
if !found {
break 'program Err(Stop::Fail);
}
}
Step::Save(slot) => {
if let Some(slots) = state.slots.as_deref_mut() {
slots.set(*slot, state.pos);
}
}
Step::Group(group) if BRANCHING => {
let decided =
earliest && index + 1 == self.decisive && self.trailing.is_empty();
if let Err(stop) = self.group(group, input, &mut state, earliest, decided) {
break 'program Err(stop);
}
}
Step::Alt(alt) if BRANCHING => {
let Some(branch) = alt.branch(haystack, state.pos, end) else {
break 'program Err(Stop::Fail);
};
if let Err(stop) = self.sequence(branch, input, &mut state, earliest) {
break 'program Err(stop);
}
}
Step::Group(_) | Step::Alt(_) => {
unreachable!("a plan without alternatives or groups has none")
}
}
}
Ok(())
};
#[cfg(all(test, feature = "std"))]
tests::COVERED.with(|covered| covered.set(covered.get() + state.pos - start + 1));
match outcome {
Ok(()) if self.trailing_hold(haystack, state.pos) => Ok(state.pos),
Err(Stop::Found(at)) if BRANCHING => Ok(at),
_ if BRANCHING => state.fall_back().ok_or(first_run_end),
_ => Err(first_run_end),
}
}
fn window_attempt<S: Slots + ?Sized>(
&self,
input: &PlanInput<'_>,
candidate: usize,
earliest: bool,
mut slots: Option<&mut S>,
) -> Result<(usize, usize), usize> {
let Step::Run(run) = &self.steps[self.first] else {
unreachable!("a window plan starts with a run");
};
let (haystack, end) = (input.haystack, input.end);
let (run_end, total) = Plan::take(run, haystack, candidate, end, usize::MAX);
let resume = run_end.max(candidate + 1);
let mut start = candidate;
for _ in 0..total.saturating_sub(run.max) {
start += run.class.match_len(haystack, start, end).unwrap_or(1);
}
let mut left = total.min(run.max);
while left >= run.min {
match self.attempt(input, start, earliest, slots.as_deref_mut()) {
Ok(match_end) => return Ok((start, match_end)),
Err(LOOK_MISS) => {
start += run.class.match_len(haystack, start, end).unwrap_or(1);
left -= 1;
}
Err(_) => break,
}
}
Err(resume)
}
#[inline(always)]
pub(crate) fn find<S: Slots + ?Sized>(
&self,
input: &PlanInput<'_>,
mut slots: Option<&mut S>,
) -> Option<(usize, usize)> {
let found = self.search(input, false, slots.as_deref_mut())?;
if let Some(slots) = slots {
slots.set(0, found.0);
slots.set(1, found.1);
}
Some(found)
}
#[inline]
pub(crate) fn is_match(&self, input: &PlanInput<'_>) -> bool {
self.search::<[usize]>(input, true, None).is_some()
}
#[inline(always)]
fn search<S: Slots + ?Sized>(
&self,
input: &PlanInput<'_>,
earliest: bool,
slots: Option<&mut S>,
) -> Option<(usize, usize)> {
let start = input.start;
match self.whole {
Whole::Attempts => {}
Whole::Run => return self.search_run(input, earliest),
Whole::Empty | Whole::Literals => return self.search_whole(input, earliest, slots),
}
if input.anchored || self.start_only {
let found = self.attempt(input, start, earliest, slots);
return found.ok().map(|match_end| (start, match_end));
}
if let Some(required) = &self.required
&& required.find(&input.haystack[start..input.end]).is_none()
{
return None;
}
if self.window && !(input.utf8 && matches!(self.candidates, Candidates::Inner(..))) {
return self.search_windows(input, earliest, slots);
}
if self.branching {
self.search_candidates::<true, S>(input, earliest, slots)
} else {
self.search_candidates::<false, S>(input, earliest, slots)
}
}
#[inline(always)]
fn search_candidates<const BRANCHING: bool, S: Slots + ?Sized>(
&self,
input: &PlanInput<'_>,
earliest: bool,
mut slots: Option<&mut S>,
) -> Option<(usize, usize)> {
let confirmed = matches!(self.candidates, Candidates::Literal(_));
let mut from = input.start;
loop {
let candidate = self.next_candidate(input, from)?;
let attempt = self.attempt_program::<BRANCHING, S>(
input,
candidate,
earliest,
confirmed,
slots.as_deref_mut(),
);
let resume = match attempt {
Ok(match_end) => return Some((candidate, match_end)),
Err(failure) => self.resume_after(input, candidate, failure),
};
if resume >= input.end {
return None;
}
from = resume;
}
}
#[inline]
fn resume_after(&self, input: &PlanInput<'_>, candidate: usize, failure: usize) -> usize {
if failure != LOOK_MISS {
if self.skip_first_run {
return failure.max(candidate + 1);
}
} else if self.look_skip {
return self.past_first_run(input, candidate);
}
candidate + 1
}
#[cold]
#[inline(never)]
fn past_first_run(&self, input: &PlanInput<'_>, candidate: usize) -> usize {
let Step::Run(run) = &self.steps[self.first] else {
unreachable!("only a plan starting with a run skips past it");
};
let (run_end, _) = Plan::take(run, input.haystack, candidate, input.end, usize::MAX);
run_end.max(candidate + 1)
}
#[inline]
fn search_run(&self, input: &PlanInput<'_>, earliest: bool) -> Option<(usize, usize)> {
let Step::Run(run) = &self.steps[0] else {
unreachable!("a plan of one run has a run");
};
if input.anchored {
let mut end = input.start;
let found = Plan::run_end(run, input, &mut end, earliest);
#[cfg(all(test, feature = "std"))]
tests::cover(input.start, end);
return found.then_some((input.start, end));
}
if let Some(member) = &self.run_bytes
&& !earliest
{
return self.search_maximal_run(run, member, input);
}
let mut from = input.start;
loop {
let candidate = self.next_candidate(input, from)?;
let mut end = candidate;
let found = Plan::run_end(run, input, &mut end, earliest);
#[cfg(all(test, feature = "std"))]
tests::cover(candidate, end);
if found {
return Some((candidate, end));
}
from = end.max(candidate + 1);
if from >= input.end {
return None;
}
}
}
#[inline]
fn search_maximal_run(
&self,
run: &Run,
member: &[bool; 256],
input: &PlanInput<'_>,
) -> Option<(usize, usize)> {
let (haystack, end) = (input.haystack, input.end);
let is_member = |at: usize| at < end && member[usize::from(haystack[at])];
let mut from = input.start;
loop {
let start = if is_member(from) {
from
} else if is_member(from + 1) {
from + 1
} else {
self.next_candidate(input, from)?
};
let mut pos = start;
while pos < end {
let b = haystack[pos];
if member[usize::from(b)] {
pos += 1;
} else if b < 0x80 {
break;
} else {
match run.class.match_len(haystack, pos, end) {
Some(len) => pos += len,
None => break,
}
}
}
#[cfg(all(test, feature = "std"))]
{
tests::SCANNED.with(|scanned| scanned.set(scanned.get() + pos - start));
tests::cover(start, pos);
}
if pos > start {
return Some((start, pos));
}
from = start + 1;
if from >= end {
return None;
}
}
}
#[inline(never)]
fn search_whole<S: Slots + ?Sized>(
&self,
input: &PlanInput<'_>,
earliest: bool,
slots: Option<&mut S>,
) -> Option<(usize, usize)> {
if self.whole == Whole::Empty {
return self.search_empty(input, earliest, slots);
}
let Candidates::Prefilter(prefilter) = &self.candidates else {
unreachable!("a plan of literals searches with its prefilter");
};
let span = Span {
start: input.start,
end: input.end,
};
let found = if input.anchored {
prefilter
.prefix(input.haystack, span)
.filter(|found| found.end <= input.end)
} else {
prefilter.find(input.haystack, span)
};
found.map(|found| (found.start, found.end))
}
fn search_empty<S: Slots + ?Sized>(
&self,
input: &PlanInput<'_>,
earliest: bool,
mut slots: Option<&mut S>,
) -> Option<(usize, usize)> {
let mut start = input.start;
loop {
let end = self
.attempt(input, start, earliest, slots.as_deref_mut())
.ok()?;
if end > start || char_boundary(input.haystack, end) {
return Some((start, end));
}
if input.anchored || start >= input.end {
return None;
}
start += 1;
}
}
#[inline(never)]
fn search_windows<S: Slots + ?Sized>(
&self,
input: &PlanInput<'_>,
earliest: bool,
mut slots: Option<&mut S>,
) -> Option<(usize, usize)> {
let mut from = input.start;
loop {
let candidate = self.next_candidate(input, from)?;
match self.window_attempt(input, candidate, earliest, slots.as_deref_mut()) {
Ok(found) => return Some(found),
Err(resume) if resume >= input.end => return None,
Err(resume) => from = resume,
}
}
}
}
enum Stop {
Fail,
Found(usize),
}
struct Accept<'p> {
group: &'p Group,
at: usize,
}
struct State<'p, 's, S: Slots + ?Sized> {
pos: usize,
slots: Option<&'s mut S>,
accept: Option<Accept<'p>>,
saved: Option<[usize; SNAPSHOT]>,
}
impl<'p, S: Slots + ?Sized> State<'p, '_, S> {
#[inline]
fn record(&mut self, group: &'p Group) {
if let Some(slots) = self.slots.as_deref() {
let saved = self.saved.get_or_insert([usize::MAX; SNAPSHOT]);
for (value, &slot) in saved.iter_mut().zip(&*group.snapshot) {
*value = slots.get(slot).unwrap_or(usize::MAX);
}
}
self.accept = Some(Accept {
group,
at: self.pos,
});
}
fn fall_back(&mut self) -> Option<usize> {
let Accept { group, at } = self.accept.take()?;
if let Some(slots) = self.slots.as_deref_mut() {
if let Some(saved) = &self.saved {
for (&value, &slot) in saved.iter().zip(&*group.snapshot) {
match value {
usize::MAX => slots.clear(slot),
value => slots.set(slot, value),
}
}
}
for &slot in &*group.completion {
slots.set(slot, at);
}
}
Some(at)
}
}
const LOOK_MISS: usize = usize::MAX;
#[inline(always)]
fn literal_at(haystack: &[u8], at: usize, end: usize, bytes: &[u8]) -> bool {
match bytes {
[byte] => at < end && haystack[at] == *byte,
_ => haystack
.get(at..end)
.is_some_and(|rest| rest.starts_with(bytes)),
}
}
pub(crate) struct PlanInput<'h> {
pub(crate) haystack: &'h [u8],
pub(crate) start: usize,
pub(crate) end: usize,
pub(crate) anchored: bool,
pub(crate) utf8: bool,
}
pub(crate) trait Slots {
fn set(&mut self, slot: usize, at: usize);
fn get(&self, slot: usize) -> Option<usize>;
fn clear(&mut self, slot: usize);
}
impl Slots for [Option<NonMaxUsize>] {
fn set(&mut self, slot: usize, at: usize) {
self[slot] = NonMaxUsize::new(at);
}
fn get(&self, slot: usize) -> Option<usize> {
self[slot].map(NonMaxUsize::get)
}
fn clear(&mut self, slot: usize) {
self[slot] = None;
}
}
impl Slots for [usize] {
fn set(&mut self, slot: usize, at: usize) {
self[slot] = at;
}
fn get(&self, slot: usize) -> Option<usize> {
Some(self[slot]).filter(|&at| at != usize::MAX)
}
fn clear(&mut self, slot: usize) {
self[slot] = usize::MAX;
}
}
#[cfg(test)]
mod tests {
use super::{Candidates, NFA_UNIT_BUDGET, Plan, PlanInput, RESCAN_BOUND};
#[cfg(feature = "std")]
std::thread_local! {
pub(super) static COVERED: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
pub(super) static SCANNED: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
}
#[cfg(feature = "std")]
pub(super) fn cover(start: usize, stop: usize) {
COVERED.with(|covered| covered.set(covered.get() + stop - start + 1));
}
fn plan(pattern: &str) -> Option<Plan> {
Plan::new(®ex_syntax::parse(pattern).unwrap(), true)
}
#[test]
fn candidates_follow_pattern_shape() {
fn name(candidates: &Candidates) -> String {
match candidates {
Candidates::Lines(crlf, _) => format!("lines {crlf}"),
Candidates::Inner(_, index, min, scan) => {
format!("inner {index} {min} else {}", name(scan))
}
Candidates::Offset(_, offset) => format!("offset {offset}"),
Candidates::Literal(_) => "literal".into(),
Candidates::Bytes(_) => "bytes".into(),
Candidates::Ranges(..) => "ranges".into(),
Candidates::Class(_) => "class".into(),
Candidates::Prefilter(_) => "prefilter".into(),
Candidates::Behind(..) => "behind".into(),
Candidates::Suffix(..) => "suffix".into(),
}
}
let kind = |pattern: &str| name(&plan(pattern).expect(pattern).candidates);
for (pattern, expected) in [
(r"(?m)^\w+\r?$", "lines false"),
(r"(?mR)^\w+$", "lines true"),
(r"(?m)^[A-Z]\w*", "lines false"),
(r"(?m)^#\w+", "literal"),
(r"(?m)\w+$", "class"),
(r"(\d{2}):(\d{2}):(\d{2})", "inner 3 2 else ranges"),
(r"\d{4}/\d{2}/\d{2}", "inner 1 4 else ranges"),
(r"\w{2}-", "inner 1 2 else class"),
(r"(?-u:\d{4})/\d", "offset 4"),
(r"(?-u:(\d{2})):\d", "offset 2"),
(r"(?-u:\d)[a-z]{70}:", "offset 71"),
("(?i)Sherlock Holmes", "prefilter"),
(r"[ab]{2}:\pL{2}:xyzw", "offset 2"),
(r"\pL{8}é\d", "ranges"),
(r".{12}a\d", "ranges"),
(r"\d\pL{70}:", "ranges"),
] {
assert_eq!(kind(pattern), expected, "{pattern}");
}
}
#[test]
fn admission_follows_shape_rules() {
for pattern in [
r"\w+",
r#""[^"]*""#,
r"\bfn\s+(\w+)",
r"\b\w+\b",
r"^\d+$",
r"(?m)\w+$",
r"a\w*?",
r"\d{4}-\d{2}-\d{2}",
"a{1,3}b*c",
r"\w+:\s*\w+",
r"\w*",
"ab|cd",
"Holmes|Watson|Lestrade",
"ab|ac",
"(?:a|)b",
r"\b(?:fn|let|mut)\b",
"(?i)holmes|watson",
"(?:ab)+",
"(?:ab){2,}",
"colou?r",
"(a)?(b*)",
r"(\d+)(?:\.(\d+))?",
r"\w+(?:\.\w+)*",
"(?:foo|bar)(?:baz)?",
"x(?:ab)*?y",
] {
assert!(plan(pattern).is_some(), "{pattern}");
}
for pattern in [
r"\w+s",
r"\w+\B",
r"(?m)[^a]+$",
"[a-z]+?x",
r"\d+$",
"a{1,70}b",
r"\w+-\w+-x",
r"x[a-z]*\d",
"ab+|ac",
"(a|ab)c",
"(?:a|)b+",
"(?:a*)*",
"(?:ab)*a",
r"x(?:ab)*?\b",
"(?:foo|bar)+qux",
"a(?:ba)*c",
r"\b(?:ab)*",
] {
assert!(plan(pattern).is_none(), "{pattern}");
}
}
#[test]
fn nfa_bound_exceeds_the_budget_wherever_the_default_limit_rejects() {
let families: &[(&str, &str, &str, usize)] = &[
("", "()", "a", 109_225),
("", "(a)", "", 109_225),
("", "(?m:^)", "a", 327_673),
("a", "(?m:$)", "", 327_673),
("", r"\b", "a", 327_673),
("", "a", "", 327_672),
("", "(?s:.)", "", 10_878),
("", r"\w", "", 210),
("", "a?", "", 100_823),
("", "a*b", "", 100_823),
("", r"(\w)", "", 210),
("", r"[\x{10000}-\x{10FFFF}]", "", 22_795),
("", r"\p{Han}", "", 2_891),
("", "[€-𝄞]", "", 12_603),
("", "(?i:[a-z])", "", 34_493),
("", r"[\x{80}-\x{7FF}]", "", 79_437),
];
for &(prefix, unit, suffix, rejected) in families {
let bound = |copies: usize| {
let pattern = format!("{prefix}{}{suffix}", unit.repeat(copies));
super::nfa_bound(®ex_syntax::parse(&pattern).unwrap())
};
let (hundred, two_hundred) = (bound(100), bound(200));
let at_rejection = hundred + (two_hundred - hundred) * (rejected - 100) / 100;
assert!(
at_rejection > 16 * NFA_UNIT_BUDGET,
"{unit}: {at_rejection} units where the limit rejects"
);
}
}
#[test]
fn nfa_units_bound_typical_patterns() {
let units = |pattern: &str| plan(pattern).unwrap().nfa_units();
assert!(units(r"\b\w+\b") <= NFA_UNIT_BUDGET);
assert!(units(r"\bfn\s+(\w+)") <= NFA_UNIT_BUDGET);
assert!(units(r#""[^"]*""#) <= NFA_UNIT_BUDGET);
assert!(units(r"\w{8}") > NFA_UNIT_BUDGET);
assert!(units(&"ab".repeat(5000)) > NFA_UNIT_BUDGET);
}
#[cfg(feature = "std")]
#[test]
fn short_first_runs_are_scanned_once() {
use alloc::format;
use alloc::vec::Vec;
let scanned = |f: &mut dyn FnMut()| {
SCANNED.with(|scanned| scanned.set(0));
COVERED.with(|covered| covered.set(0));
f();
(
SCANNED.with(core::cell::Cell::get),
COVERED.with(core::cell::Cell::get),
)
};
for minimum in [2, 8, 64] {
for (pattern, lead, tail) in [
(format!(r"[a-z]{{{minimum},}}\d"), "", 1),
(format!(r"([a-z]{{{minimum},}})(\d)"), "", 1),
(format!("[a-z]{{{minimum},}}"), "", 0),
(format!(r"-(?:[a-z]{{{minimum},}}\d|_)"), "-", 1),
] {
let plan = plan(&pattern).expect("each run is planned");
let misses = format!("{lead}{}_", "a".repeat(minimum - 1)).repeat(32);
let hit = format!("{misses}{lead}{}1", "a".repeat(minimum));
for text in [&misses, &hit] {
let len = text.len();
let expected = (text == &hit)
.then(|| (misses.len(), misses.len() + lead.len() + minimum + tail));
let input = |start: usize, end: usize| PlanInput {
haystack: text.as_bytes(),
start,
end,
anchored: false,
utf8: true,
};
let at = format!("{pattern} on {len} bytes");
let mut found = Vec::new();
let (read, covered) = scanned(&mut || {
let mut start = 0;
while let Some(span) = plan.find::<[usize]>(&input(start, len), None) {
found.push(span);
start = span.1;
}
});
assert_eq!(found, Vec::from_iter(expected), "{at}");
assert!(read <= len, "{at}: iteration read {read} run members");
assert!(
covered >= read,
"{at}: attempts cover {covered} of {read} reads"
);
assert!(covered <= 2 * (len + 1), "{at}: attempts cover {covered}");
let mut slots = [usize::MAX; 6];
let (read, _) = scanned(&mut || {
let slots = &mut slots[..plan.slot_len()];
assert_eq!(plan.find(&input(0, len), Some(slots)), expected, "{at}");
});
assert!(read <= len, "{at}: captures read {read} run members");
let (read, _) = scanned(&mut || {
assert_eq!(plan.is_match(&input(0, len)), expected.is_some(), "{at}");
});
assert!(read <= len, "{at}: membership read {read} run members");
let ranged = expected.filter(|_| tail == 0);
let (read, _) = scanned(&mut || {
let found = plan.find::<[usize]>(&input(1, len - 1), None);
assert_eq!(found, ranged, "{at}");
});
assert!(read <= len, "{at}: ranged search read {read} run members");
}
}
}
}
#[cfg(feature = "std")]
#[test]
fn attempts_read_each_byte_a_bounded_number_of_times() {
use alloc::string::String;
let patterns = [
r"\w+",
r"\w+(?:\.\w+)*",
r"(\d+)(?:\.(\d+))?",
"(?:ab)+",
"(?:ab)+c",
"x(?:ab)*y",
"(?:foo|bar)+qux",
"(?:foo|bar)(?:baz)?",
"a(?:ba)*c",
r"\w+-\w+-x",
r"x[a-z]*\d",
"Holmes|Hound",
"(?:a|b)+c",
"(a)?(b*)",
r"[a-c]{1,40}d",
r"\w+(?:,\w+)*;",
r"(?:\w\.)+x",
r"[a-z]{3,}\d",
r"\w{4,}",
r"(\d{2}):(\d{2})",
r"\d{4}/\d{2}x",
r"\w{8}:",
r"(?m)^\w+$",
r"(?m)^[\w\n]+;",
];
let fragments = [
"ab", "abab", "foo", "bar", "qu", "a.", "1.", "x", "ba", "-", "Ho", "c", "a,", "b",
"q", ".", " ", "1", "12:", "١٢", "/", ":", "\n", "é", ";",
];
let mut seed = 7u64;
let mut next = move |n: usize| {
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
(seed % n as u64) as usize
};
for pattern in patterns {
let Some(plan) = plan(pattern) else {
continue;
};
for round in 0..40 {
let mut text = String::new();
let unit: String = (0..1 + round % 4)
.map(|_| fragments[next(fragments.len())])
.collect();
while text.len() < 4000 {
if next(8) == 0 {
text.push_str(fragments[next(fragments.len())]);
} else {
text.push_str(&unit);
}
}
COVERED.with(|covered| covered.set(0));
SCANNED.with(|scanned| scanned.set(0));
let mut start = 0;
while start <= text.len() {
let input = PlanInput {
haystack: text.as_bytes(),
start,
end: text.len(),
anchored: false,
utf8: true,
};
match plan.find::<[usize]>(&input, None) {
Some((_, end)) => start = if end > start { end } else { start + 1 },
None => break,
}
}
let covered = COVERED.with(core::cell::Cell::get);
let scanned = SCANNED.with(core::cell::Cell::get);
assert!(
covered <= (RESCAN_BOUND + 8) * (text.len() + 1)
&& scanned <= (RESCAN_BOUND + 8) * (text.len() + 1),
"{pattern}: {covered} bytes read, {scanned} run members, for {} on {unit:?}",
text.len()
);
}
}
}
}