Skip to content

Instantly share code, notes, and snippets.

@Gankra
Last active October 25, 2018 14:03
Show Gist options
  • Save Gankra/b053cb4d1cb3bcaec070de89734720f7 to your computer and use it in GitHub Desktop.
Save Gankra/b053cb4d1cb3bcaec070de89734720f7 to your computer and use it in GitHub Desktop.

Raw Trait Objects 1.0

This is the sketch of a proposal for making it possible to manipulate some trait objects in stable rust.

Proposed new/stabilized API:

mod std::raw {
    /// A trait implemented by any type that is a trait object for a *single* trait.
    ///
    /// This allows generic code to constrain itself to trait-objects, and subsequently
    /// enables code to access the vtable directly and store trait-object values inline.
    ///
    /// For instance `dyn Display` implements `Trait`.
    ///
    /// Note that the restriction to one trait is a reservation for the future and *not*
    /// a guarantee. The Rust developers currently reserve the right to make multi-vtable
    /// trait objects, but this would only be useful for multi-trait trait objects like
    /// `dyn Display + Iterator`. If this desire is ever abandonned, then `dyn Display + Iterator`
    /// may implement Trait.
    ///
    /// If you wish to work with multi-trait trait objects, for now you must declare a new
    /// super-trait like `trait MyTrait: Display + Iterator { .. }`.
    pub trait Trait: ?Sized {
        /// Extracts the data and vtable pointers from a trait object.
        fn to_raw(obj: *const Self) -> TraitObject;

        /// Creates a trait object from its data and vtable pointers.
        ///
        /// Undefined Behaviour will almost certainly result if the data pointed
        /// to isn't a valid instance of the type the vtable is associated with.
        fn from_raw(obj: TraitObject) -> *const Self;
    }

    /// A wrapper for the data pointer and vtable pointer of a trait object.
    ///
    /// Note that this exact layout is not guaranteed by the language. You must use
    /// the methods on the `Trait` trait to convert between this representation and
    /// a trait object pointer.
    #[repr(C)]
    #[derive(Copy, Clone)]
    pub struct TraitObject {
        /// The data pointer of the trait object.
        pub data: *const (),
        /// The vtable pointer of the trait object.
        pub vtable: &'static Vtable,
    }

    /// The vtable for a trait object.
    ///
    /// A vtable (virtual table) represents all the necessary information to manipulate
    /// the concrete type stored inside a trait object. Notably it contains:
    ///
    /// * type size
    /// * type alignment
    /// * a pointer to the type's `drop_in_place` impl (may be a no-op for plain-old-data)
    /// * pointers to all the methods for the type's implementation of the trait
    ///
    /// Note that the first 3 are special because they're necessary to allocate, drop, 
    /// and deallocate every trait object.
    ///
    /// The layout of vtables is still unspecified, so this type is just a more-type-safe 
    /// convenience for accessing those 3 special values. Note however that `Vtable` does
    /// not actually know the trait it's associated with, indicating that, at very least,
    /// the location of `size`, `align`, and `drop_in_place` is identical for all
    /// trait object vtables in a single program.
    pub struct Vtable {
        _priv: (),
    }

    impl Vtable {
        /// Gets the size of the type associated with this vtable.
        pub fn size(&self) -> usize { ... }
        
        /// Gets the align of the type associated with this vtable. 
        pub fn align(&self) -> usize { ... }

        /// Drops the value pointed at by `data` assuming it has the type
        /// associated with this vtable.
        ///
        /// Behaviour is Undefined if the type isn't correct or the pointer
        /// is invalid to reinterpret as `&mut TheType`.
        pub unsafe fn drop_in_place(&self, data: *mut ()) { ... }
    }
}

// Example Usage (untested/uncompiled, but basic gist is there):

use std::raw::{Trait, TraitObject, Vtable};
use std::marker::PhantomData;
use std::mem;
use std::ptr;

/// A Vec of trait objects of trait `T`, where the trait objects
/// are all stored by-value inline in the buffer.
///
/// API-wise it's closer to a linked-list, since random access isn't supported.
pub struct TraitVec<T: Trait> {
    data: Vec<u8>,
    len: usize,
    _boo: PhantomData<T>,
}

impl<T: Trait> TraitVec<T> {
    pub fn push<U: Unsize<T>>(&mut self, val: U) {
        // We wrap this in a ManuallyDrop because we're going to bitwise copy
        // it into our buffer and then forget about this copy of the value.
        let val = ManuallyDrop::new(val);

        let thin_ptr: &U = &*val;
        let trait_obj: &T = thin_ptr;
        let repr = Trait::to_raw(trait_obj);

        // Note it would be slightly more effecient to push these two in one step,
        // but this is example code and I just want to get it right.
        self.push_aligned::<&'static Vtable>(&repr.vtable);
        self.push_aligned::<U>(thin_ptr);

        self.len += 1;
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn iter(&self) -> Iter<T> {
        Iter { data: self.data.as_ptr(), len: self.len, _boo: PhantomData }
    }

    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut { data: self.data.as_ptr(), len: self.len, _boo: PhantomData }
    }

