One of the most powerful parts of the Rust programming language¹ is the trait system. They form the basis of the generic system and polymorphic functions and types. There's an interesting use of traits, as so-called "trait objects", that allows for dynamic polymorphism and heterogeneous uses of types, which I'm going to look at in more detail over a short series of posts.

Update 2015-02-19: A lot of this document has been copied into the main book, with improvements and updates.

A simple example of a trait is this Foo. It has one method that is expected to return a String, and, in the real world, there would be some expectation about what the string would mean, but this is just a blog, so you're free to make up your own favourite meaning.

# #![allow(unused_variables)]
#fn main() {
trait Foo {
    fn method(&self) -> String;
}

#}

This can then be implemented for certain types, stating that these types satisfy whatever behaviours the trait is trying to summarise and allow polymorphism over. For example, bytes and strings are Foo, apparently:

impl Foo for u8 {
    fn method(&self) -> String { format!("u8: {}", *self) }
}
impl Foo for String {
    fn method(&self) -> String { format!("string: {}", *self) }
}

There's two basic ways to use traits to be polymorphic:

The first and most common are generic functions like fn func<T: Foo>(x: &T). These are implemented via monomorphisation, the compiler creates a specialised version of the generic function for every type used with it. This has some upsides—static dispatching of any method calls², allowing for inlining and hence usually higher performance—and some downsides—causing code bloat due to many copies of the same function existing in the binary, one for each type³.

Fortunately, there's second option if that trade-off is inappropriate, or if being required to know every type everywhere is impossible or undesirable.

let ref_to_t: &T = ...;

// `as` keyword for casting
let cast = ref_to_t as &Foo;

// using a `&T` in a place that has a known type of `&Foo` will implicitly coerce:
let coerce: &Foo = ref_to_t;

fn also_coerce(_unused: &Foo) {}
also_coerce(ref_to_t);

Let's start simple, with the runtime representation of a trait object. The std::raw module contains structs with layouts that are the same as the complicated build-in types, including trait objects:

# #![allow(unused_variables)]
#fn main() {
pub struct TraitObject {
    pub data: *mut (),
    pub vtable: *mut (),
}

#}

That is, a trait object like &Foo consists of a "data" pointer and a "vtable" pointer.

The data pointer addresses the data (of some unknown type T) that the trait object is storing, and the vtable pointer points to the vtable ("virtual method table") corresponding to the implementation of Foo for T.

A vtable is essentially a struct of function pointers, pointing to the concrete piece of machine code for each method in the implementation. A method call like trait_object.method() will retrieve the correct pointer out of the vtable and then do a dynamic call of it. For example:

struct FooVtable {
    destructor: fn(*mut ()),
    size: usize,
    align: usize,
    method: fn(*const ()) -> String,
}


// u8:

fn call_method_on_u8(x: *const ()) -> String {
    // the compiler guarantees that this function is only called
    // with `x` pointing to a u8
    let byte: &u8 = unsafe { &*(x as *const u8) };

    byte.method()
}

static Foo_for_u8_vtable: FooVtable = FooVtable {
    destructor: /* compiler magic */,
    size: 1,
    align: 1,

    // cast to a function pointer
    method: call_method_on_u8 as fn(*const ()) -> String,
};


// String:

fn call_method_on_String(x: *const ()) -> String {
    // the compiler guarantees that this function is only called
    // with `x` pointing to a String
    let string: &String = unsafe { &*(x as *const String) };

    string.method()
}

static Foo_for_String_vtable: FooVtable = FooVtable {
    destructor: /* compiler magic */,
    // values for a 64-bit computer, halve them for 32-bit ones
    size: 24,
    align: 8,

    method: call_method_on_String as fn(*const ()) -> String,
};

(The call_method_on_... functions could also be UFCS: <... as Foo>::method, but that's somewhat less clear.)

The destructor field in each vtable points to a function that will clean up any resources of the vtable's type, for u8 it is trivial, but for String it will free the memory. This is necessary for owning trait objects like Box<Foo>, which need to clean-up both the Box allocation and as well as the internal type when they go out of scope. The size and align fields store the size of the erased type, and its alignment requirements; these are essentially unused at the moment since the information is embedded in the destructor, but will be used in future, as trait objects are progressively made more flexible.

Suppose we've got some values that implement Foo, the explicit form of construction and use of Foo trait objects might look a bit like (ignoring the type mismatches: they're all just pointers anyway):

