From aa7024b0c7034c75d36ebe9048d12480c8d0bae2 Mon Sep 17 00:00:00 2001 From: Santiago Pastorino Date: Fri, 4 Jun 2021 10:05:27 -0300 Subject: Add VecMap to rustc_data_structures --- compiler/rustc_data_structures/src/lib.rs | 1 + compiler/rustc_data_structures/src/vec_map.rs | 137 +++++++++++++++++++++ .../rustc_data_structures/src/vec_map/tests.rs | 48 ++++++++ 3 files changed, 186 insertions(+) create mode 100644 compiler/rustc_data_structures/src/vec_map.rs create mode 100644 compiler/rustc_data_structures/src/vec_map/tests.rs (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs index a8b9f479f1e..bbfe225e23e 100644 --- a/compiler/rustc_data_structures/src/lib.rs +++ b/compiler/rustc_data_structures/src/lib.rs @@ -96,6 +96,7 @@ pub mod thin_vec; pub mod tiny_list; pub mod transitive_relation; pub mod vec_linked_list; +pub mod vec_map; pub mod work_queue; pub use atomic_ref::AtomicRef; pub mod frozen; diff --git a/compiler/rustc_data_structures/src/vec_map.rs b/compiler/rustc_data_structures/src/vec_map.rs new file mode 100644 index 00000000000..eca4ff212ac --- /dev/null +++ b/compiler/rustc_data_structures/src/vec_map.rs @@ -0,0 +1,137 @@ +use std::borrow::Borrow; +use std::iter::FromIterator; +use std::slice::{Iter, IterMut}; +use std::vec::IntoIter; + +use crate::stable_hasher::{HashStable, StableHasher}; + +#[derive(Clone, Encodable, Decodable, Debug)] +pub struct VecMap(Vec<(K, V)>); + +impl VecMap +where + K: PartialEq, +{ + pub fn new() -> Self { + VecMap(Default::default()) + } + + pub fn insert(&mut self, k: K, v: V) -> Option { + if let Some(elem) = self.0.iter_mut().find(|(key, _)| *key == k) { + Some(std::mem::replace(&mut elem.1, v)) + } else { + self.0.push((k, v)); + None + } + } + + pub fn get(&self, k: &Q) -> Option<&V> + where + K: Borrow, + Q: Eq, + { + self.0.iter().find(|(key, _)| k == key.borrow()).map(|elem| &elem.1) + } + + pub fn contains_key(&self, k: &Q) -> bool + where + K: Borrow, + Q: Eq, + { + self.get(k).is_some() + } + + pub fn is_empty(&self) -> bool { + self.0.is_empty() + } + + pub fn iter(&self) -> Iter<'_, (K, V)> { + self.into_iter() + } + + pub fn iter_mut(&mut self) -> IterMut<'_, (K, V)> { + self.into_iter() + } +} + +impl Default for VecMap { + #[inline] + fn default() -> Self { + Self(Default::default()) + } +} + +impl From> for VecMap { + fn from(vec: Vec<(K, V)>) -> Self { + Self(vec) + } +} + +impl Into> for VecMap { + fn into(self) -> Vec<(K, V)> { + self.0 + } +} + +impl FromIterator<(K, V)> for VecMap { + fn from_iter>(iter: I) -> Self { + Self(iter.into_iter().collect()) + } +} + +impl<'a, K, V> IntoIterator for &'a VecMap { + type Item = &'a (K, V); + type IntoIter = Iter<'a, (K, V)>; + + #[inline] + fn into_iter(self) -> Self::IntoIter { + self.0.iter() + } +} + +impl<'a, K, V> IntoIterator for &'a mut VecMap { + type Item = &'a mut (K, V); + type IntoIter = IterMut<'a, (K, V)>; + + #[inline] + fn into_iter(self) -> Self::IntoIter { + self.0.iter_mut() + } +} + +impl IntoIterator for VecMap { + type Item = (K, V); + type IntoIter = IntoIter<(K, V)>; + + #[inline] + fn into_iter(self) -> Self::IntoIter { + self.0.into_iter() + } +} + +impl Extend<(K, V)> for VecMap { + fn extend>(&mut self, iter: I) { + self.0.extend(iter); + } + + fn extend_one(&mut self, item: (K, V)) { + self.0.extend_one(item); + } + + fn extend_reserve(&mut self, additional: usize) { + self.0.extend_reserve(additional); + } +} + +impl HashStable for VecMap +where + K: HashStable + Eq, + V: HashStable, +{ + fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { + self.0.hash_stable(hcx, hasher) + } +} + +#[cfg(test)] +mod tests; diff --git a/compiler/rustc_data_structures/src/vec_map/tests.rs b/compiler/rustc_data_structures/src/vec_map/tests.rs new file mode 100644 index 00000000000..9083de85982 --- /dev/null +++ b/compiler/rustc_data_structures/src/vec_map/tests.rs @@ -0,0 +1,48 @@ +use super::*; + +impl VecMap { + fn into_vec(self) -> Vec<(K, V)> { + self.0.into() + } +} + +#[test] +fn test_from_iterator() { + assert_eq!( + std::iter::empty().collect::>().into_vec(), + Vec::<(i32, bool)>::new() + ); + assert_eq!(std::iter::once((42, true)).collect::>().into_vec(), vec![(42, true)]); + assert_eq!( + vec![(1, true), (2, false)].into_iter().collect::>().into_vec(), + vec![(1, true), (2, false)] + ); +} + +#[test] +fn test_into_iterator_owned() { + assert_eq!(VecMap::new().into_iter().collect::>(), Vec::<(i32, bool)>::new()); + assert_eq!(VecMap::from(vec![(1, true)]).into_iter().collect::>(), vec![(1, true)]); + assert_eq!( + VecMap::from(vec![(1, true), (2, false)]).into_iter().collect::>(), + vec![(1, true), (2, false)] + ); +} + +#[test] +fn test_insert() { + let mut v = VecMap::new(); + assert_eq!(v.insert(1, true), None); + assert_eq!(v.insert(2, false), None); + assert_eq!(v.clone().into_vec(), vec![(1, true), (2, false)]); + assert_eq!(v.insert(1, false), Some(true)); + assert_eq!(v.into_vec(), vec![(1, false), (2, false)]); +} + +#[test] +fn test_get() { + let v = vec![(1, true), (2, false)].into_iter().collect::>(); + assert_eq!(v.get(&1), Some(&true)); + assert_eq!(v.get(&2), Some(&false)); + assert_eq!(v.get(&3), None); +} -- cgit 1.4.1-3-g733a5 From dd56ec653cec248fb532fc295e1c40271238cffc Mon Sep 17 00:00:00 2001 From: Santiago Pastorino Date: Tue, 8 Jun 2021 09:40:58 -0300 Subject: Add VecMap::get_by(FnMut -> bool) --- compiler/rustc_data_structures/src/vec_map.rs | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/vec_map.rs b/compiler/rustc_data_structures/src/vec_map.rs index eca4ff212ac..fef570c786b 100644 --- a/compiler/rustc_data_structures/src/vec_map.rs +++ b/compiler/rustc_data_structures/src/vec_map.rs @@ -33,6 +33,13 @@ where self.0.iter().find(|(key, _)| k == key.borrow()).map(|elem| &elem.1) } + pub fn get_by

(&self, predicate: P) -> Option<&V> + where + for<'b> P: FnMut(&'b &(K, V)) -> bool, + { + self.0.iter().find(predicate).map(|elem| &elem.1) + } + pub fn contains_key(&self, k: &Q) -> bool where K: Borrow, -- cgit 1.4.1-3-g733a5 From ed94da14ed19c20baf8912c69b427fe910bf5d5f Mon Sep 17 00:00:00 2001 From: Santiago Pastorino Date: Tue, 8 Jun 2021 16:50:33 -0300 Subject: Explicitly pass find arguments down the predicate so coercions can apply --- compiler/rustc_data_structures/src/vec_map.rs | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/vec_map.rs b/compiler/rustc_data_structures/src/vec_map.rs index fef570c786b..81d7fe3f6bd 100644 --- a/compiler/rustc_data_structures/src/vec_map.rs +++ b/compiler/rustc_data_structures/src/vec_map.rs @@ -33,11 +33,11 @@ where self.0.iter().find(|(key, _)| k == key.borrow()).map(|elem| &elem.1) } - pub fn get_by

(&self, predicate: P) -> Option<&V> + pub fn get_by

(&self, mut predicate: P) -> Option<&V> where for<'b> P: FnMut(&'b &(K, V)) -> bool, { - self.0.iter().find(predicate).map(|elem| &elem.1) + self.0.iter().find(|kv| predicate(kv)).map(|elem| &elem.1) } pub fn contains_key(&self, k: &Q) -> bool -- cgit 1.4.1-3-g733a5 From cad762b1e24e350af3422b50b81e8b4e3b8393a0 Mon Sep 17 00:00:00 2001 From: Santiago Pastorino Date: Tue, 8 Jun 2021 16:52:33 -0300 Subject: Use impl FnMut directly as predicate type --- compiler/rustc_data_structures/src/vec_map.rs | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/vec_map.rs b/compiler/rustc_data_structures/src/vec_map.rs index 81d7fe3f6bd..ceafdbbce26 100644 --- a/compiler/rustc_data_structures/src/vec_map.rs +++ b/compiler/rustc_data_structures/src/vec_map.rs @@ -33,10 +33,7 @@ where self.0.iter().find(|(key, _)| k == key.borrow()).map(|elem| &elem.1) } - pub fn get_by

(&self, mut predicate: P) -> Option<&V> - where - for<'b> P: FnMut(&'b &(K, V)) -> bool, - { + pub fn get_by(&self, mut predicate: impl FnMut(&(K, V)) -> bool) -> Option<&V> { self.0.iter().find(|kv| predicate(kv)).map(|elem| &elem.1) } -- cgit 1.4.1-3-g733a5 From 7b1e1c73330ca9ce7ad00f7a1d61ba393ea187b1 Mon Sep 17 00:00:00 2001 From: Santiago Pastorino Date: Tue, 8 Jun 2021 17:16:05 -0300 Subject: add VecMap docs --- compiler/rustc_data_structures/src/vec_map.rs | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/vec_map.rs b/compiler/rustc_data_structures/src/vec_map.rs index ceafdbbce26..73b04d3329c 100644 --- a/compiler/rustc_data_structures/src/vec_map.rs +++ b/compiler/rustc_data_structures/src/vec_map.rs @@ -5,6 +5,8 @@ use std::vec::IntoIter; use crate::stable_hasher::{HashStable, StableHasher}; +/// A map type implemented as a vector of pairs `K` (key) and `V` (value). +/// It currently provides a subset of all the map operations, the rest could be added as needed. #[derive(Clone, Encodable, Decodable, Debug)] pub struct VecMap(Vec<(K, V)>); @@ -16,6 +18,7 @@ where VecMap(Default::default()) } + /// Sets the value of the entry, and returns the entry's old value. pub fn insert(&mut self, k: K, v: V) -> Option { if let Some(elem) = self.0.iter_mut().find(|(key, _)| *key == k) { Some(std::mem::replace(&mut elem.1, v)) @@ -25,6 +28,7 @@ where } } + /// Gets a reference to the value in the entry. pub fn get(&self, k: &Q) -> Option<&V> where K: Borrow, @@ -33,10 +37,19 @@ where self.0.iter().find(|(key, _)| k == key.borrow()).map(|elem| &elem.1) } + /// Returns the value corresponding to the supplied predicate filter. + /// + /// The supplied predicate will be applied to each (key, value) pair and it will return a + /// reference to the values where the predicate returns `true`. pub fn get_by(&self, mut predicate: impl FnMut(&(K, V)) -> bool) -> Option<&V> { self.0.iter().find(|kv| predicate(kv)).map(|elem| &elem.1) } + /// Returns `true` if the map contains a value for the specified key. + /// + /// The key may be any borrowed form of the map's key type, + /// [`Eq`] on the borrowed form *must* match those for + /// the key type. pub fn contains_key(&self, k: &Q) -> bool where K: Borrow, @@ -45,6 +58,7 @@ where self.get(k).is_some() } + /// Returns `true` if the map contains no elements. pub fn is_empty(&self) -> bool { self.0.is_empty() } -- cgit 1.4.1-3-g733a5