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.

1 files changed, 16 insertions, 4 deletions

diff --git a/compiler/rustc_serialize/src/collection_impls.rs b/compiler/rustc_serialize/src/collection_impls.rs
index 5e53f0b104d..8f8c504117c 100644
--- a/compiler/rustc_serialize/src/collection_impls.rs
+++ b/compiler/rustc_serialize/src/collection_impls.rs
@@ -1,13 +1,12 @@
 //! Implementations of serialization for structures found in liballoc
 
-use std::hash::{BuildHasher, Hash};
-
 use crate::{Decodable, Decoder, Encodable, Encoder};
+use smallvec::{Array, SmallVec};
 use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, LinkedList, VecDeque};
+use std::hash::{BuildHasher, Hash};
 use std::rc::Rc;
 use std::sync::Arc;
-
-use smallvec::{Array, SmallVec};
+use thin_vec::ThinVec;
 
 impl<S: Encoder, A: Array<Item: Encodable<S>>> Encodable<S> for SmallVec<A> {
     fn encode(&self, s: &mut S) {
@@ -23,6 +22,19 @@ impl<D: Decoder, A: Array<Item: Decodable<D>>> Decodable<D> for SmallVec<A> {
     }
 }
 
+impl<S: Encoder, T: Encodable<S>> Encodable<S> for ThinVec<T> {
+    fn encode(&self, s: &mut S) {
+        self.as_slice().encode(s);
+    }
+}
+
+impl<D: Decoder, T: Decodable<D>> Decodable<D> for ThinVec<T> {
+    fn decode(d: &mut D) -> ThinVec<T> {
+        let len = d.read_usize();
+        (0..len).map(|_| Decodable::decode(d)).collect()
+    }
+}
+
 impl<S: Encoder, T: Encodable<S>> Encodable<S> for LinkedList<T> {
     fn encode(&self, s: &mut S) {
         s.emit_usize(self.len());