Relaxing object safety rules


#1

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 :stuck_out_tongue: :

Sized Self

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.

By-value self

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.

Static method

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.

References Self

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.

Generic method

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)


#2

Part of the motivation for object safety is being able to call fn foo<T: Trait + ?Sized> with T = Trait, no matter what the contents of the function are.

You may also be interested in RFC 817. (Particularly for the Sized Self point.)

Unfortunately it breaks the motivation, since:

fn foo<T: Trait + ?Sized>() {
    T::static_method()
}
foo::<Trait>(); // which implementation to use for the static_method?

I don’t think we guarantee that the type-to-vtable map is injective (i.e. two types could have the same vtable), although we presumably could.

In general, this approach seems likely to lead to a lot of code-bloat: every type that is coerced to a Foo trait object needs to have Bar monomorphised and stored in the vtable for every type T that the trait object .Bar call happens with, even if the call can actually never happen. Maybe it’s not so bad in practice, but it does pretty complicated, as you say.


#3

I have a big mishmash of related thoughts you might be interested in (note: text was added at various times and is often relative to earlier versions of Rust, e.g. still has ~T for Box<T>).

The basic idea was that if a generic method over T doesn’t depend in any way on the specific representation and identity of T (only accesses T through references, among other restrictions), then alongside (or instead of) a monomorphization of the method for each type it’s statically instantiated with, it becomes possible to generate a fully polymorphic version of it, with trait bounds on T being satisfied dynamically by passing a hidden vtable argument to the method for each bound (dictionary-passing just like GHC). It then becomes possible to call the method with types whose identity is not known at compile time: if you have fn foo<T: Trait>(arg: &T) and a trait object bar: &Trait, the fully polymorphic version of foo looks something like fn _foo_generic(_Trait: *const impl Trait for (), arg: *const ()), and foo(bar) is satisfied by passing the vtable pointer from the trait object in the first arg, and the data pointer in the second.

In my plan where/whether the above is permitted was tracked in the types, with foo<ref T> being a contract between foo and its caller, which says that foo may not do anything which depends on the represention of T, and in exchange the caller may invoke foo with statically-unknown types. I’m unsure how (or whether) this could fit in with the DST-based system that we actually have today (with T: ?Sized being in some ways similar to, but likely not entirely the same as, my ref T).


#4

Right, but this is what I meant by it being a question of how to call it. For example, the following could be valid:

fn foo<T: Trait + ?Sized>(vt: VTable<T>) {
    vt.static_method()
}

foo::<Trait>(VTable::get(instance));
or
foo::<Trait>(VTable::from::<Type>());

The VTable< T > type would be equivalent to unit () for all non-trait-object T, but for trait-object types it would store the vtable for an implementation of that trait. The vtable is obtained either from an existing trait-object instance, or from a Type which implements the trait.

When all the types are known at compile-time, the vtable becomes a unit parameter, and the static method is called directly.

I think the Sized trait would still be necessary even with EQT: especially when interoperating with other code, it’s useful to know whether a type has a size which is fixed at compile-time.

Under EQT, how exactly does “ref T” differ from “T: ?Sized”, ie. what’s an example of a T which is valid under one but not the other?

Also, to make sure I’m understanding it correctly, EQT is effectively saying “Allow ref generic parameters to be specified either at runtime or compile time”, and then trait objects emerge naturally as a result of traits where “Self” is ref.


#5

Under EQT there would be no such thing as an “unsized type”. There would only be sized types and existential quantification. [T] itself would not be a type: rather &[T] would be short for something like exists const N: usize. &[T; N].

Sadly I’m not sure, because I don’t feel like I really understand DST that well. But to perhaps help clear up an implicit assumption which seems to be latent in your comment and isn’t quite right: ref T is not a restriction on T. In the context fn foo<ref T>(..., it is a restriction on foo, specifically on how it may use T. The absence of ref is a restriction on the callers of foo, in that they may not call foo with any types whose identity is not known statically (e.g. an existentially quantified type as in a trait object).

I think the case of calling fn foo<T: Trait>(arg: &T) with an &Trait as argument is helpful to think about. Under EQT this is possible if it’s declared ref T. Under DST would T: Trait + ?Sized allow this?

The last time I thought about this I think I reached the conclusion that ref applied to Self or to a trait type parameter doesn’t make sense, because this would imply that the trait doesn’t depend on the identity of Self (resp. T). But the whole point of a trait is that the chosen impl depends on the identity of the type. Instead traits can be thought of as a kind of bridge between the statically-known-types and the statically-unknown-types worlds. The impl of a trait is allowed to depend on the identity of the type being impled for precisely because any calls to a trait method for a statically-unknown type will be dispatched dynamically through the vtable to select the appropriate impl which does know which type it was statically. What we call “trait objects” and the syntax &Trait (Box<Trait>, whatever) would just be a specific case of existential quantification with runtime evidence to satisfy trait bounds.


#6

But presumably under EQT, you can still have: “exists const N: usize. [T; N]” within the type system, you just wouldn’t be able to actually use that type except via a reference? In which case, I’m failing to see any incompatibilities between DSTs and existentially qualified types. The main difference is that EQT has an explicit but general existential qualifier, whereas DSTs have an implied existential qualifier based on the kind of DST:

  • Trait (Object): qualified by Self, the type which implements the trait
  • Slice: [T]/str, qualified by the length, an integer
  • Dynamically Sized Struct: qualified by the same qualifier as its last field

A trait generic bound is effectively a trait object with it’s qualifier fixed at compile-time. Likewise, an array is a slice with its qualifier fixed at compile-time.

Your comments about “ref” are also true for ?Sized though, T: ?Sized is lifting the restriction on T that its size (in EQT terms, its identity) is known at compile-time. Similarly, it is a restriction on “foo” about how it can be used: foo can no longer do anything which requires knowing foo’s size/identity at compile-time.

As I understand it, that’s exactly how trait objects are intended to be used, by making it generic with a “Trait + ?Sized” bound, it allows the caller to choose between static and dynamic dispatch, thereby trading off performance against code size.