Skip to content

Instantly share code, notes, and snippets.

@Ericson2314
Last active Dec 24, 2015
Embed
What would you like to do?
// Copyright 2015 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.
use std::rc::Rc;
mod protocol {
use std::ptr;
pub trait Place {
type T: ?Sized;
// NOTE(eddyb) The use of `&mut T` here is to force
// the LLVM `noalias` and `dereferenceable(sizeof(T))`
// attributes, which are required for eliding the copy
// and producing actual in-place initialization via RVO.
// Neither of those attributes are present on `*mut T`,
// but `&mut T` is not a great choice either, the proper
// way might be to add those attributes to `Unique<T>`.
unsafe fn pointer(&mut self) -> &mut Self::T;
}
pub trait Boxed: Sized{
type P: Place;
fn write_and_fin(mut place: Self::P,
value: <Self::P as Place>::T)
-> Self
where <Self::P as Place>::T: Sized
{
unsafe {
ptr::write(place.pointer(), value);
Self::fin(place)
}
}
unsafe fn fin(filled: Self::P) -> Self;
}
pub fn box_impl<S>(value: <S::P as Place>::T) -> S
where S: Boxed,
S::P: Default,
<S::P as Place>::T: Sized
{
Boxed::write_and_fin(Default::default(), value)
}
}
macro_rules! box_ {
($x:expr) => {
::protocol::box_impl($x)
}
}
// Hacky implementations of the box protocol for Box<T> and Rc<T>.
// They pass mem::uninitialized() to Box::new, and Rc::new, respectively,
// to allocate memory and will leak the allocation in case of unwinding.
mod boxed {
use std::mem;
use protocol;
pub struct Place<T: ?Sized> {
ptr: *mut T
}
impl<T> Default for Place<T> {
fn default() -> Self {
unsafe {
Place {
ptr: mem::transmute(Box::new(mem::uninitialized::<T>()))
}
}
}
}
impl<T: ?Sized> protocol::Place for Place<T> {
type T = T;
unsafe fn pointer(&mut self) -> &mut T { &mut *self.ptr }
}
impl<T: ?Sized> protocol::Boxed for Box<T> {
type P = Place<T>;
unsafe fn fin(place: Place<T>) -> Box<T> {
mem::transmute(place.ptr)
}
}
}
mod rc {
use std::mem;
use std::rc::Rc;
use protocol;
pub struct Place<T: ?Sized> {
rc_ptr: *mut (),
data_ptr: *mut T
}
impl<T> Default for Place<T> {
fn default() -> Self {
unsafe {
let rc = Rc::new(mem::uninitialized::<T>());
Place {
data_ptr: &*rc as *const _ as *mut _,
rc_ptr: mem::transmute(rc)
}
}
}
}
impl<T: ?Sized> protocol::Place for Place<T> {
type T = T;
unsafe fn pointer(&mut self) -> &mut T {
&mut *self.data_ptr
}
}
impl<T: ?Sized> protocol::Boxed for Rc<T> {
type P = Place<T>;
unsafe fn fin(place: Place<T>) -> Rc<T> {
mem::transmute(place.rc_ptr)
}
}
}
fn main() {
let /*mut*/ v = vec![1,2];
//in_!( (v.emplace_back()) 3 );
println!("v: {:?}", v);
let b4: Box<i32> = box_!( 4 );
println!("b4: {}", b4);
let b5: Rc<i32> = box_!( 5 );
println!("b5: {}", b5);
//let b6: Box<_> = in_!( (HEAP) 6 ); // return type Box<i32>
//println!("b6: {}", b6);
//let b7: Rc<_> = in_!( (HEAP) 6 ); // return type Rc<i32>
//println!("b7: {}", b7);
let v = vec![1, 2, 3];
let bx: Box<_> = box_!(|| &v);
let rc: Rc<_> = box_!(|| &v);
assert_eq!(bx(), &v);
assert_eq!(rc(), &v);
let bx_trait: Box<Fn() -> _> = box_!(|| &v);
let rc_trait: Rc<Fn() -> _> = box_!(|| &v);
assert_eq!(bx(), &v);
assert_eq!(rc(), &v);
}
//#![feature(unsafe_destructor)] // (hopefully unnecessary soon with RFC PR 769)
//#![feature(alloc)]
#![feature(box_syntax)]
// The easiest way to illustrate the desugaring is by implementing
// it with macros. So, we will use the macro `in_` for placement-`in`
// and the macro `box_` for overloaded-`box`; you should read
// `in_!( (<place-expr>) <expr> )` as if it were `in <place-expr> { <expr> }`
// and
// `box_!( <expr> )` as if it were `box <expr>`.
// The two macros have been designed to both 1. work with current Rust
// syntax (which in some cases meant avoiding certain associated-item
// syntax that currently causes the compiler to ICE) and 2. infer the
// appropriate code to run based only on either `<place-expr>` (for
// placement-`in`) or on the expected result type (for
// overloaded-`box`).
macro_rules! in_ {
(($placer:expr) $value:expr) => { {
let p = $placer;
let (a, b): ::protocol::InferenceHelp<_>;
b = ::std::marker::PhantomData;
let mut place = ::protocol::placer_make_place(b, p);
let raw_place = ::protocol::Place::pointer(&mut place);
let value = $value;
unsafe {
::std::ptr::write(raw_place, value);
a = ::protocol::Place::finalize(place)
}
a
} }
}
macro_rules! box_ {
($value:expr) => { {
let (a, b): ::protocol::InferenceHelp<_>;
b = ::std::marker::PhantomData;
let mut place = ::protocol::box_make_place(b);
let raw_place = ::protocol::Place::pointer(&mut place);
let value = $value;
unsafe {
::std::ptr::write(raw_place, value);
a = ::protocol::Place::finalize(place)
}
a
} }
}
// Ensure is actually box
macro_rules! box_just_for_Box_ {
($value:expr) => { {
let (a, b): ::protocol::InferenceHelp<Box<_>>;
b = ::std::marker::PhantomData;
let mut place = ::protocol::box_make_place(b);
let raw_place = ::protocol::Place::pointer(&mut place);
let value = $value;
unsafe {
::std::ptr::write(raw_place, value);
a = ::protocol::Place::finalize(place)
}
a
} }
}
// Note that while both desugarings are very similar, there are some
// slight differences. In particular, the placement-`in` desugaring
// uses `Place::finalize(place)`, which is a `finalize` method that
// is overloaded based on the `place` argument (the type of which is
// derived from the `<place-expr>` input); on the other hand, the
// overloaded-`box` desugaring uses `Boxed::finalize(place)`, which is
// a `finalize` method that is overloaded based on the expected return
// type. Thus, the determination of which `finalize` method to call is
// derived from different sources in the two desugarings.
// The above desugarings refer to traits in a `protocol` module; these
// are the traits that would be put into `std::ops`, and are given
// below.
mod protocol {
use std::marker::PhantomData;
/// Both `in PLACE { BLOCK }` and `box EXPR` desugar into expressions
/// that allocate an intermediate "place" that holds uninitialized
/// state. The desugaring evaluates EXPR, and writes the result at
/// the address returned by the `pointer` method of this trait.
///
/// A `Place` can be thought of as a special representation for a
/// hypothetical `&uninit` reference (which Rust cannot currently
/// express directly). That is, it represents a pointer to
/// uninitialized storage.
///
/// The client is responsible for two steps: First, initializing the
/// payload (it can access its address via `pointer`). Second,
/// converting the agent to an instance of the owning pointer, via the
/// `finalize` method.
///
/// If evaluating EXPR fails, then the destructor for the
/// implementation of Place to clean up any intermediate state
/// (e.g. deallocate box storage, pop a stack, etc).
pub unsafe trait Place<Data: ?Sized> {
/// `Owner` is the type of the end value of `in PLACE { BLOCK }`
///
/// Note that when `in PLACE { BLOCK }` is solely used for
/// side-effecting an existing data-structure,
/// e.g. `Vec::emplace_back`, then `Owner` need not carry any
/// information at all (e.g. it can be the unit type `()` in that
/// case).
type Owner;
/// Returns the address where the input value will be written.
/// Note that the data at this address is generally uninitialized,
/// and thus one should use `ptr::write` for initializing it.
fn pointer(&mut self) -> *mut Data;
/// Converts self into the final value, shifting deallocation/cleanup
/// responsibilities (if any remain), over to the returned instance of
/// `Owner` and forgetting self.
unsafe fn finalize(self) -> Self::Owner;
}
/// Interface to implementations of `in PLACE { BLOCK }`.
///
/// `in PLACE { BLOCK }` effectively desugars into:
///
/// ```
/// let p = PLACE;
/// let mut place = Placer::make_place(p);
/// let raw_place = Place::pointer(&mut place);
/// let value = { BLOCK };
/// unsafe {
/// std::ptr::write(raw_place, value);
/// Place::finalize(place)
/// }
/// ```
///
/// The type of `in PLACE { BLOCK }` is derived from the type of `PLACE`;
/// if the type of `PLACE` is `P`, then the final type of the whole
/// expression is `P::Place::Owner` (see the `Place` trait).
///
/// Values for types implementing this trait usually are transient
/// intermediate values (e.g. the return value of `Vec::emplace_back`)
/// or `Copy`, since the `make_place` method takes `self` by value.
pub trait Placer<Data: ?Sized, Owner> {
/// `Place` is the intermedate agent guarding the
/// uninitialized state for `Data`.
type Place: Place<Data, Owner=Owner>;
/// Creates a fresh place from `self`.
fn make_place(self) -> Self::Place;
}
/// For macro
pub type InferenceHelp<T> = (T, PhantomData<T>);
/// For macro
pub fn placer_make_place<P, D, O>(_: PhantomData<O>,
p: P)
-> <P as Placer<D, O>>::Place
where P: Placer<D, O>
{
p.make_place()
}
/// Core trait for the `box EXPR` form.
///
/// `box EXPR` effectively desugars into:
///
/// ```
/// let mut place = Boxer::make_place();
/// let raw_place = Place::pointer(&mut place);
/// let value = $value;
/// unsafe {
/// ::std::ptr::write(raw_place, value);
/// Place::finalize(place)
/// }
/// ```
///
/// The type of `box EXPR` is supplied from its surrounding
/// context; in the above expansion, the result type `T` is used
/// to determine which implementation of `Boxed` to use, and that
/// `<T as Boxer>` in turn dictates determines which
/// implementation of `Place` to use, namely:
/// `<<T as Boxer>::Place as Place>`.
pub trait Boxer<Data: ?Sized>: Sized
{
type Placer: Placer<Data, Self> + Default;
}
/// For macro
pub fn box_make_place<D, B>(phan: PhantomData<B>)
-> <B::Placer as Placer<D, B>>::Place
where B: Boxer<D>
{
let p: B::Placer = Default::default();
placer_make_place(phan, p)
}
} // end of `mod protocol`
// Next, we need to see sample implementations of these traits.
// First, `Box<T>` needs to support overloaded-`box`: (Note that this
// is not the desired end implementation; e.g. the `BoxPlace`
// representation here is less efficient than it could be. This is
// just meant to illustrate that an implementation *can* be made;
// i.e. that the overloading *works*.)
//
// Also, just for kicks, I am throwing in `in HEAP { <block> }` support,
// though I do not think that needs to be part of the stable libstd.
struct HEAP;
impl Default for HEAP {
fn default() -> Self { HEAP }
}
mod impl_box_for_box {
use protocol as proto;
use std::mem;
use super::HEAP;
struct BoxPlace<T> { fake_box: Option<Box<T>> }
unsafe impl<T> proto::Place<T> for BoxPlace<T> {
type Owner = Box<T>;
fn pointer(&mut self) -> *mut T {
match self.fake_box {
Some(ref mut b) => &mut **b as *mut T,
None => panic!("impossible"),
}
}
unsafe fn finalize(mut self) -> Box<T> {
let mut ret = None;
mem::swap(&mut self.fake_box, &mut ret);
ret.unwrap()
}
}
impl<'a, T> proto::Placer<T, Box<T>> for HEAP {
type Place = BoxPlace<T>;
fn make_place(self) -> BoxPlace<T> {
let t: T = unsafe { mem::zeroed() };
BoxPlace { fake_box: Some(Box::new(t)) }
}
}
impl<T> proto::Boxer<T> for Box<T> {
type Placer = HEAP;
}
}
// Second, it might be nice if `Rc<T>` supported overloaded-`box`.
//
// (Note again that this may not be the most efficient implementation;
// it is just meant to illustrate that an implementation *can* be
// made; i.e. that the overloading *works*.)
mod impl_box_for_rc {
use protocol as proto;
use std::mem;
use std::rc::Rc;
use super::HEAP;
struct RcPlace<T> { fake_box: Option<Rc<T>> }
unsafe impl<T> proto::Place<T> for RcPlace<T> {
type Owner = Rc<T>;
fn pointer(&mut self) -> *mut T {
if let Some(ref mut b) = self.fake_box {
if let Some(r) = Rc::get_mut(b) {
return r as *mut T
}
}
panic!("impossible");
}
unsafe fn finalize(mut self) -> Rc<T> {
let mut ret = None;
mem::swap(&mut self.fake_box, &mut ret);
ret.unwrap()
}
}
impl<'a, T> proto::Placer<T, Rc<T>> for HEAP {
type Place = RcPlace<T>;
fn make_place(self) -> RcPlace<T> {
let t: T = unsafe { mem::zeroed() };
RcPlace { fake_box: Some(Rc::new(t)) }
}
}
impl<T> proto::Boxer<T> for Rc<T> {
type Placer = HEAP;
}
}
// Third, we want something to demonstrate placement-`in`. Let us use
// `Vec::emplace_back` for that:
mod impl_in_for_vec_emplace_back {
use protocol as proto;
struct VecPlacer<'a, T:'a> { v: &'a mut Vec<T> }
struct VecPlace<'a, T:'a> { v: &'a mut Vec<T> }
pub trait EmplaceBack<T> { fn emplace_back(&mut self) -> VecPlacer<T>; }
impl<T> EmplaceBack<T> for Vec<T> {
fn emplace_back(&mut self) -> VecPlacer<T> { VecPlacer { v: self } }
}
impl<'a, T> proto::Placer<T, ()> for VecPlacer<'a, T> {
type Place = VecPlace<'a, T>;
fn make_place(self) -> VecPlace<'a, T> {
self.v.reserve(1);
VecPlace { v: self.v }
}
}
unsafe impl<'a, T> proto::Place<T> for VecPlace<'a, T> {
type Owner = ();
fn pointer(&mut self) -> *mut T {
unsafe {
self.v.as_mut_ptr().offset(self.v.len() as isize)
}
}
unsafe fn finalize(mut self) -> () {
// checked by reserve.
let len = self.v.len();
self.v.set_len(len + 1)
}
}
}
// Okay, that's enough for us to actually demonstrate the syntax!
// Here's our `fn main`:
fn main() {
use std::rc::Rc;
// get hacked-in `emplace_back` into scope
use impl_in_for_vec_emplace_back::EmplaceBack;
let mut v = vec![1,2];
in_!( (v.emplace_back()) 3 );
println!("v: {:?}", v);
let b4: Box<i32> = box_!( 4 );
println!("b4: {}", b4);
let b5: Rc<i32> = box_!( 5 );
println!("b5: {}", b5);
let b6: Box<_> = in_!( (HEAP) 6 ); // return type Box<i32>
println!("b6: {}", b6);
let b7: Rc<_> = in_!( (HEAP) 6 ); // return type Rc<i32>
println!("b7: {}", b7);
let v = vec![1, 2, 3];
let bx: Box<_> = box_!(|| &v);
let rc: Rc<_> = box_!(|| &v);
assert_eq!(bx(), &v);
assert_eq!(rc(), &v);
let bx_trait: Box<Fn() -> _> = box_!(|| &v);
let rc_trait: Rc<Fn() -> _> = box_!(|| &v);
assert_eq!(bx(), &v);
assert_eq!(rc(), &v);
}
// APPENDIX B
pub type BoxFn<'a> = Box<Fn() + 'a>;
//pub fn coerce0<'a, F>(f: F) -> BoxFn<'a> where F: Fn(), F: 'a { box_!( f ) }
pub fn coerce0<'a, F>(f: F) -> BoxFn<'a> where F: Fn(), F: 'a { box_just_for_Box_!( f ) }
pub fn coerce1<'a, F>(f: F) -> BoxFn<'a> where F: Fn(), F: 'a { box f }
pub fn coerce2<'a, F>(f: F) -> BoxFn<'a> where F: Fn(), F: 'a { let b: Box<_> = box_!( f ); b }
//pub fn coerce3<'a, F>(f: F) -> BoxFn<'a> where F: Fn(), F: 'a { box_!( f ) as BoxFn }
pub fn coerce3<'a, F>(f: F) -> BoxFn<'a> where F: Fn(), F: 'a { box_just_for_Box_!( f ) as BoxFn }
trait Duh0 { fn duh() -> Self; }
trait Duh1 { fn duh() -> Self; }
trait Duh2 { fn duh() -> Self; }
trait Duh3 { fn duh() -> Self; }
//impl<T> Duh0 for Box<[T]> { fn duh() -> Box<[T]> { box_!( [] ) } }
impl<T> Duh0 for Box<[T]> { fn duh() -> Box<[T]> { box_just_for_Box_!( [] ) } }
impl<T> Duh1 for Box<[T]> { fn duh() -> Box<[T]> { box [] } }
impl<T> Duh2 for Box<[T]> { fn duh() -> Box<[T]> { let b: Box<[_; 0]> = box_!( [] ); b } }
impl<T> Duh3 for Box<[T]> { fn duh() -> Box<[T]> { let b: Box<_> = box_!( [] ); b } }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment