| 1 |
regex-automata |
| 2 |
============== |
| 3 |
This crate exposes a variety of regex engines used by the `regex` crate. |
| 4 |
It provides a vast, sprawling and "expert" level API to each regex engine. |
| 5 |
The regex engines provided by this crate focus heavily on finite automata |
| 6 |
implementations and specifically guarantee worst case `O(m * n)` time |
| 7 |
complexity for all searches. (Where `m ~ len(regex)` and `n ~ len(haystack)`.) |
| 8 |
|
| 9 |
[](https://github.com/rust-lang/regex/actions) |
| 10 |
[](https://crates.io/crates/regex-automata) |
| 11 |
|
| 12 |
|
| 13 |
### Documentation |
| 14 |
|
| 15 |
https://docs.rs/regex-automata |
| 16 |
|
| 17 |
|
| 18 |
### Example |
| 19 |
|
| 20 |
This example shows how to search for matches of multiple regexes, where each |
| 21 |
regex uses the same capture group names to parse different key-value formats. |
| 22 |
|
| 23 |
```rust |
| 24 |
use regex_automata::{meta::Regex, PatternID}; |
| 25 |
|
| 26 |
let re = Regex::new_many(&[ |
| 27 |
r#"(?m)^(?<key>[[:word:]]+)=(?<val>[[:word:]]+)$"#, |
| 28 |
r#"(?m)^(?<key>[[:word:]]+)="(?<val>[^"]+)"$"#, |
| 29 |
r#"(?m)^(?<key>[[:word:]]+)='(?<val>[^']+)'$"#, |
| 30 |
r#"(?m)^(?<key>[[:word:]]+):\s*(?<val>[[:word:]]+)$"#, |
| 31 |
]).unwrap(); |
| 32 |
let hay = r#" |
| 33 |
best_album="Blow Your Face Out" |
| 34 |
best_quote='"then as it was, then again it will be"' |
| 35 |
best_year=1973 |
| 36 |
best_simpsons_episode: HOMR |
| 37 |
"#; |
| 38 |
let mut kvs = vec![]; |
| 39 |
for caps in re.captures_iter(hay) { |
| 40 |
// N.B. One could use capture indices '1' and '2' here |
| 41 |
// as well. Capture indices are local to each pattern. |
| 42 |
// (Just like names are.) |
| 43 |
let key = &hay[caps.get_group_by_name("key").unwrap()]; |
| 44 |
let val = &hay[caps.get_group_by_name("val").unwrap()]; |
| 45 |
kvs.push((key, val)); |
| 46 |
} |
| 47 |
assert_eq!(kvs, vec![ |
| 48 |
("best_album", "Blow Your Face Out"), |
| 49 |
("best_quote", "\"then as it was, then again it will be\""), |
| 50 |
("best_year", "1973"), |
| 51 |
("best_simpsons_episode", "HOMR"), |
| 52 |
]); |
| 53 |
``` |
| 54 |
|
| 55 |
|
| 56 |
### Safety |
| 57 |
|
| 58 |
**I welcome audits of `unsafe` code.** |
| 59 |
|
| 60 |
This crate tries to be extremely conservative in its use of `unsafe`, but does |
| 61 |
use it in a few spots. In general, I am very open to removing uses of `unsafe` |
| 62 |
if it doesn't result in measurable performance regressions and doesn't result |
| 63 |
in significantly more complex code. |
| 64 |
|
| 65 |
Below is an outline of how `unsafe` is used in this crate. |
| 66 |
|
| 67 |
* `util::pool::Pool` makes use of `unsafe` to implement a fast path for |
| 68 |
accessing an element of the pool. The fast path applies to the first thread |
| 69 |
that uses the pool. In effect, the fast path is fast because it avoid a mutex |
| 70 |
lock. `unsafe` is also used in the no-std version of `Pool` to implement a spin |
| 71 |
lock for synchronization. |
| 72 |
* `util::lazy::Lazy` uses `unsafe` to implement a variant of |
| 73 |
`once_cell::sync::Lazy` that works in no-std environments. A no-std no-alloc |
| 74 |
implementation is also provided that requires use of `unsafe`. |
| 75 |
* The `dfa` module makes extensive use of `unsafe` to support zero-copy |
| 76 |
deserialization of DFAs. The high level problem is that you need to get from |
| 77 |
`&[u8]` to the internal representation of a DFA without doing any copies. |
| 78 |
This is required for support in no-std no-alloc environments. It also makes |
| 79 |
deserialization extremely cheap. |
| 80 |
* The `dfa` and `hybrid` modules use `unsafe` to explicitly elide bounds checks |
| 81 |
in the core search loops. This makes the codegen tighter and typically leads to |
| 82 |
consistent 5-10% performance improvements on some workloads. |
| 83 |
|
| 84 |
In general, the above reflect the only uses of `unsafe` throughout the entire |
| 85 |
`regex` crate. At present, there are no plans to meaningfully expand the use |
| 86 |
of `unsafe`. With that said, one thing folks have been asking for is cheap |
| 87 |
deserialization of a `regex::Regex`. My sense is that this feature will require |
| 88 |
a lot more `unsafe` in places to support zero-copy deserialization. It is |
| 89 |
unclear at this point whether this will be pursued. |
| 90 |
|
| 91 |
|
| 92 |
### Motivation |
| 93 |
|
| 94 |
I started out building this crate because I wanted to re-work the `regex` |
| 95 |
crate internals to make it more amenable to optimizations. It turns out that |
| 96 |
there are a lot of different ways to build regex engines and even more ways to |
| 97 |
compose them. Moreover, heuristic literal optimizations are often tricky to |
| 98 |
get correct, but the fruit they bear is attractive. All of these things were |
| 99 |
difficult to expand upon without risking the introduction of more bugs. So I |
| 100 |
decided to tear things down and start fresh. |
| 101 |
|
| 102 |
In the course of doing so, I ended up designing strong boundaries between each |
| 103 |
component so that each component could be reasoned and tested independently. |
| 104 |
This also made it somewhat natural to expose the components as a library unto |
| 105 |
itself. Namely, folks have been asking for more capabilities in the regex |
| 106 |
crate for a long time, but these capabilities usually come with additional API |
| 107 |
complexity that I didn't want to introduce in the `regex` crate proper. But |
| 108 |
exposing them in an "expert" level crate like `regex-automata` seemed quite |
| 109 |
fine. |
| 110 |
|
| 111 |
In the end, I do still somewhat consider this crate an experiment. It is |
| 112 |
unclear whether the strong boundaries between components will be an impediment |
| 113 |
to ongoing development or not. De-coupling tends to lead to slower development |
| 114 |
in my experience, and when you mix in the added cost of not introducing |
| 115 |
breaking changes all of the time, things can get quite complicated. But, I |
| 116 |
don't think anyone has ever release the internals of a regex engine as a |
| 117 |
library before. So it will be interesting to see how it plays out! |