Auto merge of #51569 - SimonSapin:liballoc, r=sfackler

Make the public API of the alloc crate a subset of std

This only affects **unstable** APIs.

I plan to submit an RFC proposing to stabilize the crate. The reason it isn’t stable yet (https://github.com/rust-lang/rust/issues/27783) is in case we end up merging the standard library crates into one. However the `core` crate is already stable, so if that happens we’ll need to keep it working somehow (likely by making replacing its contents by `pub use` items). We can do the same for `alloc`. This PR will hopefully make this easier, but even if that doesn’t happen consistency with `std` seems good.

16 files changed, 111 insertions, 68 deletions

diff --git a/src/liballoc/binary_heap.rs b/src/liballoc/collections/binary_heap.rs
index fcadcb544c4..fcadcb544c4 100644
--- a/src/liballoc/binary_heap.rs
+++ b/src/liballoc/collections/binary_heap.rs
diff --git a/src/liballoc/btree/map.rs b/src/liballoc/collections/btree/map.rs
index e6e454446e2..e6e454446e2 100644
--- a/src/liballoc/btree/map.rs
+++ b/src/liballoc/collections/btree/map.rs
diff --git a/src/liballoc/btree/mod.rs b/src/liballoc/collections/btree/mod.rs
index 087c9f228d4..087c9f228d4 100644
--- a/src/liballoc/btree/mod.rs
+++ b/src/liballoc/collections/btree/mod.rs
diff --git a/src/liballoc/btree/node.rs b/src/liballoc/collections/btree/node.rs
index 19bdcbc6ad6..19bdcbc6ad6 100644
--- a/src/liballoc/btree/node.rs
+++ b/src/liballoc/collections/btree/node.rs
diff --git a/src/liballoc/btree/search.rs b/src/liballoc/collections/btree/search.rs
index bc1272fbc78..bc1272fbc78 100644
--- a/src/liballoc/btree/search.rs
+++ b/src/liballoc/collections/btree/search.rs
diff --git a/src/liballoc/btree/set.rs b/src/liballoc/collections/btree/set.rs
index 2aad476d315..af9a7074e4a 100644
--- a/src/liballoc/btree/set.rs
+++ b/src/liballoc/collections/btree/set.rs
@@ -19,7 +19,7 @@ use core::iter::{Peekable, FromIterator, FusedIterator};
 use core::ops::{BitOr, BitAnd, BitXor, Sub, RangeBounds};
 
 use borrow::Borrow;
-use btree_map::{BTreeMap, Keys};
+use collections::btree_map::{self, BTreeMap, Keys};
 use super::Recover;
 
 // FIXME(conventions): implement bounded iterators
@@ -104,7 +104,7 @@ impl<'a, T: 'a + fmt::Debug> fmt::Debug for Iter<'a, T> {
 #[stable(feature = "rust1", since = "1.0.0")]
 #[derive(Debug)]
 pub struct IntoIter<T> {
-    iter: ::btree_map::IntoIter<T, ()>,
+    iter: btree_map::IntoIter<T, ()>,
 }
 
 /// An iterator over a sub-range of items in a `BTreeSet`.
@@ -117,7 +117,7 @@ pub struct IntoIter<T> {
 #[derive(Debug)]
 #[stable(feature = "btree_range", since = "1.17.0")]
 pub struct Range<'a, T: 'a> {
-    iter: ::btree_map::Range<'a, T, ()>,
+    iter: btree_map::Range<'a, T, ()>,
 }
 
 /// A lazy iterator producing elements in the difference of `BTreeSet`s.
diff --git a/src/liballoc/linked_list.rs b/src/liballoc/collections/linked_list.rs
index 9844de9a57d..9844de9a57d 100644
--- a/src/liballoc/linked_list.rs
+++ b/src/liballoc/collections/linked_list.rs
diff --git a/src/liballoc/collections/mod.rs b/src/liballoc/collections/mod.rs
new file mode 100644
index 00000000000..96e0eb633b2
--- /dev/null
+++ b/src/liballoc/collections/mod.rs
@@ -0,0 +1,88 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Collection types.
+
+#![stable(feature = "rust1", since = "1.0.0")]
+
+pub mod binary_heap;
+mod btree;
+pub mod linked_list;
+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 super::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 super::btree::set::*;
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+#[doc(no_inline)]
+pub use self::binary_heap::BinaryHeap;
+
+#[stable(feature = "rust1", since = "1.0.0")]
+#[doc(no_inline)]
+pub use self::btree_map::BTreeMap;
+
+#[stable(feature = "rust1", since = "1.0.0")]
+#[doc(no_inline)]
+pub use self::btree_set::BTreeSet;
+
+#[stable(feature = "rust1", since = "1.0.0")]
+#[doc(no_inline)]
+pub use self::linked_list::LinkedList;
+
+#[stable(feature = "rust1", since = "1.0.0")]
+#[doc(no_inline)]
+pub use self::vec_deque::VecDeque;
+
+use alloc::{AllocErr, LayoutErr};
+
+/// Augments `AllocErr` with a CapacityOverflow variant.
+#[derive(Clone, PartialEq, Eq, Debug)]
+#[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
+pub enum CollectionAllocErr {
+    /// Error due to the computed capacity exceeding the collection's maximum
+    /// (usually `isize::MAX` bytes).
+    CapacityOverflow,
+    /// Error due to the allocator (see the `AllocErr` type's docs).
+    AllocErr,
+}
+
+#[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
+impl From<AllocErr> for CollectionAllocErr {
+    #[inline]
+    fn from(AllocErr: AllocErr) -> Self {
+        CollectionAllocErr::AllocErr
+    }
+}
+
+#[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
+impl From<LayoutErr> for CollectionAllocErr {
+    #[inline]
+    fn from(_: LayoutErr) -> Self {
+        CollectionAllocErr::CapacityOverflow
+    }
+}
+
+/// 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);
+}
diff --git a/src/liballoc/vec_deque.rs b/src/liballoc/collections/vec_deque.rs
index e917a65c9c5..ba92b886138 100644
--- a/src/liballoc/vec_deque.rs
+++ b/src/liballoc/collections/vec_deque.rs
@@ -30,7 +30,7 @@ use core::slice;
 use core::hash::{Hash, Hasher};
 use core::cmp;
 
-use alloc::CollectionAllocErr;
+use collections::CollectionAllocErr;
 use raw_vec::RawVec;
 use vec::Vec;
 
@@ -2891,7 +2891,7 @@ mod tests {
 
     #[test]
     fn test_from_vec() {
-        use super::super::vec::Vec;
+        use vec::Vec;
         for cap in 0..35 {
             for len in 0..cap + 1 {
                 let mut vec = Vec::with_capacity(cap);
@@ -2907,7 +2907,7 @@ mod tests {
 
     #[test]
     fn test_vec_from_vecdeque() {
-        use super::super::vec::Vec;
+        use vec::Vec;
 
         fn create_vec_and_test_convert(cap: usize, offset: usize, len: usize) {
             let mut vd = VecDeque::with_capacity(cap);
diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index ec9b5eba561..c054042d5a1 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -13,10 +13,10 @@
 //! 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 re-exported through the [standard library](../std/index.html),
-//! and should not be used through this library.
+//! This library, like libcore, normally doesn’t need to be used directly
+//! since its contents are re-exported in the [`std` crate](../std/index.html).
+//! Crates that use the `#![no_std]` attribute however will typically
+//! not depend on `std`, so they’d use this crate instead.
 //!
 //! ## Boxed values
 //!
@@ -40,7 +40,7 @@
 //!
 //! ## Atomically reference counted pointers
 //!
-//! The [`Arc`](arc/index.html) type is the threadsafe equivalent of the `Rc`
+//! The [`Arc`](sync/index.html) type is the threadsafe equivalent of the `Rc`
 //! type. It provides all the same functionality of `Rc`, except it requires
 //! that the contained type `T` is shareable. Additionally, `Arc<T>` is itself
 //! sendable while `Rc<T>` is not.
@@ -141,13 +141,6 @@ extern crate rand;
 #[macro_use]
 mod macros;
 
-#[rustc_deprecated(since = "1.27.0", reason = "use the heap module in core, alloc, or std instead")]
-#[unstable(feature = "allocator_api", issue = "32838")]
-/// Use the `alloc` module instead.
-pub mod allocator {
-    pub use alloc::*;
-}
-
 // Heaps provided for low-level allocation strategies
 
 pub mod alloc;
@@ -169,60 +162,20 @@ mod boxed {
 }
 #[cfg(test)]
 mod boxed_test;
+pub mod collections;
 #[cfg(target_has_atomic = "ptr")]
-pub mod arc;
+pub mod sync;
 pub mod rc;
 pub mod raw_vec;
 
-// collections modules
-pub mod binary_heap;
-mod btree;
 pub mod borrow;
 pub mod fmt;
-pub mod linked_list;
 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 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);
-}
-
-#[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;
diff --git a/src/liballoc/raw_vec.rs b/src/liballoc/raw_vec.rs
index 2369ce648fd..4f2686abf45 100644
--- a/src/liballoc/raw_vec.rs
+++ b/src/liballoc/raw_vec.rs
@@ -8,6 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+#![unstable(feature = "raw_vec_internals", reason = "implemention detail", issue = "0")]
+#![doc(hidden)]
+
 use core::cmp;
 use core::mem;
 use core::ops::Drop;
@@ -15,8 +18,8 @@ use core::ptr::{self, NonNull, Unique};
 use core::slice;
 
 use alloc::{Alloc, Layout, Global, handle_alloc_error};
-use alloc::CollectionAllocErr;
-use alloc::CollectionAllocErr::*;
+use collections::CollectionAllocErr;
+use collections::CollectionAllocErr::*;
 use boxed::Box;
 
 /// A low-level utility for more ergonomically allocating, reallocating, and deallocating
@@ -264,7 +267,7 @@ impl<T, A: Alloc> RawVec<T, A> {
     /// # Examples
     ///
     /// ```
-    /// # #![feature(alloc)]
+    /// # #![feature(alloc, raw_vec_internals)]
     /// # extern crate alloc;
     /// # use std::ptr;
     /// # use alloc::raw_vec::RawVec;
@@ -468,7 +471,7 @@ impl<T, A: Alloc> RawVec<T, A> {
     /// # Examples
     ///
     /// ```
-    /// # #![feature(alloc)]
+    /// # #![feature(alloc, raw_vec_internals)]
     /// # extern crate alloc;
     /// # use std::ptr;
     /// # use alloc::raw_vec::RawVec;
diff --git a/src/liballoc/str.rs b/src/liballoc/str.rs
index ec9c39c916c..bb99d0401d3 100644
--- a/src/liballoc/str.rs
+++ b/src/liballoc/str.rs
@@ -51,7 +51,6 @@ use boxed::Box;
 use slice::{SliceConcatExt, SliceIndex};
 use string::String;
 use vec::Vec;
-use vec_deque::VecDeque;
 
 #[stable(feature = "rust1", since = "1.0.0")]
 pub use core::str::{FromStr, Utf8Error};
diff --git a/src/liballoc/string.rs b/src/liballoc/string.rs
index a988b6a26d9..6b28687a060 100644
--- a/src/liballoc/string.rs
+++ b/src/liballoc/string.rs
@@ -66,7 +66,7 @@ use core::ptr;
 use core::str::pattern::Pattern;
 use core::str::lossy;
 
-use alloc::CollectionAllocErr;
+use collections::CollectionAllocErr;
 use borrow::{Cow, ToOwned};
 use boxed::Box;
 use str::{self, from_boxed_utf8_unchecked, FromStr, Utf8Error, Chars};
diff --git a/src/liballoc/arc.rs b/src/liballoc/sync.rs
index 2abd9c85c57..2abd9c85c57 100644
--- a/src/liballoc/arc.rs
+++ b/src/liballoc/sync.rs
diff --git a/src/liballoc/task.rs b/src/liballoc/task.rs
index 7b1947b56b8..f14fe3a20da 100644
--- a/src/liballoc/task.rs
+++ b/src/liballoc/task.rs
@@ -18,10 +18,10 @@ pub use self::if_arc::*;
 #[cfg(target_has_atomic = "ptr")]
 mod if_arc {
     use super::*;
-    use arc::Arc;
     use core::marker::PhantomData;
     use core::mem;
     use core::ptr::{self, NonNull};
+    use sync::Arc;
 
     /// A way of waking up a specific task.
     ///
diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs
index 752a6c966d5..fbbaced540e 100644
--- a/src/liballoc/vec.rs
+++ b/src/liballoc/vec.rs
@@ -80,7 +80,7 @@ use core::ptr;
 use core::ptr::NonNull;
 use core::slice;
 
-use alloc::CollectionAllocErr;
+use collections::CollectionAllocErr;
 use borrow::ToOwned;
 use borrow::Cow;
 use boxed::Box;