Could type inference insert coercions to accommodate box desugaring?

[pnkfelix]

The problem here was previously documented as a drawback in rust-lang/rfcs#809 (with similar details provided in Appendix B).

Demonstration code:

#![feature(box_syntax)]

// NOTE: Scroll down to "START HERE"

fn main() { }

macro_rules! box_ {
    ($value:expr) => { {
        let mut place = ::BoxPlace::make();
        let raw_place = ::Place::pointer(&mut place);
        let value = $value;
        unsafe { ::std::ptr::write(raw_place, value); ::Boxed::fin(place) }
    } }
}

pub trait BoxPlace<Data> : Place<Data> { fn make() -> Self; }
pub trait Place<Data: ?Sized> { fn pointer(&mut self) -> *mut Data; }
pub trait Boxed<CoercedFrom> { type Place; fn fin(filled: Self::Place) -> Self; }

struct BP<T: ?Sized> { _fake_box: Option<Box<T>> }

impl<T> BoxPlace<T> for BP<T> {
    fn make() -> BP<T> { make_pl() }
}
impl<T: ?Sized> Place<T> for BP<T> {
    fn pointer(&mut self) -> *mut T { pointer(self) }
}
impl<T> Boxed<T> for Box<T> {
    type Place = BP<T>;
    fn fin(x: BP<T>) -> Self { finaliz(x) }
}

fn make_pl<T>() -> BP<T> { loop { } }
fn finaliz<T: ?Sized, CoercedFrom>(mut _filled: BP<CoercedFrom>) -> Box<T> { loop { } }
fn pointer<T: ?Sized>(_p: &mut BP<T>) -> *mut T { loop { } }

// START HERE

trait D1 { fn duh() -> Self; }
trait D2 { fn duh() -> Self; }
trait D3 { fn duh() -> Self; }
trait D4 { fn duh() -> Self; }
trait D5 { fn duh() -> Self; }
trait D6 { fn duh() -> Self; }
trait D7 { fn duh() -> Self; }

// THIS WORKS TODAY (pre box desugaring).
impl<T> D1 for Box<[T]> { fn duh() -> Box<[T]> { box [] } }

// D2/D3/D4/D5 WORK TOMORROW (they accommodate the box desugaring).
impl<T> D2 for Box<[T]> {
    fn duh() -> Box<[T]> { let b: Box<[_; 0]> =  box_!( [] ); b }
}
impl<T> D3 for Box<[T]> {
    fn duh() -> Box<[T]> { (|b| -> Box<[_; 0]> { b })(box_!( [] )) }
}
impl<T> D4 for Box<[T]> {
    fn duh() -> Box<[T]> { (|b: Box<[_; 0]>| { b })(box_!( [] )) }
}
fn the<X>(x:X) -> X { x }
impl<T> D5 for Box<[T]> {
    fn duh() -> Box<[T]> { the::<Box<[_; 0]>>(box_!( [] )) }
}

// BUT: D6 and D7 do not work.

impl<T> D6 for Box<[T]> { fn duh() -> Box<[T]> { box_!([]) } }

impl<T> D7 for Box<[T]> {
    // fn duh() -> Box<[T]> { box_!( [] ) }
    //
    // desugars to:
    fn duh() -> Box<[T]> {
        let mut place = ::BoxPlace::make();
        let raw_place = ::Place::pointer(&mut place);
        let value = [];
        unsafe { ::std::ptr::write(raw_place, value);
                 ::Boxed::fin(place) }
    }
}

The question posed by this issue is: Could we enhance the type inference and/or the design of this protocol so that, by tracking the sized-ness of the type unification variables, we could determine where coercions need to be inserted.

[pnkfelix]

cc #22181

[pnkfelix]

Also, we made some progress on a similar problem back in December thanks to @eddyb's PR #20083 (issue #20169); maybe the strategy there could be generalized to apply here.

[nikomatsakis]

