Skip to main content

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}