Auto merge of #48333 - aidanhs:aphs-no-place-for-placement, r=nikomatsakis

Remove all unstable placement features

Closes #22181, #27779. Effectively makes the assortment of placement RFCs (rust-lang/rfcs#470, rust-lang/rfcs#809, rust-lang/rfcs#1228) 'unaccepted'. It leaves `box_syntax` and keeps the `<-` token as recognised by libsyntax.

------------------------

I don't know the correct process for unaccepting an unstable feature that was accepted as an RFC so...here's a PR.

Let me preface this by saying I'm not particularly happy about doing this (I know it'll be unpopular), but I think it's the most honest expression of how things stand today. I've been motivated by a [post on reddit](https://www.reddit.com/r/rust/comments/7wrqk2/when_will_box_and_placementin_syntax_be_stable/) which asks when these features will be stable - the features have received little RFC-style design work since the end of 2015 (~2 years ago) and leaving them in limbo confuses people who want to know where they're up to. Without additional design work that needs to happen (see the collection of unresolved questions later in this post) they can't really get stabilised, and I think that design work would be most suited to an RFC rather than (currently mostly unused) experimental features in Rust nightly.

I have my own motivations - it's very simple to 'defeat' placement in debug mode today and I don't want a placement in Rust that a) has no guarantees to work and b) has no plan for in-place serde deserialisation.

There's a quote in [1]: "Ordinarily these uncertainties might lead to the RFC being postponed. [The RFC seems like a promising direction hence we will accept since it] will thus give us immediate experience with the design and help in determining the best final solution.". I propose that there have been enough additional uncertainties raised since then that the original direction is less promising and we should be think about the problem anew.

(a historical note: the first mention of placement (under that name - uninit pointers were earlier) in an RFC AFAIK is [0] in late 2014 (pre-1.0). RFCs since then have built on this base - [1] is a comment in Feb 2015 accepting a more conservative design of the Place* traits - this is back when serde still required aster and seemed to break every other nightly! A lot has changed since then, perhaps placement should too)

------------------------

Concrete unresolved questions include:

 - making placement work in debug mode [7]
 - making placement work for serde/with fallible creation [5], [irlo2], [8]
 - trait design:
   - opting into not consuming the placer in `Placer::make_place` - [2]
   - trait proliferation - [4] (+ others in that thread)
   - fallible allocation - [3], [4] (+ others in that thread)
 - support for DSTs/unsized structs (if at all) - [1], [6]

More speculative unresolved questions include:

 - better trait design with in the context of future language features [irlo1] (Q11), [irlo3]
 - interaction between custom allocators and placement [irlo3]

[0] https://github.com/rust-lang/rfcs/pull/470
[1] https://github.com/rust-lang/rfcs/pull/809#issuecomment-73910414
[2] https://github.com/rust-lang/rfcs/issues/1286
[3] https://github.com/rust-lang/rfcs/issues/1315
[4] https://github.com/rust-lang/rust/issues/27779#issuecomment-146711893
[5] https://github.com/rust-lang/rust/issues/27779#issuecomment-285562402
[6] https://github.com/rust-lang/rust/issues/27779#issuecomment-354464938
[7] https://github.com/rust-lang/rust/issues/27779#issuecomment-358025344
[8] https://github.com/rust-lang/rfcs/pull/1228#issuecomment-190825370
[irlo1] https://internals.rust-lang.org/t/placement-nwbi-faq-new-box-in-left-arrow/2789
[irlo2] https://internals.rust-lang.org/t/placement-nwbi-faq-new-box-in-left-arrow/2789/19
[irlo3] https://internals.rust-lang.org/t/lang-team-minutes-feature-status-report-placement-in-and-box/4646

3 files changed, 1 insertions, 177 deletions

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 452fa4e471c..e0b48e565d0 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -22,8 +22,7 @@ use fmt::{self, Debug};
 use hash::{Hash, Hasher, BuildHasher, SipHasher13};
 use iter::{FromIterator, FusedIterator};
 use mem::{self, replace};
