Merge branch 'master' of github.com:rust-lang/rust into add-tvSO-target

25 files changed, 1783 insertions, 594 deletions

diff --git a/src/liballoc/alloc.rs b/src/liballoc/alloc.rs
index 0c0dc928b95..f41404bf8ca 100644
--- a/src/liballoc/alloc.rs
+++ b/src/liballoc/alloc.rs
@@ -31,14 +31,14 @@ extern "Rust" {
 
 /// The global memory allocator.
 ///
-/// This type implements the [`Alloc`] trait by forwarding calls
+/// This type implements the [`AllocRef`] trait by forwarding calls
 /// to the allocator registered with the `#[global_allocator]` attribute
 /// if there is one, or the `std` crate’s default.
 ///
 /// Note: while this type is unstable, the functionality it provides can be
 /// accessed through the [free functions in `alloc`](index.html#functions).
 ///
-/// [`Alloc`]: trait.Alloc.html
+/// [`AllocRef`]: trait.AllocRef.html
 #[unstable(feature = "allocator_api", issue = "32838")]
 #[derive(Copy, Clone, Default, Debug)]
 pub struct Global;
@@ -50,14 +50,14 @@ pub struct Global;
 /// if there is one, or the `std` crate’s default.
 ///
 /// This function is expected to be deprecated in favor of the `alloc` method
-/// of the [`Global`] type when it and the [`Alloc`] trait become stable.
+/// of the [`Global`] type when it and the [`AllocRef`] trait become stable.
 ///
 /// # Safety
 ///
 /// See [`GlobalAlloc::alloc`].
 ///
 /// [`Global`]: struct.Global.html
-/// [`Alloc`]: trait.Alloc.html
+/// [`AllocRef`]: trait.AllocRef.html
 /// [`GlobalAlloc::alloc`]: trait.GlobalAlloc.html#tymethod.alloc
 ///
 /// # Examples
@@ -88,14 +88,14 @@ pub unsafe fn alloc(layout: Layout) -> *mut u8 {
 /// if there is one, or the `std` crate’s default.
 ///
 /// This function is expected to be deprecated in favor of the `dealloc` method
-/// of the [`Global`] type when it and the [`Alloc`] trait become stable.
+/// of the [`Global`] type when it and the [`AllocRef`] trait become stable.
 ///
 /// # Safety
 ///
 /// See [`GlobalAlloc::dealloc`].
 ///
 /// [`Global`]: struct.Global.html
-/// [`Alloc`]: trait.Alloc.html
+/// [`AllocRef`]: trait.AllocRef.html
 /// [`GlobalAlloc::dealloc`]: trait.GlobalAlloc.html#tymethod.dealloc
 #[stable(feature = "global_alloc", since = "1.28.0")]
 #[inline]
@@ -110,14 +110,14 @@ pub unsafe fn dealloc(ptr: *mut u8, layout: Layout) {
 /// if there is one, or the `std` crate’s default.
 ///
 /// This function is expected to be deprecated in favor of the `realloc` method
-/// of the [`Global`] type when it and the [`Alloc`] trait become stable.
+/// of the [`Global`] type when it and the [`AllocRef`] trait become stable.
 ///
 /// # Safety
 ///
 /// See [`GlobalAlloc::realloc`].
 ///
 /// [`Global`]: struct.Global.html
-/// [`Alloc`]: trait.Alloc.html
+/// [`AllocRef`]: trait.AllocRef.html
 /// [`GlobalAlloc::realloc`]: trait.GlobalAlloc.html#method.realloc
 #[stable(feature = "global_alloc", since = "1.28.0")]
 #[inline]
@@ -132,14 +132,14 @@ pub unsafe fn realloc(ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8
 /// if there is one, or the `std` crate’s default.
 ///
 /// This function is expected to be deprecated in favor of the `alloc_zeroed` method
-/// of the [`Global`] type when it and the [`Alloc`] trait become stable.
+/// of the [`Global`] type when it and the [`AllocRef`] trait become stable.
 ///
 /// # Safety
 ///
 /// See [`GlobalAlloc::alloc_zeroed`].
 ///
 /// [`Global`]: struct.Global.html
-/// [`Alloc`]: trait.Alloc.html
+/// [`AllocRef`]: trait.AllocRef.html
 /// [`GlobalAlloc::alloc_zeroed`]: trait.GlobalAlloc.html#method.alloc_zeroed
 ///
 /// # Examples
@@ -163,7 +163,7 @@ pub unsafe fn alloc_zeroed(layout: Layout) -> *mut u8 {
 }
 
 #[unstable(feature = "allocator_api", issue = "32838")]
-unsafe impl Alloc for Global {
+unsafe impl AllocRef for Global {
     #[inline]
     unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
         NonNull::new(alloc(layout)).ok_or(AllocErr)
@@ -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/benches/btree/map.rs b/src/liballoc/benches/btree/map.rs
index eb5f51d9adc..83cdebf0e3f 100644
--- a/src/liballoc/benches/btree/map.rs
+++ b/src/liballoc/benches/btree/map.rs
@@ -1,5 +1,6 @@
 use std::collections::BTreeMap;
 use std::iter::Iterator;
+use std::ops::Bound::{Excluded, Unbounded};
 use std::vec::Vec;
 
 use rand::{seq::SliceRandom, thread_rng, Rng};
@@ -146,6 +147,36 @@ pub fn iter_100000(b: &mut Bencher) {
     bench_iter(b, 100000);
 }
 
+fn bench_iter_mut(b: &mut Bencher, size: i32) {
+    let mut map = BTreeMap::<i32, i32>::new();
+    let mut rng = thread_rng();
+
+    for _ in 0..size {
+        map.insert(rng.gen(), rng.gen());
+    }
+
+    b.iter(|| {
+        for kv in map.iter_mut() {
+            black_box(kv);
+        }
+    });
+}
+
+#[bench]
+pub fn iter_mut_20(b: &mut Bencher) {
+    bench_iter_mut(b, 20);
+}
+
+#[bench]
+pub fn iter_mut_1000(b: &mut Bencher) {
+    bench_iter_mut(b, 1000);
+}
+
+#[bench]
+pub fn iter_mut_100000(b: &mut Bencher) {
+    bench_iter_mut(b, 100000);
+}
+
 fn bench_first_and_last(b: &mut Bencher, size: i32) {
     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
     b.iter(|| {
@@ -170,3 +201,58 @@ pub fn first_and_last_100(b: &mut Bencher) {
 pub fn first_and_last_10k(b: &mut Bencher) {
     bench_first_and_last(b, 10_000);
 }
+
+#[bench]
+pub fn range_excluded_excluded(b: &mut Bencher) {
+    let size = 144;
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+    b.iter(|| {
+        for first in 0..size {
+            for last in first + 1..size {
+                black_box(map.range((Excluded(first), Excluded(last))));
+            }
+        }
+    });
+}
+
+#[bench]
+pub fn range_excluded_unbounded(b: &mut Bencher) {
+    let size = 144;
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+    b.iter(|| {
+        for first in 0..size {
+            black_box(map.range((Excluded(first), Unbounded)));
+        }
+    });
+}
+
+#[bench]
+pub fn range_included_included(b: &mut Bencher) {
+    let size = 144;
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+    b.iter(|| {
+        for first in 0..size {
+            for last in first..size {
+                black_box(map.range(first..=last));
+            }
+        }
+    });
+}
+
+#[bench]
+pub fn range_included_unbounded(b: &mut Bencher) {
+    let size = 144;
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+    b.iter(|| {
+        for first in 0..size {
+            black_box(map.range(first..));
+        }
+    });
+}
+
+#[bench]
+pub fn range_unbounded_unbounded(b: &mut Bencher) {
+    let size = 144;
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+    b.iter(|| map.range(..));
+}
diff --git a/src/liballoc/benches/btree/set.rs b/src/liballoc/benches/btree/set.rs
index 18502ded308..d7c1d95a452 100644
--- a/src/liballoc/benches/btree/set.rs
+++ b/src/liballoc/benches/btree/set.rs
@@ -14,19 +14,13 @@ fn random(n: usize) -> BTreeSet<usize> {
 }
 
 fn neg(n: usize) -> BTreeSet<i32> {
-    let mut set = BTreeSet::new();
-    for i in -(n as i32)..=-1 {
-        set.insert(i);
-    }
+    let set: BTreeSet<i32> = (-(n as i32)..=-1).collect();
     assert_eq!(set.len(), n);
     set
 }
 
 fn pos(n: usize) -> BTreeSet<i32> {
-    let mut set = BTreeSet::new();
-    for i in 1..=(n as i32) {
-        set.insert(i);
-    }
+    let set: BTreeSet<i32> = (1..=(n as i32)).collect();
     assert_eq!(set.len(), n);
     set
 }
@@ -56,6 +50,43 @@ macro_rules! set_bench {
     };
 }
 
+const BUILD_SET_SIZE: usize = 100;
+
+#[bench]
+pub fn build_and_clear(b: &mut Bencher) {
+    b.iter(|| pos(BUILD_SET_SIZE).clear())
+}
+
+#[bench]
+pub fn build_and_drop(b: &mut Bencher) {
+    b.iter(|| pos(BUILD_SET_SIZE))
+}
+
+#[bench]
+pub fn build_and_into_iter(b: &mut Bencher) {
+    b.iter(|| pos(BUILD_SET_SIZE).into_iter().count())
+}
+
+#[bench]
+pub fn build_and_pop_all(b: &mut Bencher) {
+    b.iter(|| {
+        let mut s = pos(BUILD_SET_SIZE);
+        while s.pop_first().is_some() {}
+        s
+    });
+}
+
+#[bench]
+pub fn build_and_remove_all(b: &mut Bencher) {
+    b.iter(|| {
+        let mut s = pos(BUILD_SET_SIZE);
+        while let Some(elt) = s.iter().copied().next() {
+            s.remove(&elt);
+        }
+        s
+    });
+}
+
 set_bench! {intersection_100_neg_vs_100_pos, intersection, count, [neg(100), pos(100)]}
 set_bench! {intersection_100_neg_vs_10k_pos, intersection, count, [neg(100), pos(10_000)]}
 set_bench! {intersection_100_pos_vs_100_neg, intersection, count, [pos(100), neg(100)]}
diff --git a/src/liballoc/benches/string.rs b/src/liballoc/benches/string.rs
index 599c8b16828..5c95160ba2d 100644
--- a/src/liballoc/benches/string.rs
+++ b/src/liballoc/benches/string.rs
@@ -1,5 +1,5 @@
 use std::iter::repeat;
-use test::Bencher;
+use test::{black_box, Bencher};
 
 #[bench]
 fn bench_with_capacity(b: &mut Bencher) {
diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs
index 87a4924f9be..3ac4bd82a3a 100644
--- a/src/liballoc/boxed.rs
+++ b/src/liballoc/boxed.rs
@@ -2,7 +2,8 @@
 //!
 //! [`Box<T>`], casually referred to as a 'box', provides the simplest form of
 //! heap allocation in Rust. Boxes provide ownership for this allocation, and
-//! drop their contents when they go out of scope.
+//! drop their contents when they go out of scope. Boxes also ensure that they
+//! never allocate more than `isize::MAX` bytes.
 //!
 //! # Examples
 //!
@@ -145,7 +146,7 @@ use core::ptr::{self, NonNull, Unique};
 use core::slice;
 use core::task::{Context, Poll};
 
-use crate::alloc::{self, Alloc, Global};
+use crate::alloc::{self, AllocRef, Global};
 use crate::raw_vec::RawVec;
 use crate::str::from_boxed_utf8_unchecked;
 use crate::vec::Vec;
@@ -195,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
@@ -263,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))
+        }
     }
 }
 
@@ -307,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)
     }
 }
 
@@ -345,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])
     }
 }
 
@@ -1103,6 +1105,7 @@ impl<T: ?Sized> AsMut<T> for Box<T> {
 #[stable(feature = "pin", since = "1.33.0")]
 impl<T: ?Sized> Unpin for Box<T> {}
 
+#[cfg(bootstrap)]
 #[unstable(feature = "generator_trait", issue = "43122")]
 impl<G: ?Sized + Generator + Unpin> Generator for Box<G> {
     type Yield = G::Yield;
@@ -1113,6 +1116,7 @@ impl<G: ?Sized + Generator + Unpin> Generator for Box<G> {
     }
 }
 
+#[cfg(bootstrap)]
 #[unstable(feature = "generator_trait", issue = "43122")]
 impl<G: ?Sized + Generator> Generator for Pin<Box<G>> {
     type Yield = G::Yield;
@@ -1123,6 +1127,28 @@ impl<G: ?Sized + Generator> Generator for Pin<Box<G>> {
     }
 }
 
+#[cfg(not(bootstrap))]
+#[unstable(feature = "generator_trait", issue = "43122")]
+impl<G: ?Sized + Generator<R> + Unpin, R> Generator<R> for Box<G> {
+    type Yield = G::Yield;
+    type Return = G::Return;
+
+    fn resume(mut self: Pin<&mut Self>, arg: R) -> GeneratorState<Self::Yield, Self::Return> {
+        G::resume(Pin::new(&mut *self), arg)
+    }
+}
+
+#[cfg(not(bootstrap))]
+#[unstable(feature = "generator_trait", issue = "43122")]
+impl<G: ?Sized + Generator<R>, R> Generator<R> for Pin<Box<G>> {
+    type Yield = G::Yield;
+    type Return = G::Return;
+
+    fn resume(mut self: Pin<&mut Self>, arg: R) -> GeneratorState<Self::Yield, Self::Return> {
+        G::resume((*self).as_mut(), arg)
+    }
+}
+
 #[stable(feature = "futures_api", since = "1.36.0")]
 impl<F: ?Sized + Future + Unpin> Future for Box<F> {
     type Output = F::Output;
diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs
index 302c2bcd5e4..5b4b1c93347 100644
--- a/src/liballoc/collections/btree/map.rs
+++ b/src/liballoc/collections/btree/map.rs
@@ -6,10 +6,11 @@ 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 core::{fmt, mem, ptr};
 
 use super::node::{self, marker, ForceResult::*, Handle, InsertResult::*, NodeRef};
 use super::search::{self, SearchResult::*};
+use super::unwrap_unchecked;
 
 use Entry::*;
 use UnderflowResult::*;
@@ -207,6 +208,60 @@ impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
             clone_subtree(self.root.as_ref())
         }
     }
