Format the world

7 files changed, 657 insertions, 994 deletions

diff --git a/src/liballoc/collections/binary_heap.rs b/src/liballoc/collections/binary_heap.rs
index fda6f090fd7..0148711bb86 100644
--- a/src/liballoc/collections/binary_heap.rs
+++ b/src/liballoc/collections/binary_heap.rs
@@ -145,11 +145,11 @@
 #![allow(missing_docs)]
 #![stable(feature = "rust1", since = "1.0.0")]
 
-use core::ops::{Deref, DerefMut};
+use core::fmt;
 use core::iter::{FromIterator, FusedIterator, TrustedLen};
-use core::mem::{swap, size_of, ManuallyDrop};
+use core::mem::{size_of, swap, ManuallyDrop};
+use core::ops::{Deref, DerefMut};
 use core::ptr;
-use core::fmt;
 
 use crate::slice;
 use crate::vec::{self, Vec};
@@ -267,9 +267,7 @@ pub struct PeekMut<'a, T: 'a + Ord> {
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: Ord + fmt::Debug> fmt::Debug for PeekMut<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("PeekMut")
-         .field(&self.heap.data[0])
-         .finish()
+        f.debug_tuple("PeekMut").field(&self.heap.data[0]).finish()
     }
 }
 
@@ -404,14 +402,7 @@ impl<T: Ord> BinaryHeap<T> {
     /// Cost is O(1) in the worst case.
     #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
     pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>> {
-        if self.is_empty() {
-            None
-        } else {
-            Some(PeekMut {
-                heap: self,
-                sift: true,
-            })
-        }
+        if self.is_empty() { None } else { Some(PeekMut { heap: self, sift: true }) }
     }
 
     /// Removes the greatest item from the binary heap and returns it, or `None` if it
@@ -674,9 +665,7 @@ impl<T: Ord> BinaryHeap<T> {
     #[inline]
     #[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
     pub fn drain_sorted(&mut self) -> DrainSorted<'_, T> {
-        DrainSorted {
-            inner: self,
-        }
+        DrainSorted { inner: self }
     }
 }
 
@@ -718,9 +707,7 @@ impl<T> BinaryHeap<T> {
     /// ```
     #[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
     pub fn into_iter_sorted(self) -> IntoIterSorted<T> {
-        IntoIterSorted {
-            inner: self,
-        }
+        IntoIterSorted { inner: self }
     }
 
     /// Returns the greatest item in the binary heap, or `None` if it is empty.
@@ -857,7 +844,7 @@ impl<T> BinaryHeap<T> {
     /// assert!(heap.capacity() >= 10);
     /// ```
     #[inline]
-    #[unstable(feature = "shrink_to", reason = "new API", issue="56431")]
+    #[unstable(feature = "shrink_to", reason = "new API", issue = "56431")]
     pub fn shrink_to(&mut self, min_capacity: usize) {
         self.data.shrink_to(min_capacity)
     }
@@ -991,11 +978,7 @@ impl<'a, T> Hole<'a, T> {
         debug_assert!(pos < data.len());
         // SAFE: pos should be inside the slice
         let elt = ptr::read(data.get_unchecked(pos));
-        Hole {
-            data,
-            elt: ManuallyDrop::new(elt),
-            pos,
-        }
+        Hole { data, elt: ManuallyDrop::new(elt), pos }
     }
 
     #[inline]
@@ -1059,9 +1042,7 @@ pub struct Iter<'a, T: 'a> {
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("Iter")
-         .field(&self.iter.as_slice())
-         .finish()
+        f.debug_tuple("Iter").field(&self.iter.as_slice()).finish()
     }
 }
 
@@ -1127,9 +1108,7 @@ pub struct IntoIter<T> {
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("IntoIter")
-         .field(&self.iter.as_slice())
-         .finish()
+        f.debug_tuple("IntoIter").field(&self.iter.as_slice()).finish()
     }
 }
 
@@ -1281,7 +1260,7 @@ impl<T: Ord> Iterator for DrainSorted<'_, T> {
 }
 
 #[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
-impl<T: Ord> ExactSizeIterator for DrainSorted<'_, T> { }
+impl<T: Ord> ExactSizeIterator for DrainSorted<'_, T> {}
 
 #[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
 impl<T: Ord> FusedIterator for DrainSorted<'_, T> {}
diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs
index 5b48b594ff9..7d0a862d79e 100644
--- a/src/liballoc/collections/btree/map.rs
+++ b/src/liballoc/collections/btree/map.rs
@@ -2,17 +2,17 @@ use core::borrow::Borrow;
 use core::cmp::Ordering;
 use core::fmt::Debug;
 use core::hash::{Hash, Hasher};
-use core::iter::{FromIterator, Peekable, FusedIterator};
+use core::iter::{FromIterator, FusedIterator, Peekable};
 use core::marker::PhantomData;
 use core::ops::Bound::{Excluded, Included, Unbounded};
 use core::ops::{Index, RangeBounds};
 use core::{fmt, intrinsics, mem, ptr};
 
-use super::node::{self, Handle, NodeRef, marker, InsertResult::*, ForceResult::*};
+use super::node::{self, marker, ForceResult::*, Handle, InsertResult::*, NodeRef};
 use super::search::{self, SearchResult::*};
 
-use UnderflowResult::*;
 use Entry::*;
+use UnderflowResult::*;
 
 /// A map based on a B-Tree.
 ///
@@ -138,16 +138,15 @@ unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for BTreeMap<K, V> {
 impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
     fn clone(&self) -> BTreeMap<K, V> {
         fn clone_subtree<'a, K: Clone, V: Clone>(
-            node: node::NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>
+            node: node::NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>,
         ) -> BTreeMap<K, V>
-        where K: 'a, V: 'a,
+        where
+            K: 'a,
+            V: 'a,
         {
             match node.force() {
                 Leaf(leaf) => {
-                    let mut out_tree = BTreeMap {
-                        root: node::Root::new_leaf(),
-                        length: 0,
-                    };
+                    let mut out_tree = BTreeMap { root: node::Root::new_leaf(), length: 0 };
 
                     {
                         let mut out_node = match out_tree.root.as_mut().force() {
@@ -203,10 +202,7 @@ impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
         if self.is_empty() {
             // Ideally we'd call `BTreeMap::new` here, but that has the `K:
             // Ord` constraint, which this method lacks.
-            BTreeMap {
-                root: node::Root::shared_empty_root(),
-                length: 0,
-            }
+            BTreeMap { root: node::Root::shared_empty_root(), length: 0 }
         } else {
             clone_subtree(self.root.as_ref())
         }
@@ -214,8 +210,9 @@ impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
 }
 
 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
-    where K: Borrow<Q> + Ord,
-          Q: Ord
+where
+    K: Borrow<Q> + Ord,
+    Q: Ord,
 {
     type Key = K;
 
@@ -228,15 +225,11 @@ impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
 
     fn take(&mut self, key: &Q) -> Option<K> {
         match search::search_tree(self.root.as_mut(), key) {
-            Found(handle) => {
-                Some(OccupiedEntry {
-                         handle,
-                         length: &mut self.length,
-                         _marker: PhantomData,
-                     }
-                     .remove_kv()
-                     .0)
-            }
+            Found(handle) => Some(
+                OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData }
+                    .remove_kv()
+                    .0,
+            ),
             GoDown(_) => None,
         }
     }
@@ -246,13 +239,8 @@ impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
         match search::search_tree::<marker::Mut<'_>, K, (), K>(self.root.as_mut(), &key) {
             Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
             GoDown(handle) => {
-                VacantEntry {
-                    key,
-                    handle,
-                    length: &mut self.length,
-                    _marker: PhantomData,
-                }
-                .insert(());
+                VacantEntry { key, handle, length: &mut self.length, _marker: PhantomData }
+                    .insert(());
                 None
             }
         }
@@ -310,10 +298,7 @@ pub struct IntoIter<K, V> {
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        let range = Range {
-            front: self.front.reborrow(),
-            back: self.back.reborrow(),
-        };
+        let range = Range { front: self.front.reborrow(), back: self.back.reborrow() };
         f.debug_list().entries(range).finish()
     }
 }
@@ -408,10 +393,7 @@ pub struct RangeMut<'a, K: 'a, V: 'a> {
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RangeMut<'_, K, V> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        let range = Range {
-            front: self.front.reborrow(),
-            back: self.back.reborrow(),
-        };
+        let range = Range { front: self.front.reborrow(), back: self.back.reborrow() };
         f.debug_list().entries(range).finish()
     }
 }
@@ -426,25 +408,19 @@ impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RangeMut<'_, K, V> {
 pub enum Entry<'a, K: 'a, V: 'a> {
     /// A vacant entry.
     #[stable(feature = "rust1", since = "1.0.0")]
-    Vacant(#[stable(feature = "rust1", since = "1.0.0")]
-           VacantEntry<'a, K, V>),
+    Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>),
 
     /// An occupied entry.
     #[stable(feature = "rust1", since = "1.0.0")]
-    Occupied(#[stable(feature = "rust1", since = "1.0.0")]
-             OccupiedEntry<'a, K, V>),
+    Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>),
 }
 
-#[stable(feature= "debug_btree_map", since = "1.12.0")]
+#[stable(feature = "debug_btree_map", since = "1.12.0")]
 impl<K: Debug + Ord, V: Debug> Debug for Entry<'_, K, V> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match *self {
-            Vacant(ref v) => f.debug_tuple("Entry")
-                              .field(v)
-                              .finish(),
-            Occupied(ref o) => f.debug_tuple("Entry")
-                                .field(o)
-                                .finish(),
+            Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
+            Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
         }
     }
 }
@@ -463,12 +439,10 @@ pub struct VacantEntry<'a, K: 'a, V: 'a> {
     _marker: PhantomData<&'a mut (K, V)>,
 }
 
-#[stable(feature= "debug_btree_map", since = "1.12.0")]
+#[stable(feature = "debug_btree_map", since = "1.12.0")]
 impl<K: Debug + Ord, V> Debug for VacantEntry<'_, K, V> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("VacantEntry")
-         .field(self.key())
-         .finish()
+        f.debug_tuple("VacantEntry").field(self.key()).finish()
     }
 }
 
@@ -486,13 +460,10 @@ pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
     _marker: PhantomData<&'a mut (K, V)>,
 }
 
-#[stable(feature= "debug_btree_map", since = "1.12.0")]
+#[stable(feature = "debug_btree_map", since = "1.12.0")]
 impl<K: Debug + Ord, V: Debug> Debug for OccupiedEntry<'_, K, V> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_struct("OccupiedEntry")
-         .field("key", self.key())
-         .field("value", self.get())
-         .finish()
+        f.debug_struct("OccupiedEntry").field("key", self.key()).field("value", self.get()).finish()
     }
 }
 
@@ -519,10 +490,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn new() -> BTreeMap<K, V> {
-        BTreeMap {
-            root: node::Root::shared_empty_root(),
-            length: 0,
-        }
+        BTreeMap { root: node::Root::shared_empty_root(), length: 0 }
     }
 
     /// Clears the map, removing all values.
@@ -563,8 +531,9 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
-        where K: Borrow<Q>,
-              Q: Ord
+    where
+        K: Borrow<Q>,
+        Q: Ord,
     {
         match search::search_tree(self.root.as_ref(), key) {
             Found(handle) => Some(handle.into_kv().1),
@@ -589,8 +558,9 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "map_get_key_value", since = "1.40.0")]
     pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
-        where K: Borrow<Q>,
-              Q: Ord
+    where
+        K: Borrow<Q>,
+        Q: Ord,
     {
         match search::search_tree(self.root.as_ref(), k) {
             Found(handle) => Some(handle.into_kv()),
@@ -617,7 +587,9 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[unstable(feature = "map_first_last", issue = "62924")]
     pub fn first_key_value<T: ?Sized>(&self) -> Option<(&K, &V)>
-        where T: Ord, K: Borrow<T>
+    where
+        T: Ord,
+        K: Borrow<T>,
     {
         let front = first_leaf_edge(self.root.as_ref());
         front.right_kv().ok().map(Handle::into_kv)
@@ -644,15 +616,17 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[unstable(feature = "map_first_last", issue = "62924")]
     pub fn first_entry<T: ?Sized>(&mut self) -> Option<OccupiedEntry<'_, K, V>>
-        where T: Ord, K: Borrow<T>
+    where
+        T: Ord,
+        K: Borrow<T>,
     {
         match self.length {
             0 => None,
             _ => Some(OccupiedEntry {
-                          handle: self.root.as_mut().first_kv(),
-                          length: &mut self.length,
-                          _marker: PhantomData,
-                      }),
+                handle: self.root.as_mut().first_kv(),
+                length: &mut self.length,
+                _marker: PhantomData,
+            }),
         }
     }
 
@@ -674,7 +648,9 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[unstable(feature = "map_first_last", issue = "62924")]
     pub fn last_key_value<T: ?Sized>(&self) -> Option<(&K, &V)>
-        where T: Ord, K: Borrow<T>
+    where
+        T: Ord,
+        K: Borrow<T>,
     {
         let back = last_leaf_edge(self.root.as_ref());
         back.left_kv().ok().map(Handle::into_kv)
@@ -701,15 +677,17 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[unstable(feature = "map_first_last", issue = "62924")]
     pub fn last_entry<T: ?Sized>(&mut self) -> Option<OccupiedEntry<'_, K, V>>
-        where T: Ord, K: Borrow<T>
+    where
+        T: Ord,
+        K: Borrow<T>,
     {
         match self.length {
             0 => None,
             _ => Some(OccupiedEntry {
-                          handle: self.root.as_mut().last_kv(),
-                          length: &mut self.length,
-                          _marker: PhantomData,
-                      }),
+                handle: self.root.as_mut().last_kv(),
+                length: &mut self.length,
+                _marker: PhantomData,
+            }),
         }
     }
 
@@ -732,8 +710,9 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
-        where K: Borrow<Q>,
-              Q: Ord
+    where
+        K: Borrow<Q>,
+        Q: Ord,
     {
         self.get(key).is_some()
     }