(Just for the record: I am generally not a fan of tracking the "sizedness" of type variables because it is not something we necessarily know at the time that the type variable is created and so forth. But I'd consider it if we cannot find another solution.)

[steveklabnik]

Update: this code errors with

hello.rs:12:55: 12:67 error: the trait `core::marker::Sized` is not implemented for the type `[T]` [E0277]
hello.rs:12         unsafe { ::std::ptr::write(raw_place, value); ::Boxed::fin(place) }
                                                                  ^~~~~~~~~~~~
hello.rs:67:50: 67:59 note: in this expansion of box_! (defined in hello.rs)
hello.rs:12:55: 12:67 help: run `rustc --explain E0277` to see a detailed explanation
hello.rs:12:55: 12:67 note: `[T]` does not have a constant size known at compile-time
hello.rs:12:55: 12:67 note: required by `Boxed::fin`
hello.rs:9:25: 9:41 error: the trait `core::marker::Sized` is not implemented for the type `[T]` [E0277]
hello.rs:9         let mut place = ::BoxPlace::make();
                                   ^~~~~~~~~~~~~~~~
hello.rs:67:50: 67:59 note: in this expansion of box_! (defined in hello.rs)
hello.rs:9:25: 9:41 help: run `rustc --explain E0277` to see a detailed explanation
hello.rs:9:25: 9:41 note: `[T]` does not have a constant size known at compile-time
hello.rs:9:25: 9:41 note: required by `BoxPlace::make`
hello.rs:10:25: 10:41 error: the trait `Place<[_; 0]>` is not implemented for the type `BP<[T]>` [E0277]
hello.rs:10         let raw_place = ::Place::pointer(&mut place);
                                    ^~~~~~~~~~~~~~~~
hello.rs:67:50: 67:59 note: in this expansion of box_! (defined in hello.rs)
hello.rs:10:25: 10:41 help: run `rustc --explain E0277` to see a detailed explanation
hello.rs:10:25: 10:41 help: the following implementations were found:
hello.rs:10:25: 10:41 help:   <BP<T> as Place<T>>
hello.rs:10:25: 10:41 note: required by `Place::pointer`
hello.rs:78:18: 78:30 error: the trait `core::marker::Sized` is not implemented for the type `[T]` [E0277]
hello.rs:78                  ::Boxed::fin(place) }
                             ^~~~~~~~~~~~
hello.rs:78:18: 78:30 help: run `rustc --explain E0277` to see a detailed explanation
hello.rs:78:18: 78:30 note: `[T]` does not have a constant size known at compile-time
hello.rs:78:18: 78:30 note: required by `Boxed::fin`
hello.rs:74:25: 74:41 error: the trait `core::marker::Sized` is not implemented for the type `[T]` [E0277]
hello.rs:74         let mut place = ::BoxPlace::make();
                                    ^~~~~~~~~~~~~~~~
hello.rs:74:25: 74:41 help: run `rustc --explain E0277` to see a detailed explanation
hello.rs:74:25: 74:41 note: `[T]` does not have a constant size known at compile-time
hello.rs:74:25: 74:41 note: required by `BoxPlace::make`
hello.rs:75:25: 75:41 error: the trait `Place<[_; 0]>` is not implemented for the type `BP<[T]>` [E0277]
hello.rs:75         let raw_place = ::Place::pointer(&mut place);
                                    ^~~~~~~~~~~~~~~~
hello.rs:75:25: 75:41 help: run `rustc --explain E0277` to see a detailed explanation
hello.rs:75:25: 75:41 help: the following implementations were found:
hello.rs:75:25: 75:41 help:   <BP<T> as Place<T>>
hello.rs:75:25: 75:41 note: required by `Place::pointer`

I have no idea what's been going on with the placement syntax, so I'm not sure if this is expected or not. It seems like what @nikomatsakis is talking about.

[eddyb]

My first attempt at a solution resulted in #27292, but I now believe there is no point in desugaring to Rust code when we can handle this much better in type-checking if we know it's placement syntax and not just a bunch of function calls (see comment).