Struct regex_automata::dfa::dense::Config

pub struct Config { /* private fields */ }

The configuration used for compiling a dense DFA.

A dense DFA configuration is a simple data object that is typically used with dense::Builder::configure.

The default configuration guarantees that a search will never return a MatchError for any haystack or pattern. Setting a quit byte with Config::quit or enabling heuristic support for Unicode word boundaries with Config::unicode_word_boundary can in turn cause a search to return an error. See the corresponding configuration options for more details on when those error conditions arise.

Implementations

impl Config

pub fn new() -> Config

Return a new default dense DFA compiler configuration.

pub fn anchored(self, yes: bool) -> Config

Set whether matching must be anchored at the beginning of the input.

When enabled, a match must begin at the start of a search. When disabled, the DFA will act as if the pattern started with a (?s:.)*?, which enables a match to appear anywhere.

Note that if you want to run both anchored and unanchored searches without building multiple automatons, you can enable the Config::starts_for_each_pattern configuration instead. This will permit unanchored any-pattern searches and pattern-specific anchored searches. See the documentation for that configuration for an example.

By default this is disabled.

WARNING: this is subtly different than using a ^ at the start of your regex. A ^ forces a regex to match exclusively at the start of input, regardless of where you begin your search. In contrast, enabling this option will allow your regex to match anywhere in your input, but the match must start at the beginning of a search. (Most of the higher level convenience search routines make “start of input” and “start of search” equivalent, but some routines allow treating these as orthogonal.)

For example, consider the haystack aba and the following searches:

1. The regex ^a is compiled with anchored=false and searches aba starting at position 2. Since ^ requires the match to start at the beginning of the input and 2 > 0, no match is found.
2. The regex a is compiled with anchored=true and searches aba starting at position 2. This reports a match at [2, 3] since the match starts where the search started. Since there is no ^, there is no requirement for the match to start at the beginning of the input.
3. The regex a is compiled with anchored=true and searches aba starting at position 1. Since b corresponds to position 1 and since the regex is anchored, it finds no match.
4. The regex a is compiled with anchored=false and searches aba startting at position 1. Since the regex is neither anchored nor starts with ^, the regex is compiled with an implicit (?s:.)*? prefix that permits it to match anywhere. Thus, it reports a match at [2, 3].

Example

This demonstrates the differences between an anchored search and a pattern that begins with ^ (as described in the above warning message).

use regex_automata::{dfa::{Automaton, dense}, HalfMatch};

let haystack = "aba".as_bytes();

let dfa = dense::Builder::new()
    .configure(dense::Config::new().anchored(false)) // default
    .build(r"^a")?;
let got = dfa.find_leftmost_fwd_at(None, None, haystack, 2, 3)?;
// No match is found because 2 is not the beginning of the haystack,
// which is what ^ requires.
let expected = None;
assert_eq!(expected, got);

let dfa = dense::Builder::new()
    .configure(dense::Config::new().anchored(true))
    .build(r"a")?;
let got = dfa.find_leftmost_fwd_at(None, None, haystack, 2, 3)?;
// An anchored search can still match anywhere in the haystack, it just
// must begin at the start of the search which is '2' in this case.
let expected = Some(HalfMatch::must(0, 3));
assert_eq!(expected, got);

let dfa = dense::Builder::new()
    .configure(dense::Config::new().anchored(true))
    .build(r"a")?;
let got = dfa.find_leftmost_fwd_at(None, None, haystack, 1, 3)?;
// No match is found since we start searching at offset 1 which
// corresponds to 'b'. Since there is no '(?s:.)*?' prefix, no match
// is found.
let expected = None;
assert_eq!(expected, got);

let dfa = dense::Builder::new()
    .configure(dense::Config::new().anchored(false)) // default
    .build(r"a")?;