@@ -760,8 +739,9 @@ impl<K: Ord, V> BTreeMap<K, V> {
     // See `get` for implementation notes, this is basically a copy-paste with mut's added
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
-        where K: Borrow<Q>,
-              Q: Ord
+    where
+        K: Borrow<Q>,
+        Q: Ord,
     {
         match search::search_tree(self.root.as_mut(), key) {
             Found(handle) => Some(handle.into_kv_mut().1),
@@ -826,18 +806,14 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
-        where K: Borrow<Q>,
-              Q: Ord
+    where
+        K: Borrow<Q>,
+        Q: Ord,
     {
         match search::search_tree(self.root.as_mut(), key) {
-            Found(handle) => {
-                Some(OccupiedEntry {
-                         handle,
-                         length: &mut self.length,
-                         _marker: PhantomData,
-                     }
-                     .remove())
-            }
+            Found(handle) => Some(
+                OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData }.remove(),
+            ),
             GoDown(_) => None,
         }
     }
@@ -886,10 +862,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
         // First, we merge `self` and `other` into a sorted sequence in linear time.
         let self_iter = mem::take(self).into_iter();
         let other_iter = mem::take(other).into_iter();
-        let iter = MergeIter {
-            left: self_iter.peekable(),
-            right: other_iter.peekable(),
-        };
+        let iter = MergeIter { left: self_iter.peekable(), right: other_iter.peekable() };
 
         // Second, we build a tree from the sorted sequence in linear time.
         self.from_sorted_iter(iter);
@@ -927,13 +900,16 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "btree_range", since = "1.17.0")]
     pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
-        where T: Ord, K: Borrow<T>, R: RangeBounds<T>
+    where
+        T: Ord,
+        K: Borrow<T>,
+        R: RangeBounds<T>,
     {
         let root1 = self.root.as_ref();
         let root2 = self.root.as_ref();
         let (f, b) = range_search(root1, root2, range);
 
-        Range { front: f, back: b}
+        Range { front: f, back: b }
     }
 
     /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
@@ -968,17 +944,16 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "btree_range", since = "1.17.0")]
     pub fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V>
-        where T: Ord, K: Borrow<T>, R: RangeBounds<T>
+    where
+        T: Ord,
+        K: Borrow<T>,
+        R: RangeBounds<T>,
     {
         let root1 = self.root.as_mut();
         let root2 = unsafe { ptr::read(&root1) };
         let (f, b) = range_search(root1, root2, range);
 
-        RangeMut {
-            front: f,
-            back: b,
-            _marker: PhantomData,
-        }
+        RangeMut { front: f, back: b, _marker: PhantomData }
     }
 
     /// Gets the given key's corresponding entry in the map for in-place manipulation.
@@ -1005,19 +980,10 @@ impl<K: Ord, V> BTreeMap<K, V> {
         self.ensure_root_is_owned();
         match search::search_tree(self.root.as_mut(), &key) {
             Found(handle) => {
-                Occupied(OccupiedEntry {
-                    handle,
-                    length: &mut self.length,
-                    _marker: PhantomData,
-                })
+                Occupied(OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData })
             }
             GoDown(handle) => {
-                Vacant(VacantEntry {
-                    key,
-                    handle,
-                    length: &mut self.length,
-                    _marker: PhantomData,
-                })
+                Vacant(VacantEntry { key, handle, length: &mut self.length, _marker: PhantomData })
             }
         }
     }
@@ -1124,7 +1090,8 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "btree_split_off", since = "1.11.0")]
     pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
-        where K: Borrow<Q>
+    where
+        K: Borrow<Q>,
     {
         if self.is_empty() {
             return Self::new();
@@ -1182,10 +1149,10 @@ impl<K: Ord, V> BTreeMap<K, V> {
 
     /// Calculates the number of elements if it is incorrect.
     fn recalc_length(&mut self) {
-        fn dfs<'a, K, V>(
-            node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>
-        ) -> usize
-        where K: 'a, V: 'a
+        fn dfs<'a, K, V>(node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>) -> usize
+        where
+            K: 'a,
+            V: 'a,
         {
             let mut res = node.len();
 
@@ -1338,10 +1305,7 @@ impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<K, V> Clone for Iter<'_, K, V> {
     fn clone(&self) -> Self {
-        Iter {
-            range: self.range.clone(),
-            length: self.length,
-        }
+        Iter { range: self.range.clone(), length: self.length }
     }
 }
 
@@ -1410,11 +1374,7 @@ impl<K, V> IntoIterator for BTreeMap<K, V> {
         let len = self.length;
         mem::forget(self);
 
-        IntoIter {
-            front: first_leaf_edge(root1),
-            back: last_leaf_edge(root2),
-            length: len,
-        }
+        IntoIter { front: first_leaf_edge(root1), back: last_leaf_edge(root2), length: len }
     }
 }
 
@@ -1619,11 +1579,7 @@ impl<'a, K, V> Iterator for Range<'a, K, V> {
     type Item = (&'a K, &'a V);
 
     fn next(&mut self) -> Option<(&'a K, &'a V)> {
-        if self.front == self.back {
-            None
-        } else {
-            unsafe { Some(self.next_unchecked()) }
-        }
+        if self.front == self.back { None } else { unsafe { Some(self.next_unchecked()) } }
     }
 
     fn last(mut self) -> Option<(&'a K, &'a V)> {
@@ -1700,11 +1656,7 @@ impl<'a, K, V> Range<'a, K, V> {
 #[stable(feature = "btree_range", since = "1.17.0")]
 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
-        if self.front == self.back {
-            None
-        } else {
-            unsafe { Some(self.next_back_unchecked()) }
-        }
+        if self.front == self.back { None } else { unsafe { Some(self.next_back_unchecked()) } }
     }
 }
 
@@ -1746,10 +1698,7 @@ impl<K, V> FusedIterator for Range<'_, K, V> {}
 #[stable(feature = "btree_range", since = "1.17.0")]
 impl<K, V> Clone for Range<'_, K, V> {
     fn clone(&self) -> Self {
-        Range {
-            front: self.front,
-            back: self.back,
-        }
+        Range { front: self.front, back: self.back }
     }
 }
 
@@ -1758,11 +1707,7 @@ impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
     type Item = (&'a K, &'a mut V);
 
     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
-        if self.front == self.back {
-            None
-        } else {
-            unsafe { Some(self.next_unchecked()) }
-        }
+        if self.front == self.back { None } else { unsafe { Some(self.next_unchecked()) } }
     }
 
     fn last(mut self) -> Option<(&'a K, &'a mut V)> {
@@ -1809,11 +1754,7 @@ impl<'a, K, V> RangeMut<'a, K, V> {
 #[stable(feature = "btree_range", since = "1.17.0")]
 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
-        if self.front == self.back {
-            None
-        } else {
-            unsafe { Some(self.next_back_unchecked()) }
-        }
+        if self.front == self.back { None } else { unsafe { Some(self.next_back_unchecked()) } }
     }
 }
 
@@ -1934,8 +1875,9 @@ impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<K: Ord, Q: ?Sized, V> Index<&Q> for BTreeMap<K, V>
-    where K: Borrow<Q>,
-          Q: Ord
+where
+    K: Borrow<Q>,
+    Q: Ord,
 {
     type Output = V;
 
@@ -1950,9 +1892,9 @@ impl<K: Ord, Q: ?Sized, V> Index<&Q> for BTreeMap<K, V>
     }
 }
 
-fn first_leaf_edge<BorrowType, K, V>
-    (mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>)
-     -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+fn first_leaf_edge<BorrowType, K, V>(
+    mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
+) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
     loop {
         match node.force() {
             Leaf(leaf) => return leaf.first_edge(),
@@ -1963,9 +1905,9 @@ fn first_leaf_edge<BorrowType, K, V>
     }
 }
 
