Pre-RFC: Disjoint Polymorphism

[matthieum]

So, to answer your questions:

• vtable: the thin pointers can be cast to fat pointers (the reverse is not necessarily true), actually, using a single brand of vtable is the goal and this attribute just controls whether one wishes for dynamic polymorphism or not; as discussed in the alternatives it could be left out easily.

• rtti: I believe Any could be optimized to take advantage of the newly emitted RTTI information to navigate the type hierarchy. As far as I know today you can only get the “most-derived-type” out of Any whereas with RTTI information you could down-cast to any type in the hierarchy.

[matthieum]

My main concern was that despite the length and the in-depth nature of the description, I still felt pretty uncertain about some of the technical details. I don’t think this is due to complexity, but rather that a lot of the stuff just doesn’t seem necessary (to me, anyway).

I’ll put up a revision which purges out all talk about tail-padding and cfg configurability.

I do not think Coerce is a good idea. There’s a reason we don’t have DerefMove yet. In particular, making Coerce happen automatically sounds like a recipe for a lot of either bugs or surprising behavior, since it can chop off part of a structure!

Actually, std::mem::transmute refuses to transmute between data of difference sizes. I would also note the trait is unsafe precisely because you are toying with complications here.

A fair amount of the padding section seems not too interesting to me, though I can’t speak for others. I think people would probably be okay with requiring repr(C) if you’re relying on shared layout between two structs (it’s currently required for transmute to be well-defined).

I totally scrapped it out, it was distracting.

I’m much more interested in how all of this stuff applies to enums–does it? If not, it seems like a wasted opportunity, since one case that I frequently want is to be able to turn a set of enums into a larger or smaller set of enums that share the same base (as long as I’ve verified beforehand that all the necessary variants are shared between them).

No, not one bit.

It is easy for struct to share fields, but for enum to share variants brings complications:

• if you extend the enum (add more variants), then matches on the parent enum do not cover the extra variants
• if you refine the enum (remove some variants), then by seeing a mutable reference to the parent, you can add those variants

As a result, it seems that with enum the number of variants must be fixed. I cannot see how to deal with that.

I’m also interested in how generics fit in with all this. They aren’t really discussed, so I’m not sure if they present any additional challenges when it comes to dealing with alignment and so on.

I do not think so; they were not discussed because I did not see any additional challenges. I may just be short-sighted, of course.

I am not really sure about the part where you have to specify which implementations from the parent you are using. What does that buy you, exactly? What if it’s a new trait that’s defined in your own crate; do you have to define it for both the parent and any children you’re using it for there, too?

Rust tries to shy away as much as possible from implicit assumptions; I was just trying to play it safe.

All the cfg stuff sounds pretty bad to me. Why do we need it for every trait? We already have a Reflect OIBIT, which seems like a perfect candidate for deciding whether or not to expose RTTI information, and trait objects, which expose vtable information; neither option splits the language based on whether you want to generate vtables or not.

I flat out don’t understand why you need this new and elaborate rtti model for downcasts. Maybe there’s something I’m missing, but what is wrong with just using the type ID that we already have (which, again, is already bounded by Reflect)? This is how Any does it and it seems to work fine. Also, I don’t know Servo’s precise requirements, but downcasting to an intermediate trait may be what they’re interested in, since Rust can already downcast just fine to an intermediate type (well… I’m not actually exactly sure why they need cheap downcasting at all, so I probably shouldn’t presume that).

I must admit having some difficulties in using Any, so it may well be that it can accomplish much more than I credit it for.

As far as I could see in my exploration, though, Any seemed to suffer from two issues:

• it could only be build from a concrete type
• it could only down-cast to that same concrete type

I’ve tried to coax it to down-cast to traits, but was left quite frustrated by the experience (downcast_mut only targets Sized types, for example).

Thin pointers are probably the most important thing Servo needs, and also probably the most useful thing I expect to come out of all these discussions, so it’s a bit weird that they receive so little attention here.

Yes, all of that to enable thin pointers… Box<DynClass<_, _>> is a thin pointer, and so is Box<Dyn<_>>.

