Merge branch 'master' into relnotes-1.42.0

20 files changed, 790 insertions, 213 deletions

diff --git a/src/liballoc/alloc.rs b/src/liballoc/alloc.rs
index 9fb0de63e6f..f41404bf8ca 100644
--- a/src/liballoc/alloc.rs
+++ b/src/liballoc/alloc.rs
@@ -200,21 +200,27 @@ unsafe fn exchange_malloc(size: usize, align: usize) -> *mut u8 {
         align as *mut u8
     } else {
         let layout = Layout::from_size_align_unchecked(size, align);
-        let ptr = alloc(layout);
-        if !ptr.is_null() { ptr } else { handle_alloc_error(layout) }
+        match Global.alloc(layout) {
+            Ok(ptr) => ptr.as_ptr(),
+            Err(_) => handle_alloc_error(layout),
+        }
     }
 }
 
 #[cfg_attr(not(test), lang = "box_free")]
 #[inline]
+// This signature has to be the same as `Box`, otherwise an ICE will happen.
+// When an additional parameter to `Box` is added (like `A: AllocRef`), this has to be added here as
+// well.
+// For example if `Box` is changed to  `struct Box<T: ?Sized, A: AllocRef>(Unique<T>, A)`,
+// this function has to be changed to `fn box_free<T: ?Sized, A: AllocRef>(Unique<T>, A)` as well.
 pub(crate) unsafe fn box_free<T: ?Sized>(ptr: Unique<T>) {
-    let ptr = ptr.as_ptr();
-    let size = size_of_val(&*ptr);
-    let align = min_align_of_val(&*ptr);
+    let size = size_of_val(ptr.as_ref());
+    let align = min_align_of_val(ptr.as_ref());
     // We do not allocate for Box<T> when T is ZST, so deallocation is also not necessary.
     if size != 0 {
         let layout = Layout::from_size_align_unchecked(size, align);
-        dealloc(ptr as *mut u8, layout);
+        Global.dealloc(ptr.cast().into(), layout);
     }
 }
 
diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs
index d65aee09232..3ac4bd82a3a 100644
--- a/src/liballoc/boxed.rs
+++ b/src/liballoc/boxed.rs
@@ -196,12 +196,14 @@ impl<T> Box<T> {
     #[unstable(feature = "new_uninit", issue = "63291")]
     pub fn new_uninit() -> Box<mem::MaybeUninit<T>> {
         let layout = alloc::Layout::new::<mem::MaybeUninit<T>>();
-        if layout.size() == 0 {
-            return Box(NonNull::dangling().into());
+        unsafe {
+            let ptr = if layout.size() == 0 {
+                NonNull::dangling()
+            } else {
+                Global.alloc(layout).unwrap_or_else(|_| alloc::handle_alloc_error(layout)).cast()
+            };
+            Box::from_raw(ptr.as_ptr())
         }
-        let ptr =
-            unsafe { Global.alloc(layout).unwrap_or_else(|_| alloc::handle_alloc_error(layout)) };
-        Box(ptr.cast().into())
     }
 
     /// Constructs a new `Box` with uninitialized contents, with the memory
@@ -264,15 +266,14 @@ impl<T> Box<[T]> {
     #[unstable(feature = "new_uninit", issue = "63291")]
     pub fn new_uninit_slice(len: usize) -> Box<[mem::MaybeUninit<T>]> {
         let layout = alloc::Layout::array::<mem::MaybeUninit<T>>(len).unwrap();
-        let ptr = if layout.size() == 0 {
-            NonNull::dangling()
-        } else {
-            unsafe {
+        unsafe {
+            let ptr = if layout.size() == 0 {
+                NonNull::dangling()
+            } else {
                 Global.alloc(layout).unwrap_or_else(|_| alloc::handle_alloc_error(layout)).cast()
-            }
-        };
-        let slice = unsafe { slice::from_raw_parts_mut(ptr.as_ptr(), len) };
-        Box(Unique::from(slice))
+            };
+            Box::from_raw(slice::from_raw_parts_mut(ptr.as_ptr(), len))
+        }
     }
 }
 
@@ -308,7 +309,7 @@ impl<T> Box<mem::MaybeUninit<T>> {
     #[unstable(feature = "new_uninit", issue = "63291")]
     #[inline]
     pub unsafe fn assume_init(self) -> Box<T> {
-        Box(Box::into_unique(self).cast())
+        Box::from_raw(Box::into_raw(self) as *mut T)
     }
 }
 
@@ -346,7 +347,7 @@ impl<T> Box<[mem::MaybeUninit<T>]> {
     #[unstable(feature = "new_uninit", issue = "63291")]
     #[inline]
     pub unsafe fn assume_init(self) -> Box<[T]> {
-        Box(Unique::new_unchecked(Box::into_raw(self) as _))
+        Box::from_raw(Box::into_raw(self) as *mut [T])
     }
 }
 
diff --git a/src/liballoc/collections/binary_heap.rs b/src/liballoc/collections/binary_heap.rs
index c527b378f74..f38fe997b73 100644
--- a/src/liballoc/collections/binary_heap.rs
+++ b/src/liballoc/collections/binary_heap.rs
@@ -147,7 +147,7 @@
 
 use core::fmt;
 use core::iter::{FromIterator, FusedIterator, TrustedLen};
-use core::mem::{size_of, swap, ManuallyDrop};
+use core::mem::{self, size_of, swap, ManuallyDrop};
 use core::ops::{Deref, DerefMut};
 use core::ptr;
 
@@ -1239,7 +1239,19 @@ pub struct DrainSorted<'a, T: Ord> {
 impl<'a, T: Ord> Drop for DrainSorted<'a, T> {
     /// Removes heap elements in heap order.
     fn drop(&mut self) {
-        while let Some(_) = self.inner.pop() {}
+        struct DropGuard<'r, 'a, T: Ord>(&'r mut DrainSorted<'a, T>);
+
+        impl<'r, 'a, T: Ord> Drop for DropGuard<'r, 'a, T> {
+            fn drop(&mut self) {
+                while let Some(_) = self.0.inner.pop() {}
+            }
+        }
+
+        while let Some(item) = self.inner.pop() {
+            let guard = DropGuard(self);
+            drop(item);
+            mem::forget(guard);
+        }
     }
 }
 
diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs
index 0b3f603686d..b1f0ef0085f 100644
--- a/src/liballoc/collections/btree/map.rs
+++ b/src/liballoc/collections/btree/map.rs
@@ -227,7 +227,7 @@ impl<K: Clone, V: Clone> BTreeClone for BTreeMap<K, V> {
 impl<K: Clone + Ord, V: Clone> BTreeClone for BTreeMap<K, V> {
     fn clone_from(&mut self, other: &Self) {
         // This truncates `self` to `other.len()` by calling `split_off` on
-        // the first key after `other.len()` elements if it exists
+        // the first key after `other.len()` elements if it exists.
         let split_off_key = if self.len() > other.len() {
             let diff = self.len() - other.len();
             if diff <= other.len() {
@@ -247,11 +247,10 @@ impl<K: Clone + Ord, V: Clone> BTreeClone for BTreeMap<K, V> {
         // After truncation, `self` is at most as long as `other` so this loop
         // replaces every key-value pair in `self`. Since `oiter` is in sorted
         // order and the structure of the `BTreeMap` stays the same,
-        // the BTree invariants are maintained at the end of the loop
+        // the BTree invariants are maintained at the end of the loop.
         while !siter.is_empty() {
             if let Some((ok, ov)) = oiter.next() {
-                // SAFETY: This is safe because the `siter.front != siter.back` check
-                // ensures that `siter` is nonempty
+                // SAFETY: This is safe because `siter` is nonempty.
                 let (sk, sv) = unsafe { siter.next_unchecked() };
                 sk.clone_from(ok);
                 sv.clone_from(ov);
@@ -259,7 +258,7 @@ impl<K: Clone + Ord, V: Clone> BTreeClone for BTreeMap<K, V> {
                 break;
             }
         }
-        // If `other` is longer than `self`, the remaining elements are inserted
+        // If `other` is longer than `self`, the remaining elements are inserted.
         self.extend(oiter.map(|(k, v)| ((*k).clone(), (*v).clone())));
     }
 }
@@ -675,13 +674,15 @@ impl<K: Ord, V> BTreeMap<K, V> {
         T: Ord,
         K: Borrow<T>,
     {
-        match self.length {
-            0 => None,
-            _ => Some(OccupiedEntry {
-                handle: self.root.as_mut().first_kv(),
+        let front = self.root.as_mut().first_leaf_edge();
+        if let Ok(kv) = front.right_kv() {
+            Some(OccupiedEntry {
+                handle: kv.forget_node_type(),
                 length: &mut self.length,
                 _marker: PhantomData,
-            }),
+            })
+        } else {
+            None
         }
     }
 
@@ -736,13 +737,15 @@ impl<K: Ord, V> BTreeMap<K, V> {
         T: Ord,
         K: Borrow<T>,
     {
-        match self.length {
-            0 => None,
-            _ => Some(OccupiedEntry {
-                handle: self.root.as_mut().last_kv(),
+        let back = self.root.as_mut().last_leaf_edge();
+        if let Ok(kv) = back.left_kv() {
+            Some(OccupiedEntry {
+                handle: kv.forget_node_type(),
                 length: &mut self.length,
                 _marker: PhantomData,
-            }),
+            })
+        } else {
+            None
         }
     }
 
@@ -1467,7 +1470,22 @@ impl<K, V> IntoIterator for BTreeMap<K, V> {
 #[stable(feature = "btree_drop", since = "1.7.0")]
 impl<K, V> Drop for IntoIter<K, V> {
     fn drop(&mut self) {
-        self.for_each(drop);
+        struct DropGuard<'a, K, V>(&'a mut IntoIter<K, V>);
+
+        impl<'a, K, V> Drop for DropGuard<'a, K, V> {
+            fn drop(&mut self) {
+                // Continue the same loop we perform below. This only runs when unwinding, so we
+                // don't have to care about panics this time (they'll abort).
+                while let Some(_) = self.0.next() {}
+            }
+        }
+
+        while let Some(pair) = self.next() {
+            let guard = DropGuard(self);
+            drop(pair);
+            mem::forget(guard);
+        }
+
         unsafe {
             let leaf_node = ptr::read(&self.front).into_node();
             if leaf_node.is_shared_root() {
diff --git a/src/liballoc/collections/linked_list.rs b/src/liballoc/collections/linked_list.rs
index b88ca8a0fb0..a9b4e3e4706 100644
--- a/src/liballoc/collections/linked_list.rs
+++ b/src/liballoc/collections/linked_list.rs
@@ -878,6 +878,52 @@ impl<T> LinkedList<T> {
         unsafe { self.split_off_after_node(split_node, at) }
     }
 
+    /// Removes the element at the given index and returns it.
+    ///
+    /// This operation should compute in O(n) time.
+    ///
+    /// # Panics
+    /// Panics if at >= len
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(linked_list_remove)]
+    /// use std::collections::LinkedList;
+    ///
+    /// let mut d = LinkedList::new();
+    ///
+    /// d.push_front(1);
+    /// d.push_front(2);
+    /// d.push_front(3);
+    ///
+    /// assert_eq!(d.remove(1), 2);
+    /// assert_eq!(d.remove(0), 3);
+    /// assert_eq!(d.remove(0), 1);
+    /// ```
+    #[unstable(feature = "linked_list_remove", issue = "69210")]
+    pub fn remove(&mut self, at: usize) -> T {
+        let len = self.len();
+        assert!(at < len, "Cannot remove at an index outside of the list bounds");
+
+        // Below, we iterate towards the node at the given index, either from
+        // the start or the end, depending on which would be faster.
+        let offset_from_end = len - at - 1;
+        if at <= offset_from_end {
+            let mut cursor = self.cursor_front_mut();
+            for _ in 0..at {
+                cursor.move_next();
+            }
+            cursor.remove_current().unwrap()
+        } else {
+            let mut cursor = self.cursor_back_mut();
+            for _ in 0..offset_from_end {
+                cursor.move_prev();
+            }
+            cursor.remove_current().unwrap()
+        }
+    }
+
     /// Creates an iterator which uses a closure to determine if an element should be removed.
     ///
     /// If the closure returns true, then the element is removed and yielded.
@@ -1565,7 +1611,24 @@ where
     F: FnMut(&mut T) -> bool,
 {
     fn drop(&mut self) {
-        self.for_each(drop);
+        struct DropGuard<'r, 'a, T, F>(&'r mut DrainFilter<'a, T, F>)
+        where
+            F: FnMut(&mut T) -> bool;
+
+        impl<'r, 'a, T, F> Drop for DropGuard<'r, 'a, T, F>
+        where
+            F: FnMut(&mut T) -> bool,
+        {
+            fn drop(&mut self) {
+                self.0.for_each(drop);
+            }
+        }
+
+        while let Some(item) = self.next() {
+            let guard = DropGuard(self);
+            drop(item);
+            mem::forget(guard);
+        }
     }
 }
 
diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs
index 2cc450bb68a..85d1d98b8a9 100644
--- a/src/liballoc/collections/vec_deque.rs
+++ b/src/liballoc/collections/vec_deque.rs
@@ -22,6 +22,11 @@ use crate::collections::TryReserveError;
 use crate::raw_vec::RawVec;
 use crate::vec::Vec;
 
+#[stable(feature = "drain", since = "1.6.0")]
+pub use self::drain::Drain;
+
+mod drain;
+
 #[cfg(test)]
 mod tests;
 
@@ -866,6 +871,18 @@ impl<T> VecDeque<T> {
     /// ```
     #[stable(feature = "deque_extras", since = "1.16.0")]
     pub fn truncate(&mut self, len: usize) {
+        /// Runs the destructor for all items in the slice when it gets dropped (normally or
+        /// during unwinding).
+        struct Dropper<'a, T>(&'a mut [T]);
+
+        impl<'a, T> Drop for Dropper<'a, T> {
+            fn drop(&mut self) {
+                unsafe {
+                    ptr::drop_in_place(self.0);
+                }
+            }
+        }
+
         // Safe because:
         //
         // * Any slice passed to `drop_in_place` is valid; the second case has
@@ -888,8 +905,11 @@ impl<T> VecDeque<T> {
                 let drop_back = back as *mut _;
                 let drop_front = front.get_unchecked_mut(len..) as *mut _;
                 self.head = self.wrap_sub(self.head, num_dropped);
+
+                // Make sure the second half is dropped even when a destructor
+                // in the first one panics.
+                let _back_dropper = Dropper(&mut *drop_back);
                 ptr::drop_in_place(drop_front);
-                ptr::drop_in_place(drop_back);
             }
         }
     }
@@ -2526,113 +2546,6 @@ impl<T> ExactSizeIterator for IntoIter<T> {
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for IntoIter<T> {}
 
-/// A draining iterator over the elements of a `VecDeque`.
-///
-/// This `struct` is created by the [`drain`] method on [`VecDeque`]. See its
-/// documentation for more.
-///
-/// [`drain`]: struct.VecDeque.html#method.drain
-/// [`VecDeque`]: struct.VecDeque.html
-#[stable(feature = "drain", since = "1.6.0")]
-pub struct Drain<'a, T: 'a> {
-    after_tail: usize,
-    after_head: usize,
-    iter: Iter<'a, T>,
-    deque: NonNull<VecDeque<T>>,
-}
-
-#[stable(feature = "collection_debug", since = "1.17.0")]
-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()
-    }
-}
-
-#[stable(feature = "drain", since = "1.6.0")]
-unsafe impl<T: Sync> Sync for Drain<'_, T> {}
-#[stable(feature = "drain", since = "1.6.0")]
-unsafe impl<T: Send> Send for Drain<'_, T> {}
-
-#[stable(feature = "drain", since = "1.6.0")]
-impl<T> Drop for Drain<'_, T> {
-    fn drop(&mut self) {
-        self.for_each(drop);
-
-        let source_deque = unsafe { self.deque.as_mut() };
-
-        // T = source_deque_tail; H = source_deque_head; t = drain_tail; h = drain_head
-        //
-        //        T   t   h   H
-        // [. . . o o x x o o . . .]
-        //
-        let orig_tail = source_deque.tail;
-        let drain_tail = source_deque.head;
-        let drain_head = self.after_tail;
-        let orig_head = self.after_head;
-
-        let tail_len = count(orig_tail, drain_tail, source_deque.cap());
-        let head_len = count(drain_head, orig_head, source_deque.cap());
-
-        // Restore the original head value
-        source_deque.head = orig_head;
-
-        match (tail_len, head_len) {
-            (0, 0) => {
-                source_deque.head = 0;
-                source_deque.tail = 0;
-            }
-            (0, _) => {
-                source_deque.tail = drain_head;
-            }
-            (_, 0) => {
-                source_deque.head = drain_tail;
-            }
-            _ => unsafe {
-                if tail_len <= head_len {
-                    source_deque.tail = source_deque.wrap_sub(drain_head, tail_len);
-                    source_deque.wrap_copy(source_deque.tail, orig_tail, tail_len);
-                } else {
-                    source_deque.head = source_deque.wrap_add(drain_tail, head_len);
-                    source_deque.wrap_copy(drain_tail, drain_head, head_len);
-                }
-            },
-        }
-    }
-}
-
-#[stable(feature = "drain", since = "1.6.0")]
-impl<T> Iterator for Drain<'_, T> {
-    type Item = T;
-
-    #[inline]
-    fn next(&mut self) -> Option<T> {
-        self.iter.next().map(|elt| unsafe { ptr::read(elt) })
-    }
-
-    #[inline]
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.iter.size_hint()
-    }
-}
-
-#[stable(feature = "drain", since = "1.6.0")]
-impl<T> DoubleEndedIterator for Drain<'_, T> {
-    #[inline]
-    fn next_back(&mut self) -> Option<T> {
-        self.iter.next_back().map(|elt| unsafe { ptr::read(elt) })
-    }
-}
-
-#[stable(feature = "drain", since = "1.6.0")]
-impl<T> ExactSizeIterator for Drain<'_, T> {}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<T> FusedIterator for Drain<'_, T> {}
-
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A: PartialEq> PartialEq for VecDeque<A> {
     fn eq(&self, other: &VecDeque<A>) -> bool {
diff --git a/src/liballoc/collections/vec_deque/drain.rs b/src/liballoc/collections/vec_deque/drain.rs
new file mode 100644
index 00000000000..1ae94de75ad
--- /dev/null
+++ b/src/liballoc/collections/vec_deque/drain.rs
@@ -0,0 +1,126 @@
+use core::iter::FusedIterator;
+use core::ptr::{self, NonNull};
+use core::{fmt, mem};
+
+use super::{count, Iter, VecDeque};
+
+/// A draining iterator over the elements of a `VecDeque`.
+///
+/// This `struct` is created by the [`drain`] method on [`VecDeque`]. See its
+/// documentation for more.
+///
+/// [`drain`]: struct.VecDeque.html#method.drain
+/// [`VecDeque`]: struct.VecDeque.html
+#[stable(feature = "drain", since = "1.6.0")]
+pub struct Drain<'a, T: 'a> {
+    pub(crate) after_tail: usize,
+    pub(crate) after_head: usize,
+    pub(crate) iter: Iter<'a, T>,
+    pub(crate) deque: NonNull<VecDeque<T>>,
+}
+
+#[stable(feature = "collection_debug", since = "1.17.0")]
+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()
+    }
+}
+
+#[stable(feature = "drain", since = "1.6.0")]
+unsafe impl<T: Sync> Sync for Drain<'_, T> {}
+#[stable(feature = "drain", since = "1.6.0")]
+unsafe impl<T: Send> Send for Drain<'_, T> {}
+
+#[stable(feature = "drain", since = "1.6.0")]
+impl<T> Drop for Drain<'_, T> {
+    fn drop(&mut self) {
+        struct DropGuard<'r, 'a, T>(&'r mut Drain<'a, T>);
+
+        impl<'r, 'a, T> Drop for DropGuard<'r, 'a, T> {
+            fn drop(&mut self) {
+                self.0.for_each(drop);
+
+                let source_deque = unsafe { self.0.deque.as_mut() };
+
+                // T = source_deque_tail; H = source_deque_head; t = drain_tail; h = drain_head
+                //
+                //        T   t   h   H
+                // [. . . o o x x o o . . .]
+                //
+                let orig_tail = source_deque.tail;
+                let drain_tail = source_deque.head;
+                let drain_head = self.0.after_tail;
+                let orig_head = self.0.after_head;
+
+                let tail_len = count(orig_tail, drain_tail, source_deque.cap());
+                let head_len = count(drain_head, orig_head, source_deque.cap());
+
+                // Restore the original head value
+                source_deque.head = orig_head;
+
+                match (tail_len, head_len) {
+                    (0, 0) => {
+                        source_deque.head = 0;
+                        source_deque.tail = 0;
+                    }
+                    (0, _) => {
+                        source_deque.tail = drain_head;
+                    }
+                    (_, 0) => {
+                        source_deque.head = drain_tail;
+                    }
+                    _ => unsafe {
+                        if tail_len <= head_len {
+                            source_deque.tail = source_deque.wrap_sub(drain_head, tail_len);
+                            source_deque.wrap_copy(source_deque.tail, orig_tail, tail_len);
+                        } else {
+                            source_deque.head = source_deque.wrap_add(drain_tail, head_len);
+                            source_deque.wrap_copy(drain_tail, drain_head, head_len);
+                        }
+                    },
+                }
+            }
+        }
+
+        while let Some(item) = self.next() {
+            let guard = DropGuard(self);
+            drop(item);
+            mem::forget(guard);
+        }
+
+        DropGuard(self);
+    }
+}
+
+#[stable(feature = "drain", since = "1.6.0")]
+impl<T> Iterator for Drain<'_, T> {
+    type Item = T;
+
+    #[inline]
+    fn next(&mut self) -> Option<T> {
+        self.iter.next().map(|elt| unsafe { ptr::read(elt) })
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+#[stable(feature = "drain", since = "1.6.0")]
+impl<T> DoubleEndedIterator for Drain<'_, T> {
+    #[inline]
+    fn next_back(&mut self) -> Option<T> {
+        self.iter.next_back().map(|elt| unsafe { ptr::read(elt) })
+    }
+}
+
+#[stable(feature = "drain", since = "1.6.0")]
+impl<T> ExactSizeIterator for Drain<'_, T> {}
+
+#[stable(feature = "fused", since = "1.26.0")]
+impl<T> FusedIterator for Drain<'_, T> {}
diff --git a/src/liballoc/raw_vec.rs b/src/liballoc/raw_vec.rs
index e1b549bed18..144654946a2 100644
--- a/src/liballoc/raw_vec.rs
+++ b/src/liballoc/raw_vec.rs
@@ -280,7 +280,7 @@ impl<T, A: AllocRef> RawVec<T, A> {
             // 0, getting to here necessarily means the `RawVec` is overfull.
             assert!(elem_size != 0, "capacity overflow");
 
-            let (new_cap, uniq) = match self.current_layout() {
+            let (new_cap, ptr) = match self.current_layout() {
                 Some(cur) => {
                     // Since we guarantee that we never allocate more than
                     // `isize::MAX` bytes, `elem_size * self.cap <= isize::MAX` as
@@ -297,7 +297,7 @@ impl<T, A: AllocRef> RawVec<T, A> {
                     alloc_guard(new_size).unwrap_or_else(|_| capacity_overflow());
                     let ptr_res = self.a.realloc(NonNull::from(self.ptr).cast(), cur, new_size);
                     match ptr_res {
-                        Ok(ptr) => (new_cap, ptr.cast().into()),
+                        Ok(ptr) => (new_cap, ptr),
                         Err(_) => handle_alloc_error(Layout::from_size_align_unchecked(
                             new_size,
                             cur.align(),
@@ -308,13 +308,14 @@ impl<T, A: AllocRef> RawVec<T, A> {
                     // Skip to 4 because tiny `Vec`'s are dumb; but not if that
                     // would cause overflow.
                     let new_cap = if elem_size > (!0) / 8 { 1 } else { 4 };
-                    match self.a.alloc_array::<T>(new_cap) {
-                        Ok(ptr) => (new_cap, ptr.into()),
-                        Err(_) => handle_alloc_error(Layout::array::<T>(new_cap).unwrap()),
+                    let layout = Layout::array::<T>(new_cap).unwrap();
+                    match self.a.alloc(layout) {
+                        Ok(ptr) => (new_cap, ptr),
+                        Err(_) => handle_alloc_error(layout),
                     }
                 }
             };
-            self.ptr = uniq;
+            self.ptr = ptr.cast().into();
             self.cap = new_cap;
         }
     }
diff --git a/src/liballoc/string.rs b/src/liballoc/string.rs
index 96f871d8897..f5afea15d65 100644
--- a/src/liballoc/string.rs
+++ b/src/liballoc/string.rs
@@ -319,7 +319,7 @@ pub struct String {
 /// assert_eq!(vec![0, 159], value.unwrap_err().into_bytes());
 /// ```
 #[stable(feature = "rust1", since = "1.0.0")]
-#[derive(Debug)]
+#[derive(Debug, Clone, PartialEq, Eq)]
 pub struct FromUtf8Error {
     bytes: Vec<u8>,
     error: Utf8Error,
@@ -2106,18 +2106,11 @@ impl ops::DerefMut for String {
     }
 }
 
-/// An error when parsing a `String`.
+/// A type alias for [`Infallible`].
 ///
-/// This `enum` is slightly awkward: it will never actually exist. This error is
-/// part of the type signature of the implementation of [`FromStr`] on
-/// [`String`]. The return type of [`from_str`], requires that an error be
-/// defined, but, given that a [`String`] can always be made into a new
-/// [`String`] without error, this type will never actually be returned. As
-/// such, it is only here to satisfy said signature, and is useless otherwise.
+/// This alias exists for backwards compatibility, and may be eventually deprecated.
 ///
-/// [`FromStr`]: ../../std/str/trait.FromStr.html
-/// [`String`]: struct.String.html
-/// [`from_str`]: ../../std/str/trait.FromStr.html#tymethod.from_str
+/// [`Infallible`]: ../../core/convert/enum.Infallible.html
 #[stable(feature = "str_parse_error", since = "1.5.0")]
 pub type ParseError = core::convert::Infallible;
 
@@ -2125,7 +2118,7 @@ pub type ParseError = core::convert::Infallible;
 impl FromStr for String {
     type Err = core::convert::Infallible;
     #[inline]
-    fn from_str(s: &str) -> Result<String, ParseError> {
+    fn from_str(s: &str) -> Result<String, Self::Err> {
         Ok(String::from(s))
     }
 }
@@ -2208,6 +2201,14 @@ impl AsRef<str> for String {
     }
 }
 
+#[stable(feature = "string_as_mut", since = "1.43.0")]
+impl AsMut<str> for String {
+    #[inline]
+    fn as_mut(&mut self) -> &mut str {
+        self
+    }
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl AsRef<[u8]> for String {
     #[inline]
diff --git a/src/liballoc/tests/binary_heap.rs b/src/liballoc/tests/binary_heap.rs
index f49ca713921..be5516f54f3 100644
--- a/src/liballoc/tests/binary_heap.rs
+++ b/src/liballoc/tests/binary_heap.rs
@@ -1,6 +1,8 @@
 use std::collections::binary_heap::{Drain, PeekMut};
 use std::collections::BinaryHeap;
 use std::iter::TrustedLen;
+use std::panic::{catch_unwind, AssertUnwindSafe};
+use std::sync::atomic::{AtomicU32, Ordering};
 
 #[test]
 fn test_iterator() {
@@ -276,6 +278,37 @@ fn test_drain_sorted() {
 }
 
 #[test]
+fn test_drain_sorted_leak() {
+    static DROPS: AtomicU32 = AtomicU32::new(0);
+
+    #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
+    struct D(u32, bool);
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            DROPS.fetch_add(1, Ordering::SeqCst);
+
+            if self.1 {
+                panic!("panic in `drop`");
+            }
+        }
+    }
+
+    let mut q = BinaryHeap::from(vec![
+        D(0, false),
+        D(1, false),
+        D(2, false),
+        D(3, true),
+        D(4, false),
+        D(5, false),
+    ]);
+
+    catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).ok();
+
+    assert_eq!(DROPS.load(Ordering::SeqCst), 6);
+}
+
+#[test]
 fn test_extend_ref() {
     let mut a = BinaryHeap::new();
     a.push(1);
diff --git a/src/liballoc/tests/btree/map.rs b/src/liballoc/tests/btree/map.rs
index 0d009507fc7..fd07a4d3926 100644
--- a/src/liballoc/tests/btree/map.rs
+++ b/src/liballoc/tests/btree/map.rs
@@ -5,7 +5,9 @@ use std::fmt::Debug;
 use std::iter::FromIterator;
 use std::ops::Bound::{self, Excluded, Included, Unbounded};
 use std::ops::RangeBounds;
+use std::panic::catch_unwind;
 use std::rc::Rc;
+use std::sync::atomic::{AtomicU32, Ordering};
 
 use super::DeterministicRng;
 
@@ -15,7 +17,7 @@ fn test_basic_large() {
     #[cfg(not(miri))] // Miri is too slow
     let size = 10000;
     #[cfg(miri)]
-    let size = 200;
+    let size = 144; // to obtain height 3 tree (having edges to both kinds of nodes)
     assert_eq!(map.len(), 0);
 
     for i in 0..size {
@@ -23,6 +25,11 @@ fn test_basic_large() {
         assert_eq!(map.len(), i + 1);
     }
 
+    assert_eq!(map.first_key_value(), Some((&0, &0)));
+    assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1)))));
+    assert_eq!(map.first_entry().unwrap().key(), &0);
+    assert_eq!(map.last_entry().unwrap().key(), &(size - 1));
+
     for i in 0..size {
         assert_eq!(map.get(&i).unwrap(), &(i * 10));
     }
@@ -376,8 +383,8 @@ fn test_range_small() {
 }
 
 #[test]
-fn test_range_depth_2() {
-    // Assuming that node.CAPACITY is 11, having 12 pairs implies a depth 2 tree
+fn test_range_height_2() {
+    // Assuming that node.CAPACITY is 11, having 12 pairs implies a height 2 tree
     // with 2 leaves. Depending on details we don't want or need to rely upon,
     // the single key at the root will be 6 or 7.
 
@@ -519,7 +526,7 @@ fn test_range_1000() {
     #[cfg(not(miri))] // Miri is too slow
     let size = 1000;
     #[cfg(miri)]
-    let size = 200;
+    let size = 144; // to obtain height 3 tree (having edges to both kinds of nodes)
     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 
     fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
@@ -556,14 +563,15 @@ fn test_range_borrowed_key() {
 
 #[test]
 fn test_range() {
-    #[cfg(not(miri))] // Miri is too slow
     let size = 200;
+    #[cfg(not(miri))] // Miri is too slow
+    let step = 1;
     #[cfg(miri)]
-    let size = 30;
+    let step = 66;
     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 
-    for i in 0..size {
-        for j in i..size {
+    for i in (0..size).step_by(step) {
+        for j in (i..size).step_by(step) {
             let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
             let mut pairs = (i..=j).map(|i| (i, i));
 
@@ -578,14 +586,15 @@ fn test_range() {
 
 #[test]
 fn test_range_mut() {
-    #[cfg(not(miri))] // Miri is too slow
     let size = 200;
+    #[cfg(not(miri))] // Miri is too slow
+    let step = 1;
     #[cfg(miri)]
-    let size = 30;
+    let step = 66;
     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 
-    for i in 0..size {
-        for j in i..size {
+    for i in (0..size).step_by(step) {
+        for j in (i..size).step_by(step) {
             let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
             let mut pairs = (i..=j).map(|i| (i, i));
 
@@ -753,10 +762,7 @@ fn test_bad_zst() {
 #[test]
 fn test_clone() {
     let mut map = BTreeMap::new();
-    #[cfg(not(miri))] // Miri is too slow
-    let size = 100;
-    #[cfg(miri)]
-    let size = 30;
+    let size = 12; // to obtain height 2 tree (having edges to leaf nodes)
     assert_eq!(map.len(), 0);
 
     for i in 0..size {
@@ -783,24 +789,36 @@ fn test_clone() {
         assert_eq!(map.len(), size / 2 - i - 1);
         assert_eq!(map, map.clone());
     }
+
+    // Full 2-level and minimal 3-level tree (sizes 143, 144 -- the only ones we clone for).
+    for i in 1..=144 {
+        assert_eq!(map.insert(i, i), None);
+        assert_eq!(map.len(), i);
+        if i >= 143 {
+            assert_eq!(map, map.clone());
+        }
+    }
 }
 
 #[test]
 fn test_clone_from() {
     let mut map1 = BTreeMap::new();
-    let size = 30;
+    let max_size = 12; // to obtain height 2 tree (having edges to leaf nodes)
 
-    for i in 0..size {
+    // Range to max_size inclusive, because i is the size of map1 being tested.
+    for i in 0..=max_size {
         let mut map2 = BTreeMap::new();
         for j in 0..i {
             let mut map1_copy = map2.clone();
-            map1_copy.clone_from(&map1);
+            map1_copy.clone_from(&map1); // small cloned from large
             assert_eq!(map1_copy, map1);
             let mut map2_copy = map1.clone();
-            map2_copy.clone_from(&map2);
+            map2_copy.clone_from(&map2); // large cloned from small
             assert_eq!(map2_copy, map2);
             map2.insert(100 * j + 1, 2 * j + 1);
         }
+        map2.clone_from(&map1); // same length
+        assert_eq!(map2, map1);
         map1.insert(i, 10 * i);
     }
 }
@@ -951,6 +969,7 @@ create_append_test!(test_append_145, 145);
 // Tests for several randomly chosen sizes.
 create_append_test!(test_append_170, 170);
 create_append_test!(test_append_181, 181);
+#[cfg(not(miri))] // Miri is too slow
 create_append_test!(test_append_239, 239);
 #[cfg(not(miri))] // Miri is too slow
 create_append_test!(test_append_1700, 1700);
@@ -1000,3 +1019,29 @@ fn test_split_off_large_random_sorted() {
     assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
     assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
 }
+
+#[test]
+fn test_into_iter_drop_leak() {
+    static DROPS: AtomicU32 = AtomicU32::new(0);
+
+    struct D;
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            if DROPS.fetch_add(1, Ordering::SeqCst) == 3 {
+                panic!("panic in `drop`");
+            }
+        }
+    }
+
+    let mut map = BTreeMap::new();
+    map.insert("a", D);
+    map.insert("b", D);
+    map.insert("c", D);
+    map.insert("d", D);
+    map.insert("e", D);
+
+    catch_unwind(move || drop(map.into_iter())).ok();
+
+    assert_eq!(DROPS.load(Ordering::SeqCst), 5);
+}
diff --git a/src/liballoc/tests/btree/set.rs b/src/liballoc/tests/btree/set.rs
index 265ef758cc5..1a2b62d026b 100644
--- a/src/liballoc/tests/btree/set.rs
+++ b/src/liballoc/tests/btree/set.rs
@@ -487,21 +487,26 @@ fn test_first_last() {
     a.insert(2);
     assert_eq!(a.first(), Some(&1));
     assert_eq!(a.last(), Some(&2));
-    a.insert(3);
+    for i in 3..=12 {
+        a.insert(i);
+    }
     assert_eq!(a.first(), Some(&1));
-    assert_eq!(a.last(), Some(&3));
-
-    assert_eq!(a.len(), 3);
+    assert_eq!(a.last(), Some(&12));
     assert_eq!(a.pop_first(), Some(1));
-    assert_eq!(a.len(), 2);
-    assert_eq!(a.pop_last(), Some(3));
-    assert_eq!(a.len(), 1);
+    assert_eq!(a.pop_last(), Some(12));
     assert_eq!(a.pop_first(), Some(2));
-    assert_eq!(a.len(), 0);
-    assert_eq!(a.pop_last(), None);
-    assert_eq!(a.len(), 0);
+    assert_eq!(a.pop_last(), Some(11));
+    assert_eq!(a.pop_first(), Some(3));
+    assert_eq!(a.pop_last(), Some(10));
+    assert_eq!(a.pop_first(), Some(4));
+    assert_eq!(a.pop_first(), Some(5));
+    assert_eq!(a.pop_first(), Some(6));
+    assert_eq!(a.pop_first(), Some(7));
+    assert_eq!(a.pop_first(), Some(8));
+    assert_eq!(a.clone().pop_last(), Some(9));
+    assert_eq!(a.pop_first(), Some(9));
     assert_eq!(a.pop_first(), None);
-    assert_eq!(a.len(), 0);
+    assert_eq!(a.pop_last(), None);
 }
 
 fn rand_data(len: usize) -> Vec<u32> {
diff --git a/src/liballoc/tests/lib.rs b/src/liballoc/tests/lib.rs
index c1ae67a1a33..ea75f8903c3 100644
--- a/src/liballoc/tests/lib.rs
+++ b/src/liballoc/tests/lib.rs
@@ -12,6 +12,7 @@
 #![feature(binary_heap_into_iter_sorted)]
 #![feature(binary_heap_drain_sorted)]
 #![feature(vec_remove_item)]
+#![feature(split_inclusive)]
 
 use std::collections::hash_map::DefaultHasher;
 use std::hash::{Hash, Hasher};
diff --git a/src/liballoc/tests/linked_list.rs b/src/liballoc/tests/linked_list.rs
index b7736515b26..afcb9e03fd0 100644
--- a/src/liballoc/tests/linked_list.rs
+++ b/src/liballoc/tests/linked_list.rs
@@ -1,5 +1,5 @@
 use std::collections::LinkedList;
-use std::panic::catch_unwind;
+use std::panic::{catch_unwind, AssertUnwindSafe};
 
 #[test]
 fn test_basic() {
@@ -532,6 +532,74 @@ fn drain_filter_complex() {
 }
 
 #[test]
+fn drain_filter_drop_panic_leak() {
+    static mut DROPS: i32 = 0;
+
+    struct D(bool);
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+
+            if self.0 {
+                panic!("panic in `drop`");
+            }
+        }
+    }
+
+    let mut q = LinkedList::new();
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_front(D(false));
+    q.push_front(D(true));
+    q.push_front(D(false));
+
+    catch_unwind(AssertUnwindSafe(|| drop(q.drain_filter(|_| true)))).ok();
+
+    assert_eq!(unsafe { DROPS }, 8);
+    assert!(q.is_empty());
+}
+
+#[test]
+fn drain_filter_pred_panic_leak() {
+    static mut DROPS: i32 = 0;
+
+    #[derive(Debug)]
+    struct D(u32);
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+        }
+    }
+
+    let mut q = LinkedList::new();
+    q.push_back(D(3));
+    q.push_back(D(4));
+    q.push_back(D(5));
+    q.push_back(D(6));
+    q.push_back(D(7));
+    q.push_front(D(2));
+    q.push_front(D(1));
+    q.push_front(D(0));
+
+    catch_unwind(AssertUnwindSafe(|| {
+        drop(q.drain_filter(|item| if item.0 >= 2 { panic!() } else { true }))
+    }))
+    .ok();
+
+    assert_eq!(unsafe { DROPS }, 2); // 0 and 1
+    assert_eq!(q.len(), 6);
+}
+
+#[test]
 fn test_drop() {
     static mut DROPS: i32 = 0;
     struct Elem;
diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs
index 51ddb5e7a4e..3d6b4bff5e0 100644
--- a/src/liballoc/tests/slice.rs
+++ b/src/liballoc/tests/slice.rs
@@ -852,6 +852,86 @@ fn test_splitator() {
 }
 
 #[test]
+fn test_splitator_inclusive() {
+    let xs = &[1, 2, 3, 4, 5];
+
+    let splits: &[&[_]] = &[&[1, 2], &[3, 4], &[5]];
+    assert_eq!(xs.split_inclusive(|x| *x % 2 == 0).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1], &[2, 3, 4, 5]];
+    assert_eq!(xs.split_inclusive(|x| *x == 1).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.split_inclusive(|x| *x == 5).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.split_inclusive(|x| *x == 10).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1], &[2], &[3], &[4], &[5]];
+    assert_eq!(xs.split_inclusive(|_| true).collect::<Vec<&[i32]>>(), splits);
+
+    let xs: &[i32] = &[];
+    let splits: &[&[i32]] = &[&[]];
+    assert_eq!(xs.split_inclusive(|x| *x == 5).collect::<Vec<&[i32]>>(), splits);
+}
+
+#[test]
+fn test_splitator_inclusive_reverse() {
+    let xs = &[1, 2, 3, 4, 5];
+
+    let splits: &[&[_]] = &[&[5], &[3, 4], &[1, 2]];
+    assert_eq!(xs.split_inclusive(|x| *x % 2 == 0).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[2, 3, 4, 5], &[1]];
+    assert_eq!(xs.split_inclusive(|x| *x == 1).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.split_inclusive(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.split_inclusive(|x| *x == 10).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[5], &[4], &[3], &[2], &[1]];
+    assert_eq!(xs.split_inclusive(|_| true).rev().collect::<Vec<_>>(), splits);
+
+    let xs: &[i32] = &[];
+    let splits: &[&[i32]] = &[&[]];
+    assert_eq!(xs.split_inclusive(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
+}
+
+#[test]
+fn test_splitator_mut_inclusive() {
+    let xs = &mut [1, 2, 3, 4, 5];
+
+    let splits: &[&[_]] = &[&[1, 2], &[3, 4], &[5]];
+    assert_eq!(xs.split_inclusive_mut(|x| *x % 2 == 0).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1], &[2, 3, 4, 5]];
+    assert_eq!(xs.split_inclusive_mut(|x| *x == 1).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.split_inclusive_mut(|x| *x == 5).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.split_inclusive_mut(|x| *x == 10).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1], &[2], &[3], &[4], &[5]];
+    assert_eq!(xs.split_inclusive_mut(|_| true).collect::<Vec<_>>(), splits);
+
+    let xs: &mut [i32] = &mut [];
+    let splits: &[&[i32]] = &[&[]];
+    assert_eq!(xs.split_inclusive_mut(|x| *x == 5).collect::<Vec<_>>(), splits);
+}
+
+#[test]
+fn test_splitator_mut_inclusive_reverse() {
+    let xs = &mut [1, 2, 3, 4, 5];
+
+    let splits: &[&[_]] = &[&[5], &[3, 4], &[1, 2]];
+    assert_eq!(xs.split_inclusive_mut(|x| *x % 2 == 0).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[2, 3, 4, 5], &[1]];
+    assert_eq!(xs.split_inclusive_mut(|x| *x == 1).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.split_inclusive_mut(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.split_inclusive_mut(|x| *x == 10).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[5], &[4], &[3], &[2], &[1]];
+    assert_eq!(xs.split_inclusive_mut(|_| true).rev().collect::<Vec<_>>(), splits);
+
+    let xs: &mut [i32] = &mut [];
+    let splits: &[&[i32]] = &[&[]];
+    assert_eq!(xs.split_inclusive_mut(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
+}
+
+#[test]
 fn test_splitnator() {
     let xs = &[1, 2, 3, 4, 5];
 
diff --git a/src/liballoc/tests/str.rs b/src/liballoc/tests/str.rs
index d3c72615696..b703df6f3cb 100644
--- a/src/liballoc/tests/str.rs
+++ b/src/liballoc/tests/str.rs
@@ -1248,6 +1248,49 @@ fn test_split_char_iterator_no_trailing() {
 }
 
 #[test]
+fn test_split_char_iterator_inclusive() {
+    let data = "\nMäry häd ä little lämb\nLittle lämb\n";
+
+    let split: Vec<&str> = data.split_inclusive('\n').collect();
+    assert_eq!(split, ["\n", "Märy häd ä little lämb\n", "Little lämb\n"]);
+
+    let uppercase_separated = "SheePSharKTurtlECaT";
+    let mut first_char = true;
+    let split: Vec<&str> = uppercase_separated
+        .split_inclusive(|c: char| {
+            let split = !first_char && c.is_uppercase();
+            first_char = split;
+            split
+        })
+        .collect();
+    assert_eq!(split, ["SheeP", "SharK", "TurtlE", "CaT"]);
+}
+
+#[test]
+fn test_split_char_iterator_inclusive_rev() {
+    let data = "\nMäry häd ä little lämb\nLittle lämb\n";
+
+    let split: Vec<&str> = data.split_inclusive('\n').rev().collect();
+    assert_eq!(split, ["Little lämb\n", "Märy häd ä little lämb\n", "\n"]);
+
+    // Note that the predicate is stateful and thus dependent
+    // on the iteration order.
+    // (A different predicate is needed for reverse iterator vs normal iterator.)
+    // Not sure if anything can be done though.
+    let uppercase_separated = "SheePSharKTurtlECaT";
+    let mut term_char = true;
+    let split: Vec<&str> = uppercase_separated
+        .split_inclusive(|c: char| {
+            let split = term_char && c.is_uppercase();
+            term_char = c.is_uppercase();
+            split
+        })
+        .rev()
+        .collect();
+    assert_eq!(split, ["CaT", "TurtlE", "SharK", "SheeP"]);
+}
+
+#[test]
 fn test_rsplit() {
     let data = "\nMäry häd ä little lämb\nLittle lämb\n";
 
diff --git a/src/liballoc/tests/string.rs b/src/liballoc/tests/string.rs
index dd444958459..08859b2b24b 100644
--- a/src/liballoc/tests/string.rs
+++ b/src/liballoc/tests/string.rs
@@ -50,7 +50,11 @@ fn test_from_utf8() {
 
     let xs = b"hello\xFF".to_vec();
     let err = String::from_utf8(xs).unwrap_err();
+    assert_eq!(err.as_bytes(), b"hello\xff");
+    let err_clone = err.clone();
+    assert_eq!(err, err_clone);
     assert_eq!(err.into_bytes(), b"hello\xff".to_vec());
+    assert_eq!(err_clone.utf8_error().valid_up_to(), 5);
 }
 
 #[test]
diff --git a/src/liballoc/tests/vec.rs b/src/liballoc/tests/vec.rs
index 2a9bfefc713..9c4ac52acac 100644
--- a/src/liballoc/tests/vec.rs
+++ b/src/liballoc/tests/vec.rs
@@ -1,6 +1,7 @@
 use std::borrow::Cow;
 use std::collections::TryReserveError::*;
 use std::mem::size_of;
+use std::panic::{catch_unwind, AssertUnwindSafe};
 use std::vec::{Drain, IntoIter};
 use std::{isize, usize};
 
@@ -586,6 +587,44 @@ fn test_drain_inclusive_out_of_bounds() {
 }
 
 #[test]
+fn test_drain_leak() {
+    static mut DROPS: i32 = 0;
+
+    #[derive(Debug, PartialEq)]
+    struct D(u32, bool);
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+
+            if self.1 {
+                panic!("panic in `drop`");
+            }
+        }
+    }
+
+    let mut v = vec![
+        D(0, false),
+        D(1, false),
+        D(2, false),
+        D(3, false),
+        D(4, true),
+        D(5, false),
+        D(6, false),
+    ];
+
+    catch_unwind(AssertUnwindSafe(|| {
+        v.drain(2..=5);
+    }))
+    .ok();
+
+    assert_eq!(unsafe { DROPS }, 4);
+    assert_eq!(v, vec![D(0, false), D(1, false), D(6, false),]);
+}
+
+#[test]
 fn test_splice() {
     let mut v = vec![1, 2, 3, 4, 5];
     let a = [10, 11, 12];
@@ -727,6 +766,31 @@ fn test_into_iter_clone() {
 }
 
 #[test]
+fn test_into_iter_leak() {
+    static mut DROPS: i32 = 0;
+
+    struct D(bool);
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+
+            if self.0 {
+                panic!("panic in `drop`");
+            }
+        }
+    }
+
+    let v = vec![D(false), D(true), D(false)];
+
+    catch_unwind(move || drop(v.into_iter())).ok();
+
+    assert_eq!(unsafe { DROPS }, 3);
+}
+
+#[test]
 fn test_cow_from() {
     let borrowed: &[_] = &["borrowed", "(slice)"];
     let owned = vec!["owned", "(vec)"];
diff --git a/src/liballoc/tests/vec_deque.rs b/src/liballoc/tests/vec_deque.rs
index 1ab3694a3ca..101dd67d97a 100644
--- a/src/liballoc/tests/vec_deque.rs
+++ b/src/liballoc/tests/vec_deque.rs
@@ -2,7 +2,7 @@ use std::collections::TryReserveError::*;
 use std::collections::{vec_deque::Drain, VecDeque};
 use std::fmt::Debug;
 use std::mem::size_of;
-use std::panic::catch_unwind;
+use std::panic::{catch_unwind, AssertUnwindSafe};
 use std::{isize, usize};
 
 use crate::hash;
@@ -1573,3 +1573,75 @@ fn test_try_rfold_moves_iter() {
     assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
     assert_eq!(iter.next_back(), Some(&70));
 }
+
+#[test]
+fn truncate_leak() {
+    static mut DROPS: i32 = 0;
+
+    struct D(bool);
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+
+            if self.0 {
+                panic!("panic in `drop`");
+            }
+        }
+    }
+
+    let mut q = VecDeque::new();
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_front(D(true));
+    q.push_front(D(false));
+    q.push_front(D(false));
+
+    catch_unwind(AssertUnwindSafe(|| q.truncate(1))).ok();
+
+    assert_eq!(unsafe { DROPS }, 7);
+}
+
+#[test]
+fn test_drain_leak() {
+    static mut DROPS: i32 = 0;
+
+    #[derive(Debug, PartialEq)]
+    struct D(u32, bool);
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+
+            if self.1 {
+                panic!("panic in `drop`");
+            }
+        }
+    }
+
+    let mut v = VecDeque::new();
+    v.push_back(D(4, false));
+    v.push_back(D(5, false));
+    v.push_back(D(6, false));
+    v.push_front(D(3, false));
+    v.push_front(D(2, true));
+    v.push_front(D(1, false));
+    v.push_front(D(0, false));
+
+    catch_unwind(AssertUnwindSafe(|| {
+        v.drain(1..=4);
+    }))
+    .ok();
+
+    assert_eq!(unsafe { DROPS }, 4);
+    assert_eq!(v.len(), 3);
+    drop(v);
+    assert_eq!(unsafe { DROPS }, 7);
+}
diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs
index 4f6b7870e2e..29987ac44e6 100644
--- a/src/liballoc/vec.rs
+++ b/src/liballoc/vec.rs
@@ -2622,7 +2622,9 @@ impl<T: Clone> Clone for IntoIter<T> {
 unsafe impl<#[may_dangle] T> Drop for IntoIter<T> {
     fn drop(&mut self) {
         // destroy the remaining elements
-        for _x in self.by_ref() {}
+        unsafe {
+            ptr::drop_in_place(self.as_mut_slice());
+        }
 
         // RawVec handles deallocation
         let _ = unsafe { RawVec::from_raw_parts(self.buf.as_ptr(), self.cap) };
@@ -2702,23 +2704,42 @@ impl<T> DoubleEndedIterator for Drain<'_, T> {
 #[stable(feature = "drain", since = "1.6.0")]
 impl<T> Drop for Drain<'_, T> {
     fn drop(&mut self) {
-        // exhaust self first
-        self.for_each(drop);
+        /// Continues dropping the remaining elements in the `Drain`, then moves back the
+        /// un-`Drain`ed elements to restore the original `Vec`.
+        struct DropGuard<'r, 'a, T>(&'r mut Drain<'a, T>);
 
-        if self.tail_len > 0 {
-            unsafe {
-                let source_vec = self.vec.as_mut();
-                // memmove back untouched tail, update to new length
-                let start = source_vec.len();
-                let tail = self.tail_start;
-                if tail != start {
-                    let src = source_vec.as_ptr().add(tail);
-                    let dst = source_vec.as_mut_ptr().add(start);
-                    ptr::copy(src, dst, self.tail_len);
+        impl<'r, 'a, T> Drop for DropGuard<'r, 'a, T> {
+            fn drop(&mut self) {
+                // Continue the same loop we have below. If the loop already finished, this does
+                // nothing.
+                self.0.for_each(drop);
+
+                if self.0.tail_len > 0 {
+                    unsafe {
+                        let source_vec = self.0.vec.as_mut();
+                        // memmove back untouched tail, update to new length
+                        let start = source_vec.len();
+                        let tail = self.0.tail_start;
+                        if tail != start {
+                            let src = source_vec.as_ptr().add(tail);
+                            let dst = source_vec.as_mut_ptr().add(start);
+                            ptr::copy(src, dst, self.0.tail_len);
+                        }
+                        source_vec.set_len(start + self.0.tail_len);
+                    }
                 }
-                source_vec.set_len(start + self.tail_len);
             }
         }
+
+        // exhaust self first
+        while let Some(item) = self.next() {
+            let guard = DropGuard(self);
+            drop(item);
+            mem::forget(guard);
+        }
+
+        // Drop a `DropGuard` to move back the non-drained tail of `self`.
+        DropGuard(self);
     }
 }