Remove `TinyList`.

It is optimized for lists with a single element, avoiding the need for
an allocation in that case. But `SmallVec<[T; 1]>` also avoids the
allocation, and is better in general: more standard, log2 number of
allocations if the list exceeds one item, and a much more capable API.

This commit removes `TinyList` and converts the two uses to
`SmallVec<[T; 1]>`. It also reorders the `use` items in the relevant
file so they are in just two sections (`pub` and non-`pub`), ordered
alphabetically, instead of many sections. (This is a relevant part of
the change because I had to decide where to add a `use` item for
`SmallVec`.)

4 files changed, 8 insertions, 245 deletions

diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs
index b455cbeded9..2e5f3806b12 100644
--- a/compiler/rustc_data_structures/src/lib.rs
+++ b/compiler/rustc_data_structures/src/lib.rs
@@ -82,7 +82,6 @@ pub mod svh;
 pub mod sync;
 pub mod tagged_ptr;
 pub mod temp_dir;
-pub mod tiny_list;
 pub mod transitive_relation;
 pub mod unhash;
 pub mod unord;
diff --git a/compiler/rustc_data_structures/src/tiny_list.rs b/compiler/rustc_data_structures/src/tiny_list.rs
deleted file mode 100644
index 11a408f216a..00000000000
--- a/compiler/rustc_data_structures/src/tiny_list.rs
+++ /dev/null
@@ -1,80 +0,0 @@
-//! A singly-linked list.
-//!
-//! Using this data structure only makes sense under very specific
-//! circumstances:
-//!
-//! - If you have a list that rarely stores more than one element, then this
-//!   data-structure can store the element without allocating and only uses as
-//!   much space as an `Option<(T, usize)>`. If T can double as the `Option`
-//!   discriminant, it will even only be as large as `T, usize`.
-//!
-//! If you expect to store more than 1 element in the common case, steer clear
-//! and use a `Vec<T>`, `Box<[T]>`, or a `SmallVec<T>`.
-
-#[cfg(test)]
-mod tests;
-
-#[derive(Clone)]
-pub struct TinyList<T> {
-    head: Option<Element<T>>,
-}
-
-impl<T: PartialEq> TinyList<T> {
-    #[inline]
-    pub fn new() -> TinyList<T> {
-        TinyList { head: None }
-    }
-
-    #[inline]
-    pub fn new_single(data: T) -> TinyList<T> {
-        TinyList { head: Some(Element { data, next: None }) }
-    }
-
-    #[inline]
-    pub fn insert(&mut self, data: T) {
-        self.head = Some(Element { data, next: self.head.take().map(Box::new) });
-    }
-
-    #[inline]
-    pub fn remove(&mut self, data: &T) -> bool {
-        self.head = match &mut self.head {
-            Some(head) if head.data == *data => head.next.take().map(|x| *x),
-            Some(head) => return head.remove_next(data),
-            None => return false,
-        };
-        true
-    }
-
-    #[inline]
-    pub fn contains(&self, data: &T) -> bool {
-        let mut elem = self.head.as_ref();
-        while let Some(e) = elem {
-            if &e.data == data {
-                return true;
-            }
-            elem = e.next.as_deref();
-        }
-        false
-    }
-}
-
-#[derive(Clone)]
-struct Element<T> {
-    data: T,
-    next: Option<Box<Element<T>>>,
-}
-
-impl<T: PartialEq> Element<T> {
-    fn remove_next(mut self: &mut Self, data: &T) -> bool {
-        loop {
-            match self.next {
-                Some(ref mut next) if next.data == *data => {
-                    self.next = next.next.take();
-                    return true;
-                }
-                Some(ref mut next) => self = next,
-                None => return false,
-            }
-        }
-    }
-}
diff --git a/compiler/rustc_data_structures/src/tiny_list/tests.rs b/compiler/rustc_data_structures/src/tiny_list/tests.rs
deleted file mode 100644
index 4b95e62bef0..00000000000
--- a/compiler/rustc_data_structures/src/tiny_list/tests.rs
+++ /dev/null
@@ -1,155 +0,0 @@
-use super::*;
-
-extern crate test;
-use test::{black_box, Bencher};
-
-impl<T> TinyList<T> {
-    fn len(&self) -> usize {
-        let (mut elem, mut count) = (self.head.as_ref(), 0);
-        while let Some(e) = elem {
-            count += 1;
-            elem = e.next.as_deref();
-        }
-        count
-    }
-}
-
-#[test]
-fn test_contains_and_insert() {
-    fn do_insert(i: u32) -> bool {
-        i % 2 == 0
-    }
-
-    let mut list = TinyList::new();
-
-    for i in 0..10 {
-        for j in 0..i {
-            if do_insert(j) {
-                assert!(list.contains(&j));
-            } else {
-                assert!(!list.contains(&j));
-            }
-        }
-
-        assert!(!list.contains(&i));
-
-        if do_insert(i) {
-            list.insert(i);
-            assert!(list.contains(&i));
-        }
-    }
-}
-
-#[test]
-fn test_remove_first() {
-    let mut list = TinyList::new();
-    list.insert(1);
-    list.insert(2);
-    list.insert(3);
-    list.insert(4);
-    assert_eq!(list.len(), 4);
-
-    assert!(list.remove(&4));
-    assert!(!list.contains(&4));
-
-    assert_eq!(list.len(), 3);
-    assert!(list.contains(&1));
-    assert!(list.contains(&2));
-    assert!(list.contains(&3));
-}
-
-#[test]
-fn test_remove_last() {
-    let mut list = TinyList::new();
-    list.insert(1);
-    list.insert(2);
-    list.insert(3);
-    list.insert(4);
-    assert_eq!(list.len(), 4);
-
-    assert!(list.remove(&1));
-    assert!(!list.contains(&1));
-
-    assert_eq!(list.len(), 3);
-    assert!(list.contains(&2));
-    assert!(list.contains(&3));
-    assert!(list.contains(&4));
-}
-
-#[test]
-fn test_remove_middle() {
-    let mut list = TinyList::new();
-    list.insert(1);
-    list.insert(2);
-    list.insert(3);
-    list.insert(4);
-    assert_eq!(list.len(), 4);
-
-    assert!(list.remove(&2));
-    assert!(!list.contains(&2));
-
-    assert_eq!(list.len(), 3);
-    assert!(list.contains(&1));
-    assert!(list.contains(&3));
-    assert!(list.contains(&4));
-}
-
-#[test]
-fn test_remove_single() {
-    let mut list = TinyList::new();
-    list.insert(1);
-    assert_eq!(list.len(), 1);
-
-    assert!(list.remove(&1));
-    assert!(!list.contains(&1));
-
-    assert_eq!(list.len(), 0);
-}
-
-#[bench]
-fn bench_insert_empty(b: &mut Bencher) {
-    b.iter(|| {
-        let mut list = black_box(TinyList::new());
-        list.insert(1);
-        list
-    })
-}
-
-#[bench]
-fn bench_insert_one(b: &mut Bencher) {
-    b.iter(|| {
-        let mut list = black_box(TinyList::new_single(0));
-        list.insert(1);
-        list
-    })
-}
-
-#[bench]
-fn bench_contains_empty(b: &mut Bencher) {
-    b.iter(|| black_box(TinyList::new()).contains(&1));
-}
-
-#[bench]
-fn bench_contains_unknown(b: &mut Bencher) {
-    b.iter(|| black_box(TinyList::new_single(0)).contains(&1));
-}
-
-#[bench]
-fn bench_contains_one(b: &mut Bencher) {
-    b.iter(|| black_box(TinyList::new_single(1)).contains(&1));
-}
-
-#[bench]
-fn bench_remove_empty(b: &mut Bencher) {
-    b.iter(|| black_box(TinyList::new()).remove(&1));
-}
-
-#[bench]
-fn bench_remove_unknown(b: &mut Bencher) {
-    b.iter(|| black_box(TinyList::new_single(0)).remove(&1));
-}
-
-#[bench]
-fn bench_remove_one(b: &mut Bencher) {
-    b.iter(|| black_box(TinyList::new_single(1)).remove(&1));
-}
diff --git a/compiler/rustc_middle/src/mir/interpret/mod.rs b/compiler/rustc_middle/src/mir/interpret/mod.rs
index ee3cdf36820..38cb1d5f9a0 100644
--- a/compiler/rustc_middle/src/mir/interpret/mod.rs
+++ b/compiler/rustc_middle/src/mir/interpret/mod.rs
@@ -125,10 +125,11 @@ use std::io::{Read, Write};
 use std::num::NonZero;
 use std::sync::atomic::{AtomicU32, Ordering};
 
