lib.rs - Codebrowser

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;
649