+
+    fn clone_from(&mut self, other: &Self) {
+        BTreeClone::clone_from(self, other);
+    }
+}
+
+trait BTreeClone {
+    fn clone_from(&mut self, other: &Self);
+}
+
+impl<K: Clone, V: Clone> BTreeClone for BTreeMap<K, V> {
+    default fn clone_from(&mut self, other: &Self) {
+        *self = other.clone();
+    }
+}
+
+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
+        let split_off_key = if self.len() > other.len() {
+            let diff = self.len() - other.len();
+            if diff <= other.len() {
+                self.iter().nth_back(diff - 1).map(|pair| (*pair.0).clone())
+            } else {
+                self.iter().nth(other.len()).map(|pair| (*pair.0).clone())
+            }
+        } else {
+            None
+        };
+        if let Some(key) = split_off_key {
+            self.split_off(&key);
+        }
+
+        let mut siter = self.range_mut(..);
+        let mut oiter = other.iter();
+        // 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
+        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
+                let (sk, sv) = unsafe { siter.next_unchecked() };
+                sk.clone_from(ok);
+                sv.clone_from(ov);
+            } else {
+                break;
+            }
+        }
+        // If `other` is longer than `self`, the remaining elements are inserted
+        self.extend(oiter.map(|(k, v)| ((*k).clone(), (*v).clone())));
+    }
 }
 
 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
@@ -591,7 +646,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
         T: Ord,
         K: Borrow<T>,
     {
-        let front = first_leaf_edge(self.root.as_ref());
+        let front = self.root.as_ref().first_leaf_edge();
         front.right_kv().ok().map(Handle::into_kv)
     }
 
@@ -620,13 +675,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
         }
     }
 
@@ -652,7 +709,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
         T: Ord,
         K: Borrow<T>,
     {
-        let back = last_leaf_edge(self.root.as_ref());
+        let back = self.root.as_ref().last_leaf_edge();
         back.left_kv().ok().map(Handle::into_kv)
     }
 
@@ -681,13 +738,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
         }
     }
 
@@ -810,9 +869,38 @@ impl<K: Ord, V> BTreeMap<K, V> {
         K: Borrow<Q>,
         Q: Ord,
     {
+        self.remove_entry(key).map(|(_, v)| v)
+    }
+
+    /// Removes a key from the map, returning the stored key and value if the key
+    /// was previously in the map.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// #![feature(btreemap_remove_entry)]
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut map = BTreeMap::new();
+    /// map.insert(1, "a");
+    /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
+    /// assert_eq!(map.remove_entry(&1), None);
+    /// ```
+    #[unstable(feature = "btreemap_remove_entry", issue = "66714")]
+    pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
+    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(),
+                OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData }
+                    .remove_entry(),
             ),
             GoDown(_) => None,
         }
@@ -990,7 +1078,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
 
     fn from_sorted_iter<I: Iterator<Item = (K, V)>>(&mut self, iter: I) {
         self.ensure_root_is_owned();
-        let mut cur_node = last_leaf_edge(self.root.as_mut()).into_node();
+        let mut cur_node = self.root.as_mut().last_leaf_edge().into_node();
         // Iterate through all key-value pairs, pushing them into nodes at the right level.
         for (key, value) in iter {
             // Try to push key-value pair into the current leaf node.
@@ -1030,7 +1118,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
                 open_node.push(key, value, right_tree);
 
                 // Go down to the right-most leaf again.
-                cur_node = last_leaf_edge(open_node.forget_type()).into_node();
+                cur_node = open_node.forget_type().last_leaf_edge().into_node();
             }
 
             self.length += 1;
@@ -1328,7 +1416,8 @@ impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
             None
         } else {
             self.length -= 1;
-            unsafe { Some(self.range.next_unchecked()) }
+            let (k, v) = unsafe { self.range.next_unchecked() };
+            Some((k, v)) // coerce k from `&mut K` to `&K`
         }
     }
 
@@ -1348,7 +1437,8 @@ impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
             None
         } else {
             self.length -= 1;
-            unsafe { Some(self.range.next_back_unchecked()) }
+            let (k, v) = unsafe { self.range.next_back_unchecked() };
+            Some((k, v)) // coerce k from `&mut K` to `&K`
         }
     }
 }
@@ -1374,7 +1464,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: root1.first_leaf_edge(), back: root2.last_leaf_edge(), length: len }
     }
 }
 
@@ -1389,9 +1479,9 @@ impl<K, V> Drop for IntoIter<K, V> {
             }
 
             if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
-                let mut cur_node = first_parent.into_node();
-                while let Some(parent) = cur_node.deallocate_and_ascend() {
-                    cur_node = parent.into_node()
+                let mut cur_internal_node = first_parent.into_node();
+                while let Some(parent) = cur_internal_node.deallocate_and_ascend() {
+                    cur_internal_node = parent.into_node()
                 }
             }
         }
@@ -1404,37 +1494,10 @@ impl<K, V> Iterator for IntoIter<K, V> {
 
     fn next(&mut self) -> Option<(K, V)> {
         if self.length == 0 {
-            return None;
+            None
         } else {
             self.length -= 1;
-        }
-
-        let handle = unsafe { ptr::read(&self.front) };
-
-        let mut cur_handle = match handle.right_kv() {
-            Ok(kv) => {
-                let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
-                let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
-                self.front = kv.right_edge();
-                return Some((k, v));
-            }
-            Err(last_edge) => unsafe {
-                unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
-            },
-        };
-
-        loop {
-            match cur_handle.right_kv() {
-                Ok(kv) => {
-                    let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
-                    let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
-                    self.front = first_leaf_edge(kv.right_edge().descend());
-                    return Some((k, v));
-                }
-                Err(last_edge) => unsafe {
-                    cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
-                },
-            }
+            Some(unsafe { self.front.next_unchecked() })
         }
     }
 
@@ -1447,37 +1510,10 @@ impl<K, V> Iterator for IntoIter<K, V> {
 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
     fn next_back(&mut self) -> Option<(K, V)> {
         if self.length == 0 {
-            return None;
+            None
         } else {
             self.length -= 1;
-        }
-
-        let handle = unsafe { ptr::read(&self.back) };
-
-        let mut cur_handle = match handle.left_kv() {
-            Ok(kv) => {
-                let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
-                let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
-                self.back = kv.left_edge();
-                return Some((k, v));
-            }
-            Err(last_edge) => unsafe {
-                unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
-            },
-        };
-
-        loop {
-            match cur_handle.left_kv() {
-                Ok(kv) => {
-                    let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
-                    let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
-                    self.back = last_leaf_edge(kv.left_edge().descend());
-                    return Some((k, v));
-                }
-                Err(last_edge) => unsafe {
-                    cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
-                },
-            }
+            Some(unsafe { self.back.next_back_unchecked() })
         }
     }
 }
@@ -1579,7 +1615,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.is_empty() { None } else { unsafe { Some(self.next_unchecked()) } }
     }
 
     fn last(mut self) -> Option<(&'a K, &'a V)> {
@@ -1622,73 +1658,25 @@ impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
 impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
 
 impl<'a, K, V> Range<'a, K, V> {
-    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
-        let handle = self.front;
-
-        let mut cur_handle = match handle.right_kv() {
-            Ok(kv) => {
-                let ret = kv.into_kv();
-                self.front = kv.right_edge();
-                return ret;
-            }
-            Err(last_edge) => {
-                let next_level = last_edge.into_node().ascend().ok();
-                unwrap_unchecked(next_level)
-            }
-        };
+    fn is_empty(&self) -> bool {
+        self.front == self.back
+    }
 
-        loop {
-            match cur_handle.right_kv() {
-                Ok(kv) => {
-                    let ret = kv.into_kv();
-                    self.front = first_leaf_edge(kv.right_edge().descend());
-                    return ret;
-                }
-                Err(last_edge) => {
-                    let next_level = last_edge.into_node().ascend().ok();
-                    cur_handle = unwrap_unchecked(next_level);
-                }
-            }
-        }
+    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
+        self.front.next_unchecked()
     }
 }
 
 #[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.is_empty() { None } else { Some(unsafe { self.next_back_unchecked() }) }
     }
 }
 
 impl<'a, K, V> Range<'a, K, V> {
     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
-        let handle = self.back;
-
-        let mut cur_handle = match handle.left_kv() {
-            Ok(kv) => {
-                let ret = kv.into_kv();
-                self.back = kv.left_edge();
-                return ret;
-            }
-            Err(last_edge) => {
-                let next_level = last_edge.into_node().ascend().ok();
-                unwrap_unchecked(next_level)
-            }
-        };
-
-        loop {
-            match cur_handle.left_kv() {
-                Ok(kv) => {
-                    let ret = kv.into_kv();
-                    self.back = last_leaf_edge(kv.left_edge().descend());
-                    return ret;
-                }
-                Err(last_edge) => {
-                    let next_level = last_edge.into_node().ascend().ok();
-                    cur_handle = unwrap_unchecked(next_level);
-                }
-            }
-        }
+        self.back.next_back_unchecked()
     }
 }
 
@@ -1707,7 +1695,12 @@ 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.is_empty() {
+            None
+        } else {
+            let (k, v) = unsafe { self.next_unchecked() };
+            Some((k, v)) // coerce k from `&mut K` to `&K`
+        }
     }
 
     fn last(mut self) -> Option<(&'a K, &'a mut V)> {
@@ -1716,45 +1709,24 @@ impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
 }
 
 impl<'a, K, V> RangeMut<'a, K, V> {
-    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
-        let handle = ptr::read(&self.front);
-
-        let mut cur_handle = match handle.right_kv() {
-            Ok(kv) => {
-                self.front = ptr::read(&kv).right_edge();
-                // Doing the descend invalidates the references returned by `into_kv_mut`,
-                // so we have to do this last.
-                let (k, v) = kv.into_kv_mut();
-                return (k, v); // coerce k from `&mut K` to `&K`
-            }
-            Err(last_edge) => {
-                let next_level = last_edge.into_node().ascend().ok();
-                unwrap_unchecked(next_level)
-            }
-        };
+    fn is_empty(&self) -> bool {
+        self.front == self.back
+    }
 
-        loop {
-            match cur_handle.right_kv() {
-                Ok(kv) => {
-                    self.front = first_leaf_edge(ptr::read(&kv).right_edge().descend());
-                    // Doing the descend invalidates the references returned by `into_kv_mut`,
-                    // so we have to do this last.
-                    let (k, v) = kv.into_kv_mut();
-                    return (k, v); // coerce k from `&mut K` to `&K`
-                }
-                Err(last_edge) => {
-                    let next_level = last_edge.into_node().ascend().ok();
-                    cur_handle = unwrap_unchecked(next_level);
-                }
-            }
-        }
+    unsafe fn next_unchecked(&mut self) -> (&'a mut K, &'a mut V) {
+        self.front.next_unchecked()
     }
 }
 
 #[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.is_empty() {
+            None
+        } else {
+            let (k, v) = unsafe { self.next_back_unchecked() };
+            Some((k, v)) // coerce k from `&mut K` to `&K`
+        }
     }
 }
 
@@ -1762,38 +1734,8 @@ impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
 impl<K, V> FusedIterator for RangeMut<'_, K, V> {}
 
 impl<'a, K, V> RangeMut<'a, K, V> {
-    unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
-        let handle = ptr::read(&self.back);
-
-        let mut cur_handle = match handle.left_kv() {
-            Ok(kv) => {
-                self.back = ptr::read(&kv).left_edge();
-                // Doing the descend invalidates the references returned by `into_kv_mut`,
-                // so we have to do this last.
-                let (k, v) = kv.into_kv_mut();
-                return (k, v); // coerce k from `&mut K` to `&K`
-            }
-            Err(last_edge) => {
-                let next_level = last_edge.into_node().ascend().ok();
-                unwrap_unchecked(next_level)
-            }
-        };
-
-        loop {
-            match cur_handle.left_kv() {
-                Ok(kv) => {
-                    self.back = last_leaf_edge(ptr::read(&kv).left_edge().descend());
-                    // Doing the descend invalidates the references returned by `into_kv_mut`,
-                    // so we have to do this last.
-                    let (k, v) = kv.into_kv_mut();
-                    return (k, v); // coerce k from `&mut K` to `&K`
-                }
-                Err(last_edge) => {
-                    let next_level = last_edge.into_node().ascend().ok();
-                    cur_handle = unwrap_unchecked(next_level);
-                }
-            }
-        }
+    unsafe fn next_back_unchecked(&mut self) -> (&'a mut K, &'a mut V) {
+        self.back.next_back_unchecked()
     }
 }
 
@@ -1892,32 +1834,6 @@ where
     }
 }
 
-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(),
-            Internal(internal) => {
-                node = internal.first_edge().descend();
-            }
-        }
-    }
-}
-
-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(),
-            Internal(internal) => {
-                node = internal.last_edge().descend();
-            }
-        }
-    }
-}
-
 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>,
@@ -1949,60 +1865,51 @@ where
     let mut max_node = root2;
     let mut min_found = false;
     let mut max_found = false;
