summaryrefslogtreecommitdiffstats
path: root/vendor/regex-automata/src/dfa/accel.rs
blob: c0ba18ea89621b0947ef113861ed8af79a8bfc4a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
// This module defines some core types for dealing with accelerated DFA states.
// Briefly, a DFA state can be "accelerated" if all of its transitions except
// for a few loop back to itself. This directly implies that the only way out
// of such a state is if a byte corresponding to one of those non-loopback
// transitions is found. Such states are often found in simple repetitions in
// non-Unicode regexes. For example, consider '(?-u)[^a]+a'. We can look at its
// DFA with regex-cli:
//
//     $ regex-cli debug dense dfa -p '(?-u)[^a]+a' -BbC --no-table
//     D 000000:
//     Q 000001:
//      *000002:
//     A 000003: \x00-` => 3, a => 8, b-\xFF => 3
//     A 000004: \x00-` => 4, a => 7, b-\xFF => 4
//       000005: \x00-` => 4, b-\xFF => 4
//       000006: \x00-` => 3, a => 6, b-\xFF => 3
//       000007: \x00-\xFF => 2, EOI => 2
//       000008: \x00-\xFF => 2, EOI => 2
//
// In particular, state 3 is accelerated (shown via the 'A' indicator) since
// the only way to leave that state once entered is to see an 'a' byte. If
// there is a long run of non-'a' bytes, then using something like 'memchr'
// to find the next 'a' byte can be significantly faster than just using the
// standard byte-at-a-time state machine.
//
// Unfortunately, this optimization rarely applies when Unicode is enabled.
// For example, patterns like '[^a]' don't actually match any byte that isn't
// 'a', but rather, any UTF-8 encoding of a Unicode scalar value that isn't
// 'a'. This makes the state machine much more complex---far beyond a single
// state---and removes the ability to easily accelerate it. (Because if the
// machine sees a non-UTF-8 sequence, then the machine won't match through it.)
//
// In practice, we only consider accelerating states that have 3 or fewer
// non-loop transitions. At a certain point, you get diminishing returns, but
// also because that's what the memchr crate supports. The structures below
// hard-code this assumption and provide (de)serialization APIs for use inside
// a DFA.
//
// And finally, note that there is some trickery involved in making it very
// fast to not only check whether a state is accelerated at search time, but
// also to access the bytes to search for to implement the acceleration itself.
// dfa/special.rs provides more detail, but the short story is that all
// accelerated states appear contiguously in a DFA. This means we can represent
// the ID space of all accelerated DFA states with a single range. So given
// a state ID, we can determine whether it's accelerated via
//
//     min_accel_id <= id <= max_accel_id
//
// And find its corresponding accelerator with:
//
//     accels.get((id - min_accel_id) / dfa_stride)

#[cfg(feature = "dfa-build")]
use alloc::{vec, vec::Vec};

use crate::util::{
    int::Pointer,
    memchr,
    wire::{self, DeserializeError, Endian, SerializeError},
};

/// The base type used to represent a collection of accelerators.
///
/// While an `Accel` is represented as a fixed size array of bytes, a
/// *collection* of `Accel`s (called `Accels`) is represented internally as a
/// slice of u32. While it's a bit unnatural to do this and costs us a bit of
/// fairly low-risk not-safe code, it lets us remove the need for a second type
/// parameter in the definition of dense::DFA. (Which really wants everything
/// to be a slice of u32.)
type AccelTy = u32;

/// The size of the unit of representation for accelerators.
///
/// ACCEL_CAP *must* be a multiple of this size.
const ACCEL_TY_SIZE: usize = core::mem::size_of::<AccelTy>();

/// The maximum length in bytes that a single Accel can be. This is distinct
/// from the capacity of an accelerator in that the length represents only the
/// bytes that should be read.
const ACCEL_LEN: usize = 4;

/// The capacity of each accelerator, in bytes. We set this to 8 since it's a
/// multiple of 4 (our ID size) and because it gives us a little wiggle room
/// if we want to support more accel bytes in the future without a breaking
/// change.
///
/// This MUST be a multiple of ACCEL_TY_SIZE.
const ACCEL_CAP: usize = 8;