+use smallvec::{smallvec, SmallVec};
+
 use rustc_ast::LitKind;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::sync::{HashMapExt, Lock};
-use rustc_data_structures::tiny_list::TinyList;
 use rustc_errors::ErrorGuaranteed;
 use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable};
@@ -266,8 +267,8 @@ type DecodingSessionId = NonZero<u32>;
 #[derive(Clone)]
 enum State {
     Empty,
-    InProgressNonAlloc(TinyList<DecodingSessionId>),
-    InProgress(TinyList<DecodingSessionId>, AllocId),
+    InProgressNonAlloc(SmallVec<[DecodingSessionId; 1]>),
+    InProgress(SmallVec<[DecodingSessionId; 1]>, AllocId),
     Done(AllocId),
 }
 
@@ -337,8 +338,7 @@ impl<'s> AllocDecodingSession<'s> {
                             // If this is an allocation, we need to reserve an
                             // `AllocId` so we can decode cyclic graphs.
                             let alloc_id = decoder.interner().reserve_alloc_id();
-                            *entry =
-                                State::InProgress(TinyList::new_single(self.session_id), alloc_id);
+                            *entry = State::InProgress(smallvec![self.session_id], alloc_id);
                             Some(alloc_id)
                         }
                         AllocDiscriminant::Fn
@@ -346,8 +346,7 @@ impl<'s> AllocDecodingSession<'s> {
                         | AllocDiscriminant::VTable => {
                             // Fns and statics cannot be cyclic, and their `AllocId`
                             // is determined later by interning.
-                            *entry =
-                                State::InProgressNonAlloc(TinyList::new_single(self.session_id));
+                            *entry = State::InProgressNonAlloc(smallvec![self.session_id]);
                             None
                         }
                     }
@@ -357,7 +356,7 @@ impl<'s> AllocDecodingSession<'s> {
                         bug!("this should be unreachable");
                     } else {
                         // Start decoding concurrently.
-                        sessions.insert(self.session_id);
+                        sessions.push(self.session_id);
                         None
                     }
                 }
@@ -367,7 +366,7 @@ impl<'s> AllocDecodingSession<'s> {
                         return alloc_id;
                     } else {
                         // Start decoding concurrently.
-                        sessions.insert(self.session_id);
+                        sessions.push(self.session_id);
                         Some(alloc_id)
                     }
                 }