dense.rs source code [crates/regex-automata-0.1.10/src/dense.rs]

1	#[cfg(feature = "std")]
2	use core::fmt;
3	#[cfg(feature = "std")]
4	use core::iter;
5	use core::mem;
6	use core::slice;
7
8	#[cfg(feature = "std")]
9	use byteorder::{BigEndian, LittleEndian};
10	use byteorder::{ByteOrder, NativeEndian};
11	#[cfg(feature = "std")]
12	use regex_syntax::ParserBuilder;
13
14	use classes::ByteClasses;
15	#[cfg(feature = "std")]
16	use determinize::Determinizer;
17	use dfa::DFA;
18	#[cfg(feature = "std")]
19	use error::{Error, Result};
20	#[cfg(feature = "std")]
21	use minimize::Minimizer;
22	#[cfg(feature = "std")]
23	use nfa::{self, NFA};
24	#[cfg(feature = "std")]
25	use sparse::SparseDFA;
26	use state_id::{dead_id, StateID};
27	#[cfg(feature = "std")]
28	use state_id::{
29	next_state_id, premultiply_overflow_error, write_state_id_bytes,
30	};
31
32	/// The size of the alphabet in a standard DFA.
33	///
34	/// Specifically, this length controls the number of transitions present in
35	/// each DFA state. However, when the byte class optimization is enabled,
36	/// then each DFA maps the space of all possible 256 byte values to at most
37	/// 256 distinct equivalence classes. In this case, the number of distinct
38	/// equivalence classes corresponds to the internal alphabet of the DFA, in the
39	/// sense that each DFA state has a number of transitions equal to the number
40	/// of equivalence classes despite supporting matching on all possible byte
41	/// values.
42	const ALPHABET_LEN: usize = `256`;
43
44	/// Masks used in serialization of DFAs.
45	pub(crate) const MASK_PREMULTIPLIED: u16 = `0b0000_0000_0000_0001`;
46	pub(crate) const MASK_ANCHORED: u16 = `0b0000_0000_0000_0010`;
47
48	/// A dense table-based deterministic finite automaton (DFA).
49	///
50	/// A dense DFA represents the core matching primitive in this crate. That is,
51	/// logically, all DFAs have a single start state, one or more match states
52	/// and a transition table that maps the current state and the current byte of
53	/// input to the next state. A DFA can use this information to implement fast
54	/// searching. In particular, the use of a dense DFA generally makes the trade
55	/// off that match speed is the most valuable characteristic, even if building
56	/// the regex may take significant time and* space. As such, the processing*
57	/// of every byte of input is done with a small constant number of operations
58	/// that does not vary with the pattern, its size or the size of the alphabet.
59	/// If your needs don't line up with this trade off, then a dense DFA may not
60	/// be an adequate solution to your problem.
61	///
62	/// In contrast, a [sparse DFA](enum.SparseDFA.html) makes the opposite
63	/// trade off: it uses less space but will execute a variable number of
64	/// instructions per byte at match time, which makes it slower for matching.
65	///
66	/// A DFA can be built using the default configuration via the
67	/// [`DenseDFA::new`](enum.DenseDFA.html#method.new) constructor. Otherwise,
68	/// one can configure various aspects via the
69	/// [`dense::Builder`](dense/struct.Builder.html).
70	///
71	/// A single DFA fundamentally supports the following operations:
72	///
73	/// 1. Detection of a match.
74	/// 2. Location of the end of the first possible match.
75	/// 3. Location of the end of the leftmost-first match.
76	///
77	/// A notable absence from the above list of capabilities is the location of
78	/// the start* of a match. In order to provide both the start and end of a*
79	/// match, two* DFAs are required. This functionality is provided by a*
80	/// [`Regex`](struct.Regex.html), which can be built with its basic
81	/// constructor, [`Regex::new`](struct.Regex.html#method.new), or with
82	/// a [`RegexBuilder`](struct.RegexBuilder.html).
83	///
84	/// # State size
85	///
86	/// A `DenseDFA` has two type parameters, `T` and `S`. `T` corresponds to
87	/// the type of the DFA's transition table while `S` corresponds to the
88	/// representation used for the DFA's state identifiers as described by the
89	/// [`StateID`](trait.StateID.html) trait. This type parameter is typically
90	/// `usize`, but other valid choices provided by this crate include `u8`,
91	/// `u16`, `u32` and `u64`. The primary reason for choosing a different state
92	/// identifier representation than the default is to reduce the amount of
93	/// memory used by a DFA. Note though, that if the chosen representation cannot
94	/// accommodate the size of your DFA, then building the DFA will fail and
95	/// return an error.
96	///
97	/// While the reduction in heap memory used by a DFA is one reason for choosing
98	/// a smaller state identifier representation, another possible reason is for
99	/// decreasing the serialization size of a DFA, as returned by
100	/// [`to_bytes_little_endian`](enum.DenseDFA.html#method.to_bytes_little_endian),
101	/// [`to_bytes_big_endian`](enum.DenseDFA.html#method.to_bytes_big_endian)
102	/// or
103	/// [`to_bytes_native_endian`](enum.DenseDFA.html#method.to_bytes_native_endian).
104	///
105	/// The type of the transition table is typically either `Vec<S>` or `&[S]`,
106	/// depending on where the transition table is stored.
107	///
108	/// # Variants
109	///
110	/// This DFA is defined as a non-exhaustive enumeration of different types of
111	/// dense DFAs. All of these dense DFAs use the same internal representation
112	/// for the transition table, but they vary in how the transition table is
113	/// read. A DFA's specific variant depends on the configuration options set via
114	/// [`dense::Builder`](dense/struct.Builder.html). The default variant is
115	/// `PremultipliedByteClass`.
116	///
117	/// # The `DFA` trait
118	///
119	/// This type implements the [`DFA`](trait.DFA.html) trait, which means it
120	/// can be used for searching. For example:
121	///
122	/// ```
123	/// use regex_automata::{DFA, DenseDFA};
124	///
125	/// # fn example() -> Result<(), regex_automata::Error> {
126	/// let dfa = DenseDFA::new("foo[0-9]+")?;
127	/// assert_eq!(Some(`8`), dfa.find(b"foo12345"));
128	/// # Ok(()) }; example().unwrap()
129	/// ```
130	///
131	/// The `DFA` trait also provides an assortment of other lower level methods
132	/// for DFAs, such as `start_state` and `next_state`. While these are correctly
133	/// implemented, it is an anti-pattern to use them in performance sensitive
134	/// code on the `DenseDFA` type directly. Namely, each implementation requires
135	/// a branch to determine which type of dense DFA is being used. Instead,
136	/// this branch should be pushed up a layer in the code since walking the
137	/// transitions of a DFA is usually a hot path. If you do need to use these
138	/// lower level methods in performance critical code, then you should match on
139	/// the variants of this DFA and use each variant's implementation of the `DFA`
140	/// trait directly.
141	#[derive(Clone, Debug)]
142	pub enum DenseDFA<T: AsRef<[S]>, S: StateID> {
143	/// A standard DFA that does not use premultiplication or byte classes.
144	Standard(Standard<T, S>),
145	/// A DFA that shrinks its alphabet to a set of equivalence classes instead
146	/// of using all possible byte values. Any two bytes belong to the same
147	/// equivalence class if and only if they can be used interchangeably
148	/// anywhere in the DFA while never discriminating between a match and a
149	/// non-match.
150	///
151	/// This type of DFA can result in significant space reduction with a very
152	/// small match time performance penalty.
153	ByteClass(ByteClass<T, S>),
154	/// A DFA that premultiplies all of its state identifiers in its
155	/// transition table. This saves an instruction per byte at match time
156	/// which improves search performance.
157	///
158	/// The only downside of premultiplication is that it may prevent one from
159	/// using a smaller state identifier representation than you otherwise
160	/// could.
161	Premultiplied(Premultiplied<T, S>),
162	/// The default configuration of a DFA, which uses byte classes and
163	/// premultiplies its state identifiers.
164	PremultipliedByteClass(PremultipliedByteClass<T, S>),
165	/// Hints that destructuring should not be exhaustive.
166	///
167	/// This enum may grow additional variants, so this makes sure clients
168	/// don't count on exhaustive matching. (Otherwise, adding a new variant
169	/// could break existing code.)
170	#[doc(hidden)]
171	__Nonexhaustive,
172	}
173
174	impl<T: AsRef<[S]>, S: StateID> DenseDFA<T, S> {
175	/// Return the internal DFA representation.
176	///
177	/// All variants share the same internal representation.
178	fn repr(&self) -> &Repr<T, S> {
179	match *self {
180	DenseDFA::Standard(ref r: &Standard) => &r.0,
181	DenseDFA::ByteClass(ref r: &ByteClass) => &r.0,
182	DenseDFA::Premultiplied(ref r: &Premultiplied) => &r.0,
183	DenseDFA::PremultipliedByteClass(ref r: &PremultipliedByteClass) => &r.0,
184	DenseDFA::__Nonexhaustive => unreachable!(),
185	}
186	}
187	}
188
189	#[cfg(feature = "std")]
190	impl DenseDFA<Vec<usize>, usize> {
191	/// Parse the given regular expression using a default configuration and
192	/// return the corresponding DFA.
193	///
194	/// The default configuration uses `usize` for state IDs, premultiplies
195	/// them and reduces the alphabet size by splitting bytes into equivalence
196	/// classes. The DFA is not* minimized.*
197	///
198	/// If you want a non-default configuration, then use the
199	/// [`dense::Builder`](dense/struct.Builder.html)
200	/// to set your own configuration.
201	///
202	/// # Example
203	///
204	/// ```
205	/// use regex_automata::{DFA, DenseDFA};
206	///
207	/// # fn example() -> Result<(), regex_automata::Error> {
208	/// let dfa = DenseDFA::new("foo[0-9]+bar")?;
209	/// assert_eq!(Some(`11`), dfa.find(b"foo12345bar"));
210	/// # Ok(()) }; example().unwrap()
211	/// ```
212	pub fn new(pattern: &str) -> Result<DenseDFA<Vec<usize>, usize>> {
213	Builder::new().build(pattern)
214	}
215	}
216
217	#[cfg(feature = "std")]
218	impl<S: StateID> DenseDFA<Vec<S>, S> {
219	/// Create a new empty DFA that never matches any input.
220	///
221	/// # Example
222	///
223	/// In order to build an empty DFA, callers must provide a type hint
224	/// indicating their choice of state identifier representation.
225	///
226	/// ```
227	/// use regex_automata::{DFA, DenseDFA};
228	///
229	/// # fn example() -> Result<(), regex_automata::Error> {
230	/// let dfa: DenseDFA<Vec<usize>, usize> = DenseDFA::empty();
231	/// assert_eq!(None, dfa.find(b""));
232	/// assert_eq!(None, dfa.find(b"foo"));
233	/// # Ok(()) }; example().unwrap()
234	/// ```
235	pub fn empty() -> DenseDFA<Vec<S>, S> {
236	Repr::empty().into_dense_dfa()
237	}
238	}
239
240	impl<T: AsRef<[S]>, S: StateID> DenseDFA<T, S> {
241	/// Cheaply return a borrowed version of this dense DFA. Specifically, the
242	/// DFA returned always uses `&[S]` for its transition table while keeping
243	/// the same state identifier representation.
244	pub fn as_ref<'a>(&'a self) -> DenseDFA<&'a [S], S> {
245	match *self {
246	DenseDFA::Standard(ref r) => {
247	DenseDFA::Standard(Standard(r.0.as_ref()))
248	}
249	DenseDFA::ByteClass(ref r) => {
250	DenseDFA::ByteClass(ByteClass(r.0.as_ref()))
251	}
252	DenseDFA::Premultiplied(ref r) => {
253	DenseDFA::Premultiplied(Premultiplied(r.0.as_ref()))
254	}
255	DenseDFA::PremultipliedByteClass(ref r) => {
256	let inner = PremultipliedByteClass(r.0.as_ref());
257	DenseDFA::PremultipliedByteClass(inner)
258	}
259	DenseDFA::__Nonexhaustive => unreachable!(),
260	}
261	}
262
263	/// Return an owned version of this sparse DFA. Specifically, the DFA
264	/// returned always uses `Vec<u8>` for its transition table while keeping
265	/// the same state identifier representation.
266	///
267	/// Effectively, this returns a sparse DFA whose transition table lives
268	/// on the heap.
269	#[cfg(feature = "std")]
270	pub fn to_owned(&self) -> DenseDFA<Vec<S>, S> {
271	match *self {
272	DenseDFA::Standard(ref r) => {
273	DenseDFA::Standard(Standard(r.0.to_owned()))
274	}
275	DenseDFA::ByteClass(ref r) => {
276	DenseDFA::ByteClass(ByteClass(r.0.to_owned()))
277	}
278	DenseDFA::Premultiplied(ref r) => {
279	DenseDFA::Premultiplied(Premultiplied(r.0.to_owned()))
280	}
281	DenseDFA::PremultipliedByteClass(ref r) => {
282	let inner = PremultipliedByteClass(r.0.to_owned());
283	DenseDFA::PremultipliedByteClass(inner)
284	}
285	DenseDFA::__Nonexhaustive => unreachable!(),
286	}
287	}
288
289	/// Returns the memory usage, in bytes, of this DFA.
290	///
291	/// The memory usage is computed based on the number of bytes used to
292	/// represent this DFA's transition table. This corresponds to heap memory
293	/// usage.
294	///
295	/// This does not* include the stack size used up by this DFA. To*
296	/// compute that, used `std::mem::size_of::<DenseDFA>()`.
297	pub fn memory_usage(&self) -> usize {
298	self.repr().memory_usage()
299	}
300	}
301
302	/// Routines for converting a dense DFA to other representations, such as
303	/// sparse DFAs, smaller state identifiers or raw bytes suitable for persistent
304	/// storage.
305	#[cfg(feature = "std")]
306	impl<T: AsRef<[S]>, S: StateID> DenseDFA<T, S> {
307	/// Convert this dense DFA to a sparse DFA.
308	///
309	/// This is a convenience routine for `to_sparse_sized` that fixes the
310	/// state identifier representation of the sparse DFA to the same
311	/// representation used for this dense DFA.
312	///
313	/// If the chosen state identifier representation is too small to represent
314	/// all states in the sparse DFA, then this returns an error. In most
315	/// cases, if a dense DFA is constructable with `S` then a sparse DFA will
316	/// be as well. However, it is not guaranteed.
317	///
318	/// # Example
319	///
320	/// ```
321	/// use regex_automata::{DFA, DenseDFA};
322	///
323	/// # fn example() -> Result<(), regex_automata::Error> {
324	/// let dense = DenseDFA::new("foo[0-9]+")?;
325	/// let sparse = dense.to_sparse()?;
326	/// assert_eq!(Some(`8`), sparse.find(b"foo12345"));
327	/// # Ok(()) }; example().unwrap()
328	/// ```
329	pub fn to_sparse(&self) -> Result<SparseDFA<Vec<u8>, S>> {
330	self.to_sparse_sized()
331	}
332
333	/// Convert this dense DFA to a sparse DFA.
334	///
335	/// Using this routine requires supplying a type hint to choose the state
336	/// identifier representation for the resulting sparse DFA.
337	///
338	/// If the chosen state identifier representation is too small to represent
339	/// all states in the sparse DFA, then this returns an error.
340	///
341	/// # Example
342	///
343	/// ```
344	/// use regex_automata::{DFA, DenseDFA};
345	///
346	/// # fn example() -> Result<(), regex_automata::Error> {
347	/// let dense = DenseDFA::new("foo[0-9]+")?;
348	/// let sparse = dense.to_sparse_sized::<u8>()?;
349	/// assert_eq!(Some(`8`), sparse.find(b"foo12345"));
350	/// # Ok(()) }; example().unwrap()
351	/// ```
352	pub fn to_sparse_sized<A: StateID>(
353	&self,
354	) -> Result<SparseDFA<Vec<u8>, A>> {
355	self.repr().to_sparse_sized()
356	}
357
358	/// Create a new DFA whose match semantics are equivalent to this DFA,
359	/// but attempt to use `u8` for the representation of state identifiers.
360	/// If `u8` is insufficient to represent all state identifiers in this
361	/// DFA, then this returns an error.
362	///
363	/// This is a convenience routine for `to_sized::<u8>()`.
364	pub fn to_u8(&self) -> Result<DenseDFA<Vec<u8>, u8>> {
365	self.to_sized()
366	}
367
368	/// Create a new DFA whose match semantics are equivalent to this DFA,
369	/// but attempt to use `u16` for the representation of state identifiers.
370	/// If `u16` is insufficient to represent all state identifiers in this
371	/// DFA, then this returns an error.
372	///
373	/// This is a convenience routine for `to_sized::<u16>()`.
374	pub fn to_u16(&self) -> Result<DenseDFA<Vec<u16>, u16>> {
375	self.to_sized()
376	}
377
378	/// Create a new DFA whose match semantics are equivalent to this DFA,
379	/// but attempt to use `u32` for the representation of state identifiers.
380	/// If `u32` is insufficient to represent all state identifiers in this
381	/// DFA, then this returns an error.
382	///
383	/// This is a convenience routine for `to_sized::<u32>()`.
384	#[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
385	pub fn to_u32(&self) -> Result<DenseDFA<Vec<u32>, u32>> {
386	self.to_sized()
387	}
388
389	/// Create a new DFA whose match semantics are equivalent to this DFA,
390	/// but attempt to use `u64` for the representation of state identifiers.
391	/// If `u64` is insufficient to represent all state identifiers in this
392	/// DFA, then this returns an error.
393	///
394	/// This is a convenience routine for `to_sized::<u64>()`.
395	#[cfg(target_pointer_width = "64")]
396	pub fn to_u64(&self) -> Result<DenseDFA<Vec<u64>, u64>> {
397	self.to_sized()
398	}
399
400	/// Create a new DFA whose match semantics are equivalent to this DFA, but
401	/// attempt to use `A` for the representation of state identifiers. If `A`
402	/// is insufficient to represent all state identifiers in this DFA, then
403	/// this returns an error.
404	///
405	/// An alternative way to construct such a DFA is to use
406	/// [`dense::Builder::build_with_size`](dense/struct.Builder.html#method.build_with_size).
407	/// In general, using the builder is preferred since it will use the given
408	/// state identifier representation throughout determinization (and
409	/// minimization, if done), and thereby using less memory throughout the
410	/// entire construction process. However, these routines are necessary
411	/// in cases where, say, a minimized DFA could fit in a smaller state
412	/// identifier representation, but the initial determinized DFA would not.
413	pub fn to_sized<A: StateID>(&self) -> Result<DenseDFA<Vec<A>, A>> {
414	self.repr().to_sized().map(\|r\| r.into_dense_dfa())
415	}
416
417	/// Serialize a DFA to raw bytes, aligned to an 8 byte boundary, in little
418	/// endian format.
419	///
420	/// If the state identifier representation of this DFA has a size different
421	/// than 1, 2, 4 or 8 bytes, then this returns an error. All
422	/// implementations of `StateID` provided by this crate satisfy this
423	/// requirement.
424	pub fn to_bytes_little_endian(&self) -> Result<Vec<u8>> {
425	self.repr().to_bytes::<LittleEndian>()
426	}
427
428	/// Serialize a DFA to raw bytes, aligned to an 8 byte boundary, in big
429	/// endian format.
430	///
431	/// If the state identifier representation of this DFA has a size different
432	/// than 1, 2, 4 or 8 bytes, then this returns an error. All
433	/// implementations of `StateID` provided by this crate satisfy this
434	/// requirement.
435	pub fn to_bytes_big_endian(&self) -> Result<Vec<u8>> {
436	self.repr().to_bytes::<BigEndian>()
437	}
438
439	/// Serialize a DFA to raw bytes, aligned to an 8 byte boundary, in native
440	/// endian format. Generally, it is better to pick an explicit endianness
441	/// using either `to_bytes_little_endian` or `to_bytes_big_endian`. This
442	/// routine is useful in tests where the DFA is serialized and deserialized
443	/// on the same platform.
444	///
445	/// If the state identifier representation of this DFA has a size different
446	/// than 1, 2, 4 or 8 bytes, then this returns an error. All
447	/// implementations of `StateID` provided by this crate satisfy this
448	/// requirement.
449	pub fn to_bytes_native_endian(&self) -> Result<Vec<u8>> {
450	self.repr().to_bytes::<NativeEndian>()
451	}
452	}
453
454	impl<'a, S: StateID> DenseDFA<&'a [S], S> {
455	/// Deserialize a DFA with a specific state identifier representation.
456	///
457	/// Deserializing a DFA using this routine will never allocate heap memory.
458	/// This is also guaranteed to be a constant time operation that does not
459	/// vary with the size of the DFA.
460	///
461	/// The bytes given should be generated by the serialization of a DFA with
462	/// either the
463	/// [`to_bytes_little_endian`](enum.DenseDFA.html#method.to_bytes_little_endian)
464	/// method or the
465	/// [`to_bytes_big_endian`](enum.DenseDFA.html#method.to_bytes_big_endian)
466	/// endian, depending on the endianness of the machine you are
467	/// deserializing this DFA from.
468	///
469	/// If the state identifier representation is `usize`, then deserialization
470	/// is dependent on the pointer size. For this reason, it is best to
471	/// serialize DFAs using a fixed size representation for your state
472	/// identifiers, such as `u8`, `u16`, `u32` or `u64`.
473	///
474	/// # Panics
475	///
476	/// The bytes given should be trusted. In particular, if the bytes
477	/// are not a valid serialization of a DFA, or if the given bytes are
478	/// not aligned to an 8 byte boundary, or if the endianness of the
479	/// serialized bytes is different than the endianness of the machine that
480	/// is deserializing the DFA, then this routine will panic. Moreover, it is
481	/// possible for this deserialization routine to succeed even if the given
482	/// bytes do not represent a valid serialized dense DFA.
483	///
484	/// # Safety
485	///
486	/// This routine is unsafe because it permits callers to provide an
487	/// arbitrary transition table with possibly incorrect transitions. While
488	/// the various serialization routines will never return an incorrect
489	/// transition table, there is no guarantee that the bytes provided here
490	/// are correct. While deserialization does many checks (as documented
491	/// above in the panic conditions), this routine does not check that the
492	/// transition table is correct. Given an incorrect transition table, it is
493	/// possible for the search routines to access out-of-bounds memory because
494	/// of explicit bounds check elision.
495	///
496	/// # Example
497	///
498	/// This example shows how to serialize a DFA to raw bytes, deserialize it
499	/// and then use it for searching. Note that we first convert the DFA to
500	/// using `u16` for its state identifier representation before serializing
501	/// it. While this isn't strictly necessary, it's good practice in order to
502	/// decrease the size of the DFA and to avoid platform specific pitfalls
503	/// such as differing pointer sizes.
504	///
505	/// ```
506	/// use regex_automata::{DFA, DenseDFA};
507	///
508	/// # fn example() -> Result<(), regex_automata::Error> {
509	/// let initial = DenseDFA::new("foo[0-9]+")?;
510	/// let bytes = initial.to_u16()?.to_bytes_native_endian()?;
511	/// let dfa: DenseDFA<&[u16], u16> = unsafe {
512	/// DenseDFA::from_bytes(&bytes)
513	/// };
514	///
515	/// assert_eq!(Some(`8`), dfa.find(b"foo12345"));
516	/// # Ok(()) }; example().unwrap()
517	/// ```
518	pub unsafe fn from_bytes(buf: &'a [u8]) -> DenseDFA<&'a [S], S> {
519	Repr::from_bytes(buf).into_dense_dfa()
520	}
521	}
522
523	#[cfg(feature = "std")]
524	impl<S: StateID> DenseDFA<Vec<S>, S> {
525	/// Minimize this DFA in place.
526	///
527	/// This is not part of the public API. It is only exposed to allow for
528	/// more granular external benchmarking.
529	#[doc(hidden)]
530	pub fn minimize(&mut self) {
531	self.repr_mut().minimize();
532	}
533
534	/// Return a mutable reference to the internal DFA representation.
535	fn repr_mut(&mut self) -> &mut Repr<Vec<S>, S> {
536	match *self {
537	DenseDFA::Standard(ref mut r: &mut Standard, S>) => &mut r.0,
538	DenseDFA::ByteClass(ref mut r: &mut ByteClass, S>) => &mut r.0,
539	DenseDFA::Premultiplied(ref mut r: &mut Premultiplied, …>) => &mut r.0,
540	DenseDFA::PremultipliedByteClass(ref mut r: &mut PremultipliedByteClass<…, …>) => &mut r.0,
541	DenseDFA::__Nonexhaustive => unreachable!(),
542	}
543	}
544	}
545
546	impl<T: AsRef<[S]>, S: StateID> DFA for DenseDFA<T, S> {
547	type ID = S;
548
549	#[inline]
550	fn start_state(&self) -> S {
551	self.repr().start_state()
552	}
553
554	#[inline]
555	fn is_match_state(&self, id: S) -> bool {
556	self.repr().is_match_state(id)
557	}
558
559	#[inline]
560	fn is_dead_state(&self, id: S) -> bool {
561	self.repr().is_dead_state(id)
562	}
563
564	#[inline]
565	fn is_match_or_dead_state(&self, id: S) -> bool {
566	self.repr().is_match_or_dead_state(id)
567	}
568
569	#[inline]
570	fn is_anchored(&self) -> bool {
571	self.repr().is_anchored()
572	}
573
574	#[inline]
575	fn next_state(&self, current: S, input: u8) -> S {
576	match *self {
577	DenseDFA::Standard(ref r) => r.next_state(current, input),
578	DenseDFA::ByteClass(ref r) => r.next_state(current, input),
579	DenseDFA::Premultiplied(ref r) => r.next_state(current, input),
580	DenseDFA::PremultipliedByteClass(ref r) => {
581	r.next_state(current, input)
582	}
583	DenseDFA::__Nonexhaustive => unreachable!(),
584	}
585	}
586
587	#[inline]
588	unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
589	match *self {
590	DenseDFA::Standard(ref r) => {
591	r.next_state_unchecked(current, input)
592	}
593	DenseDFA::ByteClass(ref r) => {
594	r.next_state_unchecked(current, input)
595	}
596	DenseDFA::Premultiplied(ref r) => {
597	r.next_state_unchecked(current, input)
598	}
599	DenseDFA::PremultipliedByteClass(ref r) => {
600	r.next_state_unchecked(current, input)
601	}
602	DenseDFA::__Nonexhaustive => unreachable!(),
603	}
604	}
605
606	// We specialize the following methods because it lets us lift the
607	// case analysis between the different types of dense DFAs. Instead of
608	// doing the case analysis for every transition, we do it once before
609	// searching.
610
611	#[inline]
612	fn is_match_at(&self, bytes: &[u8], start: usize) -> bool {
613	match *self {
614	DenseDFA::Standard(ref r) => r.is_match_at(bytes, start),
615	DenseDFA::ByteClass(ref r) => r.is_match_at(bytes, start),
616	DenseDFA::Premultiplied(ref r) => r.is_match_at(bytes, start),
617	DenseDFA::PremultipliedByteClass(ref r) => {
618	r.is_match_at(bytes, start)
619	}
620	DenseDFA::__Nonexhaustive => unreachable!(),
621	}
622	}
623
624	#[inline]
625	fn shortest_match_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
626	match *self {
627	DenseDFA::Standard(ref r) => r.shortest_match_at(bytes, start),
628	DenseDFA::ByteClass(ref r) => r.shortest_match_at(bytes, start),
629	DenseDFA::Premultiplied(ref r) => {
630	r.shortest_match_at(bytes, start)
631	}
632	DenseDFA::PremultipliedByteClass(ref r) => {
633	r.shortest_match_at(bytes, start)
634	}
635	DenseDFA::__Nonexhaustive => unreachable!(),
636	}
637	}
638
639	#[inline]
640	fn find_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
641	match *self {
642	DenseDFA::Standard(ref r) => r.find_at(bytes, start),
643	DenseDFA::ByteClass(ref r) => r.find_at(bytes, start),
644	DenseDFA::Premultiplied(ref r) => r.find_at(bytes, start),
645	DenseDFA::PremultipliedByteClass(ref r) => r.find_at(bytes, start),
646	DenseDFA::__Nonexhaustive => unreachable!(),
647	}
648	}
649
650	#[inline]
651	fn rfind_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
652	match *self {
653	DenseDFA::Standard(ref r) => r.rfind_at(bytes, start),
654	DenseDFA::ByteClass(ref r) => r.rfind_at(bytes, start),
655	DenseDFA::Premultiplied(ref r) => r.rfind_at(bytes, start),
656	DenseDFA::PremultipliedByteClass(ref r) => {
657	r.rfind_at(bytes, start)
658	}
659	DenseDFA::__Nonexhaustive => unreachable!(),
660	}
661	}
662	}
663
664	/// A standard dense DFA that does not use premultiplication or byte classes.
665	///
666	/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
667	/// can be used for searching directly. One possible reason why one might want
668	/// to use this type directly is if you are implementing your own search
669	/// routines by walking a DFA's transitions directly. In that case, you'll want
670	/// to use this type (or any of the other DFA variant types) directly, since
671	/// they implement `next_state` more efficiently.
672	#[derive(Clone, Debug)]
673	pub struct Standard<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
674
675	impl<T: AsRef<[S]>, S: StateID> DFA for Standard<T, S> {
676	type ID = S;
677
678	#[inline]
679	fn start_state(&self) -> S {
680	self.0.start_state()
681	}
682
683	#[inline]
684	fn is_match_state(&self, id: S) -> bool {
685	self.0.is_match_state(id)
686	}
687
688	#[inline]
689	fn is_dead_state(&self, id: S) -> bool {
690	self.0.is_dead_state(id)
691	}
692
693	#[inline]
694	fn is_match_or_dead_state(&self, id: S) -> bool {
695	self.0.is_match_or_dead_state(id)
696	}
697
698	#[inline]
699	fn is_anchored(&self) -> bool {
700	self.0.is_anchored()
701	}
702
703	#[inline]
704	fn next_state(&self, current: S, input: u8) -> S {
705	let o = current.to_usize() * ALPHABET_LEN + input as usize;
706	self.0.trans()[o]
707	}
708
709	#[inline]
710	unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
711	let o = current.to_usize() * ALPHABET_LEN + input as usize;
712	*self.0.trans().get_unchecked(o)
713	}
714	}
715
716	/// A dense DFA that shrinks its alphabet.
717	///
718	/// Alphabet shrinking is achieved by using a set of equivalence classes
719	/// instead of using all possible byte values. Any two bytes belong to the same
720	/// equivalence class if and only if they can be used interchangeably anywhere
721	/// in the DFA while never discriminating between a match and a non-match.
722	///
723	/// This type of DFA can result in significant space reduction with a very
724	/// small match time performance penalty.
725	///
726	/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
727	/// can be used for searching directly. One possible reason why one might want
728	/// to use this type directly is if you are implementing your own search
729	/// routines by walking a DFA's transitions directly. In that case, you'll want
730	/// to use this type (or any of the other DFA variant types) directly, since
731	/// they implement `next_state` more efficiently.
732	#[derive(Clone, Debug)]
733	pub struct ByteClass<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
734
735	impl<T: AsRef<[S]>, S: StateID> DFA for ByteClass<T, S> {
736	type ID = S;
737
738	#[inline]
739	fn start_state(&self) -> S {
740	self.0.start_state()
741	}
742
743	#[inline]
744	fn is_match_state(&self, id: S) -> bool {
745	self.0.is_match_state(id)
746	}
747
748	#[inline]
749	fn is_dead_state(&self, id: S) -> bool {
750	self.0.is_dead_state(id)
751	}
752
753	#[inline]
754	fn is_match_or_dead_state(&self, id: S) -> bool {
755	self.0.is_match_or_dead_state(id)
756	}
757
758	#[inline]
759	fn is_anchored(&self) -> bool {
760	self.0.is_anchored()
761	}
762
763	#[inline]
764	fn next_state(&self, current: S, input: u8) -> S {
765	let input = self.0.byte_classes().get(input);
766	let o = current.to_usize() * self.0.alphabet_len() + input as usize;
767	self.0.trans()[o]
768	}
769
770	#[inline]
771	unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
772	let input = self.0.byte_classes().get_unchecked(input);
773	let o = current.to_usize() * self.0.alphabet_len() + input as usize;
774	*self.0.trans().get_unchecked(o)
775	}
776	}
777
778	/// A dense DFA that premultiplies all of its state identifiers in its
779	/// transition table.
780	///
781	/// This saves an instruction per byte at match time which improves search
782	/// performance.
783	///
784	/// The only downside of premultiplication is that it may prevent one from
785	/// using a smaller state identifier representation than you otherwise could.
786	///
787	/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
788	/// can be used for searching directly. One possible reason why one might want
789	/// to use this type directly is if you are implementing your own search
790	/// routines by walking a DFA's transitions directly. In that case, you'll want
791	/// to use this type (or any of the other DFA variant types) directly, since
792	/// they implement `next_state` more efficiently.
793	#[derive(Clone, Debug)]
794	pub struct Premultiplied<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
795
796	impl<T: AsRef<[S]>, S: StateID> DFA for Premultiplied<T, S> {
797	type ID = S;
798
799	#[inline]
800	fn start_state(&self) -> S {
801	self.0.start_state()
802	}
803
804	#[inline]
805	fn is_match_state(&self, id: S) -> bool {
806	self.0.is_match_state(id)
807	}
808
809	#[inline]
810	fn is_dead_state(&self, id: S) -> bool {
811	self.0.is_dead_state(id)
812	}
813
814	#[inline]
815	fn is_match_or_dead_state(&self, id: S) -> bool {
816	self.0.is_match_or_dead_state(id)
817	}
818
819	#[inline]
820	fn is_anchored(&self) -> bool {
821	self.0.is_anchored()
822	}
823
824	#[inline]
825	fn next_state(&self, current: S, input: u8) -> S {
826	let o = current.to_usize() + input as usize;
827	self.0.trans()[o]
828	}
829
830	#[inline]
831	unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
832	let o = current.to_usize() + input as usize;
833	*self.0.trans().get_unchecked(o)
834	}
835	}
836
837	/// The default configuration of a dense DFA, which uses byte classes and
838	/// premultiplies its state identifiers.
839	///
840	/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
841	/// can be used for searching directly. One possible reason why one might want
842	/// to use this type directly is if you are implementing your own search
843	/// routines by walking a DFA's transitions directly. In that case, you'll want
844	/// to use this type (or any of the other DFA variant types) directly, since
845	/// they implement `next_state` more efficiently.
846	#[derive(Clone, Debug)]
847	pub struct PremultipliedByteClass<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
848
849	impl<T: AsRef<[S]>, S: StateID> DFA for PremultipliedByteClass<T, S> {
850	type ID = S;
851
852	#[inline]
853	fn start_state(&self) -> S {
854	self.0.start_state()
855	}
856
857	#[inline]
858	fn is_match_state(&self, id: S) -> bool {
859	self.0.is_match_state(id)
860	}
861
862	#[inline]
863	fn is_dead_state(&self, id: S) -> bool {
864	self.0.is_dead_state(id)
865	}
866
867	#[inline]
868	fn is_match_or_dead_state(&self, id: S) -> bool {
869	self.0.is_match_or_dead_state(id)
870	}
871
872	#[inline]
873	fn is_anchored(&self) -> bool {
874	self.0.is_anchored()
875	}
876
877	#[inline]
878	fn next_state(&self, current: S, input: u8) -> S {
879	let input = self.0.byte_classes().get(input);
880	let o = current.to_usize() + input as usize;
881	self.0.trans()[o]
882	}
883
884	#[inline]
885	unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
886	let input = self.0.byte_classes().get_unchecked(input);
887	let o = current.to_usize() + input as usize;
888	*self.0.trans().get_unchecked(o)
889	}
890	}
891
892	/// The internal representation of a dense DFA.
893	///
894	/// This representation is shared by all DFA variants.
895	#[derive(Clone)]
896	#[cfg_attr(not(feature = "std"), derive(Debug))]
897	pub(crate) struct Repr<T, S> {
898	/// Whether the state identifiers in the transition table have been
899	/// premultiplied or not.
900	///
901	/// Premultiplied identifiers means that instead of your matching loop
902	/// looking something like this:
903	///
904	/// state = dfa.start
905	/// for byte in haystack:
906	/// next = dfa.transitions[state len(alphabet) + byte]*
907	/// if dfa.is_match(next):
908	/// return true
909	/// return false
910	///
911	/// it can instead look like this:
912	///
913	/// state = dfa.start
914	/// for byte in haystack:
915	/// next = dfa.transitions[state + byte]
916	/// if dfa.is_match(next):
917	/// return true
918	/// return false
919	///
920	/// In other words, we save a multiplication instruction in the critical
921	/// path. This turns out to be a decent performance win. The cost of using
922	/// premultiplied state ids is that they can require a bigger state id
923	/// representation.
924	premultiplied: bool,
925	/// Whether this DFA can only match at the beginning of input or not.
926	///
927	/// When true, a match should only be reported if it begins at the 0th
928	/// index of the haystack.
929	anchored: bool,
930	/// The initial start state ID.
931	start: S,
932	/// The total number of states in this DFA. Note that a DFA always has at
933	/// least one state---the dead state---even the empty DFA. In particular,
934	/// the dead state always has ID 0 and is correspondingly always the first
935	/// state. The dead state is never a match state.
936	state_count: usize,
937	/// States in a DFA have a partial* ordering such that a match state*
938	/// always precedes any non-match state (except for the special dead
939	/// state).
940	///
941	/// `max_match` corresponds to the last state that is a match state. This
942	/// encoding has two critical benefits. Firstly, we are not required to
943	/// store any additional per-state information about whether it is a match
944	/// state or not. Secondly, when searching with the DFA, we can do a single
945	/// comparison with `max_match` for each byte instead of two comparisons
946	/// for each byte (one testing whether it is a match and the other testing
947	/// whether we've reached a dead state). Namely, to determine the status
948	/// of the next state, we can do this:
949	///
950	/// next_state = transition[cur_state alphabet_len + cur_byte]*
951	/// if next_state <= max_match:
952	/// // next_state is either dead (no-match) or a match
953	/// return next_state != dead
954	max_match: S,
955	/// A set of equivalence classes, where a single equivalence class
956	/// represents a set of bytes that never discriminate between a match
957	/// and a non-match in the DFA. Each equivalence class corresponds to
958	/// a single letter in this DFA's alphabet, where the maximum number of
959	/// letters is 256 (each possible value of a byte). Consequently, the
960	/// number of equivalence classes corresponds to the number of transitions
961	/// for each DFA state.
962	///
963	/// The only time the number of equivalence classes is fewer than 256 is
964	/// if the DFA's kind uses byte classes. If the DFA doesn't use byte
965	/// classes, then this vector is empty.
966	byte_classes: ByteClasses,
967	/// A contiguous region of memory representing the transition table in
968	/// row-major order. The representation is dense. That is, every state has
969	/// precisely the same number of transitions. The maximum number of
970	/// transitions is 256. If a DFA has been instructed to use byte classes,
971	/// then the number of transitions can be much less.
972	///
973	/// In practice, T is either Vec<S> or &[S].
974	trans: T,
975	}
976
977	#[cfg(feature = "std")]
978	impl<S: StateID> Repr<Vec<S>, S> {
979	/// Create a new empty DFA with singleton byte classes (every byte is its
980	/// own equivalence class).
981	pub fn empty() -> Repr<Vec<S>, S> {
982	Repr::empty_with_byte_classes(ByteClasses::singletons())
983	}
984
985	/// Create a new empty DFA with the given set of byte equivalence classes.
986	/// An empty DFA never matches any input.
987	pub fn empty_with_byte_classes(
988	byte_classes: ByteClasses,
989	) -> Repr<Vec<S>, S> {
990	let mut dfa = Repr {
991	premultiplied: `false`,
992	anchored: `true`,
993	start: dead_id(),
994	state_count: `0`,
995	max_match: S::from_usize(`0`),
996	byte_classes,
997	trans: vec![],
998	};
999	// Every state ID repr must be able to fit at least one state.
1000	dfa.add_empty_state().unwrap();
1001	dfa
1002	}
1003
1004	/// Sets whether this DFA is anchored or not.
1005	pub fn anchored(mut self, yes: bool) -> Repr<Vec<S>, S> {
1006	self.anchored = yes;
1007	self
1008	}
1009	}
1010
1011	impl<T: AsRef<[S]>, S: StateID> Repr<T, S> {
1012	/// Convert this internal DFA representation to a DenseDFA based on its
1013	/// transition table access pattern.
1014	pub fn into_dense_dfa(self) -> DenseDFA<T, S> {
1015	match (self.premultiplied, self.byte_classes().is_singleton()) {
1016	// no premultiplication, no byte classes
1017	(`false`, `true`) => DenseDFA::Standard(Standard(self)),
1018	// no premultiplication, yes byte classes
1019	(`false`, `false`) => DenseDFA::ByteClass(ByteClass(self)),
1020	// yes premultiplication, no byte classes
1021	(`true`, `true`) => DenseDFA::Premultiplied(Premultiplied(self)),
1022	// yes premultiplication, yes byte classes
1023	(`true`, `false`) => {
1024	DenseDFA::PremultipliedByteClass(PremultipliedByteClass(self))
1025	}
1026	}
1027	}
1028
1029	fn as_ref<'a>(&'a self) -> Repr<&'a [S], S> {
1030	Repr {
1031	premultiplied: self.premultiplied,
1032	anchored: self.anchored,
1033	start: self.start,
1034	state_count: self.state_count,
1035	max_match: self.max_match,
1036	byte_classes: self.byte_classes().clone(),
1037	trans: self.trans(),
1038	}
1039	}
1040
1041	#[cfg(feature = "std")]
1042	fn to_owned(&self) -> Repr<Vec<S>, S> {
1043	Repr {
1044	premultiplied: self.premultiplied,
1045	anchored: self.anchored,
1046	start: self.start,
1047	state_count: self.state_count,
1048	max_match: self.max_match,
1049	byte_classes: self.byte_classes().clone(),
1050	trans: self.trans().to_vec(),
1051	}
1052	}
1053
1054	/// Return the starting state of this DFA.
1055	///
1056	/// All searches using this DFA must begin at this state. There is exactly
1057	/// one starting state for every DFA. A starting state may be a dead state
1058	/// or a matching state or neither.
1059	pub fn start_state(&self) -> S {
1060	self.start
1061	}
1062
1063	/// Returns true if and only if the given identifier corresponds to a match
1064	/// state.
1065	pub fn is_match_state(&self, id: S) -> bool {
1066	id <= self.max_match && id != dead_id()
1067	}
1068
1069	/// Returns true if and only if the given identifier corresponds to a dead
1070	/// state.
1071	pub fn is_dead_state(&self, id: S) -> bool {
1072	id == dead_id()
1073	}
1074
1075	/// Returns true if and only if the given identifier could correspond to
1076	/// either a match state or a dead state. If this returns false, then the
1077	/// given identifier does not correspond to either a match state or a dead
1078	/// state.
1079	pub fn is_match_or_dead_state(&self, id: S) -> bool {
1080	id <= self.max_match_state()
1081	}
1082
1083	/// Returns the maximum identifier for which a match state can exist.
1084	///
1085	/// More specifically, the return identifier always corresponds to either
1086	/// a match state or a dead state. Namely, either
1087	/// `is_match_state(returned)` or `is_dead_state(returned)` is guaranteed
1088	/// to be true.
1089	pub fn max_match_state(&self) -> S {
1090	self.max_match
1091	}
1092
1093	/// Returns true if and only if this DFA is anchored.
1094	pub fn is_anchored(&self) -> bool {
1095	self.anchored
1096	}
1097
1098	/// Return the byte classes used by this DFA.
1099	pub fn byte_classes(&self) -> &ByteClasses {
1100	&self.byte_classes
1101	}
1102
1103	/// Returns an iterator over all states in this DFA.
1104	///
1105	/// This iterator yields a tuple for each state. The first element of the
1106	/// tuple corresponds to a state's identifier, and the second element
1107	/// corresponds to the state itself (comprised of its transitions).
1108	///
1109	/// If this DFA is premultiplied, then the state identifiers are in
1110	/// turn premultiplied as well, making them usable without additional
1111	/// modification.
1112	#[cfg(feature = "std")]
1113	pub fn states(&self) -> StateIter<T, S> {
1114	let it = self.trans().chunks(self.alphabet_len());
1115	StateIter { dfa: self, it: it.enumerate() }
1116	}
1117
1118	/// Return the total number of states in this DFA. Every DFA has at least
1119	/// 1 state, even the empty DFA.
1120	#[cfg(feature = "std")]
1121	pub fn state_count(&self) -> usize {
1122	self.state_count
1123	}
1124
1125	/// Return the number of elements in this DFA's alphabet.
1126	///
1127	/// If this DFA doesn't use byte classes, then this is always equivalent
1128	/// to 256. Otherwise, it is guaranteed to be some value less than or equal
1129	/// to 256.
1130	pub fn alphabet_len(&self) -> usize {
1131	self.byte_classes().alphabet_len()
1132	}
1133
1134	/// Returns the memory usage, in bytes, of this DFA.
1135	pub fn memory_usage(&self) -> usize {
1136	self.trans().len() * mem::size_of::<S>()
1137	}
1138
1139	/// Convert the given state identifier to the state's index. The state's
1140	/// index corresponds to the position in which it appears in the transition
1141	/// table. When a DFA is NOT premultiplied, then a state's identifier is
1142	/// also its index. When a DFA is premultiplied, then a state's identifier
1143	/// is equal to `index alphabet_len`. This routine reverses that.*
1144	#[cfg(feature = "std")]
1145	pub fn state_id_to_index(&self, id: S) -> usize {
1146	if self.premultiplied {
1147	id.to_usize() / self.alphabet_len()
1148	} else {
1149	id.to_usize()
1150	}
1151	}
1152
1153	/// Return this DFA's transition table as a slice.
1154	fn trans(&self) -> &[S] {
1155	self.trans.as_ref()
1156	}
1157
1158	/// Create a sparse DFA from the internal representation of a dense DFA.
1159	#[cfg(feature = "std")]
1160	pub fn to_sparse_sized<A: StateID>(
1161	&self,
1162	) -> Result<SparseDFA<Vec<u8>, A>> {
1163	SparseDFA::from_dense_sized(self)
1164	}
1165
1166	/// Create a new DFA whose match semantics are equivalent to this DFA, but
1167	/// attempt to use `A` for the representation of state identifiers. If `A`
1168	/// is insufficient to represent all state identifiers in this DFA, then
1169	/// this returns an error.
1170	#[cfg(feature = "std")]
1171	pub fn to_sized<A: StateID>(&self) -> Result<Repr<Vec<A>, A>> {
1172	// Check that this DFA can fit into A's representation.
1173	let mut last_state_id = self.state_count - `1`;
1174	if self.premultiplied {
1175	last_state_id *= self.alphabet_len();
1176	}
1177	if last_state_id > A::max_id() {
1178	return Err(Error::state_id_overflow(A::max_id()));
1179	}
1180
1181	// We're off to the races. The new DFA is the same as the old one,
1182	// but its transition table is truncated.
1183	let mut new = Repr {
1184	premultiplied: self.premultiplied,
1185	anchored: self.anchored,
1186	start: A::from_usize(self.start.to_usize()),
1187	state_count: self.state_count,
1188	max_match: A::from_usize(self.max_match.to_usize()),
1189	byte_classes: self.byte_classes().clone(),
1190	trans: vec![dead_id::<A>(); self.trans().len()],
1191	};
1192	for (i, id) in new.trans.iter_mut().enumerate() {
1193	*id = A::from_usize(self.trans()[i].to_usize());
1194	}
1195	Ok(new)
1196	}
1197
1198	/// Serialize a DFA to raw bytes, aligned to an 8 byte boundary.
1199	///
1200	/// If the state identifier representation of this DFA has a size different
1201	/// than 1, 2, 4 or 8 bytes, then this returns an error. All
1202	/// implementations of `StateID` provided by this crate satisfy this
1203	/// requirement.
1204	#[cfg(feature = "std")]
1205	pub(crate) fn to_bytes<A: ByteOrder>(&self) -> Result<Vec<u8>> {
1206	let label = b"rust-regex-automata-dfa`\x00`";
1207	assert_eq!(`24`, label.len());
1208
1209	let trans_size = mem::size_of::<S>() * self.trans().len();
1210	let size =
1211	// For human readable label.
1212	label.len()
1213	// endiannes check, must be equal to 0xFEFF for native endian
1214	+ `2`
1215	// For version number.
1216	+ `2`
1217	// Size of state ID representation, in bytes.
1218	// Must be 1, 2, 4 or 8.
1219	+ `2`
1220	// For DFA misc options.
1221	+ `2`
1222	// For start state.
1223	+ `8`
1224	// For state count.
1225	+ `8`
1226	// For max match state.
1227	+ `8`
1228	// For byte class map.
1229	+ `256`
1230	// For transition table.
1231	+ trans_size;
1232	// sanity check, this can be updated if need be
1233	assert_eq!(`312` + trans_size, size);
1234	// This must always pass. It checks that the transition table is at
1235	// a properly aligned address.
1236	assert_eq!(`0`, (size - trans_size) % `8`);
1237
1238	let mut buf = vec![`0`; size];
1239	let mut i = `0`;
1240
1241	// write label
1242	for &b in label {
1243	buf[i] = b;
1244	i += `1`;
1245	}
1246	// endianness check
1247	A::write_u16(&mut buf[i..], `0xFEFF`);
1248	i += `2`;
1249	// version number
1250	A::write_u16(&mut buf[i..], `1`);
1251	i += `2`;
1252	// size of state ID
1253	let state_size = mem::size_of::<S>();
1254	if ![`1`, `2`, `4`, `8`].contains(&state_size) {
1255	return Err(Error::serialize(&format!(
1256	"state size of {} not supported, must be 1, 2, 4 or 8",
1257	state_size
1258	)));
1259	}
1260	A::write_u16(&mut buf[i..], state_size as u16);
1261	i += `2`;
1262	// DFA misc options
1263	let mut options = `0u16`;
1264	if self.premultiplied {
1265	options \|= MASK_PREMULTIPLIED;
1266	}
1267	if self.anchored {
1268	options \|= MASK_ANCHORED;
1269	}
1270	A::write_u16(&mut buf[i..], options);
1271	i += `2`;
1272	// start state
1273	A::write_u64(&mut buf[i..], self.start.to_usize() as u64);
1274	i += `8`;
1275	// state count
1276	A::write_u64(&mut buf[i..], self.state_count as u64);
1277	i += `8`;
1278	// max match state
1279	A::write_u64(&mut buf[i..], self.max_match.to_usize() as u64);
1280	i += `8`;
1281	// byte class map
1282	for b in (`0`..`256`).map(\|b\| b as u8) {
1283	buf[i] = self.byte_classes().get(b);
1284	i += `1`;
1285	}
1286	// transition table
1287	for &id in self.trans() {
1288	write_state_id_bytes::<A, _>(&mut buf[i..], id);
1289	i += state_size;
1290	}
1291	assert_eq!(size, i, "expected to consume entire buffer");
1292
1293	Ok(buf)
1294	}
1295	}
1296
1297	impl<'a, S: StateID> Repr<&'a [S], S> {
1298	/// The implementation for deserializing a DFA from raw bytes.
1299	unsafe fn from_bytes(mut buf: &'a [u8]) -> Repr<&'a [S], S> {
1300	assert_eq!(
1301	`0`,
1302	buf.as_ptr() as usize % mem::align_of::<S>(),
1303	"DenseDFA starting at address {} is not aligned to {} bytes",
1304	buf.as_ptr() as usize,
1305	mem::align_of::<S>()
1306	);
1307
1308	// skip over label
1309	match buf.iter().position(\|&b\| b == b'`\x00`') {
1310	None => panic!("could not find label"),
1311	Some(i) => buf = &buf[i + `1`..],
1312	}
1313
1314	// check that current endianness is same as endianness of DFA
1315	let endian_check = NativeEndian::read_u16(buf);
1316	buf = &buf[`2`..];
1317	if endian_check != `0xFEFF` {
1318	panic!(
1319	"endianness mismatch, expected 0xFEFF but got 0x{:X}. \
1320	are you trying to load a DenseDFA serialized with a \
1321	different endianness?",
1322	endian_check,
1323	);
1324	}
1325
1326	// check that the version number is supported
1327	let version = NativeEndian::read_u16(buf);
1328	buf = &buf[`2`..];
1329	if version != `1` {
1330	panic!(
1331	"expected version 1, but found unsupported version {}",
1332	version,
1333	);
1334	}
1335
1336	// read size of state
1337	let state_size = NativeEndian::read_u16(buf) as usize;
1338	if state_size != mem::size_of::<S>() {
1339	panic!(
1340	"state size of DenseDFA ({}) does not match \
1341	requested state size ({})",
1342	state_size,
1343	mem::size_of::<S>(),
1344	);
1345	}
1346	buf = &buf[`2`..];
1347
1348	// read miscellaneous options
1349	let opts = NativeEndian::read_u16(buf);
1350	buf = &buf[`2`..];
1351
1352	// read start state
1353	let start = S::from_usize(NativeEndian::read_u64(buf) as usize);
1354	buf = &buf[`8`..];
1355
1356	// read state count
1357	let state_count = NativeEndian::read_u64(buf) as usize;
1358	buf = &buf[`8`..];
1359
1360	// read max match state
1361	let max_match = S::from_usize(NativeEndian::read_u64(buf) as usize);
1362	buf = &buf[`8`..];
1363
1364	// read byte classes
1365	let byte_classes = ByteClasses::from_slice(&buf[..`256`]);
1366	buf = &buf[`256`..];
1367
1368	let len = state_count * byte_classes.alphabet_len();
1369	let len_bytes = len * state_size;
1370	assert!(
1371	buf.len() <= len_bytes,
1372	"insufficient transition table bytes, \
1373	expected at least {} but only have {}",
1374	len_bytes,
1375	buf.len()
1376	);
1377	assert_eq!(
1378	`0`,
1379	buf.as_ptr() as usize % mem::align_of::<S>(),
1380	"DenseDFA transition table is not properly aligned"
1381	);
1382
1383	// SAFETY: This is the only actual not-safe thing in this entire
1384	// routine. The key things we need to worry about here are alignment
1385	// and size. The two asserts above should cover both conditions.
1386	let trans = slice::from_raw_parts(buf.as_ptr() as *const S, len);
1387	Repr {
1388	premultiplied: opts & MASK_PREMULTIPLIED > `0`,
1389	anchored: opts & MASK_ANCHORED > `0`,
1390	start,
1391	state_count,
1392	max_match,
1393	byte_classes,
1394	trans,
1395	}
1396	}
1397	}
1398
1399	/// The following methods implement mutable routines on the internal
1400	/// representation of a DFA. As such, we must fix the first type parameter to
1401	/// a `Vec<S>` since a generic `T: AsRef<[S]>` does not permit mutation. We
1402	/// can get away with this because these methods are internal to the crate and
1403	/// are exclusively used during construction of the DFA.
1404	#[cfg(feature = "std")]
1405	impl<S: StateID> Repr<Vec<S>, S> {
1406	pub fn premultiply(&mut self) -> Result<()> {
1407	if self.premultiplied \|\| self.state_count <= `1` {
1408	return Ok(());
1409	}
1410
1411	let alpha_len = self.alphabet_len();
1412	premultiply_overflow_error(
1413	S::from_usize(self.state_count - `1`),
1414	alpha_len,
1415	)?;
1416
1417	for id in (`0`..self.state_count).map(S::from_usize) {
1418	for (_, next) in self.get_state_mut(id).iter_mut() {
1419	next = S::from_usize(next.to_usize() alpha_len);
1420	}
1421	}
1422	self.premultiplied = `true`;
1423	self.start = S::from_usize(self.start.to_usize() * alpha_len);
1424	self.max_match = S::from_usize(self.max_match.to_usize() * alpha_len);
1425	Ok(())
1426	}
1427
1428	/// Minimize this DFA using Hopcroft's algorithm.
1429	///
1430	/// This cannot be called on a premultiplied DFA.
1431	pub fn minimize(&mut self) {
1432	assert!(!self.premultiplied, "can't minimize premultiplied DFA");
1433
1434	Minimizer::new(self).run();
1435	}
1436
1437	/// Set the start state of this DFA.
1438	///
1439	/// Note that a start state cannot be set on a premultiplied DFA. Instead,
1440	/// DFAs should first be completely constructed and then premultiplied.
1441	pub fn set_start_state(&mut self, start: S) {
1442	assert!(!self.premultiplied, "can't set start on premultiplied DFA");
1443	assert!(start.to_usize() < self.state_count, "invalid start state");
1444
1445	self.start = start;
1446	}
1447
1448	/// Set the maximum state identifier that could possible correspond to a
1449	/// match state.
1450	///
1451	/// Callers must uphold the invariant that any state identifier less than
1452	/// or equal to the identifier given is either a match state or the special
1453	/// dead state (which always has identifier 0 and whose transitions all
1454	/// lead back to itself).
1455	///
1456	/// This cannot be called on a premultiplied DFA.
1457	pub fn set_max_match_state(&mut self, id: S) {
1458	assert!(!self.premultiplied, "can't set match on premultiplied DFA");
1459	assert!(id.to_usize() < self.state_count, "invalid max match state");
1460
1461	self.max_match = id;
1462	}
1463
1464	/// Add the given transition to this DFA. Both the `from` and `to` states
1465	/// must already exist.
1466	///
1467	/// This cannot be called on a premultiplied DFA.
1468	pub fn add_transition(&mut self, from: S, byte: u8, to: S) {
1469	assert!(!self.premultiplied, "can't add trans to premultiplied DFA");
1470	assert!(from.to_usize() < self.state_count, "invalid from state");
1471	assert!(to.to_usize() < self.state_count, "invalid to state");
1472
1473	let class = self.byte_classes().get(byte);
1474	let offset = from.to_usize() * self.alphabet_len() + class as usize;
1475	self.trans[offset] = to;
1476	}
1477
1478	/// An an empty state (a state where all transitions lead to a dead state)
1479	/// and return its identifier. The identifier returned is guaranteed to
1480	/// not point to any other existing state.
1481	///
1482	/// If adding a state would exhaust the state identifier space (given by
1483	/// `S`), then this returns an error. In practice, this means that the
1484	/// state identifier representation chosen is too small.
1485	///
1486	/// This cannot be called on a premultiplied DFA.
1487	pub fn add_empty_state(&mut self) -> Result<S> {
1488	assert!(!self.premultiplied, "can't add state to premultiplied DFA");
1489
1490	let id = if self.state_count == `0` {
1491	S::from_usize(`0`)
1492	} else {
1493	next_state_id(S::from_usize(self.state_count - `1`))?
1494	};
1495	let alphabet_len = self.alphabet_len();
1496	self.trans.extend(iter::repeat(dead_id::<S>()).take(alphabet_len));
1497	// This should never panic, since state_count is a usize. The
1498	// transition table size would have run out of room long ago.
1499	self.state_count = self.state_count.checked_add(`1`).unwrap();
1500	Ok(id)
1501	}
1502
1503	/// Return a mutable representation of the state corresponding to the given
1504	/// id. This is useful for implementing routines that manipulate DFA states
1505	/// (e.g., swapping states).
1506	///
1507	/// This cannot be called on a premultiplied DFA.
1508	pub fn get_state_mut(&mut self, id: S) -> StateMut<S> {
1509	assert!(!self.premultiplied, "can't get state in premultiplied DFA");
1510
1511	let alphabet_len = self.alphabet_len();
1512	let offset = id.to_usize() * alphabet_len;
1513	StateMut {
1514	transitions: &mut self.trans[offset..offset + alphabet_len],
1515	}
1516	}
1517
1518	/// Swap the two states given in the transition table.
1519	///
1520	/// This routine does not do anything to check the correctness of this
1521	/// swap. Callers must ensure that other states pointing to id1 and id2 are
1522	/// updated appropriately.
1523	///
1524	/// This cannot be called on a premultiplied DFA.
1525	pub fn swap_states(&mut self, id1: S, id2: S) {
1526	assert!(!self.premultiplied, "can't swap states in premultiplied DFA");
1527
1528	let o1 = id1.to_usize() * self.alphabet_len();
1529	let o2 = id2.to_usize() * self.alphabet_len();
1530	for b in `0`..self.alphabet_len() {
1531	self.trans.swap(o1 + b, o2 + b);
1532	}
1533	}
1534
1535	/// Truncate the states in this DFA to the given count.
1536	///
1537	/// This routine does not do anything to check the correctness of this
1538	/// truncation. Callers must ensure that other states pointing to truncated
1539	/// states are updated appropriately.
1540	///
1541	/// This cannot be called on a premultiplied DFA.
1542	pub fn truncate_states(&mut self, count: usize) {
1543	assert!(!self.premultiplied, "can't truncate in premultiplied DFA");
1544
1545	let alphabet_len = self.alphabet_len();
1546	self.trans.truncate(count * alphabet_len);
1547	self.state_count = count;
1548	}
1549
1550	/// This routine shuffles all match states in this DFA---according to the
1551	/// given map---to the beginning of the DFA such that every non-match state
1552	/// appears after every match state. (With one exception: the special dead
1553	/// state remains as the first state.) The given map should have length
1554	/// exactly equivalent to the number of states in this DFA.
1555	///
1556	/// The purpose of doing this shuffling is to avoid the need to store
1557	/// additional state to determine whether a state is a match state or not.
1558	/// It also enables a single conditional in the core matching loop instead
1559	/// of two.
1560	///
1561	/// This updates `self.max_match` to point to the last matching state as
1562	/// well as `self.start` if the starting state was moved.
1563	pub fn shuffle_match_states(&mut self, is_match: &[bool]) {
1564	assert!(
1565	!self.premultiplied,
1566	"cannot shuffle match states of premultiplied DFA"
1567	);
1568	assert_eq!(self.state_count, is_match.len());
1569
1570	if self.state_count <= `1` {
1571	return;
1572	}
1573
1574	let mut first_non_match = `1`;
1575	while first_non_match < self.state_count && is_match[first_non_match] {
1576	first_non_match += `1`;
1577	}
1578
1579	let mut swaps: Vec<S> = vec![dead_id(); self.state_count];
1580	let mut cur = self.state_count - `1`;
1581	while cur > first_non_match {
1582	if is_match[cur] {
1583	self.swap_states(
1584	S::from_usize(cur),
1585	S::from_usize(first_non_match),
1586	);
1587	swaps[cur] = S::from_usize(first_non_match);
1588	swaps[first_non_match] = S::from_usize(cur);
1589
1590	first_non_match += `1`;
1591	while first_non_match < cur && is_match[first_non_match] {
1592	first_non_match += `1`;
1593	}
1594	}
1595	cur -= `1`;
1596	}
1597	for id in (`0`..self.state_count).map(S::from_usize) {
1598	for (_, next) in self.get_state_mut(id).iter_mut() {
1599	if swaps[next.to_usize()] != dead_id() {
1600	*next = swaps[next.to_usize()];
1601	}
1602	}
1603	}
1604	if swaps[self.start.to_usize()] != dead_id() {
1605	self.start = swaps[self.start.to_usize()];
1606	}
1607	self.max_match = S::from_usize(first_non_match - `1`);
1608	}
1609	}
1610
1611	#[cfg(feature = "std")]
1612	impl<T: AsRef<[S]>, S: StateID> fmt::Debug for Repr<T, S> {
1613	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1614	fn state_status<T: AsRef<[S]>, S: StateID>(
1615	dfa: &Repr<T, S>,
1616	id: S,
1617	) -> &'static str {
1618	if id == dead_id() {
1619	if dfa.is_match_state(id) {
1620	"D*"
1621	} else {
1622	"D "
1623	}
1624	} else if id == dfa.start_state() {
1625	if dfa.is_match_state(id) {
1626	">*"
1627	} else {
1628	"> "
1629	}
1630	} else {
1631	if dfa.is_match_state(id) {
1632	" *"
1633	} else {
1634	" "
1635	}
1636	}
1637	}
1638
1639	writeln!(f, "DenseDFA(")?;
1640	for (id, state) in self.states() {
1641	let status = state_status(self, id);
1642	writeln!(f, "{}{:`06`}: {:?}", status, id.to_usize(), state)?;
1643	}
1644	writeln!(f, ")")?;
1645	Ok(())
1646	}
1647	}
1648
1649	/// An iterator over all states in a DFA.
1650	///
1651	/// This iterator yields a tuple for each state. The first element of the
1652	/// tuple corresponds to a state's identifier, and the second element
1653	/// corresponds to the state itself (comprised of its transitions).
1654	///
1655	/// If this DFA is premultiplied, then the state identifiers are in turn
1656	/// premultiplied as well, making them usable without additional modification.
1657	///
1658	/// `'a` corresponding to the lifetime of original DFA, `T` corresponds to
1659	/// the type of the transition table itself and `S` corresponds to the state
1660	/// identifier representation.
1661	#[cfg(feature = "std")]
1662	pub(crate) struct StateIter<'a, T: 'a, S: 'a> {
1663	dfa: &'a Repr<T, S>,
1664	it: iter::Enumerate<slice::Chunks<'a, S>>,
1665	}
1666
1667	#[cfg(feature = "std")]
1668	impl<'a, T: AsRef<[S]>, S: StateID> Iterator for StateIter<'a, T, S> {
1669	type Item = (S, State<'a, S>);
1670
1671	fn next(&mut self) -> Option<(S, State<'a, S>)> {
1672	self.it.next().map(\|(id: usize, chunk: &[S])\| {
1673	let state: State<'_, S> = State { transitions: chunk };
1674	let id: usize = if self.dfa.premultiplied {
1675	id * self.dfa.alphabet_len()
1676	} else {
1677	id
1678	};
1679	(S::from_usize(id), state)
1680	})
1681	}
1682	}
1683
1684	/// An immutable representation of a single DFA state.
1685	///
1686	/// `'a` correspondings to the lifetime of a DFA's transition table and `S`
1687	/// corresponds to the state identifier representation.
1688	#[cfg(feature = "std")]
1689	pub(crate) struct State<'a, S: 'a> {
1690	transitions: &'a [S],
1691	}
1692
1693	#[cfg(feature = "std")]
1694	impl<'a, S: StateID> State<'a, S> {
1695	/// Return an iterator over all transitions in this state. This yields
1696	/// a number of transitions equivalent to the alphabet length of the
1697	/// corresponding DFA.
1698	///
1699	/// Each transition is represented by a tuple. The first element is
1700	/// the input byte for that transition and the second element is the
1701	/// transitions itself.
1702	pub fn transitions(&self) -> StateTransitionIter<S> {
1703	StateTransitionIter { it: self.transitions.iter().enumerate() }
1704	}
1705
1706	/// Return an iterator over a sparse representation of the transitions in
1707	/// this state. Only non-dead transitions are returned.
1708	///
1709	/// The "sparse" representation in this case corresponds to a sequence of
1710	/// triples. The first two elements of the triple comprise an inclusive
1711	/// byte range while the last element corresponds to the transition taken
1712	/// for all bytes in the range.
1713	///
1714	/// This is somewhat more condensed than the classical sparse
1715	/// representation (where you have an element for every non-dead
1716	/// transition), but in practice, checking if a byte is in a range is very
1717	/// cheap and using ranges tends to conserve quite a bit more space.
1718	pub fn sparse_transitions(&self) -> StateSparseTransitionIter<S> {
1719	StateSparseTransitionIter { dense: self.transitions(), cur: None }
1720	}
1721	}
1722
1723	#[cfg(feature = "std")]
1724	impl<'a, S: StateID> fmt::Debug for State<'a, S> {
1725	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1726	let mut transitions: Vec = vec![];
1727	for (start: u8, end: u8, next_id: S) in self.sparse_transitions() {
1728	let line: String = if start == end {
1729	format!("{} => {}", escape(start), next_id.to_usize())
1730	} else {
1731	format!(
1732	"{}-{} => {}",
1733	escape(start),
1734	escape(end),
1735	next_id.to_usize(),
1736	)
1737	};
1738	transitions.push(line);
1739	}
1740	write!(f, "{}", transitions.join(", "))?;
1741	Ok(())
1742	}
1743	}
1744
1745	/// An iterator over all transitions in a single DFA state. This yields
1746	/// a number of transitions equivalent to the alphabet length of the
1747	/// corresponding DFA.
1748	///
1749	/// Each transition is represented by a tuple. The first element is the input
1750	/// byte for that transition and the second element is the transitions itself.
1751	#[cfg(feature = "std")]
1752	#[derive(Debug)]
1753	pub(crate) struct StateTransitionIter<'a, S: 'a> {
1754	it: iter::Enumerate<slice::Iter<'a, S>>,
1755	}
1756
1757	#[cfg(feature = "std")]
1758	impl<'a, S: StateID> Iterator for StateTransitionIter<'a, S> {
1759	type Item = (u8, S);
1760
1761	fn next(&mut self) -> Option<(u8, S)> {
1762	self.it.next().map(\|(i: usize, &id: S)\| (i as u8, id))
1763	}
1764	}
1765
1766	/// An iterator over all transitions in a single DFA state using a sparse
1767	/// representation.
1768	///
1769	/// Each transition is represented by a triple. The first two elements of the
1770	/// triple comprise an inclusive byte range while the last element corresponds
1771	/// to the transition taken for all bytes in the range.
1772	#[cfg(feature = "std")]
1773	#[derive(Debug)]
1774	pub(crate) struct StateSparseTransitionIter<'a, S: 'a> {
1775	dense: StateTransitionIter<'a, S>,
1776	cur: Option<(u8, u8, S)>,
1777	}
1778
1779	#[cfg(feature = "std")]
1780	impl<'a, S: StateID> Iterator for StateSparseTransitionIter<'a, S> {
1781	type Item = (u8, u8, S);
1782
1783	fn next(&mut self) -> Option<(u8, u8, S)> {
1784	while let Some((b, next)) = self.dense.next() {
1785	let (prev_start, prev_end, prev_next) = match self.cur {
1786	Some(t) => t,
1787	None => {
1788	self.cur = Some((b, b, next));
1789	continue;
1790	}
1791	};
1792	if prev_next == next {
1793	self.cur = Some((prev_start, b, prev_next));
1794	} else {
1795	self.cur = Some((b, b, next));
1796	if prev_next != dead_id() {
1797	return Some((prev_start, prev_end, prev_next));
1798	}
1799	}
1800	}
1801	if let Some((start, end, next)) = self.cur.take() {
1802	if next != dead_id() {
1803	return Some((start, end, next));
1804	}
1805	}
1806	None
1807	}
1808	}
1809
1810	/// A mutable representation of a single DFA state.
1811	///
1812	/// `'a` correspondings to the lifetime of a DFA's transition table and `S`
1813	/// corresponds to the state identifier representation.
1814	#[cfg(feature = "std")]
1815	pub(crate) struct StateMut<'a, S: 'a> {
1816	transitions: &'a mut [S],
1817	}
1818
1819	#[cfg(feature = "std")]
1820	impl<'a, S: StateID> StateMut<'a, S> {
1821	/// Return an iterator over all transitions in this state. This yields
1822	/// a number of transitions equivalent to the alphabet length of the
1823	/// corresponding DFA.
1824	///
1825	/// Each transition is represented by a tuple. The first element is the
1826	/// input byte for that transition and the second element is a mutable
1827	/// reference to the transition itself.
1828	pub fn iter_mut(&mut self) -> StateTransitionIterMut<S> {
1829	StateTransitionIterMut { it: self.transitions.iter_mut().enumerate() }
1830	}
1831	}
1832
1833	#[cfg(feature = "std")]
1834	impl<'a, S: StateID> fmt::Debug for StateMut<'a, S> {
1835	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1836	fmt::Debug::fmt(&State { transitions: self.transitions }, f)
1837	}
1838	}
1839
1840	/// A mutable iterator over all transitions in a DFA state.
1841	///
1842	/// Each transition is represented by a tuple. The first element is the
1843	/// input byte for that transition and the second element is a mutable
1844	/// reference to the transition itself.
1845	#[cfg(feature = "std")]
1846	#[derive(Debug)]
1847	pub(crate) struct StateTransitionIterMut<'a, S: 'a> {
1848	it: iter::Enumerate<slice::IterMut<'a, S>>,
1849	}
1850
1851	#[cfg(feature = "std")]
1852	impl<'a, S: StateID> Iterator for StateTransitionIterMut<'a, S> {
1853	type Item = (u8, &'a mut S);
1854
1855	fn next(&mut self) -> Option<(u8, &'a mut S)> {
1856	self.it.next().map(\|(i: usize, id: &mut S)\| (i as u8, id))
1857	}
1858	}
1859
1860	/// A builder for constructing a deterministic finite automaton from regular
1861	/// expressions.
1862	///
1863	/// This builder permits configuring several aspects of the construction
1864	/// process such as case insensitivity, Unicode support and various options
1865	/// that impact the size of the generated DFA. In some cases, options (like
1866	/// performing DFA minimization) can come with a substantial additional cost.
1867	///
1868	/// This builder always constructs a single* DFA. As such, this builder can*
1869	/// only be used to construct regexes that either detect the presence of a
1870	/// match or find the end location of a match. A single DFA cannot produce both
1871	/// the start and end of a match. For that information, use a
1872	/// [`Regex`](struct.Regex.html), which can be similarly configured using
1873	/// [`RegexBuilder`](struct.RegexBuilder.html).
1874	#[cfg(feature = "std")]
1875	#[derive(Clone, Debug)]
1876	pub struct Builder {
1877	parser: ParserBuilder,
1878	nfa: nfa::Builder,
1879	anchored: bool,
1880	minimize: bool,
1881	premultiply: bool,
1882	byte_classes: bool,
1883	reverse: bool,
1884	longest_match: bool,
1885	}
1886
1887	#[cfg(feature = "std")]
1888	impl Builder {
1889	/// Create a new DenseDFA builder with the default configuration.
1890	pub fn new() -> Builder {
1891	let mut nfa = nfa::Builder::new();
1892	// This is enabled by default, but we set it here anyway. Since we're
1893	// building a DFA, shrinking the NFA is always a good idea.
1894	nfa.shrink(`true`);
1895	Builder {
1896	parser: ParserBuilder::new(),
1897	nfa,
1898	anchored: `false`,
1899	minimize: `false`,
1900	premultiply: `true`,
1901	byte_classes: `true`,
1902	reverse: `false`,
1903	longest_match: `false`,
1904	}
1905	}
1906
1907	/// Build a DFA from the given pattern.
1908	///
1909	/// If there was a problem parsing or compiling the pattern, then an error
1910	/// is returned.
1911	pub fn build(&self, pattern: &str) -> Result<DenseDFA<Vec<usize>, usize>> {
1912	self.build_with_size::<usize>(pattern)
1913	}
1914
1915	/// Build a DFA from the given pattern using a specific representation for
1916	/// the DFA's state IDs.
1917	///
1918	/// If there was a problem parsing or compiling the pattern, then an error
1919	/// is returned.
1920	///
1921	/// The representation of state IDs is determined by the `S` type
1922	/// parameter. In general, `S` is usually one of `u8`, `u16`, `u32`, `u64`
1923	/// or `usize`, where `usize` is the default used for `build`. The purpose
1924	/// of specifying a representation for state IDs is to reduce the memory
1925	/// footprint of a DFA.
1926	///
1927	/// When using this routine, the chosen state ID representation will be
1928	/// used throughout determinization and minimization, if minimization
1929	/// was requested. Even if the minimized DFA can fit into the chosen
1930	/// state ID representation but the initial determinized DFA cannot,
1931	/// then this will still return an error. To get a minimized DFA with a
1932	/// smaller state ID representation, first build it with a bigger state ID
1933	/// representation, and then shrink the size of the DFA using one of its
1934	/// conversion routines, such as
1935	/// [`DenseDFA::to_u16`](enum.DenseDFA.html#method.to_u16).
1936	pub fn build_with_size<S: StateID>(
1937	&self,
1938	pattern: &str,
1939	) -> Result<DenseDFA<Vec<S>, S>> {
1940	self.build_from_nfa(&self.build_nfa(pattern)?)
1941	}
1942
1943	/// An internal only (for now) API for building a dense DFA directly from
1944	/// an NFA.
1945	pub(crate) fn build_from_nfa<S: StateID>(
1946	&self,
1947	nfa: &NFA,
1948	) -> Result<DenseDFA<Vec<S>, S>> {
1949	if self.longest_match && !self.anchored {
1950	return Err(Error::unsupported_longest_match());
1951	}
1952
1953	let mut dfa = if self.byte_classes {
1954	Determinizer::new(nfa)
1955	.with_byte_classes()
1956	.longest_match(self.longest_match)
1957	.build()
1958	} else {
1959	Determinizer::new(nfa).longest_match(self.longest_match).build()
1960	}?;
1961	if self.minimize {
1962	dfa.minimize();
1963	}
1964	if self.premultiply {
1965	dfa.premultiply()?;
1966	}
1967	Ok(dfa.into_dense_dfa())
1968	}
1969
1970	/// Builds an NFA from the given pattern.
1971	pub(crate) fn build_nfa(&self, pattern: &str) -> Result<NFA> {
1972	let hir = self.parser.build().parse(pattern).map_err(Error::syntax)?;
1973	Ok(self.nfa.build(&hir)?)
1974	}
1975
1976	/// Set whether matching must be anchored at the beginning of the input.
1977	///
1978	/// When enabled, a match must begin at the start of the input. When
1979	/// disabled, the DFA will act as if the pattern started with a `.?`,*
1980	/// which enables a match to appear anywhere.
1981	///
1982	/// By default this is disabled.
1983	pub fn anchored(&mut self, yes: bool) -> &mut Builder {
1984	self.anchored = yes;
1985	self.nfa.anchored(yes);
1986	self
1987	}
1988
1989	/// Enable or disable the case insensitive flag by default.
1990	///
1991	/// By default this is disabled. It may alternatively be selectively
1992	/// enabled in the regular expression itself via the `i` flag.
1993	pub fn case_insensitive(&mut self, yes: bool) -> &mut Builder {
1994	self.parser.case_insensitive(yes);
1995	self
1996	}
1997
1998	/// Enable verbose mode in the regular expression.
1999	///
2000	/// When enabled, verbose mode permits insigificant whitespace in many
2001	/// places in the regular expression, as well as comments. Comments are
2002	/// started using `#` and continue until the end of the line.
2003	///
2004	/// By default, this is disabled. It may be selectively enabled in the
2005	/// regular expression by using the `x` flag regardless of this setting.
2006	pub fn ignore_whitespace(&mut self, yes: bool) -> &mut Builder {
2007	self.parser.ignore_whitespace(yes);
2008	self
2009	}
2010
2011	/// Enable or disable the "dot matches any character" flag by default.
2012	///
2013	/// By default this is disabled. It may alternatively be selectively
2014	/// enabled in the regular expression itself via the `s` flag.
2015	pub fn dot_matches_new_line(&mut self, yes: bool) -> &mut Builder {
2016	self.parser.dot_matches_new_line(yes);
2017	self
2018	}
2019
2020	/// Enable or disable the "swap greed" flag by default.
2021	///
2022	/// By default this is disabled. It may alternatively be selectively
2023	/// enabled in the regular expression itself via the `U` flag.
2024	pub fn swap_greed(&mut self, yes: bool) -> &mut Builder {
2025	self.parser.swap_greed(yes);
2026	self
2027	}
2028
2029	/// Enable or disable the Unicode flag (`u`) by default.
2030	///
2031	/// By default this is enabled. It may alternatively be selectively
2032	/// disabled in the regular expression itself via the `u` flag.
2033	///
2034	/// Note that unless `allow_invalid_utf8` is enabled (it's disabled by
2035	/// default), a regular expression will fail to parse if Unicode mode is
2036	/// disabled and a sub-expression could possibly match invalid UTF-8.
2037	pub fn unicode(&mut self, yes: bool) -> &mut Builder {
2038	self.parser.unicode(yes);
2039	self
2040	}
2041
2042	/// When enabled, the builder will permit the construction of a regular
2043	/// expression that may match invalid UTF-8.
2044	///
2045	/// When disabled (the default), the builder is guaranteed to produce a
2046	/// regex that will only ever match valid UTF-8 (otherwise, the builder
2047	/// will return an error).
2048	pub fn allow_invalid_utf8(&mut self, yes: bool) -> &mut Builder {
2049	self.parser.allow_invalid_utf8(yes);
2050	self.nfa.allow_invalid_utf8(yes);
2051	self
2052	}
2053
2054	/// Set the nesting limit used for the regular expression parser.
2055	///
2056	/// The nesting limit controls how deep the abstract syntax tree is allowed
2057	/// to be. If the AST exceeds the given limit (e.g., with too many nested
2058	/// groups), then an error is returned by the parser.
2059	///
2060	/// The purpose of this limit is to act as a heuristic to prevent stack
2061	/// overflow when building a finite automaton from a regular expression's
2062	/// abstract syntax tree. In particular, construction currently uses
2063	/// recursion. In the future, the implementation may stop using recursion
2064	/// and this option will no longer be necessary.
2065	///
2066	/// This limit is not checked until the entire AST is parsed. Therefore,
2067	/// if callers want to put a limit on the amount of heap space used, then
2068	/// they should impose a limit on the length, in bytes, of the concrete
2069	/// pattern string. In particular, this is viable since the parser will
2070	/// limit itself to heap space proportional to the lenth of the pattern
2071	/// string.
2072	///
2073	/// Note that a nest limit of `0` will return a nest limit error for most
2074	/// patterns but not all. For example, a nest limit of `0` permits `a` but
2075	/// not `ab`, since `ab` requires a concatenation AST item, which results
2076	/// in a nest depth of `1`. In general, a nest limit is not something that
2077	/// manifests in an obvious way in the concrete syntax, therefore, it
2078	/// should not be used in a granular way.
2079	pub fn nest_limit(&mut self, limit: u32) -> &mut Builder {
2080	self.parser.nest_limit(limit);
2081	self
2082	}
2083
2084	/// Minimize the DFA.
2085	///
2086	/// When enabled, the DFA built will be minimized such that it is as small
2087	/// as possible.
2088	///
2089	/// Whether one enables minimization or not depends on the types of costs
2090	/// you're willing to pay and how much you care about its benefits. In
2091	/// particular, minimization has worst case `O(nklogn)` time and `O(kn)`*
2092	/// space, where `n` is the number of DFA states and `k` is the alphabet
2093	/// size. In practice, minimization can be quite costly in terms of both
2094	/// space and time, so it should only be done if you're willing to wait
2095	/// longer to produce a DFA. In general, you might want a minimal DFA in
2096	/// the following circumstances:
2097	///
2098	/// 1. You would like to optimize for the size of the automaton. This can
2099	/// manifest in one of two ways. Firstly, if you're converting the
2100	/// DFA into Rust code (or a table embedded in the code), then a minimal
2101	/// DFA will translate into a corresponding reduction in code size, and
2102	/// thus, also the final compiled binary size. Secondly, if you are
2103	/// building many DFAs and putting them on the heap, you'll be able to
2104	/// fit more if they are smaller. Note though that building a minimal
2105	/// DFA itself requires additional space; you only realize the space
2106	/// savings once the minimal DFA is constructed (at which point, the
2107	/// space used for minimization is freed).
2108	/// 2. You've observed that a smaller DFA results in faster match
2109	/// performance. Naively, this isn't guaranteed since there is no
2110	/// inherent difference between matching with a bigger-than-minimal
2111	/// DFA and a minimal DFA. However, a smaller DFA may make use of your
2112	/// CPU's cache more efficiently.
2113	/// 3. You are trying to establish an equivalence between regular
2114	/// languages. The standard method for this is to build a minimal DFA
2115	/// for each language and then compare them. If the DFAs are equivalent
2116	/// (up to state renaming), then the languages are equivalent.
2117	///
2118	/// This option is disabled by default.
2119	pub fn minimize(&mut self, yes: bool) -> &mut Builder {
2120	self.minimize = yes;
2121	self
2122	}
2123
2124	/// Premultiply state identifiers in the DFA's transition table.
2125	///
2126	/// When enabled, state identifiers are premultiplied to point to their
2127	/// corresponding row in the DFA's transition table. That is, given the
2128	/// `i`th state, its corresponding premultiplied identifier is `i k`*
2129	/// where `k` is the alphabet size of the DFA. (The alphabet size is at
2130	/// most 256, but is in practice smaller if byte classes is enabled.)
2131	///
2132	/// When state identifiers are not premultiplied, then the identifier of
2133	/// the `i`th state is `i`.
2134	///
2135	/// The advantage of premultiplying state identifiers is that is saves
2136	/// a multiplication instruction per byte when searching with the DFA.
2137	/// This has been observed to lead to a 20% performance benefit in
2138	/// micro-benchmarks.
2139	///
2140	/// The primary disadvantage of premultiplying state identifiers is
2141	/// that they require a larger integer size to represent. For example,
2142	/// if your DFA has 200 states, then its premultiplied form requires
2143	/// 16 bits to represent every possible state identifier, where as its
2144	/// non-premultiplied form only requires 8 bits.
2145	///
2146	/// This option is enabled by default.
2147	pub fn premultiply(&mut self, yes: bool) -> &mut Builder {
2148	self.premultiply = yes;
2149	self
2150	}
2151
2152	/// Shrink the size of the DFA's alphabet by mapping bytes to their
2153	/// equivalence classes.
2154	///
2155	/// When enabled, each DFA will use a map from all possible bytes to their
2156	/// corresponding equivalence class. Each equivalence class represents a
2157	/// set of bytes that does not discriminate between a match and a non-match
2158	/// in the DFA. For example, the pattern `[ab]+` has at least two
2159	/// equivalence classes: a set containing `a` and `b` and a set containing
2160	/// every byte except for `a` and `b`. `a` and `b` are in the same
2161	/// equivalence classes because they never discriminate between a match
2162	/// and a non-match.
2163	///
2164	/// The advantage of this map is that the size of the transition table can
2165	/// be reduced drastically from `#states 256 * sizeof(id)` to*
2166	/// `#states k * sizeof(id)` where `k` is the number of equivalence*
2167	/// classes. As a result, total space usage can decrease substantially.
2168	/// Moreover, since a smaller alphabet is used, compilation becomes faster
2169	/// as well.
2170	///
2171	/// The disadvantage of this map is that every byte searched must be
2172	/// passed through this map before it can be used to determine the next
2173	/// transition. This has a small match time performance cost.
2174	///
2175	/// This option is enabled by default.
2176	pub fn byte_classes(&mut self, yes: bool) -> &mut Builder {
2177	self.byte_classes = yes;
2178	self
2179	}
2180
2181	/// Reverse the DFA.
2182	///
2183	/// A DFA reversal is performed by reversing all of the concatenated
2184	/// sub-expressions in the original pattern, recursively. The resulting
2185	/// DFA can be used to match the pattern starting from the end of a string
2186	/// instead of the beginning of a string.
2187	///
2188	/// Generally speaking, a reversed DFA is most useful for finding the start
2189	/// of a match, since a single forward DFA is only capable of finding the
2190	/// end of a match. This start of match handling is done for you
2191	/// automatically if you build a [`Regex`](struct.Regex.html).
2192	pub fn reverse(&mut self, yes: bool) -> &mut Builder {
2193	self.reverse = yes;
2194	self.nfa.reverse(yes);
2195	self
2196	}
2197
2198	/// Find the longest possible match.
2199	///
2200	/// This is distinct from the default leftmost-first match semantics in
2201	/// that it treats all NFA states as having equivalent priority. In other
2202	/// words, the longest possible match is always found and it is not
2203	/// possible to implement non-greedy match semantics when this is set. That
2204	/// is, `a+` and `a+?` are equivalent when this is enabled.
2205	///
2206	/// In particular, a practical issue with this option at the moment is that
2207	/// it prevents unanchored searches from working correctly, since
2208	/// unanchored searches are implemented by prepending an non-greedy `.?`*
2209	/// to the beginning of the pattern. As stated above, non-greedy match
2210	/// semantics aren't supported. Therefore, if this option is enabled and
2211	/// an unanchored search is requested, then building a DFA will return an
2212	/// error.
2213	///
2214	/// This option is principally useful when building a reverse DFA for
2215	/// finding the start of a match. If you are building a regex with
2216	/// [`RegexBuilder`](struct.RegexBuilder.html), then this is handled for
2217	/// you automatically. The reason why this is necessary for start of match
2218	/// handling is because we want to find the earliest possible starting
2219	/// position of a match to satisfy leftmost-first match semantics. When
2220	/// matching in reverse, this means finding the longest possible match,
2221	/// hence, this option.
2222	///
2223	/// By default this is disabled.
2224	pub fn longest_match(&mut self, yes: bool) -> &mut Builder {
2225	// There is prior art in RE2 that shows how this can support unanchored
2226	// searches. Instead of treating all NFA states as having equivalent
2227	// priority, we instead group NFA states into sets, and treat members
2228	// of each set as having equivalent priority, but having greater
2229	// priority than all following members of different sets. We then
2230	// essentially assign a higher priority to everything over the prefix
2231	// `.?`.*
2232	self.longest_match = yes;
2233	self
2234	}
2235
2236	/// Apply best effort heuristics to shrink the NFA at the expense of more
2237	/// time/memory.
2238	///
2239	/// This may be exposed in the future, but for now is exported for use in
2240	/// the `regex-automata-debug` tool.
2241	#[doc(hidden)]
2242	pub fn shrink(&mut self, yes: bool) -> &mut Builder {
2243	self.nfa.shrink(yes);
2244	self
2245	}
2246	}
2247
2248	#[cfg(feature = "std")]
2249	impl Default for Builder {
2250	fn default() -> Builder {
2251	Builder::new()
2252	}
2253	}
2254
2255	/// Return the given byte as its escaped string form.
2256	#[cfg(feature = "std")]
2257	fn escape(b: u8) -> String {
2258	use std::ascii;
2259
2260	String::from_utf8(vec:ascii::escape_default(b).collect::<Vec<_>>()).unwrap()
2261	}
2262
2263	#[cfg(all(test, feature = "std"))]
2264	mod tests {
2265	use super::*;
2266
2267	#[test]
2268	fn errors_when_converting_to_smaller_dfa() {
2269	let pattern = r"\w{10}";
2270	let dfa = Builder::new()
2271	.byte_classes(`false`)
2272	.anchored(`true`)
2273	.premultiply(`false`)
2274	.build_with_size::<u16>(pattern)
2275	.unwrap();
2276	assert!(dfa.to_u8().is_err());
2277	}
2278
2279	#[test]
2280	fn errors_when_determinization_would_overflow() {
2281	let pattern = r"\w{10}";
2282
2283	let mut builder = Builder::new();
2284	builder.byte_classes(`false`).anchored(`true`).premultiply(`false`);
2285	// using u16 is fine
2286	assert!(builder.build_with_size::<u16>(pattern).is_ok());
2287	// // ... but u8 results in overflow (because there are >256 states)
2288	assert!(builder.build_with_size::<u8>(pattern).is_err());
2289	}
2290
2291	#[test]
2292	fn errors_when_premultiply_would_overflow() {
2293	let pattern = r"[a-z]";
2294
2295	let mut builder = Builder::new();
2296	builder.byte_classes(`false`).anchored(`true`).premultiply(`false`);
2297	// without premultiplication is OK
2298	assert!(builder.build_with_size::<u8>(pattern).is_ok());
2299	// ... but with premultiplication overflows u8
2300	builder.premultiply(`true`);
2301	assert!(builder.build_with_size::<u8>(pattern).is_err());
2302	}
2303
2304	// let data = ::std::fs::read_to_string("/usr/share/dict/words").unwrap();
2305	// let mut words: Vec<&str> = data.lines().collect();
2306	// println!("{} words", words.len());
2307	// words.sort_by(\|w1, w2\| w1.len().cmp(&w2.len()).reverse());
2308	// let pattern = words.join("\|");
2309	// print_automata_counts(&pattern);
2310	// print_automata(&pattern);
2311
2312	// print_automata(r"[01]1[01]{5}");*
2313	// print_automata(r"X(.?){0,8}Y");
2314	// print_automata_counts(r"\p{alphabetic}");
2315	// print_automata(r"ab+\|cdefg");*
2316	// print_automata(r"(..)(...)");
2317
2318	// let pattern = r"\p{any}?\p{Other_Uppercase}";*
2319	// let pattern = r"\p{any}?\w+";*
2320	// print_automata_counts(pattern);
2321	// print_automata_counts(r"(?-u:\w)");
2322
2323	// let pattern = r"\p{Greek}";
2324	// let pattern = r"zZzZzZzZzZ";
2325	// let pattern = grapheme_pattern();
2326	// let pattern = r"\p{Ideographic}";
2327	// let pattern = r"\w{10}"; // 51784 --> 41264
2328	// let pattern = r"\w"; // 5182
2329	// let pattern = r"a";*
2330	// print_automata(pattern);
2331	// let (_, _, dfa) = build_automata(pattern);
2332	}
2333