-fn last_leaf_edge<BorrowType, K, V>
-    (mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>)
-     -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+fn last_leaf_edge<BorrowType, K, V>(
+    mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
+) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
     loop {
         match node.force() {
             Leaf(leaf) => return leaf.last_edge(),
@@ -1979,20 +1921,28 @@ fn last_leaf_edge<BorrowType, K, V>
 fn range_search<BorrowType, K, V, Q: ?Sized, R: RangeBounds<Q>>(
     root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
     root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
-    range: R
-)-> (Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>,
-     Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>)
-        where Q: Ord, K: Borrow<Q>
+    range: R,
+) -> (
+    Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>,
+    Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>,
+)
+where
+    Q: Ord,
+    K: Borrow<Q>,
 {
     match (range.start_bound(), range.end_bound()) {
-        (Excluded(s), Excluded(e)) if s==e =>
-            panic!("range start and end are equal and excluded in BTreeMap"),
-        (Included(s), Included(e)) |
-        (Included(s), Excluded(e)) |
-        (Excluded(s), Included(e)) |
-        (Excluded(s), Excluded(e)) if s>e =>
-            panic!("range start is greater than range end in BTreeMap"),
-        _ => {},
+        (Excluded(s), Excluded(e)) if s == e => {
+            panic!("range start and end are equal and excluded in BTreeMap")
+        }
+        (Included(s), Included(e))
+        | (Included(s), Excluded(e))
+        | (Excluded(s), Included(e))
+        | (Excluded(s), Excluded(e))
+            if s > e =>
+        {
+            panic!("range start is greater than range end in BTreeMap")
+        }
+        _ => {}
     };
 
     let mut min_node = root1;
@@ -2004,11 +1954,17 @@ fn range_search<BorrowType, K, V, Q: ?Sized, R: RangeBounds<Q>>(
     loop {
         let min_edge = match (min_found, range.start_bound()) {
             (false, Included(key)) => match search::search_linear(&min_node, key) {
-                (i, true) => { min_found = true; i },
+                (i, true) => {
+                    min_found = true;
+                    i
+                }
                 (i, false) => i,
             },
             (false, Excluded(key)) => match search::search_linear(&min_node, key) {
-                (i, true) => { min_found = true; i+1 },
+                (i, true) => {
+                    min_found = true;
+                    i + 1
+                }
                 (i, false) => i,
             },
             (_, Unbounded) => 0,
@@ -2018,11 +1974,17 @@ fn range_search<BorrowType, K, V, Q: ?Sized, R: RangeBounds<Q>>(
 
         let max_edge = match (max_found, range.end_bound()) {
             (false, Included(key)) => match search::search_linear(&max_node, key) {
-                (i, true) => { max_found = true; i+1 },
+                (i, true) => {
+                    max_found = true;
+                    i + 1
+                }
                 (i, false) => i,
             },
             (false, Excluded(key)) => match search::search_linear(&max_node, key) {
-                (i, true) => { max_found = true; i },
+                (i, true) => {
+                    max_found = true;
+                    i
+                }
                 (i, false) => i,
             },
             (_, Unbounded) => max_node.keys().len(),
@@ -2031,8 +1993,12 @@ fn range_search<BorrowType, K, V, Q: ?Sized, R: RangeBounds<Q>>(
         };
 
         if !diverged {
-            if max_edge < min_edge { panic!("Ord is ill-defined in BTreeMap range") }
-            if min_edge != max_edge { diverged = true; }
+            if max_edge < min_edge {
+                panic!("Ord is ill-defined in BTreeMap range")
+            }
+            if min_edge != max_edge {
+                diverged = true;
+            }
         }
 
         let front = Handle::new_edge(min_node, min_edge);
@@ -2040,11 +2006,11 @@ fn range_search<BorrowType, K, V, Q: ?Sized, R: RangeBounds<Q>>(
         match (front.force(), back.force()) {
             (Leaf(f), Leaf(b)) => {
                 return (f, b);
-            },
+            }
             (Internal(min_int), Internal(max_int)) => {
                 min_node = min_int.descend();
                 max_node = max_int.descend();
-            },
+            }
             _ => unreachable!("BTreeMap has different depths"),
         };
     }
@@ -2321,13 +2287,14 @@ impl<'a, K: Ord, V> Entry<'a, K, V> {
     /// ```
     #[stable(feature = "entry_and_modify", since = "1.26.0")]
     pub fn and_modify<F>(self, f: F) -> Self
-        where F: FnOnce(&mut V)
+    where
+        F: FnOnce(&mut V),
     {
         match self {
             Occupied(mut entry) => {
                 f(entry.get_mut());
                 Occupied(entry)
-            },
+            }
             Vacant(entry) => Vacant(entry),
         }
     }
@@ -2354,7 +2321,6 @@ impl<'a, K: Ord, V: Default> Entry<'a, K, V> {
             Vacant(entry) => entry.insert(Default::default()),
         }
     }
-
 }
 
 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
@@ -2433,17 +2399,15 @@ impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
 
         loop {
             match cur_parent {
-                Ok(parent) => {
-                    match parent.insert(ins_k, ins_v, ins_edge) {
-                        Fit(_) => return unsafe { &mut *out_ptr },
-                        Split(left, k, v, right) => {
-                            ins_k = k;
-                            ins_v = v;
-                            ins_edge = right;
-                            cur_parent = left.ascend().map_err(|n| n.into_root_mut());
-                        }
+                Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) {
+                    Fit(_) => return unsafe { &mut *out_ptr },
+                    Split(left, k, v, right) => {
+                        ins_k = k;
+                        ins_v = v;
+                        ins_edge = right;
+                        cur_parent = left.ascend().map_err(|n| n.into_root_mut());
                     }
-                }
+                },
                 Err(root) => {
                     root.push_level().push(ins_k, ins_v, ins_edge);
                     return unsafe { &mut *out_ptr };
@@ -2669,8 +2633,9 @@ enum UnderflowResult<'a, K, V> {
     Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
 }
 
-fn handle_underfull_node<K, V>(node: NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal>)
-                               -> UnderflowResult<'_, K, V> {
+fn handle_underfull_node<K, V>(
+    node: NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal>,
+) -> UnderflowResult<'_, K, V> {
     let parent = if let Ok(parent) = node.ascend() {
         parent
     } else {
@@ -2679,14 +2644,12 @@ fn handle_underfull_node<K, V>(node: NodeRef<marker::Mut<'_>, K, V, marker::Leaf
 
     let (is_left, mut handle) = match parent.left_kv() {
         Ok(left) => (true, left),
-        Err(parent) => {
-            match parent.right_kv() {
-                Ok(right) => (false, right),
-                Err(parent) => {
-                    return EmptyParent(parent.into_node());
-                }
+        Err(parent) => match parent.right_kv() {
+            Ok(right) => (false, right),
+            Err(parent) => {
+                return EmptyParent(parent.into_node());
             }
-        }
+        },
     };
 
     if handle.can_merge() {
diff --git a/src/liballoc/collections/btree/node.rs b/src/liballoc/collections/btree/node.rs
index ab010b35f6a..53c2c29a9b6 100644
--- a/src/liballoc/collections/btree/node.rs
+++ b/src/liballoc/collections/btree/node.rs
@@ -33,10 +33,10 @@
 
 use core::marker::PhantomData;
 use core::mem::{self, MaybeUninit};
-use core::ptr::{self, Unique, NonNull};
+use core::ptr::{self, NonNull, Unique};
 use core::slice;
 
-use crate::alloc::{Global, Alloc, Layout};
+use crate::alloc::{Alloc, Global, Layout};
 use crate::boxed::Box;
 
 const B: usize = 6;
@@ -110,7 +110,7 @@ impl<K, V> LeafNode<K, V> {
             vals: [MaybeUninit::UNINIT; CAPACITY],
             parent: ptr::null(),
             parent_idx: MaybeUninit::uninit(),
-            len: 0
+            len: 0,
         }
     }
 }
@@ -127,12 +127,8 @@ unsafe impl Sync for NodeHeader<(), ()> {}
 // An empty node used as a placeholder for the root node, to avoid allocations.
 // We use just a header in order to save space, since no operation on an empty tree will
 // ever take a pointer past the first key.
-static EMPTY_ROOT_NODE: NodeHeader<(), ()> = NodeHeader {
-    parent: ptr::null(),
-    parent_idx: MaybeUninit::uninit(),
-    len: 0,
-    keys_start: [],
-};
+static EMPTY_ROOT_NODE: NodeHeader<(), ()> =
+    NodeHeader { parent: ptr::null(), parent_idx: MaybeUninit::uninit(), len: 0, keys_start: [] };
 
 /// The underlying representation of internal nodes. As with `LeafNode`s, these should be hidden
 /// behind `BoxedNode`s to prevent dropping uninitialized keys and values. Any pointer to an
@@ -157,10 +153,7 @@ impl<K, V> InternalNode<K, V> {
     /// `len` of 0), there must be one initialized and valid edge. This function does not set up
     /// such an edge.
     unsafe fn new() -> Self {
-        InternalNode {
-            data: LeafNode::new(),
-            edges: [MaybeUninit::UNINIT; 2*B]
-        }
+        InternalNode { data: LeafNode::new(), edges: [MaybeUninit::UNINIT; 2 * B] }
     }
 }
 
@@ -169,7 +162,7 @@ impl<K, V> InternalNode<K, V> {
 /// of nodes is actually behind the box, and, partially due to this lack of information, has no
 /// destructor.
 struct BoxedNode<K, V> {
-    ptr: Unique<LeafNode<K, V>>
+    ptr: Unique<LeafNode<K, V>>,
 }
 
 impl<K, V> BoxedNode<K, V> {
@@ -196,11 +189,11 @@ impl<K, V> BoxedNode<K, V> {
 /// and must be cleaned up manually.
 pub struct Root<K, V> {
     node: BoxedNode<K, V>,
-    height: usize
+    height: usize,
 }
 
-unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> { }
-unsafe impl<K: Send, V: Send> Send for Root<K, V> { }
+unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> {}
+unsafe impl<K: Send, V: Send> Send for Root<K, V> {}
 
 impl<K, V> Root<K, V> {
     pub fn is_shared_root(&self) -> bool {
@@ -211,7 +204,7 @@ impl<K, V> Root<K, V> {
         Root {
             node: unsafe {
                 BoxedNode::from_ptr(NonNull::new_unchecked(
-                    &EMPTY_ROOT_NODE as *const _ as *const LeafNode<K, V> as *mut _
+                    &EMPTY_ROOT_NODE as *const _ as *const LeafNode<K, V> as *mut _,
                 ))
             },
             height: 0,
@@ -219,14 +212,10 @@ impl<K, V> Root<K, V> {
     }
 
     pub fn new_leaf() -> Self {
-        Root {
-            node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })),
-            height: 0
-        }
+        Root { node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })), height: 0 }
     }
 
-    pub fn as_ref(&self)
-            -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> {
+    pub fn as_ref(&self) -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> {
         NodeRef {
             height: self.height,
             node: self.node.as_ptr(),
@@ -235,8 +224,7 @@ impl<K, V> Root<K, V> {
         }
     }
 
-    pub fn as_mut(&mut self)
-            -> NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal> {
+    pub fn as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal> {
         NodeRef {
             height: self.height,
             node: self.node.as_ptr(),
@@ -245,8 +233,7 @@ impl<K, V> Root<K, V> {
         }
     }
 
-    pub fn into_ref(self)
-            -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
+    pub fn into_ref(self) -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
         NodeRef {
             height: self.height,
             node: self.node.as_ptr(),
@@ -257,8 +244,7 @@ impl<K, V> Root<K, V> {
 
     /// Adds a new internal node with a single edge, pointing to the previous root, and make that
     /// new node the root. This increases the height by 1 and is the opposite of `pop_level`.
-    pub fn push_level(&mut self)
-            -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
+    pub fn push_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
         debug_assert!(!self.is_shared_root());
         let mut new_node = Box::new(unsafe { InternalNode::new() });
         new_node.edges[0].write(unsafe { BoxedNode::from_ptr(self.node.as_ptr()) });
@@ -270,7 +256,7 @@ impl<K, V> Root<K, V> {
             height: self.height,
             node: self.node.as_ptr(),
             root: self as *mut _,
-            _marker: PhantomData
+            _marker: PhantomData,
         };
 
         unsafe {
@@ -290,14 +276,14 @@ impl<K, V> Root<K, V> {
         let top = self.node.ptr;
 
         self.node = unsafe {
-            BoxedNode::from_ptr(self.as_mut()
-                                    .cast_unchecked::<marker::Internal>()
-                                    .first_edge()
-                                    .descend()
-                                    .node)
+            BoxedNode::from_ptr(
+                self.as_mut().cast_unchecked::<marker::Internal>().first_edge().descend().node,
+            )
         };
         self.height -= 1;
-        unsafe { (*self.as_mut().as_leaf_mut()).parent = ptr::null(); }
+        unsafe {
+            (*self.as_mut().as_leaf_mut()).parent = ptr::null();
+        }
 
         unsafe {
             Global.dealloc(NonNull::from(top).cast(), Layout::new::<InternalNode<K, V>>());
@@ -332,43 +318,34 @@ pub struct NodeRef<BorrowType, K, V, Type> {
     node: NonNull<LeafNode<K, V>>,
     // This is null unless the borrow type is `Mut`
     root: *const Root<K, V>,
-    _marker: PhantomData<(BorrowType, Type)>
+    _marker: PhantomData<(BorrowType, Type)>,
 }
 
-impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> { }
+impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> {}
 impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
     fn clone(&self) -> Self {
         *self
     }
 }
 
-unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync
-    for NodeRef<BorrowType, K, V, Type> { }
+unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {}
 
-unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send
-   for NodeRef<marker::Immut<'a>, K, V, Type> { }
-unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send
-   for NodeRef<marker::Mut<'a>, K, V, Type> { }
-unsafe impl<K: Send, V: Send, Type> Send
-   for NodeRef<marker::Owned, K, V, Type> { }
+unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {}
+unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {}
+unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {}
 
 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
     fn as_internal(&self) -> &InternalNode<K, V> {
-        unsafe {
-            &*(self.node.as_ptr() as *mut InternalNode<K, V>)
-        }
+        unsafe { &*(self.node.as_ptr() as *mut InternalNode<K, V>) }
     }
 }
 
 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
     fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
-        unsafe {
-            &mut *(self.node.as_ptr() as *mut InternalNode<K, V>)
-        }
+        unsafe { &mut *(self.node.as_ptr() as *mut InternalNode<K, V>) }
     }
 }
 
-
 impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
     /// Finds the length of the node. This is the number of keys or values. In an
     /// internal node, the number of edges is `len() + 1`.
@@ -385,22 +362,12 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
     /// Removes any static information about whether this node is a `Leaf` or an
     /// `Internal` node.
     pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
-        NodeRef {
-            height: self.height,
-            node: self.node,
-            root: self.root,
-            _marker: PhantomData
-        }
+        NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
     }
 
     /// Temporarily takes out another, immutable reference to the same node.
     fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> {
-        NodeRef {
-            height: self.height,
-            node: self.node,
-            root: self.root,
-            _marker: PhantomData
-        }
+        NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
     }
 
     /// Assert that this is indeed a proper leaf node, and not the shared root.
@@ -409,9 +376,7 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
     }
 
     fn as_header(&self) -> &NodeHeader<K, V> {
-        unsafe {
-            &*(self.node.as_ptr() as *const NodeHeader<K, V>)
-        }
+        unsafe { &*(self.node.as_ptr() as *const NodeHeader<K, V>) }
     }
 
     pub fn is_shared_root(&self) -> bool {
@@ -433,17 +398,9 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
     ///
     /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
     /// both, upon success, do nothing.
-    pub fn ascend(self) -> Result<
-        Handle<
-            NodeRef<
-                BorrowType,
-                K, V,
-                marker::Internal
-            >,
-            marker::Edge
-        >,
-        Self
-    > {
+    pub fn ascend(
+        self,
+    ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> {
         let parent_as_leaf = self.as_header().parent as *const LeafNode<K, V>;
         if let Some(non_zero) = NonNull::new(parent_as_leaf as *mut _) {
             Ok(Handle {
@@ -451,10 +408,10 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
                     height: self.height + 1,
                     node: non_zero,
                     root: self.root,
-                    _marker: PhantomData
+                    _marker: PhantomData,
                 },
                 idx: unsafe { usize::from(*self.as_header().parent_idx.as_ptr()) },
-                _marker: PhantomData
+                _marker: PhantomData,
             })
         } else {
             Err(self)
@@ -488,16 +445,9 @@ impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
     /// Similar to `ascend`, gets a reference to a node's parent node, but also
     /// deallocate the current node in the process. This is unsafe because the
     /// current node will still be accessible despite being deallocated.
-    pub unsafe fn deallocate_and_ascend(self) -> Option<
-        Handle<
-            NodeRef<
-                marker::Owned,
-                K, V,
-                marker::Internal
-            >,
-            marker::Edge
-        >
-    > {
+    pub unsafe fn deallocate_and_ascend(
+        self,
+    ) -> Option<Handle<NodeRef<marker::Owned, K, V, marker::Internal>, marker::Edge>> {
         debug_assert!(!self.is_shared_root());
         let node = self.node;
         let ret = self.ascend().ok();
@@ -510,16 +460,9 @@ impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
     /// Similar to `ascend`, gets a reference to a node's parent node, but also
     /// deallocate the current node in the process. This is unsafe because the
     /// current node will still be accessible despite being deallocated.
-    pub unsafe fn deallocate_and_ascend(self) -> Option<
-        Handle<
-            NodeRef<
-                marker::Owned,
-                K, V,
-                marker::Internal
-            >,
-            marker::Edge
-        >
-    > {
+    pub unsafe fn deallocate_and_ascend(
+        self,
+    ) -> Option<Handle<NodeRef<marker::Owned, K, V, marker::Internal>, marker::Edge>> {
         let node = self.node;
         let ret = self.ascend().ok();
         Global.dealloc(node.cast(), Layout::new::<InternalNode<K, V>>());
@@ -530,15 +473,8 @@ impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
 impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
     /// Unsafely asserts to the compiler some static information about whether this
     /// node is a `Leaf`.
-    unsafe fn cast_unchecked<NewType>(&mut self)
-            -> NodeRef<marker::Mut<'_>, K, V, NewType> {
-
-        NodeRef {
-            height: self.height,
-            node: self.node,
-            root: self.root,
-            _marker: PhantomData
-        }
+    unsafe fn cast_unchecked<NewType>(&mut self) -> NodeRef<marker::Mut<'_>, K, V, NewType> {
+        NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
     }
 
     /// Temporarily takes out another, mutable reference to the same node. Beware, as
@@ -552,12 +488,7 @@ impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
     // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef` that restricts
     // the use of `ascend` and `into_root_mut` on reborrowed pointers, preventing this unsafety.
     unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
-        NodeRef {
-            height: self.height,
-            node: self.node,
-            root: self.root,
-            _marker: PhantomData
-        }
+        NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
     }
 
     /// Returns a raw ptr to avoid asserting exclusive access to the entire node.
@@ -612,21 +543,14 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
             assert!(mem::size_of::<NodeHeader<K, V>>() == mem::size_of::<NodeHeader<K, V, K>>());
             let header = self.as_header() as *const _ as *const NodeHeader<K, V, K>;
             let keys = unsafe { &(*header).keys_start as *const _ as *const K };
-            unsafe {
-                slice::from_raw_parts(keys, self.len())
-            }
+            unsafe { slice::from_raw_parts(keys, self.len()) }
         }
     }
 
     fn into_val_slice(self) -> &'a [V] {
         debug_assert!(!self.is_shared_root());
         // We cannot be the root, so `as_leaf` is okay
-        unsafe {
-            slice::from_raw_parts(
-                MaybeUninit::first_ptr(&self.as_leaf().vals),
-                self.len()
-            )
-        }
+        unsafe { slice::from_raw_parts(MaybeUninit::first_ptr(&self.as_leaf().vals), self.len()) }
     }
 
     fn into_slices(self) -> (&'a [K], &'a [V]) {
@@ -639,9 +563,7 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
     /// Gets a mutable reference to the root itself. This is useful primarily when the
     /// height of the tree needs to be adjusted. Never call this on a reborrowed pointer.
     pub fn into_root_mut(self) -> &'a mut Root<K, V> {
-        unsafe {
-            &mut *(self.root as *mut Root<K, V>)
-        }
+        unsafe { &mut *(self.root as *mut Root<K, V>) }
     }
 
     fn into_key_slice_mut(mut self) -> &'a mut [K] {
@@ -653,7 +575,7 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
             unsafe {
                 slice::from_raw_parts_mut(
                     MaybeUninit::first_ptr_mut(&mut (*self.as_leaf_mut()).keys),
-                    self.len()
+                    self.len(),
                 )
             }
         }
@@ -664,7 +586,7 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
         unsafe {
             slice::from_raw_parts_mut(
                 MaybeUninit::first_ptr_mut(&mut (*self.as_leaf_mut()).vals),
-                self.len()
+                self.len(),
             )
         }
     }
@@ -679,14 +601,10 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
         unsafe {
             let len = self.len();
             let leaf = self.as_leaf_mut();
-            let keys = slice::from_raw_parts_mut(
-                MaybeUninit::first_ptr_mut(&mut (*leaf).keys),
-                len
-            );
-            let vals = slice::from_raw_parts_mut(
-                MaybeUninit::first_ptr_mut(&mut (*leaf).vals),
-                len
-            );
+            let keys =
+                slice::from_raw_parts_mut(MaybeUninit::first_ptr_mut(&mut (*leaf).keys), len);
+            let vals =
+                slice::from_raw_parts_mut(MaybeUninit::first_ptr_mut(&mut (*leaf).vals), len);
             (keys, vals)
         }
     }
@@ -769,10 +687,10 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
             slice_insert(
                 slice::from_raw_parts_mut(
                     MaybeUninit::first_ptr_mut(&mut self.as_internal_mut().edges),
-                    self.len()+1
+                    self.len() + 1,
                 ),
                 0,
-                edge.node
+                edge.node,
             );
 
             (*self.as_leaf_mut()).len += 1;
@@ -797,9 +715,8 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
             let edge = match self.reborrow_mut().force() {
                 ForceResult::Leaf(_) => None,
                 ForceResult::Internal(internal) => {
-                    let edge = ptr::read(
-                        internal.as_internal().edges.get_unchecked(idx + 1).as_ptr()
-                    );
+                    let edge =
+                        ptr::read(internal.as_internal().edges.get_unchecked(idx + 1).as_ptr());
                     let mut new_root = Root { node: edge, height: internal.height - 1 };
                     (*new_root.as_mut().as_leaf_mut()).parent = ptr::null();
                     Some(new_root)
@@ -828,9 +745,9 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
                     let edge = slice_remove(
                         slice::from_raw_parts_mut(
                             MaybeUninit::first_ptr_mut(&mut internal.as_internal_mut().edges),
-                            old_len+1
+                            old_len + 1,
                         ),
-                        0
+                        0,
                     );
 
                     let mut new_root = Root { node: edge, height: internal.height - 1 };
@@ -851,32 +768,31 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
     }
 
     fn into_kv_pointers_mut(mut self) -> (*mut K, *mut V) {
-        (
-            self.keys_mut().as_mut_ptr(),
-            self.vals_mut().as_mut_ptr()
-        )
+        (self.keys_mut().as_mut_ptr(), self.vals_mut().as_mut_ptr())
     }
 }
 
 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
     /// Checks whether a node is an `Internal` node or a `Leaf` node.
-    pub fn force(self) -> ForceResult<
+    pub fn force(
+        self,
+    ) -> ForceResult<
         NodeRef<BorrowType, K, V, marker::Leaf>,
-        NodeRef<BorrowType, K, V, marker::Internal>
+        NodeRef<BorrowType, K, V, marker::Internal>,
     > {
         if self.height == 0 {
             ForceResult::Leaf(NodeRef {
                 height: self.height,
                 node: self.node,
                 root: self.root,
-                _marker: PhantomData
+                _marker: PhantomData,
             })
         } else {
             ForceResult::Internal(NodeRef {
                 height: self.height,
                 node: self.node,
                 root: self.root,
-                _marker: PhantomData
+                _marker: PhantomData,
             })
         }
     }
@@ -893,10 +809,10 @@ impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
 pub struct Handle<Node, Type> {
     node: Node,
     idx: usize,
-    _marker: PhantomData<Type>
+    _marker: PhantomData<Type>,
 }
 
-impl<Node: Copy, Type> Copy for Handle<Node, Type> { }
+impl<Node: Copy, Type> Copy for Handle<Node, Type> {}
 // We don't need the full generality of `#[derive(Clone)]`, as the only time `Node` will be
 // `Clone`able is when it is an immutable reference and therefore `Copy`.
 impl<Node: Copy, Type> Clone for Handle<Node, Type> {
@@ -918,11 +834,7 @@ impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, mar
         // Necessary for correctness, but in a private module
         debug_assert!(idx < node.len());
 
-        Handle {
-            node,
-            idx,
-            _marker: PhantomData
-        }
+        Handle { node, idx, _marker: PhantomData }
     }
 
     pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
@@ -935,32 +847,24 @@ impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, mar
 }
 
 impl<BorrowType, K, V, NodeType, HandleType> PartialEq
-        for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
-
+    for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
+{
     fn eq(&self, other: &Self) -> bool {
         self.node.node == other.node.node && self.idx == other.idx
     }
 }
 
 impl<BorrowType, K, V, NodeType, HandleType>
-        Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
-
+    Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
+{
     /// Temporarily takes out another, immutable handle on the same location.
-    pub fn reborrow(&self)
-            -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> {
-
+    pub fn reborrow(&self) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> {
         // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
-        Handle {
-            node: self.node.reborrow(),
-            idx: self.idx,
-            _marker: PhantomData
-        }
+        Handle { node: self.node.reborrow(), idx: self.idx, _marker: PhantomData }
     }
 }
 
-impl<'a, K, V, NodeType, HandleType>
-        Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
-
+impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
     /// Temporarily takes out another, mutable handle on the same location. Beware, as
     /// this method is very dangerous, doubly so since it may not immediately appear
     /// dangerous.
@@ -971,52 +875,30 @@ impl<'a, K, V, NodeType, HandleType>
     /// of a reborrowed handle, out of bounds.
     // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef` that restricts
     // the use of `ascend` and `into_root_mut` on reborrowed pointers, preventing this unsafety.
-    pub unsafe fn reborrow_mut(&mut self)
-            -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> {
-
+    pub unsafe fn reborrow_mut(
+        &mut self,
+    ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> {
         // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
-        Handle {
-            node: self.node.reborrow_mut(),
-            idx: self.idx,
-            _marker: PhantomData
-        }
+        Handle { node: self.node.reborrow_mut(), idx: self.idx, _marker: PhantomData }
     }
 }
 
-impl<BorrowType, K, V, NodeType>
-        Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
-
+impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
     /// Creates a new handle to an edge in `node`. `idx` must be less than or equal to
     /// `node.len()`.
     pub fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
         // Necessary for correctness, but in a private module
         debug_assert!(idx <= node.len());
 
-        Handle {
-            node,
-            idx,
-            _marker: PhantomData
-        }
+        Handle { node, idx, _marker: PhantomData }
     }
 
-    pub fn left_kv(self)
-            -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
-
-        if self.idx > 0 {
-            Ok(Handle::new_kv(self.node, self.idx - 1))
-        } else {
-            Err(self)
-        }
+    pub fn left_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
+        if self.idx > 0 { Ok(Handle::new_kv(self.node, self.idx - 1)) } else { Err(self) }
     }
 
-    pub fn right_kv(self)
-            -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
-
-        if self.idx < self.node.len() {
-            Ok(Handle::new_kv(self.node, self.idx))
-        } else {
-            Err(self)
-        }
+    pub fn right_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
+        if self.idx < self.node.len() { Ok(Handle::new_kv(self.node, self.idx)) } else { Err(self) }
     }
 }
 
@@ -1045,9 +927,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge
     /// this edge. This method splits the node if there isn't enough room.
     ///
     /// The returned pointer points to the inserted value.
-    pub fn insert(mut self, key: K, val: V)
-            -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
-
+    pub fn insert(mut self, key: K, val: V) -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
         if self.node.len() < CAPACITY {
             let ptr = self.insert_fit(key, val);
             (InsertResult::Fit(Handle::new_kv(self.node, self.idx)), ptr)
@@ -1055,15 +935,14 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge
             let middle = Handle::new_kv(self.node, B);
             let (mut left, k, v, mut right) = middle.split();
             let ptr = if self.idx <= B {
-                unsafe {
-                    Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val)
-                }
+                unsafe { Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val) }
             } else {
                 unsafe {
                     Handle::new_edge(
                         right.as_mut().cast_unchecked::<marker::Leaf>(),
-                        self.idx - (B + 1)
-                    ).insert_fit(key, val)
+                        self.idx - (B + 1),
+                    )
+                    .insert_fit(key, val)
                 }
             };
             (InsertResult::Split(left, k, v, right), ptr)
@@ -1086,9 +965,9 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
 
     /// Unsafely asserts to the compiler some static information about whether the underlying
     /// node of this handle is a `Leaf`.
-    unsafe fn cast_unchecked<NewType>(&mut self)
-            -> Handle<NodeRef<marker::Mut<'_>, K, V, NewType>, marker::Edge> {
-
+    unsafe fn cast_unchecked<NewType>(
+        &mut self,
+    ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NewType>, marker::Edge> {
         Handle::new_edge(self.node.cast_unchecked(), self.idx)
     }
 
@@ -1107,13 +986,13 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
             slice_insert(
                 slice::from_raw_parts_mut(
                     MaybeUninit::first_ptr_mut(&mut self.node.as_internal_mut().edges),
-                    self.node.len()
+                    self.node.len(),
                 ),
                 self.idx + 1,
-                edge.node
+                edge.node,
             );
 
-            for i in (self.idx+1)..(self.node.len()+1) {
+            for i in (self.idx + 1)..(self.node.len() + 1) {
                 Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
             }
         }
@@ -1122,9 +1001,12 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
     /// Inserts a new key/value pair and an edge that will go to the right of that new pair
     /// between this edge and the key/value pair to the right of this edge. This method splits
     /// the node if there isn't enough room.
-    pub fn insert(mut self, key: K, val: V, edge: Root<K, V>)
-            -> InsertResult<'a, K, V, marker::Internal> {
-
+    pub fn insert(
+        mut self,
+        key: K,
+        val: V,
+        edge: Root<K, V>,
+    ) -> InsertResult<'a, K, V, marker::Internal> {
         // Necessary for correctness, but this is an internal module
         debug_assert!(edge.height == self.node.height - 1);
 
@@ -1142,8 +1024,9 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
                 unsafe {
                     Handle::new_edge(
                         right.as_mut().cast_unchecked::<marker::Internal>(),
-                        self.idx - (B + 1)
-                    ).insert_fit(key, val, edge);
+                        self.idx - (B + 1),
+                    )
+                    .insert_fit(key, val, edge);
                 }
             }
             InsertResult::Split(left, k, v, right)
@@ -1151,9 +1034,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
     }
 }
 
-impl<BorrowType, K, V>
-        Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
-
+impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
     /// Finds the node pointed to by this edge.
     ///
     /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
@@ -1165,30 +1046,22 @@ impl<BorrowType, K, V>
                 (&*self.node.as_internal().edges.get_unchecked(self.idx).as_ptr()).as_ptr()
             },
             root: self.node.root,
-            _marker: PhantomData
+            _marker: PhantomData,
         }
     }
 }
 