/// Search for between 1 and 3 needle bytes in the given haystack, starting the
/// search at the given position. If `needles` has a length other than 1-3,
/// then this panics.
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn find_fwd(
    needles: &[u8],
    haystack: &[u8],
    at: usize,
) -> Option<usize> {
    let bs = needles;
    let i = match needles.len() {
        1 => memchr::memchr(bs[0], &haystack[at..])?,
        2 => memchr::memchr2(bs[0], bs[1], &haystack[at..])?,
        3 => memchr::memchr3(bs[0], bs[1], bs[2], &haystack[at..])?,
        0 => panic!("cannot find with empty needles"),
        n => panic!("invalid needles length: {}", n),
    };
    Some(at + i)
}

/// Search for between 1 and 3 needle bytes in the given haystack in reverse,
/// starting the search at the given position. If `needles` has a length other
/// than 1-3, then this panics.
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn find_rev(
    needles: &[u8],
    haystack: &[u8],
    at: usize,
) -> Option<usize> {
    let bs = needles;
    match needles.len() {
        1 => memchr::memrchr(bs[0], &haystack[..at]),
        2 => memchr::memrchr2(bs[0], bs[1], &haystack[..at]),
        3 => memchr::memrchr3(bs[0], bs[1], bs[2], &haystack[..at]),
        0 => panic!("cannot find with empty needles"),
        n => panic!("invalid needles length: {}", n),
    }
}

/// Represents the accelerators for all accelerated states in a dense DFA.
///
/// The `A` type parameter represents the type of the underlying bytes.
/// Generally, this is either `&[AccelTy]` or `Vec<AccelTy>`.
#[derive(Clone)]
pub(crate) struct Accels<A> {
    /// A length prefixed slice of contiguous accelerators. See the top comment
    /// in this module for more details on how we can jump from a DFA's state
    /// ID to an accelerator in this list.
    ///
    /// The first 4 bytes always correspond to the number of accelerators
    /// that follow.
    accels: A,
}

#[cfg(feature = "dfa-build")]
impl Accels<Vec<AccelTy>> {
    /// Create an empty sequence of accelerators for a DFA.
    pub fn empty() -> Accels<Vec<AccelTy>> {
        Accels { accels: vec![0] }
    }

    /// Add an accelerator to this sequence.
    ///
    /// This adds to the accelerator to the end of the sequence and therefore
    /// should be done in correspondence with its state in the DFA.
    ///
    /// This panics if this results in more accelerators than AccelTy::MAX.
    pub fn add(&mut self, accel: Accel) {
        self.accels.extend_from_slice(&accel.as_accel_tys());
        let len = self.len();
        self.set_len(len + 1);
    }

    /// Set the number of accelerators in this sequence, which is encoded in
    /// the first 4 bytes of the underlying bytes.
    fn set_len(&mut self, new_len: usize) {
        // The only way an accelerator gets added is if a state exists for
        // it, and if a state exists, then its index is guaranteed to be
        // representable by a AccelTy by virtue of the guarantees provided by
        // StateID.
        let new_len = AccelTy::try_from(new_len).unwrap();
        self.accels[0] = new_len;
    }
}

