update libcore to 2016-04-29 nightly

3 files changed, 518 insertions, 32 deletions

diff --git a/libcollections/btree/map.rs b/libcollections/btree/map.rs
index de40568..20ef273 100644
--- a/libcollections/btree/map.rs
+++ b/libcollections/btree/map.rs
@@ -11,7 +11,7 @@
 use core::cmp::Ordering;
 use core::fmt::Debug;
 use core::hash::{Hash, Hasher};
-use core::iter::FromIterator;
+use core::iter::{FromIterator, Peekable};
 use core::marker::PhantomData;
 use core::ops::Index;
 use core::{fmt, intrinsics, mem, ptr};
@@ -348,6 +348,12 @@ pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
     _marker: PhantomData<&'a mut (K, V)>,
 }
 
+// An iterator for merging two sorted sequences into one
+struct MergeIter<K, V, I: Iterator<Item=(K, V)>> {
+    left: Peekable<I>,
+    right: Peekable<I>,
+}
+
 impl<K: Ord, V> BTreeMap<K, V> {
     /// Makes a new empty BTreeMap with a reasonable choice for B.
     ///
@@ -535,6 +541,62 @@ impl<K: Ord, V> BTreeMap<K, V> {
         }
     }
 
+    /// Moves all elements from `other` into `Self`, leaving `other` empty.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(btree_append)]
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut a = BTreeMap::new();
+    /// a.insert(1, "a");
+    /// a.insert(2, "b");
+    /// a.insert(3, "c");
+    ///
+    /// let mut b = BTreeMap::new();
+    /// b.insert(3, "d");
+    /// b.insert(4, "e");
+    /// b.insert(5, "f");
+    ///
+    /// a.append(&mut b);
+    ///
+    /// assert_eq!(a.len(), 5);
+    /// assert_eq!(b.len(), 0);
+    ///
+    /// assert_eq!(a[&1], "a");
+    /// assert_eq!(a[&2], "b");
+    /// assert_eq!(a[&3], "d");
+    /// assert_eq!(a[&4], "e");
+    /// assert_eq!(a[&5], "f");
+    /// ```
+    #[unstable(feature = "btree_append", reason = "recently added as part of collections reform 2",
+               issue = "19986")]
+    pub fn append(&mut self, other: &mut Self) {
+        // Do we have to append anything at all?
+        if other.len() == 0 {
+            return;
+        }
+
+        // We can just swap `self` and `other` if `self` is empty.
+        if self.len() == 0 {
+            mem::swap(self, other);
+            return;
+        }
+
+        // First, we merge `self` and `other` into a sorted sequence in linear time.
+        let self_iter = mem::replace(self, BTreeMap::new()).into_iter();
+        let other_iter = mem::replace(other, BTreeMap::new()).into_iter();
+        let iter = MergeIter {
+            left: self_iter.peekable(),
+            right: other_iter.peekable(),
+        };
+
+        // Second, we build a tree from the sorted sequence in linear time.
+        self.from_sorted_iter(iter);
+        self.fix_right_edge();
+    }
+
     /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
@@ -724,6 +786,76 @@ impl<K: Ord, V> BTreeMap<K, V> {
             })
         }
     }