let got = dfa.find_leftmost_fwd_at(None, None, haystack, 1, 3)?;
// Since anchored=false, an implicit '(?s:.)*?' prefix was added to the
// pattern. Even though the search starts at 'b', the 'match anything'
// prefix allows the search to match 'a'.
let expected = Some(HalfMatch::must(0, 3));
assert_eq!(expected, got);

pub fn accelerate(self, yes: bool) -> Config

Enable state acceleration.

When enabled, DFA construction will analyze each state to determine whether it is eligible for simple acceleration. Acceleration typically occurs when most of a state’s transitions loop back to itself, leaving only a select few bytes that will exit the state. When this occurs, other routines like memchr can be used to look for those bytes which may be much faster than traversing the DFA.

Callers may elect to disable this if consistent performance is more desirable than variable performance. Namely, acceleration can sometimes make searching slower than it otherwise would be if the transitions that leave accelerated states are traversed frequently.

See Automaton::accelerator for an example.

This is enabled by default.

pub fn minimize(self, yes: bool) -> Config

Minimize the DFA.

When enabled, the DFA built will be minimized such that it is as small as possible.

Whether one enables minimization or not depends on the types of costs you’re willing to pay and how much you care about its benefits. In particular, minimization has worst case O(n*k*logn) time and O(k*n) space, where n is the number of DFA states and k is the alphabet size. In practice, minimization can be quite costly in terms of both space and time, so it should only be done if you’re willing to wait longer to produce a DFA. In general, you might want a minimal DFA in the following circumstances:

1. You would like to optimize for the size of the automaton. This can manifest in one of two ways. Firstly, if you’re converting the DFA into Rust code (or a table embedded in the code), then a minimal DFA will translate into a corresponding reduction in code size, and thus, also the final compiled binary size. Secondly, if you are building many DFAs and putting them on the heap, you’ll be able to fit more if they are smaller. Note though that building a minimal DFA itself requires additional space; you only realize the space savings once the minimal DFA is constructed (at which point, the space used for minimization is freed).
2. You’ve observed that a smaller DFA results in faster match performance. Naively, this isn’t guaranteed since there is no inherent difference between matching with a bigger-than-minimal DFA and a minimal DFA. However, a smaller DFA may make use of your CPU’s cache more efficiently.
3. You are trying to establish an equivalence between regular languages. The standard method for this is to build a minimal DFA for each language and then compare them. If the DFAs are equivalent (up to state renaming), then the languages are equivalent.

Typically, minimization only makes sense as an offline process. That is, one might minimize a DFA before serializing it to persistent storage. In practical terms, minimization can take around an order of magnitude more time than compiling the initial DFA via determinization.

This option is disabled by default.

pub fn match_kind(self, kind: MatchKind) -> Config

Set the desired match semantics.

The default is MatchKind::LeftmostFirst, which corresponds to the match semantics of Perl-like regex engines. That is, when multiple patterns would match at the same leftmost position, the pattern that appears first in the concrete syntax is chosen.

Currently, the only other kind of match semantics supported is MatchKind::All. This corresponds to classical DFA construction where all possible matches are added to the DFA.

Typically, All is used when one wants to execute an overlapping search and LeftmostFirst otherwise. In particular, it rarely makes sense to use All with the various “leftmost” find routines, since the leftmost routines depend on the LeftmostFirst automata construction strategy. Specifically, LeftmostFirst adds dead states to the DFA as a way to terminate the search and report a match. LeftmostFirst also supports non-greedy matches using this strategy where as All does not.

Example: overlapping search

This example shows the typical use of MatchKind::All, which is to report overlapping matches.

use regex_automata::{
    dfa::{Automaton, OverlappingState, dense},
    HalfMatch, MatchKind,
};

let dfa = dense::Builder::new()
    .configure(dense::Config::new().match_kind(MatchKind::All))
    .build_many(&[r"\w+$", r"\S+$"])?;
let haystack = "@foo".as_bytes();
let mut state = OverlappingState::start();