impl<'a> Accels<&'a [AccelTy]> {
    /// Deserialize a sequence of accelerators from the given bytes. If there
    /// was a problem deserializing, then an error is returned.
    ///
    /// This is guaranteed to run in constant time. This does not guarantee
    /// that every accelerator in the returned collection is valid. Thus,
    /// accessing one may panic, or not-safe code that relies on accelerators
    /// being correct my result in UB.
    ///
    /// Callers may check the validity of every accelerator with the `validate`
    /// method.
    pub fn from_bytes_unchecked(
        mut slice: &'a [u8],
    ) -> Result<(Accels<&'a [AccelTy]>, usize), DeserializeError> {
        let slice_start = slice.as_ptr().as_usize();

        let (accel_len, _) =
            wire::try_read_u32_as_usize(slice, "accelerators length")?;
        // The accelerator length is part of the accel_tys slice that
        // we deserialize. This is perhaps a bit idiosyncratic. It would
        // probably be better to split out the length into a real field.

        let accel_tys_len = wire::add(
            wire::mul(accel_len, 2, "total number of accelerator accel_tys")?,
            1,
            "total number of accel_tys",
        )?;
        let accel_tys_bytes_len = wire::mul(
            ACCEL_TY_SIZE,
            accel_tys_len,
            "total number of bytes in accelerators",
        )?;
        wire::check_slice_len(slice, accel_tys_bytes_len, "accelerators")?;
        wire::check_alignment::<AccelTy>(slice)?;
        let accel_tys = &slice[..accel_tys_bytes_len];
        slice = &slice[accel_tys_bytes_len..];
        // SAFETY: We've checked the length and alignment above, and since
        // slice is just bytes and AccelTy is just a u32, we can safely cast to
        // a slice of &[AccelTy].
        let accels = unsafe {
            core::slice::from_raw_parts(
                accel_tys.as_ptr().cast::<AccelTy>(),
                accel_tys_len,
            )
        };
        Ok((Accels { accels }, slice.as_ptr().as_usize() - slice_start))
    }
}

impl<A: AsRef<[AccelTy]>> Accels<A> {
    /// Return an owned version of the accelerators.
    #[cfg(feature = "alloc")]
    pub fn to_owned(&self) -> Accels<alloc::vec::Vec<AccelTy>> {
        Accels { accels: self.accels.as_ref().to_vec() }
    }

    /// Return a borrowed version of the accelerators.
    pub fn as_ref(&self) -> Accels<&[AccelTy]> {
        Accels { accels: self.accels.as_ref() }
    }

    /// Return the bytes representing the serialization of the accelerators.
    pub fn as_bytes(&self) -> &[u8] {
        let accels = self.accels.as_ref();
        // SAFETY: This is safe because accels is a just a slice of AccelTy,
        // and u8 always has a smaller alignment.
        unsafe {
            core::slice::from_raw_parts(
                accels.as_ptr().cast::<u8>(),
                accels.len() * ACCEL_TY_SIZE,
            )
        }
    }

    /// Returns the memory usage, in bytes, of these accelerators.
    ///
    /// The memory usage is computed based on the number of bytes used to
    /// represent all of the accelerators.
    ///
    /// This does **not** include the stack size used by this value.
    pub fn memory_usage(&self) -> usize {
        self.as_bytes().len()
    }

    /// Return the bytes to search for corresponding to the accelerator in this
    /// sequence at index `i`. If no such accelerator exists, then this panics.
    ///
    /// The significance of the index is that it should be in correspondence
    /// with the index of the corresponding DFA. That is, accelerated DFA
    /// states are stored contiguously in the DFA and have an ordering implied
    /// by their respective state IDs. The state's index in that sequence
    /// corresponds to the index of its corresponding accelerator.
    #[cfg_attr(feature = "perf-inline", inline(always))]
    pub fn needles(&self, i: usize) -> &[u8] {
        if i >= self.len() {
            panic!("invalid accelerator index {}", i);
        }
        let bytes = self.as_bytes();
        let offset = ACCEL_TY_SIZE + i * ACCEL_CAP;
        let len = usize::from(bytes[offset]);
        &bytes[offset + 1..offset + 1 + len]
    }

    /// Return the total number of accelerators in this sequence.
    pub fn len(&self) -> usize {
        // This should never panic since deserialization checks that the
        // length can fit into a usize.
        usize::try_from(self.accels.as_ref()[0]).unwrap()
    }

    /// Return the accelerator in this sequence at index `i`. If no such
    /// accelerator exists, then this returns None.
    ///
    /// See the docs for `needles` on the significance of the index.
    fn get(&self, i: usize) -> Option<Accel> {
        if i >= self.len() {
            return None;
        }
        let offset = ACCEL_TY_SIZE + i * ACCEL_CAP;
        let accel = Accel::from_slice(&self.as_bytes()[offset..])
            .expect("Accels must contain valid accelerators");
        Some(accel)
    }

