1#[cfg(feature = "std")]
2use core::fmt;
3#[cfg(feature = "std")]
4use core::iter;
5use core::mem;
6use core::slice;
7
8#[cfg(feature = "std")]
9use byteorder::{BigEndian, LittleEndian};
10use byteorder::{ByteOrder, NativeEndian};
11#[cfg(feature = "std")]
12use regex_syntax::ParserBuilder;
13
14use classes::ByteClasses;
15#[cfg(feature = "std")]
16use determinize::Determinizer;
17use dfa::DFA;
18#[cfg(feature = "std")]
19use error::{Error, Result};
20#[cfg(feature = "std")]
21use minimize::Minimizer;
22#[cfg(feature = "std")]
23use nfa::{self, NFA};
24#[cfg(feature = "std")]
25use sparse::SparseDFA;
26use state_id::{dead_id, StateID};
27#[cfg(feature = "std")]
28use 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.
42const ALPHABET_LEN: usize = 256;
43
44/// Masks used in serialization of DFAs.
45pub(crate) const MASK_PREMULTIPLIED: u16 = 0b0000_0000_0000_0001;
46pub(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)]
142pub 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
174impl<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")]
190impl 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")]
218impl<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
240impl<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")]
306impl<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
454impl<'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")]
524impl<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
546impl<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)]
673pub struct Standard<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
674
675impl<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)]
733pub struct ByteClass<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
734
735impl<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)]
794pub struct Premultiplied<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
795
796impl<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)]
847pub struct PremultipliedByteClass<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
848
849impl<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))]
897pub(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")]
978impl<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
1011impl<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
1297impl<'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")]
1405impl<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")]
1612impl<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")]
1662pub(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")]
1668impl<'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")]
1689pub(crate) struct State<'a, S: 'a> {
1690 transitions: &'a [S],
1691}
1692
1693#[cfg(feature = "std")]
1694impl<'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")]
1724impl<'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)]
1753pub(crate) struct StateTransitionIter<'a, S: 'a> {
1754 it: iter::Enumerate<slice::Iter<'a, S>>,
1755}
1756
1757#[cfg(feature = "std")]
1758impl<'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)]
1774pub(crate) struct StateSparseTransitionIter<'a, S: 'a> {
1775 dense: StateTransitionIter<'a, S>,
1776 cur: Option<(u8, u8, S)>,
1777}
1778
1779#[cfg(feature = "std")]
1780impl<'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")]
1815pub(crate) struct StateMut<'a, S: 'a> {
1816 transitions: &'a mut [S],
1817}
1818
1819#[cfg(feature = "std")]
1820impl<'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")]
1834impl<'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)]
1847pub(crate) struct StateTransitionIterMut<'a, S: 'a> {
1848 it: iter::Enumerate<slice::IterMut<'a, S>>,
1849}
1850
1851#[cfg(feature = "std")]
1852impl<'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)]
1876pub 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")]
1888impl 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(n*k*logn)` time and `O(k*n)`
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")]
2249impl 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")]
2257fn 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"))]
2264mod 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"a*b+|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