Summary of efficient inheritance RFCs (original) (raw)

September 12, 2014, 4:34am 1

At next week’s weekly meeting we will discuss the proposals and implementation plan for some form of more efficient inheritance.

Background

We want some way to have code sharing which is more efficient than traits (in terms of time and space) and more flexible than enums. Our primary use case is the Servo DOM, but we would like this to be more general purpose too. Our constraints are:

• cheap field access from internal methods;
• cheap dynamic dispatch of methods;
• cheap downcasting;
• thin pointers;
• sharing of fields and methods between definitions;
• safe, i.e., doesn’t require a bunch of transmutes or other unsafe code to be usable.

And of course should be as ergonomic as possible, be orthogonal with other library features, feel ‘Rust-y’, etc.

To get an idea of the kind of thing we want to represent (and have an example with which to compare the proposals), see https://gist.github.com/jdm/9900569.

Agenda

The proposal we have mostly been discussing has been the 'enhanced enum’ proposal (RFC PR #142). First I want to make sure this is the right proposal to be concentrating on. Are any of the other proposals better for Rust? Or are there parts of them we might want to incorporate?

Address any open questions with the selected proposal, or at least identify what the open questions are.

Agree on a staging plan for implementation, in particular what needs doing pre-1.0. And how high priority the other items are.

The proposals

• Enhanced enums (142)(author and champion: nrc)
  We discussed this one a fair bit at the work week. The idea is to allow nesting of enums and structs and also for this to not necessarily be lexical nesting (i.e., there is an ‘inherits from’ syntax). Structs are then just an unsized version of enums (they may only be used via pointers and they have minimal size). We then allow virtual methods in impls in order to provide method calls somewhat like traditional OO. Downcasting is given by match. The side-benefits of this proposal are some unification of enums and structs, enum variants as types, and things like struct variants and enum structs fall out naturally, rather than being weird ad-hoc things.
• Virtual Structs (5)(author and champion: nrc)
  Stays as closely as possible to single inheritance in Java or C++. Touches only structs so does not unify structs and enums. That means we end up with two design choices (enums or virtual structs). Uses a similar scheme for virtual methods as RFC 142. The advantage of this approach is that it is pretty small and the DOM has a clear encoding. On the other hand, it is pretty much ‘bolted on’ to Rust and not very natural.
