| /*! |
| A lazy DFA backed `Regex`. |
| |
| This module provides a [`Regex`] backed by a lazy DFA. A `Regex` implements |
| convenience routines you might have come to expect, such as finding a match |
| and iterating over all non-overlapping matches. This `Regex` type is limited |
| in its capabilities to what a lazy DFA can provide. Therefore, APIs involving |
| capturing groups, for example, are not provided. |
| |
| Internally, a `Regex` is composed of two DFAs. One is a "forward" DFA that |
| finds the end offset of a match, where as the other is a "reverse" DFA that |
| find the start offset of a match. |
| |
| See the [parent module](crate::hybrid) for examples. |
| */ |
| |
| use crate::{ |
| hybrid::{ |
| dfa::{self, DFA}, |
| error::BuildError, |
| }, |
| nfa::thompson, |
| util::{ |
| iter, |
| search::{Anchored, Input, Match, MatchError, MatchKind}, |
| }, |
| }; |
| |
| /// A regular expression that uses hybrid NFA/DFAs (also called "lazy DFAs") |
| /// for searching. |
| /// |
| /// A regular expression is comprised of two lazy DFAs, a "forward" DFA and a |
| /// "reverse" DFA. The forward DFA is responsible for detecting the end of |
| /// a match while the reverse DFA is responsible for detecting the start |
| /// of a match. Thus, in order to find the bounds of any given match, a |
| /// forward search must first be run followed by a reverse search. A match |
| /// found by the forward DFA guarantees that the reverse DFA will also find |
| /// a match. |
| /// |
| /// # Fallibility |
| /// |
| /// Most of the search routines defined on this type will _panic_ when the |
| /// underlying search fails. This might be because the DFA gave up because it |
| /// saw a quit byte, whether configured explicitly or via heuristic Unicode |
| /// word boundary support, although neither are enabled by default. It might |
| /// also fail if the underlying DFA determines it isn't making effective use of |
| /// the cache (which also never happens by default). Or it might fail because |
| /// an invalid `Input` configuration is given, for example, with an unsupported |
| /// [`Anchored`] mode. |
| /// |
| /// If you need to handle these error cases instead of allowing them to trigger |
| /// a panic, then the lower level [`Regex::try_search`] provides a fallible API |
| /// that never panics. |
| /// |
| /// # Example |
| /// |
| /// This example shows how to cause a search to terminate if it sees a |
| /// `\n` byte, and handle the error returned. This could be useful if, for |
| /// example, you wanted to prevent a user supplied pattern from matching |
| /// across a line boundary. |
| /// |
| /// ``` |
| /// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| /// use regex_automata::{hybrid::{dfa, regex::Regex}, Input, MatchError}; |
| /// |
| /// let re = Regex::builder() |
| /// .dfa(dfa::Config::new().quit(b'\n', true)) |
| /// .build(r"foo\p{any}+bar")?; |
| /// let mut cache = re.create_cache(); |
| /// |
| /// let input = Input::new("foo\nbar"); |
| /// // Normally this would produce a match, since \p{any} contains '\n'. |
| /// // But since we instructed the automaton to enter a quit state if a |
| /// // '\n' is observed, this produces a match error instead. |
| /// let expected = MatchError::quit(b'\n', 3); |
| /// let got = re.try_search(&mut cache, &input).unwrap_err(); |
| /// assert_eq!(expected, got); |
| /// |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| #[derive(Debug)] |
| pub struct Regex { |
| /// The forward lazy DFA. This can only find the end of a match. |
| forward: DFA, |
| /// The reverse lazy DFA. This can only find the start of a match. |
| /// |
| /// This is built with 'all' match semantics (instead of leftmost-first) |
| /// so that it always finds the longest possible match (which corresponds |
| /// to the leftmost starting position). It is also compiled as an anchored |
| /// matcher and has 'starts_for_each_pattern' enabled. Including starting |
| /// states for each pattern is necessary to ensure that we only look for |
| /// matches of a pattern that matched in the forward direction. Otherwise, |
| /// we might wind up finding the "leftmost" starting position of a totally |
| /// different pattern! |
| reverse: DFA, |
| } |
| |
| /// Convenience routines for regex and cache construction. |
| impl Regex { |
| /// Parse the given regular expression using the default configuration and |
| /// return the corresponding regex. |
| /// |
| /// If you want a non-default configuration, then use the [`Builder`] to |
| /// set your own configuration. |
| /// |
| /// # Example |
| /// |
| /// ``` |
| /// use regex_automata::{hybrid::regex::Regex, Match}; |
| /// |
| /// let re = Regex::new("foo[0-9]+bar")?; |
| /// let mut cache = re.create_cache(); |
| /// assert_eq!( |
| /// Some(Match::must(0, 3..14)), |
| /// re.find(&mut cache, "zzzfoo12345barzzz"), |
| /// ); |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| #[cfg(feature = "syntax")] |
| pub fn new(pattern: &str) -> Result<Regex, BuildError> { |
| Regex::builder().build(pattern) |
| } |
| |
| /// Like `new`, but parses multiple patterns into a single "multi regex." |
| /// This similarly uses the default regex configuration. |
| /// |
| /// # Example |
| /// |
| /// ``` |
| /// use regex_automata::{hybrid::regex::Regex, Match}; |
| /// |
| /// let re = Regex::new_many(&["[a-z]+", "[0-9]+"])?; |
| /// let mut cache = re.create_cache(); |
| /// |
| /// let mut it = re.find_iter(&mut cache, "abc 1 foo 4567 0 quux"); |
| /// assert_eq!(Some(Match::must(0, 0..3)), it.next()); |
| /// assert_eq!(Some(Match::must(1, 4..5)), it.next()); |
| /// assert_eq!(Some(Match::must(0, 6..9)), it.next()); |
| /// assert_eq!(Some(Match::must(1, 10..14)), it.next()); |
| /// assert_eq!(Some(Match::must(1, 15..16)), it.next()); |
| /// assert_eq!(Some(Match::must(0, 17..21)), it.next()); |
| /// assert_eq!(None, it.next()); |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| #[cfg(feature = "syntax")] |
| pub fn new_many<P: AsRef<str>>( |
| patterns: &[P], |
| ) -> Result<Regex, BuildError> { |
| Regex::builder().build_many(patterns) |
| } |
| |
| /// Return a builder for configuring the construction of a `Regex`. |
| /// |
| /// This is a convenience routine to avoid needing to import the |
| /// [`Builder`] type in common cases. |
| /// |
| /// # Example |
| /// |
| /// This example shows how to use the builder to disable UTF-8 mode |
| /// everywhere. |
| /// |
| /// ``` |
| /// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| /// use regex_automata::{ |
| /// hybrid::regex::Regex, nfa::thompson, util::syntax, Match, |
| /// }; |
| /// |
| /// let re = Regex::builder() |
| /// .syntax(syntax::Config::new().utf8(false)) |
| /// .thompson(thompson::Config::new().utf8(false)) |
| /// .build(r"foo(?-u:[^b])ar.*")?; |
| /// let mut cache = re.create_cache(); |
| /// |
| /// let haystack = b"\xFEfoo\xFFarzz\xE2\x98\xFF\n"; |
| /// let expected = Some(Match::must(0, 1..9)); |
| /// let got = re.find(&mut cache, haystack); |
| /// assert_eq!(expected, got); |
| /// |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| pub fn builder() -> Builder { |
| Builder::new() |
| } |
| |
| /// Create a new cache for this `Regex`. |
| /// |
| /// The cache returned should only be used for searches for this |
| /// `Regex`. If you want to reuse the cache for another `Regex`, then |
| /// you must call [`Cache::reset`] with that `Regex` (or, equivalently, |
| /// [`Regex::reset_cache`]). |
| pub fn create_cache(&self) -> Cache { |
| Cache::new(self) |
| } |
| |
| /// Reset the given cache such that it can be used for searching with the |
| /// this `Regex` (and only this `Regex`). |
| /// |
| /// A cache reset permits reusing memory already allocated in this cache |
| /// with a different `Regex`. |
| /// |
| /// Resetting a cache sets its "clear count" to 0. This is relevant if the |
| /// `Regex` has been configured to "give up" after it has cleared the cache |
| /// a certain number of times. |
| /// |
| /// # Example |
| /// |
| /// This shows how to re-purpose a cache for use with a different `Regex`. |
| /// |
| /// ``` |
| /// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| /// use regex_automata::{hybrid::regex::Regex, Match}; |
| /// |
| /// let re1 = Regex::new(r"\w")?; |
| /// let re2 = Regex::new(r"\W")?; |
| /// |
| /// let mut cache = re1.create_cache(); |
| /// assert_eq!( |
| /// Some(Match::must(0, 0..2)), |
| /// re1.find(&mut cache, "Δ"), |
| /// ); |
| /// |
| /// // Using 'cache' with re2 is not allowed. It may result in panics or |
| /// // incorrect results. In order to re-purpose the cache, we must reset |
| /// // it with the Regex we'd like to use it with. |
| /// // |
| /// // Similarly, after this reset, using the cache with 're1' is also not |
| /// // allowed. |
| /// re2.reset_cache(&mut cache); |
| /// assert_eq!( |
| /// Some(Match::must(0, 0..3)), |
| /// re2.find(&mut cache, "☃"), |
| /// ); |
| /// |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| pub fn reset_cache(&self, cache: &mut Cache) { |
| self.forward().reset_cache(&mut cache.forward); |
| self.reverse().reset_cache(&mut cache.reverse); |
| } |
| } |
| |
| /// Standard infallible search routines for finding and iterating over matches. |
| impl Regex { |
| /// Returns true if and only if this regex matches the given haystack. |
| /// |
| /// This routine may short circuit if it knows that scanning future input |
| /// will never lead to a different result. In particular, if the underlying |
| /// DFA enters a match state or a dead state, then this routine will return |
| /// `true` or `false`, respectively, without inspecting any future input. |
| /// |
| /// # Panics |
| /// |
| /// This routine panics if the search could not complete. This can occur |
| /// in a number of circumstances: |
| /// |
| /// * The configuration of the lazy DFA may permit it to "quit" the search. |
| /// For example, setting quit bytes or enabling heuristic support for |
| /// Unicode word boundaries. The default configuration does not enable any |
| /// option that could result in the lazy DFA quitting. |
| /// * The configuration of the lazy DFA may also permit it to "give up" |
| /// on a search if it makes ineffective use of its transition table |
| /// cache. The default configuration does not enable this by default, |
| /// although it is typically a good idea to. |
| /// * When the provided `Input` configuration is not supported. For |
| /// example, by providing an unsupported anchor mode. |
| /// |
| /// When a search panics, callers cannot know whether a match exists or |
| /// not. |
| /// |
| /// Use [`Regex::try_search`] if you want to handle these error conditions. |
| /// |
| /// # Example |
| /// |
| /// ``` |
| /// use regex_automata::hybrid::regex::Regex; |
| /// |
| /// let re = Regex::new("foo[0-9]+bar")?; |
| /// let mut cache = re.create_cache(); |
| /// |
| /// assert!(re.is_match(&mut cache, "foo12345bar")); |
| /// assert!(!re.is_match(&mut cache, "foobar")); |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| #[inline] |
| pub fn is_match<'h, I: Into<Input<'h>>>( |
| &self, |
| cache: &mut Cache, |
| input: I, |
| ) -> bool { |
| // Not only can we do an "earliest" search, but we can avoid doing a |
| // reverse scan too. |
| self.forward() |
| .try_search_fwd(&mut cache.forward, &input.into().earliest(true)) |
| .unwrap() |
| .is_some() |
| } |
| |
| /// Returns the start and end offset of the leftmost match. If no match |
| /// exists, then `None` is returned. |
| /// |
| /// # Panics |
| /// |
| /// This routine panics if the search could not complete. This can occur |
| /// in a number of circumstances: |
| /// |
| /// * The configuration of the lazy DFA may permit it to "quit" the search. |
| /// For example, setting quit bytes or enabling heuristic support for |
| /// Unicode word boundaries. The default configuration does not enable any |
| /// option that could result in the lazy DFA quitting. |
| /// * The configuration of the lazy DFA may also permit it to "give up" |
| /// on a search if it makes ineffective use of its transition table |
| /// cache. The default configuration does not enable this by default, |
| /// although it is typically a good idea to. |
| /// * When the provided `Input` configuration is not supported. For |
| /// example, by providing an unsupported anchor mode. |
| /// |
| /// When a search panics, callers cannot know whether a match exists or |
| /// not. |
| /// |
| /// Use [`Regex::try_search`] if you want to handle these error conditions. |
| /// |
| /// # Example |
| /// |
| /// ``` |
| /// use regex_automata::{Match, hybrid::regex::Regex}; |
| /// |
| /// let re = Regex::new("foo[0-9]+")?; |
| /// let mut cache = re.create_cache(); |
| /// assert_eq!( |
| /// Some(Match::must(0, 3..11)), |
| /// re.find(&mut cache, "zzzfoo12345zzz"), |
| /// ); |
| /// |
| /// // Even though a match is found after reading the first byte (`a`), |
| /// // the default leftmost-first match semantics demand that we find the |
| /// // earliest match that prefers earlier parts of the pattern over latter |
| /// // parts. |
| /// let re = Regex::new("abc|a")?; |
| /// let mut cache = re.create_cache(); |
| /// assert_eq!(Some(Match::must(0, 0..3)), re.find(&mut cache, "abc")); |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| #[inline] |
| pub fn find<'h, I: Into<Input<'h>>>( |
| &self, |
| cache: &mut Cache, |
| input: I, |
| ) -> Option<Match> { |
| self.try_search(cache, &input.into()).unwrap() |
| } |
| |
| /// Returns an iterator over all non-overlapping leftmost matches in the |
| /// given bytes. If no match exists, then the iterator yields no elements. |
| /// |
| /// # Panics |
| /// |
| /// This routine panics if the search could not complete. This can occur |
| /// in a number of circumstances: |
| /// |
| /// * The configuration of the lazy DFA may permit it to "quit" the search. |
| /// For example, setting quit bytes or enabling heuristic support for |
| /// Unicode word boundaries. The default configuration does not enable any |
| /// option that could result in the lazy DFA quitting. |
| /// * The configuration of the lazy DFA may also permit it to "give up" |
| /// on a search if it makes ineffective use of its transition table |
| /// cache. The default configuration does not enable this by default, |
| /// although it is typically a good idea to. |
| /// * When the provided `Input` configuration is not supported. For |
| /// example, by providing an unsupported anchor mode. |
| /// |
| /// When a search panics, callers cannot know whether a match exists or |
| /// not. |
| /// |
| /// The above conditions also apply to the iterator returned as well. For |
| /// example, if the lazy DFA gives up or quits during a search using this |
| /// method, then a panic will occur during iteration. |
| /// |
| /// Use [`Regex::try_search`] with [`util::iter::Searcher`](iter::Searcher) |
| /// if you want to handle these error conditions. |
| /// |
| /// # Example |
| /// |
| /// ``` |
| /// use regex_automata::{hybrid::regex::Regex, Match}; |
| /// |
| /// let re = Regex::new("foo[0-9]+")?; |
| /// let mut cache = re.create_cache(); |
| /// |
| /// let text = "foo1 foo12 foo123"; |
| /// let matches: Vec<Match> = re.find_iter(&mut cache, text).collect(); |
| /// assert_eq!(matches, vec![ |
| /// Match::must(0, 0..4), |
| /// Match::must(0, 5..10), |
| /// Match::must(0, 11..17), |
| /// ]); |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| #[inline] |
| pub fn find_iter<'r, 'c, 'h, I: Into<Input<'h>>>( |
| &'r self, |
| cache: &'c mut Cache, |
| input: I, |
| ) -> FindMatches<'r, 'c, 'h> { |
| let it = iter::Searcher::new(input.into()); |
| FindMatches { re: self, cache, it } |
| } |
| } |
| |
| /// Lower level "search" primitives that accept a `&Input` for cheap reuse |
| /// and return an error if one occurs instead of panicking. |
| impl Regex { |
| /// Returns the start and end offset of the leftmost match. If no match |
| /// exists, then `None` is returned. |
| /// |
| /// This is like [`Regex::find`] but with two differences: |
| /// |
| /// 1. It is not generic over `Into<Input>` and instead accepts a |
| /// `&Input`. This permits reusing the same `Input` for multiple searches |
| /// without needing to create a new one. This _may_ help with latency. |
| /// 2. It returns an error if the search could not complete where as |
| /// [`Regex::find`] will panic. |
| /// |
| /// # Errors |
| /// |
| /// This routine errors if the search could not complete. This can occur |
| /// in a number of circumstances: |
| /// |
| /// * The configuration of the lazy DFA may permit it to "quit" the search. |
| /// For example, setting quit bytes or enabling heuristic support for |
| /// Unicode word boundaries. The default configuration does not enable any |
| /// option that could result in the lazy DFA quitting. |
| /// * The configuration of the lazy DFA may also permit it to "give up" |
| /// on a search if it makes ineffective use of its transition table |
| /// cache. The default configuration does not enable this by default, |
| /// although it is typically a good idea to. |
| /// * When the provided `Input` configuration is not supported. For |
| /// example, by providing an unsupported anchor mode. |
| /// |
| /// When a search returns an error, callers cannot know whether a match |
| /// exists or not. |
| #[inline] |
| pub fn try_search( |
| &self, |
| cache: &mut Cache, |
| input: &Input<'_>, |
| ) -> Result<Option<Match>, MatchError> { |
| let (fcache, rcache) = (&mut cache.forward, &mut cache.reverse); |
| let end = match self.forward().try_search_fwd(fcache, input)? { |
| None => return Ok(None), |
| Some(end) => end, |
| }; |
| // This special cases an empty match at the beginning of the search. If |
| // our end matches our start, then since a reverse DFA can't match past |
| // the start, it must follow that our starting position is also our end |
| // position. So short circuit and skip the reverse search. |
| if input.start() == end.offset() { |
| return Ok(Some(Match::new( |
| end.pattern(), |
| end.offset()..end.offset(), |
| ))); |
| } |
| // We can also skip the reverse search if we know our search was |
| // anchored. This occurs either when the input config is anchored or |
| // when we know the regex itself is anchored. In this case, we know the |
| // start of the match, if one is found, must be the start of the |
| // search. |
| if self.is_anchored(input) { |
| return Ok(Some(Match::new( |
| end.pattern(), |
| input.start()..end.offset(), |
| ))); |
| } |
| // N.B. I have tentatively convinced myself that it isn't necessary |
| // to specify the specific pattern for the reverse search since the |
| // reverse search will always find the same pattern to match as the |
| // forward search. But I lack a rigorous proof. Why not just provide |
| // the pattern anyway? Well, if it is needed, then leaving it out |
| // gives us a chance to find a witness. (Also, if we don't need to |
| // specify the pattern, then we don't need to build the reverse DFA |
| // with 'starts_for_each_pattern' enabled. It doesn't matter too much |
| // for the lazy DFA, but does make the overall DFA bigger.) |
| // |
| // We also need to be careful to disable 'earliest' for the reverse |
| // search, since it could be enabled for the forward search. In the |
| // reverse case, to satisfy "leftmost" criteria, we need to match as |
| // much as we can. We also need to be careful to make the search |
| // anchored. We don't want the reverse search to report any matches |
| // other than the one beginning at the end of our forward search. |
| let revsearch = input |
| .clone() |
| .span(input.start()..end.offset()) |
| .anchored(Anchored::Yes) |
| .earliest(false); |
| let start = self |
| .reverse() |
| .try_search_rev(rcache, &revsearch)? |
| .expect("reverse search must match if forward search does"); |
| debug_assert_eq!( |
| start.pattern(), |
| end.pattern(), |
| "forward and reverse search must match same pattern", |
| ); |
| debug_assert!(start.offset() <= end.offset()); |
| Ok(Some(Match::new(end.pattern(), start.offset()..end.offset()))) |
| } |
| |
| /// Returns true if either the given input specifies an anchored search |
| /// or if the underlying NFA is always anchored. |
| fn is_anchored(&self, input: &Input<'_>) -> bool { |
| match input.get_anchored() { |
| Anchored::No => { |
| self.forward().get_nfa().is_always_start_anchored() |
| } |
| Anchored::Yes | Anchored::Pattern(_) => true, |
| } |
| } |
| } |
| |
| /// Non-search APIs for querying information about the regex and setting a |
| /// prefilter. |
| impl Regex { |
| /// Return the underlying lazy DFA responsible for forward matching. |
| /// |
| /// This is useful for accessing the underlying lazy DFA and using it |
| /// directly if the situation calls for it. |
| pub fn forward(&self) -> &DFA { |
| &self.forward |
| } |
| |
| /// Return the underlying lazy DFA responsible for reverse matching. |
| /// |
| /// This is useful for accessing the underlying lazy DFA and using it |
| /// directly if the situation calls for it. |
| pub fn reverse(&self) -> &DFA { |
| &self.reverse |
| } |
| |
| /// Returns the total number of patterns matched by this regex. |
| /// |
| /// # Example |
| /// |
| /// ``` |
| /// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| /// use regex_automata::hybrid::regex::Regex; |
| /// |
| /// let re = Regex::new_many(&[r"[a-z]+", r"[0-9]+", r"\w+"])?; |
| /// assert_eq!(3, re.pattern_len()); |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| pub fn pattern_len(&self) -> usize { |
| assert_eq!(self.forward().pattern_len(), self.reverse().pattern_len()); |
| self.forward().pattern_len() |
| } |
| } |
| |
| /// An iterator over all non-overlapping matches for an infallible search. |
| /// |
| /// The iterator yields a [`Match`] value until no more matches could be found. |
| /// If the underlying regex engine returns an error, then a panic occurs. |
| /// |
| /// The lifetime parameters are as follows: |
| /// |
| /// * `'r` represents the lifetime of the regex object. |
| /// * `'h` represents the lifetime of the haystack being searched. |
| /// * `'c` represents the lifetime of the regex cache. |
| /// |
| /// This iterator can be created with the [`Regex::find_iter`] method. |
| #[derive(Debug)] |
| pub struct FindMatches<'r, 'c, 'h> { |
| re: &'r Regex, |
| cache: &'c mut Cache, |
| it: iter::Searcher<'h>, |
| } |
| |
| impl<'r, 'c, 'h> Iterator for FindMatches<'r, 'c, 'h> { |
| type Item = Match; |
| |
| #[inline] |
| fn next(&mut self) -> Option<Match> { |
| let FindMatches { re, ref mut cache, ref mut it } = *self; |
| it.advance(|input| re.try_search(cache, input)) |
| } |
| } |
| |
| /// A cache represents a partially computed forward and reverse DFA. |
| /// |
| /// A cache is the key component that differentiates a classical DFA and a |
| /// hybrid NFA/DFA (also called a "lazy DFA"). Where a classical DFA builds a |
| /// complete transition table that can handle all possible inputs, a hybrid |
| /// NFA/DFA starts with an empty transition table and builds only the parts |
| /// required during search. The parts that are built are stored in a cache. For |
| /// this reason, a cache is a required parameter for nearly every operation on |
| /// a [`Regex`]. |
| /// |
| /// Caches can be created from their corresponding `Regex` via |
| /// [`Regex::create_cache`]. A cache can only be used with either the `Regex` |
| /// that created it, or the `Regex` that was most recently used to reset it |
| /// with [`Cache::reset`]. Using a cache with any other `Regex` may result in |
| /// panics or incorrect results. |
| #[derive(Debug, Clone)] |
| pub struct Cache { |
| forward: dfa::Cache, |
| reverse: dfa::Cache, |
| } |
| |
| impl Cache { |
| /// Create a new cache for the given `Regex`. |
| /// |
| /// The cache returned should only be used for searches for the given |
| /// `Regex`. If you want to reuse the cache for another `Regex`, then you |
| /// must call [`Cache::reset`] with that `Regex`. |
| pub fn new(re: &Regex) -> Cache { |
| let forward = dfa::Cache::new(re.forward()); |
| let reverse = dfa::Cache::new(re.reverse()); |
| Cache { forward, reverse } |
| } |
| |
| /// Reset this cache such that it can be used for searching with the given |
| /// `Regex` (and only that `Regex`). |
| /// |
| /// A cache reset permits reusing memory already allocated in this cache |
| /// with a different `Regex`. |
| /// |
| /// Resetting a cache sets its "clear count" to 0. This is relevant if the |
| /// `Regex` has been configured to "give up" after it has cleared the cache |
| /// a certain number of times. |
| /// |
| /// # Example |
| /// |
| /// This shows how to re-purpose a cache for use with a different `Regex`. |
| /// |
| /// ``` |
| /// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| /// use regex_automata::{hybrid::regex::Regex, Match}; |
| /// |
| /// let re1 = Regex::new(r"\w")?; |
| /// let re2 = Regex::new(r"\W")?; |
| /// |
| /// let mut cache = re1.create_cache(); |
| /// assert_eq!( |
| /// Some(Match::must(0, 0..2)), |
| /// re1.find(&mut cache, "Δ"), |
| /// ); |
| /// |
| /// // Using 'cache' with re2 is not allowed. It may result in panics or |
| /// // incorrect results. In order to re-purpose the cache, we must reset |
| /// // it with the Regex we'd like to use it with. |
| /// // |
| /// // Similarly, after this reset, using the cache with 're1' is also not |
| /// // allowed. |
| /// cache.reset(&re2); |
| /// assert_eq!( |
| /// Some(Match::must(0, 0..3)), |
| /// re2.find(&mut cache, "☃"), |
| /// ); |
| /// |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| pub fn reset(&mut self, re: &Regex) { |
| self.forward.reset(re.forward()); |
| self.reverse.reset(re.reverse()); |
| } |
| |
| /// Return a reference to the forward cache. |
| pub fn forward(&mut self) -> &dfa::Cache { |
| &self.forward |
| } |
| |
| /// Return a reference to the reverse cache. |
| pub fn reverse(&mut self) -> &dfa::Cache { |
| &self.reverse |
| } |
| |
| /// Return a mutable reference to the forward cache. |
| /// |
| /// If you need mutable references to both the forward and reverse caches, |
| /// then use [`Cache::as_parts_mut`]. |
| pub fn forward_mut(&mut self) -> &mut dfa::Cache { |
| &mut self.forward |
| } |
| |
| /// Return a mutable reference to the reverse cache. |
| /// |
| /// If you need mutable references to both the forward and reverse caches, |
| /// then use [`Cache::as_parts_mut`]. |
| pub fn reverse_mut(&mut self) -> &mut dfa::Cache { |
| &mut self.reverse |
| } |
| |
| /// Return references to the forward and reverse caches, respectively. |
| pub fn as_parts(&self) -> (&dfa::Cache, &dfa::Cache) { |
| (&self.forward, &self.reverse) |
| } |
| |
| /// Return mutable references to the forward and reverse caches, |
| /// respectively. |
| pub fn as_parts_mut(&mut self) -> (&mut dfa::Cache, &mut dfa::Cache) { |
| (&mut self.forward, &mut self.reverse) |
| } |
| |
| /// Returns the heap memory usage, in bytes, as a sum of the forward and |
| /// reverse lazy DFA caches. |
| /// |
| /// This does **not** include the stack size used up by this cache. To |
| /// compute that, use `std::mem::size_of::<Cache>()`. |
| pub fn memory_usage(&self) -> usize { |
| self.forward.memory_usage() + self.reverse.memory_usage() |
| } |
| } |
| |
| /// A builder for a regex based on a hybrid NFA/DFA. |
| /// |
| /// This builder permits configuring options for the syntax of a pattern, the |
| /// NFA construction, the lazy DFA construction and finally the regex searching |
| /// itself. This builder is different from a general purpose regex builder |
| /// in that it permits fine grain configuration of the construction process. |
| /// The trade off for this is complexity, and the possibility of setting a |
| /// configuration that might not make sense. For example, there are two |
| /// different UTF-8 modes: |
| /// |
| /// * [`syntax::Config::utf8`](crate::util::syntax::Config::utf8) controls |
| /// whether the pattern itself can contain sub-expressions that match invalid |
| /// UTF-8. |
| /// * [`thompson::Config::utf8`] controls how the regex iterators themselves |
| /// advance the starting position of the next search when a match with zero |
| /// length is found. |
| /// |
| /// Generally speaking, callers will want to either enable all of these or |
| /// disable all of these. |
| /// |
| /// Internally, building a regex requires building two hybrid NFA/DFAs, |
| /// where one is responsible for finding the end of a match and the other is |
| /// responsible for finding the start of a match. If you only need to detect |
| /// whether something matched, or only the end of a match, then you should use |
| /// a [`dfa::Builder`] to construct a single hybrid NFA/DFA, which is cheaper |
| /// than building two of them. |
| /// |
| /// # Example |
| /// |
| /// This example shows how to disable UTF-8 mode in the syntax and the regex |
| /// itself. This is generally what you want for matching on arbitrary bytes. |
| /// |
| /// ``` |
| /// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| /// use regex_automata::{ |
| /// hybrid::regex::Regex, nfa::thompson, util::syntax, Match, |
| /// }; |
| /// |
| /// let re = Regex::builder() |
| /// .syntax(syntax::Config::new().utf8(false)) |
| /// .thompson(thompson::Config::new().utf8(false)) |
| /// .build(r"foo(?-u:[^b])ar.*")?; |
| /// let mut cache = re.create_cache(); |
| /// |
| /// let haystack = b"\xFEfoo\xFFarzz\xE2\x98\xFF\n"; |
| /// let expected = Some(Match::must(0, 1..9)); |
| /// let got = re.find(&mut cache, haystack); |
| /// assert_eq!(expected, got); |
| /// // Notice that `(?-u:[^b])` matches invalid UTF-8, |
| /// // but the subsequent `.*` does not! Disabling UTF-8 |
| /// // on the syntax permits this. |
| /// assert_eq!(b"foo\xFFarzz", &haystack[got.unwrap().range()]); |
| /// |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| #[derive(Clone, Debug)] |
| pub struct Builder { |
| dfa: dfa::Builder, |
| } |
| |
| impl Builder { |
| /// Create a new regex builder with the default configuration. |
| pub fn new() -> Builder { |
| Builder { dfa: DFA::builder() } |
| } |
| |
| /// Build a regex from the given pattern. |
| /// |
| /// If there was a problem parsing or compiling the pattern, then an error |
| /// is returned. |
| #[cfg(feature = "syntax")] |
| pub fn build(&self, pattern: &str) -> Result<Regex, BuildError> { |
| self.build_many(&[pattern]) |
| } |
| |
| /// Build a regex from the given patterns. |
| #[cfg(feature = "syntax")] |
| pub fn build_many<P: AsRef<str>>( |
| &self, |
| patterns: &[P], |
| ) -> Result<Regex, BuildError> { |
| let forward = self.dfa.build_many(patterns)?; |
| let reverse = self |
| .dfa |
| .clone() |
| .configure( |
| DFA::config() |
| .prefilter(None) |
| .specialize_start_states(false) |
| .match_kind(MatchKind::All), |
| ) |
| .thompson(thompson::Config::new().reverse(true)) |
| .build_many(patterns)?; |
| Ok(self.build_from_dfas(forward, reverse)) |
| } |
| |
| /// Build a regex from its component forward and reverse hybrid NFA/DFAs. |
| /// |
| /// This is useful when you've built a forward and reverse lazy DFA |
| /// separately, and want to combine them into a single regex. Once build, |
| /// the individual DFAs given can still be accessed via [`Regex::forward`] |
| /// and [`Regex::reverse`]. |
| /// |
| /// It is important that the reverse lazy DFA be compiled under the |
| /// following conditions: |
| /// |
| /// * It should use [`MatchKind::All`] semantics. |
| /// * It should match in reverse. |
| /// * Otherwise, its configuration should match the forward DFA. |
| /// |
| /// If these conditions aren't satisfied, then the behavior of searches is |
| /// unspecified. |
| /// |
| /// Note that when using this constructor, no configuration is applied. |
| /// Since this routine provides the DFAs to the builder, there is no |
| /// opportunity to apply other configuration options. |
| /// |
| /// # Example |
| /// |
| /// This shows how to build individual lazy forward and reverse DFAs, and |
| /// then combine them into a single `Regex`. |
| /// |
| /// ``` |
| /// use regex_automata::{ |
| /// hybrid::{dfa::DFA, regex::Regex}, |
| /// nfa::thompson, |
| /// MatchKind, |
| /// }; |
| /// |
| /// let fwd = DFA::new(r"foo[0-9]+")?; |
| /// let rev = DFA::builder() |
| /// .configure(DFA::config().match_kind(MatchKind::All)) |
| /// .thompson(thompson::Config::new().reverse(true)) |
| /// .build(r"foo[0-9]+")?; |
| /// |
| /// let re = Regex::builder().build_from_dfas(fwd, rev); |
| /// let mut cache = re.create_cache(); |
| /// assert_eq!(true, re.is_match(&mut cache, "foo123")); |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| pub fn build_from_dfas(&self, forward: DFA, reverse: DFA) -> Regex { |
| Regex { forward, reverse } |
| } |
| |
| /// Set the syntax configuration for this builder using |
| /// [`syntax::Config`](crate::util::syntax::Config). |
| /// |
| /// This permits setting things like case insensitivity, Unicode and multi |
| /// line mode. |
| #[cfg(feature = "syntax")] |
| pub fn syntax( |
| &mut self, |
| config: crate::util::syntax::Config, |
| ) -> &mut Builder { |
| self.dfa.syntax(config); |
| self |
| } |
| |
| /// Set the Thompson NFA configuration for this builder using |
| /// [`nfa::thompson::Config`](thompson::Config). |
| /// |
| /// This permits setting things like whether additional time should be |
| /// spent shrinking the size of the NFA. |
| #[cfg(feature = "syntax")] |
| pub fn thompson(&mut self, config: thompson::Config) -> &mut Builder { |
| self.dfa.thompson(config); |
| self |
| } |
| |
| /// Set the lazy DFA compilation configuration for this builder using |
| /// [`dfa::Config`](dfa::Config). |
| /// |
| /// This permits setting things like whether Unicode word boundaries should |
| /// be heuristically supported or settings how the behavior of the cache. |
| pub fn dfa(&mut self, config: dfa::Config) -> &mut Builder { |
| self.dfa.configure(config); |
| self |
| } |
| } |
| |
| impl Default for Builder { |
| fn default() -> Builder { |
| Builder::new() |
| } |
| } |