let a: String = "foo".to_string();
let x: u8 = 1;

// let b: &Foo = &a;
let b = TraitObject {
    // store the data
    data: &a,
    // store the methods
    vtable: &Foo_for_String_vtable
};

// let y: &Foo = x;
let y = TraitObject {
    // store the data
    data: &x,
    // store the methods
    vtable: &Foo_for_u8_vtable
};

// b.method();
(b.vtable.method)(b.data);

// y.method();
(y.vtable.method)(y.data);

If b or y were owning trait objects (Box<Foo>), there would be a (b.vtable.destructor)(b.data) (respectively y) call when they went out of scope.

The use of language like "fat pointer" implies that a trait object is always a pointer of some form, but why? I wrote above that

[Trait objects] are normal values and can store a value of any type that implements the given trait, where the precise type can only be known at runtime.

Rust does not put things behind a pointer by default, unlike many managed languages, so types can have different sizes. Knowing the size of the value at compile time is important for things like passing it as an argument to a function, moving it about on the stack and allocating (and deallocating) space on the heap to store it.

For Foo, we would need to have a value that could be at least either a String (24 bytes) or a u8 (1 byte), as well as any other type for which dependent crates may implement Foo (any number of bytes at all). There's no way to guarantee that this last point can work if the values are stored without a pointer, because those other types can be arbitrarily large.

Putting the value behind a pointer means the size of the value is not relevant when we are tossing a trait object around, only the size of the pointer itself.

An important piece in my story about trait objects in Rust¹ is the Sized trait, so I'm slotting in this short post between [my discussion of low-level details][previouspost] and [the post on "object safety"][nextpost].

Sized types are more flexible, since the compiler knows how to manipulate them directly: passing them directly into functions, moving them about in memory. Putting an unsized type behind a pointer effectively makes it sized. A Box trait object, like Box<Trait>, is the closest one can get to handling a trait object as a normal value; the Box ensures sizedness (at the expense of an allocation) without fundamentally changing the ownership semantics of a normal value.

The Sized trait gets some special syntax for use in bounds, at the moment: ?Sized. Such a bound is necessary because Sized is special: it is a default bound for type parameters in most positions, and so one needs some way to opt-in to a parameter not necessarily being sized.

# #![allow(unused_variables)]
#fn main() {
fn foo<T>() {} // can only be used with sized T

fn bar<T: ?Sized>() {} // can be used with both sized and unsized T

#}

This bound is particularly special because adding the ?Sized bound to a parameter T increases the number of types that can be used for T, whereas every other trait bound reduces it.