-impl<'a, K: 'a, V: 'a, NodeType>
-        Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
-
+impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
     pub fn into_kv(self) -> (&'a K, &'a V) {
         let (keys, vals) = self.node.into_slices();
-        unsafe {
-            (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx))
-        }
+        unsafe { (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx)) }
     }
 }
 
-impl<'a, K: 'a, V: 'a, NodeType>
-        Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
-
+impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
     pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
         let (keys, vals) = self.node.into_slices_mut();
-        unsafe {
-            (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
-        }
+        unsafe { (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx)) }
     }
 }
 
@@ -1209,8 +1082,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV>
     /// - The key and value pointed to by this handle and extracted.
     /// - All the key/value pairs to the right of this handle are put into a newly
     ///   allocated node.
-    pub fn split(mut self)
-            -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) {
+    pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) {
         debug_assert!(!self.node.is_shared_root());
         unsafe {
             let mut new_node = Box::new(LeafNode::new());
@@ -1223,32 +1095,26 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV>
             ptr::copy_nonoverlapping(
                 self.node.keys().as_ptr().add(self.idx + 1),
                 new_node.keys.as_mut_ptr() as *mut K,
-                new_len
+                new_len,
             );
             ptr::copy_nonoverlapping(
                 self.node.vals().as_ptr().add(self.idx + 1),
                 new_node.vals.as_mut_ptr() as *mut V,
-                new_len
+                new_len,
             );
 
             (*self.node.as_leaf_mut()).len = self.idx as u16;
             new_node.len = new_len as u16;
 
-            (
-                self.node,
-                k, v,
-                Root {
-                    node: BoxedNode::from_leaf(new_node),
-                    height: 0
-                }
-            )
+            (self.node, k, v, Root { node: BoxedNode::from_leaf(new_node), height: 0 })
         }
     }
 
     /// Removes the key/value pair pointed to by this handle, returning the edge between the
     /// now adjacent key/value pairs to the left and right of this handle.
