Rust’s unification of static and dynamic polymorphism into a single traits mechanism is one of the features that really resonate with me, coming from a C++ background. However, the rules for mixing the two, ie. the object safety rules, are much more restrictive than they need to be, so I thought an interesting discussion could be had about how they might be relaxed.
huon documents the rules here: http://huonw.github.io/blog/2015/01/object-safety/
Here’s a few ideas I’ve had for relaxing each of the current restrictions, would be great to hear feedback/new ideas/problems with my suggestions/solutions to those problems :
This is the one rule that I think needs to remain the same. Requiring a known size at compile time is by definition requiring static polymorphism. However, there may be some traits which could be relaxed to use a “RuntimeSized” bound instead of “Sized”, which would allow getting the size and alignment of a type at runtime.
This is purely a side-effect of trait objects being unsized. Niko has already mentioned that he’d like at some point to remove the restriction on passing unsized types by value, so when that happens, by-value self will no longer be an issue, although an additional thunk will be necessary to convert from the trait object to the concrete Self type.
There’s no inherit implementation difficulty here, it’s more a question of how one would specify which implementation to use. An obvious way would be to just allow calling static methods on a trait object - static methods can simply be included as part of the vtable. However, this is slightly redundant, as a trait object has both a vtable and a data pointer. Strictly speaking, only the vtable part is necessary to call a static trait method. If there was a type which stored just a vtable pointer for a particular trait (easy, since vtables always have 'static lifetime), it would be possible to call static methods without having to keep around any data as well.
Ideally this would be templated on the trait object type, so that it could safely store any valid vtable for one specific trait.
If “Self” becomes the TraitObject type, this is similar to by-value self. However, it’s also necessary to check that the runtime type of that TraitObject matches the runtime type of the “self” parameter. For simple cases, such as “Self”, or “&Self” parameters, the compiler can check that the vtables of the two trait objects match, as part of the thunk. However, this doesn’t cover uses of “Self” where the vtable is not easily accessible (such as GenericType<Self>) and introduces the potential for a panic, if the vtables don’t match, which may be surprising.
It’s possible to do smarter things given specific examples, eg. the Eq trait could handle mismatched runtime types by return false instead of panicking. If that could be generalised somehow, then it could be a good solution.
There are two approaches to this I came up with. The first is slightly more limiting (less so the more other restrictions can be lifted) and less performant, but doesn’t really require anything new, while the second is less restrictive but much more difficult to implement.
1) Monomorphise generic methods to the trait object type for each generic parameter, and use that instantiation in the vtable. This covers the common case quite well, trait methods such as “add<T: Addable>(T& arg)” become “add(Addable& arg)” in the vtable. Problems arise with more complex uses of generic params, eg. GenericType<T>, which has no direct translation to a trait object, at least not without knowing more about the semantics of GenericType<T>.
2) Properly combine static/dynamic dispatch (equivalent to allowing virtual template methods in C++) The first problem is making sure that all requried implementations are monomorphised, for example:
- Crate A declares a trait Foo with a generic method Bar<T>
- Crate B depends on A, and implements Foo for a struct Test
- Crate C depends on A, and calls Foo::Bar<T> via the Foo trait object
- Crate D depends on B and C, and passes an instance of B::Test to crate C as the trait object Foo
In this case, crate D must monomorphise the implementation of Foo::Bar for Test even though it’s only used indirectly through crate C, because when C was built it was unaware of the existence of Test. For this to work, any crate which might fullfil the role of C, must export the set of types, T which it uses to call Foo::Bar as part of its metadata, allowing crate D to handle the monomorphisation of implementations unknown to C.
To avoid generating too much code, crates should be careful to reuse monomorphisations from dependencies wherever possible, which currently is not done at all.
The second problem is how to handle vtables, when the set of monorphisations is not known when a crate is compiled.
To handle this, instead of giving generic methods a compile-time constant index into the vtable, the compiler allocates a static integer for each monomorphism of a generic method, which will contain the index. To call a generic method requires two memory reads: first read the index from the relevent static, next read the vtable entry at that index.
When compiling a crate, it calculates the best vtable layout for each trait assuming that it will be the last crate to be linked, and generates code to store the correct indices into all of the statics assuming that layout. These code blocks are all given the same symbol, so that when the crates are actually linked, the linker can merge them and keep only the last definition for that symbol. Finally, this block of code is run at initialisation time.
A similar process is used to generate code to construct the vtable - each crate generates its own method to construct the vtable for each trait containing generic methods, and the linker only keeps the one from the last crate to be linked. (This is called “linkonce” in llvm)