-use ops::{Deref, Index, InPlace, Place, Placer};
-use ptr;
+use ops::{Deref, Index};
 use sys;
 
 use super::table::{self, Bucket, EmptyBucket, FullBucket, FullBucketMut, RawTable, SafeHash};
@@ -2043,80 +2042,6 @@ impl<'a, K, V> fmt::Debug for Drain<'a, K, V>
     }
 }
 
-/// A place for insertion to a `Entry`.
-///
-/// See [`HashMap::entry`](struct.HashMap.html#method.entry) for details.
-#[must_use = "places do nothing unless written to with `<-` syntax"]
-#[unstable(feature = "collection_placement",
-           reason = "struct name and placement protocol is subject to change",
-           issue = "30172")]
-pub struct EntryPlace<'a, K: 'a, V: 'a> {
-    bucket: FullBucketMut<'a, K, V>,
-}
-
-#[unstable(feature = "collection_placement",
-           reason = "struct name and placement protocol is subject to change",
-           issue = "30172")]
-impl<'a, K: 'a + Debug, V: 'a + Debug> Debug for EntryPlace<'a, K, V> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        f.debug_struct("EntryPlace")
-            .field("key", self.bucket.read().0)
-            .field("value", self.bucket.read().1)
-            .finish()
-    }
-}
-
-#[unstable(feature = "collection_placement",
-           reason = "struct name and placement protocol is subject to change",
-           issue = "30172")]
-impl<'a, K, V> Drop for EntryPlace<'a, K, V> {
-    fn drop(&mut self) {
-        // Inplacement insertion failed. Only key need to drop.
-        // The value is failed to insert into map.
-        unsafe { self.bucket.remove_key() };
-    }
-}
-
-#[unstable(feature = "collection_placement",
-           reason = "placement protocol is subject to change",
-           issue = "30172")]
-impl<'a, K, V> Placer<V> for Entry<'a, K, V> {
-    type Place = EntryPlace<'a, K, V>;
-
-    fn make_place(self) -> EntryPlace<'a, K, V> {
-        let b = match self {
-            Occupied(mut o) => {
-                unsafe { ptr::drop_in_place(o.elem.read_mut().1); }
-                o.elem
-            }
-            Vacant(v) => {
-                unsafe { v.insert_key() }
-            }
-        };
-        EntryPlace { bucket: b }
-    }
-}
-
-#[unstable(feature = "collection_placement",
-           reason = "placement protocol is subject to change",
-           issue = "30172")]
-unsafe impl<'a, K, V> Place<V> for EntryPlace<'a, K, V> {
-    fn pointer(&mut self) -> *mut V {
-        self.bucket.read_mut().1
-    }
-}
-
-#[unstable(feature = "collection_placement",
-           reason = "placement protocol is subject to change",
-           issue = "30172")]
-impl<'a, K, V> InPlace<V> for EntryPlace<'a, K, V> {
-    type Owner = ();
-
-    unsafe fn finalize(self) {
-        mem::forget(self);
-    }
-}
-
 impl<'a, K, V> Entry<'a, K, V> {
     #[stable(feature = "rust1", since = "1.0.0")]
     /// Ensures a value is in the entry by inserting the default if empty, and returns
@@ -2539,26 +2464,6 @@ impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
         };
         b.into_mut_refs().1
     }