-    pub fn remove(mut self)
-            -> (Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, K, V) {
+    pub fn remove(
+        mut self,
+    ) -> (Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, K, V) {
         debug_assert!(!self.node.is_shared_root());
         unsafe {
             let k = slice_remove(self.node.keys_mut(), self.idx);
@@ -1267,8 +1133,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
     /// - The key and value pointed to by this handle and extracted.
     /// - All the edges and key/value pairs to the right of this handle are put into
     ///   a newly allocated node.
-    pub fn split(mut self)
-            -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) {
+    pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) {
         unsafe {
             let mut new_node = Box::new(InternalNode::new());
 
@@ -1281,36 +1146,29 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
             ptr::copy_nonoverlapping(
                 self.node.keys().as_ptr().add(self.idx + 1),
                 new_node.data.keys.as_mut_ptr() as *mut K,
-                new_len
+                new_len,
             );
             ptr::copy_nonoverlapping(
                 self.node.vals().as_ptr().add(self.idx + 1),
                 new_node.data.vals.as_mut_ptr() as *mut V,
-                new_len
+                new_len,
             );
             ptr::copy_nonoverlapping(
                 self.node.as_internal().edges.as_ptr().add(self.idx + 1),
                 new_node.edges.as_mut_ptr(),
-                new_len + 1
+                new_len + 1,
             );
 
             (*self.node.as_leaf_mut()).len = self.idx as u16;
             new_node.data.len = new_len as u16;
 
-            let mut new_root = Root {
-                node: BoxedNode::from_internal(new_node),
-                height,
-            };
+            let mut new_root = Root { node: BoxedNode::from_internal(new_node), height };
 
-            for i in 0..(new_len+1) {
+            for i in 0..(new_len + 1) {
                 Handle::new_edge(new_root.as_mut().cast_unchecked(), i).correct_parent_link();
             }
 
-            (
-                self.node,
-                k, v,
-                new_root
-            )
+            (self.node, k, v, new_root)
         }
     }
 
@@ -1318,17 +1176,10 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
     /// a node to hold the combination of the nodes to the left and right of this handle along
     /// with the key/value pair at this handle.
     pub fn can_merge(&self) -> bool {
-        (
-            self.reborrow()
-                .left_edge()
-                .descend()
-                .len()
-          + self.reborrow()
-                .right_edge()
-                .descend()
-                .len()
-          + 1
-        ) <= CAPACITY
+        (self.reborrow().left_edge().descend().len()
+            + self.reborrow().right_edge().descend().len()
+            + 1)
+            <= CAPACITY
     }
 
     /// Combines the node immediately to the left of this handle, the key/value pair pointed
@@ -1336,8 +1187,9 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
     /// child of the underlying node, returning an edge referencing that new child.
     ///
     /// Assumes that this edge `.can_merge()`.
-    pub fn merge(mut self)
-            -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
+    pub fn merge(
+        mut self,
+    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
         let self1 = unsafe { ptr::read(&self) };
         let self2 = unsafe { ptr::read(&self) };
         let mut left_node = self1.left_edge().descend();
@@ -1349,23 +1201,27 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
         debug_assert!(left_len + right_len + 1 <= CAPACITY);
 
         unsafe {
-            ptr::write(left_node.keys_mut().get_unchecked_mut(left_len),
-                       slice_remove(self.node.keys_mut(), self.idx));
+            ptr::write(
+                left_node.keys_mut().get_unchecked_mut(left_len),
+                slice_remove(self.node.keys_mut(), self.idx),
+            );
             ptr::copy_nonoverlapping(
                 right_node.keys().as_ptr(),
                 left_node.keys_mut().as_mut_ptr().add(left_len + 1),
-                right_len
+                right_len,
+            );
+            ptr::write(
+                left_node.vals_mut().get_unchecked_mut(left_len),
+                slice_remove(self.node.vals_mut(), self.idx),
             );
-            ptr::write(left_node.vals_mut().get_unchecked_mut(left_len),
-                       slice_remove(self.node.vals_mut(), self.idx));
             ptr::copy_nonoverlapping(
                 right_node.vals().as_ptr(),
                 left_node.vals_mut().as_mut_ptr().add(left_len + 1),
-                right_len
+                right_len,
             );
 
             slice_remove(&mut self.node.as_internal_mut().edges, self.idx + 1);
-            for i in self.idx+1..self.node.len() {
+            for i in self.idx + 1..self.node.len() {
                 Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
             }
             (*self.node.as_leaf_mut()).len -= 1;
@@ -1375,30 +1231,23 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
             if self.node.height > 1 {
                 ptr::copy_nonoverlapping(
                     right_node.cast_unchecked().as_internal().edges.as_ptr(),
-                    left_node.cast_unchecked()
-                             .as_internal_mut()
-                             .edges
-                             .as_mut_ptr()
-                             .add(left_len + 1),
-                    right_len + 1
+                    left_node
+                        .cast_unchecked()
+                        .as_internal_mut()
+                        .edges
+                        .as_mut_ptr()
+                        .add(left_len + 1),
+                    right_len + 1,
                 );
 
-                for i in left_len+1..left_len+right_len+2 {
-                    Handle::new_edge(
-                        left_node.cast_unchecked().reborrow_mut(),
-                        i
-                    ).correct_parent_link();
+                for i in left_len + 1..left_len + right_len + 2 {
+                    Handle::new_edge(left_node.cast_unchecked().reborrow_mut(), i)
+                        .correct_parent_link();
                 }
 
-                Global.dealloc(
-                    right_node.node.cast(),
-                    Layout::new::<InternalNode<K, V>>(),
-                );
+                Global.dealloc(right_node.node.cast(), Layout::new::<InternalNode<K, V>>());
             } else {
-                Global.dealloc(
-                    right_node.node.cast(),
-                    Layout::new::<LeafNode<K, V>>(),
-                );
+                Global.dealloc(right_node.node.cast(), Layout::new::<LeafNode<K, V>>());
             }
 
             Handle::new_edge(self.node, self.idx)
@@ -1417,7 +1266,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
 
             match self.reborrow_mut().right_edge().descend().force() {
                 ForceResult::Leaf(mut leaf) => leaf.push_front(k, v),
-                ForceResult::Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
+                ForceResult::Internal(mut internal) => internal.push_front(k, v, edge.unwrap()),
             }
         }
     }
@@ -1434,7 +1283,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
 
             match self.reborrow_mut().left_edge().descend().force() {
                 ForceResult::Leaf(mut leaf) => leaf.push(k, v),
-                ForceResult::Internal(mut internal) => internal.push(k, v, edge.unwrap())
+                ForceResult::Internal(mut internal) => internal.push(k, v, edge.unwrap()),
             }
         }
     }
@@ -1463,12 +1312,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
                 };
 
                 // Make room for stolen elements in the right child.
-                ptr::copy(right_kv.0,
-                          right_kv.0.add(count),
-                          right_len);
-                ptr::copy(right_kv.1,
-                          right_kv.1.add(count),
-                          right_len);
+                ptr::copy(right_kv.0, right_kv.0.add(count), right_len);
+                ptr::copy(right_kv.1, right_kv.1.add(count), right_len);
 
                 // Move elements from the left child to the right one.
                 move_kv(left_kv, new_left_len + 1, right_kv, 0, count - 1);
@@ -1487,15 +1332,15 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
                 (ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
                     // Make room for stolen edges.
                     let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr();
-                    ptr::copy(right_edges,
-                              right_edges.add(count),
-                              right_len + 1);
+                    ptr::copy(right_edges, right_edges.add(count), right_len + 1);
                     right.correct_childrens_parent_links(count, count + right_len + 1);
 
                     move_edges(left, new_left_len + 1, right, 0, count);
-                },
-                (ForceResult::Leaf(_), ForceResult::Leaf(_)) => { }
-                _ => { unreachable!(); }
+                }
+                (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
+                _ => {
+                    unreachable!();
+                }
             }
         }
     }
@@ -1533,12 +1378,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
                 move_kv(right_kv, count - 1, parent_kv, 0, 1);
 
                 // Fix right indexing
-                ptr::copy(right_kv.0.add(count),
-                          right_kv.0,
-                          new_right_len);
-                ptr::copy(right_kv.1.add(count),
-                          right_kv.1,
-                          new_right_len);
+                ptr::copy(right_kv.0.add(count), right_kv.0, new_right_len);
+                ptr::copy(right_kv.1.add(count), right_kv.1, new_right_len);
             }
 
             (*left_node.reborrow_mut().as_leaf_mut()).len += count as u16;
@@ -1550,64 +1391,60 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
 
                     // Fix right indexing.
                     let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr();
-                    ptr::copy(right_edges.add(count),
-                              right_edges,
-                              new_right_len + 1);
+                    ptr::copy(right_edges.add(count), right_edges, new_right_len + 1);
                     right.correct_childrens_parent_links(0, new_right_len + 1);
-                },
-                (ForceResult::Leaf(_), ForceResult::Leaf(_)) => { }
-                _ => { unreachable!(); }
+                }
+                (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
+                _ => {
+                    unreachable!();
+                }
             }
         }
     }
 }
 
 unsafe fn move_kv<K, V>(
-    source: (*mut K, *mut V), source_offset: usize,
-    dest: (*mut K, *mut V), dest_offset: usize,
-    count: usize)
-{
-    ptr::copy_nonoverlapping(source.0.add(source_offset),
-                             dest.0.add(dest_offset),
-                             count);
-    ptr::copy_nonoverlapping(source.1.add(source_offset),
-                             dest.1.add(dest_offset),
-                             count);
+    source: (*mut K, *mut V),
+    source_offset: usize,
+    dest: (*mut K, *mut V),
+    dest_offset: usize,
+    count: usize,
+) {
+    ptr::copy_nonoverlapping(source.0.add(source_offset), dest.0.add(dest_offset), count);
+    ptr::copy_nonoverlapping(source.1.add(source_offset), dest.1.add(dest_offset), count);
 }
 
 // Source and destination must have the same height.
 unsafe fn move_edges<K, V>(
-    mut source: NodeRef<marker::Mut<'_>, K, V, marker::Internal>, source_offset: usize,
-    mut dest: NodeRef<marker::Mut<'_>, K, V, marker::Internal>, dest_offset: usize,
-    count: usize)
-{
+    mut source: NodeRef<marker::Mut<'_>, K, V, marker::Internal>,
+    source_offset: usize,
+    mut dest: NodeRef<marker::Mut<'_>, K, V, marker::Internal>,
+    dest_offset: usize,
+    count: usize,
+) {
     let source_ptr = source.as_internal_mut().edges.as_mut_ptr();
     let dest_ptr = dest.as_internal_mut().edges.as_mut_ptr();
-    ptr::copy_nonoverlapping(source_ptr.add(source_offset),
-                             dest_ptr.add(dest_offset),
-                             count);
+    ptr::copy_nonoverlapping(source_ptr.add(source_offset), dest_ptr.add(dest_offset), count);
     dest.correct_childrens_parent_links(dest_offset, dest_offset + count);
 }
 
 impl<BorrowType, K, V, HandleType>
-        Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType> {
-
+    Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType>
+{
     /// Checks whether the underlying node is an `Internal` node or a `Leaf` node.
-    pub fn force(self) -> ForceResult<
+    pub fn force(
+        self,
+    ) -> ForceResult<
         Handle<NodeRef<BorrowType, K, V, marker::Leaf>, HandleType>,
-        Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>
+        Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>,
     > {
         match self.node.force() {
-            ForceResult::Leaf(node) => ForceResult::Leaf(Handle {
-                node,
-                idx: self.idx,
-                _marker: PhantomData
-            }),
-            ForceResult::Internal(node) => ForceResult::Internal(Handle {
-                node,
-                idx: self.idx,
-                _marker: PhantomData
-            })
+            ForceResult::Leaf(node) => {
+                ForceResult::Leaf(Handle { node, idx: self.idx, _marker: PhantomData })
+            }
+            ForceResult::Internal(node) => {
+                ForceResult::Internal(Handle { node, idx: self.idx, _marker: PhantomData })
+            }
         }
     }
 }
@@ -1615,8 +1452,10 @@ impl<BorrowType, K, V, HandleType>
 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
     /// Move the suffix after `self` from one node to another one. `right` must be empty.
     /// The first edge of `right` remains unchanged.
-    pub fn move_suffix(&mut self,
-            right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>) {
+    pub fn move_suffix(
+        &mut self,
+        right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
+    ) {
         unsafe {
             let left_new_len = self.idx;
             let mut left_node = self.reborrow_mut().into_node();
@@ -1630,7 +1469,6 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, ma
             let left_kv = left_node.reborrow_mut().into_kv_pointers_mut();
             let right_kv = right_node.reborrow_mut().into_kv_pointers_mut();
 
-
             move_kv(left_kv, left_new_len, right_kv, 0, right_new_len);
 
             (*left_node.reborrow_mut().as_leaf_mut()).len = left_new_len as u16;
@@ -1639,9 +1477,11 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, ma
             match (left_node.force(), right_node.force()) {
                 (ForceResult::Internal(left), ForceResult::Internal(right)) => {
                     move_edges(left, left_new_len + 1, right, 1, right_new_len);
-                },
-                (ForceResult::Leaf(_), ForceResult::Leaf(_)) => { }
-                _ => { unreachable!(); }
+                }
+                (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
+                _ => {
+                    unreachable!();
+                }
             }
         }
     }
@@ -1649,44 +1489,36 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, ma
 
 pub enum ForceResult<Leaf, Internal> {
     Leaf(Leaf),
-    Internal(Internal)
+    Internal(Internal),
 }
 
 pub enum InsertResult<'a, K, V, Type> {
     Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>),
-    Split(NodeRef<marker::Mut<'a>, K, V, Type>, K, V, Root<K, V>)
+    Split(NodeRef<marker::Mut<'a>, K, V, Type>, K, V, Root<K, V>),
 }
 
 pub mod marker {
     use core::marker::PhantomData;
 
-    pub enum Leaf { }
-    pub enum Internal { }
-    pub enum LeafOrInternal { }
+    pub enum Leaf {}
+    pub enum Internal {}
+    pub enum LeafOrInternal {}
 
-    pub enum Owned { }
+    pub enum Owned {}
     pub struct Immut<'a>(PhantomData<&'a ()>);
     pub struct Mut<'a>(PhantomData<&'a mut ()>);
 
-    pub enum KV { }
-    pub enum Edge { }
+    pub enum KV {}
+    pub enum Edge {}
 }
 
 unsafe fn slice_insert<T>(slice: &mut [T], idx: usize, val: T) {
-    ptr::copy(
-        slice.as_ptr().add(idx),
-        slice.as_mut_ptr().add(idx + 1),
-        slice.len() - idx
-    );
+    ptr::copy(slice.as_ptr().add(idx), slice.as_mut_ptr().add(idx + 1), slice.len() - idx);
     ptr::write(slice.get_unchecked_mut(idx), val);
 }
 
 unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T {
     let ret = ptr::read(slice.get_unchecked(idx));
-    ptr::copy(
-        slice.as_ptr().add(idx + 1),
-        slice.as_mut_ptr().add(idx),
-        slice.len() - idx - 1
-    );
+    ptr::copy(slice.as_ptr().add(idx + 1), slice.as_mut_ptr().add(idx), slice.len() - idx - 1);
     ret
 }