() as a common ancestor really makes no sense to me. What about, say, [T ; 0], or PhantomData? I think the proposal would be better without this.

Actually, it seems the de-facto common ancestor already; I trudge through a few standard libraries which use an unknown type (in unsafe code) and it seems to always end up being either *const () or *mut ().

I thought about leaving it out, however I really wanted to present Dyn<T> as a thin pointer alternative to &T and the cheapest option was for it to be an alias of DynClass<T, ()>. An earlier version of the RFC had a whole new lot type, with conversions back and forth, it felt quite complicated for not that much.

[matthieum]

Thanks a lot for the detailed answer.

Trait impls cannot be private. You either have the impl, or you don’t.

This begs the question of whether advertising the relationship between child and parent is mandatory / not important / harmful.

Another solution would be to pin the condition for checking whether two struct are in a relationship hinge on Child: Parent syntax (like for traits) and align this check on the privacy setting selected.

Do you think it would work better?

What is the motivation for [defining () as common ancestor]?

It is a de-facto ancestor today in the standard libraries, it seems, as *const () and *mut () are used a lot.

I was hoping to build on this to allow a slick definition of Dyn<T>.

I would find it unfortunate for multiple developers to come up with incompatible empty structs just to have a “data-less” thin pointers as they would not be compatible with each others.

I think this section should be removed from the RFC. It’s an implementation detail.

Agreed, I am culling it. The RFC is big enough as it is, and such guarantees are easier to add than remove.

Is [static dispatch] not always possible?

I need to rework this section.

There’s no way to ensure that the type parameter is only substituted with a trait.

Quite annoying; indeed. There is also a big “blank” here in how the VRef instance is supposed to get a hold of the &'static VTable corresponding to its Trait parameter…

The parameter today is mostly used in where clause; to ensure that two traits can share the same v-pointer.

I need to sleep on this.

Does DynClass actually need to be unsized?

My apologies here, DynClass can indeed be used behind &mut much like a trait can; it would otherwise be too restrictive. On top of that, being able to return a DynClass by value would lead to slicing.

DynClass should never be stack-allocated; nor should it be passed (or returned) by value. It’s a view into a bigger object.

And I currently see no way how to ensure those restrictions are followed (short of the _: [u8] trick, which will fall short whenever the compiler is upgraded to be able to return DST).

That’s about all the concrete feedback I have now, though.

It was helpful, thank you for your time.

I’m very uncomfortable with this proposal. Something about it sits wrong with me.

This sounds ominous. Without imposing, I would really like if you could find out what is causing this bad intuition.

But, you claim that these polymorphism traits can be implemented in a library.

Yes, good idea. It will also help me sort out the bugs that slipped through the crack; I’ve got some time on my hands in the coming week, so I’ll try to hack it.

[cmr]

Explicit Coercions

It is possible to require explicit coercions, however it seems strange in light of the Deref precedent and may lead to a usability hit because of the extra verbosity. Still, inference might make it sufficiently lightweight.

So you would like Coerce to be applied whenever applicable and necessary? I’m not sure if the rewrite system implied by this and Deref (and Convertible?) is terminating or confluent. I’d need to sit down and think about it some more. No longer using an associated type worries me. A precise algorithm would be really appreciated!

[matthieum]

I would note that there is neither a Convertible nor a a Transmutable trait, only the Coerce/CoerceRef/CoerceRefMut family.

I am not too satisfied with the move away from associated types either, as it means that the author of the struct loses control. With associated types only the crate containing the struct could implement the various Coerce, which makes it more resilient to changes (even though it’s labelled unsafe).

On the other hand, an associated type in Coerce and co restricts to single “inheritance” line. Today, as defined here, you can only safely coerce into:

• an empty type
• the first non-empty type

Maybe the lack of multiple targets would not be too much of an issue if we instead let the user pick to which type he wishes for automatic coercion; however it would only be safe if the compiler could check that the coercion is valid, so the trait would need some compiler “hook”, and I am wary of making the use of unsafe common-place.

