Idea/Pre-RFC: Runtime-erased types and reflections around object safety

[WorldSEnder]

Hello compiler community,

for me this is a sort-of first contact. If I should repost this somewhere else e.g. on zulip, call me out.

I am a maintainer over at yewstack/yew, and in the course of implementing a scheduler running updates for some generic library-internal datastructures, I've had the time to think about the monomorphisation á la rust vs. type erasure á la java/using void* in C/interface{} in go.

I've come up with a "blog post" describing a language extension that I think is suitable for type erasure in Rust, see this gist. It's not yet at the level for an RFC (not that I'd know the process of actually writing one), but I think the main idea is ripe enough for a discussion. Feel free to leave feedback, all spelling mistakes are mine.

[steffahn]

I had some – I think (only skimmed your thing so far) – somewhat comparable ideas myself. Wrote a few notes about it here though that’s not really anything finished / in a good state intended for others to read. With that said, feel free to take a look anyway, if you like

I somehow came to the conclusion at the time that two different new levels of type-erased parameters would be needed. Fully polymorphic (like the ones you call dyn T AFAICT), and types that can contain fully polymorphic parameters but themselves have a known size, can be put on the stack and dropped. I’ll have to think about why exactly that was necessary in my opinion, but I remember it felt appropriate and perhaps even necessary at the time.

(One of) my main motivations was that I wanted to allow for polymorphic recursion. Other motivations would be better performance, and some form of support for generic methods in object-safe traits. I did not want to add anything magical yet, e.g. vtables for trait bounds and the like. Really, I think one of the most important things when getting started with a feature like this will be to create the smallest possible viable (useful) product first, and leave any convenience-functionality built on top for later. E.g. for vtables, I thought, you could as a first step just work with passing around function pointers^[1] manually (while type safety is ensured by the erased type parameters).

---

1. or perhaps even &dyn Fn(…)s ↩︎

[CAD97]

There's ongoing work towards reducing monomorphizations automatically in MIR under "polymorphization." It's not immediately clear how much overlap there is, but it'd certainly be nice to have a guarantee of polymorphization.

This is at a high level an optimization that very code-size-concious containers can often do manually^[1] at cost of type safety, by the internals working over effectively *mut c_void and only reattaching typing as necessary.

However, it's necessary to reattach typing more often than you'd like, as you need a DynMetadata<dyn Sized> in order to get size information for ptr::copy and de/alloc. This means it's impossible to have a properly erased impl with phantom type-system-only typing, because it needs to have the Sized metadata to convert to &dyn Sized.

I don't think it's necessary/possible for types to be generic over a ghost type. Rather, we'd have

struct Box<T>(…);
impl<dyn T: ?Sized> Deref for Box<T> { … }
impl<T: ?Sized> Drop for Box<T> { … }

that is, using guaranteed phantom polymorphism is a property of the impl, not the struct.

I also worry that while dyn is appropriate here, using it will degrade the purpose of switching to requiring dyn as it marking a difference between known generic types and trait object types.

I also worry that the cost of devirtualization through the polymorophic middle may counteract some of the benefit of phantom typing.

In general, though, I absolutely support at least the ability to have (&Opaque, Metadata<T>) and polymorphize this but still maintain a typesafe impl and generic API. I personally would limit the automatic support to fully-erased-phantom-typed types to limit scope (requiring use of a trait to pass in a Metadata<T> to reconstruct &dyn Trait), but I can see the benefits of either approach; requiring the explicit elaboration of providing the pointee metadata allows the developer to control when/how it's provided, though.

Also, dyn const, despite being a seeming contradiction, is a favorite of mine for how to describe custom unsized pointers.

Textual notes

But there are places where this inlining can not be done: traits and dyn objects.

Yes but also no. If you call a &dyn _ function with a concrete type, that can be inlined. More generally, "devirtualization" is a surprisingly powerful optimization technique.

Inlining definitely can't happen while you still only have dyn _, though.

---

1. I have a crate offering ErasedPtr where a primary purpose is writing code which is polymorphized over "some pointer" but doesn't need to know the exact pointer let alone the pointee type. I also offer a Thin<Ptr<T>> which would be a primary beneficiary of phantom typing, as Thin only uses its type parameter in ghost type ways. This also raises a question of whether we can do/suggest this automatically when a type is PhantomDatad and not used for anything not compatible with phantom typing. ↩︎

[WorldSEnder]

@steffahn I took a look and it sounds similar to what you have. Indeed, for the scope of a first RFC, polymorphic recursion (and explicit function pointers) might be sufficient motivation since it doesn't need to explain trait bounds on ghost types.

@CAD97 One reason that types/structs are supposed to be generic under ghost types is that it also acts as an API promise and stability guarantee. If it's only struct Box<T>, and the analysis for impl<dyn T> Deref for Box<T> is done by inspecting the layout of Box at the place of the impl (instead of the definition of Box), then a potential layout change of Box in a future version might break the impl. So guaranteeing it on the struct is also a promise worth specifying explicitly to not cause hard to predict semver breakage.

Having <dyn T> is foremost meant as an additional promise compared to just <T>; that there is an instantiation that can be done by the codegen ahead of time that is compatible with all possible instantiations T = ConcreteType.

Reattaching the drop and clone metadata has to happen for structs owning a ghost T, true, but there's a lot of ways where this is not necessary (and it's expressible in the system, anyway). For example impl<T: Clone> Clone for Box<T> but impl<dyn T: ?Sized> Clone for Rc<T>. Of course, both the Drop impls here would be impl<T: Drop>. I consider being able to express these constraints a feature.