let expected = Some(HalfMatch::must(1, 4));
let got = dfa.find_overlapping_fwd(haystack, &mut state)?;
assert_eq!(expected, got);

// The first pattern also matches at the same position, so re-running
// the search will yield another match. Notice also that the first
// pattern is returned after the second. This is because the second
// pattern begins its match before the first, is therefore an earlier
// match and is thus reported first.
let expected = Some(HalfMatch::must(0, 4));
let got = dfa.find_overlapping_fwd(haystack, &mut state)?;
assert_eq!(expected, got);

Example: reverse automaton to find start of match

Another example for using MatchKind::All is for constructing a reverse automaton to find the start of a match. All semantics are used for this in order to find the longest possible match, which corresponds to the leftmost starting position.

Note that if you need the starting position then dfa::regex::Regex will handle this for you, so it’s usually not necessary to do this yourself.

use regex_automata::{dfa::{Automaton, dense}, HalfMatch, MatchKind};

let haystack = "123foobar456".as_bytes();
let pattern = r"[a-z]+";

let dfa_fwd = dense::DFA::new(pattern)?;
let dfa_rev = dense::Builder::new()
    .configure(dense::Config::new()
        .anchored(true)
        .match_kind(MatchKind::All)
    )
    .build(pattern)?;
let expected_fwd = HalfMatch::must(0, 9);
let expected_rev = HalfMatch::must(0, 3);
let got_fwd = dfa_fwd.find_leftmost_fwd(haystack)?.unwrap();
// Here we don't specify the pattern to search for since there's only
// one pattern and we're doing a leftmost search. But if this were an
// overlapping search, you'd need to specify the pattern that matched
// in the forward direction. (Otherwise, you might wind up finding the
// starting position of a match of some other pattern.) That in turn
// requires building the reverse automaton with starts_for_each_pattern
// enabled. Indeed, this is what Regex does internally.
let got_rev = dfa_rev.find_leftmost_rev_at(
    None, haystack, 0, got_fwd.offset(),
)?.unwrap();
assert_eq!(expected_fwd, got_fwd);
assert_eq!(expected_rev, got_rev);

pub fn starts_for_each_pattern(self, yes: bool) -> Config

Whether to compile a separate start state for each pattern in the automaton.

When enabled, a separate anchored start state is added for each pattern in the DFA. When this start state is used, then the DFA will only search for matches for the pattern specified, even if there are other patterns in the DFA.

The main downside of this option is that it can potentially increase the size of the DFA and/or increase the time it takes to build the DFA.

There are a few reasons one might want to enable this (it’s disabled by default):

1. When looking for the start of an overlapping match (using a reverse DFA), doing it correctly requires starting the reverse search using the starting state of the pattern that matched in the forward direction. Indeed, when building a Regex, it will automatically enable this option when building the reverse DFA internally.
2. When you want to use a DFA with multiple patterns to both search for matches of any pattern or to search for anchored matches of one particular pattern while using the same DFA. (Otherwise, you would need to compile a new DFA for each pattern.)
3. Since the start states added for each pattern are anchored, if you compile an unanchored DFA with one pattern while also enabling this option, then you can use the same DFA to perform anchored or unanchored searches. The latter you get with the standard search APIs. The former you get from the various _at search methods that allow you specify a pattern ID to search for.

By default this is disabled.

Example

This example shows how to use this option to permit the same DFA to run both anchored and unanchored searches for a single pattern.

use regex_automata::{
    dfa::{Automaton, dense},
    HalfMatch, PatternID,
};

let dfa = dense::Builder::new()
    .configure(dense::Config::new().starts_for_each_pattern(true))
    .build(r"foo[0-9]+")?;
let haystack = b"quux foo123";