diff --git a/src/liballoc/collections/btree/set.rs b/src/liballoc/collections/btree/set.rs
index 85b93e0eda4..282d163141b 100644
--- a/src/liballoc/collections/btree/set.rs
+++ b/src/liballoc/collections/btree/set.rs
@@ -2,14 +2,14 @@
 // to TreeMap
 
 use core::borrow::Borrow;
-use core::cmp::Ordering::{Less, Greater, Equal};
+use core::cmp::Ordering::{Equal, Greater, Less};
 use core::cmp::{max, min};
 use core::fmt::{self, Debug};
-use core::iter::{Peekable, FromIterator, FusedIterator};
-use core::ops::{BitOr, BitAnd, BitXor, Sub, RangeBounds};
+use core::iter::{FromIterator, FusedIterator, Peekable};
+use core::ops::{BitAnd, BitOr, BitXor, RangeBounds, Sub};
 
-use crate::collections::btree_map::{self, BTreeMap, Keys};
 use super::Recover;
+use crate::collections::btree_map::{self, BTreeMap, Keys};
 
 // FIXME(conventions): implement bounded iterators
 
@@ -77,9 +77,7 @@ pub struct Iter<'a, T: 'a> {
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("Iter")
-         .field(&self.iter.clone())
-         .finish()
+        f.debug_tuple("Iter").field(&self.iter.clone()).finish()
     }
 }
 
@@ -114,8 +112,9 @@ pub struct Range<'a, T: 'a> {
 /// and crucially for SymmetricDifference, nexts() reports on both sides.
 #[derive(Clone)]
 struct MergeIterInner<I>
-    where I: Iterator,
-          I::Item: Copy,
+where
+    I: Iterator,
+    I::Item: Copy,
 {
     a: I,
     b: I,
@@ -129,8 +128,9 @@ enum MergeIterPeeked<I: Iterator> {
 }
 
 impl<I> MergeIterInner<I>
-    where I: ExactSizeIterator + FusedIterator,
-          I::Item: Copy + Ord,
+where
+    I: ExactSizeIterator + FusedIterator,
+    I::Item: Copy + Ord,
 {
     fn new(a: I, b: I) -> Self {
         MergeIterInner { a, b, peeked: None }
@@ -169,14 +169,12 @@ impl<I> MergeIterInner<I>
 }
 
 impl<I> Debug for MergeIterInner<I>
-    where I: Iterator + Debug,
-          I::Item: Copy + Debug,
+where
+    I: Iterator + Debug,
+    I::Item: Copy + Debug,
 {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("MergeIterInner")
-            .field(&self.a)
-            .field(&self.b)
-            .finish()
+        f.debug_tuple("MergeIterInner").field(&self.a).field(&self.b).finish()
     }
 }
 
@@ -328,7 +326,10 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[stable(feature = "btree_range", since = "1.17.0")]
     pub fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T>
-        where K: Ord, T: Borrow<K>, R: RangeBounds<K>
+    where
+        K: Ord,
+        T: Borrow<K>,
+        R: RangeBounds<K>,
     {
         Range { iter: self.map.range(range) }
     }
@@ -355,24 +356,18 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T> {
-        let (self_min, self_max) = if let (Some(self_min), Some(self_max)) =
-            (self.first(), self.last())
-        {
-            (self_min, self_max)
-        } else {
-            return Difference {
-                inner: DifferenceInner::Iterate(self.iter()),
+        let (self_min, self_max) =
+            if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
+                (self_min, self_max)
+            } else {
+                return Difference { inner: DifferenceInner::Iterate(self.iter()) };
             };
-        };
-        let (other_min, other_max) = if let (Some(other_min), Some(other_max)) =
-            (other.first(), other.last())
-        {
-            (other_min, other_max)
-        } else {
-            return Difference {
-                inner: DifferenceInner::Iterate(self.iter()),
+        let (other_min, other_max) =
+            if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
+                (other_min, other_max)
+            } else {
+                return Difference { inner: DifferenceInner::Iterate(self.iter()) };
             };
-        };
         Difference {
             inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
                 (Greater, _) | (_, Less) => DifferenceInner::Iterate(self.iter()),
@@ -387,10 +382,7 @@ impl<T: Ord> BTreeSet<T> {
                     DifferenceInner::Iterate(self_iter)
                 }
                 _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
-                    DifferenceInner::Search {
-                        self_iter: self.iter(),
-                        other_set: other,
-                    }
+                    DifferenceInner::Search { self_iter: self.iter(), other_set: other }
                 }
                 _ => DifferenceInner::Stitch {
                     self_iter: self.iter(),
@@ -421,9 +413,10 @@ impl<T: Ord> BTreeSet<T> {
     /// assert_eq!(sym_diff, [1, 3]);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn symmetric_difference<'a>(&'a self,
-                                    other: &'a BTreeSet<T>)
-                                    -> SymmetricDifference<'a, T> {
+    pub fn symmetric_difference<'a>(
+        &'a self,
+        other: &'a BTreeSet<T>,
+    ) -> SymmetricDifference<'a, T> {
         SymmetricDifference(MergeIterInner::new(self.iter(), other.iter()))
     }
 
@@ -449,45 +442,30 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T> {
-        let (self_min, self_max) = if let (Some(self_min), Some(self_max)) =
-            (self.first(), self.last())
-        {
-            (self_min, self_max)
-        } else {
-            return Intersection {
-                inner: IntersectionInner::Answer(None),
+        let (self_min, self_max) =
+            if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
+                (self_min, self_max)
+            } else {
+                return Intersection { inner: IntersectionInner::Answer(None) };
             };
-        };
-        let (other_min, other_max) = if let (Some(other_min), Some(other_max)) =
-            (other.first(), other.last())
-        {
-            (other_min, other_max)
-        } else {
-            return Intersection {
-                inner: IntersectionInner::Answer(None),
+        let (other_min, other_max) =
+            if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
+                (other_min, other_max)
+            } else {
+                return Intersection { inner: IntersectionInner::Answer(None) };
             };
-        };
         Intersection {
             inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
                 (Greater, _) | (_, Less) => IntersectionInner::Answer(None),
                 (Equal, _) => IntersectionInner::Answer(Some(self_min)),
                 (_, Equal) => IntersectionInner::Answer(Some(self_max)),
                 _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
-                    IntersectionInner::Search {
-                        small_iter: self.iter(),
-                        large_set: other,
-                    }
+                    IntersectionInner::Search { small_iter: self.iter(), large_set: other }
                 }
                 _ if other.len() <= self.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
-                    IntersectionInner::Search {
-                        small_iter: other.iter(),
-                        large_set: self,
-                    }
+                    IntersectionInner::Search { small_iter: other.iter(), large_set: self }
                 }
-                _ => IntersectionInner::Stitch {
-                    a: self.iter(),
-                    b: other.iter(),
-                },
+                _ => IntersectionInner::Stitch { a: self.iter(), b: other.iter() },
             },
         }
     }
@@ -549,8 +527,9 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
-        where T: Borrow<Q>,
-              Q: Ord
+    where
+        T: Borrow<Q>,
+        Q: Ord,
     {
         self.map.contains_key(value)
     }
@@ -572,8 +551,9 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[stable(feature = "set_recovery", since = "1.9.0")]
     pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
-        where T: Borrow<Q>,
-              Q: Ord
+    where
+        T: Borrow<Q>,
+        Q: Ord,
     {
         Recover::get(&self.map, value)
     }