+
+    fn from_sorted_iter<I: Iterator<Item=(K, V)>>(&mut self, iter: I) {
+        let mut cur_node = last_leaf_edge(self.root.as_mut()).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.
+            if cur_node.len() < node::CAPACITY {
+                cur_node.push(key, value);
+            } else {
+                // No space left, go up and push there.
+                let mut open_node;
+                let mut test_node = cur_node.forget_type();
+                loop {
+                    match test_node.ascend() {
+                        Ok(parent) => {
+                            let parent = parent.into_node();
+                            if parent.len() < node::CAPACITY {
+                                // Found a node with space left, push here.
+                                open_node = parent;
+                                break;
+                            } else {
+                                // Go up again.
+                                test_node = parent.forget_type();
+                            }
+                        },
+                        Err(node) => {
+                            // We are at the top, create a new root node and push there.
+                            open_node = node.into_root_mut().push_level();
+                            break;
+                        },
+                    }
+                }
+
+                // Push key-value pair and new right subtree.
+                let tree_height = open_node.height() - 1;
+                let mut right_tree = node::Root::new_leaf();
+                for _ in 0..tree_height {
+                    right_tree.push_level();
+                }
+                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();
+            }
+
+            self.length += 1;
+        }
+    }
+
+    fn fix_right_edge(&mut self) {
+        // Handle underfull nodes, start from the top.
+        let mut cur_node = self.root.as_mut();
+        while let Internal(internal) = cur_node.force() {
+            // Check if right-most child is underfull.
+            let mut last_edge = internal.last_edge();
+            let right_child_len = last_edge.reborrow().descend().len();
+            if right_child_len < node::CAPACITY / 2 {
+                // We need to steal.
+                let mut last_kv = match last_edge.left_kv() {
+                    Ok(left) => left,
+                    Err(_) => unreachable!(),
+                };
+                last_kv.bulk_steal_left(node::CAPACITY/2 - right_child_len);
+                last_edge = last_kv.right_edge();
+            }
+
+            // Go further down.
+            cur_node = last_edge.descend();
+        }
+    }
 }
 
 impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
@@ -1690,32 +1822,41 @@ fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
     };
 
     if handle.can_merge() {
-        return Merged(handle.merge().into_node());
+        Merged(handle.merge().into_node())
     } else {
-        unsafe {
-            let (k, v, edge) = if is_left {
-                handle.reborrow_mut().left_edge().descend().pop()
-            } else {
-                handle.reborrow_mut().right_edge().descend().pop_front()
-            };
+        if is_left {
+            handle.steal_left();
+        } else {
+            handle.steal_right();
+        }
+        Stole(handle.into_node())
+    }
+}
 
-            let k = mem::replace(handle.reborrow_mut().into_kv_mut().0, k);
-            let v = mem::replace(handle.reborrow_mut().into_kv_mut().1, v);
+impl<K: Ord, V, I: Iterator<Item=(K, V)>> Iterator for MergeIter<K, V, I> {
+    type Item = (K, V);
 
-            // FIXME: reuse cur_node?
-            if is_left {
-                match handle.reborrow_mut().right_edge().descend().force() {
-                    Leaf(mut leaf) => leaf.push_front(k, v),
-                    Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
-                }
-            } else {
-                match handle.reborrow_mut().left_edge().descend().force() {
-                    Leaf(mut leaf) => leaf.push(k, v),
-                    Internal(mut internal) => internal.push(k, v, edge.unwrap())
-                }
-            }
-        }
+    fn next(&mut self) -> Option<(K, V)> {
+        let res = match (self.left.peek(), self.right.peek()) {
+            (Some(&(ref left_key, _)), Some(&(ref right_key, _))) => left_key.cmp(right_key),
+            (Some(_), None) => Ordering::Less,
+            (None, Some(_)) => Ordering::Greater,
+            (None, None) => return None,
+        };
 
-        return Stole(handle.into_node());
+        // Check which elements comes first and only advance the corresponding iterator.
+        // If two keys are equal, take the value from `right`.
+        match res {
+            Ordering::Less => {
+                self.left.next()
+            },
+            Ordering::Greater => {
+                self.right.next()
+            },
+            Ordering::Equal => {
+                self.left.next();
+                self.right.next()
+            },
+        }
     }
 }
diff --git a/libcollections/btree/node.rs b/libcollections/btree/node.rs
index 8ae23a6..ca1cf6b 100644
--- a/libcollections/btree/node.rs
+++ b/libcollections/btree/node.rs
@@ -31,6 +31,16 @@
 // Since Rust doesn't actually have dependent types and polymorphic recursion,
 // we make do with lots of unsafety.
 
+// A major goal of this module is to avoid complexity by treating the tree as a generic (if
+// weirdly shaped) container and avoiding dealing with most of the B-Tree invariants. As such,
+// this module doesn't care whether the entries are sorted, which nodes can be underfull, or
+// even what underfull means. However, we do rely on a few invariants:
+//
+// - Trees must have uniform depth/height. This means that every path down to a leaf from a
+//   given node has exactly the same length.
+// - 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 alloc::heap;
 use core::marker::PhantomData;
 use core::mem;
