regex_automata/util/search.rs
1/*!
2Types and routines that support the search APIs of most regex engines.
3
4This sub-module isn't exposed directly, but rather, its contents are exported
5at the crate root due to the universality of most of the types and routines in
6this module.
7*/
8
9use core::ops::{Range, RangeBounds};
10
11use crate::util::{escape::DebugByte, primitives::PatternID, utf8};
12
13/// The parameters for a regex search including the haystack to search.
14///
15/// It turns out that regex searches have a few parameters, and in most cases,
16/// those parameters have defaults that work in the vast majority of cases.
17/// This `Input` type exists to make that common case seamless while also
18/// providing an avenue for changing the parameters of a search. In particular,
19/// this type enables doing so without a combinatorial explosion of different
20/// methods and/or superfluous parameters in the common cases.
21///
22/// An `Input` permits configuring the following things:
23///
24/// * Search only a substring of a haystack, while taking the broader context
25/// into account for resolving look-around assertions.
26/// * Indicating whether to search for all patterns in a regex, or to
27/// only search for one pattern in particular.
28/// * Whether to perform an anchored on unanchored search.
29/// * Whether to report a match as early as possible.
30///
31/// All of these parameters, except for the haystack, have sensible default
32/// values. This means that the minimal search configuration is simply a call
33/// to [`Input::new`] with your haystack. Setting any other parameter is
34/// optional.
35///
36/// Moreover, for any `H` that implements `AsRef<[u8]>`, there exists a
37/// `From<H> for Input` implementation. This is useful because many of the
38/// search APIs in this crate accept an `Into<Input>`. This means you can
39/// provide string or byte strings to these routines directly, and they'll
40/// automatically get converted into an `Input` for you.
41///
42/// The lifetime parameter `'h` refers to the lifetime of the haystack.
43///
44/// # Organization
45///
46/// The API of `Input` is split into a few different parts:
47///
48/// * A builder-like API that transforms a `Input` by value. Examples:
49/// [`Input::span`] and [`Input::anchored`].
50/// * A setter API that permits mutating parameters in place. Examples:
51/// [`Input::set_span`] and [`Input::set_anchored`].
52/// * A getter API that permits retrieving any of the search parameters.
53/// Examples: [`Input::get_span`] and [`Input::get_anchored`].
54/// * A few convenience getter routines that don't conform to the above naming
55/// pattern due to how common they are. Examples: [`Input::haystack`],
56/// [`Input::start`] and [`Input::end`].
57/// * Miscellaneous predicates and other helper routines that are useful
58/// in some contexts. Examples: [`Input::is_char_boundary`].
59///
60/// A `Input` exposes so much because it is meant to be used by both callers of
61/// regex engines _and_ implementors of regex engines. A constraining factor is
62/// that regex engines should accept a `&Input` as its lowest level API, which
63/// means that implementors should only use the "getter" APIs of a `Input`.
64///
65/// # Valid bounds and search termination
66///
67/// An `Input` permits setting the bounds of a search via either
68/// [`Input::span`] or [`Input::range`]. The bounds set must be valid, or
69/// else a panic will occur. Bounds are valid if and only if:
70///
71/// * The bounds represent a valid range into the input's haystack.
72/// * **or** the end bound is a valid ending bound for the haystack *and*
73/// the start bound is exactly one greater than the start bound.
74///
75/// In the latter case, [`Input::is_done`] will return true and indicates any
76/// search receiving such an input should immediately return with no match.
77///
78/// Note that while `Input` is used for reverse searches in this crate, the
79/// `Input::is_done` predicate assumes a forward search. Because unsigned
80/// offsets are used internally, there is no way to tell from only the offsets
81/// whether a reverse search is done or not.
82///
83/// # Regex engine support
84///
85/// Any regex engine accepting an `Input` must support at least the following
86/// things:
87///
88/// * Searching a `&[u8]` for matches.
89/// * Searching a substring of `&[u8]` for a match, such that any match
90/// reported must appear entirely within that substring.
91/// * For a forwards search, a match should never be reported when
92/// [`Input::is_done`] returns true. (For reverse searches, termination should
93/// be handled outside of `Input`.)
94///
95/// Supporting other aspects of an `Input` are optional, but regex engines
96/// should handle aspects they don't support gracefully. How this is done is
97/// generally up to the regex engine. This crate generally treats unsupported
98/// anchored modes as an error to report for example, but for simplicity, in
99/// the meta regex engine, trying to search with an invalid pattern ID just
100/// results in no match being reported.
101#[derive(Clone)]
102pub struct Input<'h> {
103 haystack: &'h [u8],
104 span: Span,
105 anchored: Anchored,
106 earliest: bool,
107}
108
109impl<'h> Input<'h> {
110 /// Create a new search configuration for the given haystack.
111 #[inline]
112 pub fn new<H: ?Sized + AsRef<[u8]>>(haystack: &'h H) -> Input<'h> {
113 // Perform only one call to `haystack.as_ref()` to protect from incorrect
114 // implementations that return different values from multiple calls.
115 // This is important because there's code that relies on `span` not being
116 // out of bounds with respect to the stored `haystack`.
117 let haystack = haystack.as_ref();
118 Input {
119 haystack,
120 span: Span { start: 0, end: haystack.len() },
121 anchored: Anchored::No,
122 earliest: false,
123 }
124 }
125
126 /// Set the span for this search.
127 ///
128 /// This routine does not panic if the span given is not a valid range for
129 /// this search's haystack. If this search is run with an invalid range,
130 /// then the most likely outcome is that the actual search execution will
131 /// panic.
132 ///
133 /// This routine is generic over how a span is provided. While
134 /// a [`Span`] may be given directly, one may also provide a
135 /// `std::ops::Range<usize>`. To provide anything supported by range
136 /// syntax, use the [`Input::range`] method.
137 ///
138 /// The default span is the entire haystack.
139 ///
140 /// Note that [`Input::range`] overrides this method and vice versa.
141 ///
142 /// # Panics
143 ///
144 /// This panics if the given span does not correspond to valid bounds in
145 /// the haystack or the termination of a search.
146 ///
147 /// # Example
148 ///
149 /// This example shows how the span of the search can impact whether a
150 /// match is reported or not. This is particularly relevant for look-around
151 /// operators, which might take things outside of the span into account
152 /// when determining whether they match.
153 ///
154 /// ```
155 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
156 /// use regex_automata::{
157 /// nfa::thompson::pikevm::PikeVM,
158 /// Match, Input,
159 /// };
160 ///
161 /// // Look for 'at', but as a distinct word.
162 /// let re = PikeVM::new(r"\bat\b")?;
163 /// let mut cache = re.create_cache();
164 /// let mut caps = re.create_captures();
165 ///
166 /// // Our haystack contains 'at', but not as a distinct word.
167 /// let haystack = "batter";
168 ///
169 /// // A standard search finds nothing, as expected.
170 /// let input = Input::new(haystack);
171 /// re.search(&mut cache, &input, &mut caps);
172 /// assert_eq!(None, caps.get_match());
173 ///
174 /// // But if we wanted to search starting at position '1', we might
175 /// // slice the haystack. If we do this, it's impossible for the \b
176 /// // anchors to take the surrounding context into account! And thus,
177 /// // a match is produced.
178 /// let input = Input::new(&haystack[1..3]);
179 /// re.search(&mut cache, &input, &mut caps);
180 /// assert_eq!(Some(Match::must(0, 0..2)), caps.get_match());
181 ///
182 /// // But if we specify the span of the search instead of slicing the
183 /// // haystack, then the regex engine can "see" outside of the span
184 /// // and resolve the anchors correctly.
185 /// let input = Input::new(haystack).span(1..3);
186 /// re.search(&mut cache, &input, &mut caps);
187 /// assert_eq!(None, caps.get_match());
188 ///
189 /// # Ok::<(), Box<dyn std::error::Error>>(())
190 /// ```
191 ///
192 /// This may seem a little ham-fisted, but this scenario tends to come up
193 /// if some other regex engine found the match span and now you need to
194 /// re-process that span to look for capturing groups. (e.g., Run a faster
195 /// DFA first, find a match, then run the PikeVM on just the match span to
196 /// resolve capturing groups.) In order to implement that sort of logic
197 /// correctly, you need to set the span on the search instead of slicing
198 /// the haystack directly.
199 ///
200 /// The other advantage of using this routine to specify the bounds of the
201 /// search is that the match offsets are still reported in terms of the
202 /// original haystack. For example, the second search in the example above
203 /// reported a match at position `0`, even though `at` starts at offset
204 /// `1` because we sliced the haystack.
205 #[inline]
206 pub fn span<S: Into<Span>>(mut self, span: S) -> Input<'h> {
207 self.set_span(span);
208 self
209 }
210
211 /// Like `Input::span`, but accepts any range instead.
212 ///
213 /// This routine does not panic if the range given is not a valid range for
214 /// this search's haystack. If this search is run with an invalid range,
215 /// then the most likely outcome is that the actual search execution will
216 /// panic.
217 ///
218 /// The default range is the entire haystack.
219 ///
220 /// Note that [`Input::span`] overrides this method and vice versa.
221 ///
222 /// # Panics
223 ///
224 /// This routine will panic if the given range could not be converted
225 /// to a valid [`Range`]. For example, this would panic when given
226 /// `0..=usize::MAX` since it cannot be represented using a half-open
227 /// interval in terms of `usize`.
228 ///
229 /// This also panics if the given range does not correspond to valid bounds
230 /// in the haystack or the termination of a search.
231 ///
232 /// # Example
233 ///
234 /// ```
235 /// use regex_automata::Input;
236 ///
237 /// let input = Input::new("foobar");
238 /// assert_eq!(0..6, input.get_range());
239 ///
240 /// let input = Input::new("foobar").range(2..=4);
241 /// assert_eq!(2..5, input.get_range());
242 /// ```
243 #[inline]
244 pub fn range<R: RangeBounds<usize>>(mut self, range: R) -> Input<'h> {
245 self.set_range(range);
246 self
247 }
248
249 /// Sets the anchor mode of a search.
250 ///
251 /// When a search is anchored (so that's [`Anchored::Yes`] or
252 /// [`Anchored::Pattern`]), a match must begin at the start of a search.
253 /// When a search is not anchored (that's [`Anchored::No`]), regex engines
254 /// will behave as if the pattern started with a `(?s-u:.)*?`. This prefix
255 /// permits a match to appear anywhere.
256 ///
257 /// By default, the anchored mode is [`Anchored::No`].
258 ///
259 /// **WARNING:** this is subtly different than using a `^` at the start of
260 /// your regex. A `^` forces a regex to match exclusively at the start of
261 /// a haystack, regardless of where you begin your search. In contrast,
262 /// anchoring a search will allow your regex to match anywhere in your
263 /// haystack, but the match must start at the beginning of a search.
264 ///
265 /// For example, consider the haystack `aba` and the following searches:
266 ///
267 /// 1. The regex `^a` is compiled with `Anchored::No` and searches `aba`
268 /// starting at position `2`. Since `^` requires the match to start at
269 /// the beginning of the haystack and `2 > 0`, no match is found.
270 /// 2. The regex `a` is compiled with `Anchored::Yes` and searches `aba`
271 /// starting at position `2`. This reports a match at `[2, 3]` since
272 /// the match starts where the search started. Since there is no `^`,
273 /// there is no requirement for the match to start at the beginning of
274 /// the haystack.
275 /// 3. The regex `a` is compiled with `Anchored::Yes` and searches `aba`
276 /// starting at position `1`. Since `b` corresponds to position `1` and
277 /// since the search is anchored, it finds no match. While the regex
278 /// matches at other positions, configuring the search to be anchored
279 /// requires that it only report a match that begins at the same offset
280 /// as the beginning of the search.
281 /// 4. The regex `a` is compiled with `Anchored::No` and searches `aba`
282 /// starting at position `1`. Since the search is not anchored and
283 /// the regex does not start with `^`, the search executes as if there
284 /// is a `(?s:.)*?` prefix that permits it to match anywhere. Thus, it
285 /// reports a match at `[2, 3]`.
286 ///
287 /// Note that the [`Anchored::Pattern`] mode is like `Anchored::Yes`,
288 /// except it only reports matches for a particular pattern.
289 ///
290 /// # Example
291 ///
292 /// This demonstrates the differences between an anchored search and
293 /// a pattern that begins with `^` (as described in the above warning
294 /// message).
295 ///
296 /// ```
297 /// use regex_automata::{
298 /// nfa::thompson::pikevm::PikeVM,
299 /// Anchored, Match, Input,
300 /// };
301 ///
302 /// let haystack = "aba";
303 ///
304 /// let re = PikeVM::new(r"^a")?;
305 /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
306 /// let input = Input::new(haystack).span(2..3).anchored(Anchored::No);
307 /// re.search(&mut cache, &input, &mut caps);
308 /// // No match is found because 2 is not the beginning of the haystack,
309 /// // which is what ^ requires.
310 /// assert_eq!(None, caps.get_match());
311 ///
312 /// let re = PikeVM::new(r"a")?;
313 /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
314 /// let input = Input::new(haystack).span(2..3).anchored(Anchored::Yes);
315 /// re.search(&mut cache, &input, &mut caps);
316 /// // An anchored search can still match anywhere in the haystack, it just
317 /// // must begin at the start of the search which is '2' in this case.
318 /// assert_eq!(Some(Match::must(0, 2..3)), caps.get_match());
319 ///
320 /// let re = PikeVM::new(r"a")?;
321 /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
322 /// let input = Input::new(haystack).span(1..3).anchored(Anchored::Yes);
323 /// re.search(&mut cache, &input, &mut caps);
324 /// // No match is found since we start searching at offset 1 which
325 /// // corresponds to 'b'. Since there is no '(?s:.)*?' prefix, no match
326 /// // is found.
327 /// assert_eq!(None, caps.get_match());
328 ///
329 /// let re = PikeVM::new(r"a")?;
330 /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
331 /// let input = Input::new(haystack).span(1..3).anchored(Anchored::No);
332 /// re.search(&mut cache, &input, &mut caps);
333 /// // Since anchored=no, an implicit '(?s:.)*?' prefix was added to the
334 /// // pattern. Even though the search starts at 'b', the 'match anything'
335 /// // prefix allows the search to match 'a'.
336 /// let expected = Some(Match::must(0, 2..3));
337 /// assert_eq!(expected, caps.get_match());
338 ///
339 /// # Ok::<(), Box<dyn std::error::Error>>(())
340 /// ```
341 #[inline]
342 pub fn anchored(mut self, mode: Anchored) -> Input<'h> {
343 self.set_anchored(mode);
344 self
345 }
346
347 /// Whether to execute an "earliest" search or not.
348 ///
349 /// When running a non-overlapping search, an "earliest" search will return
350 /// the match location as early as possible. For example, given a pattern
351 /// of `foo[0-9]+` and a haystack of `foo12345`, a normal leftmost search
352 /// will return `foo12345` as a match. But an "earliest" search for regex
353 /// engines that support "earliest" semantics will return `foo1` as a
354 /// match, since as soon as the first digit following `foo` is seen, it is
355 /// known to have found a match.
356 ///
357 /// Note that "earliest" semantics generally depend on the regex engine.
358 /// Different regex engines may determine there is a match at different
359 /// points. So there is no guarantee that "earliest" matches will always
360 /// return the same offsets for all regex engines. The "earliest" notion
361 /// is really about when the particular regex engine determines there is
362 /// a match rather than a consistent semantic unto itself. This is often
363 /// useful for implementing "did a match occur or not" predicates, but
364 /// sometimes the offset is useful as well.
365 ///
366 /// This is disabled by default.
367 ///
368 /// # Example
369 ///
370 /// This example shows the difference between "earliest" searching and
371 /// normal searching.
372 ///
373 /// ```
374 /// use regex_automata::{nfa::thompson::pikevm::PikeVM, Match, Input};
375 ///
376 /// let re = PikeVM::new(r"foo[0-9]+")?;
377 /// let mut cache = re.create_cache();
378 /// let mut caps = re.create_captures();
379 ///
380 /// // A normal search implements greediness like you expect.
381 /// let input = Input::new("foo12345");
382 /// re.search(&mut cache, &input, &mut caps);
383 /// assert_eq!(Some(Match::must(0, 0..8)), caps.get_match());
384 ///
385 /// // When 'earliest' is enabled and the regex engine supports
386 /// // it, the search will bail once it knows a match has been
387 /// // found.
388 /// let input = Input::new("foo12345").earliest(true);
389 /// re.search(&mut cache, &input, &mut caps);
390 /// assert_eq!(Some(Match::must(0, 0..4)), caps.get_match());
391 /// # Ok::<(), Box<dyn std::error::Error>>(())
392 /// ```
393 #[inline]
394 pub fn earliest(mut self, yes: bool) -> Input<'h> {
395 self.set_earliest(yes);
396 self
397 }
398
399 /// Set the span for this search configuration.
400 ///
401 /// This is like the [`Input::span`] method, except this mutates the
402 /// span in place.
403 ///
404 /// This routine is generic over how a span is provided. While
405 /// a [`Span`] may be given directly, one may also provide a
406 /// `std::ops::Range<usize>`.
407 ///
408 /// # Panics
409 ///
410 /// This panics if the given span does not correspond to valid bounds in
411 /// the haystack or the termination of a search.
412 ///
413 /// # Example
414 ///
415 /// ```
416 /// use regex_automata::Input;
417 ///
418 /// let mut input = Input::new("foobar");
419 /// assert_eq!(0..6, input.get_range());
420 /// input.set_span(2..4);
421 /// assert_eq!(2..4, input.get_range());
422 /// ```
423 #[inline]
424 pub fn set_span<S: Into<Span>>(&mut self, span: S) {
425 let span = span.into();
426 assert!(
427 span.end <= self.haystack.len()
428 && span.start <= span.end.wrapping_add(1),
429 "invalid span {:?} for haystack of length {}",
430 span,
431 self.haystack.len(),
432 );
433 self.span = span;
434 }
435
436 /// Set the span for this search configuration given any range.
437 ///
438 /// This is like the [`Input::range`] method, except this mutates the
439 /// span in place.
440 ///
441 /// This routine does not panic if the range given is not a valid range for
442 /// this search's haystack. If this search is run with an invalid range,
443 /// then the most likely outcome is that the actual search execution will
444 /// panic.
445 ///
446 /// # Panics
447 ///
448 /// This routine will panic if the given range could not be converted
449 /// to a valid [`Range`]. For example, this would panic when given
450 /// `0..=usize::MAX` since it cannot be represented using a half-open
451 /// interval in terms of `usize`.
452 ///
453 /// This also panics if the given span does not correspond to valid bounds
454 /// in the haystack or the termination of a search.
455 ///
456 /// # Example
457 ///
458 /// ```
459 /// use regex_automata::Input;
460 ///
461 /// let mut input = Input::new("foobar");
462 /// assert_eq!(0..6, input.get_range());
463 /// input.set_range(2..=4);
464 /// assert_eq!(2..5, input.get_range());
465 /// ```
466 #[inline]
467 pub fn set_range<R: RangeBounds<usize>>(&mut self, range: R) {
468 use core::ops::Bound;
469
470 // It's a little weird to convert ranges into spans, and then spans
471 // back into ranges when we actually slice the haystack. Because
472 // of that process, we always represent everything as a half-open
473 // internal. Therefore, handling things like m..=n is a little awkward.
474 let start = match range.start_bound() {
475 Bound::Included(&i) => i,
476 // Can this case ever happen? Range syntax doesn't support it...
477 Bound::Excluded(&i) => i.checked_add(1).unwrap(),
478 Bound::Unbounded => 0,
479 };
480 let end = match range.end_bound() {
481 Bound::Included(&i) => i.checked_add(1).unwrap(),
482 Bound::Excluded(&i) => i,
483 Bound::Unbounded => self.haystack().len(),
484 };
485 self.set_span(Span { start, end });
486 }
487
488 /// Set the starting offset for the span for this search configuration.
489 ///
490 /// This is a convenience routine for only mutating the start of a span
491 /// without having to set the entire span.
492 ///
493 /// # Panics
494 ///
495 /// This panics if the span resulting from the new start position does not
496 /// correspond to valid bounds in the haystack or the termination of a
497 /// search.
498 ///
499 /// # Example
500 ///
501 /// ```
502 /// use regex_automata::Input;
503 ///
504 /// let mut input = Input::new("foobar");
505 /// assert_eq!(0..6, input.get_range());
506 /// input.set_start(5);
507 /// assert_eq!(5..6, input.get_range());
508 /// ```
509 #[inline]
510 pub fn set_start(&mut self, start: usize) {
511 self.set_span(Span { start, ..self.get_span() });
512 }
513
514 /// Set the ending offset for the span for this search configuration.
515 ///
516 /// This is a convenience routine for only mutating the end of a span
517 /// without having to set the entire span.
518 ///
519 /// # Panics
520 ///
521 /// This panics if the span resulting from the new end position does not
522 /// correspond to valid bounds in the haystack or the termination of a
523 /// search.
524 ///
525 /// # Example
526 ///
527 /// ```
528 /// use regex_automata::Input;
529 ///
530 /// let mut input = Input::new("foobar");
531 /// assert_eq!(0..6, input.get_range());
532 /// input.set_end(5);
533 /// assert_eq!(0..5, input.get_range());
534 /// ```
535 #[inline]
536 pub fn set_end(&mut self, end: usize) {
537 self.set_span(Span { end, ..self.get_span() });
538 }
539
540 /// Set the anchor mode of a search.
541 ///
542 /// This is like [`Input::anchored`], except it mutates the search
543 /// configuration in place.
544 ///
545 /// # Example
546 ///
547 /// ```
548 /// use regex_automata::{Anchored, Input, PatternID};
549 ///
550 /// let mut input = Input::new("foobar");
551 /// assert_eq!(Anchored::No, input.get_anchored());
552 ///
553 /// let pid = PatternID::must(5);
554 /// input.set_anchored(Anchored::Pattern(pid));
555 /// assert_eq!(Anchored::Pattern(pid), input.get_anchored());
556 /// ```
557 #[inline]
558 pub fn set_anchored(&mut self, mode: Anchored) {
559 self.anchored = mode;
560 }
561
562 /// Set whether the search should execute in "earliest" mode or not.
563 ///
564 /// This is like [`Input::earliest`], except it mutates the search
565 /// configuration in place.
566 ///
567 /// # Example
568 ///
569 /// ```
570 /// use regex_automata::Input;
571 ///
572 /// let mut input = Input::new("foobar");
573 /// assert!(!input.get_earliest());
574 /// input.set_earliest(true);
575 /// assert!(input.get_earliest());
576 /// ```
577 #[inline]
578 pub fn set_earliest(&mut self, yes: bool) {
579 self.earliest = yes;
580 }
581
582 /// Return a borrow of the underlying haystack as a slice of bytes.
583 ///
584 /// # Example
585 ///
586 /// ```
587 /// use regex_automata::Input;
588 ///
589 /// let input = Input::new("foobar");
590 /// assert_eq!(b"foobar", input.haystack());
591 /// ```
592 #[inline]
593 pub fn haystack(&self) -> &'h [u8] {
594 self.haystack
595 }
596
597 /// Return the start position of this search.
598 ///
599 /// This is a convenience routine for `search.get_span().start()`.
600 ///
601 /// When [`Input::is_done`] is `false`, this is guaranteed to return
602 /// an offset that is less than or equal to [`Input::end`]. Otherwise,
603 /// the offset is one greater than [`Input::end`].
604 ///
605 /// # Example
606 ///
607 /// ```
608 /// use regex_automata::Input;
609 ///
610 /// let input = Input::new("foobar");
611 /// assert_eq!(0, input.start());
612 ///
613 /// let input = Input::new("foobar").span(2..4);
614 /// assert_eq!(2, input.start());
615 /// ```
616 #[inline]
617 pub fn start(&self) -> usize {
618 self.get_span().start
619 }
620
621 /// Return the end position of this search.
622 ///
623 /// This is a convenience routine for `search.get_span().end()`.
624 ///
625 /// This is guaranteed to return an offset that is a valid exclusive end
626 /// bound for this input's haystack.
627 ///
628 /// # Example
629 ///
630 /// ```
631 /// use regex_automata::Input;
632 ///
633 /// let input = Input::new("foobar");
634 /// assert_eq!(6, input.end());
635 ///
636 /// let input = Input::new("foobar").span(2..4);
637 /// assert_eq!(4, input.end());
638 /// ```
639 #[inline]
640 pub fn end(&self) -> usize {
641 self.get_span().end
642 }
643
644 /// Return the span for this search configuration.
645 ///
646 /// If one was not explicitly set, then the span corresponds to the entire
647 /// range of the haystack.
648 ///
649 /// When [`Input::is_done`] is `false`, the span returned is guaranteed
650 /// to correspond to valid bounds for this input's haystack.
651 ///
652 /// # Example
653 ///
654 /// ```
655 /// use regex_automata::{Input, Span};
656 ///
657 /// let input = Input::new("foobar");
658 /// assert_eq!(Span { start: 0, end: 6 }, input.get_span());
659 /// ```
660 #[inline]
661 pub fn get_span(&self) -> Span {
662 self.span
663 }
664
665 /// Return the span as a range for this search configuration.
666 ///
667 /// If one was not explicitly set, then the span corresponds to the entire
668 /// range of the haystack.
669 ///
670 /// When [`Input::is_done`] is `false`, the range returned is guaranteed
671 /// to correspond to valid bounds for this input's haystack.
672 ///
673 /// # Example
674 ///
675 /// ```
676 /// use regex_automata::Input;
677 ///
678 /// let input = Input::new("foobar");
679 /// assert_eq!(0..6, input.get_range());
680 /// ```
681 #[inline]
682 pub fn get_range(&self) -> Range<usize> {
683 self.get_span().range()
684 }
685
686 /// Return the anchored mode for this search configuration.
687 ///
688 /// If no anchored mode was set, then it defaults to [`Anchored::No`].
689 ///
690 /// # Example
691 ///
692 /// ```
693 /// use regex_automata::{Anchored, Input, PatternID};
694 ///
695 /// let mut input = Input::new("foobar");
696 /// assert_eq!(Anchored::No, input.get_anchored());
697 ///
698 /// let pid = PatternID::must(5);
699 /// input.set_anchored(Anchored::Pattern(pid));
700 /// assert_eq!(Anchored::Pattern(pid), input.get_anchored());
701 /// ```
702 #[inline]
703 pub fn get_anchored(&self) -> Anchored {
704 self.anchored
705 }
706
707 /// Return whether this search should execute in "earliest" mode.
708 ///
709 /// # Example
710 ///
711 /// ```
712 /// use regex_automata::Input;
713 ///
714 /// let input = Input::new("foobar");
715 /// assert!(!input.get_earliest());
716 /// ```
717 #[inline]
718 pub fn get_earliest(&self) -> bool {
719 self.earliest
720 }
721
722 /// Return true if and only if this search can never return any other
723 /// matches.
724 ///
725 /// This occurs when the start position of this search is greater than the
726 /// end position of the search.
727 ///
728 /// # Example
729 ///
730 /// ```
731 /// use regex_automata::Input;
732 ///
733 /// let mut input = Input::new("foobar");
734 /// assert!(!input.is_done());
735 /// input.set_start(6);
736 /// assert!(!input.is_done());
737 /// input.set_start(7);
738 /// assert!(input.is_done());
739 /// ```
740 #[inline]
741 pub fn is_done(&self) -> bool {
742 self.get_span().start > self.get_span().end
743 }
744
745 /// Returns true if and only if the given offset in this search's haystack
746 /// falls on a valid UTF-8 encoded codepoint boundary.
747 ///
748 /// If the haystack is not valid UTF-8, then the behavior of this routine
749 /// is unspecified.
750 ///
751 /// # Example
752 ///
753 /// This shows where codepoint boundaries do and don't exist in valid
754 /// UTF-8.
755 ///
756 /// ```
757 /// use regex_automata::Input;
758 ///
759 /// let input = Input::new("☃");
760 /// assert!(input.is_char_boundary(0));
761 /// assert!(!input.is_char_boundary(1));
762 /// assert!(!input.is_char_boundary(2));
763 /// assert!(input.is_char_boundary(3));
764 /// assert!(!input.is_char_boundary(4));
765 /// ```
766 #[inline]
767 pub fn is_char_boundary(&self, offset: usize) -> bool {
768 utf8::is_boundary(self.haystack(), offset)
769 }
770}
771
772impl<'h> core::fmt::Debug for Input<'h> {
773 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
774 use crate::util::escape::DebugHaystack;
775
776 f.debug_struct("Input")
777 .field("haystack", &DebugHaystack(self.haystack()))
778 .field("span", &self.span)
779 .field("anchored", &self.anchored)
780 .field("earliest", &self.earliest)
781 .finish()
782 }
783}
784
785impl<'h, H: ?Sized + AsRef<[u8]>> From<&'h H> for Input<'h> {
786 fn from(haystack: &'h H) -> Input<'h> {
787 Input::new(haystack)
788 }
789}
790
791/// A representation of a span reported by a regex engine.
792///
793/// A span corresponds to the starting and ending _byte offsets_ of a
794/// contiguous region of bytes. The starting offset is inclusive while the
795/// ending offset is exclusive. That is, a span is a half-open interval.
796///
797/// A span is used to report the offsets of a match, but it is also used to
798/// convey which region of a haystack should be searched via routines like
799/// [`Input::span`].
800///
801/// This is basically equivalent to a `std::ops::Range<usize>`, except this
802/// type implements `Copy` which makes it more ergonomic to use in the context
803/// of this crate. Like a range, this implements `Index` for `[u8]` and `str`,
804/// and `IndexMut` for `[u8]`. For convenience, this also impls `From<Range>`,
805/// which means things like `Span::from(5..10)` work.
806#[derive(Clone, Copy, Eq, Hash, PartialEq)]
807pub struct Span {
808 /// The start offset of the span, inclusive.
809 pub start: usize,
810 /// The end offset of the span, exclusive.
811 pub end: usize,
812}
813
814impl Span {
815 /// Returns this span as a range.
816 #[inline]
817 pub fn range(&self) -> Range<usize> {
818 Range::from(*self)
819 }
820
821 /// Returns true when this span is empty. That is, when `start >= end`.
822 #[inline]
823 pub fn is_empty(&self) -> bool {
824 self.start >= self.end
825 }
826
827 /// Returns the length of this span.
828 ///
829 /// This returns `0` in precisely the cases that `is_empty` returns `true`.
830 #[inline]
831 pub fn len(&self) -> usize {
832 self.end.saturating_sub(self.start)
833 }
834
835 /// Returns true when the given offset is contained within this span.
836 ///
837 /// Note that an empty span contains no offsets and will always return
838 /// false.
839 #[inline]
840 pub fn contains(&self, offset: usize) -> bool {
841 !self.is_empty() && self.start <= offset && offset <= self.end
842 }
843
844 /// Returns a new span with `offset` added to this span's `start` and `end`
845 /// values.
846 ///
847 /// # Panics
848 ///
849 /// This panics if adding `offset` to either part of this `Span` would
850 /// result in overflow.
851 #[inline]
852 pub fn offset(&self, offset: usize) -> Span {
853 Span {
854 start: self
855 .start
856 .checked_add(offset)
857 .expect("Span::offset: start+offset overflowed usize"),
858 end: self
859 .end
860 .checked_add(offset)
861 .expect("Span::offset: end+offset overflowed usize"),
862 }
863 }
864}
865
866impl core::fmt::Debug for Span {
867 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
868 write!(f, "{}..{}", self.start, self.end)
869 }
870}
871
872impl core::ops::Index<Span> for [u8] {
873 type Output = [u8];
874
875 #[inline]
876 fn index(&self, index: Span) -> &[u8] {
877 &self[index.range()]
878 }
879}
880
881impl core::ops::IndexMut<Span> for [u8] {
882 #[inline]
883 fn index_mut(&mut self, index: Span) -> &mut [u8] {
884 &mut self[index.range()]
885 }
886}
887
888impl core::ops::Index<Span> for str {
889 type Output = str;
890
891 #[inline]
892 fn index(&self, index: Span) -> &str {
893 &self[index.range()]
894 }
895}
896
897impl From<Range<usize>> for Span {
898 #[inline]
899 fn from(range: Range<usize>) -> Span {
900 Span { start: range.start, end: range.end }
901 }
902}
903
904impl From<Span> for Range<usize> {
905 #[inline]
906 fn from(span: Span) -> Range<usize> {
907 Range { start: span.start, end: span.end }
908 }
909}
910
911impl PartialEq<Range<usize>> for Span {
912 #[inline]
913 fn eq(&self, range: &Range<usize>) -> bool {
914 self.start == range.start && self.end == range.end
915 }
916}
917
918impl PartialEq<Span> for Range<usize> {
919 #[inline]
920 fn eq(&self, span: &Span) -> bool {
921 self.start == span.start && self.end == span.end
922 }
923}
924
925/// A representation of "half" of a match reported by a DFA.
926///
927/// This is called a "half" match because it only includes the end location (or
928/// start location for a reverse search) of a match. This corresponds to the
929/// information that a single DFA scan can report. Getting the other half of
930/// the match requires a second scan with a reversed DFA.
931///
932/// A half match also includes the pattern that matched. The pattern is
933/// identified by an ID, which corresponds to its position (starting from `0`)
934/// relative to other patterns used to construct the corresponding DFA. If only
935/// a single pattern is provided to the DFA, then all matches are guaranteed to
936/// have a pattern ID of `0`.
937#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
938pub struct HalfMatch {
939 /// The pattern ID.
940 pattern: PatternID,
941 /// The offset of the match.
942 ///
943 /// For forward searches, the offset is exclusive. For reverse searches,
944 /// the offset is inclusive.
945 offset: usize,
946}
947
948impl HalfMatch {
949 /// Create a new half match from a pattern ID and a byte offset.
950 #[inline]
951 pub fn new(pattern: PatternID, offset: usize) -> HalfMatch {
952 HalfMatch { pattern, offset }
953 }
954
955 /// Create a new half match from a pattern ID and a byte offset.
956 ///
957 /// This is like [`HalfMatch::new`], but accepts a `usize` instead of a
958 /// [`PatternID`]. This panics if the given `usize` is not representable
959 /// as a `PatternID`.
960 #[inline]
961 pub fn must(pattern: usize, offset: usize) -> HalfMatch {
962 HalfMatch::new(PatternID::new(pattern).unwrap(), offset)
963 }
964
965 /// Returns the ID of the pattern that matched.
966 ///
967 /// The ID of a pattern is derived from the position in which it was
968 /// originally inserted into the corresponding DFA. The first pattern has
969 /// identifier `0`, and each subsequent pattern is `1`, `2` and so on.
970 #[inline]
971 pub fn pattern(&self) -> PatternID {
972 self.pattern
973 }
974
975 /// The position of the match.
976 ///
977 /// If this match was produced by a forward search, then the offset is
978 /// exclusive. If this match was produced by a reverse search, then the
979 /// offset is inclusive.
980 #[inline]
981 pub fn offset(&self) -> usize {
982 self.offset
983 }
984}
985
986/// A representation of a match reported by a regex engine.
987///
988/// A match has two essential pieces of information: the [`PatternID`] that
989/// matches, and the [`Span`] of the match in a haystack.
990///
991/// The pattern is identified by an ID, which corresponds to its position
992/// (starting from `0`) relative to other patterns used to construct the
993/// corresponding regex engine. If only a single pattern is provided, then all
994/// matches are guaranteed to have a pattern ID of `0`.
995///
996/// Every match reported by a regex engine guarantees that its span has its
997/// start offset as less than or equal to its end offset.
998#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
999pub struct Match {
1000 /// The pattern ID.
1001 pattern: PatternID,
1002 /// The underlying match span.
1003 span: Span,
1004}
1005
1006impl Match {
1007 /// Create a new match from a pattern ID and a span.
1008 ///
1009 /// This constructor is generic over how a span is provided. While
1010 /// a [`Span`] may be given directly, one may also provide a
1011 /// `std::ops::Range<usize>`.
1012 ///
1013 /// # Panics
1014 ///
1015 /// This panics if `end < start`.
1016 ///
1017 /// # Example
1018 ///
1019 /// This shows how to create a match for the first pattern in a regex
1020 /// object using convenient range syntax.
1021 ///
1022 /// ```
1023 /// use regex_automata::{Match, PatternID};
1024 ///
1025 /// let m = Match::new(PatternID::ZERO, 5..10);
1026 /// assert_eq!(0, m.pattern().as_usize());
1027 /// assert_eq!(5, m.start());
1028 /// assert_eq!(10, m.end());
1029 /// ```
1030 #[inline]
1031 pub fn new<S: Into<Span>>(pattern: PatternID, span: S) -> Match {
1032 let span: Span = span.into();
1033 assert!(span.start <= span.end, "invalid match span");
1034 Match { pattern, span }
1035 }
1036
1037 /// Create a new match from a pattern ID and a byte offset span.
1038 ///
1039 /// This constructor is generic over how a span is provided. While
1040 /// a [`Span`] may be given directly, one may also provide a
1041 /// `std::ops::Range<usize>`.
1042 ///
1043 /// This is like [`Match::new`], but accepts a `usize` instead of a
1044 /// [`PatternID`]. This panics if the given `usize` is not representable
1045 /// as a `PatternID`.
1046 ///
1047 /// # Panics
1048 ///
1049 /// This panics if `end < start` or if `pattern > PatternID::MAX`.
1050 ///
1051 /// # Example
1052 ///
1053 /// This shows how to create a match for the third pattern in a regex
1054 /// object using convenient range syntax.
1055 ///
1056 /// ```
1057 /// use regex_automata::Match;
1058 ///
1059 /// let m = Match::must(3, 5..10);
1060 /// assert_eq!(3, m.pattern().as_usize());
1061 /// assert_eq!(5, m.start());
1062 /// assert_eq!(10, m.end());
1063 /// ```
1064 #[inline]
1065 pub fn must<S: Into<Span>>(pattern: usize, span: S) -> Match {
1066 Match::new(PatternID::must(pattern), span)
1067 }
1068
1069 /// Returns the ID of the pattern that matched.
1070 ///
1071 /// The ID of a pattern is derived from the position in which it was
1072 /// originally inserted into the corresponding regex engine. The first
1073 /// pattern has identifier `0`, and each subsequent pattern is `1`, `2` and
1074 /// so on.
1075 #[inline]
1076 pub fn pattern(&self) -> PatternID {
1077 self.pattern
1078 }
1079
1080 /// The starting position of the match.
1081 ///
1082 /// This is a convenience routine for `Match::span().start`.
1083 #[inline]
1084 pub fn start(&self) -> usize {
1085 self.span().start
1086 }
1087
1088 /// The ending position of the match.
1089 ///
1090 /// This is a convenience routine for `Match::span().end`.
1091 #[inline]
1092 pub fn end(&self) -> usize {
1093 self.span().end
1094 }
1095
1096 /// Returns the match span as a range.
1097 ///
1098 /// This is a convenience routine for `Match::span().range()`.
1099 #[inline]
1100 pub fn range(&self) -> core::ops::Range<usize> {
1101 self.span().range()
1102 }
1103
1104 /// Returns the span for this match.
1105 #[inline]
1106 pub fn span(&self) -> Span {
1107 self.span
1108 }
1109
1110 /// Returns true when the span in this match is empty.
1111 ///
1112 /// An empty match can only be returned when the regex itself can match
1113 /// the empty string.
1114 #[inline]
1115 pub fn is_empty(&self) -> bool {
1116 self.span().is_empty()
1117 }
1118
1119 /// Returns the length of this match.
1120 ///
1121 /// This returns `0` in precisely the cases that `is_empty` returns `true`.
1122 #[inline]
1123 pub fn len(&self) -> usize {
1124 self.span().len()
1125 }
1126}
1127
1128/// A set of `PatternID`s.
1129///
1130/// A set of pattern identifiers is useful for recording which patterns have
1131/// matched a particular haystack. A pattern set _only_ includes pattern
1132/// identifiers. It does not include offset information.
1133///
1134/// # Example
1135///
1136/// This shows basic usage of a set.
1137///
1138/// ```
1139/// use regex_automata::{PatternID, PatternSet};
1140///
1141/// let pid1 = PatternID::must(5);
1142/// let pid2 = PatternID::must(8);
1143/// // Create a new empty set.
1144/// let mut set = PatternSet::new(10);
1145/// // Insert pattern IDs.
1146/// set.insert(pid1);
1147/// set.insert(pid2);
1148/// // Test membership.
1149/// assert!(set.contains(pid1));
1150/// assert!(set.contains(pid2));
1151/// // Get all members.
1152/// assert_eq!(
1153/// vec![5, 8],
1154/// set.iter().map(|p| p.as_usize()).collect::<Vec<usize>>(),
1155/// );
1156/// // Clear the set.
1157/// set.clear();
1158/// // Test that it is indeed empty.
1159/// assert!(set.is_empty());
1160/// ```
1161#[cfg(feature = "alloc")]
1162#[derive(Clone, Debug, Eq, PartialEq)]
1163pub struct PatternSet {
1164 /// The number of patterns set to 'true' in this set.
1165 len: usize,
1166 /// A map from PatternID to boolean of whether a pattern matches or not.
1167 ///
1168 /// This should probably be a bitset, but it's probably unlikely to matter
1169 /// much in practice.
1170 ///
1171 /// The main downside of this representation (and similarly for a bitset)
1172 /// is that iteration scales with the capacity of the set instead of
1173 /// the length of the set. This doesn't seem likely to be a problem in
1174 /// practice.
1175 ///
1176 /// Another alternative is to just use a 'SparseSet' for this. It does use
1177 /// more memory (quite a bit more), but that seems fine I think compared
1178 /// to the memory being used by the regex engine. The real hiccup with
1179 /// it is that it yields pattern IDs in the order they were inserted.
1180 /// Which is actually kind of nice, but at the time of writing, pattern
1181 /// IDs are yielded in ascending order in the regex crate RegexSet API.
1182 /// If we did change to 'SparseSet', we could provide an additional
1183 /// 'iter_match_order' iterator, but keep the ascending order one for
1184 /// compatibility.
1185 which: alloc::boxed::Box<[bool]>,
1186}
1187
1188#[cfg(feature = "alloc")]
1189impl PatternSet {
1190 /// Create a new set of pattern identifiers with the given capacity.
1191 ///
1192 /// The given capacity typically corresponds to (at least) the number of
1193 /// patterns in a compiled regex object.
1194 ///
1195 /// # Panics
1196 ///
1197 /// This panics if the given capacity exceeds [`PatternID::LIMIT`]. This is
1198 /// impossible if you use the `pattern_len()` method as defined on any of
1199 /// the regex engines in this crate. Namely, a regex will fail to build by
1200 /// returning an error if the number of patterns given to it exceeds the
1201 /// limit. Therefore, the number of patterns in a valid regex is always
1202 /// a correct capacity to provide here.
1203 pub fn new(capacity: usize) -> PatternSet {
1204 assert!(
1205 capacity <= PatternID::LIMIT,
1206 "pattern set capacity exceeds limit of {}",
1207 PatternID::LIMIT,
1208 );
1209 PatternSet {
1210 len: 0,
1211 which: alloc::vec![false; capacity].into_boxed_slice(),
1212 }
1213 }
1214
1215 /// Clear this set such that it contains no pattern IDs.
1216 pub fn clear(&mut self) {
1217 self.len = 0;
1218 for matched in self.which.iter_mut() {
1219 *matched = false;
1220 }
1221 }
1222
1223 /// Return true if and only if the given pattern identifier is in this set.
1224 pub fn contains(&self, pid: PatternID) -> bool {
1225 pid.as_usize() < self.capacity() && self.which[pid]
1226 }
1227
1228 /// Insert the given pattern identifier into this set and return `true` if
1229 /// the given pattern ID was not previously in this set.
1230 ///
1231 /// If the pattern identifier is already in this set, then this is a no-op.
1232 ///
1233 /// Use [`PatternSet::try_insert`] for a fallible version of this routine.
1234 ///
1235 /// # Panics
1236 ///
1237 /// This panics if this pattern set has insufficient capacity to
1238 /// store the given pattern ID.
1239 pub fn insert(&mut self, pid: PatternID) -> bool {
1240 self.try_insert(pid)
1241 .expect("PatternSet should have sufficient capacity")
1242 }
1243
1244 /// Insert the given pattern identifier into this set and return `true` if
1245 /// the given pattern ID was not previously in this set.
1246 ///
1247 /// If the pattern identifier is already in this set, then this is a no-op.
1248 ///
1249 /// # Errors
1250 ///
1251 /// This returns an error if this pattern set has insufficient capacity to
1252 /// store the given pattern ID.
1253 pub fn try_insert(
1254 &mut self,
1255 pid: PatternID,
1256 ) -> Result<bool, PatternSetInsertError> {
1257 if pid.as_usize() >= self.capacity() {
1258 return Err(PatternSetInsertError {
1259 attempted: pid,
1260 capacity: self.capacity(),
1261 });
1262 }
1263 if self.which[pid] {
1264 return Ok(false);
1265 }
1266 self.len += 1;
1267 self.which[pid] = true;
1268 Ok(true)
1269 }
1270
1271 /*
1272 // This is currently commented out because it is unused and it is unclear
1273 // whether it's useful or not. What's the harm in having it? When, if
1274 // we ever wanted to change our representation to a 'SparseSet', then
1275 // supporting this method would be a bit tricky. So in order to keep some
1276 // API evolution flexibility, we leave it out for now.
1277
1278 /// Remove the given pattern identifier from this set.
1279 ///
1280 /// If the pattern identifier was not previously in this set, then this
1281 /// does not change the set and returns `false`.
1282 ///
1283 /// # Panics
1284 ///
1285 /// This panics if `pid` exceeds the capacity of this set.
1286 pub fn remove(&mut self, pid: PatternID) -> bool {
1287 if !self.which[pid] {
1288 return false;
1289 }
1290 self.len -= 1;
1291 self.which[pid] = false;
1292 true
1293 }
1294 */
1295
1296 /// Return true if and only if this set has no pattern identifiers in it.
1297 pub fn is_empty(&self) -> bool {
1298 self.len() == 0
1299 }
1300
1301 /// Return true if and only if this set has the maximum number of pattern
1302 /// identifiers in the set. This occurs precisely when `PatternSet::len()
1303 /// == PatternSet::capacity()`.
1304 ///
1305 /// This particular property is useful to test because it may allow one to
1306 /// stop a search earlier than you might otherwise. Namely, if a search is
1307 /// only reporting which patterns match a haystack and if you know all of
1308 /// the patterns match at a given point, then there's no new information
1309 /// that can be learned by continuing the search. (Because a pattern set
1310 /// does not keep track of offset information.)
1311 pub fn is_full(&self) -> bool {
1312 self.len() == self.capacity()
1313 }
1314
1315 /// Returns the total number of pattern identifiers in this set.
1316 pub fn len(&self) -> usize {
1317 self.len
1318 }
1319
1320 /// Returns the total number of pattern identifiers that may be stored
1321 /// in this set.
1322 ///
1323 /// This is guaranteed to be less than or equal to [`PatternID::LIMIT`].
1324 ///
1325 /// Typically, the capacity of a pattern set matches the number of patterns
1326 /// in a regex object with which you are searching.
1327 pub fn capacity(&self) -> usize {
1328 self.which.len()
1329 }
1330
1331 /// Returns an iterator over all pattern identifiers in this set.
1332 ///
1333 /// The iterator yields pattern identifiers in ascending order, starting
1334 /// at zero.
1335 pub fn iter(&self) -> PatternSetIter<'_> {
1336 PatternSetIter { it: self.which.iter().enumerate() }
1337 }
1338}
1339
1340/// An error that occurs when a `PatternID` failed to insert into a
1341/// `PatternSet`.
1342///
1343/// An insert fails when the given `PatternID` exceeds the configured capacity
1344/// of the `PatternSet`.
1345///
1346/// This error is created by the [`PatternSet::try_insert`] routine.
1347#[cfg(feature = "alloc")]
1348#[derive(Clone, Debug)]
1349pub struct PatternSetInsertError {
1350 attempted: PatternID,
1351 capacity: usize,
1352}
1353
1354#[cfg(feature = "std")]
1355impl std::error::Error for PatternSetInsertError {}
1356
1357#[cfg(feature = "alloc")]
1358impl core::fmt::Display for PatternSetInsertError {
1359 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
1360 write!(
1361 f,
1362 "failed to insert pattern ID {} into pattern set \
1363 with insufficient capacity of {}",
1364 self.attempted.as_usize(),
1365 self.capacity,
1366 )
1367 }
1368}
1369
1370/// An iterator over all pattern identifiers in a [`PatternSet`].
1371///
1372/// The lifetime parameter `'a` refers to the lifetime of the pattern set being
1373/// iterated over.
1374///
1375/// This iterator is created by the [`PatternSet::iter`] method.
1376#[cfg(feature = "alloc")]
1377#[derive(Clone, Debug)]
1378pub struct PatternSetIter<'a> {
1379 it: core::iter::Enumerate<core::slice::Iter<'a, bool>>,
1380}
1381
1382#[cfg(feature = "alloc")]
1383impl<'a> Iterator for PatternSetIter<'a> {
1384 type Item = PatternID;
1385
1386 fn next(&mut self) -> Option<PatternID> {
1387 while let Some((index, &yes)) = self.it.next() {
1388 if yes {
1389 // Only valid 'PatternID' values can be inserted into the set
1390 // and construction of the set panics if the capacity would
1391 // permit storing invalid pattern IDs. Thus, 'yes' is only true
1392 // precisely when 'index' corresponds to a valid 'PatternID'.
1393 return Some(PatternID::new_unchecked(index));
1394 }
1395 }
1396 None
1397 }
1398
1399 fn size_hint(&self) -> (usize, Option<usize>) {
1400 self.it.size_hint()
1401 }
1402}
1403
1404#[cfg(feature = "alloc")]
1405impl<'a> DoubleEndedIterator for PatternSetIter<'a> {
1406 fn next_back(&mut self) -> Option<PatternID> {
1407 while let Some((index, &yes)) = self.it.next_back() {
1408 if yes {
1409 // Only valid 'PatternID' values can be inserted into the set
1410 // and construction of the set panics if the capacity would
1411 // permit storing invalid pattern IDs. Thus, 'yes' is only true
1412 // precisely when 'index' corresponds to a valid 'PatternID'.
1413 return Some(PatternID::new_unchecked(index));
1414 }
1415 }
1416 None
1417 }
1418}
1419
1420/// The type of anchored search to perform.
1421///
1422/// This is *almost* a boolean option. That is, you can either do an unanchored
1423/// search for any pattern in a regex, or you can do an anchored search for any
1424/// pattern in a regex.
1425///
1426/// A third option exists that, assuming the regex engine supports it, permits
1427/// you to do an anchored search for a specific pattern.
1428///
1429/// Note that there is no way to run an unanchored search for a specific
1430/// pattern. If you need that, you'll need to build separate regexes for each
1431/// pattern.
1432///
1433/// # Errors
1434///
1435/// If a regex engine does not support the anchored mode selected, then the
1436/// regex engine will return an error. While any non-trivial regex engine
1437/// should support at least one of the available anchored modes, there is no
1438/// singular mode that is guaranteed to be universally supported. Some regex
1439/// engines might only support unanchored searches (DFAs compiled without
1440/// anchored starting states) and some regex engines might only support
1441/// anchored searches (like the one-pass DFA).
1442///
1443/// The specific error returned is a [`MatchError`] with a
1444/// [`MatchErrorKind::UnsupportedAnchored`] kind. The kind includes the
1445/// `Anchored` value given that is unsupported.
1446///
1447/// Note that regex engines should report "no match" if, for example, an
1448/// `Anchored::Pattern` is provided with an invalid pattern ID _but_ where
1449/// anchored searches for a specific pattern are supported. This is smooths out
1450/// behavior such that it's possible to guarantee that an error never occurs
1451/// based on how the regex engine is configured. All regex engines in this
1452/// crate report "no match" when searching for an invalid pattern ID, but where
1453/// searching for a valid pattern ID is otherwise supported.
1454///
1455/// # Example
1456///
1457/// This example shows how to use the various `Anchored` modes to run a
1458/// search. We use the [`PikeVM`](crate::nfa::thompson::pikevm::PikeVM)
1459/// because it supports all modes unconditionally. Some regex engines, like
1460/// the [`onepass::DFA`](crate::dfa::onepass::DFA) cannot support unanchored
1461/// searches.
1462///
1463/// ```
1464/// # if cfg!(miri) { return Ok(()); } // miri takes too long
1465/// use regex_automata::{
1466/// nfa::thompson::pikevm::PikeVM,
1467/// Anchored, Input, Match, PatternID,
1468/// };
1469///
1470/// let re = PikeVM::new_many(&[
1471/// r"Mrs. \w+",
1472/// r"Miss \w+",
1473/// r"Mr. \w+",
1474/// r"Ms. \w+",
1475/// ])?;
1476/// let mut cache = re.create_cache();
1477/// let hay = "Hello Mr. Springsteen!";
1478///
1479/// // The default is to do an unanchored search.
1480/// assert_eq!(Some(Match::must(2, 6..21)), re.find(&mut cache, hay));
1481/// // Explicitly ask for an unanchored search. Same as above.
1482/// let input = Input::new(hay).anchored(Anchored::No);
1483/// assert_eq!(Some(Match::must(2, 6..21)), re.find(&mut cache, hay));
1484///
1485/// // Now try an anchored search. Since the match doesn't start at the
1486/// // beginning of the haystack, no match is found!
1487/// let input = Input::new(hay).anchored(Anchored::Yes);
1488/// assert_eq!(None, re.find(&mut cache, input));
1489///
1490/// // We can try an anchored search again, but move the location of where
1491/// // we start the search. Note that the offsets reported are still in
1492/// // terms of the overall haystack and not relative to where we started
1493/// // the search.
1494/// let input = Input::new(hay).anchored(Anchored::Yes).range(6..);
1495/// assert_eq!(Some(Match::must(2, 6..21)), re.find(&mut cache, input));
1496///
1497/// // Now try an anchored search for a specific pattern. We specifically
1498/// // choose a pattern that we know doesn't match to prove that the search
1499/// // only looks for the pattern we provide.
1500/// let input = Input::new(hay)
1501/// .anchored(Anchored::Pattern(PatternID::must(1)))
1502/// .range(6..);
1503/// assert_eq!(None, re.find(&mut cache, input));
1504///
1505/// // But if we switch it to the pattern that we know matches, then we find
1506/// // the match.
1507/// let input = Input::new(hay)
1508/// .anchored(Anchored::Pattern(PatternID::must(2)))
1509/// .range(6..);
1510/// assert_eq!(Some(Match::must(2, 6..21)), re.find(&mut cache, input));
1511///
1512/// # Ok::<(), Box<dyn std::error::Error>>(())
1513/// ```
1514#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1515pub enum Anchored {
1516 /// Run an unanchored search. This means a match may occur anywhere at or
1517 /// after the start position of the search.
1518 ///
1519 /// This search can return a match for any pattern in the regex.
1520 No,
1521 /// Run an anchored search. This means that a match must begin at the
1522 /// start position of the search.
1523 ///
1524 /// This search can return a match for any pattern in the regex.
1525 Yes,
1526 /// Run an anchored search for a specific pattern. This means that a match
1527 /// must be for the given pattern and must begin at the start position of
1528 /// the search.
1529 Pattern(PatternID),
1530}
1531
1532impl Anchored {
1533 /// Returns true if and only if this anchor mode corresponds to any kind of
1534 /// anchored search.
1535 ///
1536 /// # Example
1537 ///
1538 /// This examples shows that both `Anchored::Yes` and `Anchored::Pattern`
1539 /// are considered anchored searches.
1540 ///
1541 /// ```
1542 /// use regex_automata::{Anchored, PatternID};
1543 ///
1544 /// assert!(!Anchored::No.is_anchored());
1545 /// assert!(Anchored::Yes.is_anchored());
1546 /// assert!(Anchored::Pattern(PatternID::ZERO).is_anchored());
1547 /// ```
1548 #[inline]
1549 pub fn is_anchored(&self) -> bool {
1550 matches!(*self, Anchored::Yes | Anchored::Pattern(_))
1551 }
1552
1553 /// Returns the pattern ID associated with this configuration if it is an
1554 /// anchored search for a specific pattern. Otherwise `None` is returned.
1555 ///
1556 /// # Example
1557 ///
1558 /// ```
1559 /// use regex_automata::{Anchored, PatternID};
1560 ///
1561 /// assert_eq!(None, Anchored::No.pattern());
1562 /// assert_eq!(None, Anchored::Yes.pattern());
1563 ///
1564 /// let pid = PatternID::must(5);
1565 /// assert_eq!(Some(pid), Anchored::Pattern(pid).pattern());
1566 /// ```
1567 #[inline]
1568 pub fn pattern(&self) -> Option<PatternID> {
1569 match *self {
1570 Anchored::Pattern(pid) => Some(pid),
1571 _ => None,
1572 }
1573 }
1574}
1575
1576/// The kind of match semantics to use for a regex pattern.
1577///
1578/// The default match kind is `LeftmostFirst`, and this corresponds to the
1579/// match semantics used by most backtracking engines, such as Perl.
1580///
1581/// # Leftmost first or "preference order" match semantics
1582///
1583/// Leftmost-first semantics determine which match to report when there are
1584/// multiple paths through a regex that match at the same position. The tie is
1585/// essentially broken by how a backtracker would behave. For example, consider
1586/// running the regex `foofoofoo|foofoo|foo` on the haystack `foofoo`. In this
1587/// case, both the `foofoo` and `foo` branches match at position `0`. So should
1588/// the end of the match be `3` or `6`?
1589///
1590/// A backtracker will conceptually work by trying `foofoofoo` and failing.
1591/// Then it will try `foofoo`, find the match and stop there. Thus, the
1592/// leftmost-first match position is `6`. This is called "leftmost-first" or
1593/// "preference order" because the order of the branches as written in the
1594/// regex pattern is what determines how to break the tie.
1595///
1596/// (Note that leftmost-longest match semantics, which break ties by always
1597/// taking the longest matching string, are not currently supported by this
1598/// crate. These match semantics tend to be found in POSIX regex engines.)
1599///
1600/// This example shows how leftmost-first semantics work, and how it even
1601/// applies to multi-pattern regexes:
1602///
1603/// ```
1604/// use regex_automata::{
1605/// nfa::thompson::pikevm::PikeVM,
1606/// Match,
1607/// };
1608///
1609/// let re = PikeVM::new_many(&[
1610/// r"foofoofoo",
1611/// r"foofoo",
1612/// r"foo",
1613/// ])?;
1614/// let mut cache = re.create_cache();
1615/// let got: Vec<Match> = re.find_iter(&mut cache, "foofoo").collect();
1616/// let expected = vec![Match::must(1, 0..6)];
1617/// assert_eq!(expected, got);
1618///
1619/// # Ok::<(), Box<dyn std::error::Error>>(())
1620/// ```
1621///
1622/// # All matches
1623///
1624/// The `All` match semantics report any and all matches, and generally will
1625/// attempt to match as much as possible. It doesn't respect any sort of match
1626/// priority at all, so things like non-greedy matching don't work in this
1627/// mode.
1628///
1629/// The fact that non-greedy matching doesn't work generally makes most forms
1630/// of unanchored non-overlapping searches have unintuitive behavior. Namely,
1631/// unanchored searches behave as if there is a `(?s-u:.)*?` prefix at the
1632/// beginning of the pattern, which is specifically non-greedy. Since it will
1633/// be treated as greedy in `All` match semantics, this generally means that
1634/// it will first attempt to consume all of the haystack and is likely to wind
1635/// up skipping matches.
1636///
1637/// Generally speaking, `All` should only be used in two circumstances:
1638///
1639/// * When running an anchored search and there is a desire to match as much as
1640/// possible. For example, when building a reverse regex matcher to find the
1641/// start of a match after finding the end. In this case, the reverse search
1642/// is anchored to the end of the match found by the forward search.
1643/// * When running overlapping searches. Since `All` encodes all possible
1644/// matches, this is generally what you want for an overlapping search. If you
1645/// try to use leftmost-first in an overlapping search, it is likely to produce
1646/// counter-intuitive results since leftmost-first specifically excludes some
1647/// matches from its underlying finite state machine.
1648///
1649/// This example demonstrates the counter-intuitive behavior of `All` semantics
1650/// when using a standard leftmost unanchored search:
1651///
1652/// ```
1653/// use regex_automata::{
1654/// nfa::thompson::pikevm::PikeVM,
1655/// Match, MatchKind,
1656/// };
1657///
1658/// let re = PikeVM::builder()
1659/// .configure(PikeVM::config().match_kind(MatchKind::All))
1660/// .build("foo")?;
1661/// let hay = "first foo second foo wat";
1662/// let mut cache = re.create_cache();
1663/// let got: Vec<Match> = re.find_iter(&mut cache, hay).collect();
1664/// // Notice that it completely skips the first 'foo'!
1665/// let expected = vec![Match::must(0, 17..20)];
1666/// assert_eq!(expected, got);
1667///
1668/// # Ok::<(), Box<dyn std::error::Error>>(())
1669/// ```
1670///
1671/// This second example shows how `All` semantics are useful for an overlapping
1672/// search. Note that we use lower level lazy DFA APIs here since the NFA
1673/// engines only currently support a very limited form of overlapping search.
1674///
1675/// ```
1676/// use regex_automata::{
1677/// hybrid::dfa::{DFA, OverlappingState},
1678/// HalfMatch, Input, MatchKind,
1679/// };
1680///
1681/// let re = DFA::builder()
1682/// // If we didn't set 'All' semantics here, then the regex would only
1683/// // match 'foo' at offset 3 and nothing else. Why? Because the state
1684/// // machine implements preference order and knows that the 'foofoo' and
1685/// // 'foofoofoo' branches can never match since 'foo' will always match
1686/// // when they match and take priority.
1687/// .configure(DFA::config().match_kind(MatchKind::All))
1688/// .build(r"foo|foofoo|foofoofoo")?;
1689/// let mut cache = re.create_cache();
1690/// let mut state = OverlappingState::start();
1691/// let input = Input::new("foofoofoo");
1692/// let mut got = vec![];
1693/// loop {
1694/// re.try_search_overlapping_fwd(&mut cache, &input, &mut state)?;
1695/// let m = match state.get_match() {
1696/// None => break,
1697/// Some(m) => m,
1698/// };
1699/// got.push(m);
1700/// }
1701/// let expected = vec![
1702/// HalfMatch::must(0, 3),
1703/// HalfMatch::must(0, 6),
1704/// HalfMatch::must(0, 9),
1705/// ];
1706/// assert_eq!(expected, got);
1707///
1708/// # Ok::<(), Box<dyn std::error::Error>>(())
1709/// ```
1710#[non_exhaustive]
1711#[derive(Clone, Copy, Default, Debug, Eq, PartialEq)]
1712pub enum MatchKind {
1713 /// Report all possible matches.
1714 All,
1715 /// Report only the leftmost matches. When multiple leftmost matches exist,
1716 /// report the match corresponding to the part of the regex that appears
1717 /// first in the syntax.
1718 #[default]
1719 LeftmostFirst,
1720 // There is prior art in RE2 that shows that we should be able to add
1721 // LeftmostLongest too. The tricky part of it is supporting ungreedy
1722 // repetitions. Instead of treating all NFA states as having equivalent
1723 // priority (as in 'All') or treating all NFA states as having distinct
1724 // priority based on order (as in 'LeftmostFirst'), we instead group NFA
1725 // states into sets, and treat members of each set as having equivalent
1726 // priority, but having greater priority than all following members
1727 // of different sets.
1728 //
1729 // However, it's not clear whether it's really worth adding this. After
1730 // all, leftmost-longest can be emulated when using literals by using
1731 // leftmost-first and sorting the literals by length in descending order.
1732 // However, this won't work for arbitrary regexes. e.g., `\w|\w\w` will
1733 // always match `a` in `ab` when using leftmost-first, but leftmost-longest
1734 // would match `ab`.
1735}
1736
1737impl MatchKind {
1738 #[cfg(feature = "alloc")]
1739 pub(crate) fn continue_past_first_match(&self) -> bool {
1740 *self == MatchKind::All
1741 }
1742}
1743
1744/// An error indicating that a search stopped before reporting whether a
1745/// match exists or not.
1746///
1747/// To be very clear, this error type implies that one cannot assume that no
1748/// matches occur, since the search stopped before completing. That is, if
1749/// you're looking for information about where a search determined that no
1750/// match can occur, then this error type does *not* give you that. (Indeed, at
1751/// the time of writing, if you need such a thing, you have to write your own
1752/// search routine.)
1753///
1754/// Normally, when one searches for something, the response is either an
1755/// affirmative "it was found at this location" or a negative "not found at
1756/// all." However, in some cases, a regex engine can be configured to stop its
1757/// search before concluding whether a match exists or not. When this happens,
1758/// it may be important for the caller to know why the regex engine gave up and
1759/// where in the input it gave up at. This error type exposes the 'why' and the
1760/// 'where.'
1761///
1762/// For example, the DFAs provided by this library generally cannot correctly
1763/// implement Unicode word boundaries. Instead, they provide an option to
1764/// eagerly support them on ASCII text (since Unicode word boundaries are
1765/// equivalent to ASCII word boundaries when searching ASCII text), but will
1766/// "give up" if a non-ASCII byte is seen. In such cases, one is usually
1767/// required to either report the failure to the caller (unergonomic) or
1768/// otherwise fall back to some other regex engine (ergonomic, but potentially
1769/// costly).
1770///
1771/// More generally, some regex engines offer the ability for callers to specify
1772/// certain bytes that will trigger the regex engine to automatically quit if
1773/// they are seen.
1774///
1775/// Still yet, there may be other reasons for a failed match. For example,
1776/// the hybrid DFA provided by this crate can be configured to give up if it
1777/// believes that it is not efficient. This in turn permits callers to choose a
1778/// different regex engine.
1779///
1780/// (Note that DFAs are configured by default to never quit or give up in this
1781/// fashion. For example, by default, a DFA will fail to build if the regex
1782/// pattern contains a Unicode word boundary. One needs to opt into the "quit"
1783/// behavior via options, like
1784/// [`hybrid::dfa::Config::unicode_word_boundary`](crate::hybrid::dfa::Config::unicode_word_boundary).)
1785///
1786/// There are a couple other ways a search
1787/// can fail. For example, when using the
1788/// [`BoundedBacktracker`](crate::nfa::thompson::backtrack::BoundedBacktracker)
1789/// with a haystack that is too long, or trying to run an unanchored search
1790/// with a [one-pass DFA](crate::dfa::onepass).
1791#[derive(Clone, Debug, Eq, PartialEq)]
1792pub struct MatchError(
1793 #[cfg(feature = "alloc")] alloc::boxed::Box<MatchErrorKind>,
1794 #[cfg(not(feature = "alloc"))] MatchErrorKind,
1795);
1796
1797impl MatchError {
1798 /// Create a new error value with the given kind.
1799 ///
1800 /// This is a more verbose version of the kind-specific constructors,
1801 /// e.g., `MatchError::quit`.
1802 pub fn new(kind: MatchErrorKind) -> MatchError {
1803 #[cfg(feature = "alloc")]
1804 {
1805 MatchError(alloc::boxed::Box::new(kind))
1806 }
1807 #[cfg(not(feature = "alloc"))]
1808 {
1809 MatchError(kind)
1810 }
1811 }
1812
1813 /// Returns a reference to the underlying error kind.
1814 pub fn kind(&self) -> &MatchErrorKind {
1815 &self.0
1816 }
1817
1818 /// Create a new "quit" error. The given `byte` corresponds to the value
1819 /// that tripped a search's quit condition, and `offset` corresponds to the
1820 /// location in the haystack at which the search quit.
1821 ///
1822 /// This is the same as calling `MatchError::new` with a
1823 /// [`MatchErrorKind::Quit`] kind.
1824 pub fn quit(byte: u8, offset: usize) -> MatchError {
1825 MatchError::new(MatchErrorKind::Quit { byte, offset })
1826 }
1827
1828 /// Create a new "gave up" error. The given `offset` corresponds to the
1829 /// location in the haystack at which the search gave up.
1830 ///
1831 /// This is the same as calling `MatchError::new` with a
1832 /// [`MatchErrorKind::GaveUp`] kind.
1833 pub fn gave_up(offset: usize) -> MatchError {
1834 MatchError::new(MatchErrorKind::GaveUp { offset })
1835 }
1836
1837 /// Create a new "haystack too long" error. The given `len` corresponds to
1838 /// the length of the haystack that was problematic.
1839 ///
1840 /// This is the same as calling `MatchError::new` with a
1841 /// [`MatchErrorKind::HaystackTooLong`] kind.
1842 pub fn haystack_too_long(len: usize) -> MatchError {
1843 MatchError::new(MatchErrorKind::HaystackTooLong { len })
1844 }
1845
1846 /// Create a new "unsupported anchored" error. This occurs when the caller
1847 /// requests a search with an anchor mode that is not supported by the
1848 /// regex engine.
1849 ///
1850 /// This is the same as calling `MatchError::new` with a
1851 /// [`MatchErrorKind::UnsupportedAnchored`] kind.
1852 pub fn unsupported_anchored(mode: Anchored) -> MatchError {
1853 MatchError::new(MatchErrorKind::UnsupportedAnchored { mode })
1854 }
1855}
1856
1857/// The underlying kind of a [`MatchError`].
1858///
1859/// This is a **non-exhaustive** enum. That means new variants may be added in
1860/// a semver-compatible release.
1861#[non_exhaustive]
1862#[derive(Clone, Debug, Eq, PartialEq)]
1863pub enum MatchErrorKind {
1864 /// The search saw a "quit" byte at which it was instructed to stop
1865 /// searching.
1866 Quit {
1867 /// The "quit" byte that was observed that caused the search to stop.
1868 byte: u8,
1869 /// The offset at which the quit byte was observed.
1870 offset: usize,
1871 },
1872 /// The search, based on heuristics, determined that it would be better
1873 /// to stop, typically to provide the caller an opportunity to use an
1874 /// alternative regex engine.
1875 ///
1876 /// Currently, the only way for this to occur is via the lazy DFA and
1877 /// only when it is configured to do so (it will not return this error by
1878 /// default).
1879 GaveUp {
1880 /// The offset at which the search stopped. This corresponds to the
1881 /// position immediately following the last byte scanned.
1882 offset: usize,
1883 },
1884 /// This error occurs if the haystack given to the regex engine was too
1885 /// long to be searched. This occurs, for example, with regex engines
1886 /// like the bounded backtracker that have a configurable fixed amount of
1887 /// capacity that is tied to the length of the haystack. Anything beyond
1888 /// that configured limit will result in an error at search time.
1889 HaystackTooLong {
1890 /// The length of the haystack that exceeded the limit.
1891 len: usize,
1892 },
1893 /// An error indicating that a particular type of anchored search was
1894 /// requested, but that the regex engine does not support it.
1895 ///
1896 /// When this error occurs with [`Anchored::Pattern`], then one common
1897 /// cause is that the underlying regex engine was built without support
1898 /// for anchored starting states for each pattern. For DFA engines, this
1899 /// typically means enabling the
1900 /// [`hybrid::dfa::Config::starts_for_each_pattern`](crate::hybrid::dfa::Config::starts_for_each_pattern)
1901 /// or
1902 /// [`dfa::dense::Config::starts_for_each_pattern`](crate::dfa::dense::Config::starts_for_each_pattern)
1903 /// configuration option, depending on which regex engine is being built.
1904 ///
1905 /// Note that this error should not be returned by a regex engine simply
1906 /// because the pattern ID is invalid (i.e., equal to or exceeds the number
1907 /// of patterns in the regex). In that case, the regex engine should report
1908 /// a non-match.
1909 UnsupportedAnchored {
1910 /// The anchored mode given that is unsupported.
1911 mode: Anchored,
1912 },
1913}
1914
1915#[cfg(feature = "std")]
1916impl std::error::Error for MatchError {}
1917
1918impl core::fmt::Display for MatchError {
1919 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
1920 match *self.kind() {
1921 MatchErrorKind::Quit { byte, offset } => write!(
1922 f,
1923 "quit search after observing byte {:?} at offset {}",
1924 DebugByte(byte),
1925 offset,
1926 ),
1927 MatchErrorKind::GaveUp { offset } => {
1928 write!(f, "gave up searching at offset {offset}")
1929 }
1930 MatchErrorKind::HaystackTooLong { len } => {
1931 write!(f, "haystack of length {len} is too long")
1932 }
1933 MatchErrorKind::UnsupportedAnchored { mode: Anchored::Yes } => {
1934 write!(f, "anchored searches are not supported or enabled")
1935 }
1936 MatchErrorKind::UnsupportedAnchored { mode: Anchored::No } => {
1937 write!(f, "unanchored searches are not supported or enabled")
1938 }
1939 MatchErrorKind::UnsupportedAnchored {
1940 mode: Anchored::Pattern(pid),
1941 } => {
1942 write!(
1943 f,
1944 "anchored searches for a specific pattern ({}) are \
1945 not supported or enabled",
1946 pid.as_usize(),
1947 )
1948 }
1949 }
1950 }
1951}
1952
1953#[cfg(test)]
1954mod tests {
1955 use super::*;
1956
1957 #[test]
1958 #[should_panic(expected = "overflowed usize")]
1959 fn span_offset_overflow_panics() {
1960 let s = Span { start: usize::MAX, end: usize::MAX };
1961 let _ = s.offset(1);
1962 }
1963
1964 use super::*;
1965
1966 // We test that our 'MatchError' type is the size we expect. This isn't an
1967 // API guarantee, but if the size increases, we really want to make sure we
1968 // decide to do that intentionally. So this should be a speed bump. And in
1969 // general, we should not increase the size without a very good reason.
1970 //
1971 // Why? Because low level search APIs return Result<.., MatchError>. When
1972 // MatchError gets bigger, so to does the Result type.
1973 //
1974 // Now, when 'alloc' is enabled, we do box the error, which de-emphasizes
1975 // the importance of keeping a small error type. But without 'alloc', we
1976 // still want things to be small.
1977 #[test]
1978 fn match_error_size() {
1979 let expected_size = if cfg!(feature = "alloc") {
1980 core::mem::size_of::<usize>()
1981 } else {
1982 2 * core::mem::size_of::<usize>()
1983 };
1984 assert_eq!(expected_size, core::mem::size_of::<MatchError>());
1985 }
1986
1987 // Same as above, but for the underlying match error kind.
1988 #[cfg(target_pointer_width = "64")]
1989 #[test]
1990 fn match_error_kind_size() {
1991 let expected_size = 2 * core::mem::size_of::<usize>();
1992 assert_eq!(expected_size, core::mem::size_of::<MatchErrorKind>());
1993 }
1994
1995 #[cfg(target_pointer_width = "32")]
1996 #[test]
1997 fn match_error_kind_size() {
1998 let expected_size = 3 * core::mem::size_of::<usize>();
1999 assert_eq!(expected_size, core::mem::size_of::<MatchErrorKind>());
2000 }
2001
2002 #[test]
2003 fn incorrect_asref_guard() {
2004 struct Bad(std::cell::Cell<bool>);
2005
2006 impl AsRef<[u8]> for Bad {
2007 fn as_ref(&self) -> &[u8] {
2008 if self.0.replace(false) {
2009 &[]
2010 } else {
2011 &[0; 1000]
2012 }
2013 }
2014 }
2015
2016 let bad = Bad(std::cell::Cell::new(true));
2017 let input = Input::new(&bad);
2018 assert!(input.end() <= input.haystack().len());
2019 }
2020}