-    let mut diverged = false;
 
     loop {
-        let min_edge = match (min_found, range.start_bound()) {
-            (false, Included(key)) => match search::search_linear(&min_node, key) {
-                (i, true) => {
+        let front = match (min_found, range.start_bound()) {
+            (false, Included(key)) => match search::search_node(min_node, key) {
+                Found(kv) => {
                     min_found = true;
-                    i
+                    kv.left_edge()
                 }
-                (i, false) => i,
+                GoDown(edge) => edge,
             },
-            (false, Excluded(key)) => match search::search_linear(&min_node, key) {
-                (i, true) => {
+            (false, Excluded(key)) => match search::search_node(min_node, key) {
+                Found(kv) => {
                     min_found = true;
-                    i + 1
+                    kv.right_edge()
                 }
-                (i, false) => i,
+                GoDown(edge) => edge,
             },
-            (_, Unbounded) => 0,
-            (true, Included(_)) => min_node.keys().len(),
-            (true, Excluded(_)) => 0,
+            (true, Included(_)) => min_node.last_edge(),
+            (true, Excluded(_)) => min_node.first_edge(),
+            (_, Unbounded) => min_node.first_edge(),
         };
 
-        let max_edge = match (max_found, range.end_bound()) {
-            (false, Included(key)) => match search::search_linear(&max_node, key) {
-                (i, true) => {
+        let back = match (max_found, range.end_bound()) {
+            (false, Included(key)) => match search::search_node(max_node, key) {
+                Found(kv) => {
                     max_found = true;
-                    i + 1
+                    kv.right_edge()
                 }
-                (i, false) => i,
+                GoDown(edge) => edge,
             },
-            (false, Excluded(key)) => match search::search_linear(&max_node, key) {
-                (i, true) => {
+            (false, Excluded(key)) => match search::search_node(max_node, key) {
+                Found(kv) => {
                     max_found = true;
-                    i
+                    kv.left_edge()
                 }
-                (i, false) => i,
+                GoDown(edge) => edge,
             },
-            (_, Unbounded) => max_node.keys().len(),
-            (true, Included(_)) => 0,
-            (true, Excluded(_)) => max_node.keys().len(),
+            (true, Included(_)) => max_node.first_edge(),
+            (true, Excluded(_)) => max_node.last_edge(),
+            (_, Unbounded) => max_node.last_edge(),
         };
 
-        if !diverged {
-            if max_edge < min_edge {
-                panic!("Ord is ill-defined in BTreeMap range")
-            }
-            if min_edge != max_edge {
-                diverged = true;
-            }
+        if front.partial_cmp(&back) == Some(Ordering::Greater) {
+            panic!("Ord is ill-defined in BTreeMap range");
         }
-
-        let front = Handle::new_edge(min_node, min_edge);
-        let back = Handle::new_edge(max_node, max_edge);
         match (front.force(), back.force()) {
             (Leaf(f), Leaf(b)) => {
                 return (f, b);
@@ -2016,17 +1923,6 @@ where
     }
 }
 
-#[inline(always)]
-unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
-    val.unwrap_or_else(|| {
-        if cfg!(debug_assertions) {
-            panic!("'unchecked' unwrap on None in BTreeMap");
-        } else {
-            intrinsics::unreachable();
-        }
-    })
-}
-
 impl<K, V> BTreeMap<K, V> {
     /// Gets an iterator over the entries of the map, sorted by key.
     ///
@@ -2053,8 +1949,8 @@ impl<K, V> BTreeMap<K, V> {
     pub fn iter(&self) -> Iter<'_, K, V> {
         Iter {
             range: Range {
-                front: first_leaf_edge(self.root.as_ref()),
-                back: last_leaf_edge(self.root.as_ref()),
+                front: self.root.as_ref().first_leaf_edge(),
+                back: self.root.as_ref().last_leaf_edge(),
             },
             length: self.length,
         }
@@ -2087,8 +1983,8 @@ impl<K, V> BTreeMap<K, V> {
         let root2 = unsafe { ptr::read(&root1) };
         IterMut {
             range: RangeMut {
-                front: first_leaf_edge(root1),
-                back: last_leaf_edge(root2),
+                front: root1.first_leaf_edge(),
+                back: root2.last_leaf_edge(),
                 _marker: PhantomData,
             },
             length: self.length,
@@ -2591,7 +2487,7 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
                 let key_loc = internal.kv_mut().0 as *mut K;
                 let val_loc = internal.kv_mut().1 as *mut V;
 
-                let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
+                let to_remove = internal.right_edge().descend().first_leaf_edge().right_kv().ok();
                 let to_remove = unsafe { unwrap_unchecked(to_remove) };
 
                 let (hole, key, val) = to_remove.remove();
diff --git a/src/liballoc/collections/btree/mod.rs b/src/liballoc/collections/btree/mod.rs
index f73a24d0991..fb5825ee21a 100644
--- a/src/liballoc/collections/btree/mod.rs
+++ b/src/liballoc/collections/btree/mod.rs
@@ -1,4 +1,5 @@
 pub mod map;
+mod navigate;
 mod node;
 mod search;
 pub mod set;
@@ -11,3 +12,14 @@ trait Recover<Q: ?Sized> {
     fn take(&mut self, key: &Q) -> Option<Self::Key>;
     fn replace(&mut self, key: Self::Key) -> Option<Self::Key>;
 }
+
+#[inline(always)]
+pub unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
+    val.unwrap_or_else(|| {
+        if cfg!(debug_assertions) {
+            panic!("'unchecked' unwrap on None in BTreeMap");
+        } else {
+            core::intrinsics::unreachable();
+        }
+    })
+}
diff --git a/src/liballoc/collections/btree/navigate.rs b/src/liballoc/collections/btree/navigate.rs
new file mode 100644
index 00000000000..65321897231
--- /dev/null
+++ b/src/liballoc/collections/btree/navigate.rs
@@ -0,0 +1,244 @@
+use core::ptr;
+
+use super::node::{marker, ForceResult::*, Handle, NodeRef};
+use super::unwrap_unchecked;
+
+macro_rules! def_next {
+    { unsafe fn $name:ident : $next_kv:ident $next_edge:ident $initial_leaf_edge:ident } => {
+        /// Given a leaf edge handle into an immutable tree, returns a handle to the next
+        /// leaf edge and references to the key and value between these edges.
+        /// Unsafe because the caller must ensure that the given leaf edge has a successor.
+        unsafe fn $name <'a, K: 'a, V: 'a>(
+            leaf_edge: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
+        ) -> (Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>, &'a K, &'a V) {
+            let mut cur_handle = match leaf_edge.$next_kv() {
+                Ok(leaf_kv) => {
+                    let (k, v) = leaf_kv.into_kv();
+                    let next_leaf_edge = leaf_kv.$next_edge();
+                    return (next_leaf_edge, k, v);
+                }
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    unwrap_unchecked(next_level)
+                }
+            };
+
+            loop {
+                cur_handle = match cur_handle.$next_kv() {
+                    Ok(internal_kv) => {
+                        let (k, v) = internal_kv.into_kv();
+                        let next_internal_edge = internal_kv.$next_edge();
+                        let next_leaf_edge = next_internal_edge.descend().$initial_leaf_edge();
+                        return (next_leaf_edge, k, v);
+                    }
+                    Err(last_edge) => {
+                        let next_level = last_edge.into_node().ascend().ok();
+                        unwrap_unchecked(next_level)
+                    }
+                }
+            }
+        }
+    };
+}
+
+macro_rules! def_next_mut {
+    { unsafe fn $name:ident : $next_kv:ident $next_edge:ident $initial_leaf_edge:ident } => {
+        /// Given a leaf edge handle into a mutable tree, returns handles to the next
+        /// leaf edge and to the KV between these edges.
+        /// Unsafe for two reasons:
+        /// - the caller must ensure that the given leaf edge has a successor;
+        /// - both returned handles represent mutable references into the same tree
+        ///   that can easily invalidate each other, even on immutable use.
+        unsafe fn $name <'a, K: 'a, V: 'a>(
+            leaf_edge: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+        ) -> (Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+              Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>) {
+            let mut cur_handle = match leaf_edge.$next_kv() {
+                Ok(leaf_kv) => {
+                    let next_leaf_edge = ptr::read(&leaf_kv).$next_edge();
+                    return (next_leaf_edge, leaf_kv.forget_node_type());
+                }
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    unwrap_unchecked(next_level)
+                }
+            };
+
+            loop {
+                cur_handle = match cur_handle.$next_kv() {
+                    Ok(internal_kv) => {
+                        let next_internal_edge = ptr::read(&internal_kv).$next_edge();
+                        let next_leaf_edge = next_internal_edge.descend().$initial_leaf_edge();
+                        return (next_leaf_edge, internal_kv.forget_node_type());
+                    }
+                    Err(last_edge) => {
+                        let next_level = last_edge.into_node().ascend().ok();
+                        unwrap_unchecked(next_level)
+                    }
+                }
+            }
+        }
+    };
+}
+
+macro_rules! def_next_dealloc {
+    { unsafe fn $name:ident : $next_kv:ident $next_edge:ident $initial_leaf_edge:ident } => {
+        /// Given a leaf edge handle into an owned tree, returns a handle to the next
+        /// leaf edge and the key and value between these edges, while deallocating
+        /// any node left behind.
+        /// Unsafe for two reasons:
+        /// - the caller must ensure that the given leaf edge has a successor;
+        /// - the node pointed at by the given handle, and its ancestors, may be deallocated,
+        ///   while the reference to those nodes in the surviving ancestors is left dangling;
+        ///   thus using the returned handle is dangerous.
+        unsafe fn $name <K, V>(
+            leaf_edge: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
+        ) -> (Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>, K, V) {
+            let mut cur_handle = match leaf_edge.$next_kv() {
+                Ok(leaf_kv) => {
+                    let k = ptr::read(leaf_kv.reborrow().into_kv().0);
+                    let v = ptr::read(leaf_kv.reborrow().into_kv().1);
+                    let next_leaf_edge = leaf_kv.$next_edge();
+                    return (next_leaf_edge, k, v);
+                }
+                Err(last_edge) => {
+                    unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
+                }
+            };
+
+            loop {
+                cur_handle = match cur_handle.$next_kv() {
+                    Ok(internal_kv) => {
+                        let k = ptr::read(internal_kv.reborrow().into_kv().0);
+                        let v = ptr::read(internal_kv.reborrow().into_kv().1);
+                        let next_internal_edge = internal_kv.$next_edge();
+                        let next_leaf_edge = next_internal_edge.descend().$initial_leaf_edge();
+                        return (next_leaf_edge, k, v);
+                    }
+                    Err(last_edge) => {
+                        unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
+                    }
+                }
+            }
+        }
+    };
+}
+
+def_next! {unsafe fn next_unchecked: right_kv right_edge first_leaf_edge}
+def_next! {unsafe fn next_back_unchecked: left_kv left_edge last_leaf_edge}
+def_next_mut! {unsafe fn next_unchecked_mut: right_kv right_edge first_leaf_edge}
+def_next_mut! {unsafe fn next_back_unchecked_mut: left_kv left_edge last_leaf_edge}
+def_next_dealloc! {unsafe fn next_unchecked_deallocating: right_kv right_edge first_leaf_edge}
+def_next_dealloc! {unsafe fn next_back_unchecked_deallocating: left_kv left_edge last_leaf_edge}
+
+impl<'a, K, V> Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge> {
+    /// Moves the leaf edge handle to the next leaf edge and returns references to the
+    /// key and value in between.
+    /// Unsafe because the caller must ensure that the leaf edge is not the last one in the tree.
+    pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
+        let (next_edge, k, v) = next_unchecked(*self);
+        *self = next_edge;
+        (k, v)
+    }
+
+    /// Moves the leaf edge handle to the previous leaf edge and returns references to the
+    /// key and value in between.
+    /// Unsafe because the caller must ensure that the leaf edge is not the first one in the tree.
+    pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
+        let (next_edge, k, v) = next_back_unchecked(*self);
+        *self = next_edge;
+        (k, v)
+    }
+}
+
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
+    /// Moves the leaf edge handle to the next leaf edge and returns references to the
+    /// key and value in between.
+    /// Unsafe for two reasons:
+    /// - The caller must ensure that the leaf edge is not the last one in the tree.
+    /// - Using the updated handle may well invalidate the returned references.
+    pub unsafe fn next_unchecked(&mut self) -> (&'a mut K, &'a mut V) {
+        let (next_edge, kv) = next_unchecked_mut(ptr::read(self));
+        *self = next_edge;
+        // Doing the descend (and perhaps another move) invalidates the references
+        // returned by `into_kv_mut`, so we have to do this last.
+        kv.into_kv_mut()
+    }
+
+    /// Moves the leaf edge handle to the previous leaf and returns references to the
+    /// key and value in between.
+    /// Unsafe for two reasons:
+    /// - The caller must ensure that the leaf edge is not the first one in the tree.
+    /// - Using the updated handle may well invalidate the returned references.
+    pub unsafe fn next_back_unchecked(&mut self) -> (&'a mut K, &'a mut V) {
+        let (next_edge, kv) = next_back_unchecked_mut(ptr::read(self));
+        *self = next_edge;
+        // Doing the descend (and perhaps another move) invalidates the references
+        // returned by `into_kv_mut`, so we have to do this last.
+        kv.into_kv_mut()
+    }
+}
+
+impl<K, V> Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge> {
+    /// Moves the leaf edge handle to the next leaf edge and returns the key and value
+    /// in between, while deallocating any node left behind.
+    /// Unsafe for three reasons:
+    /// - The caller must ensure that the leaf edge is not the last one in the tree
+    ///   and is not a handle previously resulting from counterpart `next_back_unchecked`.
+    /// - If the leaf edge is the last edge of a node, that node and possibly ancestors
+    ///   will be deallocated, while the reference to those nodes in the surviving ancestor
+    ///   is left dangling; thus further use of the leaf edge handle is dangerous.
+    ///   It is, however, safe to call this method again on the updated handle.
+    ///   if the two preconditions above hold.
+    /// - Using the updated handle may well invalidate the returned references.
+    pub unsafe fn next_unchecked(&mut self) -> (K, V) {
+        let (next_edge, k, v) = next_unchecked_deallocating(ptr::read(self));
+        *self = next_edge;
+        (k, v)
+    }
+
+    /// Moves the leaf edge handle to the previous leaf edge and returns the key
+    /// and value in between, while deallocating any node left behind.
+    /// Unsafe for three reasons:
+    /// - The caller must ensure that the leaf edge is not the first one in the tree
+    ///   and is not a handle previously resulting from counterpart `next_unchecked`.
+    /// - If the lead edge is the first edge of a node, that node and possibly ancestors
+    ///   will be deallocated, while the reference to those nodes in the surviving ancestor
+    ///   is left dangling; thus further use of the leaf edge handle is dangerous.
+    ///   It is, however, safe to call this method again on the updated handle.
+    ///   if the two preconditions above hold.
+    /// - Using the updated handle may well invalidate the returned references.
+    pub unsafe fn next_back_unchecked(&mut self) -> (K, V) {
+        let (next_edge, k, v) = next_back_unchecked_deallocating(ptr::read(self));
+        *self = next_edge;
+        (k, v)
+    }
+}
+
+impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+    /// Returns the leftmost leaf edge in or underneath a node - in other words, the edge
+    /// you need first when navigating forward (or last when navigating backward).
+    #[inline]
+    pub fn first_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+        let mut node = self;
+        loop {
+            match node.force() {
+                Leaf(leaf) => return leaf.first_edge(),
+                Internal(internal) => node = internal.first_edge().descend(),
+            }
+        }
+    }
+
+    /// Returns the rightmost leaf edge in or underneath a node - in other words, the edge
+    /// you need last when navigating forward (or first when navigating backward).
+    #[inline]
+    pub fn last_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+        let mut node = self;
+        loop {
+            match node.force() {
+                Leaf(leaf) => return leaf.last_edge(),
+                Internal(internal) => node = internal.last_edge().descend(),
+            }
+        }
+    }
+}
diff --git a/src/liballoc/collections/btree/node.rs b/src/liballoc/collections/btree/node.rs
index 260e51d635d..abf926186e8 100644
--- a/src/liballoc/collections/btree/node.rs
+++ b/src/liballoc/collections/btree/node.rs
@@ -31,12 +31,13 @@
 // - A node of length `n` has `n` keys, `n` values, and (in an internal node) `n + 1` edges.
 //   This implies that even an empty internal node has at least one edge.
 
+use core::cmp::Ordering;
 use core::marker::PhantomData;
 use core::mem::{self, MaybeUninit};
 use core::ptr::{self, NonNull, Unique};
 use core::slice;
 
-use crate::alloc::{Alloc, Global, Layout};
+use crate::alloc::{AllocRef, Global, Layout};
 use crate::boxed::Box;
 
 const B: usize = 6;
@@ -54,10 +55,8 @@ pub const CAPACITY: usize = 2 * B - 1;
 /// `NodeHeader` because we do not want unnecessary padding between `len` and the keys.
 /// Crucially, `NodeHeader` can be safely transmuted to different K and V. (This is exploited
 /// by `as_header`.)
-/// See `into_key_slice` for an explanation of K2. K2 cannot be safely transmuted around
-/// because the size of `NodeHeader` depends on its alignment!
 #[repr(C)]
-struct NodeHeader<K, V, K2 = ()> {
+struct NodeHeader<K, V> {
     /// We use `*const` as opposed to `*mut` so as to be covariant in `K` and `V`.
     /// This either points to an actual node or is null.
     parent: *const InternalNode<K, V>,
@@ -72,9 +71,6 @@ struct NodeHeader<K, V, K2 = ()> {
     /// This next to `parent_idx` to encourage the compiler to join `len` and
     /// `parent_idx` into the same 32-bit word, reducing space overhead.
     len: u16,
-
-    /// See `into_key_slice`.
-    keys_start: [K2; 0],
 }
 #[repr(C)]
 struct LeafNode<K, V> {
@@ -128,7 +124,7 @@ unsafe impl Sync for NodeHeader<(), ()> {}
 // 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: [] };
+    NodeHeader { parent: ptr::null(), parent_idx: MaybeUninit::uninit(), len: 0 };
 
 /// 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
@@ -268,10 +264,10 @@ impl<K, V> Root<K, V> {
 
     /// Removes the root node, using its first child as the new root. This cannot be called when
     /// the tree consists only of a leaf node. As it is intended only to be called when the root
-    /// has only one edge, no cleanup is done on any of the other children are elements of the root.
+    /// has only one edge, no cleanup is done on any of the other children of the root.
     /// This decreases the height by 1 and is the opposite of `push_level`.
     pub fn pop_level(&mut self) {
-        debug_assert!(self.height > 0);
+        assert!(self.height > 0);
 
         let top = self.node.ptr;
 
@@ -349,6 +345,9 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
 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`.
+    /// For any node, the number of possible edge handles is also `len() + 1`.
+    /// Note that, despite being safe, calling this function can have the side effect
+    /// of invalidating mutable references that unsafe code has created.
     pub fn len(&self) -> usize {
         self.as_header().len as usize
     }
@@ -374,7 +373,8 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
     /// If the node is a leaf, this function simply opens up its data.
     /// If the node is an internal node, so not a leaf, it does have all the data a leaf has
     /// (header, keys and values), and this function exposes that.
-    /// See `NodeRef` on why the node may not be a shared root.
+    /// Unsafe because the node must not be the shared root. For more information,
+    /// see the `NodeRef` comments.
     unsafe fn as_leaf(&self) -> &LeafNode<K, V> {
         debug_assert!(!self.is_shared_root());
         self.node.as_ref()
@@ -390,14 +390,14 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
     }
 
     /// Borrows a view into the keys stored in the node.
-    /// Works on all possible nodes, including the shared root.
-    pub fn keys(&self) -> &[K] {
+    /// Unsafe because the caller must ensure that the node is not the shared root.
+    pub unsafe fn keys(&self) -> &[K] {
         self.reborrow().into_key_slice()
     }
 
     /// Borrows a view into the values stored in the node.
-    /// The caller must ensure that the node is not the shared root.
-    fn vals(&self) -> &[V] {
+    /// Unsafe because the caller must ensure that the node is not the shared root.
+    unsafe fn vals(&self) -> &[V] {
         self.reborrow().into_val_slice()
     }
 
@@ -429,25 +429,26 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
     }
 
     pub fn first_edge(self) -> Handle<Self, marker::Edge> {
-        Handle::new_edge(self, 0)
+        unsafe { Handle::new_edge(self, 0) }
     }
 
     pub fn last_edge(self) -> Handle<Self, marker::Edge> {
         let len = self.len();
-        Handle::new_edge(self, len)
+        unsafe { Handle::new_edge(self, len) }
     }
 
     /// Note that `self` must be nonempty.
     pub fn first_kv(self) -> Handle<Self, marker::KV> {
-        debug_assert!(self.len() > 0);
-        Handle::new_kv(self, 0)
+        let len = self.len();
+        assert!(len > 0);
+        unsafe { Handle::new_kv(self, 0) }
     }
 
     /// Note that `self` must be nonempty.
     pub fn last_kv(self) -> Handle<Self, marker::KV> {
         let len = self.len();
-        debug_assert!(len > 0);
-        Handle::new_kv(self, len - 1)
+        assert!(len > 0);
+        unsafe { Handle::new_kv(self, len - 1) }
     }
 }
 
@@ -458,7 +459,7 @@ impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
     pub unsafe fn deallocate_and_ascend(
         self,
     ) -> Option<Handle<NodeRef<marker::Owned, K, V, marker::Internal>, marker::Edge>> {
-        debug_assert!(!self.is_shared_root());
+        assert!(!self.is_shared_root());
         let node = self.node;
         let ret = self.ascend().ok();
         Global.dealloc(node.cast(), Layout::new::<LeafNode<K, V>>());
@@ -513,71 +514,35 @@ impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
         self.node.as_ptr()
     }
 
-    /// The caller must ensure that the node is not the shared root.
-    fn keys_mut(&mut self) -> &mut [K] {
-        unsafe { self.reborrow_mut().into_key_slice_mut() }
+    /// Unsafe because the caller must ensure that the node is not the shared root.
+    unsafe fn keys_mut(&mut self) -> &mut [K] {
+        self.reborrow_mut().into_key_slice_mut()
     }
 
-    /// The caller must ensure that the node is not the shared root.
-    fn vals_mut(&mut self) -> &mut [V] {
-        unsafe { self.reborrow_mut().into_val_slice_mut() }
+    /// Unsafe because the caller must ensure that the node is not the shared root.
+    unsafe fn vals_mut(&mut self) -> &mut [V] {
+        self.reborrow_mut().into_val_slice_mut()
     }
 }
 
 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
-    fn into_key_slice(self) -> &'a [K] {
-        // We have to be careful here because we might be pointing to the shared root.
-        // In that case, we must not create an `&LeafNode`.  We could just return
-        // an empty slice whenever the length is 0 (this includes the shared root),
-        // but we want to avoid that run-time check.
-        // Instead, we create a slice pointing into the node whenever possible.
-        // We can sometimes do this even for the shared root, as the slice will be
-        // empty and `NodeHeader` contains an empty `keys_start` array.
-        // We cannot *always* do this because:
-        // - `keys_start` is not correctly typed because we want `NodeHeader`'s size to
-        //   not depend on the alignment of `K` (needed because `as_header` should be safe).
-        //   For this reason, `NodeHeader` has this `K2` parameter (that's usually `()`
-        //   and hence just adds a size-0-align-1 field, not affecting layout).
-        //   If the correctly typed header is more highly aligned than the allocated header,
-        //   we cannot transmute safely.
-        // - Even if we can transmute, the offset of a correctly typed `keys_start` might
-        //   be different and outside the bounds of the allocated header!
-        // So we do an alignment check and a size check first, that will be evaluated
-        // at compile-time, and only do any run-time check in the rare case that
-        // the compile-time checks signal danger.
-        if (mem::align_of::<NodeHeader<K, V, K>>() > mem::align_of::<NodeHeader<K, V>>()
-            || mem::size_of::<NodeHeader<K, V, K>>() != mem::size_of::<NodeHeader<K, V>>())
-            && self.is_shared_root()
-        {
-            &[]
-        } else {
-            // If we are a `LeafNode<K, V>`, we can always transmute to
-            // `NodeHeader<K, V, K>` and `keys_start` always has the same offset
-            // as the actual `keys`.
-            // Thanks to the checks above, we know that we can transmute to
-            // `NodeHeader<K, V, K>` and that `keys_start` will be
-            // in-bounds of some allocation even if this is the shared root!
-            // (We might be one-past-the-end, but that is allowed by LLVM.)
-            // Thus we can use `NodeHeader<K, V, K>`
-            // to compute the pointer where the keys start.
-            // This entire hack will become unnecessary once
-            // <https://github.com/rust-lang/rfcs/pull/2582> lands, then we can just take a raw
-            // pointer to the `keys` field of `*const InternalNode<K, V>`.
-            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 because the caller must ensure that the node is not the shared root.
+    unsafe fn into_key_slice(self) -> &'a [K] {
+        debug_assert!(!self.is_shared_root());
+        // We cannot be the shared root, so `as_leaf` is okay.
+        slice::from_raw_parts(MaybeUninit::first_ptr(&self.as_leaf().keys), self.len())
     }
 
-    /// The caller must ensure that the node is not the shared root.
-    fn into_val_slice(self) -> &'a [V] {
+    /// Unsafe because the caller must ensure that the node is not the shared root.
+    unsafe fn into_val_slice(self) -> &'a [V] {
         debug_assert!(!self.is_shared_root());
         // We cannot be the shared root, so `as_leaf` is okay.
-        unsafe { slice::from_raw_parts(MaybeUninit::first_ptr(&self.as_leaf().vals), self.len()) }
+        slice::from_raw_parts(MaybeUninit::first_ptr(&self.as_leaf().vals), self.len())
     }
 
-    fn into_slices(self) -> (&'a [K], &'a [V]) {
-        let k = unsafe { ptr::read(&self) };
+    /// Unsafe because the caller must ensure that the node is not the shared root.
+    unsafe fn into_slices(self) -> (&'a [K], &'a [V]) {
+        let k = ptr::read(&self);
         (k.into_key_slice(), self.into_val_slice())
     }
 }
@@ -589,59 +554,45 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
         unsafe { &mut *(self.root as *mut Root<K, V>) }
     }
 
-    fn into_key_slice_mut(mut self) -> &'a mut [K] {
-        // Same as for `into_key_slice` above, we try to avoid a run-time check.
-        if (mem::align_of::<NodeHeader<K, V, K>>() > mem::align_of::<NodeHeader<K, V>>()
-            || mem::size_of::<NodeHeader<K, V, K>>() != mem::size_of::<NodeHeader<K, V>>())
-            && self.is_shared_root()
-        {
-            &mut []
-        } else {
-            unsafe {
-                slice::from_raw_parts_mut(
-                    MaybeUninit::first_ptr_mut(&mut (*self.as_leaf_mut()).keys),
-                    self.len(),
-                )
-            }
-        }
+    /// Unsafe because the caller must ensure that the node is not the shared root.
+    unsafe fn into_key_slice_mut(mut self) -> &'a mut [K] {
+        debug_assert!(!self.is_shared_root());
+        // We cannot be the shared root, so `as_leaf_mut` is okay.
+        slice::from_raw_parts_mut(
+            MaybeUninit::first_ptr_mut(&mut (*self.as_leaf_mut()).keys),
+            self.len(),
+        )
     }
 
-    /// The caller must ensure that the node is not the shared root.
-    fn into_val_slice_mut(mut self) -> &'a mut [V] {
+    /// Unsafe because the caller must ensure that the node is not the shared root.
+    unsafe fn into_val_slice_mut(mut self) -> &'a mut [V] {
         debug_assert!(!self.is_shared_root());
-        unsafe {
-            slice::from_raw_parts_mut(
-                MaybeUninit::first_ptr_mut(&mut (*self.as_leaf_mut()).vals),
-                self.len(),
-            )
-        }
+        slice::from_raw_parts_mut(
+            MaybeUninit::first_ptr_mut(&mut (*self.as_leaf_mut()).vals),
+            self.len(),
+        )
     }
 
-    /// The caller must ensure that the node is not the shared root.
-    fn into_slices_mut(mut self) -> (&'a mut [K], &'a mut [V]) {
+    /// Unsafe because the caller must ensure that the node is not the shared root.
+    unsafe fn into_slices_mut(mut self) -> (&'a mut [K], &'a mut [V]) {
         debug_assert!(!self.is_shared_root());
         // We cannot use the getters here, because calling the second one
         // invalidates the reference returned by the first.
         // More precisely, it is the call to `len` that is the culprit,
         // because that creates a shared reference to the header, which *can*
         // overlap with the keys (and even the values, for ZST keys).
-        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);
-            (keys, vals)
-        }
+        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);
+        (keys, vals)
     }
 }
 
 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
     /// Adds a key/value pair the end of the node.
     pub fn push(&mut self, key: K, val: V) {
-        // Necessary for correctness, but this is an internal module
-        debug_assert!(self.len() < CAPACITY);
+        assert!(self.len() < CAPACITY);
         debug_assert!(!self.is_shared_root());
 
         let idx = self.len();
@@ -656,8 +607,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
 
     /// Adds a key/value pair to the beginning of the node.
     pub fn push_front(&mut self, key: K, val: V) {
-        // Necessary for correctness, but this is an internal module
-        debug_assert!(self.len() < CAPACITY);
+        assert!(self.len() < CAPACITY);
         debug_assert!(!self.is_shared_root());
 
         unsafe {
@@ -673,9 +623,8 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
     /// Adds a key/value pair and an edge to go to the right of that pair to
     /// the end of the node.
     pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
-        // Necessary for correctness, but this is an internal module
-        debug_assert!(edge.height == self.height - 1);
-        debug_assert!(self.len() < CAPACITY);
+        assert!(edge.height == self.height - 1);
+        assert!(self.len() < CAPACITY);
         debug_assert!(!self.is_shared_root());
 
         let idx = self.len();
@@ -691,23 +640,25 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
         }
     }
 
-    fn correct_childrens_parent_links(&mut self, first: usize, after_last: usize) {
+    // Unsafe because 'first' and 'after_last' must be in range
+    unsafe fn correct_childrens_parent_links(&mut self, first: usize, after_last: usize) {
+        debug_assert!(first <= self.len());
+        debug_assert!(after_last <= self.len() + 1);
         for i in first..after_last {
-            Handle::new_edge(unsafe { self.reborrow_mut() }, i).correct_parent_link();
+            Handle::new_edge(self.reborrow_mut(), i).correct_parent_link();
         }
     }
 
     fn correct_all_childrens_parent_links(&mut self) {
         let len = self.len();
-        self.correct_childrens_parent_links(0, len + 1);
+        unsafe { self.correct_childrens_parent_links(0, len + 1) };
     }
 
     /// Adds a key/value pair and an edge to go to the left of that pair to
     /// the beginning of the node.
     pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) {
-        // Necessary for correctness, but this is an internal module
-        debug_assert!(edge.height == self.height - 1);
-        debug_assert!(self.len() < CAPACITY);
+        assert!(edge.height == self.height - 1);
+        assert!(self.len() < CAPACITY);
         debug_assert!(!self.is_shared_root());
 
         unsafe {
@@ -733,8 +684,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
     /// Removes a key/value pair from the end of this node. If this is an internal node,
     /// also removes the edge that was to the right of that pair.
     pub fn pop(&mut self) -> (K, V, Option<Root<K, V>>) {
-        // Necessary for correctness, but this is an internal module
-        debug_assert!(self.len() > 0);
+        assert!(self.len() > 0);
 
         let idx = self.len() - 1;
 
@@ -760,8 +710,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
     /// Removes a key/value pair from the beginning of this node. If this is an internal node,
     /// also removes the edge that was to the left of that pair.
     pub fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) {
-        // Necessary for correctness, but this is an internal module
-        debug_assert!(self.len() > 0);
+        assert!(self.len() > 0);
 
         let old_len = self.len();
 
@@ -796,8 +745,8 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
         }
     }
 
-    /// The caller must ensure that the node is not the shared root.
-    fn into_kv_pointers_mut(mut self) -> (*mut K, *mut V) {
+    /// Unsafe because the caller must ensure that the node is not the shared root.
+    unsafe fn into_kv_pointers_mut(mut self) -> (*mut K, *mut V) {
         (self.keys_mut().as_mut_ptr(), self.vals_mut().as_mut_ptr())
     }
 }
@@ -859,20 +808,20 @@ impl<Node, Type> Handle<Node, Type> {
 }
 
 impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
-    /// Creates a new handle to a key/value pair in `node`. `idx` must be less than `node.len()`.
-    pub fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
-        // Necessary for correctness, but in a private module
+    /// Creates a new handle to a key/value pair in `node`.
+    /// Unsafe because the caller must ensure that `idx < node.len()`.
+    pub unsafe fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
         debug_assert!(idx < node.len());
 
         Handle { node, idx, _marker: PhantomData }
     }
 
     pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
-        Handle::new_edge(self.node, self.idx)
+        unsafe { Handle::new_edge(self.node, self.idx) }
     }
 
     pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
-        Handle::new_edge(self.node, self.idx + 1)
+        unsafe { Handle::new_edge(self.node, self.idx + 1) }
     }
 }
 
@@ -884,6 +833,14 @@ impl<BorrowType, K, V, NodeType, HandleType> PartialEq
     }
 }
 
+impl<BorrowType, K, V, NodeType, HandleType> PartialOrd
+    for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
+{
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        if self.node.node == other.node.node { Some(self.idx.cmp(&other.idx)) } else { None }
+    }
+}
+
 impl<BorrowType, K, V, NodeType, HandleType>
     Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
 {
@@ -914,21 +871,28 @@ impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeT
 }
 
 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
+    /// Creates a new handle to an edge in `node`.
+    /// Unsafe because the caller must ensure that `idx <= node.len()`.
+    pub unsafe fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
         debug_assert!(idx <= node.len());
 
         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) }
+        if self.idx > 0 {
+            Ok(unsafe { 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) }
+        if self.idx < self.node.len() {
+            Ok(unsafe { Handle::new_kv(self.node, self.idx) })
+        } else {
+            Err(self)
+        }
     }
 }
 
@@ -960,9 +924,10 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge
     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)
+            let kv = unsafe { Handle::new_kv(self.node, self.idx) };
+            (InsertResult::Fit(kv), ptr)
         } else {
-            let middle = Handle::new_kv(self.node, B);
+            let middle = unsafe { 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) }
@@ -1037,14 +1002,14 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
         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);
+        assert!(edge.height == self.node.height - 1);
 
         if self.node.len() < CAPACITY {
             self.insert_fit(key, val, edge);
-            InsertResult::Fit(Handle::new_kv(self.node, self.idx))
+            let kv = unsafe { Handle::new_kv(self.node, self.idx) };
+            InsertResult::Fit(kv)
         } else {
-            let middle = Handle::new_kv(self.node, B);
+            let middle = unsafe { Handle::new_kv(self.node, B) };
             let (mut left, k, v, mut right) = middle.split();
             if self.idx <= B {
                 unsafe {
@@ -1083,15 +1048,19 @@ impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marke
 
 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 {
+            let (keys, vals) = self.node.into_slices();
+            (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> {
     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 {
+            let (keys, vals) = self.node.into_slices_mut();
+            (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
+        }
     }
 }
 
@@ -1113,7 +1082,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV>
     /// - 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>) {
-        debug_assert!(!self.node.is_shared_root());
+        assert!(!self.node.is_shared_root());
         unsafe {
             let mut new_node = Box::new(LeafNode::new());
 
@@ -1145,7 +1114,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV>
     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());
+        assert!(!self.node.is_shared_root());
         unsafe {
             let k = slice_remove(self.node.keys_mut(), self.idx);
             let v = slice_remove(self.node.vals_mut(), self.idx);
@@ -1228,7 +1197,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
         let right_len = right_node.len();
 
         // necessary for correctness, but in a private module
-        debug_assert!(left_len + right_len + 1 <= CAPACITY);
+        assert!(left_len + right_len + 1 <= CAPACITY);
 
         unsafe {
             ptr::write(
@@ -1327,8 +1296,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
             let right_len = right_node.len();
 
             // Make sure that we may steal safely.
-            debug_assert!(right_len + count <= CAPACITY);
-            debug_assert!(left_len >= count);
+            assert!(right_len + count <= CAPACITY);
+            assert!(left_len >= count);
 
             let new_left_len = left_len - count;
 
@@ -1384,8 +1353,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
             let right_len = right_node.len();
 
             // Make sure that we may steal safely.
-            debug_assert!(left_len + count <= CAPACITY);
-            debug_assert!(right_len >= count);
+            assert!(left_len + count <= CAPACITY);
+            assert!(right_len >= count);
 
             let new_right_len = right_len - count;
 
@@ -1458,6 +1427,22 @@ unsafe fn move_edges<K, V>(
     dest.correct_childrens_parent_links(dest_offset, dest_offset + count);
 }
 
+impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::KV> {
+    pub fn forget_node_type(
+        self,
+    ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
+        unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
+    }
+}
+
+impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV> {
+    pub fn forget_node_type(
+        self,
+    ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
+        unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
+    }
+}
+
 impl<BorrowType, K, V, HandleType>
     Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType>
 {
@@ -1493,24 +1478,26 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, ma
             let right_new_len = left_node.len() - left_new_len;
             let mut right_node = right.reborrow_mut();
 
-            debug_assert!(right_node.len() == 0);
-            debug_assert!(left_node.height == right_node.height);
+            assert!(right_node.len() == 0);
+            assert!(left_node.height == right_node.height);
 
-            let left_kv = left_node.reborrow_mut().into_kv_pointers_mut();
-            let right_kv = right_node.reborrow_mut().into_kv_pointers_mut();
+            if right_new_len > 0 {
+                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);
+                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;
-            (*right_node.reborrow_mut().as_leaf_mut()).len = right_new_len as u16;
+                (*left_node.reborrow_mut().as_leaf_mut()).len = left_new_len as u16;
+                (*right_node.reborrow_mut().as_leaf_mut()).len = right_new_len as u16;
 
-            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!();
+                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!();
+                    }
                 }
             }
         }
diff --git a/src/liballoc/collections/btree/search.rs b/src/liballoc/collections/btree/search.rs
index 3f3c49a2ef8..2ba5cebbdee 100644
--- a/src/liballoc/collections/btree/search.rs
+++ b/src/liballoc/collections/btree/search.rs
@@ -10,6 +10,10 @@ pub enum SearchResult<BorrowType, K, V, FoundType, GoDownType> {
     GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>),
 }
 
+/// Looks up a given key in a (sub)tree headed by the given node, recursively.
+/// Returns a `Found` with the handle of the matching KV, if any. Otherwise,
+/// returns a `GoDown` with the handle of the possible leaf edge where the key
+/// belongs.
 pub fn search_tree<BorrowType, K, V, Q: ?Sized>(
     mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
     key: &Q,
@@ -32,6 +36,10 @@ where
     }
 }
 
+/// Looks up a given key in a given node, without recursion.
+/// Returns a `Found` with the handle of the matching KV, if any. Otherwise,
+/// returns a `GoDown` with the handle of the edge where the key might be found.
+/// If the node is a leaf, a `GoDown` edge is not an actual edge but a possible edge.
 pub fn search_node<BorrowType, K, V, Type, Q: ?Sized>(
     node: NodeRef<BorrowType, K, V, Type>,
     key: &Q,
@@ -41,12 +49,17 @@ where
     K: Borrow<Q>,
 {
     match search_linear(&node, key) {
-        (idx, true) => Found(Handle::new_kv(node, idx)),
-        (idx, false) => SearchResult::GoDown(Handle::new_edge(node, idx)),
+        (idx, true) => Found(unsafe { Handle::new_kv(node, idx) }),
+        (idx, false) => SearchResult::GoDown(unsafe { Handle::new_edge(node, idx) }),
     }
 }
 
-pub fn search_linear<BorrowType, K, V, Type, Q: ?Sized>(
+/// Returns the index in the node at which the key (or an equivalent) exists
+/// or could exist, and whether it exists in the node itself. If it doesn't
+/// exist in the node itself, it may exist in the subtree with that index
+/// (if the node has subtrees). If the key doesn't exist in node or subtree,
+/// the returned index is the position or subtree where the key belongs.
+fn search_linear<BorrowType, K, V, Type, Q: ?Sized>(
     node: &NodeRef<BorrowType, K, V, Type>,
     key: &Q,
 ) -> (usize, bool)
@@ -54,12 +67,20 @@ where
     Q: Ord,
     K: Borrow<Q>,
 {
-    for (i, k) in node.keys().iter().enumerate() {
-        match key.cmp(k.borrow()) {
-            Ordering::Greater => {}
-            Ordering::Equal => return (i, true),
-            Ordering::Less => return (i, false),
+    // This function is defined over all borrow types (immutable, mutable, owned),
+    // and may be called on the shared root in each case.
+    // Using `keys()` is fine here even if BorrowType is mutable, as all we return
+    // is an index -- not a reference.
+    let len = node.len();
+    if len > 0 {
+        let keys = unsafe { node.keys() }; // safe because a non-empty node cannot be the shared root
+        for (i, k) in keys.iter().enumerate() {
+            match key.cmp(k.borrow()) {
+                Ordering::Greater => {}
+                Ordering::Equal => return (i, true),
+                Ordering::Less => return (i, false),
+            }
         }
     }
-    (node.keys().len(), false)
+    (len, false)
 }
diff --git a/src/liballoc/collections/btree/set.rs b/src/liballoc/collections/btree/set.rs
index f5487426814..b100ce754ca 100644
--- a/src/liballoc/collections/btree/set.rs
+++ b/src/liballoc/collections/btree/set.rs
@@ -56,12 +56,23 @@ use crate::collections::btree_map::{self, BTreeMap, Keys};
 ///     println!("{}", book);
 /// }
 /// ```
-#[derive(Clone, Hash, PartialEq, Eq, Ord, PartialOrd)]
+#[derive(Hash, PartialEq, Eq, Ord, PartialOrd)]
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct BTreeSet<T> {
     map: BTreeMap<T, ()>,
 }
 
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: Clone> Clone for BTreeSet<T> {
+    fn clone(&self) -> Self {
+        BTreeSet { map: self.map.clone() }
+    }
+
+    fn clone_from(&mut self, other: &Self) {
+        self.map.clone_from(&other.map);
+    }
+}
+
 /// An iterator over the items of a `BTreeSet`.
 ///
 /// This `struct` is created by the [`iter`] method on [`BTreeSet`].
diff --git a/src/liballoc/collections/linked_list.rs b/src/liballoc/collections/linked_list.rs
index 29bf2fdb30c..b88ca8a0fb0 100644
--- a/src/liballoc/collections/linked_list.rs
+++ b/src/liballoc/collections/linked_list.rs
@@ -242,6 +242,121 @@ impl<T> LinkedList<T> {
 
         self.len -= 1;
     }
+
+    /// Splices a series of nodes between two existing nodes.
+    ///
+    /// Warning: this will not check that the provided node belongs to the two existing lists.
+    #[inline]
+    unsafe fn splice_nodes(
+        &mut self,
+        existing_prev: Option<NonNull<Node<T>>>,
+        existing_next: Option<NonNull<Node<T>>>,
+        mut splice_start: NonNull<Node<T>>,
+        mut splice_end: NonNull<Node<T>>,
+        splice_length: usize,
+    ) {
+        // This method takes care not to create multiple mutable references to whole nodes at the same time,
+        // to maintain validity of aliasing pointers into `element`.
+        if let Some(mut existing_prev) = existing_prev {
+            existing_prev.as_mut().next = Some(splice_start);
+        } else {
+            self.head = Some(splice_start);
+        }
+        if let Some(mut existing_next) = existing_next {
+            existing_next.as_mut().prev = Some(splice_end);
+        } else {
+            self.tail = Some(splice_end);
+        }
+        splice_start.as_mut().prev = existing_prev;
+        splice_end.as_mut().next = existing_next;
+
+        self.len += splice_length;
+    }
+
+    /// Detaches all nodes from a linked list as a series of nodes.
+    #[inline]
+    fn detach_all_nodes(mut self) -> Option<(NonNull<Node<T>>, NonNull<Node<T>>, usize)> {
+        let head = self.head.take();
+        let tail = self.tail.take();
+        let len = mem::replace(&mut self.len, 0);
+        if let Some(head) = head {
+            let tail = tail.unwrap_or_else(|| unsafe { core::hint::unreachable_unchecked() });
+            Some((head, tail, len))
+        } else {
+            None
+        }
+    }
+
+    #[inline]
+    unsafe fn split_off_before_node(
+        &mut self,
+        split_node: Option<NonNull<Node<T>>>,
+        at: usize,
+    ) -> Self {
+        // The split node is the new head node of the second part
+        if let Some(mut split_node) = split_node {
+            let first_part_head;
+            let first_part_tail;
+            first_part_tail = split_node.as_mut().prev.take();
+            if let Some(mut tail) = first_part_tail {
+                tail.as_mut().next = None;
+                first_part_head = self.head;
+            } else {
+                first_part_head = None;
+            }
+
+            let first_part = LinkedList {
+                head: first_part_head,
+                tail: first_part_tail,
+                len: at,
+                marker: PhantomData,
+            };
+
+            // Fix the head ptr of the second part
+            self.head = Some(split_node);
+            self.len = self.len - at;
+
+            first_part
+        } else {
+            mem::replace(self, LinkedList::new())
+        }
+    }
+
+    #[inline]
+    unsafe fn split_off_after_node(
+        &mut self,
+        split_node: Option<NonNull<Node<T>>>,
+        at: usize,
+    ) -> Self {
+        // The split node is the new tail node of the first part and owns
+        // the head of the second part.
+        if let Some(mut split_node) = split_node {
+            let second_part_head;
+            let second_part_tail;
+            second_part_head = split_node.as_mut().next.take();
+            if let Some(mut head) = second_part_head {
+                head.as_mut().prev = None;
+                second_part_tail = self.tail;
+            } else {
+                second_part_tail = None;
+            }
+
+            let second_part = LinkedList {
+                head: second_part_head,
+                tail: second_part_tail,
+                len: self.len - at,
+                marker: PhantomData,
+            };
+
+            // Fix the tail ptr of the first part
+            self.tail = Some(split_node);
+            self.len = at;
+
+            second_part
+        } else {
+            mem::replace(self, LinkedList::new())
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -319,6 +434,27 @@ impl<T> LinkedList<T> {
         }
     }
 
+    /// Moves all elements from `other` to the begin of the list.
+    #[unstable(feature = "linked_list_prepend", issue = "none")]
+    pub fn prepend(&mut self, other: &mut Self) {
+        match self.head {
+            None => mem::swap(self, other),
+            Some(mut head) => {
+                // `as_mut` is okay here because we have exclusive access to the entirety
+                // of both lists.
+                if let Some(mut other_tail) = other.tail.take() {
+                    unsafe {
+                        head.as_mut().prev = Some(other_tail);
+                        other_tail.as_mut().next = Some(head);
+                    }
+
+                    self.head = other.head.take();
+                    self.len += mem::replace(&mut other.len, 0);
+                }
+            }
+        }
+    }
+
     /// Provides a forward iterator.
     ///
     /// # Examples
@@ -373,6 +509,42 @@ impl<T> LinkedList<T> {
         IterMut { head: self.head, tail: self.tail, len: self.len, list: self }
     }
 
+    /// Provides a cursor at the front element.
+    ///
+    /// The cursor is pointing to the "ghost" non-element if the list is empty.
+    #[inline]
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn cursor_front(&self) -> Cursor<'_, T> {
+        Cursor { index: 0, current: self.head, list: self }
+    }
+
+    /// Provides a cursor with editing operations at the front element.
+    ///
+    /// The cursor is pointing to the "ghost" non-element if the list is empty.
+    #[inline]
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T> {
+        CursorMut { index: 0, current: self.head, list: self }
+    }
+
+    /// Provides a cursor at the back element.
+    ///
+    /// The cursor is pointing to the "ghost" non-element if the list is empty.
+    #[inline]
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn cursor_back(&self) -> Cursor<'_, T> {
+        Cursor { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self }
+    }
+
+    /// Provides a cursor with editing operations at the back element.
+    ///
+    /// The cursor is pointing to the "ghost" non-element if the list is empty.
+    #[inline]
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T> {
+        CursorMut { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self }
+    }
+
     /// Returns `true` if the `LinkedList` is empty.
     ///
     /// This operation should compute in O(1) time.
@@ -703,30 +875,7 @@ impl<T> LinkedList<T> {
             }
             iter.tail
         };
-
-        // The split node is the new tail node of the first part and owns
-        // the head of the second part.
-        let second_part_head;
-
-        unsafe {
-            second_part_head = split_node.unwrap().as_mut().next.take();
-            if let Some(mut head) = second_part_head {
-                head.as_mut().prev = None;
-            }
-        }
-
-        let second_part = LinkedList {
-            head: second_part_head,
-            tail: self.tail,
-            len: len - at,
-            marker: PhantomData,
-        };
-
-        // Fix the tail ptr of the first part
-        self.tail = split_node;
-        self.len = at;
-
-        second_part
+        unsafe { self.split_off_after_node(split_node, at) }
     }
 
     /// Creates an iterator which uses a closure to determine if an element should be removed.
@@ -986,6 +1135,388 @@ impl<T> IterMut<'_, T> {
     }
 }
 
+/// A cursor over a `LinkedList`.
+///
+/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
+///
+/// Cursors always rest between two elements in the list, and index in a logically circular way.
+/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
+/// tail of the list.
+///
+/// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty.
+#[unstable(feature = "linked_list_cursors", issue = "58533")]
+pub struct Cursor<'a, T: 'a> {
+    index: usize,
+    current: Option<NonNull<Node<T>>>,
+    list: &'a LinkedList<T>,
+}
+
+#[unstable(feature = "linked_list_cursors", issue = "58533")]
+impl<T: fmt::Debug> fmt::Debug for Cursor<'_, T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish()
+    }
+}
+
+/// A cursor over a `LinkedList` with editing operations.
+///
+/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
+/// safely mutate the list during iteration. This is because the lifetime of its yielded
+/// references is tied to its own lifetime, instead of just the underlying list. This means
+/// cursors cannot yield multiple elements at once.
+///
+/// Cursors always rest between two elements in the list, and index in a logically circular way.
+/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
+/// tail of the list.
+#[unstable(feature = "linked_list_cursors", issue = "58533")]
+pub struct CursorMut<'a, T: 'a> {
+    index: usize,
+    current: Option<NonNull<Node<T>>>,
+    list: &'a mut LinkedList<T>,
+}
+
+#[unstable(feature = "linked_list_cursors", issue = "58533")]
+impl<T: fmt::Debug> fmt::Debug for CursorMut<'_, T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish()
+    }
+}
+
+impl<'a, T> Cursor<'a, T> {
+    /// Returns the cursor position index within the `LinkedList`.
+    ///
+    /// This returns `None` if the cursor is currently pointing to the
+    /// "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn index(&self) -> Option<usize> {
+        let _ = self.current?;
+        Some(self.index)
+    }
+
+    /// Moves the cursor to the next element of the `LinkedList`.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this will move it to
+    /// the first element of the `LinkedList`. If it is pointing to the last
+    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn move_next(&mut self) {
+        match self.current.take() {
+            // We had no current element; the cursor was sitting at the start position
+            // Next element should be the head of the list
+            None => {
+                self.current = self.list.head;
+                self.index = 0;
+            }
+            // We had a previous element, so let's go to its next
+            Some(current) => unsafe {
+                self.current = current.as_ref().next;
+                self.index += 1;
+            },
+        }
+    }
+
+    /// Moves the cursor to the previous element of the `LinkedList`.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this will move it to
+    /// the last element of the `LinkedList`. If it is pointing to the first
+    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn move_prev(&mut self) {
+        match self.current.take() {
+            // No current. We're at the start of the list. Yield None and jump to the end.
+            None => {
+                self.current = self.list.tail;
+                self.index = self.list.len().checked_sub(1).unwrap_or(0);
+            }
+            // Have a prev. Yield it and go to the previous element.
+            Some(current) => unsafe {
+                self.current = current.as_ref().prev;
+                self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
+            },
+        }
+    }
+
+    /// Returns a reference to the element that the cursor is currently
+    /// pointing to.
+    ///
+    /// This returns `None` if the cursor is currently pointing to the
+    /// "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn current(&self) -> Option<&'a T> {
+        unsafe { self.current.map(|current| &(*current.as_ptr()).element) }
+    }
+
+    /// Returns a reference to the next element.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this returns
+    /// the first element of the `LinkedList`. If it is pointing to the last
+    /// element of the `LinkedList` then this returns `None`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn peek_next(&self) -> Option<&'a T> {
+        unsafe {
+            let next = match self.current {
+                None => self.list.head,
+                Some(current) => current.as_ref().next,
+            };
+            next.map(|next| &(*next.as_ptr()).element)
+        }
+    }
+
+    /// Returns a reference to the previous element.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this returns
+    /// the last element of the `LinkedList`. If it is pointing to the first
+    /// element of the `LinkedList` then this returns `None`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn peek_prev(&self) -> Option<&'a T> {
+        unsafe {
+            let prev = match self.current {
+                None => self.list.tail,
+                Some(current) => current.as_ref().prev,
+            };
+            prev.map(|prev| &(*prev.as_ptr()).element)
+        }
+    }
+}
+
+impl<'a, T> CursorMut<'a, T> {
+    /// Returns the cursor position index within the `LinkedList`.
+    ///
+    /// This returns `None` if the cursor is currently pointing to the
+    /// "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn index(&self) -> Option<usize> {
+        let _ = self.current?;
+        Some(self.index)
+    }
+
+    /// Moves the cursor to the next element of the `LinkedList`.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this will move it to
+    /// the first element of the `LinkedList`. If it is pointing to the last
+    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn move_next(&mut self) {
+        match self.current.take() {
+            // We had no current element; the cursor was sitting at the start position
+            // Next element should be the head of the list
+            None => {
+                self.current = self.list.head;
+                self.index = 0;
+            }
+            // We had a previous element, so let's go to its next
+            Some(current) => unsafe {
+                self.current = current.as_ref().next;
+                self.index += 1;
+            },
+        }
+    }
+
+    /// Moves the cursor to the previous element of the `LinkedList`.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this will move it to
+    /// the last element of the `LinkedList`. If it is pointing to the first
+    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn move_prev(&mut self) {
+        match self.current.take() {
+            // No current. We're at the start of the list. Yield None and jump to the end.
+            None => {
+                self.current = self.list.tail;
+                self.index = self.list.len().checked_sub(1).unwrap_or(0);
+            }
+            // Have a prev. Yield it and go to the previous element.
+            Some(current) => unsafe {
+                self.current = current.as_ref().prev;
+                self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
+            },
+        }
+    }
+
+    /// Returns a reference to the element that the cursor is currently
+    /// pointing to.
+    ///
+    /// This returns `None` if the cursor is currently pointing to the
+    /// "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn current(&mut self) -> Option<&mut T> {
+        unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) }
+    }
+
+    /// Returns a reference to the next element.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this returns
+    /// the first element of the `LinkedList`. If it is pointing to the last
+    /// element of the `LinkedList` then this returns `None`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn peek_next(&mut self) -> Option<&mut T> {
+        unsafe {
+            let next = match self.current {
+                None => self.list.head,
+                Some(current) => current.as_ref().next,
+            };
+            next.map(|next| &mut (*next.as_ptr()).element)
+        }
+    }
+
+    /// Returns a reference to the previous element.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this returns
+    /// the last element of the `LinkedList`. If it is pointing to the first
+    /// element of the `LinkedList` then this returns `None`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn peek_prev(&mut self) -> Option<&mut T> {
+        unsafe {
+            let prev = match self.current {
+                None => self.list.tail,
+                Some(current) => current.as_ref().prev,
+            };
+            prev.map(|prev| &mut (*prev.as_ptr()).element)
+        }
+    }
+
+    /// Returns a read-only cursor pointing to the current element.
+    ///
+    /// The lifetime of the returned `Cursor` is bound to that of the
+    /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
+    /// `CursorMut` is frozen for the lifetime of the `Cursor`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn as_cursor<'cm>(&'cm self) -> Cursor<'cm, T> {
+        Cursor { list: self.list, current: self.current, index: self.index }
+    }
+}
+
+// Now the list editing operations
+
+impl<'a, T> CursorMut<'a, T> {
+    /// Inserts a new element into the `LinkedList` after the current one.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the new element is
+    /// inserted at the front of the `LinkedList`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn insert_after(&mut self, item: T) {
+        unsafe {
+            let spliced_node = Box::into_raw_non_null(Box::new(Node::new(item)));
+            let node_next = match self.current {
+                None => self.list.head,
+                Some(node) => node.as_ref().next,
+            };
+            self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1);
+            if self.current.is_none() {
+                // The "ghost" non-element's index has changed.
+                self.index = self.list.len;
+            }
+        }
+    }
+
+    /// Inserts a new element into the `LinkedList` before the current one.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the new element is
+    /// inserted at the end of the `LinkedList`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn insert_before(&mut self, item: T) {
+        unsafe {
+            let spliced_node = Box::into_raw_non_null(Box::new(Node::new(item)));
+            let node_prev = match self.current {
+                None => self.list.tail,
+                Some(node) => node.as_ref().prev,
+            };
+            self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1);
+            self.index += 1;
+        }
+    }
+
+    /// Removes the current element from the `LinkedList`.
+    ///
+    /// The element that was removed is returned, and the cursor is
+    /// moved to point to the next element in the `LinkedList`.
+    ///
+    /// If the cursor is currently pointing to the "ghost" non-element then no element
+    /// is removed and `None` is returned.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn remove_current(&mut self) -> Option<T> {
+        let unlinked_node = self.current?;
+        unsafe {
+            self.current = unlinked_node.as_ref().next;
+            self.list.unlink_node(unlinked_node);
+            let unlinked_node = Box::from_raw(unlinked_node.as_ptr());
+            Some(unlinked_node.element)
+        }
+    }
+
+    /// Inserts the elements from the given `LinkedList` after the current one.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the new elements are
+    /// inserted at the start of the `LinkedList`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn splice_after(&mut self, list: LinkedList<T>) {
+        unsafe {
+            let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
+                Some(parts) => parts,
+                _ => return,
+            };
+            let node_next = match self.current {
+                None => self.list.head,
+                Some(node) => node.as_ref().next,
+            };
+            self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len);
+            if self.current.is_none() {
+                // The "ghost" non-element's index has changed.
+                self.index = self.list.len;
+            }
+        }
+    }
+
+    /// Inserts the elements from the given `LinkedList` before the current one.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the new elements are
+    /// inserted at the end of the `LinkedList`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn splice_before(&mut self, list: LinkedList<T>) {
+        unsafe {
+            let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
+                Some(parts) => parts,
+                _ => return,
+            };
+            let node_prev = match self.current {
+                None => self.list.tail,
+                Some(node) => node.as_ref().prev,
+            };
+            self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len);
+            self.index += splice_len;
+        }
+    }
+
+    /// Splits the list into two after the current element. This will return a
+    /// new list consisting of everything after the cursor, with the original
+    /// list retaining everything before.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the entire contents
+    /// of the `LinkedList` are moved.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn split_after(&mut self) -> LinkedList<T> {
+        let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 };
+        if self.index == self.list.len {
+            // The "ghost" non-element's index has changed to 0.
+            self.index = 0;
+        }
+        unsafe { self.list.split_off_after_node(self.current, split_off_idx) }
+    }
+
+    /// Splits the list into two before the current element. This will return a
+    /// new list consisting of everything before the cursor, with the original
+    /// list retaining everything after.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the entire contents
+    /// of the `LinkedList` are moved.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn split_before(&mut self) -> LinkedList<T> {
+        let split_off_idx = self.index;
+        self.index = 0;
+        unsafe { self.list.split_off_before_node(self.current, split_off_idx) }
+    }
+}
+
 /// 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>