Using dyn as the keyword was a thought to get a first syntax. If there's a nice alternative, I'd consider this, obv. The reason to use it here is that: (1) It's a keyword on the binder that introduces the generic argument, since it's a promise about that generic argument. In the note of steffahn above, there's an extra trait ?Concrete instead, which is kinda weird: It only makes sense to talk about ghost type variables, which is a promise to be indifferent to instantiations of the variable. A specific type is not a ghost type. (2) It has something to do with trait objects, since it's an alternative for them in function signatures.

Trusting the experience from Haskell and GHC, I believe that devirtualizing functions and inlining vtables where the type can be statically determined is still doable in a reasonable amount of time. After all, it's also saving time from not performing monomorphization.

Thank you both for the constructive feedback

[steffahn]

@WorldSEnder

It's a keyword on the binder that introduces a generic argument, since it's a promise about that generic argument. In the note of steffahn above, there's an extra trait ?Concrete instead, which is kinda weird: It only makes sense to talk about ghost type variables, which is a promise to be indifferent to instantiations of the variable. A specific type is not a ghost type.

To clarify on the syntax in my post, T: ?Concrete and poly T are different things, and it was also mostly stand-in syntax in principle. The idea was that both work like Sized-style opt-out trait bounds; so that you could say that e.g. poly T is just sugar for T: ?Mono (“Mono” would mean “monomorphized”), and there’s a hierarchy Concrete: Mono, and T: Concrete (implying also T: Mono) is implicit on all type parameters, whereas T: ?Concrete and T: ?Mono are different levels of opt-out.

As for why (at least) two different things might be necessary: If you have a fully polymorphic type T, assuming that something like Box<T> is allowed, (or if not, at least an alternative like the PolyBox<T> in my notes is possible) you still cannot simply pass such a Box<T> to any legacy generic function foo<S>(x: S): One (and perhaps the main) reason why: if T: 'static then Box<T> with polymorphic T can still not meet any Any bounds, yet I believe supporting : 'static for polymorphic type parameters is a valuable feature to have.

@WorldSEnder

For example impl<T: Clone> Clone for Box<T> but impl<dyn T: ?Sized> Clone for Rc<T>. Of course, both the Drop impls here would be impl<T: Drop>. I consider being able to express these constraints a feature.

I would be wary of auto-magical handling of Drop, too, particularly if it would entail any implicit passing around of vtables. As you can see in the example code at the end of my code, it seems feasible to handle drop code manually in some dedicated type like the PolyBox there, which would mean that existing types Box (or similarly Rc/Arc) would not be made to support directly containing poly T/dyn T type parameters at all.

Of course discussing a feature for more ergonomic Drop interaction is reasonable, but I believe it can quickly lead to many complications. In fully monomorphization free languages with comparable type systems, e.g. Haskell, your trait solver will generate vtables from other vtables at run-time, relying on essentially closure-like objects for “vtable”s at run-time, managed by the garbage collector, etc… If I want to support dropping Box<T> for some dyn T parameter, I would either need to pass a Drop function for the Box<T> itself (even though this type might not be part of the function signature at all…) or I would need to create Box<T>-drop glue based on a function for the drop glue of T; but that becomes a closure-like thing for the generated Box<T>-drop glue then, which is where things would start to become complicated.