@@ -43,17 +53,43 @@ use boxed::Box;
 const B: usize = 6;
 pub const CAPACITY: usize = 2 * B - 1;
 
+/// The underlying representation of leaf nodes. Note that it is often unsafe to actually store
+/// these, since only the first `len` keys and values are assumed to be initialized. As such,
+/// these should always be put behind pointers, and specifically behind `BoxedNode` in the owned
+/// case.
+///
+/// See also rust-lang/rfcs#197, which would make this structure significantly more safe by
+/// avoiding accidentally dropping unused and uninitialized keys and values.
 struct LeafNode<K, V> {
+    /// The arrays storing the actual data of the node. Only the first `len` elements of each
+    /// array are initialized and valid.
     keys: [K; CAPACITY],
     vals: [V; CAPACITY],
+
+    /// 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>,
+
+    /// This node's index into the parent node's `edges` array.
+    /// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`.
+    /// This is only guaranteed to be initialized when `parent` is nonnull.
     parent_idx: u16,
+
+    /// The number of keys and values this node stores.
+    ///
+    /// This is at the end of the node's representation and 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,
 }
 
 impl<K, V> LeafNode<K, V> {
+    /// Creates a new `LeafNode`. Unsafe because all nodes should really be hidden behind
+    /// `BoxedNode`, preventing accidental dropping of uninitialized keys and values.
     unsafe fn new() -> Self {
         LeafNode {
+            // As a general policy, we leave fields uninitialized if they can be, as this should
+            // be both slightly faster and easier to track in Valgrind.
             keys: mem::uninitialized(),
             vals: mem::uninitialized(),
             parent: ptr::null(),
@@ -63,15 +99,28 @@ impl<K, V> LeafNode<K, V> {
     }
 }
 
-// We use repr(C) so that a pointer to an internal node can be
-// directly used as a pointer to a leaf node
+/// 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
+/// `InternalNode` can be directly casted to a pointer to the underlying `LeafNode` portion of the
+/// node, allowing code to act on leaf and internal nodes generically without having to even check
+/// which of the two a pointer is pointing at. This property is enabled by the use of `repr(C)`.
 #[repr(C)]
 struct InternalNode<K, V> {
     data: LeafNode<K, V>,
+
+    /// The pointers to the children of this node. `len + 1` of these are considered
+    /// initialized and valid.
     edges: [BoxedNode<K, V>; 2 * B],
 }
 
 impl<K, V> InternalNode<K, V> {
+    /// Creates a new `InternalNode`.
+    ///
+    /// This is unsafe for two reasons. First, it returns an `InternalNode` by value, risking
+    /// dropping of uninitialized fields. Second, an invariant of internal nodes is that `len + 1`
+    /// edges are initialized and valid, meaning that even when the node is empty (having a
+    /// `len` of 0), there must be one initialized and valid edge. This function does not set up
+    /// such an edge.
     unsafe fn new() -> Self {
         InternalNode {
             data: LeafNode::new(),
@@ -80,8 +129,12 @@ impl<K, V> InternalNode<K, V> {
     }
 }
 
+/// An owned pointer to a node. This basically is either `Box<LeafNode<K, V>>` or
+/// `Box<InternalNode<K, V>>`. However, it contains no information as to which of the two types
+/// of nodes is acutally behind the box, and, partially due to this lack of information, has no
+/// destructor.
 struct BoxedNode<K, V> {
-    ptr: Unique<LeafNode<K, V>> // we don't know if this points to a leaf node or an internal node
+    ptr: Unique<LeafNode<K, V>>
 }
 
 impl<K, V> BoxedNode<K, V> {
@@ -156,7 +209,7 @@ impl<K, V> Root<K, V> {
         }
     }
 
-    /// Add a new internal node with a single edge, pointing to the previous root, and make that
+    /// Adds a new internal node with a single edge, pointing to the previous root, and make that
     /// new node the root. This increases the height by 1 and is the opposite of `pop_level`.
     pub fn push_level(&mut self)
             -> NodeRef<marker::Mut, K, V, marker::Internal> {
@@ -180,7 +233,7 @@ impl<K, V> Root<K, V> {
         ret
     }
 
-    /// Remove the root node, using its first child as the new root. This cannot be called when
+    /// 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.
     /// This decreases the height by 1 and is the opposite of `push_level`.
@@ -229,6 +282,7 @@ impl<K, V> Root<K, V> {
 pub struct NodeRef<BorrowType, K, V, Type> {
     height: usize,
     node: NonZero<*const LeafNode<K, V>>,
+    // This is null unless the borrow type is `Mut`
     root: *const Root<K, V>,
     _marker: PhantomData<(BorrowType, Type)>
 }
@@ -268,10 +322,20 @@ 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`.
     pub fn len(&self) -> usize {
         self.as_leaf().len as usize
     }
 
+    /// Returns the height of this node in the whole tree. Zero height denotes the
+    /// leaf level.
+    pub fn height(&self) -> usize {
+        self.height
+    }
+
+    /// Removes any static information about whether this node is a `Leaf` or an
+    /// `Internal` node.
     pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
         NodeRef {
             height: self.height,
@@ -281,6 +345,7 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
         }
     }
 
+    /// Temporarily takes out another, immutable reference to the same node.
     fn reborrow<'a>(&'a self) -> NodeRef<marker::Immut<'a>, K, V, Type> {
         NodeRef {
             height: self.height,
@@ -304,6 +369,13 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
         self.reborrow().into_slices().1
     }
 
+    /// Finds the parent of the current node. Returns `Ok(handle)` if the current
+    /// node actually has a parent, where `handle` points to the edge of the parent
+    /// that points to the current node. Returns `Err(self)` if the current node has
+    /// no parent, giving back the original `NodeRef`.
+    ///
+    /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
+    /// both, upon success, do nothing.
     pub fn ascend(self) -> Result<
         Handle<
             NodeRef<
@@ -344,6 +416,9 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
 }
 
 impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
+    /// Similar to `ascend`, gets a reference to a node's parent node, but also
+    /// deallocate the current node in the process. This is unsafe because the
+    /// current node will still be accessible despite being deallocated.
     pub unsafe fn deallocate_and_ascend(self) -> Option<
         Handle<
             NodeRef<
@@ -362,6 +437,9 @@ impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
 }
 
 impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
+    /// Similar to `ascend`, gets a reference to a node's parent node, but also
+    /// deallocate the current node in the process. This is unsafe because the
+    /// current node will still be accessible despite being deallocated.
     pub unsafe fn deallocate_and_ascend(self) -> Option<
         Handle<
             NodeRef<
@@ -384,6 +462,8 @@ impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
 }
 
 impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
+    /// Unsafely asserts to the compiler some static information about whether this
+    /// node is a `Leaf`.
     unsafe fn cast_unchecked<NewType>(&mut self)
             -> NodeRef<marker::Mut, K, V, NewType> {
 
@@ -395,6 +475,16 @@ impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
         }
     }
 
+    /// Temporarily takes out another, mutable reference to the same node. Beware, as
+    /// this method is very dangerous, doubly so since it may not immediately appear
+    /// dangerous.
+    ///
+    /// Because mutable pointers can roam anywhere around the tree and can even (through
+    /// `into_root_mut`) mess with the root of the tree, the result of `reborrow_mut`
+    /// can easily be used to make the original mutable pointer dangling, or, in the case
+    /// of a reborrowed handle, out of bounds.
+    // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef` that restricts
+    // the use of `ascend` and `into_root_mut` on reborrowed pointers, preventing this unsafety.
     unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut, K, V, Type> {
         NodeRef {
             height: self.height,
@@ -437,6 +527,8 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
 }
 
 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
+    /// Gets a mutable reference to the root itself. This is useful primarily when the
+    /// height of the tree needs to be adjusted. Never call this on a reborrowed pointer.
     pub fn into_root_mut(self) -> &'a mut Root<K, V> {
         unsafe {
             &mut *(self.root as *mut Root<K, V>)
@@ -460,6 +552,7 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
 }
 
 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);
@@ -474,6 +567,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
         self.as_leaf_mut().len += 1;
     }
 
+    /// 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);
@@ -488,6 +582,8 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
 }
 
 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);
@@ -506,6 +602,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 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);
@@ -534,6 +632,8 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
 }
 
 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);
