Skip to main content

regex_automata/util/
primitives.rs

1/*!
2Lower level primitive types that are useful in a variety of circumstances.
3
4# Overview
5
6This list represents the principle types in this module and briefly describes
7when you might want to use them.
8
9* [`PatternID`] - A type that represents the identifier of a regex pattern.
10This is probably the most widely used type in this module (which is why it's
11also re-exported in the crate root).
12* [`StateID`] - A type the represents the identifier of a finite automaton
13state. This is used for both NFAs and DFAs, with the notable exception of
14the hybrid NFA/DFA. (The hybrid NFA/DFA uses a special purpose "lazy" state
15identifier.)
16* [`SmallIndex`] - The internal representation of both a `PatternID` and a
17`StateID`. Its purpose is to serve as a type that can index memory without
18being as big as a `usize` on 64-bit targets. The main idea behind this type
19is that there are many things in regex engines that will, in practice, never
20overflow a 32-bit integer. (For example, like the number of patterns in a regex
21or the number of states in an NFA.) Thus, a `SmallIndex` can be used to index
22memory without peppering `as` casts everywhere. Moreover, it forces callers
23to handle errors in the case where, somehow, the value would otherwise overflow
24either a 32-bit integer or a `usize` (e.g., on 16-bit targets).
25* [`NonMaxUsize`] - Represents a `usize` that cannot be `usize::MAX`. As a
26result, `Option<NonMaxUsize>` has the same size in memory as a `usize`. This
27useful, for example, when representing the offsets of submatches since it
28reduces memory usage by a factor of 2. It is a legal optimization since Rust
29guarantees that slices never have a length that exceeds `isize::MAX`.
30*/
31
32use core::num::NonZeroUsize;
33
34#[cfg(feature = "alloc")]
35use alloc::vec::Vec;
36
37use crate::util::int::{Usize, U16, U32, U64};
38
39/// A `usize` that can never be `usize::MAX`.
40///
41/// This is similar to `core::num::NonZeroUsize`, but instead of not permitting
42/// a zero value, this does not permit a max value.
43///
44/// This is useful in certain contexts where one wants to optimize the memory
45/// usage of things that contain match offsets. Namely, since Rust slices
46/// are guaranteed to never have a length exceeding `isize::MAX`, we can use
47/// `usize::MAX` as a sentinel to indicate that no match was found. Indeed,
48/// types like `Option<NonMaxUsize>` have exactly the same size in memory as a
49/// `usize`.
50///
51/// This type is defined to be `repr(transparent)` for
52/// `core::num::NonZeroUsize`, which is in turn defined to be
53/// `repr(transparent)` for `usize`.
54#[derive(Clone, Copy, Eq, Hash, PartialEq, PartialOrd, Ord)]
55#[repr(transparent)]
56pub struct NonMaxUsize(NonZeroUsize);
57
58impl NonMaxUsize {
59    /// Create a new `NonMaxUsize` from the given value.
60    ///
61    /// This returns `None` only when the given value is equal to `usize::MAX`.
62    #[inline]
63    pub fn new(value: usize) -> Option<NonMaxUsize> {
64        NonZeroUsize::new(value.wrapping_add(1)).map(NonMaxUsize)
65    }
66
67    /// Return the underlying `usize` value. The returned value is guaranteed
68    /// to not equal `usize::MAX`.
69    #[inline]
70    pub fn get(self) -> usize {
71        self.0.get().wrapping_sub(1)
72    }
73}
74
75// We provide our own Debug impl because seeing the internal repr can be quite
76// surprising if you aren't expecting it. e.g., 'NonMaxUsize(5)' vs just '5'.
77impl core::fmt::Debug for NonMaxUsize {
78    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
79        write!(f, "{:?}", self.get())
80    }
81}
82
83/// A type that represents a "small" index.
84///
85/// The main idea of this type is to provide something that can index memory,
86/// but uses less memory than `usize` on 64-bit systems. Specifically, its
87/// representation is always a `u32` and has `repr(transparent)` enabled. (So
88/// it is safe to transmute between a `u32` and a `SmallIndex`.)
89///
90/// A small index is typically useful in cases where there is no practical way
91/// that the index will overflow a 32-bit integer. A good example of this is
92/// an NFA state. If you could somehow build an NFA with `2^30` states, its
93/// memory usage would be exorbitant and its runtime execution would be so
94/// slow as to be completely worthless. Therefore, this crate generally deems
95/// it acceptable to return an error if it would otherwise build an NFA that
96/// requires a slice longer than what a 32-bit integer can index. In exchange,
97/// we can use 32-bit indices instead of 64-bit indices in various places.
98///
99/// This type ensures this by providing a constructor that will return an error
100/// if its argument cannot fit into the type. This makes it much easier to
101/// handle these sorts of boundary cases that are otherwise extremely subtle.
102///
103/// On all targets, this type guarantees that its value will fit in a `u32`,
104/// `i32`, `usize` and an `isize`. This means that on 16-bit targets, for
105/// example, this type's maximum value will never overflow an `isize`,
106/// which means it will never overflow a `i16` even though its internal
107/// representation is still a `u32`.
108///
109/// The purpose for making the type fit into even signed integer types like
110/// `isize` is to guarantee that the difference between any two small indices
111/// is itself also a small index. This is useful in certain contexts, e.g.,
112/// for delta encoding.
113///
114/// # Other types
115///
116/// The following types wrap `SmallIndex` to provide a more focused use case:
117///
118/// * [`PatternID`] is for representing the identifiers of patterns.
119/// * [`StateID`] is for representing the identifiers of states in finite
120/// automata. It is used for both NFAs and DFAs.
121///
122/// # Representation
123///
124/// This type is always represented internally by a `u32` and is marked as
125/// `repr(transparent)`. Thus, this type always has the same representation as
126/// a `u32`. It is thus safe to transmute between a `u32` and a `SmallIndex`.
127///
128/// # Indexing
129///
130/// For convenience, callers may use a `SmallIndex` to index slices.
131///
132/// # Safety
133///
134/// While a `SmallIndex` is meant to guarantee that its value fits into `usize`
135/// without using as much space as a `usize` on all targets, callers must
136/// not rely on this property for safety. Callers may choose to rely on this
137/// property for correctness however. For example, creating a `SmallIndex` with
138/// an invalid value can be done in entirely safe code. This may in turn result
139/// in panics or silent logical errors.
140#[derive(
141    Clone, Copy, Debug, Default, Eq, Hash, PartialEq, PartialOrd, Ord,
142)]
143#[repr(transparent)]
144pub struct SmallIndex(u32);
145
146impl SmallIndex {
147    /// The maximum index value.
148    #[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
149    pub const MAX: SmallIndex =
150        // FIXME: Use as_usize() once const functions in traits are stable.
151        SmallIndex::new_unchecked(i32::MAX as usize - 1);
152
153    /// The maximum index value.
154    #[cfg(target_pointer_width = "16")]
155    pub const MAX: SmallIndex = SmallIndex::new_unchecked(isize::MAX - 1);
156
157    /// The total number of values that can be represented as a small index.
158    pub const LIMIT: usize = SmallIndex::MAX.as_usize() + 1;
159
160    /// The zero index value.
161    pub const ZERO: SmallIndex = SmallIndex::new_unchecked(0);
162
163    /// The number of bytes that a single small index uses in memory.
164    pub const SIZE: usize = core::mem::size_of::<SmallIndex>();
165
166    /// Create a new small index.
167    ///
168    /// If the given index exceeds [`SmallIndex::MAX`], then this returns
169    /// an error.
170    #[inline]
171    pub fn new(index: usize) -> Result<SmallIndex, SmallIndexError> {
172        SmallIndex::try_from(index)
173    }
174
175    /// Create a new small index without checking whether the given value
176    /// exceeds [`SmallIndex::MAX`].
177    ///
178    /// Using this routine with an invalid index value will result in
179    /// unspecified behavior, but *not* undefined behavior. In particular, an
180    /// invalid index value is likely to cause panics or possibly even silent
181    /// logical errors.
182    ///
183    /// Callers must never rely on a `SmallIndex` to be within a certain range
184    /// for memory safety.
185    #[inline]
186    pub const fn new_unchecked(index: usize) -> SmallIndex {
187        // FIXME: Use as_u32() once const functions in traits are stable.
188        SmallIndex(index as u32)
189    }
190
191    /// Like [`SmallIndex::new`], but panics if the given index is not valid.
192    #[inline]
193    pub fn must(index: usize) -> SmallIndex {
194        SmallIndex::new(index).expect("invalid small index")
195    }
196
197    /// Return this small index as a `usize`. This is guaranteed to never
198    /// overflow `usize`.
199    #[inline]
200    pub const fn as_usize(&self) -> usize {
201        // FIXME: Use as_usize() once const functions in traits are stable.
202        self.0 as usize
203    }
204
205    /// Return this small index as a `u64`. This is guaranteed to never
206    /// overflow.
207    #[inline]
208    pub const fn as_u64(&self) -> u64 {
209        // FIXME: Use u64::from() once const functions in traits are stable.
210        self.0 as u64
211    }
212
213    /// Return the internal `u32` of this small index. This is guaranteed to
214    /// never overflow `u32`.
215    #[inline]
216    pub const fn as_u32(&self) -> u32 {
217        self.0
218    }
219
220    /// Return the internal `u32` of this small index represented as an `i32`.
221    /// This is guaranteed to never overflow an `i32`.
222    #[inline]
223    pub const fn as_i32(&self) -> i32 {
224        // This is OK because we guarantee that our max value is <= i32::MAX.
225        self.0 as i32
226    }
227
228    /// Returns one more than this small index as a usize.
229    ///
230    /// Since a small index has constraints on its maximum value, adding `1` to
231    /// it will always fit in a `usize`, `u32` and a `i32`.
232    #[inline]
233    pub fn one_more(&self) -> usize {
234        self.as_usize() + 1
235    }
236
237    /// Decode this small index from the bytes given using the native endian
238    /// byte order for the current target.
239    ///
240    /// If the decoded integer is not representable as a small index for the
241    /// current target, then this returns an error.
242    #[inline]
243    pub fn from_ne_bytes(
244        bytes: [u8; 4],
245    ) -> Result<SmallIndex, SmallIndexError> {
246        let id = u32::from_ne_bytes(bytes);
247        if id > SmallIndex::MAX.as_u32() {
248            return Err(SmallIndexError { attempted: u64::from(id) });
249        }
250        Ok(SmallIndex::new_unchecked(id.as_usize()))
251    }
252
253    /// Decode this small index from the bytes given using the native endian
254    /// byte order for the current target.
255    ///
256    /// This is analogous to [`SmallIndex::new_unchecked`] in that is does not
257    /// check whether the decoded integer is representable as a small index.
258    #[inline]
259    pub fn from_ne_bytes_unchecked(bytes: [u8; 4]) -> SmallIndex {
260        SmallIndex::new_unchecked(u32::from_ne_bytes(bytes).as_usize())
261    }
262
263    /// Return the underlying small index integer as raw bytes in native endian
264    /// format.
265    #[inline]
266    pub fn to_ne_bytes(&self) -> [u8; 4] {
267        self.0.to_ne_bytes()
268    }
269}
270
271impl<T> core::ops::Index<SmallIndex> for [T] {
272    type Output = T;
273
274    #[inline]
275    fn index(&self, index: SmallIndex) -> &T {
276        &self[index.as_usize()]
277    }
278}
279
280impl<T> core::ops::IndexMut<SmallIndex> for [T] {
281    #[inline]
282    fn index_mut(&mut self, index: SmallIndex) -> &mut T {
283        &mut self[index.as_usize()]
284    }
285}
286
287#[cfg(feature = "alloc")]
288impl<T> core::ops::Index<SmallIndex> for Vec<T> {
289    type Output = T;
290
291    #[inline]
292    fn index(&self, index: SmallIndex) -> &T {
293        &self[index.as_usize()]
294    }
295}
296
297#[cfg(feature = "alloc")]
298impl<T> core::ops::IndexMut<SmallIndex> for Vec<T> {
299    #[inline]
300    fn index_mut(&mut self, index: SmallIndex) -> &mut T {
301        &mut self[index.as_usize()]
302    }
303}
304
305impl From<u8> for SmallIndex {
306    fn from(index: u8) -> SmallIndex {
307        SmallIndex::new_unchecked(usize::from(index))
308    }
309}
310
311impl TryFrom<u16> for SmallIndex {
312    type Error = SmallIndexError;
313
314    fn try_from(index: u16) -> Result<SmallIndex, SmallIndexError> {
315        if u32::from(index) > SmallIndex::MAX.as_u32() {
316            return Err(SmallIndexError { attempted: u64::from(index) });
317        }
318        Ok(SmallIndex::new_unchecked(index.as_usize()))
319    }
320}
321
322impl TryFrom<u32> for SmallIndex {
323    type Error = SmallIndexError;
324
325    fn try_from(index: u32) -> Result<SmallIndex, SmallIndexError> {
326        if index > SmallIndex::MAX.as_u32() {
327            return Err(SmallIndexError { attempted: u64::from(index) });
328        }
329        Ok(SmallIndex::new_unchecked(index.as_usize()))
330    }
331}
332
333impl TryFrom<u64> for SmallIndex {
334    type Error = SmallIndexError;
335
336    fn try_from(index: u64) -> Result<SmallIndex, SmallIndexError> {
337        if index > SmallIndex::MAX.as_u64() {
338            return Err(SmallIndexError { attempted: index });
339        }
340        Ok(SmallIndex::new_unchecked(index.as_usize()))
341    }
342}
343
344impl TryFrom<usize> for SmallIndex {
345    type Error = SmallIndexError;
346
347    fn try_from(index: usize) -> Result<SmallIndex, SmallIndexError> {
348        if index > SmallIndex::MAX.as_usize() {
349            return Err(SmallIndexError { attempted: index.as_u64() });
350        }
351        Ok(SmallIndex::new_unchecked(index))
352    }
353}
354
355#[cfg(test)]
356impl quickcheck::Arbitrary for SmallIndex {
357    fn arbitrary(gen: &mut quickcheck::Gen) -> SmallIndex {
358        use core::cmp::max;
359
360        let id = max(i32::MIN + 1, i32::arbitrary(gen)).abs();
361        if id > SmallIndex::MAX.as_i32() {
362            SmallIndex::MAX
363        } else {
364            SmallIndex::new(usize::try_from(id).unwrap()).unwrap()
365        }
366    }
367}
368
369/// This error occurs when a small index could not be constructed.
370///
371/// This occurs when given an integer exceeding the maximum small index value.
372///
373/// When the `std` feature is enabled, this implements the `Error` trait.
374#[derive(Clone, Debug, Eq, PartialEq)]
375pub struct SmallIndexError {
376    attempted: u64,
377}
378
379impl SmallIndexError {
380    /// Returns the value that could not be converted to a small index.
381    pub fn attempted(&self) -> u64 {
382        self.attempted
383    }
384}
385
386#[cfg(feature = "std")]
387impl std::error::Error for SmallIndexError {}
388
389impl core::fmt::Display for SmallIndexError {
390    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
391        write!(
392            f,
393            "failed to create small index from {:?}, which exceeds {:?}",
394            self.attempted(),
395            SmallIndex::MAX,
396        )
397    }
398}
399
400#[derive(Clone, Debug)]
401pub(crate) struct SmallIndexIter {
402    rng: core::ops::Range<usize>,
403}
404
405impl Iterator for SmallIndexIter {
406    type Item = SmallIndex;
407
408    fn next(&mut self) -> Option<SmallIndex> {
409        if self.rng.start >= self.rng.end {
410            return None;
411        }
412        let next_id = self.rng.start + 1;
413        let id = core::mem::replace(&mut self.rng.start, next_id);
414        // new_unchecked is OK since we asserted that the number of
415        // elements in this iterator will fit in an ID at construction.
416        Some(SmallIndex::new_unchecked(id))
417    }
418}
419
420macro_rules! index_type_impls {
421    ($name:ident, $err:ident, $iter:ident, $withiter:ident) => {
422        impl $name {
423            /// The maximum value.
424            pub const MAX: $name = $name(SmallIndex::MAX);
425
426            /// The total number of values that can be represented.
427            pub const LIMIT: usize = SmallIndex::LIMIT;
428
429            /// The zero value.
430            pub const ZERO: $name = $name(SmallIndex::ZERO);
431
432            /// The number of bytes that a single value uses in memory.
433            pub const SIZE: usize = SmallIndex::SIZE;
434
435            /// Create a new value that is represented by a "small index."
436            ///
437            /// If the given index exceeds the maximum allowed value, then this
438            /// returns an error.
439            #[inline]
440            pub fn new(value: usize) -> Result<$name, $err> {
441                SmallIndex::new(value).map($name).map_err($err)
442            }
443
444            /// Create a new value without checking whether the given argument
445            /// exceeds the maximum.
446            ///
447            /// Using this routine with an invalid value will result in
448            /// unspecified behavior, but *not* undefined behavior. In
449            /// particular, an invalid ID value is likely to cause panics or
450            /// possibly even silent logical errors.
451            ///
452            /// Callers must never rely on this type to be within a certain
453            /// range for memory safety.
454            #[inline]
455            pub const fn new_unchecked(value: usize) -> $name {
456                $name(SmallIndex::new_unchecked(value))
457            }
458
459            /// Like `new`, but panics if the given value is not valid.
460            #[inline]
461            pub fn must(value: usize) -> $name {
462                $name::new(value).expect(concat!(
463                    "invalid ",
464                    stringify!($name),
465                    " value"
466                ))
467            }
468
469            /// Return the internal value as a `usize`. This is guaranteed to
470            /// never overflow `usize`.
471            #[inline]
472            pub const fn as_usize(&self) -> usize {
473                self.0.as_usize()
474            }
475
476            /// Return the internal value as a `u64`. This is guaranteed to
477            /// never overflow.
478            #[inline]
479            pub const fn as_u64(&self) -> u64 {
480                self.0.as_u64()
481            }
482
483            /// Return the internal value as a `u32`. This is guaranteed to
484            /// never overflow `u32`.
485            #[inline]
486            pub const fn as_u32(&self) -> u32 {
487                self.0.as_u32()
488            }
489
490            /// Return the internal value as a i32`. This is guaranteed to
491            /// never overflow an `i32`.
492            #[inline]
493            pub const fn as_i32(&self) -> i32 {
494                self.0.as_i32()
495            }
496
497            /// Returns one more than this value as a usize.
498            ///
499            /// Since values represented by a "small index" have constraints
500            /// on their maximum value, adding `1` to it will always fit in a
501            /// `usize`, `u32` and a `i32`.
502            #[inline]
503            pub fn one_more(&self) -> usize {
504                self.0.one_more()
505            }
506
507            /// Decode this value from the bytes given using the native endian
508            /// byte order for the current target.
509            ///
510            /// If the decoded integer is not representable as a small index
511            /// for the current target, then this returns an error.
512            #[inline]
513            pub fn from_ne_bytes(bytes: [u8; 4]) -> Result<$name, $err> {
514                SmallIndex::from_ne_bytes(bytes).map($name).map_err($err)
515            }
516
517            /// Decode this value from the bytes given using the native endian
518            /// byte order for the current target.
519            ///
520            /// This is analogous to `new_unchecked` in that is does not check
521            /// whether the decoded integer is representable as a small index.
522            #[inline]
523            pub fn from_ne_bytes_unchecked(bytes: [u8; 4]) -> $name {
524                $name(SmallIndex::from_ne_bytes_unchecked(bytes))
525            }
526
527            /// Return the underlying integer as raw bytes in native endian
528            /// format.
529            #[inline]
530            pub fn to_ne_bytes(&self) -> [u8; 4] {
531                self.0.to_ne_bytes()
532            }
533
534            /// Returns an iterator over all values from 0 up to and not
535            /// including the given length.
536            ///
537            /// If the given length exceeds this type's limit, then this
538            /// panics.
539            pub(crate) fn iter(len: usize) -> $iter {
540                $iter::new(len)
541            }
542        }
543
544        // We write our own Debug impl so that we get things like PatternID(5)
545        // instead of PatternID(SmallIndex(5)).
546        impl core::fmt::Debug for $name {
547            fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
548                f.debug_tuple(stringify!($name)).field(&self.as_u32()).finish()
549            }
550        }
551
552        impl<T> core::ops::Index<$name> for [T] {
553            type Output = T;
554
555            #[inline]
556            fn index(&self, index: $name) -> &T {
557                &self[index.as_usize()]
558            }
559        }
560
561        impl<T> core::ops::IndexMut<$name> for [T] {
562            #[inline]
563            fn index_mut(&mut self, index: $name) -> &mut T {
564                &mut self[index.as_usize()]
565            }
566        }
567
568        #[cfg(feature = "alloc")]
569        impl<T> core::ops::Index<$name> for Vec<T> {
570            type Output = T;
571
572            #[inline]
573            fn index(&self, index: $name) -> &T {
574                &self[index.as_usize()]
575            }
576        }
577
578        #[cfg(feature = "alloc")]
579        impl<T> core::ops::IndexMut<$name> for Vec<T> {
580            #[inline]
581            fn index_mut(&mut self, index: $name) -> &mut T {
582                &mut self[index.as_usize()]
583            }
584        }
585
586        impl From<u8> for $name {
587            fn from(value: u8) -> $name {
588                $name(SmallIndex::from(value))
589            }
590        }
591
592        impl TryFrom<u16> for $name {
593            type Error = $err;
594
595            fn try_from(value: u16) -> Result<$name, $err> {
596                SmallIndex::try_from(value).map($name).map_err($err)
597            }
598        }
599
600        impl TryFrom<u32> for $name {
601            type Error = $err;
602
603            fn try_from(value: u32) -> Result<$name, $err> {
604                SmallIndex::try_from(value).map($name).map_err($err)
605            }
606        }
607
608        impl TryFrom<u64> for $name {
609            type Error = $err;
610
611            fn try_from(value: u64) -> Result<$name, $err> {
612                SmallIndex::try_from(value).map($name).map_err($err)
613            }
614        }
615
616        impl TryFrom<usize> for $name {
617            type Error = $err;
618
619            fn try_from(value: usize) -> Result<$name, $err> {
620                SmallIndex::try_from(value).map($name).map_err($err)
621            }
622        }
623
624        #[cfg(test)]
625        impl quickcheck::Arbitrary for $name {
626            fn arbitrary(gen: &mut quickcheck::Gen) -> $name {
627                $name(SmallIndex::arbitrary(gen))
628            }
629        }
630
631        /// This error occurs when a value could not be constructed.
632        ///
633        /// This occurs when given an integer exceeding the maximum allowed
634        /// value.
635        ///
636        /// When the `std` feature is enabled, this implements the `Error`
637        /// trait.
638        #[derive(Clone, Debug, Eq, PartialEq)]
639        pub struct $err(SmallIndexError);
640
641        impl $err {
642            /// Returns the value that could not be converted to an ID.
643            pub fn attempted(&self) -> u64 {
644                self.0.attempted()
645            }
646        }
647
648        #[cfg(feature = "std")]
649        impl std::error::Error for $err {}
650
651        impl core::fmt::Display for $err {
652            fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
653                write!(
654                    f,
655                    "failed to create {} from {:?}, which exceeds {:?}",
656                    stringify!($name),
657                    self.attempted(),
658                    $name::MAX,
659                )
660            }
661        }
662
663        #[derive(Clone, Debug)]
664        pub(crate) struct $iter(SmallIndexIter);
665
666        impl $iter {
667            fn new(len: usize) -> $iter {
668                assert!(
669                    len <= $name::LIMIT,
670                    "cannot create iterator for {} when number of \
671                     elements exceed {:?}",
672                    stringify!($name),
673                    $name::LIMIT,
674                );
675                $iter(SmallIndexIter { rng: 0..len })
676            }
677        }
678
679        impl Iterator for $iter {
680            type Item = $name;
681
682            fn next(&mut self) -> Option<$name> {
683                self.0.next().map($name)
684            }
685        }
686
687        /// An iterator adapter that is like std::iter::Enumerate, but attaches
688        /// small index values instead. It requires `ExactSizeIterator`. At
689        /// construction, it ensures that the index of each element in the
690        /// iterator is representable in the corresponding small index type.
691        #[derive(Clone, Debug)]
692        pub(crate) struct $withiter<I> {
693            it: I,
694            ids: $iter,
695        }
696
697        impl<I: Iterator + ExactSizeIterator> $withiter<I> {
698            fn new(it: I) -> $withiter<I> {
699                let ids = $name::iter(it.len());
700                $withiter { it, ids }
701            }
702        }
703
704        impl<I: Iterator + ExactSizeIterator> Iterator for $withiter<I> {
705            type Item = ($name, I::Item);
706
707            fn next(&mut self) -> Option<($name, I::Item)> {
708                let item = self.it.next()?;
709                // Number of elements in this iterator must match, according
710                // to contract of ExactSizeIterator.
711                let id = self.ids.next().unwrap();
712                Some((id, item))
713            }
714        }
715    };
716}
717
718/// The identifier of a regex pattern, represented by a [`SmallIndex`].
719///
720/// The identifier for a pattern corresponds to its relative position among
721/// other patterns in a single finite state machine. Namely, when building
722/// a multi-pattern regex engine, one must supply a sequence of patterns to
723/// match. The position (starting at 0) of each pattern in that sequence
724/// represents its identifier. This identifier is in turn used to identify and
725/// report matches of that pattern in various APIs.
726///
727/// See the [`SmallIndex`] type for more information about what it means for
728/// a pattern ID to be a "small index."
729///
730/// Note that this type is defined in the
731/// [`util::primitives`](crate::util::primitives) module, but it is also
732/// re-exported at the crate root due to how common it is.
733#[derive(Clone, Copy, Default, Eq, Hash, PartialEq, PartialOrd, Ord)]
734#[repr(transparent)]
735pub struct PatternID(SmallIndex);
736
737/// The identifier of a finite automaton state, represented by a
738/// [`SmallIndex`].
739///
740/// Most regex engines in this crate are built on top of finite automata. Each
741/// state in a finite automaton defines transitions from its state to another.
742/// Those transitions point to other states via their identifiers, i.e., a
743/// `StateID`. Since finite automata tend to contain many transitions, it is
744/// much more memory efficient to define state IDs as small indices.
745///
746/// See the [`SmallIndex`] type for more information about what it means for
747/// a state ID to be a "small index."
748#[derive(Clone, Copy, Default, Eq, Hash, PartialEq, PartialOrd, Ord)]
749#[repr(transparent)]
750pub struct StateID(SmallIndex);
751
752index_type_impls!(PatternID, PatternIDError, PatternIDIter, WithPatternIDIter);
753index_type_impls!(StateID, StateIDError, StateIDIter, WithStateIDIter);
754
755/// A utility trait that defines a couple of adapters for making it convenient
756/// to access indices as "small index" types. We require ExactSizeIterator so
757/// that iterator construction can do a single check to make sure the index of
758/// each element is representable by its small index type.
759pub(crate) trait IteratorIndexExt: Iterator {
760    fn with_pattern_ids(self) -> WithPatternIDIter<Self>
761    where
762        Self: Sized + ExactSizeIterator,
763    {
764        WithPatternIDIter::new(self)
765    }
766
767    fn with_state_ids(self) -> WithStateIDIter<Self>
768    where
769        Self: Sized + ExactSizeIterator,
770    {
771        WithStateIDIter::new(self)
772    }
773}
774
775impl<I: Iterator> IteratorIndexExt for I {}