Tracking issue for placement new

[alexcrichton]

This is a tracking issue for the unstable placement_new_protocol feature in the standard library, and placement_in_syntax/box_syntax in the compiler.

(@pnkfelix adds below:)

Things to decide / finalize before stabilization:

• placement-in syntax, e.g. in PLACE { BLOCK } vs PLACE <- EXPR. (See Place left arrow syntax (place <- expr) rfcs#1228 )
• protocol interface, e.g. passing &mut self vs self for the Placer::make_place (Placement protocol should not consume Placer rfcs#1286).
• Is a desugaring box EXPR part of this? (currently the desugaring doesn't work due to type inference issues).
• Factor a common Place for InPlace and BoxPlace, or just have the InPlace trait independently from any BoxPlace.

[nagisa]

At least this needs to be decided before this can become stable.

[huonw]

I've adapted this issue from being explicitly focused on just the library aspects of placement new to encompassing both that and the compiler impl (since they're fairly intertwined). I've also been thinking about this a little recently.

General links:

• RFC Place left arrow syntax (place <- expr) rfcs#1228 changes the syntax from in X { Y } to X <- Y
• box and in expressions (tracking issue for RFC 809) #22181

Trait proliferation

We currently have Place,Placer & InPlace and BoxPlace & Boxed. The Place trait is trying to abstract out a commonality between BoxPlace and InPlace: the pointer method. The lang team discussed this and decided that this may be unnecessary abstraction, since its not obvious how important it is to share these details at the trait level (NB. one can still share the code itself if a type impls both BoxPlace and InPlace and since one can, say, call one pointer(&mut self) -> *mut T method from the other).

Placer blanket impl

The Placer:(InPlace+Place) relationship is very similar to the IntoIterator:Iterator one: The former is designed to convert into the later so that one can use in (respectively for & iterator adaptors/consumers) with things that aren't directly InPlaces (e.g. in vec { elem }/vec <- elem) or Iterator (e.g. for _ in &[1, 2, 3]). IntoIterator has a blanket impl

impl<I> IntoIterator for I where I: Iterator {
     type Item = I::Item;
     type IntoIter = I;
     fn into_iter(self) -> I { self }
}

which means that all Iterators can be transparently used in places that expect IntoIterator, without the creator of the Iterator having to remember or write anything more.

It'd be interesting if a similar thing could happen with Placer and InPlace, i.e. have:

impl<Data, P> Placer<Data> for P where P: InPlace<Data> {
    type Place = P;
    fn make_place(self) -> P { self }
}

However this hits a coherence error, #28881.

(Combined with merging Place and InPlace, this would mean creating many Placers would only require implementing a single trait, InPlace, rather than the 3 it does today.)

Fallible placement

Handling fallible placement allocations is a little idiosyncratic, but seems possible, by handling failure in in X { Y } (aka X <- Y) when creating X itself, not by having the whole expression return a Result to indicate problems.

I find this a little unintuitive for both implementers and users. For implementers, one is basically forced to do the allocation immediately when creating the Placer, and then pass through the pointer (i.e. Placer::make_place and Place::pointer just return an already-created value), making the layers of traits seems a bit strange. For users, it feels more natural to have X <- Y return Result<_, _>, but only when X is something that can fail, which possibly requires HKTs to encode (and may not be worth it).

The broad thoughts was that this wasn't that strange, and that it won't come up that often (i.e. heavily biased toward OS/embedded development), but that it's very nice that there is some possibility to write this.

This is a version of Box that supports placement in and allows allocation failures to be recovered from (people may be most interested in the main/func example at the start, and/or how the procotol is implemented after that; the details of MyBox itself at the end aren't so important):

#![feature(placement_in_syntax, placement_new_protocol)]

fn main() {
    let x: Result<_, _> = MyBox::place().map(|p| in p { 1 }); // ....map(|p| p <- 1)
    // with `try { ... ? ... }` this could also be:
    // let x = try { in MyBox::place()? { 1 } }; // ... try { MyBoxPlace()? <- 1 };
    println!("{}", *x.unwrap());

    println!("{}", *func(2).unwrap());
}

fn func(val: i32) -> Result<MyBox<i32>, BadAlloc> {
    let mut x = in try!(MyBox::place()) { val }; // ... try!(MyBox::place()) <- val
    *x += 10;
    Ok(x)
}

// implementation of the `in`  procotol:

pub struct MyBoxPlace<T> {
    ptr: *mut T
}
#[derive(Debug)]
pub struct BadAlloc;

impl<T> MyBox<T> {
    pub fn place() -> Result<MyBoxPlace<T>, BadAlloc> {
        let p = unsafe {malloc(mem::size_of::<T>())};
        if p.is_null() {
            Err(BadAlloc)
        } else {
            Ok(MyBoxPlace { ptr: p as *mut T })
        }
    }
}
impl<T> ops::Placer<T> for MyBoxPlace<T> {
    type Place = Self;
    fn make_place(self) -> Self { self }
}
impl<T> ops::Place<T> for MyBoxPlace<T> {
    fn pointer(&mut self) -> *mut T { self.ptr }
}

impl<T> ops::InPlace<T> for MyBoxPlace<T> {
    type Owner = MyBox<T>;
    unsafe fn finalize(self) -> MyBox<T> {
        let p = self.ptr as *const T;
        mem::forget(self);
        MyBox { ptr: p }   
    }
}
impl<T> Drop for MyBoxPlace<T> {
    fn drop(&mut self) {
        unsafe {
            free(self.ptr as *mut u8);
        }
    }
}


// implementation of the pointer itself

use std::{mem, ops, ptr};

extern {
    fn malloc(x: usize) -> *mut u8;
    fn free(p: *mut u8);
}

/// Custom `Box`
pub struct MyBox<T> {
    ptr: *const T
}

// make `MyBox` behave like a pointer
impl<T> ops::Deref for MyBox<T> {
    type Target = T;
    fn deref(&self) -> &T {
        unsafe {&*self.ptr}    
    }
}
impl<T> ops::DerefMut for MyBox<T> {
    fn deref_mut(&mut self) -> &mut T {
        unsafe {&mut *(self.ptr as *mut T)}
    }
}
// etc.

impl<T> Drop for MyBox<T> {
    fn drop(&mut self) {
        unsafe {
            drop(ptr::read(self.ptr));
            free(self.ptr as *mut u8);
        }
    }
}

[briansmith]

How would this handle this use case? This is trying to create a way to store any instance of a trait T in a way that they can be copied around, without knowing anything about the concrete type except that it implements the T trait and that the concrete type is small enough to fit in the buffer.

const MAX_SIZE: usize = 128;

struct StaticBox<T> {
  buffer: [u8; MAX_SIZE]
}

impl StaticBox<T> {
  fn as_ref(&self) -> &T {
    // We know an instance of T has been allocated in self.buffer, but
    // how do we get it out?
    unimplemented!();
  }
}

trait T {
  fn new() -> T;
  fn do_something(&self);
}

struct A { a: u8 }
impl T for A {
  fn new() { A { a: 1 } }
  fn do_something() { unimplemented!() }
}

struct B { b: [u64; 8] }
impl T for B {
  fn new() { B { b: [0; 8] } }
  fn do_something() { unimplemented!() }
}

fn create_and_return_a_T() -> StaticBox<T> {
  let x: StaticBox<T> = unimplemented!(); // initialize an instance of `A` inside |x|.
  x
}

fn main() {
  let a = create_and_return_a_T();
  let b: &T = a.as_ref();
}

[arielb1]

@briansmith

I imagine you would want an array of u64 - for alignment - instead of an array of u8. Anyway, I don't think there is a safe way of doing this (do we have a placer impl for raw pointers?)

[huonw]

cc rust-lang/rfcs#1286

[pnkfelix]

FYI draft of FAQ here https://internals.rust-lang.org/t/placemet-nwbi-faq-new-box-in-left-arrow/2789

[petrochenkov]

Q(9). Which stdlib datatypes currently support placement-in?
A. None, currently. 😄
We are still finalizing the protocol API and have not added Placer support to any of the standard library types.

I still think it's important to have placement insertion for basic collections (Vec and HashMap) implemented, tested and benchmarked (!) before finalizing the protocol. Fewer chances to do something wrong this way.
In particular we need to make sure that performance doesn't regress on small types (~pointer sized) compared to non-placement insertion (by marking the new code for exceptional case as cold or something like that?).

[pnkfelix]

@petrochenkov I don't think I have ever suggested stabilizing the protocol before it has been implemented for all the collection types that we can think of. :) (Feel free to point out where I may have misled...)

[pnkfelix]

@petrochenkov but I can see how the answer written there can be misinterpreted.

I'll try to change that specific text; for the most part, I hope that discussion about the FAQ itself can be restricted to that internals thread.

[comex]

(I started writing the following as a comment on the FAQ thread on internals, before I saw it was partially addressed here, but I'll post it in full anyway...)

So why does the placer protocol need two types/traits? As I understand it, a method like "emplace_back" would normally return basically a wrapper object with a reference to the container in question; Rust would then call make_place(), whose implementation would actually reserve space in the container, returning a Place which could then be finalize()d (or else dropped normally if the expression on the right of the <- panicked). But why not cut out the middle operation and have emplace_back() itself do the allocation and return a Place, which <- would accept on the left instead of a Placer?

One drawback would be that global allocators would have to look like heap() <- foo rather than HEAP <- foo. But the former arguably looks better anyway due to not being in all caps, and more importantly, this removes an important asymmetry when it comes to fallible allocators:

Fallible allocators (i.e. allocators that can fail without panicking) cannot implement Placer the expected way, where the make_place implementation is what does the actual grunt work of allocation, because of course there is no way to tell the compiler to stop before writing data in. This could be worked around in the Placer protocol itself, e.g. by having make_place return a Result<Self::Place, Self::Place::Owner> (where if it returned Err(owner), the <- expression would evaluate to owner without evaluating the right hand side), but that would be both complicated and really weird, since the syntax would have no indication that the right hand side could sometimes just not be evaluated.

In lieu of that, such allocators would have to allocate before returning a Placer, so the Placer would just be a wrapper around a Place. e.g. fn fallible_alloc<T>() -> Result<Placer<T>, ()>, and then user code would typically look like try!(fallible_alloc()) <- expr, which is not bad at all and makes the control flow divergence more explicit.

Which is fine, but means that the ability to use constants as Placers which, as far as I can tell, is the only advantage of having a separate Placer trait, does not work for fallible allocators, creating the aforementioned asymmetry. Since it's not a very big advantage and often results in unnecessary wrapper object juggling anyway, it seems to me more sensible to get rid of it.

...this is the point where I stopped writing, and now I see that the question of allowing Placers to fail has been touched on above, and one additional advantage of having a separate Placer is mentioned - that you can have short forms like vec <- elem rather than needing an explicit emplace method (however named). This is something, but I'm not convinced it's worth it personally, so I maintain the conclusion of the last paragraph.

(Sidenote - even if Rust's standard library doesn't care to deal with allocation failure, when it comes to the language itself, Rust's use of explicit option types rather than null pointers should make safety in the presence of allocation failure considerably easier than in C. Just saying.)

[Stebalien]

@huonw, are the following traits not sufficient to reduce trait proliferation?

trait Placer<Data: ?Sized> {
    type Place: Place<Data>;
    fn make_place(&mut self) -> Self::Place;
}

unsafe trait Place<Data: ?Sized> {
    type Owner;
    fn pointer(&mut self) -> *mut Data;
    unsafe fn finalize(self) -> Self::Owner;
}

trait Boxer<Data: ?Sized>: Sized {
    type Place: Place<Data, Owner=Self>;
    fn make_place() -> Self::Place;
}

impl<T> Boxer<T> for Box<T> { /* ... */ }

impl<T> Place<T> for IntermediateBox<T> { /* ... */ }

[pcwalton]

Wanted for WebRender.

[bstrie]

Should the stabilization of box_syntax or the design of placement new affect box_patterns (#29641)? Wondering if that gate should be tracked in this issue as well.

[pnkfelix]

Status update: https://internals.rust-lang.org/t/lang-team-minutes-feature-status-report-placement-in-and-box/4646

[scottjmaddox]

Would it be possible to just avoid all the issues brought up with placement syntax and provide a ptr::write like intrinsic that allowed directly writing a static Struct to a pointer as a stop-gap solution? As is, Rust does not really support large structs, because they're always allocated on the stack before writing, resulting in stack overflows. This would fill the basic need, while leaving all the other questions until later.

[aidanhs]

Placement new is imminently about to be/has been removed as an unstable feature and the RFCs unaccepted. The approved/merged PR is at #48333 and the tracking issues were at #22181 and #27779 (this issue). Note that this does not affect box syntax - there is a new tracking issue for that at #49733.

Find the internals thread where you can discuss this more at https://internals.rust-lang.org/t/removal-of-all-unstable-placement-features/7223. Please add any thoughts there. This is the summary comment.

So why remove placement?

The implementation does not fulfil the design goals

As described in rust-lang/rfcs#470 (referred to by the accepted rust-lang/rfcs#809), the implementation of placement new should

Add user-defined placement in expression (more succinctly, "an in expression"), an operator analogous to "placement new" in C++. This provides a way for a user to specify (1.) how the backing storage for some datum should be allocated, (2.) that the allocation should be ordered before the evaluation of the datum, and (3.) that the datum should preferably be stored directly into the backing storage (rather than allocating temporary storage on the stack and then copying the datum from the stack into the backing storage).

The summarised goals (from the same RFC text) are to be able to:

1. Place an object at a specific address (references the original C++ goals)
2. Allocate objects in arenas (references the original C++ goals)
3. Be competitive with the implementation in C++

Now consider the description of C++ behaviour in https://isocpp.org/wiki/faq/dtors#placement-new and note that during construction, the this pointer will point to the allocated location, so that all fields are assigned directly to the allocated location. It follows that we must provide similar guarantees to achive goal 3 (be competitive with C++), so the "preferably" in the implementation description is not strong enough - it is actually necessary.

Unfortunately, it is easy to show that rust does not construct objects directly into the allocation in debug mode. This is an artificially simple case that uses a struct literal rather than the very common Rust pattern of 'return value construction' (most new functions).

It appears that the current implementation cannot competitive with C++ placement as-is. A new RFC might either propose different guarantees, or describe how the implementation should work given the very different method of construction in Rust (compared to C++). Straw man: "A call to a fn() -> T can be satisfied by a fn(&uninit T) function of the same name (allowing you to assign fields directly in the function body via the uninit reference)".

The functionality of placement is unpredictable

As described by the C++ goals for placement (mentioned above), placement is typically used because you need to have explicit control over the location an object is put at. We saw above that Rust fails in very simple cases, but even if it didn't there is a more general issue - there is no feedback to the user whether placement is actually working. For example, there is no way for a user to tell that linkedlist.back_place() <- [0u8; 10*1024*1024] is placed but linkedlist.back_place() <- [[0u8; 10*1024*1024]] is not.

Effectively, placement as implemented today is a 'slightly-better-effort to place values than normal assignment'. For an API that aims to offer additional control, this unpredictability is a significant problem. A new RFC might provide either provide clear guidance and documentation on what placement is guaranteed, or require that compilation will fail if a requested placement cannot succeed. Straw man 1: "Placement only works for arrays of bytes. Function calls (e.g. serde or anything with fallible creation) and DSTs will not work". Straw man 2: "If a same-name fn(&uninit T) does not exist for the fn() -> T call being placed, compilation will fail".

Specific unresolved questions

There are a number of specific unresolved questions around the RFC(s), but there has been effectively no design work for about 2 years. These include (some already covered above):

• making placement work for serde/with fallible creation [5], [irlo2], [7]
• 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] rust-lang/rfcs#470
[1] rust-lang/rfcs#809 (comment)
[2] rust-lang/rfcs#1286
[3] rust-lang/rfcs#1315
[4] #27779 (comment)
[5] #27779 (comment)
[6] #27779 (comment)
[7] rust-lang/rfcs#1228 (comment)
[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

I've opted to list these rather than going into detail, as they're generally covered comprehensively by the corresponding links. A future RFC might examine these points to identify areas to explictly address, including (in no particular order):

• does the new RFC support DSTs? serde and fallible creation?
• does the new RFC have a lot of traits? Is it justified?
• can the new RFC handle cases where allocation fails? Does this align with wider language plans (if any) for fallible allocation?
• are there upcoming/potential language features that could affect the design of the new RFC? e.g. custom allocators, NoMove, HKTs? What would the implications be?

[aidanhs]

@scottjmaddox I responded to you on the internals thread - https://internals.rust-lang.org/t/removal-of-all-unstable-placement-features/7223/2.

[aidanhs]

Closing since the unaccepting PR has been merged.

[abonander]

@aidanhs this is the tracking RFC for box_syntax as well, according to the Unstable Book.

[aidanhs]

@abonander good point. I've created a new tracking issue for just box syntax, updated my summary comment above and made a post on the thread in the internals forum.

[kennytm]

@aidanhs You'll need to update the tracking issue number in the Rust source as well.

[est31]

@kennytm I've filed PR #51066 for this

[Kixunil]

@aidanhs thank you for the summary! I've finally understood it well.