1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
|
/*!
This module defines two bespoke forward DFA search routines. One for the lazy
DFA and one for the fully compiled DFA. These routines differ from the normal
ones by reporting the position at which the search terminates when a match
*isn't* found.
This position at which a search terminates is useful in contexts where the meta
regex engine runs optimizations that could go quadratic if we aren't careful.
Namely, a regex search *could* scan to the end of the haystack only to report a
non-match. If the caller doesn't know that the search scanned to the end of the
haystack, it might restart the search at the next literal candidate it finds
and repeat the process.
Providing the caller with the position at which the search stopped provides a
way for the caller to determine the point at which subsequent scans should not
pass. This is principally used in the "reverse inner" optimization, which works
like this:
1. Look for a match of an inner literal. Say, 'Z' in '\w+Z\d+'.
2. At the spot where 'Z' matches, do a reverse anchored search from there for
'\w+'.
3. If the reverse search matches, it corresponds to the start position of a
(possible) match. At this point, do a forward anchored search to find the end
position. If an end position is found, then we have a match and we know its
bounds.
If the forward anchored search in (3) searches the entire rest of the haystack
but reports a non-match, then a naive implementation of the above will continue
back at step 1 looking for more candidates. There might still be a match to be
found! It's possible. But we already scanned the whole haystack. So if we keep
repeating the process, then we might wind up taking quadratic time in the size
of the haystack, which is not great.
So if the forward anchored search in (3) reports the position at which it
stops, then we can detect whether quadratic behavior might be occurring in
steps (1) and (2). For (1), it occurs if the literal candidate found occurs
*before* the end of the previous search in (3), since that means we're now
going to look for another match in a place where the forward search has already
scanned. It is *correct* to do so, but our technique has become inefficient.
For (2), quadratic behavior occurs similarly when its reverse search extends
past the point where the previous forward search in (3) terminated. Indeed, to
implement (2), we use the sibling 'limited' module for ensuring our reverse
scan doesn't go further than we want.
See the 'opt/reverse-inner' benchmarks in rebar for a real demonstration of
how quadratic behavior is mitigated.
*/
use crate::{meta::error::RetryFailError, HalfMatch, Input, MatchError};
#[cfg(feature = "dfa-build")]
pub(crate) fn dfa_try_search_half_fwd(
dfa: &crate::dfa::dense::DFA<alloc::vec::Vec<u32>>,
input: &Input<'_>,
) -> Result<Result<HalfMatch, usize>, RetryFailError> {
use crate::dfa::{accel, Automaton};
let mut mat = None;
let mut sid = dfa.start_state_forward(input)?;
let mut at = input.start();
while at < input.end() {
sid = dfa.next_state(sid, input.haystack()[at]);
if dfa.is_special_state(sid) {
if dfa.is_match_state(sid) {
let pattern = dfa.match_pattern(sid, 0);
mat = Some(HalfMatch::new(pattern, at));
if input.get_earliest() {
return Ok(mat.ok_or(at));
}
if dfa.is_accel_state(sid) {
let needs = dfa.accelerator(sid);
at = accel::find_fwd(needs, input.haystack(), at)
.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)
.unwrap_or(input.end());
continue;
} else if dfa.is_dead_state(sid) {
return Ok(mat.ok_or(at));
} else if dfa.is_quit_state(sid) {
if mat.is_some() {
return Ok(mat.ok_or(at));
}
return Err(MatchError::quit(input.haystack()[at], at).into());
} else {
// Ideally we wouldn't use a DFA that specialized start states
// and thus 'is_start_state()' could never be true here, but in
// practice we reuse the DFA created for the full regex which
// will specialize start states whenever there is a prefilter.
debug_assert!(dfa.is_start_state(sid));
}
}
at += 1;
}
dfa_eoi_fwd(dfa, input, &mut sid, &mut mat)?;
Ok(mat.ok_or(at))
}
#[cfg(feature = "hybrid")]
pub(crate) fn hybrid_try_search_half_fwd(
dfa: &crate::hybrid::dfa::DFA,
cache: &mut crate::hybrid::dfa::Cache,
input: &Input<'_>,
) -> Result<Result<HalfMatch, usize>, RetryFailError> {
let mut mat = None;
let mut sid = dfa.start_state_forward(cache, input)?;
let mut at = input.start();
while at < input.end() {
sid = dfa
.next_state(cache, sid, input.haystack()[at])
.map_err(|_| MatchError::gave_up(at))?;
if sid.is_tagged() {
if sid.is_match() {
let pattern = dfa.match_pattern(cache, sid, 0);
mat = Some(HalfMatch::new(pattern, at));
if input.get_earliest() {
return Ok(mat.ok_or(at));
}
} else if sid.is_dead() {
return Ok(mat.ok_or(at));
} else if sid.is_quit() {
if mat.is_some() {
return Ok(mat.ok_or(at));
}
return Err(MatchError::quit(input.haystack()[at], at).into());
} else {
// We should NEVER get an unknown state ID back from
// dfa.next_state().
debug_assert!(!sid.is_unknown());
// Ideally we wouldn't use a lazy DFA that specialized start
// states and thus 'sid.is_start()' could never be true here,
// but in practice we reuse the lazy DFA created for the full
// regex which will specialize start states whenever there is
// a prefilter.
debug_assert!(sid.is_start());
}
}
at += 1;
}
hybrid_eoi_fwd(dfa, cache, input, &mut sid, &mut mat)?;
Ok(mat.ok_or(at))
}
#[cfg(feature = "dfa-build")]
#[cfg_attr(feature = "perf-inline", inline(always))]
fn dfa_eoi_fwd(
dfa: &crate::dfa::dense::DFA<alloc::vec::Vec<u32>>,
input: &Input<'_>,
sid: &mut crate::util::primitives::StateID,
mat: &mut Option<HalfMatch>,
) -> Result<(), MatchError> {
use crate::dfa::Automaton;
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) {
if mat.is_some() {
return Ok(());
}
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(feature = "hybrid")]
#[cfg_attr(feature = "perf-inline", inline(always))]
fn hybrid_eoi_fwd(
dfa: &crate::hybrid::dfa::DFA,
cache: &mut crate::hybrid::dfa::Cache,
input: &Input<'_>,
sid: &mut crate::hybrid::LazyStateID,
mat: &mut Option<HalfMatch>,
) -> Result<(), MatchError> {
let sp = input.get_span();
match input.haystack().get(sp.end) {
Some(&b) => {
*sid = dfa
.next_state(cache, *sid, b)
.map_err(|_| MatchError::gave_up(sp.end))?;
if sid.is_match() {
let pattern = dfa.match_pattern(cache, *sid, 0);
*mat = Some(HalfMatch::new(pattern, sp.end));
} else if sid.is_quit() {
if mat.is_some() {
return Ok(());
}
return Err(MatchError::quit(b, sp.end));
}
}
None => {
*sid = dfa
.next_eoi_state(cache, *sid)
.map_err(|_| MatchError::gave_up(input.haystack().len()))?;
if sid.is_match() {
let pattern = dfa.match_pattern(cache, *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!(!sid.is_quit());
}
}
Ok(())
}
|
