Auto merge of #49669 - SimonSapin:global-alloc, r=alexcrichton

Add GlobalAlloc trait + tweaks for initial stabilization

This is the outcome of discussion at the Rust All Hands in Berlin. The high-level goal is stabilizing sooner rather than later the ability to [change the global allocator](https://github.com/rust-lang/rust/issues/27389), as well as allocating memory without abusing `Vec::with_capacity` + `mem::forget`.

Since we’re not ready to settle every detail of the `Alloc` trait for the purpose of collections that are generic over the allocator type (for example the possibility of a separate trait for deallocation only, and what that would look like exactly), we propose introducing separately **a new `GlobalAlloc` trait**, for use with the `#[global_allocator]` attribute.

We also propose a number of changes to existing APIs. They are batched in this one PR in order to minimize disruption to Nightly users.

The plan for initial stabilization is detailed in the tracking issue https://github.com/rust-lang/rust/issues/49668.

CC @rust-lang/libs, @glandium

## Immediate breaking changes to unstable features

* For pointers to allocated memory, change the pointed type from `u8` to `Opaque`, a new public [extern type](https://github.com/rust-lang/rust/issues/43467). Since extern types are not `Sized`, `<*mut _>::offset` cannot be used without first casting to another pointer type. (We hope that extern types can also be stabilized soon.)
* In the `Alloc` trait, change these pointers to `ptr::NonNull` and change the `AllocErr` type to a zero-size struct. This makes return types `Result<ptr::NonNull<Opaque>, AllocErr>` be pointer-sized.
* Instead of a new `Layout`, `realloc` takes only a new size (in addition to the pointer and old `Layout`). Changing the alignment is not supported with `realloc`.
* Change the return type of `Layout::from_size_align` from `Option<Self>` to `Result<Self, LayoutErr>`, with `LayoutErr` a new opaque struct.
* A `static` item registered as the global allocator with the `#[global_allocator]` **must now implement the new `GlobalAlloc` trait** instead of `Alloc`.

## Eventually-breaking changes to unstable features, with a deprecation period

* Rename the respective `heap` modules to `alloc` in the `core`, `alloc`, and `std` crates. (Yes, this does mean that `::alloc::alloc::Alloc::alloc` is a valid path to a trait method if you have `exetrn crate alloc;`)
* Rename the the `Heap` type to `Global`, since it is the entry point for what’s registered with `#[global_allocator]`.

Old names remain available for now, as deprecated `pub use` reexports.

## Backward-compatible changes

* Add a new [extern type](https://github.com/rust-lang/rust/issues/43467) `Opaque`, for use in pointers to allocated memory.
* Add a new `GlobalAlloc` trait shown below. Unlike `Alloc`, it uses bare `*mut Opaque` without `NonNull` or `Result`. NULL in return values indicates an error (of unspecified nature). This is easier to implement on top of `malloc`-like APIs.
* Add impls of `GlobalAlloc` for both the `Global` and `System` types, in addition to existing impls of `Alloc`. This enables calling `GlobalAlloc` methods on the stable channel before `Alloc` is stable. Implementing two traits with identical method names can make some calls ambiguous, but most code is expected to have no more than one of the two traits in scope. Erroneous code like `use std::alloc::Global; #[global_allocator] static A: Global = Global;` (where `Global` is defined to call itself, causing infinite recursion) is not statically prevented by the type system, but we count on it being hard enough to do accidentally and easy enough to diagnose.

```rust
extern {
    pub type Opaque;
}

pub unsafe trait GlobalAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut Opaque;
    unsafe fn dealloc(&self, ptr: *mut Opaque, layout: Layout);

    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut Opaque {
        // Default impl: self.alloc() and ptr::write_bytes()
    }
    unsafe fn realloc(&self, ptr: *mut Opaque, old_layout: Layout, new_size: usize) -> *mut Opaque {
        // Default impl: self.alloc() and ptr::copy_nonoverlapping() and self.dealloc()
    }

    fn oom(&self) -> ! {
        // intrinsics::abort
    }

    // More methods with default impls may be added in the future
}
```

## Bikeshed

The tracking issue https://github.com/rust-lang/rust/issues/49668 lists some open questions. If consensus is reached before this PR is merged, changes can be integrated.

19 files changed, 181 insertions, 227 deletions

diff --git a/src/libstd/alloc.rs b/src/libstd/alloc.rs
new file mode 100644
index 00000000000..ff578ec42d2
--- /dev/null
+++ b/src/libstd/alloc.rs
@@ -0,0 +1,121 @@
+// Copyright 2017 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.
+
+//! dox
+
+#![unstable(issue = "32838", feature = "allocator_api")]
+
+#[doc(inline)] #[allow(deprecated)] pub use alloc_crate::alloc::Heap;
+#[doc(inline)] pub use alloc_crate::alloc::Global;
+#[doc(inline)] pub use alloc_system::System;
+#[doc(inline)] pub use core::alloc::*;
+
+#[cfg(not(test))]
+#[doc(hidden)]
+#[allow(unused_attributes)]
+pub mod __default_lib_allocator {
+    use super::{System, Layout, GlobalAlloc, Opaque};
+    // for symbol names src/librustc/middle/allocator.rs
+    // for signatures src/librustc_allocator/lib.rs
+
+    // linkage directives are provided as part of the current compiler allocator
+    // ABI
+
+    #[no_mangle]
+    #[rustc_std_internal_symbol]
+    pub unsafe extern fn __rdl_alloc(size: usize, align: usize) -> *mut u8 {
+        let layout = Layout::from_size_align_unchecked(size, align);
+        System.alloc(layout) as *mut u8
+    }
+
+    #[no_mangle]
+    #[rustc_std_internal_symbol]
+    pub unsafe extern fn __rdl_oom() -> ! {
+        System.oom()
+    }
+
+    #[no_mangle]
+    #[rustc_std_internal_symbol]
+    pub unsafe extern fn __rdl_dealloc(ptr: *mut u8,
+                                       size: usize,
+                                       align: usize) {
+        System.dealloc(ptr as *mut Opaque, Layout::from_size_align_unchecked(size, align))
+    }
+
+    #[no_mangle]
+    #[rustc_std_internal_symbol]
+    pub unsafe extern fn __rdl_realloc(ptr: *mut u8,
+                                       old_size: usize,
+                                       align: usize,
+                                       new_size: usize) -> *mut u8 {
+        let old_layout = Layout::from_size_align_unchecked(old_size, align);
+        System.realloc(ptr as *mut Opaque, old_layout, new_size) as *mut u8
+    }
+
+    #[no_mangle]
+    #[rustc_std_internal_symbol]
+    pub unsafe extern fn __rdl_alloc_zeroed(size: usize, align: usize) -> *mut u8 {
+        let layout = Layout::from_size_align_unchecked(size, align);
+        System.alloc_zeroed(layout) as *mut u8
+    }
+
+    #[cfg(stage0)]
+    pub mod stage0 {
+        #[no_mangle]
+        #[rustc_std_internal_symbol]
+        pub unsafe extern fn __rdl_usable_size(_layout: *const u8,
+                                               _min: *mut usize,
+                                               _max: *mut usize) {
+            unimplemented!()
+        }
+
+        #[no_mangle]
+        #[rustc_std_internal_symbol]
+        pub unsafe extern fn __rdl_alloc_excess(_size: usize,
+                                                _align: usize,
+                                                _excess: *mut usize,
+                                                _err: *mut u8) -> *mut u8 {
+            unimplemented!()
+        }
+
+        #[no_mangle]
+        #[rustc_std_internal_symbol]
+        pub unsafe extern fn __rdl_realloc_excess(_ptr: *mut u8,
+                                                  _old_size: usize,
+                                                  _old_align: usize,
+                                                  _new_size: usize,
+                                                  _new_align: usize,
+                                                  _excess: *mut usize,
+                                                  _err: *mut u8) -> *mut u8 {
+            unimplemented!()
+        }
+
+        #[no_mangle]
+        #[rustc_std_internal_symbol]
+        pub unsafe extern fn __rdl_grow_in_place(_ptr: *mut u8,
+                                                 _old_size: usize,
+                                                 _old_align: usize,
+                                                 _new_size: usize,
+                                                 _new_align: usize) -> u8 {
+            unimplemented!()
+        }
+
+        #[no_mangle]
+        #[rustc_std_internal_symbol]
+        pub unsafe extern fn __rdl_shrink_in_place(_ptr: *mut u8,
+                                                   _old_size: usize,
+                                                   _old_align: usize,
+                                                   _new_size: usize,
+                                                   _new_align: usize) -> u8 {
+            unimplemented!()
+        }
+
+    }
+}
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index e0b48e565d0..20a4f9b508d 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -11,10 +11,8 @@
 use self::Entry::*;
 use self::VacantEntryState::*;
 
-use alloc::heap::Heap;
-use alloc::allocator::CollectionAllocErr;
+use alloc::{Global, Alloc, CollectionAllocErr};
 use cell::Cell;
-use core::heap::Alloc;
 use borrow::Borrow;
 use cmp::max;
 use fmt::{self, Debug};
@@ -786,7 +784,7 @@ impl<K, V, S> HashMap<K, V, S>
     pub fn reserve(&mut self, additional: usize) {
         match self.try_reserve(additional) {
             Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"),
-            Err(CollectionAllocErr::AllocErr(e)) => Heap.oom(e),
+            Err(CollectionAllocErr::AllocErr) => Global.oom(),
             Ok(()) => { /* yay */ }
          }
     }
@@ -3636,7 +3634,7 @@ mod test_map {
             if let Err(CapacityOverflow) = empty_bytes.try_reserve(max_no_ovf) {
             } else { panic!("isize::MAX + 1 should trigger a CapacityOverflow!") }
         } else {
-            if let Err(AllocErr(_)) = empty_bytes.try_reserve(max_no_ovf) {
+            if let Err(AllocErr) = empty_bytes.try_reserve(max_no_ovf) {
             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
         }
     }
diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index fa6053d3f6d..93f059076d7 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -8,9 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use alloc::heap::Heap;
-use core::heap::{Alloc, Layout};
-
+use alloc::{Global, Alloc, Layout, CollectionAllocErr};
 use cmp;
 use hash::{BuildHasher, Hash, Hasher};
 use marker;
@@ -18,7 +16,6 @@ use mem::{align_of, size_of, needs_drop};
 use mem;
 use ops::{Deref, DerefMut};
 use ptr::{self, Unique, NonNull};
-use alloc::allocator::CollectionAllocErr;
 
 use self::BucketState::*;
 
@@ -757,15 +754,13 @@ impl<K, V> RawTable<K, V> {
             return Err(CollectionAllocErr::CapacityOverflow);
         }
 
-        let buffer = Heap.alloc(Layout::from_size_align(size, alignment)
-            .ok_or(CollectionAllocErr::CapacityOverflow)?)?;
-
-        let hashes = buffer as *mut HashUint;
+        let buffer = Global.alloc(Layout::from_size_align(size, alignment)
+            .map_err(|_| CollectionAllocErr::CapacityOverflow)?)?;
 
         Ok(RawTable {
             capacity_mask: capacity.wrapping_sub(1),
             size: 0,
-            hashes: TaggedHashUintPtr::new(hashes),
+            hashes: TaggedHashUintPtr::new(buffer.cast().as_ptr()),
             marker: marker::PhantomData,
         })
     }
@@ -775,7 +770,7 @@ impl<K, V> RawTable<K, V> {
     unsafe fn new_uninitialized(capacity: usize) -> RawTable<K, V> {
         match Self::try_new_uninitialized(capacity) {
             Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"),
-            Err(CollectionAllocErr::AllocErr(e)) => Heap.oom(e),
+            Err(CollectionAllocErr::AllocErr) => Global.oom(),
             Ok(table) => { table }
         }
     }
@@ -814,7 +809,7 @@ impl<K, V> RawTable<K, V> {
     pub fn new(capacity: usize) -> RawTable<K, V> {
         match Self::try_new(capacity) {
             Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"),
-            Err(CollectionAllocErr::AllocErr(e)) => Heap.oom(e),
+            Err(CollectionAllocErr::AllocErr) => Global.oom(),
             Ok(table) => { table }
         }
     }
@@ -1188,8 +1183,8 @@ unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for RawTable<K, V> {
         debug_assert!(!oflo, "should be impossible");
 
         unsafe {
-            Heap.dealloc(self.hashes.ptr() as *mut u8,
-                         Layout::from_size_align(size, align).unwrap());
+            Global.dealloc(NonNull::new_unchecked(self.hashes.ptr()).as_opaque(),
+                           Layout::from_size_align(size, align).unwrap());
             // Remember how everything was allocated out of one buffer
             // during initialization? We only need one call to free here.
         }
diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index c7ad27d8d26..9cf73824dea 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -424,13 +424,13 @@
 #[doc(hidden)]
 pub use ops::Bound;
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::{BinaryHeap, BTreeMap, BTreeSet};
+pub use alloc_crate::{BinaryHeap, BTreeMap, BTreeSet};
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::{LinkedList, VecDeque};
+pub use alloc_crate::{LinkedList, VecDeque};
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::{binary_heap, btree_map, btree_set};
+pub use alloc_crate::{binary_heap, btree_map, btree_set};
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::{linked_list, vec_deque};
+pub use alloc_crate::{linked_list, vec_deque};
 
 #[stable(feature = "rust1", since = "1.0.0")]
 pub use self::hash_map::HashMap;
@@ -446,7 +446,7 @@ pub mod range {
 }
 
 #[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
-pub use alloc::allocator::CollectionAllocErr;
+pub use heap::CollectionAllocErr;
 
 mod hash;
 
diff --git a/src/libstd/error.rs b/src/libstd/error.rs
index 3d0c96585b5..3c209928d43 100644
--- a/src/libstd/error.rs
+++ b/src/libstd/error.rs
@@ -51,13 +51,13 @@
 // coherence challenge (e.g., specialization, neg impls, etc) we can
 // reconsider what crate these items belong in.
 
-use alloc::allocator;
 use any::TypeId;
 use borrow::Cow;
 use cell;
 use char;
 use core::array;
 use fmt::{self, Debug, Display};
+use heap::{AllocErr, LayoutErr, CannotReallocInPlace};
 use mem::transmute;
 use num;
 use str;
@@ -241,18 +241,27 @@ impl Error for ! {
 #[unstable(feature = "allocator_api",
            reason = "the precise API and guarantees it provides may be tweaked.",
            issue = "32838")]
-impl Error for allocator::AllocErr {
+impl Error for AllocErr {
     fn description(&self) -> &str {
-        allocator::AllocErr::description(self)
+        "memory allocation failed"
     }
 }
 
 #[unstable(feature = "allocator_api",
            reason = "the precise API and guarantees it provides may be tweaked.",
            issue = "32838")]
-impl Error for allocator::CannotReallocInPlace {
+impl Error for LayoutErr {
     fn description(&self) -> &str {
-        allocator::CannotReallocInPlace::description(self)
+        "invalid parameters to Layout::from_size_align"
+    }
+}
+
+#[unstable(feature = "allocator_api",
+           reason = "the precise API and guarantees it provides may be tweaked.",
+           issue = "32838")]
+impl Error for CannotReallocInPlace {
+    fn description(&self) -> &str {
+        CannotReallocInPlace::description(self)
     }
 }
 
diff --git a/src/libstd/heap.rs b/src/libstd/heap.rs
deleted file mode 100644
index 4a391372c3a..00000000000
--- a/src/libstd/heap.rs
+++ /dev/null
@@ -1,176 +0,0 @@
-// Copyright 2017 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.
-
-//! dox
-
-#![unstable(issue = "32838", feature = "allocator_api")]
-
-pub use alloc::heap::Heap;
-pub use alloc_system::System;
-pub use core::heap::*;
-
-#[cfg(not(test))]
-#[doc(hidden)]
-#[allow(unused_attributes)]
-pub mod __default_lib_allocator {
-    use super::{System, Layout, Alloc, AllocErr};
-    use ptr;
-
-    // for symbol names src/librustc/middle/allocator.rs
-    // for signatures src/librustc_allocator/lib.rs
-
-    // linkage directives are provided as part of the current compiler allocator
-    // ABI
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rdl_alloc(size: usize,
-                                     align: usize,
-                                     err: *mut u8) -> *mut u8 {
-        let layout = Layout::from_size_align_unchecked(size, align);
-        match System.alloc(layout) {
-            Ok(p) => p,
-            Err(e) => {
-                ptr::write(err as *mut AllocErr, e);
-                0 as *mut u8
-            }
-        }
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rdl_oom(err: *const u8) -> ! {
-        System.oom((*(err as *const AllocErr)).clone())
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rdl_dealloc(ptr: *mut u8,
-                                       size: usize,
-                                       align: usize) {
-        System.dealloc(ptr, Layout::from_size_align_unchecked(size, align))
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rdl_usable_size(layout: *const u8,
-                                           min: *mut usize,
-                                           max: *mut usize) {
-        let pair = System.usable_size(&*(layout as *const Layout));
-        *min = pair.0;
-        *max = pair.1;
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rdl_realloc(ptr: *mut u8,
-                                       old_size: usize,
-                                       old_align: usize,
-                                       new_size: usize,
-                                       new_align: usize,
-                                       err: *mut u8) -> *mut u8 {
-        let old_layout = Layout::from_size_align_unchecked(old_size, old_align);
-        let new_layout = Layout::from_size_align_unchecked(new_size, new_align);
-        match System.realloc(ptr, old_layout, new_layout) {
-            Ok(p) => p,
-            Err(e) => {
-                ptr::write(err as *mut AllocErr, e);
-                0 as *mut u8
-            }
-        }
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rdl_alloc_zeroed(size: usize,
-                                            align: usize,
-                                            err: *mut u8) -> *mut u8 {
-        let layout = Layout::from_size_align_unchecked(size, align);
-        match System.alloc_zeroed(layout) {
-            Ok(p) => p,
-            Err(e) => {
-                ptr::write(err as *mut AllocErr, e);
-                0 as *mut u8
-            }
-        }
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rdl_alloc_excess(size: usize,
-                                            align: usize,
-                                            excess: *mut usize,
-                                            err: *mut u8) -> *mut u8 {
-        let layout = Layout::from_size_align_unchecked(size, align);
-        match System.alloc_excess(layout) {
-            Ok(p) => {
-                *excess = p.1;
-                p.0
-            }
-            Err(e) => {
-                ptr::write(err as *mut AllocErr, e);
-                0 as *mut u8
-            }
-        }
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rdl_realloc_excess(ptr: *mut u8,
-                                              old_size: usize,
-                                              old_align: usize,
-                                              new_size: usize,
-                                              new_align: usize,
-                                              excess: *mut usize,
-                                              err: *mut u8) -> *mut u8 {
-        let old_layout = Layout::from_size_align_unchecked(old_size, old_align);
-        let new_layout = Layout::from_size_align_unchecked(new_size, new_align);
-        match System.realloc_excess(ptr, old_layout, new_layout) {
-            Ok(p) => {
-                *excess = p.1;
-                p.0
-            }
-            Err(e) => {
-                ptr::write(err as *mut AllocErr, e);
-                0 as *mut u8
-            }
-        }
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rdl_grow_in_place(ptr: *mut u8,
-                                             old_size: usize,
-                                             old_align: usize,
-                                             new_size: usize,
-                                             new_align: usize) -> u8 {
-        let old_layout = Layout::from_size_align_unchecked(old_size, old_align);
-        let new_layout = Layout::from_size_align_unchecked(new_size, new_align);
-        match System.grow_in_place(ptr, old_layout, new_layout) {
-            Ok(()) => 1,
-            Err(_) => 0,
-        }
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rdl_shrink_in_place(ptr: *mut u8,
-                                               old_size: usize,
-                                               old_align: usize,
-                                               new_size: usize,
-                                               new_align: usize) -> u8 {
-        let old_layout = Layout::from_size_align_unchecked(old_size, old_align);
-        let new_layout = Layout::from_size_align_unchecked(new_size, new_align);
-        match System.shrink_in_place(ptr, old_layout, new_layout) {
-            Ok(()) => 1,
-            Err(_) => 0,
-        }
-    }
-}
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index c82d600e4a1..a34fcb5a7f9 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -275,6 +275,7 @@
 #![feature(macro_reexport)]
 #![feature(macro_vis_matcher)]
 #![feature(needs_panic_runtime)]
+#![feature(nonnull_cast)]
 #![feature(exhaustive_patterns)]
 #![feature(nonzero)]
 #![feature(num_bits_bytes)]
@@ -351,7 +352,7 @@ extern crate core as __core;
 
 #[macro_use]
 #[macro_reexport(vec, format)]
-extern crate alloc;
+extern crate alloc as alloc_crate;
 extern crate alloc_system;
 #[doc(masked)]
 extern crate libc;
@@ -437,21 +438,21 @@ pub use core::u32;
 #[stable(feature = "rust1", since = "1.0.0")]
 pub use core::u64;
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::boxed;
+pub use alloc_crate::boxed;
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::rc;
+pub use alloc_crate::rc;
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::borrow;
+pub use alloc_crate::borrow;
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::fmt;
+pub use alloc_crate::fmt;
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::slice;
+pub use alloc_crate::slice;
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::str;
+pub use alloc_crate::str;
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::string;
+pub use alloc_crate::string;
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::vec;
+pub use alloc_crate::vec;
 #[stable(feature = "rust1", since = "1.0.0")]
 pub use core::char;
 #[stable(feature = "i128", since = "1.26.0")]
@@ -477,7 +478,14 @@ pub mod path;
 pub mod process;
 pub mod sync;
 pub mod time;
-pub mod heap;
+pub mod alloc;
+
+#[unstable(feature = "allocator_api", issue = "32838")]
+#[rustc_deprecated(since = "1.27.0", reason = "module renamed to `alloc`")]
+/// Use the `alloc` module instead.
+pub mod heap {
+    pub use alloc::*;
+}
 
 // Platform-abstraction modules
 #[macro_use]
diff --git a/src/libstd/sync/mod.rs b/src/libstd/sync/mod.rs
index 289b47b3484..642b284c6c7 100644
--- a/src/libstd/sync/mod.rs
+++ b/src/libstd/sync/mod.rs
@@ -18,7 +18,7 @@
 #![stable(feature = "rust1", since = "1.0.0")]
 
 #[stable(feature = "rust1", since = "1.0.0")]
-pub use alloc::arc::{Arc, Weak};
+pub use alloc_crate::arc::{Arc, Weak};
 #[stable(feature = "rust1", since = "1.0.0")]
 pub use core::sync::atomic;
 
diff --git a/src/libstd/sync/mpsc/mpsc_queue.rs b/src/libstd/sync/mpsc/mpsc_queue.rs
index 296773d20f6..df945ac3859 100644
--- a/src/libstd/sync/mpsc/mpsc_queue.rs
+++ b/src/libstd/sync/mpsc/mpsc_queue.rs
@@ -23,10 +23,9 @@
 
 pub use self::PopResult::*;
 
-use alloc::boxed::Box;
 use core::ptr;
 use core::cell::UnsafeCell;
-
+use boxed::Box;
 use sync::atomic::{AtomicPtr, Ordering};
 
 /// A result of the `pop` function.
diff --git a/src/libstd/sync/mpsc/spsc_queue.rs b/src/libstd/sync/mpsc/spsc_queue.rs
index cc4be92276a..9482f6958b3 100644
--- a/src/libstd/sync/mpsc/spsc_queue.rs
+++ b/src/libstd/sync/mpsc/spsc_queue.rs
@@ -16,7 +16,7 @@
 
 // http://www.1024cores.net/home/lock-free-algorithms/queues/unbounded-spsc-queue
 
-use alloc::boxed::Box;
+use boxed::Box;
 use core::ptr;
 use core::cell::UnsafeCell;
 
diff --git a/src/libstd/sys/cloudabi/thread.rs b/src/libstd/sys/cloudabi/thread.rs
index a22d9053b69..5d66936b2a4 100644
--- a/src/libstd/sys/cloudabi/thread.rs
+++ b/src/libstd/sys/cloudabi/thread.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use alloc::boxed::FnBox;
+use boxed::FnBox;
 use cmp;
 use ffi::CStr;
 use io;
diff --git a/src/libstd/sys/redox/thread.rs b/src/libstd/sys/redox/thread.rs
index f20350269b7..110d46ca3ab 100644
--- a/src/libstd/sys/redox/thread.rs
+++ b/src/libstd/sys/redox/thread.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use alloc::boxed::FnBox;
+use boxed::FnBox;
 use ffi::CStr;
 use io;
 use mem;
diff --git a/src/libstd/sys/unix/thread.rs b/src/libstd/sys/unix/thread.rs
index 2db3d4a5744..9e388808030 100644
--- a/src/libstd/sys/unix/thread.rs
+++ b/src/libstd/sys/unix/thread.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use alloc::boxed::FnBox;
+use boxed::FnBox;
 use cmp;
 use ffi::CStr;
 use io;
diff --git a/src/libstd/sys/wasm/thread.rs b/src/libstd/sys/wasm/thread.rs
index 7345843b975..728e678a2e8 100644
--- a/src/libstd/sys/wasm/thread.rs
+++ b/src/libstd/sys/wasm/thread.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use alloc::boxed::FnBox;
+use boxed::FnBox;
 use ffi::CStr;
 use io;
 use sys::{unsupported, Void};
diff --git a/src/libstd/sys/windows/process.rs b/src/libstd/sys/windows/process.rs
index bd5507e8f89..be442f41374 100644
--- a/src/libstd/sys/windows/process.rs
+++ b/src/libstd/sys/windows/process.rs
@@ -31,7 +31,7 @@ use sys::stdio;
 use sys::cvt;
 use sys_common::{AsInner, FromInner, IntoInner};
 use sys_common::process::{CommandEnv, EnvKey};
-use alloc::borrow::Borrow;
+use borrow::Borrow;
 
 ////////////////////////////////////////////////////////////////////////////////
 // Command
diff --git a/src/libstd/sys/windows/thread.rs b/src/libstd/sys/windows/thread.rs
index 4b3d1b586b5..b6f63303dc2 100644
--- a/src/libstd/sys/windows/thread.rs
+++ b/src/libstd/sys/windows/thread.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use alloc::boxed::FnBox;
+use boxed::FnBox;
 use io;
 use ffi::CStr;
 use mem;
diff --git a/src/libstd/sys_common/at_exit_imp.rs b/src/libstd/sys_common/at_exit_imp.rs
index ce6fd4cb075..26da51c9825 100644
--- a/src/libstd/sys_common/at_exit_imp.rs
+++ b/src/libstd/sys_common/at_exit_imp.rs
@@ -12,7 +12,7 @@
 //!
 //! Documentation can be found on the `rt::at_exit` function.
 
-use alloc::boxed::FnBox;
+use boxed::FnBox;
 use ptr;
 use sys_common::mutex::Mutex;
 
diff --git a/src/libstd/sys_common/process.rs b/src/libstd/sys_common/process.rs
index d0c5951bd6c..ddf0ebe603e 100644
--- a/src/libstd/sys_common/process.rs
+++ b/src/libstd/sys_common/process.rs
@@ -14,7 +14,7 @@
 use ffi::{OsStr, OsString};
 use env;
 use collections::BTreeMap;
-use alloc::borrow::Borrow;
+use borrow::Borrow;
 
 pub trait EnvKey:
     From<OsString> + Into<OsString> +
diff --git a/src/libstd/sys_common/thread.rs b/src/libstd/sys_common/thread.rs
index f1379b6ec63..da6f58ef6bb 100644
--- a/src/libstd/sys_common/thread.rs
+++ b/src/libstd/sys_common/thread.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use alloc::boxed::FnBox;
+use boxed::FnBox;
 use env;
 use sync::atomic::{self, Ordering};
 use sys::stack_overflow;