// Here's a normal unanchored search. Notice that we use 'None' for the
// pattern ID. Since the DFA was built as an unanchored machine, it
// use its default unanchored starting state.
let expected = HalfMatch::must(0, 11);
assert_eq!(Some(expected), dfa.find_leftmost_fwd_at(
    None, None, haystack, 0, haystack.len(),
)?);
// But now if we explicitly specify the pattern to search ('0' being
// the only pattern in the DFA), then it will use the starting state
// for that specific pattern which is always anchored. Since the
// pattern doesn't have a match at the beginning of the haystack, we
// find nothing.
assert_eq!(None, dfa.find_leftmost_fwd_at(
    None, Some(PatternID::must(0)), haystack, 0, haystack.len(),
)?);
// And finally, an anchored search is not the same as putting a '^' at
// beginning of the pattern. An anchored search can only match at the
// beginning of the *search*, which we can change:
assert_eq!(Some(expected), dfa.find_leftmost_fwd_at(
    None, Some(PatternID::must(0)), haystack, 5, haystack.len(),
)?);

pub fn byte_classes(self, yes: bool) -> Config

Whether to attempt to shrink the size of the DFA’s alphabet or not.

This option is enabled by default and should never be disabled unless one is debugging a generated DFA.

When enabled, the DFA will use a map from all possible bytes to their corresponding equivalence class. Each equivalence class represents a set of bytes that does not discriminate between a match and a non-match in the DFA. For example, the pattern [ab]+ has at least two equivalence classes: a set containing a and b and a set containing every byte except for a and b. a and b are in the same equivalence classes because they never discriminate between a match and a non-match.

The advantage of this map is that the size of the transition table can be reduced drastically from #states * 256 * sizeof(StateID) to #states * k * sizeof(StateID) where k is the number of equivalence classes (rounded up to the nearest power of 2). As a result, total space usage can decrease substantially. Moreover, since a smaller alphabet is used, DFA compilation becomes faster as well.

WARNING: This is only useful for debugging DFAs. Disabling this does not yield any speed advantages. Namely, even when this is disabled, a byte class map is still used while searching. The only difference is that every byte will be forced into its own distinct equivalence class. This is useful for debugging the actual generated transitions because it lets one see the transitions defined on actual bytes instead of the equivalence classes.

pub fn unicode_word_boundary(self, yes: bool) -> Config

Heuristically enable Unicode word boundaries.

When set, this will attempt to implement Unicode word boundaries as if they were ASCII word boundaries. This only works when the search input is ASCII only. If a non-ASCII byte is observed while searching, then a MatchError::Quit error is returned.

A possible alternative to enabling this option is to simply use an ASCII word boundary, e.g., via (?-u:\b). The main reason to use this option is if you absolutely need Unicode support. This option lets one use a fast search implementation (a DFA) for some potentially very common cases, while providing the option to fall back to some other regex engine to handle the general case when an error is returned.

If the pattern provided has no Unicode word boundary in it, then this option has no effect. (That is, quitting on a non-ASCII byte only occurs when this option is enabled and a Unicode word boundary is present in the pattern.)

This is almost equivalent to setting all non-ASCII bytes to be quit bytes. The only difference is that this will cause non-ASCII bytes to be quit bytes only when a Unicode word boundary is present in the pattern.

When enabling this option, callers must be prepared to handle a MatchError error during search. When using a Regex, this corresponds to using the try_ suite of methods. Alternatively, if callers can guarantee that their input is ASCII only, then a MatchError::Quit error will never be returned while searching.

This is disabled by default.

Example

This example shows how to heuristically enable Unicode word boundaries in a pattern. It also shows what happens when a search comes across a non-ASCII byte.

use regex_automata::{
    dfa::{Automaton, dense},
    HalfMatch, MatchError, MatchKind,
};

let dfa = dense::Builder::new()
    .configure(dense::Config::new().unicode_word_boundary(true))
    .build(r"\b[0-9]+\b")?;