diff --git a/src/liballoc/collections/linked_list/tests.rs b/src/liballoc/collections/linked_list/tests.rs
index 1b1d8eab39b..085f734ed91 100644
--- a/src/liballoc/collections/linked_list/tests.rs
+++ b/src/liballoc/collections/linked_list/tests.rs
@@ -304,3 +304,155 @@ fn drain_to_empty_test() {
     assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
 }
+
+#[test]
+fn test_cursor_move_peek() {
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front();
+    assert_eq!(cursor.current(), Some(&1));
+    assert_eq!(cursor.peek_next(), Some(&2));
+    assert_eq!(cursor.peek_prev(), None);
+    assert_eq!(cursor.index(), Some(0));
+    cursor.move_prev();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&1));
+    assert_eq!(cursor.peek_prev(), Some(&6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_next();
+    cursor.move_next();
+    assert_eq!(cursor.current(), Some(&2));
+    assert_eq!(cursor.peek_next(), Some(&3));
+    assert_eq!(cursor.peek_prev(), Some(&1));
+    assert_eq!(cursor.index(), Some(1));
+
+    let mut cursor = m.cursor_back();
+    assert_eq!(cursor.current(), Some(&6));
+    assert_eq!(cursor.peek_next(), None);
+    assert_eq!(cursor.peek_prev(), Some(&5));
+    assert_eq!(cursor.index(), Some(5));
+    cursor.move_next();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&1));
+    assert_eq!(cursor.peek_prev(), Some(&6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_prev();
+    cursor.move_prev();
+    assert_eq!(cursor.current(), Some(&5));
+    assert_eq!(cursor.peek_next(), Some(&6));
+    assert_eq!(cursor.peek_prev(), Some(&4));
+    assert_eq!(cursor.index(), Some(4));
+
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    assert_eq!(cursor.current(), Some(&mut 1));
+    assert_eq!(cursor.peek_next(), Some(&mut 2));
+    assert_eq!(cursor.peek_prev(), None);
+    assert_eq!(cursor.index(), Some(0));
+    cursor.move_prev();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&mut 1));
+    assert_eq!(cursor.peek_prev(), Some(&mut 6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_next();
+    cursor.move_next();
+    assert_eq!(cursor.current(), Some(&mut 2));
+    assert_eq!(cursor.peek_next(), Some(&mut 3));
+    assert_eq!(cursor.peek_prev(), Some(&mut 1));
+    assert_eq!(cursor.index(), Some(1));
+    let mut cursor2 = cursor.as_cursor();
+    assert_eq!(cursor2.current(), Some(&2));
+    assert_eq!(cursor2.index(), Some(1));
+    cursor2.move_next();
+    assert_eq!(cursor2.current(), Some(&3));
+    assert_eq!(cursor2.index(), Some(2));
+    assert_eq!(cursor.current(), Some(&mut 2));
+    assert_eq!(cursor.index(), Some(1));
+
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_back_mut();
+    assert_eq!(cursor.current(), Some(&mut 6));
+    assert_eq!(cursor.peek_next(), None);
+    assert_eq!(cursor.peek_prev(), Some(&mut 5));
+    assert_eq!(cursor.index(), Some(5));
+    cursor.move_next();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&mut 1));
+    assert_eq!(cursor.peek_prev(), Some(&mut 6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_prev();
+    cursor.move_prev();
+    assert_eq!(cursor.current(), Some(&mut 5));
+    assert_eq!(cursor.peek_next(), Some(&mut 6));
+    assert_eq!(cursor.peek_prev(), Some(&mut 4));
+    assert_eq!(cursor.index(), Some(4));
+    let mut cursor2 = cursor.as_cursor();
+    assert_eq!(cursor2.current(), Some(&5));
+    assert_eq!(cursor2.index(), Some(4));
+    cursor2.move_prev();
+    assert_eq!(cursor2.current(), Some(&4));
+    assert_eq!(cursor2.index(), Some(3));
+    assert_eq!(cursor.current(), Some(&mut 5));
+    assert_eq!(cursor.index(), Some(4));
+}
+
+#[test]
+fn test_cursor_mut_insert() {
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    cursor.insert_before(7);
+    cursor.insert_after(8);
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_prev();
+    cursor.insert_before(9);
+    cursor.insert_after(10);
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]);
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_prev();
+    assert_eq!(cursor.remove_current(), None);
+    cursor.move_next();
+    cursor.move_next();
+    assert_eq!(cursor.remove_current(), Some(7));
+    cursor.move_prev();
+    cursor.move_prev();
+    cursor.move_prev();
+    assert_eq!(cursor.remove_current(), Some(9));
+    cursor.move_next();
+    assert_eq!(cursor.remove_current(), Some(10));
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    let mut p: LinkedList<u32> = LinkedList::new();
+    p.extend(&[100, 101, 102, 103]);
+    let mut q: LinkedList<u32> = LinkedList::new();
+    q.extend(&[200, 201, 202, 203]);
+    cursor.splice_after(p);
+    cursor.splice_before(q);
+    check_links(&m);
+    assert_eq!(
+        m.iter().cloned().collect::<Vec<_>>(),
+        &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]
+    );
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_prev();
+    let tmp = cursor.split_before();
+    assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
+    m = tmp;
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    let tmp = cursor.split_after();
+    assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]);
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]);
+}
diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index fdabf109b2e..ffa4176cc79 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -60,6 +60,7 @@
 #![stable(feature = "alloc", since = "1.36.0")]
 #![doc(
     html_root_url = "https://doc.rust-lang.org/nightly/",
+    html_playground_url = "https://play.rust-lang.org/",
     issue_tracker_base_url = "https://github.com/rust-lang/rust/issues/",
     test(no_crate_inject, attr(allow(unused_variables), deny(warnings)))
 )]
@@ -104,7 +105,6 @@
 #![feature(ptr_offset_from)]
 #![feature(rustc_attrs)]
 #![feature(receiver_trait)]
-#![feature(slice_from_raw_parts)]
 #![feature(specialization)]
 #![feature(staged_api)]
 #![feature(std_internals)]
diff --git a/src/liballoc/raw_vec.rs b/src/liballoc/raw_vec.rs
index 86aed612efe..144654946a2 100644
--- a/src/liballoc/raw_vec.rs
+++ b/src/liballoc/raw_vec.rs
@@ -7,7 +7,7 @@ use core::ops::Drop;
 use core::ptr::{self, NonNull, Unique};
 use core::slice;
 
-use crate::alloc::{handle_alloc_error, Alloc, AllocErr, Global, Layout};
+use crate::alloc::{handle_alloc_error, AllocErr, AllocRef, Global, Layout};
 use crate::boxed::Box;
 use crate::collections::TryReserveError::{self, *};
 
@@ -42,13 +42,13 @@ mod tests;
 /// field. This allows zero-sized types to not be special-cased by consumers of
 /// this type.
 #[allow(missing_debug_implementations)]