@@ -558,6 +658,8 @@ 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);
@@ -597,6 +699,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
 }
 
 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+    /// Checks whether a node is an `Internal` node or a `Leaf` node.
     pub fn force(self) -> ForceResult<
         NodeRef<BorrowType, K, V, marker::Leaf>,
         NodeRef<BorrowType, K, V, marker::Internal>
@@ -619,6 +722,14 @@ impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
     }
 }
 
+/// A reference to a specific key/value pair or edge within a node. The `Node` parameter
+/// must be a `NodeRef`, while the `Type` can either be `KV` (signifying a handle on a key/value
+/// pair) or `Edge` (signifying a handle on an edge).
+///
+/// Note that even `Leaf` nodes can have `Edge` handles. Instead of representing a pointer to
+/// a child node, these represent the spaces where child pointers would go between the key/value
+/// pairs. For example, in a node with length 2, there would be 3 possible edge locations - one
+/// to the left of the node, one between the two pairs, and one at the right of the node.
 pub struct Handle<Node, Type> {
     node: Node,
     idx: usize,
@@ -626,6 +737,8 @@ pub struct Handle<Node, Type> {
 }
 
 impl<Node: Copy, Type> Copy for Handle<Node, Type> { }
+// We don't need the full generality of `#[derive(Clone)]`, as the only time `Node` will be
+// `Clone`able is when it is an immutable reference and therefore `Copy`.
 impl<Node: Copy, Type> Clone for Handle<Node, Type> {
     fn clone(&self) -> Self {
         *self
@@ -633,12 +746,14 @@ impl<Node: Copy, Type> Clone for Handle<Node, Type> {
 }
 
 impl<Node, Type> Handle<Node, Type> {
+    /// Retrieves the node that contains the edge of key/value pair this handle pointes to.
     pub fn into_node(self) -> Node {
         self.node
     }
 }
 
 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
         debug_assert!(idx < node.len());
@@ -670,6 +785,7 @@ impl<BorrowType, K, V, NodeType, HandleType> PartialEq
 impl<BorrowType, K, V, NodeType, HandleType>
         Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
 
+    /// Temporarily takes out another, immutable handle on the same location.
     pub fn reborrow(&self)
             -> Handle<NodeRef<marker::Immut, K, V, NodeType>, HandleType> {
 
@@ -685,6 +801,16 @@ impl<BorrowType, K, V, NodeType, HandleType>
 impl<'a, K, V, NodeType, HandleType>
         Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
 
+    /// Temporarily takes out another, mutable handle on the same location. Beware, as
+    /// this method is very dangerous, doubly so since it may not immediately appear
+    /// dangerous.
+    ///
+    /// Because mutable pointers can roam anywhere around the tree and can even (through
+    /// `into_root_mut`) mess with the root of the tree, the result of `reborrow_mut`
+    /// can easily be used to make the original mutable pointer dangling, or, in the case
+    /// of a reborrowed handle, out of bounds.
+    // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef` that restricts
+    // the use of `ascend` and `into_root_mut` on reborrowed pointers, preventing this unsafety.
     pub unsafe fn reborrow_mut(&mut self)
             -> Handle<NodeRef<marker::Mut, K, V, NodeType>, HandleType> {
 
@@ -700,6 +826,8 @@ impl<'a, K, V, NodeType, HandleType>
 impl<BorrowType, K, V, NodeType>
         Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
 
+    /// Creates a new handle to an edge in `node`. `idx` must be less than or equal to
+    /// `node.len()`.
     pub fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
         // Necessary for correctness, but in a private module
         debug_assert!(idx <= node.len());
@@ -733,6 +861,11 @@ impl<BorrowType, K, V, NodeType>
 }
 
 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
+    /// Inserts a new key/value pair between the key/value pairs to the right and left of
+    /// this edge. This method assumes that there is enough space in the node for the new
+    /// pair to fit.
+    ///
+    /// The returned pointer points to the inserted value.
     fn insert_fit(&mut self, key: K, val: V) -> *mut V {
         // Necessary for correctness, but in a private module
         debug_assert!(self.node.len() < CAPACITY);
@@ -747,6 +880,10 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge
         }
     }
 
+    /// Inserts a new key/value pair between the key/value pairs to the right and left of
+    /// this edge. This method splits the node if there isn't enough room.
+    ///
+    /// The returned pointer points to the inserted value.
     pub fn insert(mut self, key: K, val: V)
             -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
 
@@ -774,6 +911,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge
 }
 
 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
+    /// Fixes the parent pointer and index in the child node below this edge. This is useful
+    /// when the ordering of edges has been changed, such as in the various `insert` methods.
     fn correct_parent_link(mut self) {
         let idx = self.idx as u16;
         let ptr = self.node.as_internal_mut() as *mut _;
@@ -782,18 +921,24 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
         child.as_leaf_mut().parent_idx = idx;
     }
 
+    /// Unsafely asserts to the compiler some static information about whether the underlying
+    /// node of this handle is a `Leaf`.
     unsafe fn cast_unchecked<NewType>(&mut self)
             -> Handle<NodeRef<marker::Mut, K, V, NewType>, marker::Edge> {
 
         Handle::new_edge(self.node.cast_unchecked(), self.idx)
     }
 
+    /// Inserts a new key/value pair and an edge that will go to the right of that new pair
+    /// between this edge and the key/value pair to the right of this edge. This method assumes
+    /// that there is enough space in the node for the new pair to fit.
     fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
         // Necessary for correctness, but in an internal module
         debug_assert!(self.node.len() < CAPACITY);
         debug_assert!(edge.height == self.node.height - 1);
 
         unsafe {
+            // This cast is a lie, but it allows us to reuse the key/value insertion logic.
             self.cast_unchecked::<marker::Leaf>().insert_fit(key, val);
 
             slice_insert(
@@ -811,6 +956,9 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
         }
     }
 
+    /// Inserts a new key/value pair and an edge that will go to the right of that new pair
+    /// between this edge and the key/value pair to the right of this edge. This method splits
+    /// the node if there isn't enough room.
     pub fn insert(mut self, key: K, val: V, edge: Root<K, V>)
             -> InsertResult<'a, K, V, marker::Internal> {
 
@@ -843,6 +991,10 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
 impl<BorrowType, K, V>
         Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
 
+    /// Finds the node pointed to by this edge.
+    ///
+    /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
+    /// both, upon success, do nothing.
     pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
         NodeRef {
             height: self.node.height - 1,
@@ -885,6 +1037,13 @@ impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker
 }
 
 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
+    /// Splits the underlying node into three parts:
+    ///
+    /// - The node is truncated to only contain the key/value pairs to the right of
+    ///   this handle.
+    /// - The key and value pointed to by this handle and extracted.
+    /// - All the key/value pairs to the right of this handle are put into a newly
+    ///   allocated node.
     pub fn split(mut self)
             -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) {
         unsafe {
@@ -920,6 +1079,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV>
         }
     }
 
+    /// Removes the key/value pair pointed to by this handle, returning the edge between the
+    /// now adjacent key/value pairs to the left and right of this handle.
     pub fn remove(mut self)
             -> (Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, K, V) {
         unsafe {
@@ -932,6 +1093,13 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV>
 }
 
 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
+    /// Splits the underlying node into three parts:
+    ///
+    /// - The node is truncated to only contain the edges and key/value pairs to the
+    ///   right of this handle.
+    /// - The key and value pointed to by this handle and extracted.
+    /// - All the edges and key/value pairs to the right of this handle are put into
+    ///   a newly allocated node.
     pub fn split(mut self)
             -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) {
         unsafe {
@@ -979,6 +1147,9 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
         }
     }
 
+    /// Returns whether it is valid to call `.merge()`, i.e., whether there is enough room in
+    /// a node to hold the combination of the nodes to the left and right of this handle along
+    /// with the key/value pair at this handle.
     pub fn can_merge(&self) -> bool {
         (
             self.reborrow()
@@ -993,6 +1164,11 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
         ) <= CAPACITY
     }
 
+    /// Combines the node immediately to the left of this handle, the key/value pair pointed
+    /// to by this handle, and the node immediately to the right of this handle into one new
+    /// child of the underlying node, returning an edge referencing that new child.
+    ///
+    /// Assumes that this edge `.can_merge()`.
     pub fn merge(mut self)
             -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
         let self1 = unsafe { ptr::read(&self) };
@@ -1063,11 +1239,145 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
             Handle::new_edge(self.node, self.idx)
         }
     }
