Why are trait methods with generic type parameters object-unsafe?

Question

To quote the Book (emphasis mine),

The same is true of generic type parameters that are filled in with concrete type parameters when the trait is used: the concrete types become part of the type that implements the trait. When the type is forgotten through the use of a trait object, there is no way to know what types to fill in the generic type parameters with.

I cannot understand the rationale. For a concrete example, consider the following

pub trait Echoer {
    fn echo<T>(&self, v: T) -> T;
}

pub struct Foo { }

impl Echoer for Foo {
    fn echo<T>(&self, v: T) -> T {
        println!("v = {}", v);
        return v;
    }
}

pub fn passthrough<T>(e: Box<dyn Echoer>, v: T) {
    return e.echo(v);
}

fn main() {
    let foo = Foo { };
    passthrough(foo, 42);
}

The result is, of course, an error

$ cargo run
   Compiling gui v0.1.0 (/tmp/gui)
error[E0038]: the trait `Echoer` cannot be made into an object
  --> src/main.rs:14:27
   |
14 | pub fn passthrough<T>(e: Box<dyn Echoer>, v: T) {
   |                           ^^^^^^^^^^^^^^^ `Echoer` cannot be made into an object
   |
   = help: consider moving `echo` to another trait
note: for a trait to be "object safe" it needs to allow building a vtable to allow the call to be resolvable dynamically; for more information visit <https://doc.rust-lang.org/reference/items/traits.html#object-safety>
  --> src/main.rs:2:8
   |
1  | pub trait Echoer {
   |           ------ this trait cannot be made into an object...
2  |     fn echo<T>(&self, v: T) -> T;
   |        ^^^^ ...because method `echo` has generic type parameters

error: aborting due to previous error

For more information about this error, try `rustc --explain E0038`.
error: could not compile `gui`

To learn more, run the command again with --verbose.

From my understanding, even though e forgets about its concrete type when being cast into a trait object, it can still infer that it needs to fill the generic type parameter of echo<T> with i32, since it's called inside passthrough<T>, which is monomorphized to passthrough<i32> at compile time.

What does "the concrete types become part of the type that implements the trait" mean? Why can't trait methods fill their generic type parameters at compile time, e.g. just call echo<i32>?

Are you familiar with vtables and dynamic dispatch (which are how Rust implements trait objects)? — loganfsmyth
@loganfsmyth I'm not familiar with vtables, but I know Python and its duck typing mechanism, which I assume is conceptually close to dynamic dispatch. I mean, why can't vtables in trait objects (however they are implemented) store a pointer to a concrete method like echo<i32> (after compile time type inference)? — nalzok
Does this answer your question? Why does a generic method inside a trait require trait object to be sized? — loganfsmyth
echo can accept any T, so the vtable would have to potentially contain infinitely many possible functions, which isn't possible. Your code may only use i32, but that doesn't affect the generation of the vtable. — loganfsmyth
@loganfsmyth Thanks for the pointer. The linked question is related but doesn't fully answer my question. The accepted answer in that thread says a function/method cannot be both static- and dynamic- dispatched, but why not? At each invocation of a trait method, the concrete type is known at compile time, so the vtable only needs to store the pointers to "relevant" methods, e.g. Foo::echo<i32> and Bar::echo<i32>. (I'm assuming Rust generates a vtable for each invocation of passthrough, when concrete types are cast into trait objects) — nalzok

loganfsmyth loganfsmyth · Accepted Answer · 2021-05-31T03:33:52

This is similar to Why does a generic method inside a trait require trait object to be sized? but I'll spell out the details here.

Rust trait objects are fat pointers implemented using a vtable.

When Rust compiles code such as

pub fn passthrough<T>(e: Box<dyn Echoer>, v: T) {
    return e.echo(v);
}

it needs to decide what echo function to call. A Box is basically a pointer to value, and in the case of your code, a Foo will be stored on the heap, and a Box<Foo> would be a pointer to a Foo. If you then converted that into a Box<dyn Echoer>, the new Box actually contains two pointers, one to the Foo on the heap, and one to a vtable. This vtable is what allows Rust to know what to do when it sees the e.echo(v). The compiled output for your e.echo(v) call will look at the vtable to find the echo implementation for whatever type e points to, and then call it, in this case passing the Foo pointer for &self.

That part is easy in the case of a simple function, but the complexity and issues here comes in due to the <T> part of fn echo<T>(&self, v: T) -> T;. Template functions by their nature are aimed at declaring many functions using a single definition, but if a vtable is needed, what should it contain? If your trait contains a method that has a type parameter like <T>, where are an unknown number of T types that could be needed. That means Rust needs to either disallow vtables that reference functions with type parameters, or else it it needs to predict ahead of time every possible T type that could be needed, and include that in the vtable. Rust follows the first option and throws compiler errors like those you are seeing.

While knowing the full set of T types ahead of time may be possible in some cases, and may seem clear to a programmer working in a small codebase, it would be quite complicated and potentially make very large vtables in any non-trivial case. It would also require Rust to have full knowledge of your entire application in other to properly compile things. That could hugely slow down compile times, at a minimum.

Consider for instance that Rust generally compiles dependencies separately from your main code, and does not need to recompile your dependencies when you edit your own project's code. If you need to know all T types ahead of time to generate a vtable, you need to process all dependencies and all of your own code before deciding which T values are used and only then compile the function templates. Similarly, say that dependency contained code like the example in your question, every time you changed your own project, Rust would then have to check if your changes introduced a dynamic call to a function with a type parameter that wasn't used before, then it would also need to go recompile the dependency in order to create a new vtable with the newly referenced function as well.

At a minimum, it would introduce a ton of additional complexity.

Why are trait methods with generic type parameters object-unsafe?

2 Answers