Handmade Rust Part 2: Unq, an allocator-aware Box

In the Rust standard library, Box is a RAII wrapper for an object on the heap. It’s actually a special type that’s not implemented purely in the library, but also use special features called lang items. It uses the global allocator to allocate its memory. We want a similar type that also has an allocator associated to it. We’ll call it Unq, which mirror C++’s unique_ptr.

Defining Unq

pub struct Unq<T: ?Sized, A: Allocator>
{
    ptr: NonNull<T>,
    alloc: A,
}

T is the wrapped type. It is optionally sized because we want to allow trait objects to be wrapped in there. For those unfamiliar with traits, they are basically Rust’s interfaces, but they allow both static and dynamic dispatch. A trait object is an object and its accompanying virtual functions table that allows dynamic dispatch. They use the syntax dyn Trait. For example, &mut dyn Trait and Unq<dyn Trait, A> are both trait objects.

Creating and dropping a Unq

When creating a Unq, we pass to it a value of type T and an allocator. The necessary memory is allocated. Then we can write the value using core::ptr::write, which moves a value into a potentially uninitialized memory location.

Edit 2019-03-25: I originally used forget(replace(ptr, value)) to write the value, but @myrrlyn pointed out that ptr::write is actually a better choice here because it doesn’t require initialized memory like replace does.

impl<T, A: Allocator> Unq<T, A>
{
    pub fn new(value: T, mut alloc: A) -> Self
    {
        let mut ptr = /* Allocate memory */;

        unsafe
        {
            core::ptr::write(ptr.as_mut(), value);
        }

        // ...
    }
}

Note that this means that the value first has to live on the stack before being copied to the heap. Maybe in the future we’ll implement a method to create a Unq from a type that implements Default in place.

When dropping the Unq, before deallocating the memory, we first want to drop the contained value. To do so we could use core::mem::drop, but we would first need to copy the value, which we don’t want. Instead we can use core::ptr::drop_in_place to drop the value at a given memory location.

impl<T: ?Sized, A: Allocator> Drop for Unq<T, A>
{
    fn drop(&mut self)
    {
        unsafe
        {
            drop_in_place(self.ptr.as_ptr());
            // Deallocate
        }
    }
}

Making Unq usable

We can now create a Unq, but then there is no way to access the underlying value. To do so, we’ll implement core::ops::Deref and core::ops::DerefMut. Those are basically operator overloadings that tells the compiler what to do when dereferencing a Unq. By returning self.ptr.as_ref() and self.ptr.as_mut() respectively, we allow the user to access members and methods of the wrapped object simply by writing my_unq.member = new_value; or my_unq.do_something();.

Finally, we need Unq to be able to do dynamic dispatch, so we need to tell the compiler that Unq is covariant over T, meaning that when T is a subtype of U, Unq<T> is a subtype of Unq<U>. We’ll be able to write something like this:

trait MyTrait
{
    fn do_something(&self);
}

struct MyObject;

impl MyTrait for MyObject
{
    fn do_something(&self) {}
}

fn foo()
{
    let alloc = ...;
    let my_unq : Unq<dyn MyTrait, ...> = Unq::new(MyObject{}, ...);
    my_unq.do_something();
}

Do to so, we need to implement core::ops::CoerceUnsized which is not stable (so we have to use the nightly toolchain).

impl<T: ?Sized + Unsize<U>, U: ?Sized, A: Allocator>
    CoerceUnsized<Unq<U, A>>
    for Unq<T, A> {}

In this snippet, T would be MyObject and U dyn MyTrait. T: Unsize<U> basically means that T can be seen as the dynamically sized type U. I won’t go into too much details because I’m not sure I understand all of it myself, but there are plenty of resources to learn about DSTs.

Wrap up

The current implementation of Unq is available here: fnd::unique::Unq. I’m sure we’ll have to add some stuff to it in the future, but this is the minimal implementation for now. Next time we’ll implement a growable array type. As always don’t hesitate to ping me on Twitter.

Contents