Merge crate `collections` into `alloc`

1 files changed, 150 insertions, 10 deletions

diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index 418a084da67..5252dabc127 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -1,4 +1,4 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// Copyright 2014-2017 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
@@ -8,18 +8,16 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//! # The Rust core allocation library
+//! # The Rust core allocation and collections library
 //!
-//! This is the lowest level library through which allocation in Rust can be
-//! performed.
+//! This library provides smart pointers and collections for managing
+//! heap-allocated values.
 //!
 //! This library, like libcore, is not intended for general usage, but rather as
 //! a building block of other libraries. The types and interfaces in this
 //! library are reexported through the [standard library](../std/index.html),
 //! and should not be used through this library.
 //!
-//! Currently, there are four major definitions in this library.
-//!
 //! ## Boxed values
 //!
 //! The [`Box`](boxed/index.html) type is a smart pointer type. There can
@@ -51,6 +49,12 @@
 //! paired with synchronization primitives such as mutexes to allow mutation of
 //! shared resources.
 //!
+//! ## Collections
+//!
+//! Implementations of the most common general purpose data structures are
+//! defined in this library. They are reexported through the
+//! [standard collections library](../std/collections/index.html).
+//!
 //! ## Heap interfaces
 //!
 //! The [`heap`](heap/index.html) module defines the low-level interface to the
@@ -71,8 +75,20 @@
 #![no_std]
 #![needs_allocator]
 #![deny(warnings)]
+#![deny(missing_debug_implementations)]
 
+#![cfg_attr(test, allow(deprecated))] // rand
+#![cfg_attr(test, feature(placement_in))]
+#![cfg_attr(not(test), feature(char_escape_debug))]
+#![cfg_attr(not(test), feature(core_float))]
+#![cfg_attr(not(test), feature(exact_size_is_empty))]
+#![cfg_attr(not(test), feature(slice_rotate))]
+#![cfg_attr(not(test), feature(sort_unstable))]
+#![cfg_attr(not(test), feature(str_checked_slicing))]
+#![cfg_attr(test, feature(rand, test))]
 #![feature(allocator)]
+#![feature(allow_internal_unstable)]
+#![feature(box_patterns)]
 #![feature(box_syntax)]
 #![feature(cfg_target_has_atomic)]
 #![feature(coerce_unsized)]
@@ -80,16 +96,33 @@
 #![feature(core_intrinsics)]
 #![feature(custom_attribute)]
 #![feature(dropck_eyepatch)]
-#![cfg_attr(not(test), feature(exact_size_is_empty))]
+#![feature(exact_size_is_empty)]
+#![feature(fmt_internals)]
 #![feature(fundamental)]
+#![feature(fused)]
 #![feature(generic_param_attrs)]
+#![feature(i128_type)]
+#![feature(inclusive_range)]
 #![feature(lang_items)]
+#![feature(manually_drop)]
 #![feature(needs_allocator)]
+#![feature(nonzero)]
+#![feature(offset_to)]
 #![feature(optin_builtin_traits)]
+#![feature(pattern)]
 #![feature(placement_in_syntax)]
+#![feature(placement_new_protocol)]
 #![feature(shared)]
+#![feature(slice_get_slice)]
+#![feature(slice_patterns)]
+#![feature(slice_rsplit)]
+#![feature(specialization)]
 #![feature(staged_api)]
+#![feature(str_internals)]
+#![feature(str_mut_extras)]
+#![feature(trusted_len)]
 #![feature(unboxed_closures)]
+#![feature(unicode)]
 #![feature(unique)]
 #![feature(unsize)]
 
@@ -101,6 +134,10 @@
 #[cfg(test)]
 #[macro_use]
 extern crate std;
+#[cfg(test)]
+extern crate test;
+
+extern crate std_unicode;
 
 // Module with internal macros used by other modules (needs to be included before other modules).
 #[macro_use]
@@ -120,7 +157,7 @@ pub mod heap;
 pub mod boxed;
 #[cfg(test)]
 mod boxed {
-    pub use std::boxed::{Box, HEAP};
+    pub use std::boxed::{Box, IntermediateBox, HEAP};
 }
 #[cfg(test)]
 mod boxed_test;
@@ -128,8 +165,111 @@ mod boxed_test;
 pub mod arc;
 pub mod rc;
 pub mod raw_vec;
-#[unstable(feature = "str_box_extras", issue = "41119")]
-pub mod str;
 pub mod oom;
 
+// collections modules
+pub mod binary_heap;
+mod btree;
+pub mod borrow;
+pub mod fmt;
+pub mod linked_list;
+pub mod range;
+pub mod slice;
+pub mod str;
+pub mod string;
+pub mod vec;
+pub mod vec_deque;
+
+#[stable(feature = "rust1", since = "1.0.0")]
+pub mod btree_map {
+    //! A map based on a B-Tree.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub use btree::map::*;
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+pub mod btree_set {
+    //! A set based on a B-Tree.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub use btree::set::*;
+}
+
+#[cfg(not(test))]
+mod std {
+    pub use core::ops;      // RangeFull
+}
+
+/// An endpoint of a range of keys.
+///
+/// # Examples
+///
+/// `Bound`s are range endpoints:
+///
+/// ```
+/// #![feature(collections_range)]
+///
+/// use std::collections::range::RangeArgument;
+/// use std::collections::Bound::*;
+///
+/// assert_eq!((..100).start(), Unbounded);
+/// assert_eq!((1..12).start(), Included(&1));
+/// assert_eq!((1..12).end(), Excluded(&12));
+/// ```
+///
+/// Using a tuple of `Bound`s as an argument to [`BTreeMap::range`].
+/// Note that in most cases, it's better to use range syntax (`1..5`) instead.
+///
+/// ```
+/// use std::collections::BTreeMap;
+/// use std::collections::Bound::{Excluded, Included, Unbounded};
+///
+/// let mut map = BTreeMap::new();
+/// map.insert(3, "a");
+/// map.insert(5, "b");
+/// map.insert(8, "c");
+///
+/// for (key, value) in map.range((Excluded(3), Included(8))) {
+///     println!("{}: {}", key, value);
+/// }
+///
+/// assert_eq!(Some((&3, &"a")), map.range((Unbounded, Included(5))).next());
+/// ```
+///
+/// [`BTreeMap::range`]: btree_map/struct.BTreeMap.html#method.range
+#[stable(feature = "collections_bound", since = "1.17.0")]
+#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
+pub enum Bound<T> {
+    /// An inclusive bound.
+    #[stable(feature = "collections_bound", since = "1.17.0")]
+    Included(T),
+    /// An exclusive bound.
+    #[stable(feature = "collections_bound", since = "1.17.0")]
+    Excluded(T),
+    /// An infinite endpoint. Indicates that there is no bound in this direction.
+    #[stable(feature = "collections_bound", since = "1.17.0")]
+    Unbounded,
+}
+
+/// An intermediate trait for specialization of `Extend`.
+#[doc(hidden)]
+trait SpecExtend<I: IntoIterator> {
+    /// Extends `self` with the contents of the given iterator.
+    fn spec_extend(&mut self, iter: I);
+}
+
 pub use oom::oom;
+
+#[doc(no_inline)]
+pub use binary_heap::BinaryHeap;
+#[doc(no_inline)]
+pub use btree_map::BTreeMap;
+#[doc(no_inline)]
+pub use btree_set::BTreeSet;
+#[doc(no_inline)]
+pub use linked_list::LinkedList;
+#[doc(no_inline)]
+pub use vec_deque::VecDeque;
+#[doc(no_inline)]
+pub use string::String;
+#[doc(no_inline)]
+pub use vec::Vec;