Auto merge of #100869 - nnethercote:replace-ThinVec, r=spastorino

Replace `rustc_data_structures::thin_vec::ThinVec` with `thin_vec::ThinVec`

`rustc_data_structures::thin_vec::ThinVec` looks like this:
```
pub struct ThinVec<T>(Option<Box<Vec<T>>>);
```
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<TypeBinding>` rather than a `&[TypeBinding]`, because this
  avoid some unnecessary allocations.

r? `@spastorino`

5 files changed, 13 insertions, 235 deletions

diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml
index 5c641f54f68..2d8658db5e6 100644
--- a/compiler/rustc_data_structures/Cargo.toml
+++ b/compiler/rustc_data_structures/Cargo.toml
@@ -8,25 +8,26 @@ doctest = false
 
 [dependencies]
 arrayvec = { version = "0.7", default-features = false }
+bitflags = "1.2.1"
+cfg-if = "0.1.2"
 ena = "0.14"
 indexmap = { version = "1.9.1" }
-tracing = "0.1"
 jobserver_crate = { version = "0.1.13", package = "jobserver" }
-rustc_serialize = { path = "../rustc_serialize" }
-rustc_macros = { path = "../rustc_macros" }
-rustc_graphviz = { path = "../rustc_graphviz" }
-cfg-if = "0.1.2"
-stable_deref_trait = "1.0.0"
-rayon = { version = "0.4.0", package = "rustc-rayon", optional = true }
+libc = "0.2"
+measureme = "10.0.0"
 rayon-core = { version = "0.4.0", package = "rustc-rayon-core", optional = true }
+rayon = { version = "0.4.0", package = "rustc-rayon", optional = true }
+rustc_graphviz = { path = "../rustc_graphviz" }
 rustc-hash = "1.1.0"
-smallvec = { version = "1.8.1", features = ["const_generics", "union", "may_dangle"] }
 rustc_index = { path = "../rustc_index", package = "rustc_index" }
-bitflags = "1.2.1"
-measureme = "10.0.0"
-libc = "0.2"
+rustc_macros = { path = "../rustc_macros" }
+rustc_serialize = { path = "../rustc_serialize" }
+smallvec = { version = "1.8.1", features = ["const_generics", "union", "may_dangle"] }
+stable_deref_trait = "1.0.0"
 stacker = "0.1.14"
 tempfile = "3.2"
+thin-vec = "0.2.8"
+tracing = "0.1"
 
 [dependencies.parking_lot]
 version = "0.11"
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<T>: Sized {
     fn map_in_place<F>(&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<Box<..>>` 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<T>(Option<Box<Vec<T>>>);
-
-impl<T> ThinVec<T> {
-    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<T> From<Vec<T>> for ThinVec<T> {
-    fn from(vec: Vec<T>) -> Self {
-        if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) }
-    }
-}
-
-impl<T> Into<Vec<T>> for ThinVec<T> {
-    fn into(self) -> Vec<T> {
-        match self {
-            ThinVec(None) => Vec::new(),
-            ThinVec(Some(vec)) => *vec,
-        }
-    }
-}
-
-impl<T> ::std::ops::Deref for ThinVec<T> {
-    type Target = [T];
-    fn deref(&self) -> &[T] {
-        match *self {
-            ThinVec(None) => &[],
-            ThinVec(Some(ref vec)) => vec,
-        }
-    }
-}
-
-impl<T> ::std::ops::DerefMut for ThinVec<T> {
-    fn deref_mut(&mut self) -> &mut [T] {
-        match *self {
-            ThinVec(None) => &mut [],
-            ThinVec(Some(ref mut vec)) => vec,
-        }
-    }
-}
-
-impl<T> FromIterator<T> for ThinVec<T> {
-    fn from_iter<I: IntoIterator<Item = T>>(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<T> IntoIterator for ThinVec<T> {
-    type Item = T;
-    type IntoIter = std::vec::IntoIter<T>;
-
-    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<T> {
-    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<T> {
-    type Item = &'a mut T;
-    type IntoIter = std::slice::IterMut<'a, T>;
-
-    fn into_iter(self) -> Self::IntoIter {
-        self.as_mut().iter_mut()
-    }
-}
-
-impl<T> Extend<T> for ThinVec<T> {
-    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
-        match *self {
-            ThinVec(Some(ref mut vec)) => vec.extend(iter),
-            ThinVec(None) => *self = iter.into_iter().collect::<Vec<_>>().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<T: HashStable<CTX>, CTX> HashStable<CTX> for ThinVec<T> {
-    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
-        (**self).hash_stable(hcx, hasher)
-    }
-}
-
-impl<T> Default for ThinVec<T> {
-    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<T> ThinVec<T> {
-    fn into_vec(self) -> Vec<T> {
-        self.into()
-    }
-}
-
-#[test]
-fn test_from_iterator() {
-    assert_eq!(std::iter::empty().collect::<ThinVec<String>>().into_vec(), Vec::<String>::new());
-    assert_eq!(std::iter::once(42).collect::<ThinVec<_>>().into_vec(), vec![42]);
-    assert_eq!([1, 2].into_iter().collect::<ThinVec<_>>().into_vec(), vec![1, 2]);
-    assert_eq!([1, 2, 3].into_iter().collect::<ThinVec<_>>().into_vec(), vec![1, 2, 3]);
-}
-
-#[test]
-fn test_into_iterator_owned() {
-    assert_eq!(ThinVec::new().into_iter().collect::<Vec<String>>(), Vec::<String>::new());
-    assert_eq!(ThinVec::from(vec![1]).into_iter().collect::<Vec<_>>(), vec![1]);
-    assert_eq!(ThinVec::from(vec![1, 2]).into_iter().collect::<Vec<_>>(), vec![1, 2]);
-    assert_eq!(ThinVec::from(vec![1, 2, 3]).into_iter().collect::<Vec<_>>(), vec![1, 2, 3]);
-}
-
-#[test]
-fn test_into_iterator_ref() {
-    assert_eq!(ThinVec::new().iter().collect::<Vec<&String>>(), Vec::<&String>::new());
-    assert_eq!(ThinVec::from(vec![1]).iter().collect::<Vec<_>>(), vec![&1]);
-    assert_eq!(ThinVec::from(vec![1, 2]).iter().collect::<Vec<_>>(), vec![&1, &2]);
-    assert_eq!(ThinVec::from(vec![1, 2, 3]).iter().collect::<Vec<_>>(), vec![&1, &2, &3]);
-}
-
-#[test]
-fn test_into_iterator_ref_mut() {
-    assert_eq!(ThinVec::new().iter_mut().collect::<Vec<&mut String>>(), Vec::<&mut String>::new());
-    assert_eq!(ThinVec::from(vec![1]).iter_mut().collect::<Vec<_>>(), vec![&mut 1]);
-    assert_eq!(ThinVec::from(vec![1, 2]).iter_mut().collect::<Vec<_>>(), vec![&mut 1, &mut 2]);
-    assert_eq!(
-        ThinVec::from(vec![1, 2, 3]).iter_mut().collect::<Vec<_>>(),
-        vec![&mut 1, &mut 2, &mut 3],
-    );
-}