Debian Codegraph @

third_party/rust/regex-automata/src/hybrid/id.rs

raw
1 /// A state identifier specifically tailored for lazy DFAs.
2 ///
3 /// A lazy state ID logically represents a pointer to a DFA state. In practice,
4 /// by limiting the number of DFA states it can address, it reserves some
5 /// bits of its representation to encode some additional information. That
6 /// additional information is called a "tag." That tag is used to record
7 /// whether the state it points to is an unknown, dead, quit, start or match
8 /// state.
9 ///
10 /// When implementing a low level search routine with a lazy DFA, it is
11 /// necessary to query the type of the current state to know what to do:
12 ///
13 /// * **Unknown** - The state has not yet been computed. The
14 /// parameters used to get this state ID must be re-passed to
15 /// [`DFA::next_state`](crate::hybrid::dfa::DFA::next_state), which will never
16 /// return an unknown state ID.
17 /// * **Dead** - A dead state only has transitions to itself. It indicates that
18 /// the search cannot do anything else and should stop with whatever result it
19 /// has.
20 /// * **Quit** - A quit state indicates that the automaton could not answer
21 /// whether a match exists or not. Correct search implementations must return a
22 /// [`MatchError::quit`](crate::MatchError::quit) when a DFA enters a quit
23 /// state.
24 /// * **Start** - A start state is a state in which a search can begin.
25 /// Lazy DFAs usually have more than one start state. Branching on
26 /// this isn't required for correctness, but a common optimization is
27 /// to run a prefilter when a search enters a start state. Note that
28 /// start states are *not* tagged automatically, and one must enable the
29 /// [`Config::specialize_start_states`](crate::hybrid::dfa::Config::specialize_start_states)
30 /// setting for start states to be tagged. The reason for this is
31 /// that a DFA search loop is usually written to execute a prefilter once it
32 /// enters a start state. But if there is no prefilter, this handling can be
33 /// quite diastrous as the DFA may ping-pong between the special handling code
34 /// and a possible optimized hot path for handling untagged states. When start
35 /// states aren't specialized, then they are untagged and remain in the hot
36 /// path.
37 /// * **Match** - A match state indicates that a match has been found.
38 /// Depending on the semantics of your search implementation, it may either
39 /// continue until the end of the haystack or a dead state, or it might quit
40 /// and return the match immediately.
41 ///
42 /// As an optimization, the [`is_tagged`](LazyStateID::is_tagged) predicate
43 /// can be used to determine if a tag exists at all. This is useful to avoid
44 /// branching on all of the above types for every byte searched.
45 ///
46 /// # Example
47 ///
48 /// This example shows how `LazyStateID` can be used to implement a correct
49 /// search routine with minimal branching. In particular, this search routine
50 /// implements "leftmost" matching, which means that it doesn't immediately
51 /// stop once a match is found. Instead, it continues until it reaches a dead
52 /// state.
53 ///
54 /// Notice also how a correct search implementation deals with
55 /// [`CacheError`](crate::hybrid::CacheError)s returned by some of
56 /// the lazy DFA routines. When a `CacheError` occurs, it returns
57 /// [`MatchError::gave_up`](crate::MatchError::gave_up).
58 ///
59 /// ```
60 /// use regex_automata::{
61 /// hybrid::dfa::{Cache, DFA},
62 /// HalfMatch, MatchError, Input,
63 /// };
64 ///
65 /// fn find_leftmost_first(
66 /// dfa: &DFA,
67 /// cache: &mut Cache,
68 /// haystack: &[u8],
69 /// ) -> Result<Option<HalfMatch>, MatchError> {
70 /// // The start state is determined by inspecting the position and the
71 /// // initial bytes of the haystack. Note that start states can never
72 /// // be match states (since DFAs in this crate delay matches by 1
73 /// // byte), so we don't need to check if the start state is a match.
74 /// let mut sid = dfa.start_state_forward(
75 /// cache,
76 /// &Input::new(haystack),
77 /// )?;
78 /// let mut last_match = None;
79 /// // Walk all the bytes in the haystack. We can quit early if we see
80 /// // a dead or a quit state. The former means the automaton will
81 /// // never transition to any other state. The latter means that the
82 /// // automaton entered a condition in which its search failed.
83 /// for (i, &b) in haystack.iter().enumerate() {
84 /// sid = dfa
85 /// .next_state(cache, sid, b)
86 /// .map_err(|_| MatchError::gave_up(i))?;
87 /// if sid.is_tagged() {
88 /// if sid.is_match() {
89 /// last_match = Some(HalfMatch::new(
90 /// dfa.match_pattern(cache, sid, 0),
91 /// i,
92 /// ));
93 /// } else if sid.is_dead() {
94 /// return Ok(last_match);
95 /// } else if sid.is_quit() {
96 /// // It is possible to enter into a quit state after
97 /// // observing a match has occurred. In that case, we
98 /// // should return the match instead of an error.
99 /// if last_match.is_some() {
100 /// return Ok(last_match);
101 /// }
102 /// return Err(MatchError::quit(b, i));
103 /// }
104 /// // Implementors may also want to check for start states and
105 /// // handle them differently for performance reasons. But it is
106 /// // not necessary for correctness. Note that in order to check
107 /// // for start states, you'll need to enable the
108 /// // 'specialize_start_states' config knob, otherwise start
109 /// // states will not be tagged.
110 /// }
111 /// }
112 /// // Matches are always delayed by 1 byte, so we must explicitly walk
113 /// // the special "EOI" transition at the end of the search.
114 /// sid = dfa
115 /// .next_eoi_state(cache, sid)
116 /// .map_err(|_| MatchError::gave_up(haystack.len()))?;
117 /// if sid.is_match() {
118 /// last_match = Some(HalfMatch::new(
119 /// dfa.match_pattern(cache, sid, 0),
120 /// haystack.len(),
121 /// ));
122 /// }
123 /// Ok(last_match)
124 /// }
125 ///
126 /// // We use a greedy '+' operator to show how the search doesn't just stop
127 /// // once a match is detected. It continues extending the match. Using
128 /// // '[a-z]+?' would also work as expected and stop the search early.
129 /// // Greediness is built into the automaton.
130 /// let dfa = DFA::new(r"[a-z]+")?;
131 /// let mut cache = dfa.create_cache();
132 /// let haystack = "123 foobar 4567".as_bytes();
133 /// let mat = find_leftmost_first(&dfa, &mut cache, haystack)?.unwrap();
134 /// assert_eq!(mat.pattern().as_usize(), 0);
135 /// assert_eq!(mat.offset(), 10);
136 ///
137 /// // Here's another example that tests our handling of the special
138 /// // EOI transition. This will fail to find a match if we don't call
139 /// // 'next_eoi_state' at the end of the search since the match isn't found
140 /// // until the final byte in the haystack.
141 /// let dfa = DFA::new(r"[0-9]{4}")?;
142 /// let mut cache = dfa.create_cache();
143 /// let haystack = "123 foobar 4567".as_bytes();
144 /// let mat = find_leftmost_first(&dfa, &mut cache, haystack)?.unwrap();
145 /// assert_eq!(mat.pattern().as_usize(), 0);
146 /// assert_eq!(mat.offset(), 15);
147 ///
148 /// // And note that our search implementation above automatically works
149 /// // with multi-DFAs. Namely, `dfa.match_pattern(match_state, 0)` selects
150 /// // the appropriate pattern ID for us.
151 /// let dfa = DFA::new_many(&[r"[a-z]+", r"[0-9]+"])?;
152 /// let mut cache = dfa.create_cache();
153 /// let haystack = "123 foobar 4567".as_bytes();
154 /// let mat = find_leftmost_first(&dfa, &mut cache, haystack)?.unwrap();
155 /// assert_eq!(mat.pattern().as_usize(), 1);
156 /// assert_eq!(mat.offset(), 3);
157 /// let mat = find_leftmost_first(&dfa, &mut cache, &haystack[3..])?.unwrap();
158 /// assert_eq!(mat.pattern().as_usize(), 0);
159 /// assert_eq!(mat.offset(), 7);
160 /// let mat = find_leftmost_first(&dfa, &mut cache, &haystack[10..])?.unwrap();
161 /// assert_eq!(mat.pattern().as_usize(), 1);
162 /// assert_eq!(mat.offset(), 5);
163 ///
164 /// # Ok::<(), Box<dyn std::error::Error>>(())
165 /// ```
166 #[derive(
167 Clone, Copy, Debug, Default, Eq, Hash, PartialEq, PartialOrd, Ord,
168 )]
169 pub struct LazyStateID(u32);
170
171 impl LazyStateID {
172 #[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
173 const MAX_BIT: usize = 31;
174
175 #[cfg(target_pointer_width = "16")]
176 const MAX_BIT: usize = 15;
177
178 const MASK_UNKNOWN: usize = 1 << (LazyStateID::MAX_BIT);
179 const MASK_DEAD: usize = 1 << (LazyStateID::MAX_BIT - 1);
180 const MASK_QUIT: usize = 1 << (LazyStateID::MAX_BIT - 2);
181 const MASK_START: usize = 1 << (LazyStateID::MAX_BIT - 3);
182 const MASK_MATCH: usize = 1 << (LazyStateID::MAX_BIT - 4);
183 const MAX: usize = LazyStateID::MASK_MATCH - 1;
184
185 /// Create a new lazy state ID.
186 ///
187 /// If the given identifier exceeds [`LazyStateID::MAX`], then this returns
188 /// an error.
189 #[inline]
190 pub(crate) fn new(id: usize) -> Result<LazyStateID, LazyStateIDError> {
191 if id > LazyStateID::MAX {
192 let attempted = u64::try_from(id).unwrap();
193 return Err(LazyStateIDError { attempted });
194 }
195 Ok(LazyStateID::new_unchecked(id))
196 }
197
198 /// Create a new lazy state ID without checking whether the given value
199 /// exceeds [`LazyStateID::MAX`].
200 ///
201 /// While this is unchecked, providing an incorrect value must never
202 /// sacrifice memory safety.
203 #[inline]
204 const fn new_unchecked(id: usize) -> LazyStateID {
205 // FIXME: Use as_u32() once const functions in traits are stable.
206 LazyStateID(id as u32)
207 }
208
209 /// Return this lazy state ID as an untagged `usize`.
210 ///
211 /// If this lazy state ID is tagged, then the usize returned is the state
212 /// ID without the tag. If the ID was not tagged, then the usize returned
213 /// is equivalent to the state ID.
214 #[inline]
215 pub(crate) fn as_usize_untagged(&self) -> usize {
216 self.as_usize_unchecked() & LazyStateID::MAX
217 }
218
219 /// Return this lazy state ID as its raw internal `usize` value, which may
220 /// be tagged (and thus greater than LazyStateID::MAX).
221 #[inline]
222 pub(crate) const fn as_usize_unchecked(&self) -> usize {
223 // FIXME: Use as_usize() once const functions in traits are stable.
224 self.0 as usize
225 }
226
227 #[inline]
228 pub(crate) const fn to_unknown(&self) -> LazyStateID {
229 LazyStateID::new_unchecked(
230 self.as_usize_unchecked() | LazyStateID::MASK_UNKNOWN,
231 )
232 }
233
234 #[inline]
235 pub(crate) const fn to_dead(&self) -> LazyStateID {
236 LazyStateID::new_unchecked(
237 self.as_usize_unchecked() | LazyStateID::MASK_DEAD,
238 )
239 }
240
241 #[inline]
242 pub(crate) const fn to_quit(&self) -> LazyStateID {
243 LazyStateID::new_unchecked(
244 self.as_usize_unchecked() | LazyStateID::MASK_QUIT,
245 )
246 }
247
248 /// Return this lazy state ID as a state ID that is tagged as a start
249 /// state.
250 #[inline]
251 pub(crate) const fn to_start(&self) -> LazyStateID {
252 LazyStateID::new_unchecked(
253 self.as_usize_unchecked() | LazyStateID::MASK_START,
254 )
255 }
256
257 /// Return this lazy state ID as a lazy state ID that is tagged as a match
258 /// state.
259 #[inline]
260 pub(crate) const fn to_match(&self) -> LazyStateID {
261 LazyStateID::new_unchecked(
262 self.as_usize_unchecked() | LazyStateID::MASK_MATCH,
263 )
264 }
265
266 /// Return true if and only if this lazy state ID is tagged.
267 ///
268 /// When a lazy state ID is tagged, then one can conclude that it is one
269 /// of a match, start, dead, quit or unknown state.
270 #[inline]
271 pub const fn is_tagged(&self) -> bool {
272 self.as_usize_unchecked() > LazyStateID::MAX
273 }
274
275 /// Return true if and only if this represents a lazy state ID that is
276 /// "unknown." That is, the state has not yet been created. When a caller
277 /// sees this state ID, it generally means that a state has to be computed
278 /// in order to proceed.
279 #[inline]
280 pub const fn is_unknown(&self) -> bool {
281 self.as_usize_unchecked() & LazyStateID::MASK_UNKNOWN > 0
282 }
283
284 /// Return true if and only if this represents a dead state. A dead state
285 /// is a state that can never transition to any other state except the
286 /// dead state. When a dead state is seen, it generally indicates that a
287 /// search should stop.
288 #[inline]
289 pub const fn is_dead(&self) -> bool {
290 self.as_usize_unchecked() & LazyStateID::MASK_DEAD > 0
291 }
292
293 /// Return true if and only if this represents a quit state. A quit state
294 /// is a state that is representationally equivalent to a dead state,
295 /// except it indicates the automaton has reached a point at which it can
296 /// no longer determine whether a match exists or not. In general, this
297 /// indicates an error during search and the caller must either pass this
298 /// error up or use a different search technique.
299 #[inline]
300 pub const fn is_quit(&self) -> bool {
301 self.as_usize_unchecked() & LazyStateID::MASK_QUIT > 0
302 }
303
304 /// Return true if and only if this lazy state ID has been tagged as a
305 /// start state.
306 ///
307 /// Note that if
308 /// [`Config::specialize_start_states`](crate::hybrid::dfa::Config) is
309 /// disabled (which is the default), then this will always return false
310 /// since start states won't be tagged.
311 #[inline]
312 pub const fn is_start(&self) -> bool {
313 self.as_usize_unchecked() & LazyStateID::MASK_START > 0
314 }
315
316 /// Return true if and only if this lazy state ID has been tagged as a
317 /// match state.
318 #[inline]
319 pub const fn is_match(&self) -> bool {
320 self.as_usize_unchecked() & LazyStateID::MASK_MATCH > 0
321 }
322 }
323
324 /// This error occurs when a lazy state ID could not be constructed.
325 ///
326 /// This occurs when given an integer exceeding the maximum lazy state ID
327 /// value.
328 ///
329 /// When the `std` feature is enabled, this implements the `Error` trait.
330 #[derive(Clone, Debug, Eq, PartialEq)]
331 pub(crate) struct LazyStateIDError {
332 attempted: u64,
333 }
334
335 impl LazyStateIDError {
336 /// Returns the value that failed to constructed a lazy state ID.
337 pub(crate) fn attempted(&self) -> u64 {
338 self.attempted
339 }
340 }
341
342 #[cfg(feature = "std")]
343 impl std::error::Error for LazyStateIDError {}
344
345 impl core::fmt::Display for LazyStateIDError {
346 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
347 write!(
348 f,
349 "failed to create LazyStateID from {:?}, which exceeds {:?}",
350 self.attempted(),
351 LazyStateID::MAX,
352 )
353 }
354 }