diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
commit | 36d22d82aa202bb199967e9512281e9a53db42c9 (patch) | |
tree | 105e8c98ddea1c1e4784a60a5a6410fa416be2de /third_party/rust/phf/src | |
parent | Initial commit. (diff) | |
download | firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.tar.xz firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.zip |
Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/rust/phf/src')
-rw-r--r-- | third_party/rust/phf/src/lib.rs | 157 | ||||
-rw-r--r-- | third_party/rust/phf/src/map.rs | 301 | ||||
-rw-r--r-- | third_party/rust/phf/src/ordered_map.rs | 312 | ||||
-rw-r--r-- | third_party/rust/phf/src/ordered_set.rs | 170 | ||||
-rw-r--r-- | third_party/rust/phf/src/set.rs | 147 |
5 files changed, 1087 insertions, 0 deletions
diff --git a/third_party/rust/phf/src/lib.rs b/third_party/rust/phf/src/lib.rs new file mode 100644 index 0000000000..e60f524b0a --- /dev/null +++ b/third_party/rust/phf/src/lib.rs @@ -0,0 +1,157 @@ +//! Rust-PHF is a library to generate efficient lookup tables at compile time using +//! [perfect hash functions](http://en.wikipedia.org/wiki/Perfect_hash_function). +//! +//! It currently uses the +//! [CHD algorithm](http://cmph.sourceforge.net/papers/esa09.pdf) and can generate +//! a 100,000 entry map in roughly .4 seconds. By default statistics are not +//! produced, but if you set the environment variable `PHF_STATS` it will issue +//! a compiler note about how long it took. +//! +//! MSRV (minimum supported rust version) is Rust 1.46. +//! +//! ## Usage +//! +//! PHF data structures can be constructed via either the procedural +//! macros in the `phf_macros` crate or code generation supported by the +//! `phf_codegen` crate. If you prefer macros, you can easily use them by +//! enabling the `macros` feature of the `phf` crate, like: +//! +//!```toml +//! [dependencies] +//! phf = { version = "0.10", features = ["macros"] } +//! ``` +//! +//! To compile the `phf` crate with a dependency on +//! libcore instead of libstd, enabling use in environments where libstd +//! will not work, set `default-features = false` for the dependency: +//! +//! ```toml +//! [dependencies] +//! # to use `phf` in `no_std` environments +//! phf = { version = "0.10", default-features = false } +//! ``` +//! +//! ## Example (with the `macros` feature enabled) +//! +//! ```rust +//! use phf::phf_map; +//! +//! #[derive(Clone)] +//! pub enum Keyword { +//! Loop, +//! Continue, +//! Break, +//! Fn, +//! Extern, +//! } +//! +//! static KEYWORDS: phf::Map<&'static str, Keyword> = phf_map! { +//! "loop" => Keyword::Loop, +//! "continue" => Keyword::Continue, +//! "break" => Keyword::Break, +//! "fn" => Keyword::Fn, +//! "extern" => Keyword::Extern, +//! }; +//! +//! pub fn parse_keyword(keyword: &str) -> Option<Keyword> { +//! KEYWORDS.get(keyword).cloned() +//! } +//! ``` +//! +//! Alternatively, you can use the [`phf_codegen`] crate to generate PHF datatypes +//! in a build script. +//! +//! [`phf_codegen`]: https://docs.rs/phf_codegen +//! +//! ## Note +//! +//! Currently, the macro syntax has some limitations and may not +//! work as you want. See [#183] or [#196] for example. +//! +//! [#183]: https://github.com/rust-phf/rust-phf/issues/183 +//! [#196]: https://github.com/rust-phf/rust-phf/issues/196 + +#![doc(html_root_url = "https://docs.rs/phf/0.10")] +#![warn(missing_docs)] +#![cfg_attr(not(feature = "std"), no_std)] + +#[cfg(feature = "std")] +extern crate std as core; + +#[cfg(feature = "macros")] +/// Macro to create a `static` (compile-time) [`Map`]. +/// +/// Requires the `macros` feature. +/// +/// Supported key expressions are: +/// - literals: bools, (byte) strings, bytes, chars, and integers (these must have a type suffix) +/// - arrays of `u8` integers +/// - `UniCase::unicode(string)` or `UniCase::ascii(string)` if the `unicase` feature is enabled +/// +/// # Example +/// +/// ``` +/// use phf::{phf_map, Map}; +/// +/// static MY_MAP: Map<&'static str, u32> = phf_map! { +/// "hello" => 1, +/// "world" => 2, +/// }; +/// +/// fn main () { +/// assert_eq!(MY_MAP["hello"], 1); +/// } +/// ``` +#[proc_macro_hack::proc_macro_hack] +pub use phf_macros::phf_map; + +#[cfg(feature = "macros")] +/// Macro to create a `static` (compile-time) [`OrderedMap`]. +/// +/// Requires the `macros` feature. Same usage as [`phf_map`]. +#[proc_macro_hack::proc_macro_hack] +pub use phf_macros::phf_ordered_map; + +#[cfg(feature = "macros")] +/// Macro to create a `static` (compile-time) [`Set`]. +/// +/// Requires the `macros` feature. +/// +/// # Example +/// +/// ``` +/// use phf::{phf_set, Set}; +/// +/// static MY_SET: Set<&'static str> = phf_set! { +/// "hello world", +/// "hola mundo", +/// }; +/// +/// fn main () { +/// assert!(MY_SET.contains("hello world")); +/// } +/// ``` +#[proc_macro_hack::proc_macro_hack] +pub use phf_macros::phf_set; + +#[cfg(feature = "macros")] +/// Macro to create a `static` (compile-time) [`OrderedSet`]. +/// +/// Requires the `macros` feature. Same usage as [`phf_set`]. +#[proc_macro_hack::proc_macro_hack] +pub use phf_macros::phf_ordered_set; + +#[doc(inline)] +pub use self::map::Map; +#[doc(inline)] +pub use self::ordered_map::OrderedMap; +#[doc(inline)] +pub use self::ordered_set::OrderedSet; +#[doc(inline)] +pub use self::set::Set; +pub use phf_shared::PhfHash; + +pub mod map; +pub mod ordered_map; +pub mod ordered_set; +pub mod set; diff --git a/third_party/rust/phf/src/map.rs b/third_party/rust/phf/src/map.rs new file mode 100644 index 0000000000..5b74445c10 --- /dev/null +++ b/third_party/rust/phf/src/map.rs @@ -0,0 +1,301 @@ +//! An immutable map constructed at compile time. +use core::fmt; +use core::iter::FusedIterator; +use core::iter::IntoIterator; +use core::ops::Index; +use core::slice; +use phf_shared::{self, HashKey, PhfBorrow, PhfHash}; +#[cfg(feature = "serde")] +use serde::ser::{Serialize, SerializeMap, Serializer}; + +/// An immutable map constructed at compile time. +/// +/// ## Note +/// +/// The fields of this struct are public so that they may be initialized by the +/// `phf_map!` macro and code generation. They are subject to change at any +/// time and should never be accessed directly. +pub struct Map<K: 'static, V: 'static> { + #[doc(hidden)] + pub key: HashKey, + #[doc(hidden)] + pub disps: &'static [(u32, u32)], + #[doc(hidden)] + pub entries: &'static [(K, V)], +} + +impl<K, V> fmt::Debug for Map<K, V> +where + K: fmt::Debug, + V: fmt::Debug, +{ + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt.debug_map().entries(self.entries()).finish() + } +} + +impl<'a, K, V, T: ?Sized> Index<&'a T> for Map<K, V> +where + T: Eq + PhfHash, + K: PhfBorrow<T>, +{ + type Output = V; + + fn index(&self, k: &'a T) -> &V { + self.get(k).expect("invalid key") + } +} + +impl<K, V> Map<K, V> { + /// Returns the number of entries in the `Map`. + #[inline] + pub const fn len(&self) -> usize { + self.entries.len() + } + + /// Returns true if the `Map` is empty. + #[inline] + pub const fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Determines if `key` is in the `Map`. + pub fn contains_key<T: ?Sized>(&self, key: &T) -> bool + where + T: Eq + PhfHash, + K: PhfBorrow<T>, + { + self.get(key).is_some() + } + + /// Returns a reference to the value that `key` maps to. + pub fn get<T: ?Sized>(&self, key: &T) -> Option<&V> + where + T: Eq + PhfHash, + K: PhfBorrow<T>, + { + self.get_entry(key).map(|e| e.1) + } + + /// Returns a reference to the map's internal static instance of the given + /// key. + /// + /// This can be useful for interning schemes. + pub fn get_key<T: ?Sized>(&self, key: &T) -> Option<&K> + where + T: Eq + PhfHash, + K: PhfBorrow<T>, + { + self.get_entry(key).map(|e| e.0) + } + + /// Like `get`, but returns both the key and the value. + pub fn get_entry<T: ?Sized>(&self, key: &T) -> Option<(&K, &V)> + where + T: Eq + PhfHash, + K: PhfBorrow<T>, + { + if self.disps.is_empty() { + return None; + } //Prevent panic on empty map + let hashes = phf_shared::hash(key, &self.key); + let index = phf_shared::get_index(&hashes, &*self.disps, self.entries.len()); + let entry = &self.entries[index as usize]; + let b: &T = entry.0.borrow(); + if b == key { + Some((&entry.0, &entry.1)) + } else { + None + } + } + + /// Returns an iterator over the key/value pairs in the map. + /// + /// Entries are returned in an arbitrary but fixed order. + pub fn entries(&self) -> Entries<'_, K, V> { + Entries { + iter: self.entries.iter(), + } + } + + /// Returns an iterator over the keys in the map. + /// + /// Keys are returned in an arbitrary but fixed order. + pub fn keys(&self) -> Keys<'_, K, V> { + Keys { + iter: self.entries(), + } + } + + /// Returns an iterator over the values in the map. + /// + /// Values are returned in an arbitrary but fixed order. + pub fn values(&self) -> Values<'_, K, V> { + Values { + iter: self.entries(), + } + } +} + +impl<'a, K, V> IntoIterator for &'a Map<K, V> { + type Item = (&'a K, &'a V); + type IntoIter = Entries<'a, K, V>; + + fn into_iter(self) -> Entries<'a, K, V> { + self.entries() + } +} + +/// An iterator over the key/value pairs in a `Map`. +pub struct Entries<'a, K, V> { + iter: slice::Iter<'a, (K, V)>, +} + +impl<'a, K, V> Clone for Entries<'a, K, V> { + #[inline] + fn clone(&self) -> Self { + Self { + iter: self.iter.clone(), + } + } +} + +impl<'a, K, V> fmt::Debug for Entries<'a, K, V> +where + K: fmt::Debug, + V: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<'a, K, V> Iterator for Entries<'a, K, V> { + type Item = (&'a K, &'a V); + + fn next(&mut self) -> Option<(&'a K, &'a V)> { + self.iter.next().map(|&(ref k, ref v)| (k, v)) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, K, V> DoubleEndedIterator for Entries<'a, K, V> { + fn next_back(&mut self) -> Option<(&'a K, &'a V)> { + self.iter.next_back().map(|e| (&e.0, &e.1)) + } +} + +impl<'a, K, V> ExactSizeIterator for Entries<'a, K, V> {} + +impl<'a, K, V> FusedIterator for Entries<'a, K, V> {} + +/// An iterator over the keys in a `Map`. +pub struct Keys<'a, K, V> { + iter: Entries<'a, K, V>, +} + +impl<'a, K, V> Clone for Keys<'a, K, V> { + #[inline] + fn clone(&self) -> Self { + Self { + iter: self.iter.clone(), + } + } +} + +impl<'a, K, V> fmt::Debug for Keys<'a, K, V> +where + K: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<'a, K, V> Iterator for Keys<'a, K, V> { + type Item = &'a K; + + fn next(&mut self) -> Option<&'a K> { + self.iter.next().map(|e| e.0) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> { + fn next_back(&mut self) -> Option<&'a K> { + self.iter.next_back().map(|e| e.0) + } +} + +impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {} + +impl<'a, K, V> FusedIterator for Keys<'a, K, V> {} + +/// An iterator over the values in a `Map`. +pub struct Values<'a, K, V> { + iter: Entries<'a, K, V>, +} + +impl<'a, K, V> Clone for Values<'a, K, V> { + #[inline] + fn clone(&self) -> Self { + Self { + iter: self.iter.clone(), + } + } +} + +impl<'a, K, V> fmt::Debug for Values<'a, K, V> +where + V: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<'a, K, V> Iterator for Values<'a, K, V> { + type Item = &'a V; + + fn next(&mut self) -> Option<&'a V> { + self.iter.next().map(|e| e.1) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> { + fn next_back(&mut self) -> Option<&'a V> { + self.iter.next_back().map(|e| e.1) + } +} + +impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {} + +impl<'a, K, V> FusedIterator for Values<'a, K, V> {} + +#[cfg(feature = "serde")] +impl<K, V> Serialize for Map<K, V> +where + K: Serialize, + V: Serialize, +{ + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + let mut map = serializer.serialize_map(Some(self.len()))?; + for (k, v) in self.entries() { + map.serialize_entry(k, v)?; + } + map.end() + } +} diff --git a/third_party/rust/phf/src/ordered_map.rs b/third_party/rust/phf/src/ordered_map.rs new file mode 100644 index 0000000000..c8d5ac59bf --- /dev/null +++ b/third_party/rust/phf/src/ordered_map.rs @@ -0,0 +1,312 @@ +//! An order-preserving immutable map constructed at compile time. +use core::fmt; +use core::iter::FusedIterator; +use core::iter::IntoIterator; +use core::ops::Index; +use core::slice; +use phf_shared::{self, HashKey, PhfBorrow, PhfHash}; + +/// An order-preserving immutable map constructed at compile time. +/// +/// Unlike a `Map`, iteration order is guaranteed to match the definition +/// order. +/// +/// ## Note +/// +/// The fields of this struct are public so that they may be initialized by the +/// `phf_ordered_map!` macro and code generation. They are subject to change at +/// any time and should never be accessed directly. +pub struct OrderedMap<K: 'static, V: 'static> { + #[doc(hidden)] + pub key: HashKey, + #[doc(hidden)] + pub disps: &'static [(u32, u32)], + #[doc(hidden)] + pub idxs: &'static [usize], + #[doc(hidden)] + pub entries: &'static [(K, V)], +} + +impl<K, V> fmt::Debug for OrderedMap<K, V> +where + K: fmt::Debug, + V: fmt::Debug, +{ + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt.debug_map().entries(self.entries()).finish() + } +} + +impl<'a, K, V, T: ?Sized> Index<&'a T> for OrderedMap<K, V> +where + T: Eq + PhfHash, + K: PhfBorrow<T>, +{ + type Output = V; + + fn index(&self, k: &'a T) -> &V { + self.get(k).expect("invalid key") + } +} + +impl<K, V> OrderedMap<K, V> { + /// Returns the number of entries in the `OrderedMap`. + #[inline] + pub const fn len(&self) -> usize { + self.entries.len() + } + + /// Returns true if the `OrderedMap` is empty. + #[inline] + pub const fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Returns a reference to the value that `key` maps to. + pub fn get<T: ?Sized>(&self, key: &T) -> Option<&V> + where + T: Eq + PhfHash, + K: PhfBorrow<T>, + { + self.get_entry(key).map(|e| e.1) + } + + /// Returns a reference to the map's internal static instance of the given + /// key. + /// + /// This can be useful for interning schemes. + pub fn get_key<T: ?Sized>(&self, key: &T) -> Option<&K> + where + T: Eq + PhfHash, + K: PhfBorrow<T>, + { + self.get_entry(key).map(|e| e.0) + } + + /// Determines if `key` is in the `OrderedMap`. + pub fn contains_key<T: ?Sized>(&self, key: &T) -> bool + where + T: Eq + PhfHash, + K: PhfBorrow<T>, + { + self.get(key).is_some() + } + + /// Returns the index of the key within the list used to initialize + /// the ordered map. + pub fn get_index<T: ?Sized>(&self, key: &T) -> Option<usize> + where + T: Eq + PhfHash, + K: PhfBorrow<T>, + { + self.get_internal(key).map(|(i, _)| i) + } + + /// Returns references to both the key and values at an index + /// within the list used to initialize the ordered map. See `.get_index(key)`. + pub fn index(&self, index: usize) -> Option<(&K, &V)> { + self.entries.get(index).map(|&(ref k, ref v)| (k, v)) + } + + /// Like `get`, but returns both the key and the value. + pub fn get_entry<T: ?Sized>(&self, key: &T) -> Option<(&K, &V)> + where + T: Eq + PhfHash, + K: PhfBorrow<T>, + { + self.get_internal(key).map(|(_, e)| e) + } + + fn get_internal<T: ?Sized>(&self, key: &T) -> Option<(usize, (&K, &V))> + where + T: Eq + PhfHash, + K: PhfBorrow<T>, + { + if self.disps.is_empty() { + return None; + } //Prevent panic on empty map + let hashes = phf_shared::hash(key, &self.key); + let idx_index = phf_shared::get_index(&hashes, &*self.disps, self.idxs.len()); + let idx = self.idxs[idx_index as usize]; + let entry = &self.entries[idx]; + + let b: &T = entry.0.borrow(); + if b == key { + Some((idx, (&entry.0, &entry.1))) + } else { + None + } + } + + /// Returns an iterator over the key/value pairs in the map. + /// + /// Entries are returned in the same order in which they were defined. + pub fn entries(&self) -> Entries<'_, K, V> { + Entries { + iter: self.entries.iter(), + } + } + + /// Returns an iterator over the keys in the map. + /// + /// Keys are returned in the same order in which they were defined. + pub fn keys(&self) -> Keys<'_, K, V> { + Keys { + iter: self.entries(), + } + } + + /// Returns an iterator over the values in the map. + /// + /// Values are returned in the same order in which they were defined. + pub fn values(&self) -> Values<'_, K, V> { + Values { + iter: self.entries(), + } + } +} + +impl<'a, K, V> IntoIterator for &'a OrderedMap<K, V> { + type Item = (&'a K, &'a V); + type IntoIter = Entries<'a, K, V>; + + fn into_iter(self) -> Entries<'a, K, V> { + self.entries() + } +} + +/// An iterator over the entries in a `OrderedMap`. +pub struct Entries<'a, K, V> { + iter: slice::Iter<'a, (K, V)>, +} + +impl<'a, K, V> Clone for Entries<'a, K, V> { + #[inline] + fn clone(&self) -> Self { + Self { + iter: self.iter.clone(), + } + } +} + +impl<'a, K, V> fmt::Debug for Entries<'a, K, V> +where + K: fmt::Debug, + V: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<'a, K, V> Iterator for Entries<'a, K, V> { + type Item = (&'a K, &'a V); + + fn next(&mut self) -> Option<(&'a K, &'a V)> { + self.iter.next().map(|e| (&e.0, &e.1)) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, K, V> DoubleEndedIterator for Entries<'a, K, V> { + fn next_back(&mut self) -> Option<(&'a K, &'a V)> { + self.iter.next_back().map(|e| (&e.0, &e.1)) + } +} + +impl<'a, K, V> ExactSizeIterator for Entries<'a, K, V> {} + +impl<'a, K, V> FusedIterator for Entries<'a, K, V> {} + +/// An iterator over the keys in a `OrderedMap`. +pub struct Keys<'a, K, V> { + iter: Entries<'a, K, V>, +} + +impl<'a, K, V> Clone for Keys<'a, K, V> { + #[inline] + fn clone(&self) -> Self { + Self { + iter: self.iter.clone(), + } + } +} + +impl<'a, K, V> fmt::Debug for Keys<'a, K, V> +where + K: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<'a, K, V> Iterator for Keys<'a, K, V> { + type Item = &'a K; + + fn next(&mut self) -> Option<&'a K> { + self.iter.next().map(|e| e.0) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> { + fn next_back(&mut self) -> Option<&'a K> { + self.iter.next_back().map(|e| e.0) + } +} + +impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {} + +impl<'a, K, V> FusedIterator for Keys<'a, K, V> {} + +/// An iterator over the values in a `OrderedMap`. +pub struct Values<'a, K, V> { + iter: Entries<'a, K, V>, +} + +impl<'a, K, V> Clone for Values<'a, K, V> { + #[inline] + fn clone(&self) -> Self { + Self { + iter: self.iter.clone(), + } + } +} + +impl<'a, K, V> fmt::Debug for Values<'a, K, V> +where + V: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<'a, K, V> Iterator for Values<'a, K, V> { + type Item = &'a V; + + fn next(&mut self) -> Option<&'a V> { + self.iter.next().map(|e| e.1) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> { + fn next_back(&mut self) -> Option<&'a V> { + self.iter.next_back().map(|e| e.1) + } +} + +impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {} + +impl<'a, K, V> FusedIterator for Values<'a, K, V> {} diff --git a/third_party/rust/phf/src/ordered_set.rs b/third_party/rust/phf/src/ordered_set.rs new file mode 100644 index 0000000000..e85d45711f --- /dev/null +++ b/third_party/rust/phf/src/ordered_set.rs @@ -0,0 +1,170 @@ +//! An order-preserving immutable set constructed at compile time. +use crate::{ordered_map, OrderedMap, PhfHash}; +use core::fmt; +use core::iter::FusedIterator; +use core::iter::IntoIterator; +use phf_shared::PhfBorrow; + +/// An order-preserving immutable set constructed at compile time. +/// +/// Unlike a `Set`, iteration order is guaranteed to match the definition +/// order. +/// +/// ## Note +/// +/// The fields of this struct are public so that they may be initialized by the +/// `phf_ordered_set!` macro and code generation. They are subject to change at +/// any time and should never be accessed directly. +pub struct OrderedSet<T: 'static> { + #[doc(hidden)] + pub map: OrderedMap<T, ()>, +} + +impl<T> fmt::Debug for OrderedSet<T> +where + T: fmt::Debug, +{ + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt.debug_set().entries(self).finish() + } +} + +impl<T> OrderedSet<T> { + /// Returns the number of elements in the `OrderedSet`. + #[inline] + pub const fn len(&self) -> usize { + self.map.len() + } + + /// Returns true if the `OrderedSet` contains no elements. + #[inline] + pub const fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Returns a reference to the set's internal static instance of the given + /// key. + /// + /// This can be useful for interning schemes. + pub fn get_key<U: ?Sized>(&self, key: &U) -> Option<&T> + where + U: Eq + PhfHash, + T: PhfBorrow<U>, + { + self.map.get_key(key) + } + + /// Returns the index of the key within the list used to initialize + /// the ordered set. + pub fn get_index<U: ?Sized>(&self, key: &U) -> Option<usize> + where + U: Eq + PhfHash, + T: PhfBorrow<U>, + { + self.map.get_index(key) + } + + /// Returns a reference to the key at an index + /// within the list used to initialize the ordered set. See `.get_index(key)`. + pub fn index(&self, index: usize) -> Option<&T> { + self.map.index(index).map(|(k, &())| k) + } + + /// Returns true if `value` is in the `OrderedSet`. + pub fn contains<U: ?Sized>(&self, value: &U) -> bool + where + U: Eq + PhfHash, + T: PhfBorrow<U>, + { + self.map.contains_key(value) + } + + /// Returns an iterator over the values in the set. + /// + /// Values are returned in the same order in which they were defined. + pub fn iter(&self) -> Iter<'_, T> { + Iter { + iter: self.map.keys(), + } + } +} + +impl<T> OrderedSet<T> +where + T: Eq + PhfHash + PhfBorrow<T>, +{ + /// Returns true if `other` shares no elements with `self`. + #[inline] + pub fn is_disjoint(&self, other: &OrderedSet<T>) -> bool { + !self.iter().any(|value| other.contains(value)) + } + + /// Returns true if `other` contains all values in `self`. + #[inline] + pub fn is_subset(&self, other: &OrderedSet<T>) -> bool { + self.iter().all(|value| other.contains(value)) + } + + /// Returns true if `self` contains all values in `other`. + #[inline] + pub fn is_superset(&self, other: &OrderedSet<T>) -> bool { + other.is_subset(self) + } +} + +impl<'a, T> IntoIterator for &'a OrderedSet<T> { + type Item = &'a T; + type IntoIter = Iter<'a, T>; + + fn into_iter(self) -> Iter<'a, T> { + self.iter() + } +} + +/// An iterator over the values in a `OrderedSet`. +pub struct Iter<'a, T> { + iter: ordered_map::Keys<'a, T, ()>, +} + +impl<'a, T> Clone for Iter<'a, T> { + #[inline] + fn clone(&self) -> Self { + Self { + iter: self.iter.clone(), + } + } +} + +impl<'a, T> fmt::Debug for Iter<'a, T> +where + T: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = &'a T; + + #[inline] + fn next(&mut self) -> Option<&'a T> { + self.iter.next() + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, T> DoubleEndedIterator for Iter<'a, T> { + #[inline] + fn next_back(&mut self) -> Option<&'a T> { + self.iter.next_back() + } +} + +impl<'a, T> ExactSizeIterator for Iter<'a, T> {} + +impl<'a, T> FusedIterator for Iter<'a, T> {} diff --git a/third_party/rust/phf/src/set.rs b/third_party/rust/phf/src/set.rs new file mode 100644 index 0000000000..d9fdd5bb23 --- /dev/null +++ b/third_party/rust/phf/src/set.rs @@ -0,0 +1,147 @@ +//! An immutable set constructed at compile time. +use core::fmt; +use core::iter::FusedIterator; +use core::iter::IntoIterator; + +use phf_shared::{PhfBorrow, PhfHash}; + +use crate::{map, Map}; + +/// An immutable set constructed at compile time. +/// +/// ## Note +/// +/// The fields of this struct are public so that they may be initialized by the +/// `phf_set!` macro and code generation. They are subject to change at any +/// time and should never be accessed directly. +pub struct Set<T: 'static> { + #[doc(hidden)] + pub map: Map<T, ()>, +} + +impl<T> fmt::Debug for Set<T> +where + T: fmt::Debug, +{ + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt.debug_set().entries(self).finish() + } +} + +impl<T> Set<T> { + /// Returns the number of elements in the `Set`. + #[inline] + pub const fn len(&self) -> usize { + self.map.len() + } + + /// Returns true if the `Set` contains no elements. + #[inline] + pub const fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Returns a reference to the set's internal static instance of the given + /// key. + /// + /// This can be useful for interning schemes. + pub fn get_key<U: ?Sized>(&self, key: &U) -> Option<&T> + where + U: Eq + PhfHash, + T: PhfBorrow<U>, + { + self.map.get_key(key) + } + + /// Returns true if `value` is in the `Set`. + pub fn contains<U: ?Sized>(&self, value: &U) -> bool + where + U: Eq + PhfHash, + T: PhfBorrow<U>, + { + self.map.contains_key(value) + } + + /// Returns an iterator over the values in the set. + /// + /// Values are returned in an arbitrary but fixed order. + pub fn iter(&self) -> Iter<'_, T> { + Iter { + iter: self.map.keys(), + } + } +} + +impl<T> Set<T> +where + T: Eq + PhfHash + PhfBorrow<T>, +{ + /// Returns true if `other` shares no elements with `self`. + pub fn is_disjoint(&self, other: &Set<T>) -> bool { + !self.iter().any(|value| other.contains(value)) + } + + /// Returns true if `other` contains all values in `self`. + pub fn is_subset(&self, other: &Set<T>) -> bool { + self.iter().all(|value| other.contains(value)) + } + + /// Returns true if `self` contains all values in `other`. + pub fn is_superset(&self, other: &Set<T>) -> bool { + other.is_subset(self) + } +} + +impl<'a, T> IntoIterator for &'a Set<T> { + type Item = &'a T; + type IntoIter = Iter<'a, T>; + + fn into_iter(self) -> Iter<'a, T> { + self.iter() + } +} + +/// An iterator over the values in a `Set`. +pub struct Iter<'a, T: 'static> { + iter: map::Keys<'a, T, ()>, +} + +impl<'a, T> Clone for Iter<'a, T> { + #[inline] + fn clone(&self) -> Self { + Self { + iter: self.iter.clone(), + } + } +} + +impl<'a, T> fmt::Debug for Iter<'a, T> +where + T: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = &'a T; + + fn next(&mut self) -> Option<&'a T> { + self.iter.next() + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, T> DoubleEndedIterator for Iter<'a, T> { + fn next_back(&mut self) -> Option<&'a T> { + self.iter.next_back() + } +} + +impl<'a, T> ExactSizeIterator for Iter<'a, T> {} + +impl<'a, T> FusedIterator for Iter<'a, T> {} |