This unusual decision was chosen because of the increased flexibility of sized types, and some data (which I now can't find in the issue tracker) which indicated that most type parameters needed to be sized. That is, not having these defaults would result in many instances of T: Sized bounds in the standard library and elsewhere.

However, I believe this data did not consider using some form of inference (like lifetime elision) to try to guess when sizedness was likely to be needed, and some data Niko has been collecting apparently implies that such inference may make removing this special case significantly more palatable. (It may or may not be so palatable so as to be worth the breaking change...)

[whypointers]: {% post_url 2015-01-10-peeking-inside-trait-objects %}#why-pointers [dst]: http://smallcultfollowing.com/babysteps/blog/2014/01/05/dst-take-5/

A trait object in Rust¹ can only be constructed out of traits that satisfy certain restrictions, which are collectively called "object safety". This object safety can appear to be a needless restriction at first, I'll try to give a deeper understanding into why it exists and related compiler behaviour.

[previouspost]: {% post_url 2015-01-10-peeking-inside-trait-objects %} [sizedpost]: {% post_url 2015-01-12-the-sized-trait %}

This is the second (and a half) in a short series of articles on trait objects. The first one---[Peeking inside Trait Objects][previouspost]---set the scene by looking into the low-level implementation details of trait objects, and the first-and-a-half-th---[an interlude about Sized][sizedpost]---looked at the special Sized trait. I strongly recommended at least glancing over it to be familiar with trait objects, vtables and Sized, since this post builds on those concepts.

The notion of object safety was introduced in RFC 255, with the motivation that one should be able to use the dynamic trait object types Foo (as a type) in more places where a "static" Foo (as a trait) generic is expected. In a sense, it is bringing the two uses of traits---static dispatch and dynamic dispatch---closer together, reducing special handling in the language.

The high-level behaviour/restriction imposed by that RFC is: a trait object---&Foo, &mut Foo, etc.---can only be made out of a trait Foo if Foo is object safe. This section will focus on borrowed & trait objects, but what is said applies to any.

Let's look at an example of the things object safety enables: if we have a trait Foo and a function like

fn func<T: Foo + ?Sized>(x: &T) { ... }

It would be nice to be able to call it like func(object) where object: &Foo; that is, take T to be the dynamically sized type Foo. As you might guess from the context, it is not possible to do this without some notion of object safety: the arbitrary piece of code ... can do bad (uncontrolled) things.

Take it on faith (for a few paragraphs) that calling a generic method is one example of something that can't be done on a trait object. So, let's define a trait and a function like:

trait Bad {
    fn generic_method<A>(&self, value: A);
}

fn func<T: Bad + ?Sized>(x: &T) {
    x.generic_method("foo"); // A = &str
    x.generic_method(1_u8); // A = u8
}

The function func can't be called like foo(obj) where obj is a trait object &Bad because the generic method calls are illegal. There's a possible approaches here, like

1. have signatures like <T: Foo + ?Sized>(x: &T) not work with T = Foo by default, for any trait Foo,
2. check the body of the function to see if it is legal to have T = Bad when we ask for that, or
3. ensure that we can never pass a &Bad into func.

Approach 1 is what existed before object safety, and is what object safety was designed to solve. Approach 2 violates Rust's goal of needing to know only the signatures of any function/method called to type-check a program. That is, if one satisfies the signature one can call it, unlike C++, there's no need to type-check internal code of each the actual instantiation of a generic because the signatures guarantee that the internals will be legal.

Approach 3 is the one that Rust takes via object safety, by ensuring that it is impossible to ever encounter a scenario in which a function with signature fn func<T: Foo + ?Sized>(x: &T) that does bad things, could have T == Foo. That is, make it so that the only way that a &Foo can be created is if there's no way that func can misbehave.

Object safety and those sort of function signatures apply particularly to UFCS (uniform function call syntax), which allows one to call methods as normal, generic function scoped under the type/trait in which they are defined, for example, the UFCS function Bad::generic_method from the trait above effectively has signature:

fn Bad::generic_method<Self: Bad + ?Sized, A>(self: &Self, x: A)

If fn method(&self) comes from a trait Foo, x.method() can always be rewritten to Foo::method(x) (modulo auto-deref and auto-ref, which possibly add an & and/or some number of *s), however, without object safety, it may not be possible to write trait_object.method() as Foo::method(trait_object). Object safety guarantees this transformation is always valid---making UFCS and method calls essentially equivalent---by outlawing creating a trait object in situations where it would be invalid.

After RFC 546 and PR 20341, making trait objects automatically work with those sort of generic functions is achieved by effectively having the compiler implicitly create an implementation of Foo (as a trait) for Foo (as a type). Each method of the trait is implemented to call into the corresponding method in the vtable. In the explicit notation of [my previous post][previouspost], the situation might look something like:

trait Foo {
    fn method1(&self);
    fn method2(&mut self, x: i32, y: String) -> usize;
}

// autogenerated impl
impl<'a> Foo for Foo+'a {
    fn method1(&self) {
        // `self` is an `&Foo` trait object.

        // load the right function pointer and call it with the opaque data pointer
        (self.vtable.method1)(self.data)
    }
    fn method2(&mut self, x: i32, y: String) -> usize {
        // `self` is an `&mut Foo` trait object

        // as above, passing along the other arguments
        (self.vtable.method2)(self.data, x, y)
    }
}

To be clear: the .vtable and .data notation doesn't work directly on trait objects, so that code has no hope of compiling, I am just being explicit about actual behaviour.

The rules for object safety were set-out in that initial RFC 255, with two missed cases identified and resolved in RFC 428 and RFC 546. At the time of writing, the possible ways to be object-unsafe are described by two enums:

pub enum ObjectSafetyViolation<'tcx> {
    /// Self : Sized declared on the trait
    SizedSelf,

    /// Method has someting illegal
    Method(Rc<ty::Method<'tcx>>, MethodViolationCode),
}

/// Reasons a method might not be object-safe.
#[derive(Copy,Clone,Show)]
pub enum MethodViolationCode {
    /// e.g., `fn(self)`
    ByValueSelf,

    /// e.g., `fn foo()`
    StaticMethod,

    /// e.g., `fn foo(&self, x: Self)` or `fn foo(&self) -> Self`
    ReferencesSelf,

    /// e.g., `fn foo<A>()`
    Generic,
}

Let's go through each case.

Update 2015-05-06: RFC 817 added more precise control over object safety via where clauses, see [Where Self Meets Sized: Revisiting Object Safety][whereselfsized].

[whereselfsized]: {% post_url 2015-05-06-where-self-meets-sized-revisiting-object-safety %}

# #![allow(unused_variables)]
#fn main() {
trait Foo: Sized {
    fn method(&self);
}

#}

The trait Foo inherits from Sized, requiring the Self type to be sized, and hence writing impl Foo for Foo is illegal: the type Foo is not sized and doesn't implement Sized. Traits default to Self being possibly-unsized---effectively a bound Self: ?Sized---to make more traits object safe by default.

Update 2015-05-06: this is no longer object unsafe, but it is impossible to call such methods on possibly-unsized types, including trait objects. That is, one can define traits with self methods, but one is statically disallowed from call those methods on trait objects (and on generics that could be trait objects).

# #![allow(unused_variables)]
#fn main() {
trait Foo {
    fn method(self);
}

#}

At the moment⁶, it's not possible to use trait objects by-value anywhere, due to the lack of sizedness. If one were to write an impl Foo for Foo, the signature of method would mean self has type Foo: a by-value unsized type, illegal!

# #![allow(unused_variables)]
#fn main() {
trait Foo {
    fn func() -> i32;
}

#}

impl<'a> Foo for Foo+'a {
    fn func() -> i32 {
        // what goes here??
    }
}

# #![allow(unused_variables)]
#fn main() {
trait Foo {
    fn method(&self, other: &Self);
}

#}

impl<'a> Foo for Foo+'a {
    fn method(&self, other: &(Foo+'a))
        (self.vtable.method)(self.data, /* what goes here? */)
    }
}

# #![allow(unused_variables)]
#fn main() {
trait Foo {
    fn method<A>(&self, a: A);
}

#}

impl<'a> Foo for Foo+'a {
    fn method<A>(&self, a: A) {
        (self.vtable./* ... huh ???*/)(self.data, a: A)
    }
}

# #![allow(unused_variables)]
#fn main() {
trait Foo {
    fn method_u8(&self);     // A = u8
    fn method_i8(&self);     // A = i8
    fn method_String(&self); // A = String
    fn method_unit(&self);   // A = ()
    // ...
}

#}

The concept of object safety in Rust was recently refined to be more flexible in an important way: the checks can be disabled for specific methods by using where clauses to restrict them to only work when Self: Sized.

[trait-objects]: {% post_url 2015-01-10-peeking-inside-trait-objects %} sized: {% post_url 2015-01-12-the-sized-trait %} [object-safety]: {% post_url 2015-01-13-object-safety %}

This post is a rather belated fourth entry in my series on trait objects and object safety: [Peeking inside Trait Objects][trait-objects], The Sized Trait and [Object Safety][object-safety]. It's been long enough that a refresher is definitely in order, although this isn't complete coverage of the details.

Rust offers open sets of types, type erasure and dynamic dispatch via [trait objects][trait-objects]. However, to ensure a uniform handling of trait objects and non-trait objects in generic code, there are certain restrictions about exactly which traits can be used to create objects: this is [object safety][object-safety].

A trait is object safe only if the compiler can automatically implement it for itself, by implementing each method as a dynamic function call through the vtable stored in a trait object.

trait Foo {
    fn method_a(&self) -> u8;

    fn method_b(&self, x: f32) -> String;
}

// automatically inserted by the compiler
impl<'a> Foo for Foo+'a {
    fn method_a(&self) -> u8 {
         // dynamic dispatch to `method_a` of erased type
         self.method_a()
    }
    fn method_b(&self, x: f32) -> String {
         // as above
         self.method_b(x)
    }
}

Without the object safety rules one can write functions with type signatures satisfied by trait objects, where the internals make it impossible to actually use with trait objects. However, Rust tries to ensure that this can't happen---code should only need to know the signatures of anything it calls, not the internals---and hence object safety.

These rules outlaw creating trait objects of, for example, traits with generic methods:

trait Bar {
    fn bad<T>(&self, x: T);
}

impl Bar for u8 {
    fn bad<T>(&self, _: T) {}
}

fn main() {
    &1_u8 as &Bar;
}

/*
...:10:5: 10:7 error: cannot convert to a trait object because trait `Bar` is not object-safe [E0038]
...:10     &1 as &Bar;
           ^~
...:10:5: 10:7 note: method `bad` has generic type parameters
...:10     &1 as &Bar;
           ^~
*/

Trait object values always appear behind a pointer, like &SomeTrait or Box<AnotherTrait>, since the trait value "SomeTrait" itself doesn't have size known at compile time. This property is captured via the Sized trait, which is implemented for types like i32, or simple structs and enums, but not for unsized slices [T], or the plain trait types SomeTrait.

One impact of introducing object safety was that the design of several traits had to change. The most noticeable ones were Iterator, and the IO traits Read and Write (although they were probably Reader and Writer at that point).

Focusing on the former, before object safety it was defined something⁸ like:

trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;
    fn size_hint(&self) -> (usize, Option<usize>) { /* ... */ }

    // ... methods methods methods ...

    fn zip<U>(self, other: U) -> Zip<Self, U::IntoIter>
        where U: IntoIterator
    { /* ... */ }

    fn map<B, F>(self, f: F) -> Map<Self, F>
        where F: FnMut(Self::Item) -> B
    { /* ... */ }

    // etc
}

trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;

    fn size_hint(&self) -> (usize, Option<usize>) { /* ... */ }
}