Requiring that poly T/dyn T simply cannot be dropped (in a polymorphic setting) except by using manually handled drop code e.g. via unsafe code handling a fn(*mut T), perhaps behind safe wrappers like PolyBox, seems like a potentially more straightforward approach…

…at least as far as my creativity goes. Perhaps you’ve come up with good ideas around how to handle Drop implementations? I haven’t read your whole thing in complete detail yet; if there’s a relevant section, feel free to point me to it.

[CAD97]

@WorldSEnder

Of course, both the Drop impls here would be impl<T: Drop>.

No. T: Drop is never what you want. There is no way to specify a type which cannot be dropped ("linear").

Specifically, T: Drop refers to types with an explicit drop implementation. Additionally, the generics for impl Drop must exactly match those used when defining the type.

@steffahn

If I want to support dropping Box<T> for some dyn T parameter, I would either need to pass a Drop function for the Box<T> itself (even though this type might not be part of the function signature at all…) or I would need to create Box<T>-drop glue based on a function for the drop glue of T; but that becomes a closure-like thing for the generated Box<T>-drop glue then, which is where things would start to become complicated.

AIUI the OP's intent is that there would be a single available fn <for<dyn T> Box<T>>::drop_in_place(self, _: DynMetadata<dyn Sized>) available, and this is what would be called by dropping some Box<dyn T>.

I agree though that having a fully opaque polymorphized but typesafe type and explicitly passing any dyn metadata used to manipulate it captures the primary benefit (guaranteed typesafe polymorphization) while being much simpler to specify.

[HeroicKatora]

@steffahn

Requiring that poly T/dyn T simply cannot be dropped (in a polymorphic setting) except by using manually handled drop code e.g. via unsafe code handling a fn(*mut T), perhaps behind safe wrappers like PolyBox, seems like a potentially more straightforward approach…

Not having it droppable does sound inconsistent with trait bounds otherwise. The trait Empty {} vtable currently contains three pointers: drop_in_place, size, align. And it would generally be expected that anything with at least a Sized bounds introduces them as well. That is specifcally I would expect the vtable associated to Box<dyn T> to contain the same:

- align_of::<T>()
- size_of::<T>()
- drop_in_place::<T>

with the generated drop-glue of Box also being polymorphic over that vtable. I.e., fictionally, just to show semantics:

impl Drop for Box<dyn T> {
    fn drop(&mut self) {
        <dyn T>::drop_in_place(&mut **self);
        dealloc(self.into_raw(),
            Layout::from_size_align(<dyn T>::size_of, <dyn T>::align_of))
    }
}

Note that this is consistent with an explicit type parameter, in which the monomorphisation contains a call to drop_in_place::<T>.

That said, there's an argument for having semantics for dyn T: ?Sized in which the align, size are explicitly not part of the generated and available vtable. I'm currently highly unsure what implications such semantics have. In particular, it seems that a lot of code would not be inherently able to work with such a parameter (similar to code not being automatically const-able). But: code that does offer such an interface would promise to never drop an instance of the parameter, nor move one? Which is a rather odd but intriguing guarantee—very much like extern type of which these aren't available either..

In any case the idea of having dyn that explicitly does not include those items would also be interesting in another way. Indeed, the implicit parameter of fn foo<dyn T> could be a ZST if the vtable is actually empty; and relying on this fact would allow having a new kind of generativity. If no runtime information remains of the type behind the pointer, well, the caller must have ensured (statically) that parameters are passed around correctly. Right? So we could finally fix the awkward lifetime parameters in generativity. Since this is a lot more complex I don't want to detract from the main discussion though.

[steffahn]

As I noted above, my view is that one can avoid

@steffahn

any implicit passing around of vtables

In that case, there is no (implicit) vtable with a poly T/dyn T parameter, and with no vtable, you can’t drop a value or know its size either. In my interpretation of fn foo<poly T>(…) { … } does exactly the same as fn foo<T>(…) { … } except that the former might not compile in cases where the latter does compile; but the win is that the former will never be monomorphized around the choice of T. Something like fn foo<poly T>() -> usize { std::mem::size_of::<&T>() } would always return size_of::<usize>(), i.e. a &T for poly T does not suddenly include any vtable. This also means that you can e.g. have multiple indirections. You can have fn bar<poly T>(x: &&&T) {} and call this function with let r: &&&i32 = &&&42; bar(r);.