-
-    // Only used for InPlacement insert. Avoid unnecessary value copy.
-    // The value remains uninitialized.
-    unsafe fn insert_key(self) -> FullBucketMut<'a, K, V> {
-        match self.elem {
-            NeqElem(mut bucket, disp) => {
-                if disp >= DISPLACEMENT_THRESHOLD {
-                    bucket.table_mut().set_tag(true);
-                }
-                let uninit = mem::uninitialized();
-                robin_hood(bucket, disp, self.hash, self.key, uninit)
-            },
-            NoElem(mut bucket, disp) => {
-                if disp >= DISPLACEMENT_THRESHOLD {
-                    bucket.table_mut().set_tag(true);
-                }
-                bucket.put_key(self.hash, self.key)
-            },
-        }
-    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -2823,7 +2728,6 @@ mod test_map {
     use super::RandomState;
     use cell::RefCell;
     use rand::{thread_rng, Rng};
-    use panic;
     use realstd::collections::CollectionAllocErr::*;
     use realstd::mem::size_of;
     use realstd::usize;
@@ -3710,59 +3614,6 @@ mod test_map {
     }
 
     #[test]
-    fn test_placement_in() {
-        let mut map = HashMap::new();
-        map.extend((0..10).map(|i| (i, i)));
-
-        map.entry(100) <- 100;
-        assert_eq!(map[&100], 100);
-
-        map.entry(0) <- 10;
-        assert_eq!(map[&0], 10);
-
-        assert_eq!(map.len(), 11);
-    }
-
-    #[test]
-    fn test_placement_panic() {
-        let mut map = HashMap::new();
-        map.extend((0..10).map(|i| (i, i)));
-
-        fn mkpanic() -> usize { panic!() }
-
-        // modify existing key
-        // when panic happens, previous key is removed.
-        let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| { map.entry(0) <- mkpanic(); }));
-        assert_eq!(map.len(), 9);
-        assert!(!map.contains_key(&0));
-
-        // add new key
-        let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| { map.entry(100) <- mkpanic(); }));
-        assert_eq!(map.len(), 9);
-        assert!(!map.contains_key(&100));
-    }
-
-    #[test]
-    fn test_placement_drop() {
-        // correctly drop
-        struct TestV<'a>(&'a mut bool);
-        impl<'a> Drop for TestV<'a> {
-            fn drop(&mut self) {
-                if !*self.0 { panic!("value double drop!"); } // no double drop
-                *self.0 = false;
-            }
-        }
-
-        fn makepanic<'a>() -> TestV<'a> { panic!() }
-
-        let mut can_drop = true;
-        let mut hm = HashMap::new();
-        hm.insert(0, TestV(&mut can_drop));
-        let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| { hm.entry(0) <- makepanic(); }));
-        assert_eq!(hm.len(), 0);
-    }
-
-    #[test]
     fn test_try_reserve() {
 
         let mut empty_bytes: HashMap<u8,u8> = HashMap::new();
diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index c6861c82a23..fa6053d3f6d 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -486,21 +486,6 @@ impl<K, V, M> EmptyBucket<K, V, M>
             table: self.table,
         }
     }
-
-    /// Puts given key, remain value uninitialized.
-    /// It is only used for inplacement insertion.
-    pub unsafe fn put_key(mut self, hash: SafeHash, key: K) -> FullBucket<K, V, M> {
-        *self.raw.hash() = hash.inspect();
-        let pair_ptr = self.raw.pair();
-        ptr::write(&mut (*pair_ptr).0, key);
-
-        self.table.borrow_table_mut().size += 1;
-
-        FullBucket {
-            raw: self.raw,
-            table: self.table,
-        }
-    }
 }
 
 impl<K, V, M: Deref<Target = RawTable<K, V>>> FullBucket<K, V, M> {
@@ -576,17 +561,6 @@ impl<'t, K, V> FullBucket<K, V, &'t mut RawTable<K, V>> {
             v)
         }
     }
-
-    /// Remove this bucket's `key` from the hashtable.
-    /// Only used for inplacement insertion.
-    /// NOTE: `Value` is uninitialized when this function is called, don't try to drop the `Value`.
-    pub unsafe fn remove_key(&mut self) {
-        self.table.size -= 1;
-
-        *self.raw.hash() = EMPTY_BUCKET;
-        let pair_ptr = self.raw.pair();
-        ptr::drop_in_place(&mut (*pair_ptr).0); // only drop key
-    }
 }
 
 // This use of `Put` is misleading and restrictive, but safe and sufficient for our use cases
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index 68d3b946d9e..e18e055654b 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -290,7 +290,6 @@
 #![feature(panic_internals)]
 #![feature(panic_unwind)]
 #![feature(peek)]
-#![feature(placement_in_syntax)]
 #![feature(placement_new_protocol)]
 #![feature(prelude_import)]
 #![feature(ptr_internals)]