// The match occurs before the search ever observes the snowman
// character, so no error occurs.
let haystack = "foo 123 ☃".as_bytes();
let expected = Some(HalfMatch::must(0, 7));
let got = dfa.find_leftmost_fwd(haystack)?;
assert_eq!(expected, got);

// Notice that this search fails, even though the snowman character
// occurs after the ending match offset. This is because search
// routines read one byte past the end of the search to account for
// look-around, and indeed, this is required here to determine whether
// the trailing \b matches.
let haystack = "foo 123☃".as_bytes();
let expected = MatchError::Quit { byte: 0xE2, offset: 7 };
let got = dfa.find_leftmost_fwd(haystack);
assert_eq!(Err(expected), got);

pub fn quit(self, byte: u8, yes: bool) -> Config

Add a “quit” byte to the DFA.

When a quit byte is seen during search time, then search will return a MatchError::Quit error indicating the offset at which the search stopped.

A quit byte will always overrule any other aspects of a regex. For example, if the x byte is added as a quit byte and the regex \w is used, then observing x will cause the search to quit immediately despite the fact that x is in the \w class.

This mechanism is primarily useful for heuristically enabling certain features like Unicode word boundaries in a DFA. Namely, if the input to search is ASCII, then a Unicode word boundary can be implemented via an ASCII word boundary with no change in semantics. Thus, a DFA can attempt to match a Unicode word boundary but give up as soon as it observes a non-ASCII byte. Indeed, if callers set all non-ASCII bytes to be quit bytes, then Unicode word boundaries will be permitted when building DFAs. Of course, callers should enable Config::unicode_word_boundary if they want this behavior instead. (The advantage being that non-ASCII quit bytes will only be added if a Unicode word boundary is in the pattern.)

When enabling this option, callers must be prepared to handle a MatchError error during search. When using a Regex, this corresponds to using the try_ suite of methods.

By default, there are no quit bytes set.

Panics

This panics if heuristic Unicode word boundaries are enabled and any non-ASCII byte is removed from the set of quit bytes. Namely, enabling Unicode word boundaries requires setting every non-ASCII byte to a quit byte. So if the caller attempts to undo any of that, then this will panic.

Example

This example shows how to cause a search to terminate if it sees a \n byte. This could be useful if, for example, you wanted to prevent a user supplied pattern from matching across a line boundary.

use regex_automata::{
    dfa::{Automaton, dense},
    HalfMatch, MatchError,
};

let dfa = dense::Builder::new()
    .configure(dense::Config::new().quit(b'\n', true))
    .build(r"foo\p{any}+bar")?;

let haystack = "foo\nbar".as_bytes();
// 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 { byte: 0x0A, offset: 3 };
let got = dfa.find_leftmost_fwd(haystack).unwrap_err();
assert_eq!(expected, got);

pub fn dfa_size_limit(self, bytes: Option<usize>) -> Config

Set a size limit on the total heap used by a DFA.

This size limit is expressed in bytes and is applied during determinization of an NFA into a DFA. If the DFA’s heap usage, and only the DFA, exceeds this configured limit, then determinization is stopped and an error is returned.

This limit does not apply to auxiliary storage used during determinization that isn’t part of the generated DFA.

This limit is only applied during determinization. Currently, there is no way to post-pone this check to after minimization if minimization was enabled.

The total limit on heap used during determinization is the sum of the DFA and determinization size limits.

The default is no limit.

Example

This example shows a DFA that fails to build because of a configured size limit. This particular example also serves as a cautionary tale demonstrating just how big DFAs with large Unicode character classes can get.

use regex_automata::dfa::{dense, Automaton};

// 3MB isn't enough!
dense::Builder::new()
    .configure(dense::Config::new().dfa_size_limit(Some(3_000_000)))
    .build(r"\w{20}")
    .unwrap_err();

// ... but 4MB probably is!
// (Note that DFA sizes aren't necessarily stable between releases.)
let dfa = dense::Builder::new()
    .configure(dense::Config::new().dfa_size_limit(Some(4_000_000)))
    .build(r"\w{20}")?;
let haystack = "A".repeat(20).into_bytes();
assert!(dfa.find_leftmost_fwd(&haystack)?.is_some());

While one needs a little more than 3MB to represent \w{20}, it turns out that you only need a little more than 4KB to represent (?-u:\w{20}). So only use Unicode if you need it!

pub fn determinize_size_limit(self, bytes: Option<usize>) -> Config

Set a size limit on the total heap used by determinization.

This size limit is expressed in bytes and is applied during determinization of an NFA into a DFA. If the heap used for auxiliary storage during determinization (memory that is not in the DFA but necessary for building the DFA) exceeds this configured limit, then determinization is stopped and an error is returned.

This limit does not apply to heap used by the DFA itself.

The total limit on heap used during determinization is the sum of the DFA and determinization size limits.

The default is no limit.

Example

This example shows a DFA that fails to build because of a configured size limit on the amount of heap space used by determinization. This particular example complements the example for Config::dfa_size_limit by demonstrating that not only does Unicode potentially make DFAs themselves big, but it also results in more auxiliary storage during determinization. (Although, auxiliary storage is still not as much as the DFA itself.)

use regex_automata::dfa::{dense, Automaton};

// 300KB isn't enough!
dense::Builder::new()
    .configure(dense::Config::new()
        .determinize_size_limit(Some(300_000))
    )
    .build(r"\w{20}")
    .unwrap_err();

// ... but 400KB probably is!
// (Note that auxiliary storage sizes aren't necessarily stable between
// releases.)
let dfa = dense::Builder::new()
    .configure(dense::Config::new()
        .determinize_size_limit(Some(400_000))
    )
    .build(r"\w{20}")?;
let haystack = "A".repeat(20).into_bytes();
assert!(dfa.find_leftmost_fwd(&haystack)?.is_some());

pub fn get_anchored(&self) -> bool

Returns whether this configuration has enabled anchored searches.

pub fn get_accelerate(&self) -> bool

Returns whether this configuration has enabled simple state acceleration.

pub fn get_minimize(&self) -> bool

Returns whether this configuration has enabled the expensive process of minimizing a DFA.

pub fn get_match_kind(&self) -> MatchKind

Returns the match semantics set in this configuration.

pub fn get_starts_for_each_pattern(&self) -> bool

Returns whether this configuration has enabled anchored starting states for every pattern in the DFA.

pub fn get_byte_classes(&self) -> bool

Returns whether this configuration has enabled byte classes or not. This is typically a debugging oriented option, as disabling it confers no speed benefit.

pub fn get_unicode_word_boundary(&self) -> bool

Returns whether this configuration has enabled heuristic Unicode word boundary support. When enabled, it is possible for a search to return an error.

pub fn get_quit(&self, byte: u8) -> bool

Returns whether this configuration will instruct the DFA to enter a quit state whenever the given byte is seen during a search. When at least one byte has this enabled, it is possible for a search to return an error.

pub fn get_dfa_size_limit(&self) -> Option<usize>

Returns the DFA size limit of this configuration if one was set. The size limit is total number of bytes on the heap that a DFA is permitted to use. If the DFA exceeds this limit during construction, then construction is stopped and an error is returned.

pub fn get_determinize_size_limit(&self) -> Option<usize>

Returns the determinization size limit of this configuration if one was set. The size limit is total number of bytes on the heap that determinization is permitted to use. If determinization exceeds this limit during construction, then construction is stopped and an error is returned.

This is different from the DFA size limit in that this only applies to the auxiliary storage used during determinization. Once determinization is complete, this memory is freed.

The limit on the total heap memory used is the sum of the DFA and determinization size limits.

Trait Implementations

impl Clone for Config

fn clone(&self) -> Config

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Config

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Config

fn default() -> Config

Returns the “default value” for a type.

impl Copy for Config