| 1 |
/*! |
| 2 |
This module defines two bespoke reverse DFA searching routines. (One for the |
| 3 |
lazy DFA and one for the fully compiled DFA.) These routines differ from the |
| 4 |
usual ones by permitting the caller to specify a minimum starting position. |
| 5 |
That is, the search will begin at `input.end()` and will usually stop at |
| 6 |
`input.start()`, unless `min_start > input.start()`, in which case, the search |
| 7 |
will stop at `min_start`. |
| 8 |
|
| 9 |
In other words, this lets you say, "no, the search must not extend past this |
| 10 |
point, even if it's within the bounds of the given `Input`." And if the search |
| 11 |
*does* want to go past that point, it stops and returns a "may be quadratic" |
| 12 |
error, which indicates that the caller should retry using some other technique. |
| 13 |
|
| 14 |
These routines specifically exist to protect against quadratic behavior when |
| 15 |
employing the "reverse suffix" and "reverse inner" optimizations. Without the |
| 16 |
backstop these routines provide, it is possible for parts of the haystack to |
| 17 |
get re-scanned over and over again. The backstop not only prevents this, but |
| 18 |
*tells you when it is happening* so that you can change the strategy. |
| 19 |
|
| 20 |
Why can't we just use the normal search routines? We could use the normal |
| 21 |
search routines and just set the start bound on the provided `Input` to our |
| 22 |
`min_start` position. The problem here is that it's impossible to distinguish |
| 23 |
between "no match because we reached the end of input" and "determined there |
| 24 |
was no match well before the end of input." The former case is what we care |
| 25 |
about with respect to quadratic behavior. The latter case is totally fine. |
| 26 |
|
| 27 |
Why don't we modify the normal search routines to report the position at which |
| 28 |
the search stops? I considered this, and I still wonder if it is indeed the |
| 29 |
right thing to do. However, I think the straight-forward thing to do there |
| 30 |
would be to complicate the return type signature of almost every search routine |
| 31 |
in this crate, which I really do not want to do. It therefore might make more |
| 32 |
sense to provide a richer way for search routines to report meta data, but that |
| 33 |
was beyond my bandwidth to work on at the time of writing. |
| 34 |
|
| 35 |
See the 'opt/reverse-inner' and 'opt/reverse-suffix' benchmarks in rebar for a |
| 36 |
real demonstration of how quadratic behavior is mitigated. |
| 37 |
*/ |
| 38 |
|
| 39 |
use crate::{ |
| 40 |
meta::error::{RetryError, RetryQuadraticError}, |
| 41 |
HalfMatch, Input, MatchError, |
| 42 |
}; |
| 43 |
|
| 44 |
#[cfg(feature = "dfa-build")] |
| 45 |
pub(crate) fn dfa_try_search_half_rev( |
| 46 |
dfa: &crate::dfa::dense::DFA<alloc::vec::Vec<u32>>, |
| 47 |
input: &Input<'_>, |
| 48 |
min_start: usize, |
| 49 |
) -> Result<Option<HalfMatch>, RetryError> { |
| 50 |
use crate::dfa::Automaton; |
| 51 |
|
| 52 |
let mut mat = None; |
| 53 |
let mut sid = dfa.start_state_reverse(input)?; |
| 54 |
if input.start() == input.end() { |
| 55 |
dfa_eoi_rev(dfa, input, &mut sid, &mut mat)?; |
| 56 |
return Ok(mat); |
| 57 |
} |
| 58 |
let mut at = input.end() - 1; |
| 59 |
loop { |
| 60 |
sid = dfa.next_state(sid, input.haystack()[at]); |
| 61 |
if dfa.is_special_state(sid) { |
| 62 |
if dfa.is_match_state(sid) { |
| 63 |
let pattern = dfa.match_pattern(sid, 0); |
| 64 |
// Since reverse searches report the beginning of a |
| 65 |
// match and the beginning is inclusive (not exclusive |
| 66 |
// like the end of a match), we add 1 to make it |
| 67 |
// inclusive. |
| 68 |
mat = Some(HalfMatch::new(pattern, at + 1)); |
| 69 |
} else if dfa.is_dead_state(sid) { |
| 70 |
return Ok(mat); |
| 71 |
} else if dfa.is_quit_state(sid) { |
| 72 |
return Err(MatchError::quit(input.haystack()[at], at).into()); |
| 73 |
} |
| 74 |
} |
| 75 |
if at == input.start() { |
| 76 |
break; |
| 77 |
} |
| 78 |
at -= 1; |
| 79 |
if at < min_start { |
| 80 |
trace!( |
| 81 |
"reached position {} which is before the previous literal \ |
| 82 |
match, quitting to avoid quadratic behavior", |
| 83 |
at, |
| 84 |
); |
| 85 |
return Err(RetryError::Quadratic(RetryQuadraticError::new())); |
| 86 |
} |
| 87 |
} |
| 88 |
let was_dead = dfa.is_dead_state(sid); |
| 89 |
dfa_eoi_rev(dfa, input, &mut sid, &mut mat)?; |
| 90 |
// If we reach the beginning of the search and we could otherwise still |
| 91 |
// potentially keep matching if there was more to match, then we actually |
| 92 |
// return an error to indicate giving up on this optimization. Why? Because |
| 93 |
// we can't prove that the real match begins at where we would report it. |
| 94 |
// |
| 95 |
// This only happens when all of the following are true: |
| 96 |
// |
| 97 |
// 1) We reach the starting point of our search span. |
| 98 |
// 2) The match we found is before the starting point. |
| 99 |
// 3) The FSM reports we could possibly find a longer match. |
| 100 |
// |
| 101 |
// We need (1) because otherwise the search stopped before the starting |
| 102 |
// point and there is no possible way to find a more leftmost position. |
| 103 |
// |
| 104 |
// We need (2) because if the match found has an offset equal to the minimum |
| 105 |
// possible offset, then there is no possible more leftmost match. |
| 106 |
// |
| 107 |
// We need (3) because if the FSM couldn't continue anyway (i.e., it's in |
| 108 |
// a dead state), then we know we couldn't find anything more leftmost |
| 109 |
// than what we have. (We have to check the state we were in prior to the |
| 110 |
// EOI transition since the EOI transition will usually bring us to a dead |
| 111 |
// state by virtue of it represents the end-of-input.) |
| 112 |
if at == input.start() |
| 113 |
&& mat.map_or(false, |m| m.offset() > input.start()) |
| 114 |
&& !was_dead |
| 115 |
{ |
| 116 |
trace!( |
| 117 |
"reached beginning of search at offset {} without hitting \ |
| 118 |
a dead state, quitting to avoid potential false positive match", |
| 119 |
at, |
| 120 |
); |
| 121 |
return Err(RetryError::Quadratic(RetryQuadraticError::new())); |
| 122 |
} |
| 123 |
Ok(mat) |
| 124 |
} |
| 125 |
|
| 126 |
#[cfg(feature = "hybrid")] |
| 127 |
pub(crate) fn hybrid_try_search_half_rev( |
| 128 |
dfa: &crate::hybrid::dfa::DFA, |
| 129 |
cache: &mut crate::hybrid::dfa::Cache, |
| 130 |
input: &Input<'_>, |
| 131 |
min_start: usize, |
| 132 |
) -> Result<Option<HalfMatch>, RetryError> { |
| 133 |
let mut mat = None; |
| 134 |
let mut sid = dfa.start_state_reverse(cache, input)?; |
| 135 |
if input.start() == input.end() { |
| 136 |
hybrid_eoi_rev(dfa, cache, input, &mut sid, &mut mat)?; |
| 137 |
return Ok(mat); |
| 138 |
} |
| 139 |
let mut at = input.end() - 1; |
| 140 |
loop { |
| 141 |
sid = dfa |
| 142 |
.next_state(cache, sid, input.haystack()[at]) |
| 143 |
.map_err(|_| MatchError::gave_up(at))?; |
| 144 |
if sid.is_tagged() { |
| 145 |
if sid.is_match() { |
| 146 |
let pattern = dfa.match_pattern(cache, sid, 0); |
| 147 |
// Since reverse searches report the beginning of a |
| 148 |
// match and the beginning is inclusive (not exclusive |
| 149 |
// like the end of a match), we add 1 to make it |
| 150 |
// inclusive. |
| 151 |
mat = Some(HalfMatch::new(pattern, at + 1)); |
| 152 |
} else if sid.is_dead() { |
| 153 |
return Ok(mat); |
| 154 |
} else if sid.is_quit() { |
| 155 |
return Err(MatchError::quit(input.haystack()[at], at).into()); |
| 156 |
} |
| 157 |
} |
| 158 |
if at == input.start() { |
| 159 |
break; |
| 160 |
} |
| 161 |
at -= 1; |
| 162 |
if at < min_start { |
| 163 |
trace!( |
| 164 |
"reached position {} which is before the previous literal \ |
| 165 |
match, quitting to avoid quadratic behavior", |
| 166 |
at, |
| 167 |
); |
| 168 |
return Err(RetryError::Quadratic(RetryQuadraticError::new())); |
| 169 |
} |
| 170 |
} |
| 171 |
let was_dead = sid.is_dead(); |
| 172 |
hybrid_eoi_rev(dfa, cache, input, &mut sid, &mut mat)?; |
| 173 |
// See the comments in the full DFA routine above for why we need this. |
| 174 |
if at == input.start() |
| 175 |
&& mat.map_or(false, |m| m.offset() > input.start()) |
| 176 |
&& !was_dead |
| 177 |
{ |
| 178 |
trace!( |
| 179 |
"reached beginning of search at offset {} without hitting \ |
| 180 |
a dead state, quitting to avoid potential false positive match", |
| 181 |
at, |
| 182 |
); |
| 183 |
return Err(RetryError::Quadratic(RetryQuadraticError::new())); |
| 184 |
} |
| 185 |
Ok(mat) |
| 186 |
} |
| 187 |
|
| 188 |
#[cfg(feature = "dfa-build")] |
| 189 |
#[cfg_attr(feature = "perf-inline", inline(always))] |
| 190 |
fn dfa_eoi_rev( |
| 191 |
dfa: &crate::dfa::dense::DFA<alloc::vec::Vec<u32>>, |
| 192 |
input: &Input<'_>, |
| 193 |
sid: &mut crate::util::primitives::StateID, |
| 194 |
mat: &mut Option<HalfMatch>, |
| 195 |
) -> Result<(), MatchError> { |
| 196 |
use crate::dfa::Automaton; |
| 197 |
|
| 198 |
let sp = input.get_span(); |
| 199 |
if sp.start > 0 { |
| 200 |
let byte = input.haystack()[sp.start - 1]; |
| 201 |
*sid = dfa.next_state(*sid, byte); |
| 202 |
if dfa.is_match_state(*sid) { |
| 203 |
let pattern = dfa.match_pattern(*sid, 0); |
| 204 |
*mat = Some(HalfMatch::new(pattern, sp.start)); |
| 205 |
} else if dfa.is_quit_state(*sid) { |
| 206 |
return Err(MatchError::quit(byte, sp.start - 1)); |
| 207 |
} |
| 208 |
} else { |
| 209 |
*sid = dfa.next_eoi_state(*sid); |
| 210 |
if dfa.is_match_state(*sid) { |
| 211 |
let pattern = dfa.match_pattern(*sid, 0); |
| 212 |
*mat = Some(HalfMatch::new(pattern, 0)); |
| 213 |
} |
| 214 |
// N.B. We don't have to check 'is_quit' here because the EOI |
| 215 |
// transition can never lead to a quit state. |
| 216 |
debug_assert!(!dfa.is_quit_state(*sid)); |
| 217 |
} |
| 218 |
Ok(()) |
| 219 |
} |
| 220 |
|
| 221 |
#[cfg(feature = "hybrid")] |
| 222 |
#[cfg_attr(feature = "perf-inline", inline(always))] |
| 223 |
fn hybrid_eoi_rev( |
| 224 |
dfa: &crate::hybrid::dfa::DFA, |
| 225 |
cache: &mut crate::hybrid::dfa::Cache, |
| 226 |
input: &Input<'_>, |
| 227 |
sid: &mut crate::hybrid::LazyStateID, |
| 228 |
mat: &mut Option<HalfMatch>, |
| 229 |
) -> Result<(), MatchError> { |
| 230 |
let sp = input.get_span(); |
| 231 |
if sp.start > 0 { |
| 232 |
let byte = input.haystack()[sp.start - 1]; |
| 233 |
*sid = dfa |
| 234 |
.next_state(cache, *sid, byte) |
| 235 |
.map_err(|_| MatchError::gave_up(sp.start))?; |
| 236 |
if sid.is_match() { |
| 237 |
let pattern = dfa.match_pattern(cache, *sid, 0); |
| 238 |
*mat = Some(HalfMatch::new(pattern, sp.start)); |
| 239 |
} else if sid.is_quit() { |
| 240 |
return Err(MatchError::quit(byte, sp.start - 1)); |
| 241 |
} |
| 242 |
} else { |
| 243 |
*sid = dfa |
| 244 |
.next_eoi_state(cache, *sid) |
| 245 |
.map_err(|_| MatchError::gave_up(sp.start))?; |
| 246 |
if sid.is_match() { |
| 247 |
let pattern = dfa.match_pattern(cache, *sid, 0); |
| 248 |
*mat = Some(HalfMatch::new(pattern, 0)); |
| 249 |
} |
| 250 |
// N.B. We don't have to check 'is_quit' here because the EOI |
| 251 |
// transition can never lead to a quit state. |
| 252 |
debug_assert!(!sid.is_quit()); |
| 253 |
} |
| 254 |
Ok(()) |
| 255 |
} |