If &T inside of bar was required to have a vtable, then callers could only pass values with T behind one level of indirection, I suppose… some sort of unsizing-like operation would be needed. A function fn baz<T>(x: &T, y: &T) would handle redundant copies of the same vtables. (Without such implicit vtables, one of the main powers of polymorphic parameters is that you don’t need all those vtables attached to every single value, like you do with dyn Trait).

[WorldSEnder]

In that case, there is no (implicit) vtable with a poly T/dyn T parameter

It is my intention, as well, which also means I agree that dropping a value of dyn T type would not be allowed, neither calling std::mem::size_of::<T> nor std::ptr::drop_in_place::<T>. But I didn't realize this means that we have to give up compatibility between &dyn Trait and <dyn T: Trait> somewhat, bar additional traits like ?Concrete.

[steffahn]

@WorldSEnder

this means that we have to give up compatibility between &dyn Trait and <dyn T: Trait> somewhat

I mean, if there’s no <dyn T: Trait> allowed in the first place, then you would instead need to pass some form of explicit TraitVtable<T> object around anyways; in which case such a vtable object could also offer methods for converting &T to &dyn Trait and the like. The possibilities are a whole spectrum between doing all of this manually, or having the language at least offer such explicit vtable types itself (automatically generated, essentially), all the way to allowing to call trait methods on &T directly or convert to &dyn Trait, as long as a vtable “is in scope”, or perhaps even passing around such vtables implicitly based on dyn T: Trait> bounds which might become allowed for this in the future; and it seems feasible to add such more advanced / magical / convenience features later, too, AFAICT.

[HeroicKatora]

@steffahn

a &T for poly T does not suddenly include any vtable.

We agree here. We also agree on semantics of size_of::<&T>(), this should be the size of a thin pointer.

But in my interpretation: The vtable is part of an additional implicit parameter or local and not part of pointers. And it would seem quite logical to me if that table was also passed to impls that utilize such a parameter (in particular impl<dyn T> Drop for _). The OP text asserts that it should be possible to call fn(&dyn Trait) when one has an instance &T of dyn T: Trait. This is only possible if at least the information of the instance is available (but it need not be attached to the reference itself) and we stitch the fat pointer back together—so we need to full vtable somewhere, including implicit Sized contents. This interpretation is also why I'm so interested in ?Sized idea because all dyn objects currently work under the same restriction.

[WorldSEnder]

Focusing on the case where no trait bounds on dyn T variables are allowed for a first RFC, at least the following should work and result in a single impl:

struct UpdateRunner<dyn Comp, dyn Msg> {
    state: ComponentState<Comp>,
    meta: DynMetadata<dyn Component<Message = Msg>>,
}
impl<dyn Comp, dyn Msg> Runnable for UpdateRunner<Comp, Msg> { ... }

that is, the associated types would all have to be listed explicitly. That makes it a bit uncomfortable, but I guess it's manageable.

[CAD97]

@HeroicKatora

very much like extern type

... hmm. Could you implement a dyn T (modulo polymorphization guarantee) as

extern {
    type _Opaque;
}

// separate type as extern type cannot carry generics
pub type Opaque<T: ?Sized> {
    _ghost: PhantomData<T>,
    _opaque: _Opaque,
}

impl<'a, T: ?Sized> &'a Opaque<T> {
    pub fn cast<U: ?Sized>(self) -> &'a Opaque<U>;
    pub fn split(val: &T) -> (Self, ptr::Metadata<T>);
    pub unsafe fn combine(self, ptr::Metadata<T>) -> &'a T;
}

// etc for &mut, *const, *mut, ptr::NonNull, etc

? Would it make sense for pointer split into parts to use this?

On the other hand, this is kind of an inversion. Ideally we'd have &T = (&Opaque<T>, ptr::Metadata<T>) (et al). At some level we need a raw pointer type which doesn't hold pointer metadata if we're going to have custom pointer metadata. (Custom allocators are already messing with Box; MIR primitives containing user defined types is a mess to avoid.)

[HeroicKatora]

That's kind of the semantics I had thought of. At least, this would make it straightforward to explain what's going on. The advantage being that the compiler (or rather, the new kind of generic) takes care of the unsafety for you—including when projecting into associated types and constants.

But there's still confusion over combine above, this shouldn't return Self but some dyn-object reference.

[CAD97]

@HeroicKatora

this shouldn't return Self but some dyn-object reference.

... oops, combine was supposed to return &'a T (and for you to use Opaque<dyn Trait>::combine to get &dyn Trait).