From b38106b6d8478fbfbded5403ee31c056c71cef48 Mon Sep 17 00:00:00 2001 From: Nicholas Nethercote Date: Wed, 17 Aug 2022 14:22:30 +1000 Subject: Replace `rustc_data_structures::thin_vec::ThinVec` with `thin_vec::ThinVec`. `rustc_data_structures::thin_vec::ThinVec` looks like this: ``` pub struct ThinVec(Option>>); ``` It's just a zero word if the vector is empty, but requires two allocations if it is non-empty. So it's only usable in cases where the vector is empty most of the time. This commit removes it in favour of `thin_vec::ThinVec`, which is also word-sized, but stores the length and capacity in the same allocation as the elements. It's good in a wider variety of situation, e.g. in enum variants where the vector is usually/always non-empty. The commit also: - Sorts some `Cargo.toml` dependency lists, to make additions easier. - Sorts some `use` item lists, to make additions easier. - Changes `clean_trait_ref_with_bindings` to take a `ThinVec` rather than a `&[TypeBinding]`, because this avoid some unnecessary allocations. --- compiler/rustc_data_structures/src/lib.rs | 1 - compiler/rustc_data_structures/src/map_in_place.rs | 2 +- compiler/rustc_data_structures/src/thin_vec.rs | 180 --------------------- .../rustc_data_structures/src/thin_vec/tests.rs | 42 ----- 4 files changed, 1 insertion(+), 224 deletions(-) delete mode 100644 compiler/rustc_data_structures/src/thin_vec.rs delete mode 100644 compiler/rustc_data_structures/src/thin_vec/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 c8b09cffe01..a7429ed008f 100644 --- a/compiler/rustc_data_structures/src/lib.rs +++ b/compiler/rustc_data_structures/src/lib.rs @@ -75,7 +75,6 @@ pub mod profiling; pub mod sharded; pub mod stack; pub mod sync; -pub mod thin_vec; pub mod tiny_list; pub mod transitive_relation; pub mod vec_linked_list; diff --git a/compiler/rustc_data_structures/src/map_in_place.rs b/compiler/rustc_data_structures/src/map_in_place.rs index d912211443a..a0d4b7ade1f 100644 --- a/compiler/rustc_data_structures/src/map_in_place.rs +++ b/compiler/rustc_data_structures/src/map_in_place.rs @@ -1,6 +1,6 @@ -use crate::thin_vec::ThinVec; use smallvec::{Array, SmallVec}; use std::ptr; +use thin_vec::ThinVec; pub trait MapInPlace: Sized { fn map_in_place(&mut self, mut f: F) diff --git a/compiler/rustc_data_structures/src/thin_vec.rs b/compiler/rustc_data_structures/src/thin_vec.rs deleted file mode 100644 index fce42e709ab..00000000000 --- a/compiler/rustc_data_structures/src/thin_vec.rs +++ /dev/null @@ -1,180 +0,0 @@ -use crate::stable_hasher::{HashStable, StableHasher}; - -use std::iter::FromIterator; - -/// A vector type optimized for cases where this size is usually 0 (cf. `SmallVec`). -/// The `Option>` wrapping allows us to represent a zero sized vector with `None`, -/// which uses only a single (null) pointer. -#[derive(Clone, Encodable, Decodable, Debug, Hash, Eq, PartialEq)] -pub struct ThinVec(Option>>); - -impl ThinVec { - pub fn new() -> Self { - ThinVec(None) - } - - pub fn iter(&self) -> std::slice::Iter<'_, T> { - self.into_iter() - } - - pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, T> { - self.into_iter() - } - - pub fn push(&mut self, item: T) { - match *self { - ThinVec(Some(ref mut vec)) => vec.push(item), - ThinVec(None) => *self = vec![item].into(), - } - } - - /// Note: if `set_len(0)` is called on a non-empty `ThinVec`, it will - /// remain in the `Some` form. This is required for some code sequences - /// (such as the one in `flat_map_in_place`) that call `set_len(0)` before - /// an operation that might panic, and then call `set_len(n)` again - /// afterwards. - pub unsafe fn set_len(&mut self, new_len: usize) { - match *self { - ThinVec(None) => { - // A prerequisite of `Vec::set_len` is that `new_len` must be - // less than or equal to capacity(). The same applies here. - if new_len != 0 { - panic!("unsafe ThinVec::set_len({})", new_len); - } - } - ThinVec(Some(ref mut vec)) => vec.set_len(new_len), - } - } - - pub fn insert(&mut self, index: usize, value: T) { - match *self { - ThinVec(None) => { - if index == 0 { - *self = vec![value].into(); - } else { - panic!("invalid ThinVec::insert"); - } - } - ThinVec(Some(ref mut vec)) => vec.insert(index, value), - } - } - - pub fn remove(&mut self, index: usize) -> T { - match self { - ThinVec(None) => panic!("invalid ThinVec::remove"), - ThinVec(Some(vec)) => vec.remove(index), - } - } - - pub fn as_slice(&self) -> &[T] { - match self { - ThinVec(None) => &[], - ThinVec(Some(vec)) => vec.as_slice(), - } - } -} - -impl From> for ThinVec { - fn from(vec: Vec) -> Self { - if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) } - } -} - -impl Into> for ThinVec { - fn into(self) -> Vec { - match self { - ThinVec(None) => Vec::new(), - ThinVec(Some(vec)) => *vec, - } - } -} - -impl ::std::ops::Deref for ThinVec { - type Target = [T]; - fn deref(&self) -> &[T] { - match *self { - ThinVec(None) => &[], - ThinVec(Some(ref vec)) => vec, - } - } -} - -impl ::std::ops::DerefMut for ThinVec { - fn deref_mut(&mut self) -> &mut [T] { - match *self { - ThinVec(None) => &mut [], - ThinVec(Some(ref mut vec)) => vec, - } - } -} - -impl FromIterator for ThinVec { - fn from_iter>(iter: I) -> Self { - // `Vec::from_iter()` should not allocate if the iterator is empty. - let vec: Vec<_> = iter.into_iter().collect(); - if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) } - } -} - -impl IntoIterator for ThinVec { - type Item = T; - type IntoIter = std::vec::IntoIter; - - fn into_iter(self) -> Self::IntoIter { - // This is still performant because `Vec::new()` does not allocate. - self.0.map_or_else(Vec::new, |ptr| *ptr).into_iter() - } -} - -impl<'a, T> IntoIterator for &'a ThinVec { - type Item = &'a T; - type IntoIter = std::slice::Iter<'a, T>; - - fn into_iter(self) -> Self::IntoIter { - self.as_ref().iter() - } -} - -impl<'a, T> IntoIterator for &'a mut ThinVec { - type Item = &'a mut T; - type IntoIter = std::slice::IterMut<'a, T>; - - fn into_iter(self) -> Self::IntoIter { - self.as_mut().iter_mut() - } -} - -impl Extend for ThinVec { - fn extend>(&mut self, iter: I) { - match *self { - ThinVec(Some(ref mut vec)) => vec.extend(iter), - ThinVec(None) => *self = iter.into_iter().collect::>().into(), - } - } - - fn extend_one(&mut self, item: T) { - self.push(item) - } - - fn extend_reserve(&mut self, additional: usize) { - match *self { - ThinVec(Some(ref mut vec)) => vec.reserve(additional), - ThinVec(None) => *self = Vec::with_capacity(additional).into(), - } - } -} - -impl, CTX> HashStable for ThinVec { - fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { - (**self).hash_stable(hcx, hasher) - } -} - -impl Default for ThinVec { - fn default() -> Self { - Self(None) - } -} - -#[cfg(test)] -mod tests; diff --git a/compiler/rustc_data_structures/src/thin_vec/tests.rs b/compiler/rustc_data_structures/src/thin_vec/tests.rs deleted file mode 100644 index 0221b9912bb..00000000000 --- a/compiler/rustc_data_structures/src/thin_vec/tests.rs +++ /dev/null @@ -1,42 +0,0 @@ -use super::*; - -impl ThinVec { - fn into_vec(self) -> Vec { - self.into() - } -} - -#[test] -fn test_from_iterator() { - assert_eq!(std::iter::empty().collect::>().into_vec(), Vec::::new()); - assert_eq!(std::iter::once(42).collect::>().into_vec(), vec![42]); - assert_eq!([1, 2].into_iter().collect::>().into_vec(), vec![1, 2]); - assert_eq!([1, 2, 3].into_iter().collect::>().into_vec(), vec![1, 2, 3]); -} - -#[test] -fn test_into_iterator_owned() { - assert_eq!(ThinVec::new().into_iter().collect::>(), Vec::::new()); - assert_eq!(ThinVec::from(vec![1]).into_iter().collect::>(), vec![1]); - assert_eq!(ThinVec::from(vec![1, 2]).into_iter().collect::>(), vec![1, 2]); - assert_eq!(ThinVec::from(vec![1, 2, 3]).into_iter().collect::>(), vec![1, 2, 3]); -} - -#[test] -fn test_into_iterator_ref() { - assert_eq!(ThinVec::new().iter().collect::>(), Vec::<&String>::new()); - assert_eq!(ThinVec::from(vec![1]).iter().collect::>(), vec![&1]); - assert_eq!(ThinVec::from(vec![1, 2]).iter().collect::>(), vec![&1, &2]); - assert_eq!(ThinVec::from(vec![1, 2, 3]).iter().collect::>(), vec![&1, &2, &3]); -} - -#[test] -fn test_into_iterator_ref_mut() { - assert_eq!(ThinVec::new().iter_mut().collect::>(), Vec::<&mut String>::new()); - assert_eq!(ThinVec::from(vec![1]).iter_mut().collect::>(), vec![&mut 1]); - assert_eq!(ThinVec::from(vec![1, 2]).iter_mut().collect::>(), vec![&mut 1, &mut 2]); - assert_eq!( - ThinVec::from(vec![1, 2, 3]).iter_mut().collect::>(), - vec![&mut 1, &mut 2, &mut 3], - ); -} -- cgit 1.4.1-3-g733a5