    /// Returns an iterator of accelerators in this sequence.
    fn iter(&self) -> IterAccels<'_, A> {
        IterAccels { accels: self, i: 0 }
    }

    /// Writes these accelerators to the given byte buffer using the indicated
    /// endianness. If the given buffer is too small, then an error is
    /// returned. Upon success, the total number of bytes written is returned.
    /// The number of bytes written is guaranteed to be a multiple of 8.
    pub fn write_to<E: Endian>(
        &self,
        dst: &mut [u8],
    ) -> Result<usize, SerializeError> {
        let nwrite = self.write_to_len();
        assert_eq!(
            nwrite % ACCEL_TY_SIZE,
            0,
            "expected accelerator bytes written to be a multiple of {}",
            ACCEL_TY_SIZE,
        );
        if dst.len() < nwrite {
            return Err(SerializeError::buffer_too_small("accelerators"));
        }

        // The number of accelerators can never exceed AccelTy::MAX.
        E::write_u32(AccelTy::try_from(self.len()).unwrap(), dst);
        // The actual accelerators are just raw bytes and thus their endianness
        // is irrelevant. So we can copy them as bytes.
        dst[ACCEL_TY_SIZE..nwrite]
            .copy_from_slice(&self.as_bytes()[ACCEL_TY_SIZE..nwrite]);
        Ok(nwrite)
    }

    /// Validates that every accelerator in this collection can be successfully
    /// deserialized as a valid accelerator.
    pub fn validate(&self) -> Result<(), DeserializeError> {
        for chunk in self.as_bytes()[ACCEL_TY_SIZE..].chunks(ACCEL_CAP) {
            let _ = Accel::from_slice(chunk)?;
        }
        Ok(())
    }

    /// Returns the total number of bytes written by `write_to`.
    pub fn write_to_len(&self) -> usize {
        self.as_bytes().len()
    }
}

impl<A: AsRef<[AccelTy]>> core::fmt::Debug for Accels<A> {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        write!(f, "Accels(")?;
        let mut list = f.debug_list();
        for a in self.iter() {
            list.entry(&a);
        }
        list.finish()?;
        write!(f, ")")
    }
}

#[derive(Debug)]
struct IterAccels<'a, A: AsRef<[AccelTy]>> {
    accels: &'a Accels<A>,
    i: usize,
}

impl<'a, A: AsRef<[AccelTy]>> Iterator for IterAccels<'a, A> {
    type Item = Accel;

    fn next(&mut self) -> Option<Accel> {
        let accel = self.accels.get(self.i)?;
        self.i += 1;
        Some(accel)
    }
}

/// Accel represents a structure for determining how to "accelerate" a DFA
/// state.
///
/// Namely, it contains zero or more bytes that must be seen in order for the
/// DFA to leave the state it is associated with. In practice, the actual range
/// is 1 to 3 bytes.
///
/// The purpose of acceleration is to identify states whose vast majority
/// of transitions are just loops back to the same state. For example,
/// in the regex `(?-u)^[^a]+b`, the corresponding DFA will have a state
/// (corresponding to `[^a]+`) where all transitions *except* for `a` and
/// `b` loop back to itself. Thus, this state can be "accelerated" by simply
/// looking for the next occurrence of either `a` or `b` instead of explicitly
/// following transitions. (In this case, `b` transitions to the next state
/// where as `a` would transition to the dead state.)
#[derive(Clone)]
pub(crate) struct Accel {
    /// The first byte is the length. Subsequent bytes are the accelerated
    /// bytes.
    ///
    /// Note that we make every accelerator 8 bytes as a slightly wasteful
    /// way of making sure alignment is always correct for state ID sizes of
    /// 1, 2, 4 and 8. This should be okay since accelerated states aren't
    /// particularly common, especially when Unicode is enabled.
    bytes: [u8; ACCEL_CAP],
}

