summaryrefslogtreecommitdiffstats
path: root/third_party/rust/regex-automata/src/dfa/search.rs
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/regex-automata/src/dfa/search.rs')
-rw-r--r--third_party/rust/regex-automata/src/dfa/search.rs654
1 files changed, 654 insertions, 0 deletions
diff --git a/third_party/rust/regex-automata/src/dfa/search.rs b/third_party/rust/regex-automata/src/dfa/search.rs
new file mode 100644
index 0000000000..8c012a5944
--- /dev/null
+++ b/third_party/rust/regex-automata/src/dfa/search.rs
@@ -0,0 +1,654 @@
+use crate::{
+ dfa::{
+ accel,
+ automaton::{Automaton, OverlappingState},
+ },
+ util::{
+ prefilter::Prefilter,
+ primitives::StateID,
+ search::{Anchored, HalfMatch, Input, Span},
+ },
+ MatchError,
+};
+
+#[inline(never)]
+pub fn find_fwd<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+) -> Result<Option<HalfMatch>, MatchError> {
+ if input.is_done() {
+ return Ok(None);
+ }
+ let pre = if input.get_anchored().is_anchored() {
+ None
+ } else {
+ dfa.get_prefilter()
+ };
+ // Searching with a pattern ID is always anchored, so we should never use
+ // a prefilter.
+ if pre.is_some() {
+ if input.get_earliest() {
+ find_fwd_imp(dfa, input, pre, true)
+ } else {
+ find_fwd_imp(dfa, input, pre, false)
+ }
+ } else {
+ if input.get_earliest() {
+ find_fwd_imp(dfa, input, None, true)
+ } else {
+ find_fwd_imp(dfa, input, None, false)
+ }
+ }
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn find_fwd_imp<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+ pre: Option<&'_ Prefilter>,
+ earliest: bool,
+) -> Result<Option<HalfMatch>, MatchError> {
+ // See 'prefilter_restart' docs for explanation.
+ let universal_start = dfa.universal_start_state(Anchored::No).is_some();
+ let mut mat = None;
+ let mut sid = init_fwd(dfa, input)?;
+ let mut at = input.start();
+ // This could just be a closure, but then I think it would be unsound
+ // because it would need to be safe to invoke. This way, the lack of safety
+ // is clearer in the code below.
+ macro_rules! next_unchecked {
+ ($sid:expr, $at:expr) => {{
+ let byte = *input.haystack().get_unchecked($at);
+ dfa.next_state_unchecked($sid, byte)
+ }};
+ }
+
+ if let Some(ref pre) = pre {
+ let span = Span::from(at..input.end());
+ // If a prefilter doesn't report false positives, then we don't need to
+ // touch the DFA at all. However, since all matches include the pattern
+ // ID, and the prefilter infrastructure doesn't report pattern IDs, we
+ // limit this optimization to cases where there is exactly one pattern.
+ // In that case, any match must be the 0th pattern.
+ match pre.find(input.haystack(), span) {
+ None => return Ok(mat),
+ Some(ref span) => {
+ at = span.start;
+ if !universal_start {
+ sid = prefilter_restart(dfa, &input, at)?;
+ }
+ }
+ }
+ }
+ while at < input.end() {
+ // SAFETY: There are two safety invariants we need to uphold here in
+ // the loops below: that 'sid' and 'prev_sid' are valid state IDs
+ // for this DFA, and that 'at' is a valid index into 'haystack'.
+ // For the former, we rely on the invariant that next_state* and
+ // start_state_forward always returns a valid state ID (given a valid
+ // state ID in the former case). For the latter safety invariant, we
+ // always guard unchecked access with a check that 'at' is less than
+ // 'end', where 'end <= haystack.len()'. In the unrolled loop below, we
+ // ensure that 'at' is always in bounds.
+ //
+ // PERF: See a similar comment in src/hybrid/search.rs that justifies
+ // this extra work to make the search loop fast. The same reasoning and
+ // benchmarks apply here.
+ let mut prev_sid;
+ while at < input.end() {
+ prev_sid = unsafe { next_unchecked!(sid, at) };
+ if dfa.is_special_state(prev_sid) || at + 3 >= input.end() {
+ core::mem::swap(&mut prev_sid, &mut sid);
+ break;
+ }
+ at += 1;
+
+ sid = unsafe { next_unchecked!(prev_sid, at) };
+ if dfa.is_special_state(sid) {
+ break;
+ }
+ at += 1;
+
+ prev_sid = unsafe { next_unchecked!(sid, at) };
+ if dfa.is_special_state(prev_sid) {
+ core::mem::swap(&mut prev_sid, &mut sid);
+ break;
+ }
+ at += 1;
+
+ sid = unsafe { next_unchecked!(prev_sid, at) };
+ if dfa.is_special_state(sid) {
+ break;
+ }
+ at += 1;
+ }
+ if dfa.is_special_state(sid) {
+ if dfa.is_start_state(sid) {
+ if let Some(ref pre) = pre {
+ let span = Span::from(at..input.end());
+ match pre.find(input.haystack(), span) {
+ None => return Ok(mat),
+ Some(ref span) => {
+ // We want to skip any update to 'at' below
+ // at the end of this iteration and just
+ // jump immediately back to the next state
+ // transition at the leading position of the
+ // candidate match.
+ //
+ // ... but only if we actually made progress
+ // with our prefilter, otherwise if the start
+ // state has a self-loop, we can get stuck.
+ if span.start > at {
+ at = span.start;
+ if !universal_start {
+ sid = prefilter_restart(dfa, &input, at)?;
+ }
+ continue;
+ }
+ }
+ }
+ } else if dfa.is_accel_state(sid) {
+ let needles = dfa.accelerator(sid);
+ at = accel::find_fwd(needles, input.haystack(), at + 1)
+ .unwrap_or(input.end());
+ continue;
+ }
+ } else if dfa.is_match_state(sid) {
+ let pattern = dfa.match_pattern(sid, 0);
+ mat = Some(HalfMatch::new(pattern, at));
+ if earliest {
+ return Ok(mat);
+ }
+ if dfa.is_accel_state(sid) {
+ let needles = dfa.accelerator(sid);
+ at = accel::find_fwd(needles, input.haystack(), at + 1)
+ .unwrap_or(input.end());
+ continue;
+ }
+ } else if dfa.is_accel_state(sid) {
+ let needs = dfa.accelerator(sid);
+ at = accel::find_fwd(needs, input.haystack(), at + 1)
+ .unwrap_or(input.end());
+ continue;
+ } else if dfa.is_dead_state(sid) {
+ return Ok(mat);
+ } else {
+ // It's important that this is a debug_assert, since this can
+ // actually be tripped even if DFA::from_bytes succeeds and
+ // returns a supposedly valid DFA.
+ debug_assert!(dfa.is_quit_state(sid));
+ return Err(MatchError::quit(input.haystack()[at], at));
+ }
+ }
+ at += 1;
+ }
+ eoi_fwd(dfa, input, &mut sid, &mut mat)?;
+ Ok(mat)
+}
+
+#[inline(never)]
+pub fn find_rev<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+) -> Result<Option<HalfMatch>, MatchError> {
+ if input.is_done() {
+ return Ok(None);
+ }
+ if input.get_earliest() {
+ find_rev_imp(dfa, input, true)
+ } else {
+ find_rev_imp(dfa, input, false)
+ }
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn find_rev_imp<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+ earliest: bool,
+) -> Result<Option<HalfMatch>, MatchError> {
+ let mut mat = None;
+ let mut sid = init_rev(dfa, input)?;
+ // In reverse search, the loop below can't handle the case of searching an
+ // empty slice. Ideally we could write something congruent to the forward
+ // search, i.e., 'while at >= start', but 'start' might be 0. Since we use
+ // an unsigned offset, 'at >= 0' is trivially always true. We could avoid
+ // this extra case handling by using a signed offset, but Rust makes it
+ // annoying to do. So... We just handle the empty case separately.
+ if input.start() == input.end() {
+ eoi_rev(dfa, input, &mut sid, &mut mat)?;
+ return Ok(mat);
+ }
+
+ let mut at = input.end() - 1;
+ macro_rules! next_unchecked {
+ ($sid:expr, $at:expr) => {{
+ let byte = *input.haystack().get_unchecked($at);
+ dfa.next_state_unchecked($sid, byte)
+ }};
+ }
+ loop {
+ // SAFETY: See comments in 'find_fwd' for a safety argument.
+ let mut prev_sid;
+ while at >= input.start() {
+ prev_sid = unsafe { next_unchecked!(sid, at) };
+ if dfa.is_special_state(prev_sid)
+ || at <= input.start().saturating_add(3)
+ {
+ core::mem::swap(&mut prev_sid, &mut sid);
+ break;
+ }
+ at -= 1;
+
+ sid = unsafe { next_unchecked!(prev_sid, at) };
+ if dfa.is_special_state(sid) {
+ break;
+ }
+ at -= 1;
+
+ prev_sid = unsafe { next_unchecked!(sid, at) };
+ if dfa.is_special_state(prev_sid) {
+ core::mem::swap(&mut prev_sid, &mut sid);
+ break;
+ }
+ at -= 1;
+
+ sid = unsafe { next_unchecked!(prev_sid, at) };
+ if dfa.is_special_state(sid) {
+ break;
+ }
+ at -= 1;
+ }
+ if dfa.is_special_state(sid) {
+ if dfa.is_start_state(sid) {
+ if dfa.is_accel_state(sid) {
+ let needles = dfa.accelerator(sid);
+ at = accel::find_rev(needles, input.haystack(), at)
+ .map(|i| i + 1)
+ .unwrap_or(input.start());
+ }
+ } else if dfa.is_match_state(sid) {
+ let pattern = dfa.match_pattern(sid, 0);
+ // Since reverse searches report the beginning of a match
+ // and the beginning is inclusive (not exclusive like the
+ // end of a match), we add 1 to make it inclusive.
+ mat = Some(HalfMatch::new(pattern, at + 1));
+ if earliest {
+ return Ok(mat);
+ }
+ if dfa.is_accel_state(sid) {
+ let needles = dfa.accelerator(sid);
+ at = accel::find_rev(needles, input.haystack(), at)
+ .map(|i| i + 1)
+ .unwrap_or(input.start());
+ }
+ } else if dfa.is_accel_state(sid) {
+ let needles = dfa.accelerator(sid);
+ // If the accelerator returns nothing, why don't we quit the
+ // search? Well, if the accelerator doesn't find anything, that
+ // doesn't mean we don't have a match. It just means that we
+ // can't leave the current state given one of the 255 possible
+ // byte values. However, there might be an EOI transition. So
+ // we set 'at' to the end of the haystack, which will cause
+ // this loop to stop and fall down into the EOI transition.
+ at = accel::find_rev(needles, input.haystack(), at)
+ .map(|i| i + 1)
+ .unwrap_or(input.start());
+ } else if dfa.is_dead_state(sid) {
+ return Ok(mat);
+ } else {
+ debug_assert!(dfa.is_quit_state(sid));
+ return Err(MatchError::quit(input.haystack()[at], at));
+ }
+ }
+ if at == input.start() {
+ break;
+ }
+ at -= 1;
+ }
+ eoi_rev(dfa, input, &mut sid, &mut mat)?;
+ Ok(mat)
+}
+
+#[inline(never)]
+pub fn find_overlapping_fwd<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+ state: &mut OverlappingState,
+) -> Result<(), MatchError> {
+ state.mat = None;
+ if input.is_done() {
+ return Ok(());
+ }
+ let pre = if input.get_anchored().is_anchored() {
+ None
+ } else {
+ dfa.get_prefilter()
+ };
+ if pre.is_some() {
+ find_overlapping_fwd_imp(dfa, input, pre, state)
+ } else {
+ find_overlapping_fwd_imp(dfa, input, None, state)
+ }
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn find_overlapping_fwd_imp<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+ pre: Option<&'_ Prefilter>,
+ state: &mut OverlappingState,
+) -> Result<(), MatchError> {
+ // See 'prefilter_restart' docs for explanation.
+ let universal_start = dfa.universal_start_state(Anchored::No).is_some();
+ let mut sid = match state.id {
+ None => {
+ state.at = input.start();
+ init_fwd(dfa, input)?
+ }
+ Some(sid) => {
+ if let Some(match_index) = state.next_match_index {
+ let match_len = dfa.match_len(sid);
+ if match_index < match_len {
+ state.next_match_index = Some(match_index + 1);
+ let pattern = dfa.match_pattern(sid, match_index);
+ state.mat = Some(HalfMatch::new(pattern, state.at));
+ return Ok(());
+ }
+ }
+ // Once we've reported all matches at a given position, we need to
+ // advance the search to the next position.
+ state.at += 1;
+ if state.at > input.end() {
+ return Ok(());
+ }
+ sid
+ }
+ };
+
+ // NOTE: We don't optimize the crap out of this routine primarily because
+ // it seems like most find_overlapping searches will have higher match
+ // counts, and thus, throughput is perhaps not as important. But if you
+ // have a use case for something faster, feel free to file an issue.
+ while state.at < input.end() {
+ sid = dfa.next_state(sid, input.haystack()[state.at]);
+ if dfa.is_special_state(sid) {
+ state.id = Some(sid);
+ if dfa.is_start_state(sid) {
+ if let Some(ref pre) = pre {
+ let span = Span::from(state.at..input.end());
+ match pre.find(input.haystack(), span) {
+ None => return Ok(()),
+ Some(ref span) => {
+ if span.start > state.at {
+ state.at = span.start;
+ if !universal_start {
+ sid = prefilter_restart(
+ dfa, &input, state.at,
+ )?;
+ }
+ continue;
+ }
+ }
+ }
+ } else if dfa.is_accel_state(sid) {
+ let needles = dfa.accelerator(sid);
+ state.at = accel::find_fwd(
+ needles,
+ input.haystack(),
+ state.at + 1,
+ )
+ .unwrap_or(input.end());
+ continue;
+ }
+ } else if dfa.is_match_state(sid) {
+ state.next_match_index = Some(1);
+ let pattern = dfa.match_pattern(sid, 0);
+ state.mat = Some(HalfMatch::new(pattern, state.at));
+ return Ok(());
+ } else if dfa.is_accel_state(sid) {
+ let needs = dfa.accelerator(sid);
+ // If the accelerator returns nothing, why don't we quit the
+ // search? Well, if the accelerator doesn't find anything, that
+ // doesn't mean we don't have a match. It just means that we
+ // can't leave the current state given one of the 255 possible
+ // byte values. However, there might be an EOI transition. So
+ // we set 'at' to the end of the haystack, which will cause
+ // this loop to stop and fall down into the EOI transition.
+ state.at =
+ accel::find_fwd(needs, input.haystack(), state.at + 1)
+ .unwrap_or(input.end());
+ continue;
+ } else if dfa.is_dead_state(sid) {
+ return Ok(());
+ } else {
+ debug_assert!(dfa.is_quit_state(sid));
+ return Err(MatchError::quit(
+ input.haystack()[state.at],
+ state.at,
+ ));
+ }
+ }
+ state.at += 1;
+ }
+
+ let result = eoi_fwd(dfa, input, &mut sid, &mut state.mat);
+ state.id = Some(sid);
+ if state.mat.is_some() {
+ // '1' is always correct here since if we get to this point, this
+ // always corresponds to the first (index '0') match discovered at
+ // this position. So the next match to report at this position (if
+ // it exists) is at index '1'.
+ state.next_match_index = Some(1);
+ }
+ result
+}
+
+#[inline(never)]
+pub(crate) fn find_overlapping_rev<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+ state: &mut OverlappingState,
+) -> Result<(), MatchError> {
+ state.mat = None;
+ if input.is_done() {
+ return Ok(());
+ }
+ let mut sid = match state.id {
+ None => {
+ let sid = init_rev(dfa, input)?;
+ state.id = Some(sid);
+ if input.start() == input.end() {
+ state.rev_eoi = true;
+ } else {
+ state.at = input.end() - 1;
+ }
+ sid
+ }
+ Some(sid) => {
+ if let Some(match_index) = state.next_match_index {
+ let match_len = dfa.match_len(sid);
+ if match_index < match_len {
+ state.next_match_index = Some(match_index + 1);
+ let pattern = dfa.match_pattern(sid, match_index);
+ state.mat = Some(HalfMatch::new(pattern, state.at));
+ return Ok(());
+ }
+ }
+ // Once we've reported all matches at a given position, we need
+ // to advance the search to the next position. However, if we've
+ // already followed the EOI transition, then we know we're done
+ // with the search and there cannot be any more matches to report.
+ if state.rev_eoi {
+ return Ok(());
+ } else if state.at == input.start() {
+ // At this point, we should follow the EOI transition. This
+ // will cause us the skip the main loop below and fall through
+ // to the final 'eoi_rev' transition.
+ state.rev_eoi = true;
+ } else {
+ // We haven't hit the end of the search yet, so move on.
+ state.at -= 1;
+ }
+ sid
+ }
+ };
+ while !state.rev_eoi {
+ sid = dfa.next_state(sid, input.haystack()[state.at]);
+ if dfa.is_special_state(sid) {
+ state.id = Some(sid);
+ if dfa.is_start_state(sid) {
+ if dfa.is_accel_state(sid) {
+ let needles = dfa.accelerator(sid);
+ state.at =
+ accel::find_rev(needles, input.haystack(), state.at)
+ .map(|i| i + 1)
+ .unwrap_or(input.start());
+ }
+ } else if dfa.is_match_state(sid) {
+ state.next_match_index = Some(1);
+ let pattern = dfa.match_pattern(sid, 0);
+ state.mat = Some(HalfMatch::new(pattern, state.at + 1));
+ return Ok(());
+ } else if dfa.is_accel_state(sid) {
+ let needles = dfa.accelerator(sid);
+ // If the accelerator returns nothing, why don't we quit the
+ // search? Well, if the accelerator doesn't find anything, that
+ // doesn't mean we don't have a match. It just means that we
+ // can't leave the current state given one of the 255 possible
+ // byte values. However, there might be an EOI transition. So
+ // we set 'at' to the end of the haystack, which will cause
+ // this loop to stop and fall down into the EOI transition.
+ state.at =
+ accel::find_rev(needles, input.haystack(), state.at)
+ .map(|i| i + 1)
+ .unwrap_or(input.start());
+ } else if dfa.is_dead_state(sid) {
+ return Ok(());
+ } else {
+ debug_assert!(dfa.is_quit_state(sid));
+ return Err(MatchError::quit(
+ input.haystack()[state.at],
+ state.at,
+ ));
+ }
+ }
+ if state.at == input.start() {
+ break;
+ }
+ state.at -= 1;
+ }
+
+ let result = eoi_rev(dfa, input, &mut sid, &mut state.mat);
+ state.rev_eoi = true;
+ state.id = Some(sid);
+ if state.mat.is_some() {
+ // '1' is always correct here since if we get to this point, this
+ // always corresponds to the first (index '0') match discovered at
+ // this position. So the next match to report at this position (if
+ // it exists) is at index '1'.
+ state.next_match_index = Some(1);
+ }
+ result
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn init_fwd<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+) -> Result<StateID, MatchError> {
+ let sid = dfa.start_state_forward(input)?;
+ // Start states can never be match states, since all matches are delayed
+ // by 1 byte.
+ debug_assert!(!dfa.is_match_state(sid));
+ Ok(sid)
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn init_rev<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+) -> Result<StateID, MatchError> {
+ let sid = dfa.start_state_reverse(input)?;
+ // Start states can never be match states, since all matches are delayed
+ // by 1 byte.
+ debug_assert!(!dfa.is_match_state(sid));
+ Ok(sid)
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn eoi_fwd<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+ sid: &mut StateID,
+ mat: &mut Option<HalfMatch>,
+) -> Result<(), MatchError> {
+ let sp = input.get_span();
+ match input.haystack().get(sp.end) {
+ Some(&b) => {
+ *sid = dfa.next_state(*sid, b);
+ if dfa.is_match_state(*sid) {
+ let pattern = dfa.match_pattern(*sid, 0);
+ *mat = Some(HalfMatch::new(pattern, sp.end));
+ } else if dfa.is_quit_state(*sid) {
+ return Err(MatchError::quit(b, sp.end));
+ }
+ }
+ None => {
+ *sid = dfa.next_eoi_state(*sid);
+ if dfa.is_match_state(*sid) {
+ let pattern = dfa.match_pattern(*sid, 0);
+ *mat = Some(HalfMatch::new(pattern, input.haystack().len()));
+ }
+ // N.B. We don't have to check 'is_quit' here because the EOI
+ // transition can never lead to a quit state.
+ debug_assert!(!dfa.is_quit_state(*sid));
+ }
+ }
+ Ok(())
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn eoi_rev<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+ sid: &mut StateID,
+ mat: &mut Option<HalfMatch>,
+) -> Result<(), MatchError> {
+ let sp = input.get_span();
+ if sp.start > 0 {
+ let byte = input.haystack()[sp.start - 1];
+ *sid = dfa.next_state(*sid, byte);
+ if dfa.is_match_state(*sid) {
+ let pattern = dfa.match_pattern(*sid, 0);
+ *mat = Some(HalfMatch::new(pattern, sp.start));
+ } else if dfa.is_quit_state(*sid) {
+ return Err(MatchError::quit(byte, sp.start - 1));
+ }
+ } else {
+ *sid = dfa.next_eoi_state(*sid);
+ if dfa.is_match_state(*sid) {
+ let pattern = dfa.match_pattern(*sid, 0);
+ *mat = Some(HalfMatch::new(pattern, 0));
+ }
+ // N.B. We don't have to check 'is_quit' here because the EOI
+ // transition can never lead to a quit state.
+ debug_assert!(!dfa.is_quit_state(*sid));
+ }
+ Ok(())
+}
+
+/// Re-compute the starting state that a DFA should be in after finding a
+/// prefilter candidate match at the position `at`.
+///
+/// The function with the same name has a bit more docs in hybrid/search.rs.
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn prefilter_restart<A: Automaton + ?Sized>(
+ dfa: &A,
+ input: &Input<'_>,
+ at: usize,
+) -> Result<StateID, MatchError> {
+ let mut input = input.clone();
+ input.set_start(at);
+ init_fwd(dfa, &input)
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-08-29 03:06:10 +0000