@@ -624,20 +604,18 @@ impl<T: Ord> BTreeSet<T> {
         if self.len() > other.len() {
             return false;
         }
-        let (self_min, self_max) = if let (Some(self_min), Some(self_max)) =
-            (self.first(), self.last())
-        {
-            (self_min, self_max)
-        } else {
-            return true; // self is empty
-        };
-        let (other_min, other_max) = if let (Some(other_min), Some(other_max)) =
-            (other.first(), other.last())
-        {
-            (other_min, other_max)
-        } else {
-            return false; // other is empty
-        };
+        let (self_min, self_max) =
+            if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
+                (self_min, self_max)
+            } else {
+                return true; // self is empty
+            };
+        let (other_min, other_max) =
+            if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
+                (other_min, other_max)
+            } else {
+                return false; // other is empty
+            };
         let mut self_iter = self.iter();
         match self_min.cmp(other_min) {
             Less => return false,
@@ -855,8 +833,9 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
-        where T: Borrow<Q>,
-              Q: Ord
+    where
+        T: Borrow<Q>,
+        Q: Ord,
     {
         self.map.remove(value).is_some()
     }
@@ -878,8 +857,9 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[stable(feature = "set_recovery", since = "1.9.0")]
     pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
-        where T: Borrow<Q>,
-              Q: Ord
+    where
+        T: Borrow<Q>,
+        Q: Ord,
     {
         Recover::take(&mut self.map, value)
     }
@@ -947,7 +927,10 @@ impl<T: Ord> BTreeSet<T> {
     /// assert!(b.contains(&41));
     /// ```
     #[stable(feature = "btree_split_off", since = "1.11.0")]
-    pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self where T: Borrow<Q> {
+    pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
+    where
+        T: Borrow<Q>,
+    {
         BTreeSet { map: self.map.split_off(key) }
     }
 }
@@ -1213,7 +1196,9 @@ impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ExactSizeIterator for Iter<'_, T> {
-    fn len(&self) -> usize { self.iter.len() }
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
 }
 
 #[stable(feature = "fused", since = "1.26.0")]
@@ -1238,7 +1223,9 @@ impl<T> DoubleEndedIterator for IntoIter<T> {
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ExactSizeIterator for IntoIter<T> {
-    fn len(&self) -> usize { self.iter.len() }
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
 }
 
 #[stable(feature = "fused", since = "1.26.0")]
@@ -1279,20 +1266,13 @@ impl<T> Clone for Difference<'_, T> {
     fn clone(&self) -> Self {
         Difference {
             inner: match &self.inner {
-                DifferenceInner::Stitch {
-                    self_iter,
-                    other_iter,
-                } => DifferenceInner::Stitch {
+                DifferenceInner::Stitch { self_iter, other_iter } => DifferenceInner::Stitch {
                     self_iter: self_iter.clone(),
                     other_iter: other_iter.clone(),
                 },
-                DifferenceInner::Search {
-                    self_iter,
-                    other_set,
-                } => DifferenceInner::Search {
-                    self_iter: self_iter.clone(),
-                    other_set,
-                },
+                DifferenceInner::Search { self_iter, other_set } => {
+                    DifferenceInner::Search { self_iter: self_iter.clone(), other_set }
+                }
                 DifferenceInner::Iterate(iter) => DifferenceInner::Iterate(iter.clone()),
             },
         }
@@ -1304,16 +1284,10 @@ impl<'a, T: Ord> Iterator for Difference<'a, T> {
 
     fn next(&mut self) -> Option<&'a T> {
         match &mut self.inner {
-            DifferenceInner::Stitch {
-                self_iter,
-                other_iter,
-            } => {
+            DifferenceInner::Stitch { self_iter, other_iter } => {
                 let mut self_next = self_iter.next()?;
                 loop {
-                    match other_iter
-                        .peek()
-                        .map_or(Less, |other_next| self_next.cmp(other_next))
-                    {
+                    match other_iter.peek().map_or(Less, |other_next| self_next.cmp(other_next)) {
                         Less => return Some(self_next),
                         Equal => {
                             self_next = self_iter.next()?;
@@ -1325,10 +1299,7 @@ impl<'a, T: Ord> Iterator for Difference<'a, T> {
                     }
                 }
             }
-            DifferenceInner::Search {
-                self_iter,
-                other_set,
-            } => loop {
+            DifferenceInner::Search { self_iter, other_set } => loop {
                 let self_next = self_iter.next()?;
                 if !other_set.contains(&self_next) {
                     return Some(self_next);
@@ -1340,14 +1311,10 @@ impl<'a, T: Ord> Iterator for Difference<'a, T> {
 
     fn size_hint(&self) -> (usize, Option<usize>) {
         let (self_len, other_len) = match &self.inner {
-            DifferenceInner::Stitch {
-                self_iter,
-                other_iter,
-            } => (self_iter.len(), other_iter.len()),
-            DifferenceInner::Search {
-                self_iter,
-                other_set,
-            } => (self_iter.len(), other_set.len()),
+            DifferenceInner::Stitch { self_iter, other_iter } => {
+                (self_iter.len(), other_iter.len())
+            }
+            DifferenceInner::Search { self_iter, other_set } => (self_iter.len(), other_set.len()),
             DifferenceInner::Iterate(iter) => (iter.len(), 0),
         };
         (self_len.saturating_sub(other_len), Some(self_len))
@@ -1393,20 +1360,12 @@ impl<T> Clone for Intersection<'_, T> {
     fn clone(&self) -> Self {
         Intersection {
             inner: match &self.inner {
-                IntersectionInner::Stitch {
-                    a,
-                    b,
-                } => IntersectionInner::Stitch {
-                    a: a.clone(),
-                    b: b.clone(),
-                },
-                IntersectionInner::Search {
-                    small_iter,
-                    large_set,
-                } => IntersectionInner::Search {
-                    small_iter: small_iter.clone(),
-                    large_set,
-                },
+                IntersectionInner::Stitch { a, b } => {
+                    IntersectionInner::Stitch { a: a.clone(), b: b.clone() }
+                }
+                IntersectionInner::Search { small_iter, large_set } => {
+                    IntersectionInner::Search { small_iter: small_iter.clone(), large_set }
+                }
                 IntersectionInner::Answer(answer) => IntersectionInner::Answer(*answer),
             },
         }
@@ -1418,10 +1377,7 @@ impl<'a, T: Ord> Iterator for Intersection<'a, T> {
 
     fn next(&mut self) -> Option<&'a T> {
         match &mut self.inner {
-            IntersectionInner::Stitch {
-                a,
-                b,
-            } => {
+            IntersectionInner::Stitch { a, b } => {
                 let mut a_next = a.next()?;
                 let mut b_next = b.next()?;
                 loop {
@@ -1432,10 +1388,7 @@ impl<'a, T: Ord> Iterator for Intersection<'a, T> {
                     }
                 }
             }
-            IntersectionInner::Search {
-                small_iter,
-                large_set,
-            } => loop {
+            IntersectionInner::Search { small_iter, large_set } => loop {
                 let small_next = small_iter.next()?;
                 if large_set.contains(&small_next) {
                     return Some(small_next);
diff --git a/src/liballoc/collections/linked_list.rs b/src/liballoc/collections/linked_list.rs
index 5a6d4ee2aea..4931093c55c 100644
--- a/src/liballoc/collections/linked_list.rs
+++ b/src/liballoc/collections/linked_list.rs
@@ -14,14 +14,14 @@
 
 use core::cmp::Ordering;
 use core::fmt;
-use core::hash::{Hasher, Hash};
+use core::hash::{Hash, Hasher};
 use core::iter::{FromIterator, FusedIterator};
 use core::marker::PhantomData;
 use core::mem;
 use core::ptr::NonNull;
 
-use crate::boxed::Box;
 use super::SpecExtend;
+use crate::boxed::Box;
 
 #[cfg(test)]
 mod tests;
@@ -66,9 +66,7 @@ pub struct Iter<'a, T: 'a> {
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("Iter")
-         .field(&self.len)
-         .finish()
+        f.debug_tuple("Iter").field(&self.len).finish()
     }
 }
 
@@ -101,10 +99,7 @@ pub struct IterMut<'a, T: 'a> {
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("IterMut")
-         .field(&self.list)
-         .field(&self.len)
-         .finish()
+        f.debug_tuple("IterMut").field(&self.list).field(&self.len).finish()
     }
 }
 
@@ -124,19 +119,13 @@ pub struct IntoIter<T> {
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("IntoIter")
-         .field(&self.list)
-         .finish()
+        f.debug_tuple("IntoIter").field(&self.list).finish()
     }
 }
 
 impl<T> Node<T> {
     fn new(element: T) -> Self {
-        Node {
-            next: None,
-            prev: None,
-            element,
-        }
+        Node { next: None, prev: None, element }
     }
 
     fn into_element(self: Box<Self>) -> T {
@@ -278,12 +267,7 @@ impl<T> LinkedList<T> {
     #[rustc_const_stable(feature = "const_linked_list_new", since = "1.32.0")]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub const fn new() -> Self {
-        LinkedList {
-            head: None,
-            tail: None,
-            len: 0,
-            marker: PhantomData,
-        }
+        LinkedList { head: None, tail: None, len: 0, marker: PhantomData }
     }
 
     /// Moves all elements from `other` to the end of the list.
@@ -357,12 +341,7 @@ impl<T> LinkedList<T> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn iter(&self) -> Iter<'_, T> {
-        Iter {
-            head: self.head,
-            tail: self.tail,
-            len: self.len,
-            marker: PhantomData,
-        }
+        Iter { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
     }
 
     /// Provides a forward iterator with mutable references.
@@ -391,12 +370,7 @@ impl<T> LinkedList<T> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn iter_mut(&mut self) -> IterMut<'_, T> {
-        IterMut {
-            head: self.head,
-            tail: self.tail,
-            len: self.len,
-            list: self,
-        }
+        IterMut { head: self.head, tail: self.tail, len: self.len, list: self }
     }
 
     /// Returns `true` if the `LinkedList` is empty.
@@ -491,7 +465,8 @@ impl<T> LinkedList<T> {
     /// ```
     #[stable(feature = "linked_list_contains", since = "1.12.0")]
     pub fn contains(&self, x: &T) -> bool
-        where T: PartialEq<T>
+    where
+        T: PartialEq<T>,
     {
         self.iter().any(|e| e == x)
     }
@@ -513,9 +488,7 @@ impl<T> LinkedList<T> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn front(&self) -> Option<&T> {
-        unsafe {
-            self.head.as_ref().map(|node| &node.as_ref().element)
-        }
+        unsafe { self.head.as_ref().map(|node| &node.as_ref().element) }
     }
 
     /// Provides a mutable reference to the front element, or `None` if the list
@@ -541,9 +514,7 @@ impl<T> LinkedList<T> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn front_mut(&mut self) -> Option<&mut T> {
-        unsafe {
-            self.head.as_mut().map(|node| &mut node.as_mut().element)
-        }
+        unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
     }
 
     /// Provides a reference to the back element, or `None` if the list is
@@ -563,9 +534,7 @@ impl<T> LinkedList<T> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn back(&self) -> Option<&T> {
-        unsafe {
-            self.tail.as_ref().map(|node| &node.as_ref().element)
-        }
+        unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) }
     }
 
     /// Provides a mutable reference to the back element, or `None` if the list
@@ -591,9 +560,7 @@ impl<T> LinkedList<T> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn back_mut(&mut self) -> Option<&mut T> {
-        unsafe {
-            self.tail.as_mut().map(|node| &mut node.as_mut().element)
-        }
+        unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) }
     }
 
     /// Adds an element first in the list.
@@ -790,19 +757,14 @@ impl<T> LinkedList<T> {
     /// ```
     #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
     pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>
-        where F: FnMut(&mut T) -> bool
+    where
+        F: FnMut(&mut T) -> bool,
     {
         // avoid borrow issues.
         let it = self.head;
         let old_len = self.len;
 
-        DrainFilter {
-            list: self,
-            it: it,
-            pred: filter,
-            idx: 0,
-            old_len: old_len,
-        }
+        DrainFilter { list: self, it: it, pred: filter, idx: 0, old_len: old_len }
     }
 }
 
@@ -960,9 +922,11 @@ impl<T> IterMut<'_, T> {
     /// }
     /// ```
     #[inline]
-    #[unstable(feature = "linked_list_extras",
-               reason = "this is probably better handled by a cursor type -- we'll see",
-               issue = "27794")]
+    #[unstable(
+        feature = "linked_list_extras",
+        reason = "this is probably better handled by a cursor type -- we'll see",
+        issue = "27794"
+    )]
     pub fn insert_next(&mut self, element: T) {
         match self.head {
             // `push_back` is okay with aliasing `element` references
@@ -1008,16 +972,16 @@ impl<T> IterMut<'_, T> {
     /// assert_eq!(it.next().unwrap(), &2);
     /// ```
     #[inline]
-    #[unstable(feature = "linked_list_extras",
-               reason = "this is probably better handled by a cursor type -- we'll see",
-               issue = "27794")]
+    #[unstable(
+        feature = "linked_list_extras",
+        reason = "this is probably better handled by a cursor type -- we'll see",
+        issue = "27794"
+    )]
     pub fn peek_next(&mut self) -> Option<&mut T> {
         if self.len == 0 {
             None
         } else {
-            unsafe {
-                self.head.as_mut().map(|node| &mut node.as_mut().element)
-            }
+            unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
         }
     }
 }
@@ -1025,7 +989,8 @@ impl<T> IterMut<'_, T> {
 /// An iterator produced by calling `drain_filter` on LinkedList.
 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
 pub struct DrainFilter<'a, T: 'a, F: 'a>
-    where F: FnMut(&mut T) -> bool,
+where
+    F: FnMut(&mut T) -> bool,
 {
     list: &'a mut LinkedList<T>,
     it: Option<NonNull<Node<T>>>,
@@ -1036,7 +1001,8 @@ pub struct DrainFilter<'a, T: 'a, F: 'a>
 
 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
 impl<T, F> Iterator for DrainFilter<'_, T, F>
-    where F: FnMut(&mut T) -> bool,
+where
+    F: FnMut(&mut T) -> bool,
 {
     type Item = T;
 
@@ -1064,7 +1030,8 @@ impl<T, F> Iterator for DrainFilter<'_, T, F>
 
 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
 impl<T, F> Drop for DrainFilter<'_, T, F>
-    where F: FnMut(&mut T) -> bool,
+where
+    F: FnMut(&mut T) -> bool,
 {
     fn drop(&mut self) {
         self.for_each(drop);
@@ -1073,12 +1040,11 @@ impl<T, F> Drop for DrainFilter<'_, T, F>
 
 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
 impl<T: fmt::Debug, F> fmt::Debug for DrainFilter<'_, T, F>
-    where F: FnMut(&mut T) -> bool
+where
+    F: FnMut(&mut T) -> bool,
 {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("DrainFilter")
-         .field(&self.list)
-         .finish()
+        f.debug_tuple("DrainFilter").field(&self.list).finish()
     }
 }
 
diff --git a/src/liballoc/collections/mod.rs b/src/liballoc/collections/mod.rs
index 390a48180c0..0bb62373fab 100644
--- a/src/liballoc/collections/mod.rs
+++ b/src/liballoc/collections/mod.rs
@@ -45,7 +45,7 @@ use crate::alloc::{Layout, LayoutErr};
 
 /// The error type for `try_reserve` methods.
 #[derive(Clone, PartialEq, Eq, Debug)]
-#[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
+#[unstable(feature = "try_reserve", reason = "new API", issue = "48043")]
 pub enum TryReserveError {
     /// Error due to the computed capacity exceeding the collection's maximum
     /// (usually `isize::MAX` bytes).
@@ -57,15 +57,19 @@ pub enum TryReserveError {
         layout: Layout,
 
         #[doc(hidden)]
-        #[unstable(feature = "container_error_extra", issue = "none", reason = "\
+        #[unstable(
+            feature = "container_error_extra",
+            issue = "none",
+            reason = "\
             Enable exposing the allocator’s custom error value \
             if an associated type is added in the future: \
-            https://github.com/rust-lang/wg-allocators/issues/23")]
+            https://github.com/rust-lang/wg-allocators/issues/23"
+        )]
         non_exhaustive: (),
     },
 }
 
-#[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
+#[unstable(feature = "try_reserve", reason = "new API", issue = "48043")]
 impl From<LayoutErr> for TryReserveError {
     #[inline]
     fn from(_: LayoutErr) -> Self {
diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs
index 913613653a6..9d2eec94a0c 100644
--- a/src/liballoc/collections/vec_deque.rs
+++ b/src/liballoc/collections/vec_deque.rs
@@ -10,13 +10,13 @@
 use core::array::LengthAtMost32;
 use core::cmp::{self, Ordering};
 use core::fmt;
+use core::hash::{Hash, Hasher};
 use core::iter::{once, repeat_with, FromIterator, FusedIterator};
 use core::mem::{self, replace};
 use core::ops::Bound::{Excluded, Included, Unbounded};
 use core::ops::{Index, IndexMut, RangeBounds, Try};
 use core::ptr::{self, NonNull};
 use core::slice;
-use core::hash::{Hash, Hasher};
 
 use crate::collections::TryReserveError;
 use crate::raw_vec::RawVec;
@@ -89,13 +89,12 @@ impl<'a, 'b, T> PairSlices<'a, 'b, T> {
         !self.b0.is_empty()
     }
 
-    fn remainder(self) -> impl Iterator<Item=&'b [T]> {
+    fn remainder(self) -> impl Iterator<Item = &'b [T]> {
         once(self.b0).chain(once(self.b1))
     }
 }
 
-impl<'a, 'b, T> Iterator for PairSlices<'a, 'b, T>
-{
+impl<'a, 'b, T> Iterator for PairSlices<'a, 'b, T> {
     type Item = (&'a mut [T], &'b [T]);
     fn next(&mut self) -> Option<Self::Item> {
         // Get next part length
@@ -247,41 +246,45 @@ impl<T> VecDeque<T> {
     /// Copies a contiguous block of memory len long from src to dst
     #[inline]
     unsafe fn copy(&self, dst: usize, src: usize, len: usize) {
-        debug_assert!(dst + len <= self.cap(),
-                      "cpy dst={} src={} len={} cap={}",
-                      dst,
-                      src,
-                      len,
-                      self.cap());
-        debug_assert!(src + len <= self.cap(),
-                      "cpy dst={} src={} len={} cap={}",
-                      dst,
-                      src,
-                      len,
-                      self.cap());
-        ptr::copy(self.ptr().add(src),
-                  self.ptr().add(dst),
-                  len);
+        debug_assert!(
+            dst + len <= self.cap(),
+            "cpy dst={} src={} len={} cap={}",
+            dst,
+            src,
+            len,
+            self.cap()
+        );
+        debug_assert!(
+            src + len <= self.cap(),
+            "cpy dst={} src={} len={} cap={}",
+            dst,
+            src,
+            len,
+            self.cap()
+        );
+        ptr::copy(self.ptr().add(src), self.ptr().add(dst), len);
     }
 
     /// Copies a contiguous block of memory len long from src to dst
     #[inline]
     unsafe fn copy_nonoverlapping(&self, dst: usize, src: usize, len: usize) {
-        debug_assert!(dst + len <= self.cap(),
-                      "cno dst={} src={} len={} cap={}",
-                      dst,
-                      src,
-                      len,
-                      self.cap());
-        debug_assert!(src + len <= self.cap(),
-                      "cno dst={} src={} len={} cap={}",
-                      dst,
-                      src,
-                      len,
-                      self.cap());
-        ptr::copy_nonoverlapping(self.ptr().add(src),
-                                 self.ptr().add(dst),
-                                 len);
+        debug_assert!(
+            dst + len <= self.cap(),
+            "cno dst={} src={} len={} cap={}",
+            dst,
+            src,
+            len,
+            self.cap()
+        );
+        debug_assert!(
+            src + len <= self.cap(),
+            "cno dst={} src={} len={} cap={}",
+            dst,
+            src,
+            len,
+            self.cap()
+        );
+        ptr::copy_nonoverlapping(self.ptr().add(src), self.ptr().add(dst), len);
     }
 
     /// Copies a potentially wrapping block of memory len long from src to dest.
@@ -292,12 +295,14 @@ impl<T> VecDeque<T> {
         fn diff(a: usize, b: usize) -> usize {
             if a <= b { b - a } else { a - b }
         }
-        debug_assert!(cmp::min(diff(dst, src), self.cap() - diff(dst, src)) + len <= self.cap(),
-                      "wrc dst={} src={} len={} cap={}",
-                      dst,
-                      src,
-                      len,
-                      self.cap());
+        debug_assert!(
+            cmp::min(diff(dst, src), self.cap() - diff(dst, src)) + len <= self.cap(),
+            "wrc dst={} src={} len={} cap={}",
+            dst,
+            src,
+            len,
+            self.cap()
+        );
 
         if src == dst || len == 0 {
             return;
@@ -475,11 +480,7 @@ impl<T> VecDeque<T> {
         let cap = cmp::max(capacity + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
         assert!(cap > capacity, "capacity overflow");
 
-        VecDeque {
-            tail: 0,
-            head: 0,
-            buf: RawVec::with_capacity(cap),
-        }
+        VecDeque { tail: 0, head: 0, buf: RawVec::with_capacity(cap) }
     }
 
     /// Retrieves an element in the `VecDeque` by index.
@@ -565,10 +566,7 @@ impl<T> VecDeque<T> {
         assert!(j < self.len());
         let ri = self.wrap_add(self.tail, i);
         let rj = self.wrap_add(self.tail, j);
-        unsafe {
-            ptr::swap(self.ptr().add(ri),
-                      self.ptr().add(rj))
-        }
+        unsafe { ptr::swap(self.ptr().add(ri), self.ptr().add(rj)) }
     }
 
     /// Returns the number of elements the `VecDeque` can hold without
@@ -635,7 +633,8 @@ impl<T> VecDeque<T> {
     pub fn reserve(&mut self, additional: usize) {
         let old_cap = self.cap();
         let used_cap = self.len() + 1;
-        let new_cap = used_cap.checked_add(additional)
+        let new_cap = used_cap
+            .checked_add(additional)
             .and_then(|needed_cap| needed_cap.checked_next_power_of_two())
             .expect("capacity overflow");
 
@@ -683,8 +682,8 @@ impl<T> VecDeque<T> {
     /// }
     /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
     /// ```
-    #[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
-    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError>  {
+    #[unstable(feature = "try_reserve", reason = "new API", issue = "48043")]
+    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
         self.try_reserve(additional)
     }
 
@@ -721,11 +720,12 @@ impl<T> VecDeque<T> {
     /// }
     /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
     /// ```
-    #[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
+    #[unstable(feature = "try_reserve", reason = "new API", issue = "48043")]
     pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
         let old_cap = self.cap();
         let used_cap = self.len() + 1;
-        let new_cap = used_cap.checked_add(additional)
+        let new_cap = used_cap
+            .checked_add(additional)
             .and_then(|needed_cap| needed_cap.checked_next_power_of_two())
             .ok_or(TryReserveError::CapacityOverflow)?;
 
@@ -781,16 +781,14 @@ impl<T> VecDeque<T> {
     /// buf.shrink_to(0);
     /// assert!(buf.capacity() >= 4);
     /// ```
-    #[unstable(feature = "shrink_to", reason = "new API", issue="56431")]
+    #[unstable(feature = "shrink_to", reason = "new API", issue = "56431")]
     pub fn shrink_to(&mut self, min_capacity: usize) {
         assert!(self.capacity() >= min_capacity, "Tried to shrink to a larger capacity");
 
         // +1 since the ringbuffer always leaves one space empty
         // len + 1 can't overflow for an existing, well-formed ringbuffer.
-        let target_cap = cmp::max(
-            cmp::max(min_capacity, self.len()) + 1,
-            MINIMUM_CAPACITY + 1
-        ).next_power_of_two();
+        let target_cap = cmp::max(cmp::max(min_capacity, self.len()) + 1, MINIMUM_CAPACITY + 1)
+            .next_power_of_two();
 
         if target_cap < self.cap() {
             // There are three cases of interest:
@@ -913,11 +911,7 @@ impl<T> VecDeque<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn iter(&self) -> Iter<'_, T> {
-        Iter {
-            tail: self.tail,
-            head: self.head,
-            ring: unsafe { self.buffer_as_slice() },
-        }
+        Iter { tail: self.tail, head: self.head, ring: unsafe { self.buffer_as_slice() } }
     }
 
     /// Returns a front-to-back iterator that returns mutable references.
@@ -939,11 +933,7 @@ impl<T> VecDeque<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn iter_mut(&mut self) -> IterMut<'_, T> {
-        IterMut {
-            tail: self.tail,
-            head: self.head,
-            ring: unsafe { self.buffer_as_mut_slice() },
-        }
+        IterMut { tail: self.tail, head: self.head, ring: unsafe { self.buffer_as_mut_slice() } }
     }
 
     /// Returns a pair of slices which contain, in order, the contents of the
@@ -1073,7 +1063,8 @@ impl<T> VecDeque<T> {
     #[inline]
     #[stable(feature = "drain", since = "1.6.0")]
     pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
-        where R: RangeBounds<usize>
+    where
+        R: RangeBounds<usize>,
     {
         // Memory safety
         //
@@ -1089,12 +1080,12 @@ impl<T> VecDeque<T> {
         let start = match range.start_bound() {
             Included(&n) => n,
             Excluded(&n) => n + 1,
-            Unbounded    => 0,
+            Unbounded => 0,
         };
         let end = match range.end_bound() {
             Included(&n) => n + 1,
             Excluded(&n) => n,
-            Unbounded    => len,
+            Unbounded => len,
         };
         assert!(start <= end, "drain lower bound was too large");
         assert!(end <= len, "drain upper bound was too large");
@@ -1174,7 +1165,8 @@ impl<T> VecDeque<T> {
     /// ```
     #[stable(feature = "vec_deque_contains", since = "1.12.0")]
     pub fn contains(&self, x: &T) -> bool
-        where T: PartialEq<T>
+    where
+        T: PartialEq<T>,
     {
         let (a, b) = self.as_slices();
         a.contains(x) || b.contains(x)
@@ -1197,11 +1189,7 @@ impl<T> VecDeque<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn front(&self) -> Option<&T> {
-        if !self.is_empty() {
-            Some(&self[0])
-        } else {
-            None
-        }
+        if !self.is_empty() { Some(&self[0]) } else { None }
     }
 
     /// Provides a mutable reference to the front element, or `None` if the
@@ -1225,11 +1213,7 @@ impl<T> VecDeque<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn front_mut(&mut self) -> Option<&mut T> {
-        if !self.is_empty() {
-            Some(&mut self[0])
-        } else {
-            None
-        }
+        if !self.is_empty() { Some(&mut self[0]) } else { None }
     }
 
     /// Provides a reference to the back element, or `None` if the `VecDeque` is
@@ -1249,11 +1233,7 @@ impl<T> VecDeque<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn back(&self) -> Option<&T> {
-        if !self.is_empty() {
-            Some(&self[self.len() - 1])
-        } else {
-            None
-        }
+        if !self.is_empty() { Some(&self[self.len() - 1]) } else { None }
     }
 
     /// Provides a mutable reference to the back element, or `None` if the
@@ -1278,11 +1258,7 @@ impl<T> VecDeque<T> {
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn back_mut(&mut self) -> Option<&mut T> {
         let len = self.len();
-        if !self.is_empty() {
-            Some(&mut self[len - 1])
-        } else {
-            None
-        }
+        if !self.is_empty() { Some(&mut self[len - 1]) } else { None }
     }
 
     /// Removes the first element and returns it, or `None` if the `VecDeque` is
@@ -1897,22 +1873,24 @@ impl<T> VecDeque<T> {
                 // `at` lies in the first half.
                 let amount_in_first = first_len - at;
 
-                ptr::copy_nonoverlapping(first_half.as_ptr().add(at),
-                                         other.ptr(),
-                                         amount_in_first);
+                ptr::copy_nonoverlapping(first_half.as_ptr().add(at), other.ptr(), amount_in_first);
 
                 // just take all of the second half.
-                ptr::copy_nonoverlapping(second_half.as_ptr(),
-                                         other.ptr().add(amount_in_first),
-                                         second_len);
+                ptr::copy_nonoverlapping(
+                    second_half.as_ptr(),
+                    other.ptr().add(amount_in_first),
+                    second_len,
+                );
             } else {
                 // `at` lies in the second half, need to factor in the elements we skipped
                 // in the first half.
                 let offset = at - first_len;
                 let amount_in_second = second_len - offset;
-                ptr::copy_nonoverlapping(second_half.as_ptr().add(offset),
-                                         other.ptr(),
-                                         amount_in_second);
+                ptr::copy_nonoverlapping(
+                    second_half.as_ptr().add(offset),
+                    other.ptr(),
+                    amount_in_second,
+                );
             }
         }
 
@@ -1979,7 +1957,8 @@ impl<T> VecDeque<T> {
     /// ```
     #[stable(feature = "vec_deque_retain", since = "1.4.0")]
     pub fn retain<F>(&mut self, mut f: F)
-        where F: FnMut(&T) -> bool
+    where
+        F: FnMut(&T) -> bool,
     {
         let len = self.len();
         let mut del = 0;
@@ -2034,7 +2013,7 @@ impl<T> VecDeque<T> {
     /// assert_eq!(buf, [5, 10, 101, 102, 103]);
     /// ```
     #[stable(feature = "vec_resize_with", since = "1.33.0")]
-    pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut()->T) {
+    pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T) {
         let len = self.len();
 
         if new_len > len {
@@ -2250,10 +2229,7 @@ pub struct Iter<'a, T: 'a> {
 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        f.debug_tuple("Iter")
-            .field(&front)
-            .field(&back)
-            .finish()
+        f.debug_tuple("Iter").field(&front).field(&back).finish()
     }
 }
 
@@ -2261,11 +2237,7 @@ impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> Clone for Iter<'_, T> {
     fn clone(&self) -> Self {
-        Iter {
-            ring: self.ring,
-            tail: self.tail,
-            head: self.head,
-        }
+        Iter { ring: self.ring, tail: self.tail, head: self.head }
     }
 }
 
@@ -2290,7 +2262,8 @@ impl<'a, T> Iterator for Iter<'a, T> {
     }
 
     fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
-        where F: FnMut(Acc, Self::Item) -> Acc
+    where
+        F: FnMut(Acc, Self::Item) -> Acc,
     {
         let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
         accum = front.iter().fold(accum, &mut f);
@@ -2350,7 +2323,8 @@ impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
     }
 
     fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
-        where F: FnMut(Acc, Self::Item) -> Acc
+    where
+        F: FnMut(Acc, Self::Item) -> Acc,
     {
         let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
         accum = back.iter().rfold(accum, &mut f);
@@ -2392,7 +2366,6 @@ impl<T> ExactSizeIterator for Iter<'_, T> {
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for Iter<'_, T> {}
 
-
 /// A mutable iterator over the elements of a `VecDeque`.
 ///
 /// This `struct` is created by the [`iter_mut`] method on [`VecDeque`]. See its
@@ -2411,10 +2384,7 @@ pub struct IterMut<'a, T: 'a> {
 impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         let (front, back) = RingSlices::ring_slices(&*self.ring, self.head, self.tail);
-        f.debug_tuple("IterMut")
-            .field(&front)
-            .field(&back)
-            .finish()
+        f.debug_tuple("IterMut").field(&front).field(&back).finish()
     }
 }
 
@@ -2443,7 +2413,8 @@ impl<'a, T> Iterator for IterMut<'a, T> {
     }
 
     fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
-        where F: FnMut(Acc, Self::Item) -> Acc
+    where
+        F: FnMut(Acc, Self::Item) -> Acc,
     {
         let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
         accum = front.iter_mut().fold(accum, &mut f);
@@ -2482,7 +2453,8 @@ impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
     }
 
     fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
-        where F: FnMut(Acc, Self::Item) -> Acc
+    where
+        F: FnMut(Acc, Self::Item) -> Acc,
     {
         let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
         accum = back.iter_mut().rfold(accum, &mut f);
@@ -2516,9 +2488,7 @@ pub struct IntoIter<T> {
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("IntoIter")
-         .field(&self.inner)
-         .finish()
+        f.debug_tuple("IntoIter").field(&self.inner).finish()
     }
 }
 
@@ -2575,10 +2545,10 @@ pub struct Drain<'a, T: 'a> {
 impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         f.debug_tuple("Drain")
-         .field(&self.after_tail)
-         .field(&self.after_head)
-         .field(&self.iter)
-         .finish()
+            .field(&self.after_tail)
+            .field(&self.after_head)
+            .field(&self.iter)
+            .finish()
     }
 }
 
@@ -2835,7 +2805,9 @@ impl<A> Extend<A> for VecDeque<A> {
 
             let head = self.head;
             self.head = self.wrap_add(self.head, 1);
-            unsafe { self.buffer_write(head, element); }
+            unsafe {
+                self.buffer_write(head, element);
+            }
         }
     }
 }
@@ -2873,17 +2845,15 @@ impl<T> From<Vec<T>> for VecDeque<T> {
 
             // We need to extend the buf if it's not a power of two, too small
             // or doesn't have at least one free space
-            if !buf.capacity().is_power_of_two() || (buf.capacity() < (MINIMUM_CAPACITY + 1)) ||
-               (buf.capacity() == len) {
+            if !buf.capacity().is_power_of_two()
+                || (buf.capacity() < (MINIMUM_CAPACITY + 1))
+                || (buf.capacity() == len)
+            {
                 let cap = cmp::max(buf.capacity() + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
                 buf.reserve_exact(len, cap - len);
             }
 
-            VecDeque {
-                tail: 0,
-                head: len,
-                buf,
-            }
+            VecDeque { tail: 0, head: len, buf }
         }
     }
 }
@@ -2936,9 +2906,7 @@ impl<T> From<VecDeque<T>> for Vec<T> {
                     // do this in at most three copy moves.
                     if (cap - tail) > head {
                         // right hand block is the long one; move that enough for the left
-                        ptr::copy(buf.add(tail),
-                                  buf.add(tail - head),
-                                  cap - tail);
+                        ptr::copy(buf.add(tail), buf.add(tail - head), cap - tail);
                         // copy left in the end
                         ptr::copy(buf, buf.add(cap - head), head);
                         // shift the new thing to the start
@@ -2976,10 +2944,8 @@ impl<T> From<VecDeque<T>> for Vec<T> {
                         let n_ops = right_edge - left_edge;
                         left_edge += n_ops;
                         right_edge += right_offset + 1;
-
                     }
                 }
-
             }
             let out = Vec::from_raw_parts(buf, len, cap);
             mem::forget(other);