third_party/rust_crates/ask2patch/aho-corasick/src/classes.rs - fuchsia - Git at Google

 use std::fmt;

 /// A representation of byte oriented equivalence classes.
 ///
 /// This is used in an FSM to reduce the size of the transition table. This can
 /// have a particularly large impact not only on the total size of an FSM, but
 /// also on compile times.
 #[derive(Clone, Copy)]
 pub struct ByteClasses([u8; 256]);

 impl ByteClasses {
     /// Creates a new set of equivalence classes where all bytes are mapped to
     /// the same class.
     pub fn empty() -> ByteClasses {
         ByteClasses([0; 256])
     }

     /// Creates a new set of equivalence classes where each byte belongs to
     /// its own equivalence class.
     pub fn singletons() -> ByteClasses {
         let mut classes = ByteClasses::empty();
         for i in 0..256 {
             classes.set(i as u8, i as u8);
         }
         classes
     }

     /// Set the equivalence class for the given byte.
     #[inline]
     pub fn set(&mut self, byte: u8, class: u8) {
         self.0[byte as usize] = class;
     }

     /// Get the equivalence class for the given byte.
     #[inline]
     pub fn get(&self, byte: u8) -> u8 {
         // SAFETY: This is safe because all dense transitions have
         // exactly 256 elements, so all u8 values are valid indices.
         self.0[byte as usize]
     }

     /// Return the total number of elements in the alphabet represented by
     /// these equivalence classes. Equivalently, this returns the total number
     /// of equivalence classes.
     #[inline]
     pub fn alphabet_len(&self) -> usize {
         self.0[255] as usize + 1
     }

     /// Returns true if and only if every byte in this class maps to its own
     /// equivalence class. Equivalently, there are 256 equivalence classes
     /// and each class contains exactly one byte.
     #[inline]
     pub fn is_singleton(&self) -> bool {
         self.alphabet_len() == 256
     }

     /// Returns an iterator over a sequence of representative bytes from each
     /// equivalence class. Namely, this yields exactly N items, where N is
     /// equivalent to the number of equivalence classes. Each item is an
     /// arbitrary byte drawn from each equivalence class.
     ///
     /// This is useful when one is determinizing an NFA and the NFA's alphabet
     /// hasn't been converted to equivalence classes yet. Picking an arbitrary
     /// byte from each equivalence class then permits a full exploration of
     /// the NFA instead of using every possible byte value.
     pub fn representatives(&self) -> ByteClassRepresentatives<'_> {
         ByteClassRepresentatives { classes: self, byte: 0, last_class: None }
     }

     /// Returns all of the bytes in the given equivalence class.
     ///
     /// The second element in the tuple indicates the number of elements in
     /// the array.
     fn elements(&self, equiv: u8) -> ([u8; 256], usize) {
         let (mut array, mut len) = ([0; 256], 0);
         for b in 0..256 {
             if self.get(b as u8) == equiv {
                 array[len] = b as u8;
                 len += 1;
             }
         }
         (array, len)
     }
 }

 impl fmt::Debug for ByteClasses {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         if self.is_singleton() {
             write!(f, "ByteClasses({{singletons}})")
         } else {
             write!(f, "ByteClasses(")?;
             for equiv in 0..self.alphabet_len() {
                 let (members, len) = self.elements(equiv as u8);
                 write!(f, " {} => {:?}", equiv, &members[..len])?;
             }
             write!(f, ")")
         }
     }
 }

 /// An iterator over representative bytes from each equivalence class.
 #[derive(Debug)]
 pub struct ByteClassRepresentatives<'a> {
     classes: &'a ByteClasses,
     byte: usize,
     last_class: Option<u8>,
 }

 impl<'a> Iterator for ByteClassRepresentatives<'a> {
     type Item = u8;

     fn next(&mut self) -> Option<u8> {
         while self.byte < 256 {
             let byte = self.byte as u8;
             let class = self.classes.get(byte);
             self.byte += 1;

             if self.last_class != Some(class) {
                 self.last_class = Some(class);
                 return Some(byte);
             }
         }
         None
     }
 }

 /// A byte class builder keeps track of an *approximation* of equivalence
 /// classes of bytes during NFA construction. That is, every byte in an
 /// equivalence class cannot discriminate between a match and a non-match.
 ///
 /// For example, in the literals `abc` and `xyz`, the bytes [\x00-`], [d-w]
 /// and [{-\xFF] never discriminate between a match and a non-match, precisely
 /// because they never occur in the literals anywhere.
 ///
 /// Note though that this does not necessarily compute the minimal set of
 /// equivalence classes. For example, in the literals above, the byte ranges
 /// [\x00-`], [d-w] and [{-\xFF] are all treated as distinct equivalence
 /// classes even though they could be treated a single class. The reason for
 /// this is implementation complexity. In the future, we should endeavor to
 /// compute the minimal equivalence classes since they can have a rather large
 /// impact on the size of the DFA.
 ///
 /// The representation here is 256 booleans, all initially set to false. Each
 /// boolean maps to its corresponding byte based on position. A `true` value
 /// indicates the end of an equivalence class, where its corresponding byte
 /// and all of the bytes corresponding to all previous contiguous `false`
 /// values are in the same equivalence class.
 ///
 /// This particular representation only permits contiguous ranges of bytes to
 /// be in the same equivalence class, which means that we can never discover
 /// the true minimal set of equivalence classes.
 #[derive(Debug)]
 pub struct ByteClassBuilder(Vec<bool>);

 impl ByteClassBuilder {
     /// Create a new builder of byte classes where all bytes are part of the
     /// same equivalence class.
     pub fn new() -> ByteClassBuilder {
         ByteClassBuilder(vec![false; 256])
     }

     /// Indicate the the range of byte given (inclusive) can discriminate a
     /// match between it and all other bytes outside of the range.
     pub fn set_range(&mut self, start: u8, end: u8) {
         debug_assert!(start <= end);
         if start > 0 {
             self.0[start as usize - 1] = true;
         }
         self.0[end as usize] = true;
     }

     /// Build byte classes that map all byte values to their corresponding
     /// equivalence class. The last mapping indicates the largest equivalence
     /// class identifier (which is never bigger than 255).
     pub fn build(&self) -> ByteClasses {
         let mut classes = ByteClasses::empty();
         let mut class = 0u8;
         let mut i = 0;
         loop {
             classes.set(i as u8, class as u8);
             if i >= 255 {
                 break;
             }
             if self.0[i] {
                 class = class.checked_add(1).unwrap();
             }
             i += 1;
         }
         classes
     }
 }

 #[cfg(test)]
 mod tests {
     use super::*;

     #[test]
     fn byte_classes() {
         let mut set = ByteClassBuilder::new();
         set.set_range(b'a', b'z');

         let classes = set.build();
         assert_eq!(classes.get(0), 0);
         assert_eq!(classes.get(1), 0);
         assert_eq!(classes.get(2), 0);
         assert_eq!(classes.get(b'a' - 1), 0);
         assert_eq!(classes.get(b'a'), 1);
         assert_eq!(classes.get(b'm'), 1);
         assert_eq!(classes.get(b'z'), 1);
         assert_eq!(classes.get(b'z' + 1), 2);
         assert_eq!(classes.get(254), 2);
         assert_eq!(classes.get(255), 2);

         let mut set = ByteClassBuilder::new();
         set.set_range(0, 2);
         set.set_range(4, 6);
         let classes = set.build();
         assert_eq!(classes.get(0), 0);
         assert_eq!(classes.get(1), 0);
         assert_eq!(classes.get(2), 0);
         assert_eq!(classes.get(3), 1);
         assert_eq!(classes.get(4), 2);
         assert_eq!(classes.get(5), 2);
         assert_eq!(classes.get(6), 2);
         assert_eq!(classes.get(7), 3);
         assert_eq!(classes.get(255), 3);
     }

     #[test]
     fn full_byte_classes() {
         let mut set = ByteClassBuilder::new();
         for i in 0..256u16 {
             set.set_range(i as u8, i as u8);
         }
         assert_eq!(set.build().alphabet_len(), 256);
     }
 }
	use std::fmt;

	/// A representation of byte oriented equivalence classes.
	///
	/// This is used in an FSM to reduce the size of the transition table. This can
	/// have a particularly large impact not only on the total size of an FSM, but
	/// also on compile times.
	#[derive(Clone, Copy)]
	pub struct ByteClasses([u8; 256]);

	impl ByteClasses {
	/// Creates a new set of equivalence classes where all bytes are mapped to
	/// the same class.
	pub fn empty() -> ByteClasses {
	ByteClasses([0; 256])
	}

	/// Creates a new set of equivalence classes where each byte belongs to
	/// its own equivalence class.
	pub fn singletons() -> ByteClasses {
	let mut classes = ByteClasses::empty();
	for i in 0..256 {
	classes.set(i as u8, i as u8);
	}
	classes
	}

	/// Set the equivalence class for the given byte.
	#[inline]
	pub fn set(&mut self, byte: u8, class: u8) {
	self.0[byte as usize] = class;
	}

	/// Get the equivalence class for the given byte.
	#[inline]
	pub fn get(&self, byte: u8) -> u8 {
	// SAFETY: This is safe because all dense transitions have
	// exactly 256 elements, so all u8 values are valid indices.
	self.0[byte as usize]
	}

	/// Return the total number of elements in the alphabet represented by
	/// these equivalence classes. Equivalently, this returns the total number
	/// of equivalence classes.
	#[inline]
	pub fn alphabet_len(&self) -> usize {
	self.0[255] as usize + 1
	}

	/// Returns true if and only if every byte in this class maps to its own
	/// equivalence class. Equivalently, there are 256 equivalence classes
	/// and each class contains exactly one byte.
	#[inline]
	pub fn is_singleton(&self) -> bool {
	self.alphabet_len() == 256
	}

	/// Returns an iterator over a sequence of representative bytes from each
	/// equivalence class. Namely, this yields exactly N items, where N is
	/// equivalent to the number of equivalence classes. Each item is an
	/// arbitrary byte drawn from each equivalence class.
	///
	/// This is useful when one is determinizing an NFA and the NFA's alphabet
	/// hasn't been converted to equivalence classes yet. Picking an arbitrary
	/// byte from each equivalence class then permits a full exploration of
	/// the NFA instead of using every possible byte value.
	pub fn representatives(&self) -> ByteClassRepresentatives<'_> {
	ByteClassRepresentatives { classes: self, byte: 0, last_class: None }
	}

	/// Returns all of the bytes in the given equivalence class.
	///
	/// The second element in the tuple indicates the number of elements in
	/// the array.
	fn elements(&self, equiv: u8) -> ([u8; 256], usize) {
	let (mut array, mut len) = ([0; 256], 0);
	for b in 0..256 {
	if self.get(b as u8) == equiv {
	array[len] = b as u8;
	len += 1;
	}
	}
	(array, len)
	}
	}

	impl fmt::Debug for ByteClasses {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
	if self.is_singleton() {
	write!(f, "ByteClasses({{singletons}})")
	} else {
	write!(f, "ByteClasses(")?;
	for equiv in 0..self.alphabet_len() {
	let (members, len) = self.elements(equiv as u8);
	write!(f, " {} => {:?}", equiv, &members[..len])?;
	}
	write!(f, ")")
	}
	}
	}

	/// An iterator over representative bytes from each equivalence class.
	#[derive(Debug)]
	pub struct ByteClassRepresentatives<'a> {
	classes: &'a ByteClasses,
	byte: usize,
	last_class: Option<u8>,
	}

	impl<'a> Iterator for ByteClassRepresentatives<'a> {
	type Item = u8;

	fn next(&mut self) -> Option<u8> {
	while self.byte < 256 {
	let byte = self.byte as u8;
	let class = self.classes.get(byte);
	self.byte += 1;

	if self.last_class != Some(class) {
	self.last_class = Some(class);
	return Some(byte);
	}
	}
	None
	}
	}

	/// A byte class builder keeps track of an approximation of equivalence
	/// classes of bytes during NFA construction. That is, every byte in an
	/// equivalence class cannot discriminate between a match and a non-match.
	///
	/// For example, in the literals `abc` and `xyz`, the bytes [\x00-`], [d-w]
	/// and [{-\xFF] never discriminate between a match and a non-match, precisely
	/// because they never occur in the literals anywhere.
	///
	/// Note though that this does not necessarily compute the minimal set of
	/// equivalence classes. For example, in the literals above, the byte ranges
	/// [\x00-`], [d-w] and [{-\xFF] are all treated as distinct equivalence
	/// classes even though they could be treated a single class. The reason for
	/// this is implementation complexity. In the future, we should endeavor to
	/// compute the minimal equivalence classes since they can have a rather large
	/// impact on the size of the DFA.
	///
	/// The representation here is 256 booleans, all initially set to false. Each
	/// boolean maps to its corresponding byte based on position. A `true` value
	/// indicates the end of an equivalence class, where its corresponding byte
	/// and all of the bytes corresponding to all previous contiguous `false`
	/// values are in the same equivalence class.
	///
	/// This particular representation only permits contiguous ranges of bytes to
	/// be in the same equivalence class, which means that we can never discover
	/// the true minimal set of equivalence classes.
	#[derive(Debug)]
	pub struct ByteClassBuilder(Vec<bool>);

	impl ByteClassBuilder {
	/// Create a new builder of byte classes where all bytes are part of the
	/// same equivalence class.
	pub fn new() -> ByteClassBuilder {
	ByteClassBuilder(vec![false; 256])
	}

	/// Indicate the the range of byte given (inclusive) can discriminate a
	/// match between it and all other bytes outside of the range.
	pub fn set_range(&mut self, start: u8, end: u8) {
	debug_assert!(start <= end);
	if start > 0 {
	self.0[start as usize - 1] = true;
	}
	self.0[end as usize] = true;
	}

	/// Build byte classes that map all byte values to their corresponding
	/// equivalence class. The last mapping indicates the largest equivalence
	/// class identifier (which is never bigger than 255).
	pub fn build(&self) -> ByteClasses {
	let mut classes = ByteClasses::empty();
	let mut class = 0u8;
	let mut i = 0;
	loop {
	classes.set(i as u8, class as u8);
	if i >= 255 {
	break;
	}
	if self.0[i] {
	class = class.checked_add(1).unwrap();
	}
	i += 1;
	}
	classes
	}
	}

	#[cfg(test)]
	mod tests {
	use super::*;

	#[test]
	fn byte_classes() {
	let mut set = ByteClassBuilder::new();
	set.set_range(b'a', b'z');

	let classes = set.build();
	assert_eq!(classes.get(0), 0);
	assert_eq!(classes.get(1), 0);
	assert_eq!(classes.get(2), 0);
	assert_eq!(classes.get(b'a' - 1), 0);
	assert_eq!(classes.get(b'a'), 1);
	assert_eq!(classes.get(b'm'), 1);
	assert_eq!(classes.get(b'z'), 1);
	assert_eq!(classes.get(b'z' + 1), 2);
	assert_eq!(classes.get(254), 2);
	assert_eq!(classes.get(255), 2);

	let mut set = ByteClassBuilder::new();
	set.set_range(0, 2);
	set.set_range(4, 6);
	let classes = set.build();
	assert_eq!(classes.get(0), 0);
	assert_eq!(classes.get(1), 0);
	assert_eq!(classes.get(2), 0);
	assert_eq!(classes.get(3), 1);
	assert_eq!(classes.get(4), 2);
	assert_eq!(classes.get(5), 2);
	assert_eq!(classes.get(6), 2);
	assert_eq!(classes.get(7), 3);
	assert_eq!(classes.get(255), 3);
	}

	#[test]
	fn full_byte_classes() {
	let mut set = ByteClassBuilder::new();
	for i in 0..256u16 {
	set.set_range(i as u8, i as u8);
	}
	assert_eq!(set.build().alphabet_len(), 256);
	}
	}