Debian Codegraph @

.cargo/vendor/regex-automata/README.md

raw
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 [![Build status](https://github.com/rust-lang/regex/workflows/ci/badge.svg)](https://github.com/rust-lang/regex/actions)
10 [![Crates.io](https://img.shields.io/crates/v/regex-automata.svg)](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!