| 1 |
/*! |
| 2 |
This crate exposes a variety of regex engines used by the `regex` crate. |
| 3 |
It provides a vast, sprawling and "expert" level API to each regex engine. |
| 4 |
The regex engines provided by this crate focus heavily on finite automata |
| 5 |
implementations and specifically guarantee worst case `O(m * n)` time |
| 6 |
complexity for all searches. (Where `m ~ len(regex)` and `n ~ len(haystack)`.) |
| 7 |
|
| 8 |
The primary goal of this crate is to serve as an implementation detail for the |
| 9 |
`regex` crate. A secondary goal is to make its internals available for use by |
| 10 |
others. |
| 11 |
|
| 12 |
# Table of contents |
| 13 |
|
| 14 |
* [Should I be using this crate?](#should-i-be-using-this-crate) gives some |
| 15 |
reasons for and against using this crate. |
| 16 |
* [Examples](#examples) provides a small selection of things you can do with |
| 17 |
this crate. |
| 18 |
* [Available regex engines](#available-regex-engines) provides a hyperlinked |
| 19 |
list of all regex engines in this crate. |
| 20 |
* [API themes](#api-themes) discusses common elements used throughout this |
| 21 |
crate. |
| 22 |
* [Crate features](#crate-features) documents the extensive list of Cargo |
| 23 |
features available. |
| 24 |
|
| 25 |
# Should I be using this crate? |
| 26 |
|
| 27 |
If you find yourself here because you just want to use regexes, then you should |
| 28 |
first check out whether the [`regex` crate](https://docs.rs/regex) meets |
| 29 |
your needs. It provides a streamlined and difficult-to-misuse API for regex |
| 30 |
searching. |
| 31 |
|
| 32 |
If you're here because there is something specific you want to do that can't |
| 33 |
be easily done with `regex` crate, then you are perhaps in the right place. |
| 34 |
It's most likely that the first stop you'll want to make is to explore the |
| 35 |
[`meta` regex APIs](meta). Namely, the `regex` crate is just a light wrapper |
| 36 |
over a [`meta::Regex`], so its API will probably be the easiest to transition |
| 37 |
to. In contrast to the `regex` crate, the `meta::Regex` API supports more |
| 38 |
search parameters and does multi-pattern searches. However, it isn't quite as |
| 39 |
ergonomic. |
| 40 |
|
| 41 |
Otherwise, the following is an inexhaustive list of reasons to use this crate: |
| 42 |
|
| 43 |
* You want to analyze or use a [Thompson `NFA`](nfa::thompson::NFA) directly. |
| 44 |
* You want more powerful multi-pattern search than what is provided by |
| 45 |
`RegexSet` in the `regex` crate. All regex engines in this crate support |
| 46 |
multi-pattern searches. |
| 47 |
* You want to use one of the `regex` crate's internal engines directly because |
| 48 |
of some interesting configuration that isn't possible via the `regex` crate. |
| 49 |
For example, a [lazy DFA's configuration](hybrid::dfa::Config) exposes a |
| 50 |
dizzying number of options for controlling its execution. |
| 51 |
* You want to use the lower level search APIs. For example, both the [lazy |
| 52 |
DFA](hybrid::dfa) and [fully compiled DFAs](dfa) support searching by exploring |
| 53 |
the automaton one state at a time. This might be useful, for example, for |
| 54 |
stream searches or searches of strings stored in non-contiguous in memory. |
| 55 |
* You want to build a fully compiled DFA and then [use zero-copy |
| 56 |
deserialization](dfa::dense::DFA::from_bytes) to load it into memory and use |
| 57 |
it for searching. This use case is supported in core-only no-std/no-alloc |
| 58 |
environments. |
| 59 |
* You want to run [anchored searches](Input::anchored) without using the `^` |
| 60 |
anchor in your regex pattern. |
| 61 |
* You need to work-around contention issues with |
| 62 |
sharing a regex across multiple threads. The |
| 63 |
[`meta::Regex::search_with`](meta::Regex::search_with) API permits bypassing |
| 64 |
any kind of synchronization at all by requiring the caller to provide the |
| 65 |
mutable scratch spaced needed during a search. |
| 66 |
* You want to build your own regex engine on top of the `regex` crate's |
| 67 |
infrastructure. |
| 68 |
|
| 69 |
# Examples |
| 70 |
|
| 71 |
This section tries to identify a few interesting things you can do with this |
| 72 |
crate and demonstrates them. |
| 73 |
|
| 74 |
### Multi-pattern searches with capture groups |
| 75 |
|
| 76 |
One of the more frustrating limitations of `RegexSet` in the `regex` crate |
| 77 |
(at the time of writing) is that it doesn't report match positions. With this |
| 78 |
crate, multi-pattern support was intentionally designed in from the beginning, |
| 79 |
which means it works in all regex engines and even for capture groups as well. |
| 80 |
|
| 81 |
This example shows how to search for matches of multiple regexes, where each |
| 82 |
regex uses the same capture group names to parse different key-value formats. |
| 83 |
|
| 84 |
``` |
| 85 |
use regex_automata::{meta::Regex, PatternID}; |
| 86 |
|
| 87 |
let re = Regex::new_many(&[ |
| 88 |
r#"(?m)^(?<key>[[:word:]]+)=(?<val>[[:word:]]+)$"#, |
| 89 |
r#"(?m)^(?<key>[[:word:]]+)="(?<val>[^"]+)"$"#, |
| 90 |
r#"(?m)^(?<key>[[:word:]]+)='(?<val>[^']+)'$"#, |
| 91 |
r#"(?m)^(?<key>[[:word:]]+):\s*(?<val>[[:word:]]+)$"#, |
| 92 |
])?; |
| 93 |
let hay = r#" |
| 94 |
best_album="Blow Your Face Out" |
| 95 |
best_quote='"then as it was, then again it will be"' |
| 96 |
best_year=1973 |
| 97 |
best_simpsons_episode: HOMR |
| 98 |
"#; |
| 99 |
let mut kvs = vec![]; |
| 100 |
for caps in re.captures_iter(hay) { |
| 101 |
// N.B. One could use capture indices '1' and '2' here |
| 102 |
// as well. Capture indices are local to each pattern. |
| 103 |
// (Just like names are.) |
| 104 |
let key = &hay[caps.get_group_by_name("key").unwrap()]; |
| 105 |
let val = &hay[caps.get_group_by_name("val").unwrap()]; |
| 106 |
kvs.push((key, val)); |
| 107 |
} |
| 108 |
assert_eq!(kvs, vec![ |
| 109 |
("best_album", "Blow Your Face Out"), |
| 110 |
("best_quote", "\"then as it was, then again it will be\""), |
| 111 |
("best_year", "1973"), |
| 112 |
("best_simpsons_episode", "HOMR"), |
| 113 |
]); |
| 114 |
|
| 115 |
# Ok::<(), Box<dyn std::error::Error>>(()) |
| 116 |
``` |
| 117 |
|
| 118 |
### Build a full DFA and walk it manually |
| 119 |
|
| 120 |
One of the regex engines in this crate is a fully compiled DFA. It takes worst |
| 121 |
case exponential time to build, but once built, it can be easily explored and |
| 122 |
used for searches. Here's a simple example that uses its lower level APIs to |
| 123 |
implement a simple anchored search by hand. |
| 124 |
|
| 125 |
``` |
| 126 |
use regex_automata::{dfa::{Automaton, dense}, Input}; |
| 127 |
|
| 128 |
let dfa = dense::DFA::new(r"(?-u)\b[A-Z]\w+z\b")?; |
| 129 |
let haystack = "Quartz"; |
| 130 |
|
| 131 |
// The start state is determined by inspecting the position and the |
| 132 |
// initial bytes of the haystack. |
| 133 |
let mut state = dfa.start_state_forward(&Input::new(haystack))?; |
| 134 |
// Walk all the bytes in the haystack. |
| 135 |
for &b in haystack.as_bytes().iter() { |
| 136 |
state = dfa.next_state(state, b); |
| 137 |
} |
| 138 |
// DFAs in this crate require an explicit |
| 139 |
// end-of-input transition if a search reaches |
| 140 |
// the end of a haystack. |
| 141 |
state = dfa.next_eoi_state(state); |
| 142 |
assert!(dfa.is_match_state(state)); |
| 143 |
|
| 144 |
# Ok::<(), Box<dyn std::error::Error>>(()) |
| 145 |
``` |
| 146 |
|
| 147 |
Or do the same with a lazy DFA that avoids exponential worst case compile time, |
| 148 |
but requires mutable scratch space to lazily build the DFA during the search. |
| 149 |
|
| 150 |
``` |
| 151 |
use regex_automata::{hybrid::dfa::DFA, Input}; |
| 152 |
|
| 153 |
let dfa = DFA::new(r"(?-u)\b[A-Z]\w+z\b")?; |
| 154 |
let mut cache = dfa.create_cache(); |
| 155 |
let hay = "Quartz"; |
| 156 |
|
| 157 |
// The start state is determined by inspecting the position and the |
| 158 |
// initial bytes of the haystack. |
| 159 |
let mut state = dfa.start_state_forward(&mut cache, &Input::new(hay))?; |
| 160 |
// Walk all the bytes in the haystack. |
| 161 |
for &b in hay.as_bytes().iter() { |
| 162 |
state = dfa.next_state(&mut cache, state, b)?; |
| 163 |
} |
| 164 |
// DFAs in this crate require an explicit |
| 165 |
// end-of-input transition if a search reaches |
| 166 |
// the end of a haystack. |
| 167 |
state = dfa.next_eoi_state(&mut cache, state)?; |
| 168 |
assert!(state.is_match()); |
| 169 |
|
| 170 |
# Ok::<(), Box<dyn std::error::Error>>(()) |
| 171 |
``` |
| 172 |
|
| 173 |
### Find all overlapping matches |
| 174 |
|
| 175 |
This example shows how to build a DFA and use it to find all possible matches, |
| 176 |
including overlapping matches. A similar example will work with a lazy DFA as |
| 177 |
well. This also works with multiple patterns and will report all matches at the |
| 178 |
same position where multiple patterns match. |
| 179 |
|
| 180 |
``` |
| 181 |
use regex_automata::{ |
| 182 |
dfa::{dense, Automaton, OverlappingState}, |
| 183 |
Input, MatchKind, |
| 184 |
}; |
| 185 |
|
| 186 |
let dfa = dense::DFA::builder() |
| 187 |
.configure(dense::DFA::config().match_kind(MatchKind::All)) |
| 188 |
.build(r"(?-u)\w{3,}")?; |
| 189 |
let input = Input::new("homer marge bart lisa maggie"); |
| 190 |
let mut state = OverlappingState::start(); |
| 191 |
|
| 192 |
let mut matches = vec![]; |
| 193 |
while let Some(hm) = { |
| 194 |
dfa.try_search_overlapping_fwd(&input, &mut state)?; |
| 195 |
state.get_match() |
| 196 |
} { |
| 197 |
matches.push(hm.offset()); |
| 198 |
} |
| 199 |
assert_eq!(matches, vec![ |
| 200 |
3, 4, 5, // hom, home, homer |
| 201 |
9, 10, 11, // mar, marg, marge |
| 202 |
15, 16, // bar, bart |
| 203 |
20, 21, // lis, lisa |
| 204 |
25, 26, 27, 28, // mag, magg, maggi, maggie |
| 205 |
]); |
| 206 |
|
| 207 |
# Ok::<(), Box<dyn std::error::Error>>(()) |
| 208 |
``` |
| 209 |
|
| 210 |
# Available regex engines |
| 211 |
|
| 212 |
The following is a complete list of all regex engines provided by this crate, |
| 213 |
along with a very brief description of it and why you might want to use it. |
| 214 |
|
| 215 |
* [`dfa::regex::Regex`] is a regex engine that works on top of either |
| 216 |
[dense](dfa::dense) or [sparse](dfa::sparse) fully compiled DFAs. You might |
| 217 |
use a DFA if you need the fastest possible regex engine in this crate and can |
| 218 |
afford the exorbitant memory usage usually required by DFAs. Low level APIs on |
| 219 |
fully compiled DFAs are provided by the [`Automaton` trait](dfa::Automaton). |
| 220 |
Fully compiled dense DFAs can handle all regexes except for searching a regex |
| 221 |
with a Unicode word boundary on non-ASCII haystacks. A fully compiled DFA based |
| 222 |
regex can only report the start and end of each match. |
| 223 |
* [`hybrid::regex::Regex`] is a regex engine that works on top of a lazily |
| 224 |
built DFA. Its performance profile is very similar to that of fully compiled |
| 225 |
DFAs, but can be slower in some pathological cases. Fully compiled DFAs are |
| 226 |
also amenable to more optimizations, such as state acceleration, that aren't |
| 227 |
available in a lazy DFA. You might use this lazy DFA if you can't abide the |
| 228 |
worst case exponential compile time of a full DFA, but still want the DFA |
| 229 |
search performance in the vast majority of cases. A lazy DFA based regex can |
| 230 |
only report the start and end of each match. |
| 231 |
* [`dfa::onepass::DFA`] is a regex engine that is implemented as a DFA, but |
| 232 |
can report the matches of each capture group in addition to the start and end |
| 233 |
of each match. The catch is that it only works on a somewhat small subset of |
| 234 |
regexes known as "one-pass." You'll want to use this for cases when you need |
| 235 |
capture group matches and the regex is one-pass since it is likely to be faster |
| 236 |
than any alternative. A one-pass DFA can handle all types of regexes, but does |
| 237 |
have some reasonable limits on the number of capture groups it can handle. |
| 238 |
* [`nfa::thompson::backtrack::BoundedBacktracker`] is a regex engine that uses |
| 239 |
backtracking, but keeps track of the work it has done to avoid catastrophic |
| 240 |
backtracking. Like the one-pass DFA, it provides the matches of each capture |
| 241 |
group. It retains the `O(m * n)` worst case time bound. This tends to be slower |
| 242 |
than the one-pass DFA regex engine, but faster than the PikeVM. It can handle |
| 243 |
all types of regexes, but usually only works well with small haystacks and |
| 244 |
small regexes due to the memory required to avoid redoing work. |
| 245 |
* [`nfa::thompson::pikevm::PikeVM`] is a regex engine that can handle all |
| 246 |
regexes, of all sizes and provides capture group matches. It tends to be a tool |
| 247 |
of last resort because it is also usually the slowest regex engine. |
| 248 |
* [`meta::Regex`] is the meta regex engine that combines *all* of the above |
| 249 |
engines into one. The reason for this is that each of the engines above have |
| 250 |
their own caveats such as, "only handles a subset of regexes" or "is generally |
| 251 |
slow." The meta regex engine accounts for all of these caveats and composes |
| 252 |
the engines in a way that attempts to mitigate each engine's weaknesses while |
| 253 |
emphasizing its strengths. For example, it will attempt to run a lazy DFA even |
| 254 |
if it might fail. In which case, it will restart the search with a likely |
| 255 |
slower but more capable regex engine. The meta regex engine is what you should |
| 256 |
default to. Use one of the above engines directly only if you have a specific |
| 257 |
reason to. |
| 258 |
|
| 259 |
# API themes |
| 260 |
|
| 261 |
While each regex engine has its own APIs and configuration options, there are |
| 262 |
some general themes followed by all of them. |
| 263 |
|
| 264 |
### The `Input` abstraction |
| 265 |
|
| 266 |
Most search routines in this crate accept anything that implements |
| 267 |
`Into<Input>`. Both `&str` and `&[u8]` haystacks satisfy this constraint, which |
| 268 |
means that things like `engine.search("foo")` will work as you would expect. |
| 269 |
|
| 270 |
By virtue of accepting an `Into<Input>` though, callers can provide more than |
| 271 |
just a haystack. Indeed, the [`Input`] type has more details, but briefly, |
| 272 |
callers can use it to configure various aspects of the search: |
| 273 |
|
| 274 |
* The span of the haystack to search via [`Input::span`] or [`Input::range`], |
| 275 |
which might be a substring of the haystack. |
| 276 |
* Whether to run an anchored search or not via [`Input::anchored`]. This |
| 277 |
permits one to require matches to start at the same offset that the search |
| 278 |
started. |
| 279 |
* Whether to ask the regex engine to stop as soon as a match is seen via |
| 280 |
[`Input::earliest`]. This can be used to find the offset of a match as soon |
| 281 |
as it is known without waiting for the full leftmost-first match to be found. |
| 282 |
This can also be used to avoid the worst case `O(m * n^2)` time complexity |
| 283 |
of iteration. |
| 284 |
|
| 285 |
Some lower level search routines accept an `&Input` for performance reasons. |
| 286 |
In which case, `&Input::new("haystack")` can be used for a simple search. |
| 287 |
|
| 288 |
### Error reporting |
| 289 |
|
| 290 |
Most, but not all, regex engines in this crate can fail to execute a search. |
| 291 |
When a search fails, callers cannot determine whether or not a match exists. |
| 292 |
That is, the result is indeterminate. |
| 293 |
|
| 294 |
Search failure, in all cases in this crate, is represented by a [`MatchError`]. |
| 295 |
Routines that can fail start with the `try_` prefix in their name. For example, |
| 296 |
[`hybrid::regex::Regex::try_search`] can fail for a number of reasons. |
| 297 |
Conversely, routines that either can't fail or can panic on failure lack the |
| 298 |
`try_` prefix. For example, [`hybrid::regex::Regex::find`] will panic in |
| 299 |
cases where [`hybrid::regex::Regex::try_search`] would return an error, and |
| 300 |
[`meta::Regex::find`] will never panic. Therefore, callers need to pay close |
| 301 |
attention to the panicking conditions in the documentation. |
| 302 |
|
| 303 |
In most cases, the reasons that a search fails are either predictable or |
| 304 |
configurable, albeit at some additional cost. |
| 305 |
|
| 306 |
An example of predictable failure is |
| 307 |
[`BoundedBacktracker::try_search`](nfa::thompson::backtrack::BoundedBacktracker::try_search). |
| 308 |
Namely, it fails whenever the multiplication of the haystack, the regex and some |
| 309 |
constant exceeds the |
| 310 |
[configured visited capacity](nfa::thompson::backtrack::Config::visited_capacity). |
| 311 |
Callers can predict the failure in terms of haystack length via the |
| 312 |
[`BoundedBacktracker::max_haystack_len`](nfa::thompson::backtrack::BoundedBacktracker::max_haystack_len) |
| 313 |
method. While this form of failure is technically avoidable by increasing the |
| 314 |
visited capacity, it isn't practical to do so for all inputs because the |
| 315 |
memory usage required for larger haystacks becomes impractically large. So in |
| 316 |
practice, if one is using the bounded backtracker, you really do have to deal |
| 317 |
with the failure. |
| 318 |
|
| 319 |
An example of configurable failure happens when one enables heuristic support |
| 320 |
for Unicode word boundaries in a DFA. Namely, since the DFAs in this crate |
| 321 |
(except for the one-pass DFA) do not support Unicode word boundaries on |
| 322 |
non-ASCII haystacks, building a DFA from an NFA that contains a Unicode word |
| 323 |
boundary will itself fail. However, one can configure DFAs to still be built in |
| 324 |
this case by |
| 325 |
[configuring heuristic support for Unicode word boundaries](hybrid::dfa::Config::unicode_word_boundary). |
| 326 |
If the NFA the DFA is built from contains a Unicode word boundary, then the |
| 327 |
DFA will still be built, but special transitions will be added to every state |
| 328 |
that cause the DFA to fail if any non-ASCII byte is seen. This failure happens |
| 329 |
at search time and it requires the caller to opt into this. |
| 330 |
|
| 331 |
There are other ways for regex engines to fail in this crate, but the above |
| 332 |
two should represent the general theme of failures one can find. Dealing |
| 333 |
with these failures is, in part, one the responsibilities of the [meta regex |
| 334 |
engine](meta). Notice, for example, that the meta regex engine exposes an API |
| 335 |
that never returns an error nor panics. It carefully manages all of the ways |
| 336 |
in which the regex engines can fail and either avoids the predictable ones |
| 337 |
entirely (e.g., the bounded backtracker) or reacts to configured failures by |
| 338 |
falling back to a different engine (e.g., the lazy DFA quitting because it saw |
| 339 |
a non-ASCII byte). |
| 340 |
|
| 341 |
### Configuration and Builders |
| 342 |
|
| 343 |
Most of the regex engines in this crate come with two types to facilitate |
| 344 |
building the regex engine: a `Config` and a `Builder`. A `Config` is usually |
| 345 |
specific to that particular regex engine, but other objects such as parsing and |
| 346 |
NFA compilation have `Config` types too. A `Builder` is the thing responsible |
| 347 |
for taking inputs (either pattern strings or already-parsed patterns or even |
| 348 |
NFAs directly) and turning them into an actual regex engine that can be used |
| 349 |
for searching. |
| 350 |
|
| 351 |
The main reason why building a regex engine is a bit complicated is because |
| 352 |
of the desire to permit composition with de-coupled components. For example, |
| 353 |
you might want to [manually construct a Thompson NFA](nfa::thompson::Builder) |
| 354 |
and then build a regex engine from it without ever using a regex parser |
| 355 |
at all. On the other hand, you might also want to build a regex engine directly |
| 356 |
from the concrete syntax. This demonstrates why regex engine construction is |
| 357 |
so flexible: it needs to support not just convenient construction, but also |
| 358 |
construction from parts built elsewhere. |
| 359 |
|
| 360 |
This is also in turn why there are many different `Config` structs in this |
| 361 |
crate. Let's look more closely at an example: [`hybrid::regex::Builder`]. It |
| 362 |
accepts three different `Config` types for configuring construction of a lazy |
| 363 |
DFA regex: |
| 364 |
|
| 365 |
* [`hybrid::regex::Builder::syntax`] accepts a |
| 366 |
[`util::syntax::Config`] for configuring the options found in the |
| 367 |
[`regex-syntax`](regex_syntax) crate. For example, whether to match |
| 368 |
case insensitively. |
| 369 |
* [`hybrid::regex::Builder::thompson`] accepts a [`nfa::thompson::Config`] for |
| 370 |
configuring construction of a [Thompson NFA](nfa::thompson::NFA). For example, |
| 371 |
whether to build an NFA that matches the reverse language described by the |
| 372 |
regex. |
| 373 |
* [`hybrid::regex::Builder::dfa`] accept a [`hybrid::dfa::Config`] for |
| 374 |
configuring construction of the pair of underlying lazy DFAs that make up the |
| 375 |
lazy DFA regex engine. For example, changing the capacity of the cache used to |
| 376 |
store the transition table. |
| 377 |
|
| 378 |
The lazy DFA regex engine uses all three of those configuration objects for |
| 379 |
methods like [`hybrid::regex::Builder::build`], which accepts a pattern |
| 380 |
string containing the concrete syntax of your regex. It uses the syntax |
| 381 |
configuration to parse it into an AST and translate it into an HIR. Then the |
| 382 |
NFA configuration when compiling the HIR into an NFA. And then finally the DFA |
| 383 |
configuration when lazily determinizing the NFA into a DFA. |
| 384 |
|
| 385 |
Notice though that the builder also has a |
| 386 |
[`hybrid::regex::Builder::build_from_dfas`] constructor. This permits callers |
| 387 |
to build the underlying pair of lazy DFAs themselves (one for the forward |
| 388 |
searching to find the end of a match and one for the reverse searching to find |
| 389 |
the start of a match), and then build the regex engine from them. The lazy |
| 390 |
DFAs, in turn, have their own builder that permits [construction directly from |
| 391 |
a Thompson NFA](hybrid::dfa::Builder::build_from_nfa). Continuing down the |
| 392 |
rabbit hole, a Thompson NFA has its own compiler that permits [construction |
| 393 |
directly from an HIR](nfa::thompson::Compiler::build_from_hir). The lazy DFA |
| 394 |
regex engine builder lets you follow this rabbit hole all the way down, but |
| 395 |
also provides convenience routines that do it for you when you don't need |
| 396 |
precise control over every component. |
| 397 |
|
| 398 |
The [meta regex engine](meta) is a good example of something that utilizes the |
| 399 |
full flexibility of these builders. It often needs not only precise control |
| 400 |
over each component, but also shares them across multiple regex engines. |
| 401 |
(Most sharing is done by internal reference accounting. For example, an |
| 402 |
[`NFA`](nfa::thompson::NFA) is reference counted internally which makes cloning |
| 403 |
cheap.) |
| 404 |
|
| 405 |
### Size limits |
| 406 |
|
| 407 |
Unlike the `regex` crate, the `regex-automata` crate specifically does not |
| 408 |
enable any size limits by default. That means users of this crate need to |
| 409 |
be quite careful when using untrusted patterns. Namely, because bounded |
| 410 |
repetitions can grow exponentially by stacking them, it is possible to build a |
| 411 |
very large internal regex object from just a small pattern string. For example, |
| 412 |
the NFA built from the pattern `a{10}{10}{10}{10}{10}{10}{10}` is over 240MB. |
| 413 |
|
| 414 |
There are multiple size limit options in this crate. If one or more size limits |
| 415 |
are relevant for the object you're building, they will be configurable via |
| 416 |
methods on a corresponding `Config` type. |
| 417 |
|
| 418 |
# Crate features |
| 419 |
|
| 420 |
This crate has a dizzying number of features. The main idea is to be able to |
| 421 |
control how much stuff you pull in for your specific use case, since the full |
| 422 |
crate is quite large and can dramatically increase compile times and binary |
| 423 |
size. |
| 424 |
|
| 425 |
The most barebones but useful configuration is to disable all default features |
| 426 |
and enable only `dfa-search`. This will bring in just the DFA deserialization |
| 427 |
and search routines without any dependency on `std` or `alloc`. This does |
| 428 |
require generating and serializing a DFA, and then storing it somewhere, but |
| 429 |
it permits regex searches in freestanding or embedded environments. |
| 430 |
|
| 431 |
Because there are so many features, they are split into a few groups. |
| 432 |
|
| 433 |
The default set of features is: `std`, `syntax`, `perf`, `unicode`, `meta`, |
| 434 |
`nfa`, `dfa` and `hybrid`. Basically, the default is to enable everything |
| 435 |
except for development related features like `logging`. |
| 436 |
|
| 437 |
### Ecosystem features |
| 438 |
|
| 439 |
* **std** - Enables use of the standard library. In terms of APIs, this usually |
| 440 |
just means that error types implement the `std::error::Error` trait. Otherwise, |
| 441 |
`std` sometimes enables the code to be faster, for example, using a `HashMap` |
| 442 |
instead of a `BTreeMap`. (The `std` feature matters more for dependencies like |
| 443 |
`aho-corasick` and `memchr`, where `std` is required to enable certain classes |
| 444 |
of SIMD optimizations.) Enabling `std` automatically enables `alloc`. |
| 445 |
* **alloc** - Enables use of the `alloc` library. This is required for most |
| 446 |
APIs in this crate. The main exception is deserializing and searching with |
| 447 |
fully compiled DFAs. |
| 448 |
* **logging** - Adds a dependency on the `log` crate and makes this crate emit |
| 449 |
log messages of varying degrees of utility. The log messages are especially |
| 450 |
useful in trying to understand what the meta regex engine is doing. |
| 451 |
|
| 452 |
### Performance features |
| 453 |
|
| 454 |
* **perf** - Enables all of the below features. |
| 455 |
* **perf-inline** - When enabled, `inline(always)` is used in (many) strategic |
| 456 |
locations to help performance at the expense of longer compile times and |
| 457 |
increased binary size. |
| 458 |
* **perf-literal** - Enables all literal related optimizations. |
| 459 |
* **perf-literal-substring** - Enables all single substring literal |
| 460 |
optimizations. This includes adding a dependency on the `memchr` crate. |
| 461 |
* **perf-literal-multisubstring** - Enables all multiple substring literal |
| 462 |
optimizations. This includes adding a dependency on the `aho-corasick` |
| 463 |
crate. |
| 464 |
|
| 465 |
### Unicode features |
| 466 |
|
| 467 |
* **unicode** - |
| 468 |
Enables all Unicode features. This feature is enabled by default, and will |
| 469 |
always cover all Unicode features, even if more are added in the future. |
| 470 |
* **unicode-age** - |
| 471 |
Provide the data for the |
| 472 |
[Unicode `Age` property](https://www.unicode.org/reports/tr44/tr44-24.html#Character_Age). |
| 473 |
This makes it possible to use classes like `\p{Age:6.0}` to refer to all |
| 474 |
codepoints first introduced in Unicode 6.0 |
| 475 |
* **unicode-bool** - |
| 476 |
Provide the data for numerous Unicode boolean properties. The full list |
| 477 |
is not included here, but contains properties like `Alphabetic`, `Emoji`, |
| 478 |
`Lowercase`, `Math`, `Uppercase` and `White_Space`. |
| 479 |
* **unicode-case** - |
| 480 |
Provide the data for case insensitive matching using |
| 481 |
[Unicode's "simple loose matches" specification](https://www.unicode.org/reports/tr18/#Simple_Loose_Matches). |
| 482 |
* **unicode-gencat** - |
| 483 |
Provide the data for |
| 484 |
[Unicode general categories](https://www.unicode.org/reports/tr44/tr44-24.html#General_Category_Values). |
| 485 |
This includes, but is not limited to, `Decimal_Number`, `Letter`, |
| 486 |
`Math_Symbol`, `Number` and `Punctuation`. |
| 487 |
* **unicode-perl** - |
| 488 |
Provide the data for supporting the Unicode-aware Perl character classes, |
| 489 |
corresponding to `\w`, `\s` and `\d`. This is also necessary for using |
| 490 |
Unicode-aware word boundary assertions. Note that if this feature is |
| 491 |
disabled, the `\s` and `\d` character classes are still available if the |
| 492 |
`unicode-bool` and `unicode-gencat` features are enabled, respectively. |
| 493 |
* **unicode-script** - |
| 494 |
Provide the data for |
| 495 |
[Unicode scripts and script extensions](https://www.unicode.org/reports/tr24/). |
| 496 |
This includes, but is not limited to, `Arabic`, `Cyrillic`, `Hebrew`, |
| 497 |
`Latin` and `Thai`. |
| 498 |
* **unicode-segment** - |
| 499 |
Provide the data necessary to provide the properties used to implement the |
| 500 |
[Unicode text segmentation algorithms](https://www.unicode.org/reports/tr29/). |
| 501 |
This enables using classes like `\p{gcb=Extend}`, `\p{wb=Katakana}` and |
| 502 |
`\p{sb=ATerm}`. |
| 503 |
* **unicode-word-boundary** - |
| 504 |
Enables support for Unicode word boundaries, i.e., `\b`, in regexes. When |
| 505 |
this and `unicode-perl` are enabled, then data tables from `regex-syntax` are |
| 506 |
used to implement Unicode word boundaries. However, if `regex-syntax` isn't |
| 507 |
enabled as a dependency then one can still enable this feature. It will |
| 508 |
cause `regex-automata` to bundle its own data table that would otherwise be |
| 509 |
redundant with `regex-syntax`'s table. |
| 510 |
|
| 511 |
### Regex engine features |
| 512 |
|
| 513 |
* **syntax** - Enables a dependency on `regex-syntax`. This makes APIs |
| 514 |
for building regex engines from pattern strings available. Without the |
| 515 |
`regex-syntax` dependency, the only way to build a regex engine is generally |
| 516 |
to deserialize a previously built DFA or to hand assemble an NFA using its |
| 517 |
[builder API](nfa::thompson::Builder). Once you have an NFA, you can build any |
| 518 |
of the regex engines in this crate. The `syntax` feature also enables `alloc`. |
| 519 |
* **meta** - Enables the meta regex engine. This also enables the `syntax` and |
| 520 |
`nfa-pikevm` features, as both are the minimal requirements needed. The meta |
| 521 |
regex engine benefits from enabling any of the other regex engines and will |
| 522 |
use them automatically when appropriate. |
| 523 |
* **nfa** - Enables all NFA related features below. |
| 524 |
* **nfa-thompson** - Enables the Thompson NFA APIs. This enables `alloc`. |
| 525 |
* **nfa-pikevm** - Enables the PikeVM regex engine. This enables |
| 526 |
`nfa-thompson`. |
| 527 |
* **nfa-backtrack** - Enables the bounded backtracker regex engine. This |
| 528 |
enables `nfa-thompson`. |
| 529 |
* **dfa** - Enables all DFA related features below. |
| 530 |
* **dfa-build** - Enables APIs for determinizing DFAs from NFAs. This |
| 531 |
enables `nfa-thompson` and `dfa-search`. |
| 532 |
* **dfa-search** - Enables APIs for searching with DFAs. |
| 533 |
* **dfa-onepass** - Enables the one-pass DFA API. This enables |
| 534 |
`nfa-thompson`. |
| 535 |
* **hybrid** - Enables the hybrid NFA/DFA or "lazy DFA" regex engine. This |
| 536 |
enables `alloc` and `nfa-thompson`. |
| 537 |
|
| 538 |
*/ |
| 539 |
|
| 540 |
// We are no_std. |
| 541 |
#![no_std] |
| 542 |
// All APIs need docs! |
| 543 |
#![deny(missing_docs)] |
| 544 |
// Some intra-doc links are broken when certain features are disabled, so we |
| 545 |
// only bleat about it when most (all?) features are enabled. But when we do, |
| 546 |
// we block the build. Links need to work. |
| 547 |
#![cfg_attr( |
| 548 |
all( |
| 549 |
feature = "std", |
| 550 |
feature = "nfa", |
| 551 |
feature = "dfa", |
| 552 |
feature = "hybrid" |
| 553 |
), |
| 554 |
deny(rustdoc::broken_intra_doc_links) |
| 555 |
)] |
| 556 |
// Broken rustdoc links are very easy to come by when you start disabling |
| 557 |
// features. Namely, features tend to change imports, and imports change what's |
| 558 |
// available to link to. |
| 559 |
// |
| 560 |
// Basically, we just don't support rustdoc for anything other than the maximal |
| 561 |
// feature configuration. Other configurations will work, they just won't be |
| 562 |
// perfect. |
| 563 |
// |
| 564 |
// So here, we specifically allow them so we don't even get warned about them. |
| 565 |
#![cfg_attr( |
| 566 |
not(all( |
| 567 |
feature = "std", |
| 568 |
feature = "nfa", |
| 569 |
feature = "dfa", |
| 570 |
feature = "hybrid" |
| 571 |
)), |
| 572 |
allow(rustdoc::broken_intra_doc_links) |
| 573 |
)] |
| 574 |
// Kinda similar, but eliminating all of the dead code and unused import |
| 575 |
// warnings for every feature combo is a fool's errand. Instead, we just |
| 576 |
// suppress those, but still let them through in a common configuration when we |
| 577 |
// build most of everything. |
| 578 |
// |
| 579 |
// This does actually suggest that when features are disabled, we are actually |
| 580 |
// compiling more code than we need to be. And this is perhaps not so great |
| 581 |
// because disabling features is usually done in order to reduce compile times |
| 582 |
// by reducing the amount of code one compiles... However, usually, most of the |
| 583 |
// time this dead code is a relatively small amount from the 'util' module. |
| 584 |
// But... I confess... There isn't a ton of visibility on this. |
| 585 |
// |
| 586 |
// I'm happy to try to address this in a different way, but "let's annotate |
| 587 |
// every function in 'util' with some non-local combination of features" just |
| 588 |
// cannot be the way forward. |
| 589 |
#![cfg_attr( |
| 590 |
not(all( |
| 591 |
feature = "std", |
| 592 |
feature = "nfa", |
| 593 |
feature = "dfa", |
| 594 |
feature = "hybrid", |
| 595 |
feature = "perf-literal-substring", |
| 596 |
feature = "perf-literal-multisubstring", |
| 597 |
)), |
| 598 |
allow(dead_code, unused_imports, unused_variables) |
| 599 |
)] |
| 600 |
// We generally want all types to impl Debug. |
| 601 |
#![warn(missing_debug_implementations)] |
| 602 |
// No clue why this thing is still unstable because it's pretty amazing. This |
| 603 |
// adds Cargo feature annotations to items in the rustdoc output. Which is |
| 604 |
// sadly hugely beneficial for this crate due to the number of features. |
| 605 |
#![cfg_attr(docsrs, feature(doc_auto_cfg))] |
| 606 |
|
| 607 |
// I have literally never tested this crate on 16-bit, so it is quite |
| 608 |
// suspicious to advertise support for it. But... the regex crate, at time |
| 609 |
// of writing, at least claims to support it by not doing any conditional |
| 610 |
// compilation based on the target pointer width. So I guess I remain |
| 611 |
// consistent with that here. |
| 612 |
// |
| 613 |
// If you are here because you're on a 16-bit system and you were somehow using |
| 614 |
// the regex crate previously, please file an issue. Please be prepared to |
| 615 |
// provide some kind of reproduction or carve out some path to getting 16-bit |
| 616 |
// working in CI. (Via qemu?) |
| 617 |
#[cfg(not(any( |
| 618 |
target_pointer_width = "16", |
| 619 |
target_pointer_width = "32", |
| 620 |
target_pointer_width = "64" |
| 621 |
)))] |
| 622 |
compile_error!("not supported on non-{16,32,64}, please file an issue"); |
| 623 |
|
| 624 |
#[cfg(any(test, feature = "std"))] |
| 625 |
extern crate std; |
| 626 |
|
| 627 |
#[cfg(feature = "alloc")] |
| 628 |
extern crate alloc; |
| 629 |
|
| 630 |
#[cfg(doctest)] |
| 631 |
doc_comment::doctest!("../README.md"); |
| 632 |
|
| 633 |
#[doc(inline)] |
| 634 |
pub use crate::util::primitives::PatternID; |
| 635 |
pub use crate::util::search::*; |
| 636 |
|
| 637 |
#[macro_use] |
| 638 |
mod macros; |
| 639 |
|
| 640 |
#[cfg(any(feature = "dfa-search", feature = "dfa-onepass"))] |
| 641 |
pub mod dfa; |
| 642 |
#[cfg(feature = "hybrid")] |
| 643 |
pub mod hybrid; |
| 644 |
#[cfg(feature = "meta")] |
| 645 |
pub mod meta; |
| 646 |
#[cfg(feature = "nfa-thompson")] |
| 647 |
pub mod nfa; |
| 648 |
pub mod util; |