Crate regex_automata
source ·Expand description
A low level regular expression library that uses deterministic finite automata.
It supports a rich syntax with Unicode support, has 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.
§Overview
This section gives a brief overview of the primary types in this crate:
- A
Regex
provides a way to search for matches of a regular expression. This includes iterating over matches with both the start and end positions of each match. - A
RegexBuilder
provides a way configure many compilation options for a regex. - A
DenseDFA
provides low level access to a DFA that uses a dense representation (uses lots of space, but fast searching). - A
SparseDFA
provides the same API as aDenseDFA
, but uses a sparse representation (uses less space, but slower matching). - A
DFA
trait that defines an interface that all DFAs must implement. - Both dense DFAs and sparse DFAs support serialization to raw bytes and cheap deserialization.
§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::Regex;
let re = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
let text = b"2018-12-24 2016-10-08";
let matches: Vec<(usize, usize)> = re.find_iter(text).collect();
assert_eq!(matches, vec![(0, 10), (11, 21)]);
§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::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<(usize, usize)> = re.find_iter(text).collect();
assert_eq!(matches, vec![(0, 10), (11, 21)]);
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::Regex;
let dense_re = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
let sparse_re = Regex::from_dfas(
dense_re.forward().to_sparse()?,
dense_re.reverse().to_sparse()?,
);
let text = b"2018-12-24 2016-10-08";
let matches: Vec<(usize, usize)> = sparse_re.find_iter(text).collect();
assert_eq!(matches, vec![(0, 10), (11, 21)]);
§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. In particular, deserialization is guaranteed to be cheap because it will always be a constant time operation.
use regex_automata::{DenseDFA, 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 = re1.forward().to_u16()?.to_bytes_native_endian()?;
let rev_bytes = re1.reverse().to_u16()?.to_bytes_native_endian()?;
// now deserialize both---we need to specify the correct type!
let fwd: DenseDFA<&[u16], u16> = unsafe { DenseDFA::from_bytes(&fwd_bytes) };
let rev: DenseDFA<&[u16], u16> = unsafe { DenseDFA::from_bytes(&rev_bytes) };
// finally, reconstruct our regex
let re2 = Regex::from_dfas(fwd, rev);
// we can use it like normal
let text = b"2018-12-24 2016-10-08";
let matches: Vec<(usize, usize)> = re2.find_iter(text).collect();
assert_eq!(matches, vec![(0, 10), (11, 21)]);
There are a few points worth noting here:
- We need to extract the raw DFAs used by the regex and serialize those. You
can build the DFAs manually yourself using
dense::Builder
, but using the DFAs from aRegex
guarantees that the DFAs are built correctly. - We specifically convert the dense DFA to a representation that uses
u16
for its state identifiers usingDenseDFA::to_u16
. While this isn’t strictly necessary, if we skipped this step, then the serialized bytes would useusize
for state identifiers, which does not have a fixed size. Usingu16
ensures that we can deserialize this DFA even on platforms with a smaller pointer size. If our DFA is too big foru16
state identifiers, then one can useu32
oru64
. - To convert the DFA to raw bytes, we use the
to_bytes_native_endian
method. In practice, you’ll want to use eitherDenseDFA::to_bytes_little_endian
orDenseDFA::to_bytes_big_endian
, depending on which platform you’re deserializing your DFA from. If you intend to deserialize on either platform, then you’ll need to serialize both and deserialize the right one depending on your target’s endianness. - Deserializing a DFA requires the use of
unsafe
because the raw bytes must be trusted. In particular, while some degree of sanity checks are performed, nothing guarantees the integrity of the DFA’s transition table since deserialization is a constant time operation. Since searching with a DFA must be able to follow transitions blindly for performance reasons, giving incorrect bytes to the deserialization API can result in memory unsafety.
The same process can be achieved with sparse DFAs as well:
use regex_automata::{SparseDFA, Regex};
let re1 = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
// serialize both
let fwd_bytes = re1.forward().to_u16()?.to_sparse()?.to_bytes_native_endian()?;
let rev_bytes = re1.reverse().to_u16()?.to_sparse()?.to_bytes_native_endian()?;
// now deserialize both---we need to specify the correct type!
let fwd: SparseDFA<&[u8], u16> = unsafe { SparseDFA::from_bytes(&fwd_bytes) };
let rev: SparseDFA<&[u8], u16> = unsafe { SparseDFA::from_bytes(&rev_bytes) };
// finally, reconstruct our regex
let re2 = Regex::from_dfas(fwd, rev);
// we can use it like normal
let text = b"2018-12-24 2016-10-08";
let matches: Vec<(usize, usize)> = re2.find_iter(text).collect();
assert_eq!(matches, vec![(0, 10), (11, 21)]);
Note that unlike dense DFAs, sparse DFAs have no alignment requirements. Conversely, dense DFAs must be be aligned to the same alignment as their state identifier representation.
§Support for no_std
This crate comes with a std
feature that is enabled by default. When the
std
feature is enabled, the API of this crate will include the facilities
necessary for compiling, serializing, deserializing and searching with regular
expressions. When the std
feature is disabled, the API of this crate will
shrink such that it only includes the facilities necessary for deserializing
and searching with regular expressions.
The intended workflow for no_std
environments is thus as follows:
- Write a program with the
std
feature that compiles and serializes a regular expression. Serialization should only happen after first converting the DFAs to use a fixed size state identifier instead of the defaultusize
. You may also need to serialize both little and big endian versions of each DFA. (So that’s 4 DFAs in total for each regex.) - In your
no_std
environment, follow the examples above for deserializing your previously serialized DFAs into regexes. You can then search with them as you would any regex.
Deserialization can happen anywhere. For example, with bytes embedded into a binary or with a file memory mapped at runtime.
Note that the
ucd-generate
tool will do the first step for you with its dfa
or regex
sub-commands.
§Syntax
This crate 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.
Currently, there are a couple limitations. In general, this crate does not support zero-width assertions, although they may be added in the future. This includes:
- Anchors such as
^
,$
,\A
and\z
. - Word boundary assertions such as
\b
and\B
.
It is possible to run a search that is anchored at the beginning of the input.
To do that, set the
RegexBuilder::anchored
option when building a regex. By default, all searches are unanchored.
§Differences with the regex crate
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 crate provides a lower level
regular expression interface that is a bit less convenient while providing more
explicit control over memory usage and search times.
Here are some specific negative differences:
- Compilation can take an exponential amount of time and space in the size
of the regex pattern. While most patterns do not exhibit worst case
exponential time, such patterns do exist. For example,
[01]*1[01]{N}
will build a DFA with2^(N+1)
states. For this reason, untrusted patterns should not be compiled with this library. (In the future, the API may expose an option to return an error if the DFA gets too big.) - This crate does not support sub-match extraction, which can be achieved with the regex crate’s “captures” API. This may be added in the future, but is unlikely.
- While the regex crate doesn’t necessarily sport fast compilation times, the
regexes in this crate are almost universally slow to compile, especially when
they contain large Unicode character classes. For example, on my system,
compiling
\w{3}
with byte classes enabled takes just over 1 second and almost 5MB of memory! (Compiling a sparse regex takes about the same time but only uses about 500KB of memory.) Conversly, compiling the same regex without Unicode support, e.g.,(?-u)\w{3}
, takes under 1 millisecond and less than 5KB of memory. For this reason, you should only use Unicode character classes if you absolutely need them! - This crate does not support regex sets.
- This crate does not support zero-width assertions such as
^
,$
,\b
or\B
. - As a lower level crate, this library does not do literal optimizations. In exchange, you get predictable performance regardless of input. The philosophy here is that literal optimizations should be applied at a higher level, although there is no easy support for this in the ecosystem yet.
- There is no
&str
API like in the regex crate. In this crate, all APIs operate on&[u8]
. By default, match indices are guaranteed to fall on UTF-8 boundaries, unlessRegexBuilder::allow_invalid_utf8
is enabled.
With some of the downsides out of the way, here are some positive differences:
- Both dense and sparse DFAs can be serialized to raw bytes, and then cheaply deserialized. Deserialization always takes constant time since searching can be performed directly on the raw serialized bytes of a DFA.
- This crate was specifically designed so that the searching phase of a DFA has
minimal runtime requirements, and can therefore be used in
no_std
environments. Whileno_std
environments cannot compile regexes, they can deserialize pre-compiled regexes. - Since this crate builds DFAs ahead of time, it will generally out-perform
the
regex
crate on equivalent tasks. The performance difference is likely not large. However, because of a complex set of optimizations in the regex crate (like literal optimizations), an accurate performance comparison may be difficult to do. - Sparse DFAs provide a way to build a DFA ahead of time that sacrifices search performance a small amount, but uses much less storage space. Potentially even less than what the regex crate uses.
- This crate exposes DFAs directly, such as
DenseDFA
andSparseDFA
, which enables one to do less work in some cases. For example, if you only need the end of a match and not the start of a match, then you can use a DFA directly without building aRegex
, which always requires a second DFA to find the start of a match. - Aside from choosing between dense and sparse DFAs, there are several options for configuring the space usage vs search time trade off. These include things like choosing a smaller state identifier representation, to premultiplying state identifiers and splitting a DFA’s alphabet into equivalence classes. Finally, DFA minimization is also provided, but can increase compilation times dramatically.
Re-exports§
Modules§
- Types and routines specific to dense DFAs.
- Types and routines specific to sparse DFAs.
Structs§
- An error that occurred during the construction of a DFA.
- A regular expression that uses deterministic finite automata for fast searching.
- A builder for a regex based on deterministic finite automatons.
Enums§
- The kind of error that occurred.
Traits§
- A trait describing the interface of a deterministic finite automaton (DFA).
- A trait describing the representation of a DFA’s state identifier.