How `box` should work

[glaebhoerl]

We need to come up with a final design for how the box operator should work.

Here is what I personally think would be ideal; unfortunately it involves features which are not yet part of the language.

// just to avoid a name clash with existing `Box`, otherwise the name is up for grabs
trait MakeBox {
    type Where = ();
    fn make_box<'s, T>(self: &'s out Self<T>, wherein: Where) -> &'s out T;
}

The box operator would desugar to a call to make_box (see below). If a value-level argument is required to specify where the box should be allocated, such as for arenas (i.e. box(here) val syntax), its type is specified by the Where associated type. Most of the time this defaults to (). MakeBox itself is a higher-kinded trait, implemented for the generic box type itself. (So if you have impl MakeBox for SomeBox, val: T, then e.g. box val: SomeBox<T>.)

make_box relies on &out references such as described by RFC PR 98 (see also the comments), which is a reference type which points to an uninitialized value and represents the obligation to initialize it. make_box takes as argument the obligation to initialize a box, e.g. a SomeBox<T>, allocates the box itself, and returns to the caller the obligation to initialize the contained value.

We would have impls such as:

impl MakeBox for Box { ... }
impl MakeBox for Rc  { ... }
impl MakeBox for Gc  { ... }

struct Arena { ... }
struct ArenaRef<'s, T> { ... }

impl<'s> MakeBox for ArenaRef<'s, ..> { // partial type application
    type Where = &'s mut Arena;
    ...
}

Given an expression:

box(here) foo

• The type of the resulting box is determined by inference (as with e.g. from_string()).
• The type of the expression is SomeBox<Foo>, where foo: Foo, SomeBox: MakeBox, and here: <SomeBox as MakeBox>::Where.
• If here is omitted, it defaults to (), so box foo becomes box(()) foo.
• If it is unconstrained, the box type could potentially default to Box.
• To specify the desired box type manually, when it can't be inferred from the context, use type ascription and a type wildcard. Currently, this means e.g. let rc_foo: Rc<_> = box foo;. When we gain general type ascription syntax, it could instead be box foo: Rc<_>. (In each case the result type is Rc<Foo>.)

This latter point is why it is important for the trait to be higher-kinded. If the trait is higher-kinded, it is sufficient to annotate the outer type (the box type), and the type argument can be inferred, because it is the same as the type of the value being boxed. If MakeBox were formulated using an associated type instead, as e.g. Deref, then the type ascription would be required to specify the full type, including the type of the contained value.

Finally, given the above expression:

box(here) foo

This would desugar to:

{
    let the_box;
    *the_box.make_box(here) = foo;
    the_box
}

The second line initializes the_box using make_box, and then initializes the contained value with foo. (foo here is an arbitrary expression, not necessarily a variable.)

[thestinger]

It has to clean up allocated resources if result_expression in box (place_expression) result_expression throws an exception. It also needs to support in-place constructor in collections via various methods like emplace_front and emplace_back on std::deque in C++.

[glaebhoerl]

emplace_back could be expressed straightforwardly using &out without even involving box:

fn emplace_back<'s, T>(self: &'s mut Vec<T>) -> &'s out T;

[pnkfelix]

see also alternative design (needs RFC) with prototype at Rust PR 18233: rust-lang/rust/pull/18233

[pnkfelix]

(in particular, any design needs to ensure that it handles failure of the <value-expr> in box (<place-expr>) <value-expr> properly; I think the description outlined in this issue is relying on &out doing the cleanup on failure automatically, but I'm not sure that design works out once we get rid of drop flags...)

(ah, apologies to @thestinger who said much the same thing a few comments up.)

[arielb1]

@pnkfelix

&out pointers are linear, and therefore don't work well with unwinding, as there is no correct destructor for the &out T when you don't have a T, so locals can't be linear.

Something like:

trait AllocHole<'a, out T> {
  // associated field. const associated fields can't be assigned to,
  // but writing to an &out associated field destroys its owner (this
  // doesn't work with trait objects).
  const internals: &'a out T 
}

// fundep version. replace out parameters with associated types for 
trait Allocator<'a, T, PLACE, out HOLE> where HOLE : AllocHole<'a, T>, PLACE: Copy {
    fn alloc(&'a out self, p: PLACE) -> HOLE;
}

// We may need some hacks to convince typeck
// that Box<#[generic j]> impls Allocator<#[generic j], (), ...>
impl<'a, T> Allocator<T, (), BoxHole<'a, T>> for Box<T>
    fn alloc(&'a out self, p: ()) -> BoxHole<'a, T> {
        unsafe {
            let ptr = malloc::<T>();
            *self = Box(ptr);
            BoxHole(transmute(ptr))
        }
    }
}

struct BoxHole<'a, T>(&'a out T);

impl<'a, T> Drop for BoxHole<'a, T> {
  fn drop(&mut self) {
    unsafe { free::<T>(transmute(self.0)); }
  }
}

// box(PLACE) EXPR should translate to
// {
//     let mut result;
//     let mut hole = (&out result).alloc(PLACE);
//     *hole = EXPR;
//     result
// }

We would need some kind of linear types and constant linear associated types, but it could work.

I don't think my proposal requires typeck hacks/HKT/whatever, because the following code,
which is pretty similar, works today:

trait MyTrait<T, P> {
  fn work(&mut self, p: P, t: T);
}

impl<T> MyTrait<T, ()> for Option<T> {
  fn work(&mut self, _: (), _: T) {}
}

fn main() {
  let mut o = None;
  o.work((), 0u);
  println!("{}", o);
}

Of course, to be generic over allocators, one still needs HKT, Π₂TB, or Π₁TB + Associated Types.

[Noratrieb]

i have an idea for how it should work: not