impl Accel {
    /// Returns an empty accel, where no bytes are accelerated.
    #[cfg(feature = "dfa-build")]
    pub fn new() -> Accel {
        Accel { bytes: [0; ACCEL_CAP] }
    }

    /// Returns a verified accelerator derived from the beginning of the given
    /// slice.
    ///
    /// If the slice is not long enough or contains invalid bytes for an
    /// accelerator, then this returns an error.
    pub fn from_slice(mut slice: &[u8]) -> Result<Accel, DeserializeError> {
        slice = &slice[..core::cmp::min(ACCEL_LEN, slice.len())];
        let bytes = slice
            .try_into()
            .map_err(|_| DeserializeError::buffer_too_small("accelerator"))?;
        Accel::from_bytes(bytes)
    }

    /// Returns a verified accelerator derived from raw bytes.
    ///
    /// If the given bytes are invalid, then this returns an error.
    fn from_bytes(bytes: [u8; 4]) -> Result<Accel, DeserializeError> {
        if usize::from(bytes[0]) >= ACCEL_LEN {
            return Err(DeserializeError::generic(
                "accelerator bytes cannot have length more than 3",
            ));
        }
        Ok(Accel::from_bytes_unchecked(bytes))
    }

    /// Returns an accelerator derived from raw bytes.
    ///
    /// This does not check whether the given bytes are valid. Invalid bytes
    /// cannot sacrifice memory safety, but may result in panics or silent
    /// logic bugs.
    fn from_bytes_unchecked(bytes: [u8; 4]) -> Accel {
        Accel { bytes: [bytes[0], bytes[1], bytes[2], bytes[3], 0, 0, 0, 0] }
    }

    /// Attempts to add the given byte to this accelerator. If the accelerator
    /// is already full or thinks the byte is a poor accelerator, then this
    /// returns false. Otherwise, returns true.
    ///
    /// If the given byte is already in this accelerator, then it panics.
    #[cfg(feature = "dfa-build")]
    pub fn add(&mut self, byte: u8) -> bool {
        if self.len() >= 3 {
            return false;
        }
        // As a special case, we totally reject trying to accelerate a state
        // with an ASCII space. In most cases, it occurs very frequently, and
        // tends to result in worse overall performance.
        if byte == b' ' {
            return false;
        }
        assert!(
            !self.contains(byte),
            "accelerator already contains {:?}",
            crate::util::escape::DebugByte(byte)
        );
        self.bytes[self.len() + 1] = byte;
        self.bytes[0] += 1;
        true
    }

    /// Return the number of bytes in this accelerator.
    pub fn len(&self) -> usize {
        usize::from(self.bytes[0])
    }

    /// Returns true if and only if there are no bytes in this accelerator.
    #[cfg(feature = "dfa-build")]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns the slice of bytes to accelerate.
    ///
    /// If this accelerator is empty, then this returns an empty slice.
    fn needles(&self) -> &[u8] {
        &self.bytes[1..1 + self.len()]
    }

    /// Returns true if and only if this accelerator will accelerate the given
    /// byte.
    #[cfg(feature = "dfa-build")]
    fn contains(&self, byte: u8) -> bool {
        self.needles().iter().position(|&b| b == byte).is_some()
    }

    /// Returns the accelerator bytes as an array of AccelTys.
    #[cfg(feature = "dfa-build")]
    fn as_accel_tys(&self) -> [AccelTy; 2] {
        assert_eq!(ACCEL_CAP, 8);
        // These unwraps are OK since ACCEL_CAP is set to 8.
        let first =
            AccelTy::from_ne_bytes(self.bytes[0..4].try_into().unwrap());
        let second =
            AccelTy::from_ne_bytes(self.bytes[4..8].try_into().unwrap());
        [first, second]
    }
}

impl core::fmt::Debug for Accel {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        write!(f, "Accel(")?;
        let mut set = f.debug_set();
        for &b in self.needles() {
            set.entry(&crate::util::escape::DebugByte(b));
        }
        set.finish()?;
        write!(f, ")")
    }
}