• Fat objects (9)(author: MicahChalmer; champion: pnkfelix)
  Proposes using a pointer to a vtable+data and treating it as DST for representing objects. I use a similar scheme for representing virtual structs in RFC 142. RFC 9 does not actually propose a mechanism for supporting inheritance and efficient virtual methods, just a representation for objects. It suggests using Niko’s earlier [proposal](http://smallcultfollowing.com/babysteps/blog/2013/10/24 /single-inheritance/) for single inheritance by allowing struct inheritance and traits to extend structs. I.e., traits inherit fields from structs.
• Extending enums (11)(author: bill-myers ; champion: zwarich)
  Proposes combining enums and structs in a similar, but not identical way to RFC 142. Internal nodes are enums, leaf nodes are structs. Introduces impl ... as match and impl ... use ... to handle method dispatch rather than virtual methods in impls. I’m afraid I don’t understand exactly how these work. Efficient virtual dispatch seems to be an optimisation the compiler would do in some circumstances (basically when using an enum within a crate) rather than explicit behaviour, but that probably still satisfies the constraints here. I think this idea will not work without a sized/unsized distinction for enums/structs (maybe I’m wrong). There might be other parts of the proposal we like though.
• Trait based inheritance (223)(author: gereeter ; champion: acrichto)
  “This is largely based upon #9 and #91, but fleshed out to make an actual inheritance proposal.”. Seems to be lower level than the other proposals, providing building blocks rather than whole solutions. Structs inherit by using the parent struct as a field and using an attribute to force it to come first in the runtime layout. Adds traits to manually extend coercions and subtyping. Fat pointers are made thin by storing the vtable info in the struct manually and more traits to implement for casting. This proposal is more flexible, but also more boilerplate-prone than the other.
• Kimundi and eddyb have promised an RFC for a possible solution using trait fields. WIP RFC - https://etherpad.mozilla.org/RrQ24kMxz0. Encoding of jdm’s example: https://gist.github.com/eddyb/69e4d2c14c3610f14ea3. TODO - we should assign someone to champion this.

Cheers, Nick

tomaka September 12, 2014, 7:39am 2

In my opinion an additional constraint should be added:

• not being redundant with traits

I hate the current situation in C++ where half the code base uses inheritance and the one half uses templates. I would really dislike it if half of the Rust code base used inheritance as an abstraction mechanics and the other half used traits.

pepp September 12, 2014, 8:30am 3

I second the “not being redundant with traits” requirement.

Moreover, I would like if you could opt-in to “virtual struct” on value-by-value basis as it is currently possible with boxing, mutability. synchronization and other stuff. However, that is possible only with the fat pointer proposal. But it plays nicely with the “pay only for what you need” mantra.

pnkfelix September 12, 2014, 10:35am 4

Indeed, I think the choice was quite deliberate: Let someone else figure out the semantics for inheritance and downcasting, while focusing within RFC PR 9 solely on a unifying treatment of trait objects as either:

• fat-pointers to arbitrary instances, or
• thin-pointers to fat instances.

and the main choice facing the data structure designer are about where you choose to put the word of metadata.

In particular, while the RFC references one particular method for struct inheritance, I think the intention was for this feature to be composable with other potential ways of expressing struct inheritance, such as described in the other RFCs here. (I'm wondering in particular if it would be feasible to take virtual out of RFC PR 142 and using fat objects in its place. I need to read RFC PR 142 more closely first.)

pnkfelix September 12, 2014, 10:49am 5

Wait, I quoted this in full in my earlier comment, but now I want to dispute this portion of the claim.

I think RFC PR 9 does provide a mechanism for efficient virtual method dispatch; its just struct inheritance that it left for another RFC. Namely, for virtual method dispatch, I think its intention was to reuse the existing vtables that we are already emitting for fat-pointers, and just coupling them to the object instances instead of putting them on the fat-pointers.

It is possible that our current calling convention makes it hard (or even impossible) to reuse the vtables in this way. But that seems fixable to me; each method meth in impl TraitBar for StructFoo { fn meth(&self) { ... } } will want to take a pointer to the instance data, which we would need to compute via distinct code sequences for thin-pointers-to-fat-objects vs fat-pointers, but it seems to me like the compiler will have the information it needs to emit those adjustments.

As for method dispatch on trait hierarchies: If trait TraitBaz: TraitBar, then the vtable for TraitBaz carries all of the methods for both traits. That sounds like it should work the same for both fat-pointers and for thin-pointers-to-fat-objects (assuming the adjustments I alluded to in the previous paragraph.)

(Its possible that all of this needs to be laid out more explicitly in RFC PR 9.)

gulbanana September 12, 2014, 10:57am 6

Were glaebhoerl’s ideas about replacing subtyping with coercion applicable to this effort?

pepp September 12, 2014, 12:28pm 7

I think RFC PR 9 does provide a mechanism for efficient virtual method dispatch; its just struct inheritance that it left for another RFC. ... I think its intention was to reuse the existing vtables that we are already emitting for fat-pointers, and just coupling them to the object instances instead of putting them on the fat-pointers.

Yes, that is the case.

@tomaka @pepp

Yeah and that’s why I believe that we should go with one of the trait based proposals (like PR 223). PR 223 also has the advantage of being very flexible (so other inheritance patterns and memory layouts can be implemented for interop purposes).

The ergonomics issues of PR 223 should be fixable by macros. And the fact that inheritance has no dedicated syntax is both a disadvantage and an advantage - It discourages people from overusing inheritance.

rpjohnst September 12, 2014, 4:09pm 9

I don’t like the idea of simply adding any kind of inheritance directly, because that has exactly the same problem as trait objects without the Fat Objects addition- choices have to be made in the language and they are either non-negotiable when you’re designing your data structures, or they add too many knobs and you end up like C++. This applies to both #142 and #5, making them somewhat of a no-go in my opinion.

However, the list of constraints is good. I would most like to see them implemented as orthogonally (to each other) as possible. In other words:

• We already have traits for dynamic dispatch (they are basically reified vtables)
• We already have match for “downcasting” (and if let)
• The Fat Objects proposal gives thin pointers without conflating them with inheritance
• RFC PR 91 (or Trait Based Inheritance, #223) gives control over and access to object layout, providing cheap field access and field sharing also without conflating them with inheritance.

RFC PRs #91 and #233 are good because they implement casting and field access not with new language knobs but with the trait constraint system, just like how #9 does thin pointers and modules do access control without tacking them onto the behemoth feature of “inheritance”.

As for their extra verbosity, there could be a macro as mentioned, but I don’t really see it as an issue. There aren’t an awful lot of cases that we need inheritance, really, and encouraging people to use only the features they need is a giant plus. Composition over inheritance and all that.

Even though I prefer PR 223 for full-on inheritance support, I still think some unifications of structs and enums are good. But making enums and structs "very similar but subtlely different" is not the way to go. Instead, structs and enum variants should be almost equal.

brson September 12, 2014, 5:17pm 11

Thanks for getting all of this organized, @nrc.

aturon September 12, 2014, 8:42pm 12

@nrc I volunteered to champion @eddyb and @Kimundi’s proposal.

@pnkfelix:

Having written the RFC PR 9 proposal, I'll chime in just to say that your interpretation is exactly how I intended it. The idea was to use the same vtable as are currently used with fat pointers, and leave to single inheritance for some other RFC. The idea with linking to Niko's single inheritance post was not to advocate for that particular proposal. It was an example so that I could demonstrate how fat objects, plus some impelmentation of single inheritance, suffice to meet the requirements mentioned under Background above. I put this in the RFC to express that:

Single inheritance is necessary to meet all the listed requirements, but isn't really the focus of this RFC--another RFC should focus on choosing the exact form of it. It's included here by reference, just so I can use it to show that combining it with fat objects meets the requirements that inspired the virtual struct proposal.

I'm looking at the line notes on the PR and will update the branch to correct the noted errors in the sample code.

nrc September 12, 2014, 10:13pm 14

Thanks for clarifying Felix!

nrc September 12, 2014, 10:15pm 15

Ah yes, sorry I forgot that.

nrc September 12, 2014, 10:17pm 16

I remember these from some point, but I couldn’t find an RFC. Perhaps it was closed or merged into another RFC?

pnkfelix September 12, 2014, 11:01pm 17

FYI I realize in hindsight that I may have painted the fat objects RFC in a little bit too rosy a light. It is not clear to me whether it can handle Upcasting from a subtrait object to one of its super traits via the same thin pointer. I only realized this some time after posting my previous message.

If I get the chance I will review the RFC again and see how it handles thus case, perhaps this is a situation where one is simply expected to go from a thin-ptr up to a fat-ptr before then upcasting. Not sure yet.

Cheers, Felix

Yes, I see the problem. I have not addressed how to get a low-cost upcast between a trait and a supertrait on thin pointers. (You couldn’t the address from a &Fat<Element> unmodified as a a &Fat<Node>.)

Kimundi and eddyb’s etherpad (as linked in the summary) contains an idea about how to rearrange the vtable layout that would make such upcasts into either a no-op or a constant offset. I think their handling of upcasting would work with the “fat objects” idea to enable this.

jdoda September 13, 2014, 8:50pm 19

nrc September 13, 2014, 10:39pm 20

Thanks for the link! With a bit more digging, I found RFC PR 91 (https://github.com/rust-lang/rfcs/pull/91) which is an evolution of those ideas. That was closed as postponed for when we could think about coercions (which we are separately starting to do now). There might be some interesting ideas for the inheritance discussion, I’ll have a look…