    /// Pushes data, ensuring proper alignment
    fn push_aligned<U>(&mut self, data: &U) {
        unsafe {
            let size = mem::size_of::<U>();
            let align = mem::align_of::<U>();

            // Get pointer to the end of the buffer
            let base_pos = self.data.as_ptr().offset(self.data.len()) as usize;
            let new_pos = round_to_align(ptr, align);
            let idx = new_pos - base_pos;
            let new_len = idx + size;

            // Note it should technically be fine to leave this uninitialized, but
            // this is example code and I just want to get it right.
            self.data.resize(new_len, 0);

            (self.data.as_mut_ptr().offset(idx) as *mut U).copy_from_nonoverlapping(data, 1);
            self.data.set_len(new_len);
        }
    }
}


impl<T> Drop for TraitVec<T> {
    fn drop(&mut self) {
        for elem in self.iter_mut() {
            unsafe { ptr::drop_in_place(elem); }
        }
    }
}

struct Iter<'a, T: Trait + 'a> {
    data: *const u8,
    len: usize,
    _boo: PhantomData<&'a T>,
}

struct IterMut<'a, T: Trait + 'a> {
    data: *const u8,
    len: usize,
    _boo: PhantomData<&'a T>,
}

impl<'a, T: Trait + 'a> Iterator for Iter<'a, T: Trait> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            unsafe {
                align_ptr(&mut self.data, mem::align_of::<&'static Vtable>());
                let vtable: &'static Vtable = &*(self.data as *const Vtable);

                align_ptr(&mut self.data, vtable.align());
                let data = self.data as *const ();

                self.len -= 1;
                Some(&*Trait::from_raw(TraitObject { vtable, data }))
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }
}

impl<'a, T: Trait + 'a> Iterator for IterMut<'a, T: Trait> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            unsafe {
                align_ptr(&mut self.data, mem::align_of::<&'static Vtable>());
                let vtable: &'static Vtable = &*(self.data as *const Vtable);

                align_ptr(&mut self.data, vtable.align());
                let data = self.data as *const ();

                self.len -= 1;
                Some(&mut *(Trait::from_raw(TraitObject { vtable, data }) as *mut T))
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }
}

fn align_ptr(ptr: &mut *const u8, align: usize) {
    let base = (*ptr) as usize;
    let new_pos = round_to_align(base, align);
    *ptr = new_pos as *const u8;
}

/// Rounds a value to have the given alignment.
fn round_to_align(val: usize, align: usize) -> usize {
    // This can probably be rewritten to be bitmasks since align is always a power
    // of 2 but the compiler may not know that (since align may be loaded from a vtable).
    // For now modulo is used for clarity
    assert!(align.is_power_of_two());
    
    // Examples for this code:
    // * val = 9, align = 4 -- desired result = 12
    //   pre_val = 8, mod = 0, remainder = 4, result = 12
    //
    // * val = 8, align = 4 -- desired result = 8
    //   pre_val = 7, mod = 3, remainder = 1, result = 8
    //
    // * val = 11, align = 4 -- desired result = 12
    //   pre_val = 10, mod = 2, remainder = 2, result = 12

    // We subtract 1 so the case where `val` is already aligned is handled right.
    let pre_val = val - 1;
    let mod = pre_val % align;
    let remainder = align - mod;
    pre_val + remainder
}

PFAQ (probably frequently asked questions):

Why not make Vtable generic over its trait?

This would allow us to avoid even claiming that size/align/drop have a single location, but having them be in the same location is desirable to keep code size low (because all trait objects can share the code for align_of_val, size_of_val, drop_in_place. Keeping code size low is especially desirable when using trait objects, since that's part of their reason for existence. I'm unaware of any serious motivation to not have these values be at the head of the vtable.

The type-safety gains of making Vtable generic are dubious since you need to pull the type out of the aether in from_raw anyway. If you really care, you can make your own type-safe wrapper with PhantomData.

Why not have a from_raw_mut

Eh sure, I just didn't feel like it. The example code would get cleaner on a single line, I guess?

Why expose any methods on vtable

As the example demonstrates, it is necessary to be able to look up alignment to even materialize the trait object when it's stored inline with the vtable pointer. Once you've committed to align, might as well commit to the other 2 major fixed items.

Why *const ()

It's my favourite void*, shrug

Why not make Vtable partially defined

Since the fixed fields have to be a prefix, we could actually define them in the struct, but honestly it just didn't seem useful, and it felt like it would probably encourage some janky behaviours. Plus drop_in_place is more convenient as a proper method. Also this theoretically lets us still do janky packing or indirections, as long as they're computable in the same way for all trait objects?

@bjorn3
Copy link

bjorn3 commented Oct 25, 2018

    pub struct Vtable {
        _priv: (),
    }

Why not make this an extern type?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment