Module dfa

A module for building and searching with deterministic finite automata (DFAs).

Like other modules in this crate, DFAs support a rich regex syntax with Unicode features. DFAs also have extensive options for configuring the best space vs time trade off for your use case and provides support for cheap deserialization of automata for use in no_std environments.

If you're looking for lazy DFAs that build themselves incrementally during search, then please see the top-level hybrid module.

Overview

This section gives a brief overview of the primary types in this module:

There is also a onepass module that provides a one-pass DFA. The unique advantage of this DFA is that, for the class of regexes it can be built with, it supports reporting the spans of matching capturing groups. It is the only DFA in this crate capable of such a thing.

Example: basic regex searching

This example shows how to compile a regex using the default configuration and then use it to find matches in a byte string:

use regex_automata::{Match, dfa::regex::Regex};

let re = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}")?;
let text = b"2018-12-24 2016-10-08";
let matches: Vec<Match> = re.find_iter(text).collect();
assert_eq!(matches, vec![
    Match::must(0, 0..10),
    Match::must(0, 11..21),
]);
# Ok::<(), Box<dyn std::error::Error>>(())

Example: searching with regex sets

The DFAs in this module all fully support searching with multiple regexes simultaneously. You can use this support with standard leftmost-first style searching to find non-overlapping matches:

# if cfg!(miri) { return Ok(()); } // miri takes too long
use regex_automata::{Match, dfa::regex::Regex};

let re = Regex::new_many(&[r"\w+", r"\S+"])?;
let text = b"@foo bar";
let matches: Vec<Match> = re.find_iter(text).collect();
assert_eq!(matches, vec![
    Match::must(1, 0..4),
    Match::must(0, 5..8),
]);
# Ok::<(), Box<dyn std::error::Error>>(())

Example: use sparse DFAs

By default, compiling a regex will use dense DFAs internally. This uses more memory, but executes searches more quickly. If you can abide slower searches (somewhere around 3-5x), then sparse DFAs might make more sense since they can use significantly less space.

Using sparse DFAs is as easy as using Regex::new_sparse instead of Regex::new:

use regex_automata::{Match, dfa::regex::Regex};

let re = Regex::new_sparse(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
let text = b"2018-12-24 2016-10-08";
let matches: Vec<Match> = re.find_iter(text).collect();
assert_eq!(matches, vec![
    Match::must(0, 0..10),
    Match::must(0, 11..21),
]);
# Ok::<(), Box<dyn std::error::Error>>(())

If you already have dense DFAs for some reason, they can be converted to sparse DFAs and used to build a new Regex. For example:

use regex_automata::{Match, dfa::regex::Regex};

let dense_re = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
let sparse_re = Regex::builder().build_from_dfas(
    dense_re.forward().to_sparse()?,
    dense_re.reverse().to_sparse()?,
);
let text = b"2018-12-24 2016-10-08";
let matches: Vec<Match> = sparse_re.find_iter(text).collect();
assert_eq!(matches, vec![
    Match::must(0, 0..10),
    Match::must(0, 11..21),
]);
# Ok::<(), Box<dyn std::error::Error>>(())

Example: deserialize a DFA

This shows how to first serialize a DFA into raw bytes, and then deserialize those raw bytes back into a DFA. While this particular example is a bit contrived, this same technique can be used in your program to deserialize a DFA at start up time or by memory mapping a file.

use regex_automata::{Match, dfa::{dense, regex::Regex}};

let re1 = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
// serialize both the forward and reverse DFAs, see note below
let (fwd_bytes, fwd_pad) = re1.forward().to_bytes_native_endian();
let (rev_bytes, rev_pad) = re1.reverse().to_bytes_native_endian();
// now deserialize both---we need to specify the correct type!
let fwd: dense::DFA<&[u32]> = dense::DFA::from_bytes(&fwd_bytes[fwd_pad..])?.0;
let rev: dense::DFA<&[u32]> = dense::DFA::from_bytes(&rev_bytes[rev_pad..])?.0;
// finally, reconstruct our regex
let re2 = Regex::builder().build_from_dfas(fwd, rev);

// we can use it like normal
let text = b"2018-12-24 2016-10-08";
let matches: Vec<Match> = re2.find_iter(text).collect();
assert_eq!(matches, vec![
    Match::must(0, 0..10),
    Match::must(0, 11..21),
]);
# Ok::<(), Box<dyn std::error::Error>>(())

There are a few points worth noting here:

The same process can be achieved with sparse DFAs as well:

use regex_automata::{Match, dfa::{sparse, regex::Regex}};

let re1 = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
// serialize both
let fwd_bytes = re1.forward().to_sparse()?.to_bytes_native_endian();
let rev_bytes = re1.reverse().to_sparse()?.to_bytes_native_endian();
// now deserialize both---we need to specify the correct type!
let fwd: sparse::DFA<&[u8]> = sparse::DFA::from_bytes(&fwd_bytes)?.0;
let rev: sparse::DFA<&[u8]> = sparse::DFA::from_bytes(&rev_bytes)?.0;
// finally, reconstruct our regex
let re2 = Regex::builder().build_from_dfas(fwd, rev);

// we can use it like normal
let text = b"2018-12-24 2016-10-08";
let matches: Vec<Match> = re2.find_iter(text).collect();
assert_eq!(matches, vec![
    Match::must(0, 0..10),
    Match::must(0, 11..21),
]);
# Ok::<(), Box<dyn std::error::Error>>(())

Note that unlike dense DFAs, sparse DFAs have no alignment requirements. Conversely, dense DFAs must be aligned to the same alignment as a StateID.

Support for no_std and alloc-only

This crate comes with alloc and std features that are enabled by default. When the alloc or std features are enabled, the API of this module will include the facilities necessary for compiling, serializing, deserializing and searching with DFAs. When only the alloc feature is enabled, then implementations of the std::error::Error trait are dropped, but everything else generally remains the same. When both the alloc and std features are disabled, the API of this module will shrink such that it only includes the facilities necessary for deserializing and searching with DFAs.

The intended workflow for no_std environments is thus as follows:

Deserialization can happen anywhere. For example, with bytes embedded into a binary or with a file memory mapped at runtime.

The regex-cli command (found in the same repository as this crate) can be used to serialize DFAs to files and generate Rust code to read them.

Syntax

This module supports the same syntax as the regex crate, since they share the same parser. You can find an exhaustive list of supported syntax in the documentation for the regex crate.

There are two things that are not supported by the DFAs in this module:

There are no plans to lift either of these limitations.

Note that these restrictions are identical to the restrictions on lazy DFAs.

Differences with general purpose regexes

The main goal of the regex crate is to serve as a general purpose regular expression engine. It aims to automatically balance low compile times, fast search times and low memory usage, while also providing a convenient API for users. In contrast, this module provides a lower level regular expression interface based exclusively on DFAs that is a bit less convenient while providing more explicit control over memory usage and search times.

Here are some specific negative differences:

With some of the downsides out of the way, here are some positive differences:

Modules