| 1 |
/*! |
| 2 |
This module provides APIs for dealing with the alphabets of finite state |
| 3 |
machines. |
| 4 |
|
| 5 |
There are two principal types in this module, [`ByteClasses`] and [`Unit`]. |
| 6 |
The former defines the alphabet of a finite state machine while the latter |
| 7 |
represents an element of that alphabet. |
| 8 |
|
| 9 |
To a first approximation, the alphabet of all automata in this crate is just |
| 10 |
a `u8`. Namely, every distinct byte value. All 256 of them. In practice, this |
| 11 |
can be quite wasteful when building a transition table for a DFA, since it |
| 12 |
requires storing a state identifier for each element in the alphabet. Instead, |
| 13 |
we collapse the alphabet of an automaton down into equivalence classes, where |
| 14 |
every byte in the same equivalence class never discriminates between a match or |
| 15 |
a non-match from any other byte in the same class. For example, in the regex |
| 16 |
`[a-z]+`, then you could consider it having an alphabet consisting of two |
| 17 |
equivalence classes: `a-z` and everything else. In terms of the transitions on |
| 18 |
an automaton, it doesn't actually require representing every distinct byte. |
| 19 |
Just the equivalence classes. |
| 20 |
|
| 21 |
The downside of equivalence classes is that, of course, searching a haystack |
| 22 |
deals with individual byte values. Those byte values need to be mapped to |
| 23 |
their corresponding equivalence class. This is what `ByteClasses` does. In |
| 24 |
practice, doing this for every state transition has negligible impact on modern |
| 25 |
CPUs. Moreover, it helps make more efficient use of the CPU cache by (possibly |
| 26 |
considerably) shrinking the size of the transition table. |
| 27 |
|
| 28 |
One last hiccup concerns `Unit`. Namely, because of look-around and how the |
| 29 |
DFAs in this crate work, we need to add a sentinel value to our alphabet |
| 30 |
of equivalence classes that represents the "end" of a search. We call that |
| 31 |
sentinel [`Unit::eoi`] or "end of input." Thus, a `Unit` is either an |
| 32 |
equivalence class corresponding to a set of bytes, or it is a special "end of |
| 33 |
input" sentinel. |
| 34 |
|
| 35 |
In general, you should not expect to need either of these types unless you're |
| 36 |
doing lower level shenanigans with DFAs, or even building your own DFAs. |
| 37 |
(Although, you don't have to use these types to build your own DFAs of course.) |
| 38 |
For example, if you're walking a DFA's state graph, it's probably useful to |
| 39 |
make use of [`ByteClasses`] to visit each element in the DFA's alphabet instead |
| 40 |
of just visiting every distinct `u8` value. The latter isn't necessarily wrong, |
| 41 |
but it could be potentially very wasteful. |
| 42 |
*/ |
| 43 |
use crate::util::{ |
| 44 |
escape::DebugByte, |
| 45 |
wire::{self, DeserializeError, SerializeError}, |
| 46 |
}; |
| 47 |
|
| 48 |
/// Unit represents a single unit of haystack for DFA based regex engines. |
| 49 |
/// |
| 50 |
/// It is not expected for consumers of this crate to need to use this type |
| 51 |
/// unless they are implementing their own DFA. And even then, it's not |
| 52 |
/// required: implementors may use other techniques to handle haystack units. |
| 53 |
/// |
| 54 |
/// Typically, a single unit of haystack for a DFA would be a single byte. |
| 55 |
/// However, for the DFAs in this crate, matches are delayed by a single byte |
| 56 |
/// in order to handle look-ahead assertions (`\b`, `$` and `\z`). Thus, once |
| 57 |
/// we have consumed the haystack, we must run the DFA through one additional |
| 58 |
/// transition using a unit that indicates the haystack has ended. |
| 59 |
/// |
| 60 |
/// There is no way to represent a sentinel with a `u8` since all possible |
| 61 |
/// values *may* be valid haystack units to a DFA, therefore this type |
| 62 |
/// explicitly adds room for a sentinel value. |
| 63 |
/// |
| 64 |
/// The sentinel EOI value is always its own equivalence class and is |
| 65 |
/// ultimately represented by adding 1 to the maximum equivalence class value. |
| 66 |
/// So for example, the regex `^[a-z]+$` might be split into the following |
| 67 |
/// equivalence classes: |
| 68 |
/// |
| 69 |
/// ```text |
| 70 |
/// 0 => [\x00-`] |
| 71 |
/// 1 => [a-z] |
| 72 |
/// 2 => [{-\xFF] |
| 73 |
/// 3 => [EOI] |
| 74 |
/// ``` |
| 75 |
/// |
| 76 |
/// Where EOI is the special sentinel value that is always in its own |
| 77 |
/// singleton equivalence class. |
| 78 |
#[derive(Clone, Copy, Eq, PartialEq, PartialOrd, Ord)] |
| 79 |
pub struct Unit(UnitKind); |
| 80 |
|
| 81 |
#[derive(Clone, Copy, Eq, PartialEq, PartialOrd, Ord)] |
| 82 |
enum UnitKind { |
| 83 |
/// Represents a byte value, or more typically, an equivalence class |
| 84 |
/// represented as a byte value. |
| 85 |
U8(u8), |
| 86 |
/// Represents the "end of input" sentinel. We regretably use a `u16` |
| 87 |
/// here since the maximum sentinel value is `256`. Thankfully, we don't |
| 88 |
/// actually store a `Unit` anywhere, so this extra space shouldn't be too |
| 89 |
/// bad. |
| 90 |
EOI(u16), |
| 91 |
} |
| 92 |
|
| 93 |
impl Unit { |
| 94 |
/// Create a new haystack unit from a byte value. |
| 95 |
/// |
| 96 |
/// All possible byte values are legal. However, when creating a haystack |
| 97 |
/// unit for a specific DFA, one should be careful to only construct units |
| 98 |
/// that are in that DFA's alphabet. Namely, one way to compact a DFA's |
| 99 |
/// in-memory representation is to collapse its transitions to a set of |
| 100 |
/// equivalence classes into a set of all possible byte values. If a DFA |
| 101 |
/// uses equivalence classes instead of byte values, then the byte given |
| 102 |
/// here should be the equivalence class. |
| 103 |
pub fn u8(byte: u8) -> Unit { |
| 104 |
Unit(UnitKind::U8(byte)) |
| 105 |
} |
| 106 |
|
| 107 |
/// Create a new "end of input" haystack unit. |
| 108 |
/// |
| 109 |
/// The value given is the sentinel value used by this unit to represent |
| 110 |
/// the "end of input." The value should be the total number of equivalence |
| 111 |
/// classes in the corresponding alphabet. Its maximum value is `256`, |
| 112 |
/// which occurs when every byte is its own equivalence class. |
| 113 |
/// |
| 114 |
/// # Panics |
| 115 |
/// |
| 116 |
/// This panics when `num_byte_equiv_classes` is greater than `256`. |
| 117 |
pub fn eoi(num_byte_equiv_classes: usize) -> Unit { |
| 118 |
assert!( |
| 119 |
num_byte_equiv_classes <= 256, |
| 120 |
"max number of byte-based equivalent classes is 256, but got {}", |
| 121 |
num_byte_equiv_classes, |
| 122 |
); |
| 123 |
Unit(UnitKind::EOI(u16::try_from(num_byte_equiv_classes).unwrap())) |
| 124 |
} |
| 125 |
|
| 126 |
/// If this unit is not an "end of input" sentinel, then returns its |
| 127 |
/// underlying byte value. Otherwise return `None`. |
| 128 |
pub fn as_u8(self) -> Option<u8> { |
| 129 |
match self.0 { |
| 130 |
UnitKind::U8(b) => Some(b), |
| 131 |
UnitKind::EOI(_) => None, |
| 132 |
} |
| 133 |
} |
| 134 |
|
| 135 |
/// If this unit is an "end of input" sentinel, then return the underlying |
| 136 |
/// sentinel value that was given to [`Unit::eoi`]. Otherwise return |
| 137 |
/// `None`. |
| 138 |
pub fn as_eoi(self) -> Option<u16> { |
| 139 |
match self.0 { |
| 140 |
UnitKind::U8(_) => None, |
| 141 |
UnitKind::EOI(sentinel) => Some(sentinel), |
| 142 |
} |
| 143 |
} |
| 144 |
|
| 145 |
/// Return this unit as a `usize`, regardless of whether it is a byte value |
| 146 |
/// or an "end of input" sentinel. In the latter case, the underlying |
| 147 |
/// sentinel value given to [`Unit::eoi`] is returned. |
| 148 |
pub fn as_usize(self) -> usize { |
| 149 |
match self.0 { |
| 150 |
UnitKind::U8(b) => usize::from(b), |
| 151 |
UnitKind::EOI(eoi) => usize::from(eoi), |
| 152 |
} |
| 153 |
} |
| 154 |
|
| 155 |
/// Returns true if and only of this unit is a byte value equivalent to the |
| 156 |
/// byte given. This always returns false when this is an "end of input" |
| 157 |
/// sentinel. |
| 158 |
pub fn is_byte(self, byte: u8) -> bool { |
| 159 |
self.as_u8().map_or(false, |b| b == byte) |
| 160 |
} |
| 161 |
|
| 162 |
/// Returns true when this unit represents an "end of input" sentinel. |
| 163 |
pub fn is_eoi(self) -> bool { |
| 164 |
self.as_eoi().is_some() |
| 165 |
} |
| 166 |
|
| 167 |
/// Returns true when this unit corresponds to an ASCII word byte. |
| 168 |
/// |
| 169 |
/// This always returns false when this unit represents an "end of input" |
| 170 |
/// sentinel. |
| 171 |
pub fn is_word_byte(self) -> bool { |
| 172 |
self.as_u8().map_or(false, crate::util::utf8::is_word_byte) |
| 173 |
} |
| 174 |
} |
| 175 |
|
| 176 |
impl core::fmt::Debug for Unit { |
| 177 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 178 |
match self.0 { |
| 179 |
UnitKind::U8(b) => write!(f, "{:?}", DebugByte(b)), |
| 180 |
UnitKind::EOI(_) => write!(f, "EOI"), |
| 181 |
} |
| 182 |
} |
| 183 |
} |
| 184 |
|
| 185 |
/// A representation of byte oriented equivalence classes. |
| 186 |
/// |
| 187 |
/// This is used in a DFA to reduce the size of the transition table. This can |
| 188 |
/// have a particularly large impact not only on the total size of a dense DFA, |
| 189 |
/// but also on compile times. |
| 190 |
/// |
| 191 |
/// The essential idea here is that the alphabet of a DFA is shrunk from the |
| 192 |
/// usual 256 distinct byte values down to a set of equivalence classes. The |
| 193 |
/// guarantee you get is that any byte belonging to the same equivalence class |
| 194 |
/// can be treated as if it were any other byte in the same class, and the |
| 195 |
/// result of a search wouldn't change. |
| 196 |
/// |
| 197 |
/// # Example |
| 198 |
/// |
| 199 |
/// This example shows how to get byte classes from an |
| 200 |
/// [`NFA`](crate::nfa::thompson::NFA) and ask for the class of various bytes. |
| 201 |
/// |
| 202 |
/// ``` |
| 203 |
/// use regex_automata::nfa::thompson::NFA; |
| 204 |
/// |
| 205 |
/// let nfa = NFA::new("[a-z]+")?; |
| 206 |
/// let classes = nfa.byte_classes(); |
| 207 |
/// // 'a' and 'z' are in the same class for this regex. |
| 208 |
/// assert_eq!(classes.get(b'a'), classes.get(b'z')); |
| 209 |
/// // But 'a' and 'A' are not. |
| 210 |
/// assert_ne!(classes.get(b'a'), classes.get(b'A')); |
| 211 |
/// |
| 212 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 213 |
/// ``` |
| 214 |
#[derive(Clone, Copy)] |
| 215 |
pub struct ByteClasses([u8; 256]); |
| 216 |
|
| 217 |
impl ByteClasses { |
| 218 |
/// Creates a new set of equivalence classes where all bytes are mapped to |
| 219 |
/// the same class. |
| 220 |
#[inline] |
| 221 |
pub fn empty() -> ByteClasses { |
| 222 |
ByteClasses([0; 256]) |
| 223 |
} |
| 224 |
|
| 225 |
/// Creates a new set of equivalence classes where each byte belongs to |
| 226 |
/// its own equivalence class. |
| 227 |
#[inline] |
| 228 |
pub fn singletons() -> ByteClasses { |
| 229 |
let mut classes = ByteClasses::empty(); |
| 230 |
for b in 0..=255 { |
| 231 |
classes.set(b, b); |
| 232 |
} |
| 233 |
classes |
| 234 |
} |
| 235 |
|
| 236 |
/// Deserializes a byte class map from the given slice. If the slice is of |
| 237 |
/// insufficient length or otherwise contains an impossible mapping, then |
| 238 |
/// an error is returned. Upon success, the number of bytes read along with |
| 239 |
/// the map are returned. The number of bytes read is always a multiple of |
| 240 |
/// 8. |
| 241 |
pub(crate) fn from_bytes( |
| 242 |
slice: &[u8], |
| 243 |
) -> Result<(ByteClasses, usize), DeserializeError> { |
| 244 |
wire::check_slice_len(slice, 256, "byte class map")?; |
| 245 |
let mut classes = ByteClasses::empty(); |
| 246 |
for (b, &class) in slice[..256].iter().enumerate() { |
| 247 |
classes.set(u8::try_from(b).unwrap(), class); |
| 248 |
} |
| 249 |
// We specifically don't use 'classes.iter()' here because that |
| 250 |
// iterator depends on 'classes.alphabet_len()' being correct. But that |
| 251 |
// is precisely the thing we're trying to verify below! |
| 252 |
for &b in classes.0.iter() { |
| 253 |
if usize::from(b) >= classes.alphabet_len() { |
| 254 |
return Err(DeserializeError::generic( |
| 255 |
"found equivalence class greater than alphabet len", |
| 256 |
)); |
| 257 |
} |
| 258 |
} |
| 259 |
Ok((classes, 256)) |
| 260 |
} |
| 261 |
|
| 262 |
/// Writes this byte class map to the given byte buffer. if the given |
| 263 |
/// buffer is too small, then an error is returned. Upon success, the total |
| 264 |
/// number of bytes written is returned. The number of bytes written is |
| 265 |
/// guaranteed to be a multiple of 8. |
| 266 |
pub(crate) fn write_to( |
| 267 |
&self, |
| 268 |
mut dst: &mut [u8], |
| 269 |
) -> Result<usize, SerializeError> { |
| 270 |
let nwrite = self.write_to_len(); |
| 271 |
if dst.len() < nwrite { |
| 272 |
return Err(SerializeError::buffer_too_small("byte class map")); |
| 273 |
} |
| 274 |
for b in 0..=255 { |
| 275 |
dst[0] = self.get(b); |
| 276 |
dst = &mut dst[1..]; |
| 277 |
} |
| 278 |
Ok(nwrite) |
| 279 |
} |
| 280 |
|
| 281 |
/// Returns the total number of bytes written by `write_to`. |
| 282 |
pub(crate) fn write_to_len(&self) -> usize { |
| 283 |
256 |
| 284 |
} |
| 285 |
|
| 286 |
/// Set the equivalence class for the given byte. |
| 287 |
#[inline] |
| 288 |
pub fn set(&mut self, byte: u8, class: u8) { |
| 289 |
self.0[usize::from(byte)] = class; |
| 290 |
} |
| 291 |
|
| 292 |
/// Get the equivalence class for the given byte. |
| 293 |
#[inline] |
| 294 |
pub fn get(&self, byte: u8) -> u8 { |
| 295 |
self.0[usize::from(byte)] |
| 296 |
} |
| 297 |
|
| 298 |
/// Get the equivalence class for the given haystack unit and return the |
| 299 |
/// class as a `usize`. |
| 300 |
#[inline] |
| 301 |
pub fn get_by_unit(&self, unit: Unit) -> usize { |
| 302 |
match unit.0 { |
| 303 |
UnitKind::U8(b) => usize::from(self.get(b)), |
| 304 |
UnitKind::EOI(b) => usize::from(b), |
| 305 |
} |
| 306 |
} |
| 307 |
|
| 308 |
/// Create a unit that represents the "end of input" sentinel based on the |
| 309 |
/// number of equivalence classes. |
| 310 |
#[inline] |
| 311 |
pub fn eoi(&self) -> Unit { |
| 312 |
// The alphabet length already includes the EOI sentinel, hence why |
| 313 |
// we subtract 1. |
| 314 |
Unit::eoi(self.alphabet_len().checked_sub(1).unwrap()) |
| 315 |
} |
| 316 |
|
| 317 |
/// Return the total number of elements in the alphabet represented by |
| 318 |
/// these equivalence classes. Equivalently, this returns the total number |
| 319 |
/// of equivalence classes. |
| 320 |
#[inline] |
| 321 |
pub fn alphabet_len(&self) -> usize { |
| 322 |
// Add one since the number of equivalence classes is one bigger than |
| 323 |
// the last one. But add another to account for the final EOI class |
| 324 |
// that isn't explicitly represented. |
| 325 |
usize::from(self.0[255]) + 1 + 1 |
| 326 |
} |
| 327 |
|
| 328 |
/// Returns the stride, as a base-2 exponent, required for these |
| 329 |
/// equivalence classes. |
| 330 |
/// |
| 331 |
/// The stride is always the smallest power of 2 that is greater than or |
| 332 |
/// equal to the alphabet length, and the `stride2` returned here is the |
| 333 |
/// exponent applied to `2` to get the smallest power. This is done so that |
| 334 |
/// converting between premultiplied state IDs and indices can be done with |
| 335 |
/// shifts alone, which is much faster than integer division. |
| 336 |
#[inline] |
| 337 |
pub fn stride2(&self) -> usize { |
| 338 |
let zeros = self.alphabet_len().next_power_of_two().trailing_zeros(); |
| 339 |
usize::try_from(zeros).unwrap() |
| 340 |
} |
| 341 |
|
| 342 |
/// Returns true if and only if every byte in this class maps to its own |
| 343 |
/// equivalence class. Equivalently, there are 257 equivalence classes |
| 344 |
/// and each class contains either exactly one byte or corresponds to the |
| 345 |
/// singleton class containing the "end of input" sentinel. |
| 346 |
#[inline] |
| 347 |
pub fn is_singleton(&self) -> bool { |
| 348 |
self.alphabet_len() == 257 |
| 349 |
} |
| 350 |
|
| 351 |
/// Returns an iterator over all equivalence classes in this set. |
| 352 |
#[inline] |
| 353 |
pub fn iter(&self) -> ByteClassIter<'_> { |
| 354 |
ByteClassIter { classes: self, i: 0 } |
| 355 |
} |
| 356 |
|
| 357 |
/// Returns an iterator over a sequence of representative bytes from each |
| 358 |
/// equivalence class within the range of bytes given. |
| 359 |
/// |
| 360 |
/// When the given range is unbounded on both sides, the iterator yields |
| 361 |
/// exactly N items, where N is equivalent to the number of equivalence |
| 362 |
/// classes. Each item is an arbitrary byte drawn from each equivalence |
| 363 |
/// class. |
| 364 |
/// |
| 365 |
/// This is useful when one is determinizing an NFA and the NFA's alphabet |
| 366 |
/// hasn't been converted to equivalence classes. Picking an arbitrary byte |
| 367 |
/// from each equivalence class then permits a full exploration of the NFA |
| 368 |
/// instead of using every possible byte value and thus potentially saves |
| 369 |
/// quite a lot of redundant work. |
| 370 |
/// |
| 371 |
/// # Example |
| 372 |
/// |
| 373 |
/// This shows an example of what a complete sequence of representatives |
| 374 |
/// might look like from a real example. |
| 375 |
/// |
| 376 |
/// ``` |
| 377 |
/// use regex_automata::{nfa::thompson::NFA, util::alphabet::Unit}; |
| 378 |
/// |
| 379 |
/// let nfa = NFA::new("[a-z]+")?; |
| 380 |
/// let classes = nfa.byte_classes(); |
| 381 |
/// let reps: Vec<Unit> = classes.representatives(..).collect(); |
| 382 |
/// // Note that the specific byte values yielded are not guaranteed! |
| 383 |
/// let expected = vec![ |
| 384 |
/// Unit::u8(b'\x00'), |
| 385 |
/// Unit::u8(b'a'), |
| 386 |
/// Unit::u8(b'{'), |
| 387 |
/// Unit::eoi(3), |
| 388 |
/// ]; |
| 389 |
/// assert_eq!(expected, reps); |
| 390 |
/// |
| 391 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 392 |
/// ``` |
| 393 |
/// |
| 394 |
/// Note though, that you can ask for an arbitrary range of bytes, and only |
| 395 |
/// representatives for that range will be returned: |
| 396 |
/// |
| 397 |
/// ``` |
| 398 |
/// use regex_automata::{nfa::thompson::NFA, util::alphabet::Unit}; |
| 399 |
/// |
| 400 |
/// let nfa = NFA::new("[a-z]+")?; |
| 401 |
/// let classes = nfa.byte_classes(); |
| 402 |
/// let reps: Vec<Unit> = classes.representatives(b'A'..=b'z').collect(); |
| 403 |
/// // Note that the specific byte values yielded are not guaranteed! |
| 404 |
/// let expected = vec![ |
| 405 |
/// Unit::u8(b'A'), |
| 406 |
/// Unit::u8(b'a'), |
| 407 |
/// ]; |
| 408 |
/// assert_eq!(expected, reps); |
| 409 |
/// |
| 410 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 411 |
/// ``` |
| 412 |
pub fn representatives<R: core::ops::RangeBounds<u8>>( |
| 413 |
&self, |
| 414 |
range: R, |
| 415 |
) -> ByteClassRepresentatives<'_> { |
| 416 |
use core::ops::Bound; |
| 417 |
|
| 418 |
let cur_byte = match range.start_bound() { |
| 419 |
Bound::Included(&i) => usize::from(i), |
| 420 |
Bound::Excluded(&i) => usize::from(i).checked_add(1).unwrap(), |
| 421 |
Bound::Unbounded => 0, |
| 422 |
}; |
| 423 |
let end_byte = match range.end_bound() { |
| 424 |
Bound::Included(&i) => { |
| 425 |
Some(usize::from(i).checked_add(1).unwrap()) |
| 426 |
} |
| 427 |
Bound::Excluded(&i) => Some(usize::from(i)), |
| 428 |
Bound::Unbounded => None, |
| 429 |
}; |
| 430 |
assert_ne!( |
| 431 |
cur_byte, |
| 432 |
usize::MAX, |
| 433 |
"start range must be less than usize::MAX", |
| 434 |
); |
| 435 |
ByteClassRepresentatives { |
| 436 |
classes: self, |
| 437 |
cur_byte, |
| 438 |
end_byte, |
| 439 |
last_class: None, |
| 440 |
} |
| 441 |
} |
| 442 |
|
| 443 |
/// Returns an iterator of the bytes in the given equivalence class. |
| 444 |
/// |
| 445 |
/// This is useful when one needs to know the actual bytes that belong to |
| 446 |
/// an equivalence class. For example, conceptually speaking, accelerating |
| 447 |
/// a DFA state occurs when a state only has a few outgoing transitions. |
| 448 |
/// But in reality, what is required is that there are only a small |
| 449 |
/// number of distinct bytes that can lead to an outgoing transition. The |
| 450 |
/// difference is that any one transition can correspond to an equivalence |
| 451 |
/// class which may contains many bytes. Therefore, DFA state acceleration |
| 452 |
/// considers the actual elements in each equivalence class of each |
| 453 |
/// outgoing transition. |
| 454 |
/// |
| 455 |
/// # Example |
| 456 |
/// |
| 457 |
/// This shows an example of how to get all of the elements in an |
| 458 |
/// equivalence class. |
| 459 |
/// |
| 460 |
/// ``` |
| 461 |
/// use regex_automata::{nfa::thompson::NFA, util::alphabet::Unit}; |
| 462 |
/// |
| 463 |
/// let nfa = NFA::new("[a-z]+")?; |
| 464 |
/// let classes = nfa.byte_classes(); |
| 465 |
/// let elements: Vec<Unit> = classes.elements(Unit::u8(1)).collect(); |
| 466 |
/// let expected: Vec<Unit> = (b'a'..=b'z').map(Unit::u8).collect(); |
| 467 |
/// assert_eq!(expected, elements); |
| 468 |
/// |
| 469 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 470 |
/// ``` |
| 471 |
#[inline] |
| 472 |
pub fn elements(&self, class: Unit) -> ByteClassElements { |
| 473 |
ByteClassElements { classes: self, class, byte: 0 } |
| 474 |
} |
| 475 |
|
| 476 |
/// Returns an iterator of byte ranges in the given equivalence class. |
| 477 |
/// |
| 478 |
/// That is, a sequence of contiguous ranges are returned. Typically, every |
| 479 |
/// class maps to a single contiguous range. |
| 480 |
fn element_ranges(&self, class: Unit) -> ByteClassElementRanges { |
| 481 |
ByteClassElementRanges { elements: self.elements(class), range: None } |
| 482 |
} |
| 483 |
} |
| 484 |
|
| 485 |
impl Default for ByteClasses { |
| 486 |
fn default() -> ByteClasses { |
| 487 |
ByteClasses::singletons() |
| 488 |
} |
| 489 |
} |
| 490 |
|
| 491 |
impl core::fmt::Debug for ByteClasses { |
| 492 |
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { |
| 493 |
if self.is_singleton() { |
| 494 |
write!(f, "ByteClasses({{singletons}})") |
| 495 |
} else { |
| 496 |
write!(f, "ByteClasses(")?; |
| 497 |
for (i, class) in self.iter().enumerate() { |
| 498 |
if i > 0 { |
| 499 |
write!(f, ", ")?; |
| 500 |
} |
| 501 |
write!(f, "{:?} => [", class.as_usize())?; |
| 502 |
for (start, end) in self.element_ranges(class) { |
| 503 |
if start == end { |
| 504 |
write!(f, "{:?}", start)?; |
| 505 |
} else { |
| 506 |
write!(f, "{:?}-{:?}", start, end)?; |
| 507 |
} |
| 508 |
} |
| 509 |
write!(f, "]")?; |
| 510 |
} |
| 511 |
write!(f, ")") |
| 512 |
} |
| 513 |
} |
| 514 |
} |
| 515 |
|
| 516 |
/// An iterator over each equivalence class. |
| 517 |
/// |
| 518 |
/// The last element in this iterator always corresponds to [`Unit::eoi`]. |
| 519 |
/// |
| 520 |
/// This is created by the [`ByteClasses::iter`] method. |
| 521 |
/// |
| 522 |
/// The lifetime `'a` refers to the lifetime of the byte classes that this |
| 523 |
/// iterator was created from. |
| 524 |
#[derive(Debug)] |
| 525 |
pub struct ByteClassIter<'a> { |
| 526 |
classes: &'a ByteClasses, |
| 527 |
i: usize, |
| 528 |
} |
| 529 |
|
| 530 |
impl<'a> Iterator for ByteClassIter<'a> { |
| 531 |
type Item = Unit; |
| 532 |
|
| 533 |
fn next(&mut self) -> Option<Unit> { |
| 534 |
if self.i + 1 == self.classes.alphabet_len() { |
| 535 |
self.i += 1; |
| 536 |
Some(self.classes.eoi()) |
| 537 |
} else if self.i < self.classes.alphabet_len() { |
| 538 |
let class = u8::try_from(self.i).unwrap(); |
| 539 |
self.i += 1; |
| 540 |
Some(Unit::u8(class)) |
| 541 |
} else { |
| 542 |
None |
| 543 |
} |
| 544 |
} |
| 545 |
} |
| 546 |
|
| 547 |
/// An iterator over representative bytes from each equivalence class. |
| 548 |
/// |
| 549 |
/// This is created by the [`ByteClasses::representatives`] method. |
| 550 |
/// |
| 551 |
/// The lifetime `'a` refers to the lifetime of the byte classes that this |
| 552 |
/// iterator was created from. |
| 553 |
#[derive(Debug)] |
| 554 |
pub struct ByteClassRepresentatives<'a> { |
| 555 |
classes: &'a ByteClasses, |
| 556 |
cur_byte: usize, |
| 557 |
end_byte: Option<usize>, |
| 558 |
last_class: Option<u8>, |
| 559 |
} |
| 560 |
|
| 561 |
impl<'a> Iterator for ByteClassRepresentatives<'a> { |
| 562 |
type Item = Unit; |
| 563 |
|
| 564 |
fn next(&mut self) -> Option<Unit> { |
| 565 |
while self.cur_byte < self.end_byte.unwrap_or(256) { |
| 566 |
let byte = u8::try_from(self.cur_byte).unwrap(); |
| 567 |
let class = self.classes.get(byte); |
| 568 |
self.cur_byte += 1; |
| 569 |
|
| 570 |
if self.last_class != Some(class) { |
| 571 |
self.last_class = Some(class); |
| 572 |
return Some(Unit::u8(byte)); |
| 573 |
} |
| 574 |
} |
| 575 |
if self.cur_byte != usize::MAX && self.end_byte.is_none() { |
| 576 |
// Using usize::MAX as a sentinel is OK because we ban usize::MAX |
| 577 |
// from appearing as a start bound in iterator construction. But |
| 578 |
// why do it this way? Well, we want to return the EOI class |
| 579 |
// whenever the end of the given range is unbounded because EOI |
| 580 |
// isn't really a "byte" per se, so the only way it should be |
| 581 |
// excluded is if there is a bounded end to the range. Therefore, |
| 582 |
// when the end is unbounded, we just need to know whether we've |
| 583 |
// reported EOI or not. When we do, we set cur_byte to a value it |
| 584 |
// can never otherwise be. |
| 585 |
self.cur_byte = usize::MAX; |
| 586 |
return Some(self.classes.eoi()); |
| 587 |
} |
| 588 |
None |
| 589 |
} |
| 590 |
} |
| 591 |
|
| 592 |
/// An iterator over all elements in an equivalence class. |
| 593 |
/// |
| 594 |
/// This is created by the [`ByteClasses::elements`] method. |
| 595 |
/// |
| 596 |
/// The lifetime `'a` refers to the lifetime of the byte classes that this |
| 597 |
/// iterator was created from. |
| 598 |
#[derive(Debug)] |
| 599 |
pub struct ByteClassElements<'a> { |
| 600 |
classes: &'a ByteClasses, |
| 601 |
class: Unit, |
| 602 |
byte: usize, |
| 603 |
} |
| 604 |
|
| 605 |
impl<'a> Iterator for ByteClassElements<'a> { |
| 606 |
type Item = Unit; |
| 607 |
|
| 608 |
fn next(&mut self) -> Option<Unit> { |
| 609 |
while self.byte < 256 { |
| 610 |
let byte = u8::try_from(self.byte).unwrap(); |
| 611 |
self.byte += 1; |
| 612 |
if self.class.is_byte(self.classes.get(byte)) { |
| 613 |
return Some(Unit::u8(byte)); |
| 614 |
} |
| 615 |
} |
| 616 |
if self.byte < 257 { |
| 617 |
self.byte += 1; |
| 618 |
if self.class.is_eoi() { |
| 619 |
return Some(Unit::eoi(256)); |
| 620 |
} |
| 621 |
} |
| 622 |
None |
| 623 |
} |
| 624 |
} |
| 625 |
|
| 626 |
/// An iterator over all elements in an equivalence class expressed as a |
| 627 |
/// sequence of contiguous ranges. |
| 628 |
#[derive(Debug)] |
| 629 |
struct ByteClassElementRanges<'a> { |
| 630 |
elements: ByteClassElements<'a>, |
| 631 |
range: Option<(Unit, Unit)>, |
| 632 |
} |
| 633 |
|
| 634 |
impl<'a> Iterator for ByteClassElementRanges<'a> { |
| 635 |
type Item = (Unit, Unit); |
| 636 |
|
| 637 |
fn next(&mut self) -> Option<(Unit, Unit)> { |
| 638 |
loop { |
| 639 |
let element = match self.elements.next() { |
| 640 |
None => return self.range.take(), |
| 641 |
Some(element) => element, |
| 642 |
}; |
| 643 |
match self.range.take() { |
| 644 |
None => { |
| 645 |
self.range = Some((element, element)); |
| 646 |
} |
| 647 |
Some((start, end)) => { |
| 648 |
if end.as_usize() + 1 != element.as_usize() |
| 649 |
|| element.is_eoi() |
| 650 |
{ |
| 651 |
self.range = Some((element, element)); |
| 652 |
return Some((start, end)); |
| 653 |
} |
| 654 |
self.range = Some((start, element)); |
| 655 |
} |
| 656 |
} |
| 657 |
} |
| 658 |
} |
| 659 |
} |
| 660 |
|
| 661 |
/// A partitioning of bytes into equivalence classes. |
| 662 |
/// |
| 663 |
/// A byte class set keeps track of an *approximation* of equivalence classes |
| 664 |
/// of bytes during NFA construction. That is, every byte in an equivalence |
| 665 |
/// class cannot discriminate between a match and a non-match. |
| 666 |
/// |
| 667 |
/// For example, in the regex `[ab]+`, the bytes `a` and `b` would be in the |
| 668 |
/// same equivalence class because it never matters whether an `a` or a `b` is |
| 669 |
/// seen, and no combination of `a`s and `b`s in the text can discriminate a |
| 670 |
/// match. |
| 671 |
/// |
| 672 |
/// Note though that this does not compute the minimal set of equivalence |
| 673 |
/// classes. For example, in the regex `[ac]+`, both `a` and `c` are in the |
| 674 |
/// same equivalence class for the same reason that `a` and `b` are in the |
| 675 |
/// same equivalence class in the aforementioned regex. However, in this |
| 676 |
/// implementation, `a` and `c` are put into distinct equivalence classes. The |
| 677 |
/// reason for this is implementation complexity. In the future, we should |
| 678 |
/// endeavor to compute the minimal equivalence classes since they can have a |
| 679 |
/// rather large impact on the size of the DFA. (Doing this will likely require |
| 680 |
/// rethinking how equivalence classes are computed, including changing the |
| 681 |
/// representation here, which is only able to group contiguous bytes into the |
| 682 |
/// same equivalence class.) |
| 683 |
#[cfg(feature = "alloc")] |
| 684 |
#[derive(Clone, Debug)] |
| 685 |
pub(crate) struct ByteClassSet(ByteSet); |
| 686 |
|
| 687 |
#[cfg(feature = "alloc")] |
| 688 |
impl Default for ByteClassSet { |
| 689 |
fn default() -> ByteClassSet { |
| 690 |
ByteClassSet::empty() |
| 691 |
} |
| 692 |
} |
| 693 |
|
| 694 |
#[cfg(feature = "alloc")] |
| 695 |
impl ByteClassSet { |
| 696 |
/// Create a new set of byte classes where all bytes are part of the same |
| 697 |
/// equivalence class. |
| 698 |
pub(crate) fn empty() -> Self { |
| 699 |
ByteClassSet(ByteSet::empty()) |
| 700 |
} |
| 701 |
|
| 702 |
/// Indicate the the range of byte given (inclusive) can discriminate a |
| 703 |
/// match between it and all other bytes outside of the range. |
| 704 |
pub(crate) fn set_range(&mut self, start: u8, end: u8) { |
| 705 |
debug_assert!(start <= end); |
| 706 |
if start > 0 { |
| 707 |
self.0.add(start - 1); |
| 708 |
} |
| 709 |
self.0.add(end); |
| 710 |
} |
| 711 |
|
| 712 |
/// Add the contiguous ranges in the set given to this byte class set. |
| 713 |
pub(crate) fn add_set(&mut self, set: &ByteSet) { |
| 714 |
for (start, end) in set.iter_ranges() { |
| 715 |
self.set_range(start, end); |
| 716 |
} |
| 717 |
} |
| 718 |
|
| 719 |
/// Convert this boolean set to a map that maps all byte values to their |
| 720 |
/// corresponding equivalence class. The last mapping indicates the largest |
| 721 |
/// equivalence class identifier (which is never bigger than 255). |
| 722 |
pub(crate) fn byte_classes(&self) -> ByteClasses { |
| 723 |
let mut classes = ByteClasses::empty(); |
| 724 |
let mut class = 0u8; |
| 725 |
let mut b = 0u8; |
| 726 |
loop { |
| 727 |
classes.set(b, class); |
| 728 |
if b == 255 { |
| 729 |
break; |
| 730 |
} |
| 731 |
if self.0.contains(b) { |
| 732 |
class = class.checked_add(1).unwrap(); |
| 733 |
} |
| 734 |
b = b.checked_add(1).unwrap(); |
| 735 |
} |
| 736 |
classes |
| 737 |
} |
| 738 |
} |
| 739 |
|
| 740 |
/// A simple set of bytes that is reasonably cheap to copy and allocation free. |
| 741 |
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)] |
| 742 |
pub(crate) struct ByteSet { |
| 743 |
bits: BitSet, |
| 744 |
} |
| 745 |
|
| 746 |
/// The representation of a byte set. Split out so that we can define a |
| 747 |
/// convenient Debug impl for it while keeping "ByteSet" in the output. |
| 748 |
#[derive(Clone, Copy, Default, Eq, PartialEq)] |
| 749 |
struct BitSet([u128; 2]); |
| 750 |
|
| 751 |
impl ByteSet { |
| 752 |
/// Create an empty set of bytes. |
| 753 |
pub(crate) fn empty() -> ByteSet { |
| 754 |
ByteSet { bits: BitSet([0; 2]) } |
| 755 |
} |
| 756 |
|
| 757 |
/// Add a byte to this set. |
| 758 |
/// |
| 759 |
/// If the given byte already belongs to this set, then this is a no-op. |
| 760 |
pub(crate) fn add(&mut self, byte: u8) { |
| 761 |
let bucket = byte / 128; |
| 762 |
let bit = byte % 128; |
| 763 |
self.bits.0[usize::from(bucket)] |= 1 << bit; |
| 764 |
} |
| 765 |
|
| 766 |
/// Remove a byte from this set. |
| 767 |
/// |
| 768 |
/// If the given byte is not in this set, then this is a no-op. |
| 769 |
pub(crate) fn remove(&mut self, byte: u8) { |
| 770 |
let bucket = byte / 128; |
| 771 |
let bit = byte % 128; |
| 772 |
self.bits.0[usize::from(bucket)] &= !(1 << bit); |
| 773 |
} |
| 774 |
|
| 775 |
/// Return true if and only if the given byte is in this set. |
| 776 |
pub(crate) fn contains(&self, byte: u8) -> bool { |
| 777 |
let bucket = byte / 128; |
| 778 |
let bit = byte % 128; |
| 779 |
self.bits.0[usize::from(bucket)] & (1 << bit) > 0 |
| 780 |
} |
| 781 |
|
| 782 |
/// Return true if and only if the given inclusive range of bytes is in |
| 783 |
/// this set. |
| 784 |
pub(crate) fn contains_range(&self, start: u8, end: u8) -> bool { |
| 785 |
(start..=end).all(|b| self.contains(b)) |
| 786 |
} |
| 787 |
|
| 788 |
/// Returns an iterator over all bytes in this set. |
| 789 |
pub(crate) fn iter(&self) -> ByteSetIter { |
| 790 |
ByteSetIter { set: self, b: 0 } |
| 791 |
} |
| 792 |
|
| 793 |
/// Returns an iterator over all contiguous ranges of bytes in this set. |
| 794 |
pub(crate) fn iter_ranges(&self) -> ByteSetRangeIter { |
| 795 |
ByteSetRangeIter { set: self, b: 0 } |
| 796 |
} |
| 797 |
|
| 798 |
/// Return true if and only if this set is empty. |
| 799 |
#[cfg_attr(feature = "perf-inline", inline(always))] |
| 800 |
pub(crate) fn is_empty(&self) -> bool { |
| 801 |
self.bits.0 == [0, 0] |
| 802 |
} |
| 803 |
|
| 804 |
/// Deserializes a byte set from the given slice. If the slice is of |
| 805 |
/// incorrect length or is otherwise malformed, then an error is returned. |
| 806 |
/// Upon success, the number of bytes read along with the set are returned. |
| 807 |
/// The number of bytes read is always a multiple of 8. |
| 808 |
pub(crate) fn from_bytes( |
| 809 |
slice: &[u8], |
| 810 |
) -> Result<(ByteSet, usize), DeserializeError> { |
| 811 |
use core::mem::size_of; |
| 812 |
|
| 813 |
wire::check_slice_len(slice, 2 * size_of::<u128>(), "byte set")?; |
| 814 |
let mut nread = 0; |
| 815 |
let (low, nr) = wire::try_read_u128(slice, "byte set low bucket")?; |
| 816 |
nread += nr; |
| 817 |
let (high, nr) = wire::try_read_u128(slice, "byte set high bucket")?; |
| 818 |
nread += nr; |
| 819 |
Ok((ByteSet { bits: BitSet([low, high]) }, nread)) |
| 820 |
} |
| 821 |
|
| 822 |
/// Writes this byte set to the given byte buffer. If the given buffer is |
| 823 |
/// too small, then an error is returned. Upon success, the total number of |
| 824 |
/// bytes written is returned. The number of bytes written is guaranteed to |
| 825 |
/// be a multiple of 8. |
| 826 |
pub(crate) fn write_to<E: crate::util::wire::Endian>( |
| 827 |
&self, |
| 828 |
dst: &mut [u8], |
| 829 |
) -> Result<usize, SerializeError> { |
| 830 |
use core::mem::size_of; |
| 831 |
|
| 832 |
let nwrite = self.write_to_len(); |
| 833 |
if dst.len() < nwrite { |
| 834 |
return Err(SerializeError::buffer_too_small("byte set")); |
| 835 |
} |
| 836 |
let mut nw = 0; |
| 837 |
E::write_u128(self.bits.0[0], &mut dst[nw..]); |
| 838 |
nw += size_of::<u128>(); |
| 839 |
E::write_u128(self.bits.0[1], &mut dst[nw..]); |
| 840 |
nw += size_of::<u128>(); |
| 841 |
assert_eq!(nwrite, nw, "expected to write certain number of bytes",); |
| 842 |
assert_eq!( |
| 843 |
nw % 8, |
| 844 |
0, |
| 845 |
"expected to write multiple of 8 bytes for byte set", |
| 846 |
); |
| 847 |
Ok(nw) |
| 848 |
} |
| 849 |
|
| 850 |
/// Returns the total number of bytes written by `write_to`. |
| 851 |
pub(crate) fn write_to_len(&self) -> usize { |
| 852 |
2 * core::mem::size_of::<u128>() |
| 853 |
} |
| 854 |
} |
| 855 |
|
| 856 |
impl core::fmt::Debug for BitSet { |
| 857 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 858 |
let mut fmtd = f.debug_set(); |
| 859 |
for b in 0u8..=255 { |
| 860 |
if (ByteSet { bits: *self }).contains(b) { |
| 861 |
fmtd.entry(&b); |
| 862 |
} |
| 863 |
} |
| 864 |
fmtd.finish() |
| 865 |
} |
| 866 |
} |
| 867 |
|
| 868 |
#[derive(Debug)] |
| 869 |
pub(crate) struct ByteSetIter<'a> { |
| 870 |
set: &'a ByteSet, |
| 871 |
b: usize, |
| 872 |
} |
| 873 |
|
| 874 |
impl<'a> Iterator for ByteSetIter<'a> { |
| 875 |
type Item = u8; |
| 876 |
|
| 877 |
fn next(&mut self) -> Option<u8> { |
| 878 |
while self.b <= 255 { |
| 879 |
let b = u8::try_from(self.b).unwrap(); |
| 880 |
self.b += 1; |
| 881 |
if self.set.contains(b) { |
| 882 |
return Some(b); |
| 883 |
} |
| 884 |
} |
| 885 |
None |
| 886 |
} |
| 887 |
} |
| 888 |
|
| 889 |
#[derive(Debug)] |
| 890 |
pub(crate) struct ByteSetRangeIter<'a> { |
| 891 |
set: &'a ByteSet, |
| 892 |
b: usize, |
| 893 |
} |
| 894 |
|
| 895 |
impl<'a> Iterator for ByteSetRangeIter<'a> { |
| 896 |
type Item = (u8, u8); |
| 897 |
|
| 898 |
fn next(&mut self) -> Option<(u8, u8)> { |
| 899 |
let asu8 = |n: usize| u8::try_from(n).unwrap(); |
| 900 |
while self.b <= 255 { |
| 901 |
let start = asu8(self.b); |
| 902 |
self.b += 1; |
| 903 |
if !self.set.contains(start) { |
| 904 |
continue; |
| 905 |
} |
| 906 |
|
| 907 |
let mut end = start; |
| 908 |
while self.b <= 255 && self.set.contains(asu8(self.b)) { |
| 909 |
end = asu8(self.b); |
| 910 |
self.b += 1; |
| 911 |
} |
| 912 |
return Some((start, end)); |
| 913 |
} |
| 914 |
None |
| 915 |
} |
| 916 |
} |
| 917 |
|
| 918 |
#[cfg(all(test, feature = "alloc"))] |
| 919 |
mod tests { |
| 920 |
use alloc::{vec, vec::Vec}; |
| 921 |
|
| 922 |
use super::*; |
| 923 |
|
| 924 |
#[test] |
| 925 |
fn byte_classes() { |
| 926 |
let mut set = ByteClassSet::empty(); |
| 927 |
set.set_range(b'a', b'z'); |
| 928 |
|
| 929 |
let classes = set.byte_classes(); |
| 930 |
assert_eq!(classes.get(0), 0); |
| 931 |
assert_eq!(classes.get(1), 0); |
| 932 |
assert_eq!(classes.get(2), 0); |
| 933 |
assert_eq!(classes.get(b'a' - 1), 0); |
| 934 |
assert_eq!(classes.get(b'a'), 1); |
| 935 |
assert_eq!(classes.get(b'm'), 1); |
| 936 |
assert_eq!(classes.get(b'z'), 1); |
| 937 |
assert_eq!(classes.get(b'z' + 1), 2); |
| 938 |
assert_eq!(classes.get(254), 2); |
| 939 |
assert_eq!(classes.get(255), 2); |
| 940 |
|
| 941 |
let mut set = ByteClassSet::empty(); |
| 942 |
set.set_range(0, 2); |
| 943 |
set.set_range(4, 6); |
| 944 |
let classes = set.byte_classes(); |
| 945 |
assert_eq!(classes.get(0), 0); |
| 946 |
assert_eq!(classes.get(1), 0); |
| 947 |
assert_eq!(classes.get(2), 0); |
| 948 |
assert_eq!(classes.get(3), 1); |
| 949 |
assert_eq!(classes.get(4), 2); |
| 950 |
assert_eq!(classes.get(5), 2); |
| 951 |
assert_eq!(classes.get(6), 2); |
| 952 |
assert_eq!(classes.get(7), 3); |
| 953 |
assert_eq!(classes.get(255), 3); |
| 954 |
} |
| 955 |
|
| 956 |
#[test] |
| 957 |
fn full_byte_classes() { |
| 958 |
let mut set = ByteClassSet::empty(); |
| 959 |
for b in 0u8..=255 { |
| 960 |
set.set_range(b, b); |
| 961 |
} |
| 962 |
assert_eq!(set.byte_classes().alphabet_len(), 257); |
| 963 |
} |
| 964 |
|
| 965 |
#[test] |
| 966 |
fn elements_typical() { |
| 967 |
let mut set = ByteClassSet::empty(); |
| 968 |
set.set_range(b'b', b'd'); |
| 969 |
set.set_range(b'g', b'm'); |
| 970 |
set.set_range(b'z', b'z'); |
| 971 |
let classes = set.byte_classes(); |
| 972 |
// class 0: \x00-a |
| 973 |
// class 1: b-d |
| 974 |
// class 2: e-f |
| 975 |
// class 3: g-m |
| 976 |
// class 4: n-y |
| 977 |
// class 5: z-z |
| 978 |
// class 6: \x7B-\xFF |
| 979 |
// class 7: EOI |
| 980 |
assert_eq!(classes.alphabet_len(), 8); |
| 981 |
|
| 982 |
let elements = classes.elements(Unit::u8(0)).collect::<Vec<_>>(); |
| 983 |
assert_eq!(elements.len(), 98); |
| 984 |
assert_eq!(elements[0], Unit::u8(b'\x00')); |
| 985 |
assert_eq!(elements[97], Unit::u8(b'a')); |
| 986 |
|
| 987 |
let elements = classes.elements(Unit::u8(1)).collect::<Vec<_>>(); |
| 988 |
assert_eq!( |
| 989 |
elements, |
| 990 |
vec![Unit::u8(b'b'), Unit::u8(b'c'), Unit::u8(b'd')], |
| 991 |
); |
| 992 |
|
| 993 |
let elements = classes.elements(Unit::u8(2)).collect::<Vec<_>>(); |
| 994 |
assert_eq!(elements, vec![Unit::u8(b'e'), Unit::u8(b'f')],); |
| 995 |
|
| 996 |
let elements = classes.elements(Unit::u8(3)).collect::<Vec<_>>(); |
| 997 |
assert_eq!( |
| 998 |
elements, |
| 999 |
vec![ |
| 1000 |
Unit::u8(b'g'), |
| 1001 |
Unit::u8(b'h'), |
| 1002 |
Unit::u8(b'i'), |
| 1003 |
Unit::u8(b'j'), |
| 1004 |
Unit::u8(b'k'), |
| 1005 |
Unit::u8(b'l'), |
| 1006 |
Unit::u8(b'm'), |
| 1007 |
], |
| 1008 |
); |
| 1009 |
|
| 1010 |
let elements = classes.elements(Unit::u8(4)).collect::<Vec<_>>(); |
| 1011 |
assert_eq!(elements.len(), 12); |
| 1012 |
assert_eq!(elements[0], Unit::u8(b'n')); |
| 1013 |
assert_eq!(elements[11], Unit::u8(b'y')); |
| 1014 |
|
| 1015 |
let elements = classes.elements(Unit::u8(5)).collect::<Vec<_>>(); |
| 1016 |
assert_eq!(elements, vec![Unit::u8(b'z')]); |
| 1017 |
|
| 1018 |
let elements = classes.elements(Unit::u8(6)).collect::<Vec<_>>(); |
| 1019 |
assert_eq!(elements.len(), 133); |
| 1020 |
assert_eq!(elements[0], Unit::u8(b'\x7B')); |
| 1021 |
assert_eq!(elements[132], Unit::u8(b'\xFF')); |
| 1022 |
|
| 1023 |
let elements = classes.elements(Unit::eoi(7)).collect::<Vec<_>>(); |
| 1024 |
assert_eq!(elements, vec![Unit::eoi(256)]); |
| 1025 |
} |
| 1026 |
|
| 1027 |
#[test] |
| 1028 |
fn elements_singletons() { |
| 1029 |
let classes = ByteClasses::singletons(); |
| 1030 |
assert_eq!(classes.alphabet_len(), 257); |
| 1031 |
|
| 1032 |
let elements = classes.elements(Unit::u8(b'a')).collect::<Vec<_>>(); |
| 1033 |
assert_eq!(elements, vec![Unit::u8(b'a')]); |
| 1034 |
|
| 1035 |
let elements = classes.elements(Unit::eoi(5)).collect::<Vec<_>>(); |
| 1036 |
assert_eq!(elements, vec![Unit::eoi(256)]); |
| 1037 |
} |
| 1038 |
|
| 1039 |
#[test] |
| 1040 |
fn elements_empty() { |
| 1041 |
let classes = ByteClasses::empty(); |
| 1042 |
assert_eq!(classes.alphabet_len(), 2); |
| 1043 |
|
| 1044 |
let elements = classes.elements(Unit::u8(0)).collect::<Vec<_>>(); |
| 1045 |
assert_eq!(elements.len(), 256); |
| 1046 |
assert_eq!(elements[0], Unit::u8(b'\x00')); |
| 1047 |
assert_eq!(elements[255], Unit::u8(b'\xFF')); |
| 1048 |
|
| 1049 |
let elements = classes.elements(Unit::eoi(1)).collect::<Vec<_>>(); |
| 1050 |
assert_eq!(elements, vec![Unit::eoi(256)]); |
| 1051 |
} |
| 1052 |
|
| 1053 |
#[test] |
| 1054 |
fn representatives() { |
| 1055 |
let mut set = ByteClassSet::empty(); |
| 1056 |
set.set_range(b'b', b'd'); |
| 1057 |
set.set_range(b'g', b'm'); |
| 1058 |
set.set_range(b'z', b'z'); |
| 1059 |
let classes = set.byte_classes(); |
| 1060 |
|
| 1061 |
let got: Vec<Unit> = classes.representatives(..).collect(); |
| 1062 |
let expected = vec![ |
| 1063 |
Unit::u8(b'\x00'), |
| 1064 |
Unit::u8(b'b'), |
| 1065 |
Unit::u8(b'e'), |
| 1066 |
Unit::u8(b'g'), |
| 1067 |
Unit::u8(b'n'), |
| 1068 |
Unit::u8(b'z'), |
| 1069 |
Unit::u8(b'\x7B'), |
| 1070 |
Unit::eoi(7), |
| 1071 |
]; |
| 1072 |
assert_eq!(expected, got); |
| 1073 |
|
| 1074 |
let got: Vec<Unit> = classes.representatives(..0).collect(); |
| 1075 |
assert!(got.is_empty()); |
| 1076 |
let got: Vec<Unit> = classes.representatives(1..1).collect(); |
| 1077 |
assert!(got.is_empty()); |
| 1078 |
let got: Vec<Unit> = classes.representatives(255..255).collect(); |
| 1079 |
assert!(got.is_empty()); |
| 1080 |
|
| 1081 |
// A weird case that is the only guaranteed to way to get an iterator |
| 1082 |
// of just the EOI class by excluding all possible byte values. |
| 1083 |
let got: Vec<Unit> = classes |
| 1084 |
.representatives(( |
| 1085 |
core::ops::Bound::Excluded(255), |
| 1086 |
core::ops::Bound::Unbounded, |
| 1087 |
)) |
| 1088 |
.collect(); |
| 1089 |
let expected = vec![Unit::eoi(7)]; |
| 1090 |
assert_eq!(expected, got); |
| 1091 |
|
| 1092 |
let got: Vec<Unit> = classes.representatives(..=255).collect(); |
| 1093 |
let expected = vec![ |
| 1094 |
Unit::u8(b'\x00'), |
| 1095 |
Unit::u8(b'b'), |
| 1096 |
Unit::u8(b'e'), |
| 1097 |
Unit::u8(b'g'), |
| 1098 |
Unit::u8(b'n'), |
| 1099 |
Unit::u8(b'z'), |
| 1100 |
Unit::u8(b'\x7B'), |
| 1101 |
]; |
| 1102 |
assert_eq!(expected, got); |
| 1103 |
|
| 1104 |
let got: Vec<Unit> = classes.representatives(b'b'..=b'd').collect(); |
| 1105 |
let expected = vec![Unit::u8(b'b')]; |
| 1106 |
assert_eq!(expected, got); |
| 1107 |
|
| 1108 |
let got: Vec<Unit> = classes.representatives(b'a'..=b'd').collect(); |
| 1109 |
let expected = vec![Unit::u8(b'a'), Unit::u8(b'b')]; |
| 1110 |
assert_eq!(expected, got); |
| 1111 |
|
| 1112 |
let got: Vec<Unit> = classes.representatives(b'b'..=b'e').collect(); |
| 1113 |
let expected = vec![Unit::u8(b'b'), Unit::u8(b'e')]; |
| 1114 |
assert_eq!(expected, got); |
| 1115 |
|
| 1116 |
let got: Vec<Unit> = classes.representatives(b'A'..=b'Z').collect(); |
| 1117 |
let expected = vec![Unit::u8(b'A')]; |
| 1118 |
assert_eq!(expected, got); |
| 1119 |
|
| 1120 |
let got: Vec<Unit> = classes.representatives(b'A'..=b'z').collect(); |
| 1121 |
let expected = vec![ |
| 1122 |
Unit::u8(b'A'), |
| 1123 |
Unit::u8(b'b'), |
| 1124 |
Unit::u8(b'e'), |
| 1125 |
Unit::u8(b'g'), |
| 1126 |
Unit::u8(b'n'), |
| 1127 |
Unit::u8(b'z'), |
| 1128 |
]; |
| 1129 |
assert_eq!(expected, got); |
| 1130 |
|
| 1131 |
let got: Vec<Unit> = classes.representatives(b'z'..).collect(); |
| 1132 |
let expected = vec![Unit::u8(b'z'), Unit::u8(b'\x7B'), Unit::eoi(7)]; |
| 1133 |
assert_eq!(expected, got); |
| 1134 |
|
| 1135 |
let got: Vec<Unit> = classes.representatives(b'z'..=0xFF).collect(); |
| 1136 |
let expected = vec![Unit::u8(b'z'), Unit::u8(b'\x7B')]; |
| 1137 |
assert_eq!(expected, got); |
| 1138 |
} |
| 1139 |
} |