That being said, the problem here might be that I use Coerce for two roles:

• the ability to auto Deref
• as a constraint on functions

I have to see what I could do if Coerce was used simply as constraint, and the user had to implement Deref for smooth conversions. It would remove the dual mechanism and the various ambiguities or surprising behaviours that could arise from it.

Note: this seems like an instance where associated constants (and the ability to check them in where clauses) would really help; with a trait Derived<T> where Self: T { isize const offset; }, we would not need Coerce for constraints check.

[Jexell]

One potiential reason to perhaps not use () is that it creates two ways of extending every single type:

impl TraitName for T {...}

and

impl TraitName for () {...}

[matthieum]

Interesting, however the two are not actually equivalent.

While a Child can easily “re-export” its Parent traits, it has to do so explicitly impl TraitName for Child {} in the current proposal. Therefore:

• traits implemented for any T (no bound) are implicitly implemented for any type
• traits implemented for () have to be implicitly re-implemented for any type, though that type might delegate the implementation by not overriding any method

It does produce a conflict though: now you can provide default method implementations either by doing so in the trait or by doing so for ().

It is unclear whether this is an issue.

[glaebhoerl]

I would need to spend some more time and effort to really understand most of this. (If you feel like helping me (there’s no obligation!), one thing that I suspect might be very helpful is if the RFC were organized more along the lines of “1. this is what we want to be able to do (e.g. such-and-such downcasting) 2. this is why we want to be able to do it (e.g. something something DOM) 3. this is how we propose to make it possible (e.g. rtti stuff)” (or maybe with 1 and 2 swapped) - for each feature. Right now it feels like a quick recap of requirements at the beginning and end, and a big grab-bag of features in the middle, with the connections and motivations not being immediately obvious. I suppose all these might be more apparent to someone who’s been following the various “inheritance-ish” RFCs in depth, but I regrettably haven’t.)

A couple of quick comments I can make though -

It’s my fault for introducing this confusion originally (in the proposal I made in haste) and the damage is probably irreparable, but I really think Coerce/“Coercible” is the wrong terminology here in the Rustic context. It’s an unfortunate case that the Haskell and Rust communities use the same words to mean different things, and I naively imported not just the concept but also its name from how GHC has it. But to recap, for the concept of reinterpreting the raw bytes of one type as another type, Haskell uses the word “coerce” (Coercible, Coercion, coerce, and unsafeCoerce) - and for the same thing, Rust uses the word “transmute” (our mem::transmute is the same thing as their unsafeCoerce). Meanwhile, Rust already uses the word “coerce”/“coercion” to mean a different thing: automatic compiler-inserted conversions between types (which are not in general reinterpretations of raw bytes - e.g. what we call “deref coercions”, which invoke Deref::deref rather than mem::transmute).

Basically, I would prefer to use something like “safely transmutable” where you currently have “coercible”.

And with respect to the formulation of the traits, I believe it is your intent that the implementation (as currently named) of coerce{,_ref{,_mut}} is always the same - it’s always mem::transmute. In other words, implementors of these traits should not be able to override these methods with different implementations. If that’s the case, the right thing to do would be to take the method out of the trait (the trait is now method-less) and provide it as a free-standing function instead (which requires the given trait as a bound).

[gereeter]

Note: I’m the author of Trait Based Inheritance.

A type U is said to be coercible to a type T when transmuting U to T “works”. This is voluntarily vague, and sufficient for this RFC.

I think that it isn’t sufficient to leave this vague in a final, on-the-repo RFC, but it sounds like this is exactly the same relation that @glaebhoerl and I put forward as in RFC 91, which does give a more formal description. Note that RFC 91 uses the term Coercible for your Coerce, both of which, as @glaebhoerl have pointed out, are probably suboptimal.

unsafe trait Coerce<Target> { fn coerce(self) -> Target { mem::transmute(self) } }

unsafe trait CoerceRef<Target> { fn coerce_ref(&self) -> &Target { mem::transmute(&self) } }