trait IteratorExt: Sized + Iterator {
    // ... methods methods methods ...

    fn zip<U>(self, other: U) -> Zip<Self, U::IntoIter>
        where U: IntoIterator
    { /* ... */ }

    fn map<B, F>(self, f: F) -> Map<Self, F>
        where F: FnMut(Self::Item) -> B
    { /* ... */ }

    // etc
}
// blanket impl, for all iterators
impl<I: Iterator> IteratorExt for I {}

// make Box<...> an Iterator by deferring to the contents
impl<I: Iterator + ?Sized> Iterator for Box<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<I::Item> {
        (**self).next()
    }

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

# #![allow(unused_variables)]
#fn main() {
fn convert_to_string<T>(x: T) -> String
    where String: From<T>
{
    String::from(x)
}

#}

trait OrdIterator: Iterator {
     fn max(&mut self) -> Option<Self::Item>;
     // ...
}

impl<A: Ord, I: Iterator<Item = A>> OrdIterator for I {
    fn max(&mut self) -> Option<A> { /* ... */ }

    // ...
}

trait Iterator {
    type Item;

    // ...

    fn max(self) -> Option<Self::Item>
        where Self::Item: Ord
    { /* ... */ }

    // ...
}

struct NotOrd;

fn main() {
    (0..10).max(); // ok
    (0..10).map(|_| NotOrd).max();
}

...:5:29: 5:34 error: the trait `core::cmp::Ord` is not implemented for the type `NotOrd` [E0277]
...:5     (0..10).map(|_| NotOrd).max();

trait Bar {
    fn bad<T>(&self, x: T)
        where Self: Sized;
}

impl Bar for u8 {
    fn bad<T>(&self, _: T)
        where Self: Sized
    {}
}

fn main() {
    &1_u8 as &Bar;
}

...:13:21: 13:31 error: the trait `core::marker::Sized` is not implemented for the type `Bar` [E0277]
...:13     (&1_u8 as &Bar).bad("foo")
                           ^~~~~~~~~~
...:13:21: 13:31 note: `Bar` does not have a constant size known at compile-time
...:13     (&1_u8 as &Bar).bad("foo")
                           ^~~~~~~~~~

trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;

    fn size_hint(&self) -> (usize, Option<usize>) { /* ... */ }

    // ... methods methods methods ...

    fn zip<U>(self, other: U) -> Zip<Self, U::IntoIter>
        where Self: Sized, U: IntoIterator
    { /* ... */ }

    fn map<B, F>(self, f: F) -> Map<Self, F>
        where Self: Sized, F: FnMut(Self::Item) -> B
    { /* ... */ }

    // etc
}