+
+    /// This removes a key/value pair from the left child and replaces it with the key/value pair
+    /// pointed to by this handle while pushing the old key/value pair of this handle into the right
+    /// child.
+    pub fn steal_left(&mut self) {
+        unsafe {
+            let (k, v, edge) = self.reborrow_mut().left_edge().descend().pop();
+
+            let k = mem::replace(self.reborrow_mut().into_kv_mut().0, k);
+            let v = mem::replace(self.reborrow_mut().into_kv_mut().1, v);
+
+            match self.reborrow_mut().right_edge().descend().force() {
+                ForceResult::Leaf(mut leaf) => leaf.push_front(k, v),
+                ForceResult::Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
+            }
+        }
+    }
+
+    /// This removes a key/value pair from the right child and replaces it with the key/value pair
+    /// pointed to by this handle while pushing the old key/value pair of this handle into the left
+    /// child.
+    pub fn steal_right(&mut self) {
+        unsafe {
+            let (k, v, edge) = self.reborrow_mut().right_edge().descend().pop_front();
+
+            let k = mem::replace(self.reborrow_mut().into_kv_mut().0, k);
+            let v = mem::replace(self.reborrow_mut().into_kv_mut().1, v);
+
+            match self.reborrow_mut().left_edge().descend().force() {
+                ForceResult::Leaf(mut leaf) => leaf.push(k, v),
+                ForceResult::Internal(mut internal) => internal.push(k, v, edge.unwrap())
+            }
+        }
+    }
+
+    /// This does stealing similar to `steal_left` but steals multiple elements at once.
+    pub fn bulk_steal_left(&mut self, n: usize) {
+        unsafe {
+            // Get raw pointers to left child's keys, values and edges.
+            let (left_len, left_k, left_v, left_e) = {
+                let mut left = self.reborrow_mut().left_edge().descend();
+
+                (left.len(),
+                 left.keys_mut().as_mut_ptr(),
+                 left.vals_mut().as_mut_ptr(),
+                 match left.force() {
+                     ForceResult::Leaf(_) => None,
+                     ForceResult::Internal(mut i) => Some(i.as_internal_mut().edges.as_mut_ptr()),
+                 })
+            };
+
+            // Get raw pointers to right child's keys, values and edges.
+            let (right_len, right_k, right_v, right_e) = {
+                let mut right = self.reborrow_mut().right_edge().descend();
+
+                (right.len(),
+                 right.keys_mut().as_mut_ptr(),
+                 right.vals_mut().as_mut_ptr(),
+                 match right.force() {
+                     ForceResult::Leaf(_) => None,
+                     ForceResult::Internal(mut i) => Some(i.as_internal_mut().edges.as_mut_ptr()),
+                 })
+            };
+
+            // Get raw pointers to parent's key and value.
+            let (parent_k, parent_v) = {
+                let kv = self.reborrow_mut().into_kv_mut();
+                (kv.0 as *mut K, kv.1 as *mut V)
+            };
+
+            // Make sure that we may steal safely.
+            debug_assert!(right_len + n <= CAPACITY);
+            debug_assert!(left_len >= n);
+
+            // Make room for stolen elements in right child.
+            ptr::copy(right_k,
+                      right_k.offset(n as isize),
+                      right_len);
+            ptr::copy(right_v,
+                      right_v.offset(n as isize),
+                      right_len);
+            if let Some(edges) = right_e {
+                ptr::copy(edges,
+                          edges.offset(n as isize),
+                          right_len+1);
+            }
+
+            // Move elements from the left child to the right one.
+            let left_ind = (left_len - n) as isize;
+            ptr::copy_nonoverlapping(left_k.offset(left_ind + 1),
+                                     right_k,
+                                     n - 1);
+            ptr::copy_nonoverlapping(left_v.offset(left_ind + 1),
+                                     right_v,
+                                     n - 1);
+            match (left_e, right_e) {
+                (Some(left), Some(right)) => {
+                    ptr::copy_nonoverlapping(left.offset(left_ind + 1),
+                                             right,
+                                             n);
+                },
+                (Some(_), None) => unreachable!(),
+                (None, Some(_)) => unreachable!(),
+                (None, None) => {},
+            }
+
+            // Copy parent key/value pair to right child.
+            ptr::copy_nonoverlapping(parent_k,
+                                     right_k.offset(n as isize - 1),
+                                     1);
+            ptr::copy_nonoverlapping(parent_v,
+                                     right_v.offset(n as isize - 1),
+                                     1);
+            // Copy left-most stolen pair to parent.
+            ptr::copy_nonoverlapping(left_k.offset(left_ind),
+                                     parent_k,
+                                     1);
+            ptr::copy_nonoverlapping(left_v.offset(left_ind),
+                                     parent_v,
+                                     1);
+
+            // Fix lengths of left and right child and parent pointers in children of the right
+            // child.
+            self.reborrow_mut().left_edge().descend().as_leaf_mut().len -= n as u16;
+            let mut right = self.reborrow_mut().right_edge().descend();
+            right.as_leaf_mut().len += n as u16;
+            if let ForceResult::Internal(mut node) = right.force() {
+                for i in 0..(right_len+n+1) {
+                    Handle::new_edge(node.reborrow_mut(), i as usize).correct_parent_link();
+                }
+            }
+        }
+    }
 }
 
 impl<BorrowType, K, V, HandleType>
         Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType> {
 
+    /// Check whether the underlying node is an `Internal` node or a `Leaf` node.
     pub fn force(self) -> ForceResult<
         Handle<NodeRef<BorrowType, K, V, marker::Leaf>, HandleType>,
         Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>
diff --git a/libcollections/btree/set.rs b/libcollections/btree/set.rs
index 23e0af8..5419d7a 100644
--- a/libcollections/btree/set.rs
+++ b/libcollections/btree/set.rs
@@ -379,7 +379,7 @@ impl<T: Ord> BTreeSet<T> {
     /// The value may be any borrowed form of the set's value type,
     /// but the ordering on the borrowed form *must* match the
     /// ordering on the value type.
-    #[unstable(feature = "set_recovery", issue = "28050")]
+    #[stable(feature = "set_recovery", since = "1.9.0")]
     pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
         where T: Borrow<Q>,
               Q: Ord
@@ -502,7 +502,7 @@ impl<T: Ord> BTreeSet<T> {
 
     /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
     /// one. Returns the replaced value.
-    #[unstable(feature = "set_recovery", issue = "28050")]
+    #[stable(feature = "set_recovery", since = "1.9.0")]
     pub fn replace(&mut self, value: T) -> Option<T> {
         Recover::replace(&mut self.map, value)
     }
@@ -538,13 +538,48 @@ impl<T: Ord> BTreeSet<T> {
     /// The value may be any borrowed form of the set's value type,
     /// but the ordering on the borrowed form *must* match the
     /// ordering on the value type.
-    #[unstable(feature = "set_recovery", issue = "28050")]
+    #[stable(feature = "set_recovery", since = "1.9.0")]
     pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
         where T: Borrow<Q>,
               Q: Ord
     {
         Recover::take(&mut self.map, value)
     }
+
+    /// Moves all elements from `other` into `Self`, leaving `other` empty.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(btree_append)]
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut a = BTreeSet::new();
+    /// a.insert(1);
+    /// a.insert(2);
+    /// a.insert(3);
+    ///
+    /// let mut b = BTreeSet::new();
+    /// b.insert(3);
+    /// b.insert(4);
+    /// b.insert(5);
+    ///
+    /// a.append(&mut b);
+    ///
+    /// assert_eq!(a.len(), 5);
+    /// assert_eq!(b.len(), 0);
+    ///
+    /// assert!(a.contains(&1));
+    /// assert!(a.contains(&2));
+    /// assert!(a.contains(&3));
+    /// assert!(a.contains(&4));
+    /// assert!(a.contains(&5));
+    /// ```
+    #[unstable(feature = "btree_append", reason = "recently added as part of collections reform 2",
+               issue = "19986")]
+    pub fn append(&mut self, other: &mut Self) {
+        self.map.append(&mut other.map);
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]