trait CoerceRefMut<Target>: CoerceRef<Target> { fn coerce_ref_mut(&mut self) -> &mut Target { mem::transmute(&mut self) } }

I have a couple questions here.

1. What is the motivation for having separate CoerceRef and CoerceRefMut traits instead of just Coerce impls for references (e.g. impl<'a> Coerce<&'a Target> for &'a Source)?

2. As @glaebhoerl pointed out, I’m not sure that these traits should actually have methods. Since every implementation should be mem::transmute, Coerce and friends can just be marker traits, and there can be a free-standing function

   fn coerce<T, S: Coerce<T>>(val: S) {
       unsafe { mem::transmute(val) }
   }
   

3. Unless the impls of these traits are very carefully generated by the compiler, these traits will result in wildly incoherent implementations. This actually isn’t a problem for marker traits, and I’ve been thinking of writing up an RFC to relax the coherence requirements for empty traits, but it would result in ambiguities in generated code if the traits had methods. Whatever strategy you choose to take for this, I think the coherence issue should be mentioned.

4. I’m not sure that it is safe for CoerceRefMut to be a safe trait. Taking the &mut str to &mut [u8] issue, leaving CoerceRefMut safe would allow an incorrect implementation. Coherence checks might prevent this at the moment, but it isn’t totally clear and, as mentioned in the previous point, the coherence rules might have to be weakened for these traits.

struct StructName: [pub] StructName (+ [pub] StructName)* { // other attributes }

This looks nice, but one lighterweight alternative would be a #[parent] attribute that you could apply to the fields of a struct. This would make access of parents more explicit and would allow automatic conversions to be easily chosen or rejected through a choice of a Deref implementation.

By deriving from another struct, the derived struct embeds its parents’ fields. However, due to encapsulation, it can only access fields that it could access if the parent was an attribute.

Continuing from the previous #[parent] suggestion, this would fall immediately out of using fields for data inheritance.

By default, should a parent of a struct implement a trait, it is not necessary for the struct to implement any method, though it still has to explicitly declare the trait implementation:

This feels very nice, though I’m not completely clear on what would happen if multiple parents implemented the trait.

It would be better if the compiler could perform the up-casts implicitly, much like with Deref, there seems to be little point in having the user fiddling with as over and over.

I’d rather have DynClass actually implement Deref<Target=S> and have the structs Deref to their parents, keeping only one system of implicit conversions.

fn make_dynamic<T, S>(original: Box<Class<T, S>>) -> Box<DynClass<T, S>> { unsafe { mem::transmute(original) } }

Why not just have

unsafe impl<T, S> Coerce<Box<DynClass<T, S>>> for Box<Class<T, S>> { }

?

fn up_cast<T, S, B, P>(original: Box<DynClass<T, S>>) -> Box<DynClass<B, P>> where T: B, S: P, S: CoerceRef<P>;

Similarly, this could be done via Coerce.

opinionated: not many building blocks here.

I know this is just my strong opinion aligning with yours, but I view this as an advantage.

Compared to Extend (#223) or associated fields (#250), this RFC does not inject data in traits (mixes payload and behaviour).

Extend explicity did not injecct data into traits. Rather, Extend corresponds almost exactly with your CoerceRef trait - it simply stated a claim that the data was there, allowing you to safely coerce references, doing an upcast. In fact, I find our proposals largely aligned with each other, though I think you definitely have a better, cleaner downcasting story than I did.

My general feeling is that I definitely like this proposal, probably in large part because of its similarity to the proposal I made. I think that focusing on having a set of features that do not step on each others’ toes and work very well together is incredibly important, and I think you have done a good job at doing that.

[Jexell]

@matthieum why do need to have both Class and DynClass and in addition to that TypeInfo, VTable and VRef? Could you not just have:

struct DynClass {
    pub data: *mut (),
    pub vtable: *mut (),
}

Due to differences between Rust and a lot of other OO languages maybe it would be better if something like DynStruct or StructObject (like TraitObject) was used instead of DynClass / Class.

Continuing on from the discussion on (), if T safely transmutes to T then it would not inherit from ().

[jan_hudec]

• thin pointers

Why are thin pointers so important? It seems to be a lot of work to get them.

Also the other features don’t seem to depend on that (and they shouldn’t; thin pointers may be useful somewhere, but I still think most code will prefer to stick with trait references), so perhaps the Class/DynClass stuff could be split off to separate RFC to further simplify the discussion.

[matthieum]

I did not make the list of requirements, they came from Servo.

If I remember correctly the problem in Servo is that there is a lot of pointers and therefore going down from 16 bytes to 8 bytes provides a substantial memory gain.

As for splitting Class/DynClass into another RFC; well, those two classes are the RFC, everything before is just erecting the necessary scaffolding to get there, so I would be quite reluctant at the early stage. I believe it’s important, in this discussion, to keep the whole picture in mind; afterward, when the time comes to implement stuff and the roadmap is clear then working in smaller increments (or switching out some of the scaffolding for other bits) will be much easier.

[jan_hudec]

If I remember correctly the problem in Servo is that there is a lot of pointers and therefore going down from 16 bytes to 8 bytes provides a substantial memory gain.

And I suspect there will be many projects that will want inheritance. but will not get big gain from this. The 8 bytes go to the Class/DynClass, so if there are many objects, but few pointers to each, the gain won’t be that big.

On the other hand, servo would surely get this benefit already without any of the inheritance stuff. Trait objects are there and they use them already and this is simply optimization for trait objects.

That’s why I think this is two mostly independent things that should be proposed separately. One is inheritance, the other is optimizing trait references.

[aturon]

@matthieum

Just wanted to drop a quick note, first of all to thank you for your effort here, and also to let you know that @nikomatsakis and I are both slowly making our way through. It’s been a crazy week post-1.0, but I hope to leave some thoughts next week.

[matthieum]

Thanks for the notice!

On the advice of @cmr I have been trying my hand at a prototype which revealed some things that did not quite work. Once the prototype is working, I’ll push it to github and link it here, then I’ll review this proposal in light of the lessons learned.

As a heads up, for example, I’ve been planning to remove all that talk about “Coerce” traits; the fact that they are used both as “marker” for inheritance and to actually coerce violates the Single Responsibility Principle which seems like poor design, I’ll be replacing them with “just” inheritance markers. I’ll also have to change the exact layout of VTable/Class, as I had not fully realized how Open Inheritance prevented full knowledge of what traits a struct implemented which means moving some stuff around.

[matthieum]

A rough prototype has been push to github: https://github.com/matthieu-m/rust-poly

There are two outstanding issues:

• [repr(C)] and custom Drop implementations apparently do not play well with each others, I suspect this means that the body of DynClass and Class should be revised
• T, as a generic parameter, cannot be declared to be a trait; this means writing constraints annoying (I introduced a trait to indicate that a struct was implementing a trait…) but it also means that the nightly version is refusing to transmute TraitObject to &T (even when T is marked ?Sized)

It is unclear whether those problems happen enough in the wild than a full-fledged solution is necessary or whether a local hack (but which) would be sufficient.

[cmr]

[repr©] and custom Drop implementations apparently do not play well with each others, I suspect this means that the body of DynClass and Class should be revised

Hm, what is the problem here? Off the top of my head I can’t think of any issues that would cause, except for potential bugs in the zeroing code.

T, as a generic parameter, cannot be declared to be a trait; this means writing constraints annoying (I introduced a trait to indicate that a struct was implementing a trait…) but it also means that the nightly version is refusing to transmute TraitObject to &T (even when T is marked ?Sized)

The issue with this is that even though T could be unsized, it isn’t guaranteed to be unsized, so &T could be either one word or two. You can work around this with transmute_copy, but in the case that T is sized, it will be incorrect.

[matthieum]

I get the following warning when implementing Drop for a #[repr(C)] type: warn(drop_with_repr_extern) (activated by default), the text of the warning suggests that implementing Drop introduces hidden state into the type.

Thanks for the transmute_copy trick; I’ll just have to trust in the user not to pass anything weird for now, but at least it’ll get the prototype going.

[matthieum]

Just wanted to let you know that I have updated my experimental repository with the latest approach: https://github.com/matthieu-m/rust-poly

I’ve got a crash in the drop glue generated by rustc (probably my fault for fiddling with Drop in the first place), but it only occurs at the end of the demo code and we can already see polymorphism in action so I am not too worried.

My next step will be to rewrite the RFC from scratch based on the experience gained with the prototype (@cmr was definitely right that the experiment was necessary). I’ll try and take care to distinguish between language/compiler changes and the library changes. Essentially they seem to boil down to:

Language/Compiler changes:

• Addition of raw::{StructInfo, TraitInfo, VTable} and intrinsics::{struct_id, trait_id}
• Addition of intrinsics::{struct_info, trait_info, v_table} (the _by_id versions being part of the kludge)
• Necessary language changes to support data inheritance, and the various “where” clauses

Library changes:

• Addition of the *Cast* traits
• Addition of Class and DynClass (supported by VRef and UntypedVRef)

[matthieum]

First of all: I apologize for taking so long to reply to you; I first wanted to clarify where I was going before answering your points, rather than hand-wave them, and it took much longer than I had anticipated.

Coercible…

So, regarding all this talk of coercion, I actually plan to remove it altogether.

I used a generic term to describe a very specific relationship (parent-child) and on top of that there was indeed a conflation of uses: both a marker trait, and an implementation.

I will instead recommend using a specific vocabulary as part of the RFC.

#[parent]

There are undeniable advantages to using an attribute on an existing data-member, not the least of which is the easiness to refer to said data-member. Or of looking it up on Google (named entities are so much easier to look up than symbols).

On the other hand, it seems more “tacked-on” (why would traits be special-cased?) and expressing bounds is less obvious (whereas if you use Child: Parent like trait, you expect Child: Parent to be a valid bound syntax).

Ultimately, it is something I’ll leave up to debate, and I’ll mention the #[parent] syntax in the alternative section of the RFC so that the community may decide.

This feels very nice, though I’m not completely clear on what would happen if multiple parents implemented the trait.

The compiler would simply refuse to automatically implement the offending methods, complaining about the ambiguity, and the user would have to specify them manually.

It would be better if the compiler could perform the up-casts implicitly, much like with Deref, there seems to be little point in having the user fiddling with as over and over.

This seemed really cool, until @cmr mentioned the potential issues in specifying the algorithm of what to deref to… I plan to strike this down and instead propose a lightweight (but explicit) syntax such as child as &Parent. I’ll let the author of Child decides whether it’s worth it to implement Deref<Target = Parent> or not.

unsafe impl<T, S> Coerce<Box<DynClass<T, S>>> for Box<Class<T, S>> { }

For now I just moved to convert::From. Works pretty well!

fn up_cast<T, S, B, P>(original: Box<DynClass<T, S>>) -> Box<DynClass<B, P>> where T: B, S: P, S: CoerceRef<P>;

Similarly, this could be done via Coerce.

Actually, I moved on to specific [Up|Down]Cast[Ref|]<T> traits, and simply provided an implementation of UpCast<Box<DynClass<B,P>>> for Box<DynClass<T,S>>.

Extend

My mistake, I read Trait: Extend<Struct> in your RFC and mistakenly concluded that it meant the trait had fields, where it was in fact just a bound. I should have been more careful.

My general feeling is that I definitely like this proposal, probably in large part because of its similarity to the proposal I made. I think that focusing on having a set of features that do not step on each others’ toes and work very well together is incredibly important, and I think you have done a good job at doing that.

I think so too! On the recommendation of @cmr I made a prototype you can find at https://github.com/matthieu-m/rust-poly and I’ll now be re-working the RFC based on the experience I gained from it and the feedback I received from here.

I expect it to take me some time, but hopefully by the end of the week I’ll have something I am not too ashamed to show off.

Thanks for your detailed feedback, and once again, my apologies for taking so long to answer.