-pub struct RawVec<T, A: Alloc = Global> {
+pub struct RawVec<T, A: AllocRef = Global> {
     ptr: Unique<T>,
     cap: usize,
     a: A,
 }
 
-impl<T, A: Alloc> RawVec<T, A> {
+impl<T, A: AllocRef> RawVec<T, A> {
     /// Like `new`, but parameterized over the choice of allocator for
     /// the returned `RawVec`.
     pub const fn new_in(a: A) -> Self {
@@ -147,7 +147,7 @@ impl<T> RawVec<T, Global> {
     }
 }
 
-impl<T, A: Alloc> RawVec<T, A> {
+impl<T, A: AllocRef> RawVec<T, A> {
     /// Reconstitutes a `RawVec` from a pointer, capacity, and allocator.
     ///
     /// # Undefined Behavior
@@ -182,7 +182,7 @@ impl<T> RawVec<T, Global> {
     }
 }
 
-impl<T, A: Alloc> RawVec<T, A> {
+impl<T, A: AllocRef> RawVec<T, A> {
     /// Gets a raw pointer to the start of the allocation. Note that this is
     /// `Unique::empty()` if `capacity == 0` or `T` is zero-sized. In the former case, you must
     /// be careful.
@@ -280,7 +280,7 @@ impl<T, A: Alloc> 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: Alloc> 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: Alloc> 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;
         }
     }
@@ -622,7 +623,7 @@ enum ReserveStrategy {
 
 use ReserveStrategy::*;
 
-impl<T, A: Alloc> RawVec<T, A> {
+impl<T, A: AllocRef> RawVec<T, A> {
     fn reserve_internal(
         &mut self,
         used_capacity: usize,
@@ -700,7 +701,7 @@ impl<T> RawVec<T, Global> {
     }
 }
 
-impl<T, A: Alloc> RawVec<T, A> {
+impl<T, A: AllocRef> RawVec<T, A> {
     /// Frees the memory owned by the `RawVec` *without* trying to drop its contents.
     pub unsafe fn dealloc_buffer(&mut self) {
         let elem_size = mem::size_of::<T>();
@@ -712,7 +713,7 @@ impl<T, A: Alloc> RawVec<T, A> {
     }
 }
 
-unsafe impl<#[may_dangle] T, A: Alloc> Drop for RawVec<T, A> {
+unsafe impl<#[may_dangle] T, A: AllocRef> Drop for RawVec<T, A> {
     /// Frees the memory owned by the `RawVec` *without* trying to drop its contents.
     fn drop(&mut self) {
         unsafe {
diff --git a/src/liballoc/raw_vec/tests.rs b/src/liballoc/raw_vec/tests.rs
index b214cef3011..63087501f0e 100644
--- a/src/liballoc/raw_vec/tests.rs
+++ b/src/liballoc/raw_vec/tests.rs
@@ -19,7 +19,7 @@ fn allocator_param() {
     struct BoundedAlloc {
         fuel: usize,
     }
-    unsafe impl Alloc for BoundedAlloc {
+    unsafe impl AllocRef for BoundedAlloc {
         unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
             let size = layout.size();
             if size > self.fuel {
diff --git a/src/liballoc/rc.rs b/src/liballoc/rc.rs
index 3080a8bf459..9dc5447397f 100644
--- a/src/liballoc/rc.rs
+++ b/src/liballoc/rc.rs
@@ -252,7 +252,7 @@ use core::ptr::{self, NonNull};
 use core::slice::{self, from_raw_parts_mut};
 use core::usize;
 
-use crate::alloc::{box_free, handle_alloc_error, Alloc, Global, Layout};
+use crate::alloc::{box_free, handle_alloc_error, AllocRef, Global, Layout};
 use crate::string::String;
 use crate::vec::Vec;
 
@@ -565,9 +565,19 @@ impl<T: ?Sized> Rc<T> {
     /// ```
     #[stable(feature = "rc_raw", since = "1.17.0")]
     pub fn into_raw(this: Self) -> *const T {
-        let ptr: *const T = &*this;
+        let ptr: *mut RcBox<T> = NonNull::as_ptr(this.ptr);
+        let fake_ptr = ptr as *mut T;
         mem::forget(this);
-        ptr
+
+        // SAFETY: This cannot go through Deref::deref.
+        // Instead, we manually offset the pointer rather than manifesting a reference.
+        // This is so that the returned pointer retains the same provenance as our pointer.
+        // This is required so that e.g. `get_mut` can write through the pointer
+        // after the Rc is recovered through `from_raw`.
+        unsafe {
+            let offset = data_offset(&(*ptr).value);
+            set_data_ptr(fake_ptr, (ptr as *mut u8).offset(offset))
+        }
     }
 
     /// Constructs an `Rc` from a raw pointer.
diff --git a/src/liballoc/string.rs b/src/liballoc/string.rs
index 96f871d8897..3cb1f259a0b 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,
@@ -2208,6 +2208,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/sync.rs b/src/liballoc/sync.rs
index dc53ad28407..fd285242d5b 100644
--- a/src/liballoc/sync.rs
+++ b/src/liballoc/sync.rs
@@ -25,7 +25,7 @@ use core::sync::atomic;
 use core::sync::atomic::Ordering::{Acquire, Relaxed, Release, SeqCst};
 use core::{isize, usize};
 
-use crate::alloc::{box_free, handle_alloc_error, Alloc, Global, Layout};
+use crate::alloc::{box_free, handle_alloc_error, AllocRef, Global, Layout};
 use crate::boxed::Box;
 use crate::rc::is_dangling;
 use crate::string::String;
@@ -545,9 +545,19 @@ impl<T: ?Sized> Arc<T> {
     /// ```
     #[stable(feature = "rc_raw", since = "1.17.0")]
     pub fn into_raw(this: Self) -> *const T {
-        let ptr: *const T = &*this;
+        let ptr: *mut ArcInner<T> = NonNull::as_ptr(this.ptr);
+        let fake_ptr = ptr as *mut T;
         mem::forget(this);
-        ptr
+
+        // SAFETY: This cannot go through Deref::deref.
+        // Instead, we manually offset the pointer rather than manifesting a reference.
+        // This is so that the returned pointer retains the same provenance as our pointer.
+        // This is required so that e.g. `get_mut` can write through the pointer
+        // after the Arc is recovered through `from_raw`.
+        unsafe {
+            let offset = data_offset(&(*ptr).data);
+            set_data_ptr(fake_ptr, (ptr as *mut u8).offset(offset))
+        }
     }
 
     /// Constructs an `Arc` from a raw pointer.
diff --git a/src/liballoc/tests/btree/map.rs b/src/liballoc/tests/btree/map.rs
index 35ce1354f52..0a26d7bf427 100644
--- a/src/liballoc/tests/btree/map.rs
+++ b/src/liballoc/tests/btree/map.rs
@@ -4,6 +4,7 @@ use std::convert::TryFrom;
 use std::fmt::Debug;
 use std::iter::FromIterator;
 use std::ops::Bound::{self, Excluded, Included, Unbounded};
+use std::ops::RangeBounds;
 use std::rc::Rc;
 
 use super::DeterministicRng;
@@ -22,6 +23,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));
     }
@@ -68,6 +74,11 @@ fn test_basic_small() {
     assert_eq!(map.last_key_value(), None);
     assert_eq!(map.keys().count(), 0);
     assert_eq!(map.values().count(), 0);
+    assert_eq!(map.range(..).next(), None);
+    assert_eq!(map.range(..1).next(), None);
+    assert_eq!(map.range(1..).next(), None);
+    assert_eq!(map.range(1..=1).next(), None);
+    assert_eq!(map.range(1..2).next(), None);
     assert_eq!(map.insert(1, 1), None);
 
     // 1 key-value pair:
@@ -118,6 +129,11 @@ fn test_basic_small() {
     assert_eq!(map.last_key_value(), None);
     assert_eq!(map.keys().count(), 0);
     assert_eq!(map.values().count(), 0);
+    assert_eq!(map.range(..).next(), None);
+    assert_eq!(map.range(..1).next(), None);
+    assert_eq!(map.range(1..).next(), None);
+    assert_eq!(map.range(1..=1).next(), None);
+    assert_eq!(map.range(1..2).next(), None);
     assert_eq!(map.remove(&1), None);
 }
 
@@ -128,7 +144,6 @@ fn test_iter() {
     #[cfg(miri)]
     let size = 200;
 
-    // Forwards
     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 
     fn test<T>(size: usize, mut iter: T)
@@ -154,7 +169,6 @@ fn test_iter_rev() {
     #[cfg(miri)]
     let size = 200;
 
-    // Forwards
     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 
     fn test<T>(size: usize, mut iter: T)
@@ -275,7 +289,6 @@ fn test_iter_mixed() {
     #[cfg(miri)]
     let size = 200;
 
-    // Forwards
     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 
     fn test<T>(size: usize, mut iter: T)
@@ -299,27 +312,147 @@ fn test_iter_mixed() {
     test(size, map.into_iter());
 }
 
-#[test]
-fn test_range_small() {
-    let size = 5;
-
-    // Forwards
-    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
-
-    let mut j = 0;
-    for ((&k, &v), i) in map.range(2..).zip(2..size) {
-        assert_eq!(k, i);
-        assert_eq!(v, i);
-        j += 1;
-    }
-    assert_eq!(j, size - 2);
+fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> {
+    map.range(range)
+        .map(|(&k, &v)| {
+            assert_eq!(k, v);
+            k
+        })
+        .collect()
 }
 
 #[test]
-fn test_range_inclusive() {
-    let size = 500;
+fn test_range_small() {
+    let size = 4;
+
+    let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
+    let all: Vec<_> = (1..=size).collect();
+    let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
+
+    assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
+    assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
+    assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
+    assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
+    assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
+    assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
+    assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
+    assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
+    assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
+    assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
+    assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
+    assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
+    assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
+    assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
+    assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
+    assert_eq!(range_keys(&map, ..), all);
+
+    assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
+    assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
+    assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
+    assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
+    assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
+    assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
+    assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
+    assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
+    assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
+    assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
+    assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
+    assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
+    assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
+    assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
+    assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
+    assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
+    assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
+    assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
+    assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
+    assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
+    assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
+    assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
+    assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
+    assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
+    assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
+    assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
+    assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
+    assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
+
+    assert_eq!(range_keys(&map, ..3), vec![1, 2]);
+    assert_eq!(range_keys(&map, 3..), vec![3, 4]);
+    assert_eq!(range_keys(&map, 2..=3), vec![2, 3]);
+}
+
+#[test]
+fn test_range_depth_2() {
+    // Assuming that node.CAPACITY is 11, having 12 pairs implies a depth 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.
+
+    let map: BTreeMap<_, _> = (1..=12).map(|i| (i, i)).collect();
+    for &root in &[6, 7] {
+        assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]);
+        assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]);
+        assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]);
+        assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]);
+
+        assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]);
+        assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]);
+        assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]);
+        assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]);
+    }
+}
+
+#[test]
+fn test_range_large() {
+    let size = 200;
 
-    let map: BTreeMap<_, _> = (0..=size).map(|i| (i, i)).collect();
+    let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
+    let all: Vec<_> = (1..=size).collect();
+    let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
+
+    assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
+    assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
+    assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
+    assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
+    assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
+    assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
+    assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
+    assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
+    assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
+    assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
+    assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
+    assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
+    assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
+    assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
+    assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
+    assert_eq!(range_keys(&map, ..), all);
+
+    assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
+    assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
+    assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
+    assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
+    assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
+    assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
+    assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
+    assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
+    assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
+    assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
+    assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
+    assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
+    assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
+    assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
+    assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
+    assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
+    assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
+    assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
+    assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
+    assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
+    assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
+    assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
+    assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
+    assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
+    assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
+    assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
+    assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
+    assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
 
     fn check<'a, L, R>(lhs: L, rhs: R)
     where
@@ -331,18 +464,9 @@ fn test_range_inclusive() {
         assert_eq!(lhs, rhs);
     }
 
-    check(map.range(size + 1..=size + 1), vec![]);
-    check(map.range(size..=size), vec![(&size, &size)]);
-    check(map.range(size..=size + 1), vec![(&size, &size)]);
-    check(map.range(0..=0), vec![(&0, &0)]);
-    check(map.range(0..=size - 1), map.range(..size));
-    check(map.range(-1..=-1), vec![]);
-    check(map.range(-1..=size), map.range(..));
-    check(map.range(..=size), map.range(..));
-    check(map.range(..=200), map.range(..201));
+    check(map.range(..=100), map.range(..101));
     check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
-    check(map.range(-1..=0), vec![(&0, &0)]);
-    check(map.range(-1..=2), vec![(&0, &0), (&1, &1), (&2, &2)]);
+    check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]);
 }
 
 #[test]
@@ -667,6 +791,26 @@ fn test_clone() {
 }
 
 #[test]
+fn test_clone_from() {
+    let mut map1 = BTreeMap::new();
+    let size = 30;
+
+    for i in 0..size {
+        let mut map2 = BTreeMap::new();
+        for j in 0..i {
+            let mut map1_copy = map2.clone();
+            map1_copy.clone_from(&map1);
+            assert_eq!(map1_copy, map1);
+            let mut map2_copy = map1.clone();
+            map2_copy.clone_from(&map2);
+            assert_eq!(map2_copy, map2);
+            map2.insert(100 * j + 1, 2 * j + 1);
+        }
+        map1.insert(i, 10 * i);
+    }
+}
+
+#[test]
 #[allow(dead_code)]
 fn test_variance() {
     use std::collections::btree_map::{IntoIter, Iter, Keys, Range, Values};
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/heap.rs b/src/liballoc/tests/heap.rs
index 43cd7187823..7fcfcf9b294 100644
--- a/src/liballoc/tests/heap.rs
+++ b/src/liballoc/tests/heap.rs
@@ -1,4 +1,4 @@
-use std::alloc::{Alloc, Global, Layout, System};
+use std::alloc::{AllocRef, Global, Layout, System};
 
 /// Issue #45955 and #62251.
 #[test]
@@ -11,7 +11,7 @@ fn std_heap_overaligned_request() {
     check_overalign_requests(Global)
 }
 
-fn check_overalign_requests<T: Alloc>(mut allocator: T) {
+fn check_overalign_requests<T: AllocRef>(mut allocator: T) {
     for &align in &[4, 8, 16, 32] {
         // less than and bigger than `MIN_ALIGN`
         for &size in &[align / 2, align - 1] {
diff --git a/src/liballoc/tests/lib.rs b/src/liballoc/tests/lib.rs
index 3fdee8bbfdf..c1ae67a1a33 100644
--- a/src/liballoc/tests/lib.rs
+++ b/src/liballoc/tests/lib.rs
@@ -11,6 +11,7 @@
 #![feature(associated_type_bounds)]
 #![feature(binary_heap_into_iter_sorted)]
 #![feature(binary_heap_drain_sorted)]
+#![feature(vec_remove_item)]
 
 use std::collections::hash_map::DefaultHasher;
 use std::hash::{Hash, Hasher};
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/vec.rs b/src/liballoc/vec.rs
index f5f8d88829f..4f6b7870e2e 100644
--- a/src/liballoc/vec.rs
+++ b/src/liballoc/vec.rs
@@ -4,6 +4,8 @@
 //! Vectors have `O(1)` indexing, amortized `O(1)` push (to the end) and
 //! `O(1)` pop (from the end).
 //!
+//! Vectors ensure they never allocate more than `isize::MAX` bytes.
+//!
 //! # Examples
 //!
 //! You can explicitly create a [`Vec<T>`] with [`new`]:
@@ -176,7 +178,7 @@ use crate::raw_vec::RawVec;
 /// ```
 ///
 /// In Rust, it's more common to pass slices as arguments rather than vectors
-/// when you just want to provide a read access. The same goes for [`String`] and
+/// when you just want to provide read access. The same goes for [`String`] and
 /// [`&str`].
 ///
 /// # Capacity and reallocation
@@ -1696,13 +1698,14 @@ impl<T> Vec<T> {
     /// # Examples
     ///
     /// ```
+    /// # #![feature(vec_remove_item)]
     /// let mut vec = vec![1, 2, 3, 1];
     ///
     /// vec.remove_item(&1);
     ///
     /// assert_eq!(vec, vec![2, 3, 1]);
     /// ```
-    #[stable(feature = "vec_remove_item", since = "1.42.0")]
+    #[unstable(feature = "vec_remove_item", reason = "recently added", issue = "40062")]
     pub fn remove_item<V>(&mut self, item: &V) -> Option<T>
     where
         T: PartialEq<V>,