Add limited implementation inheritance via traits

[brson]

Not sure if 'implementation inheritance' is the right name for this.

Servo people are complaining a lot about not being able to inherit the memory layout of supertypes, since the DOM is a classic OO hierarchy. Seems like we just have to do it. The basic idea is to let traits specify struct fields.

Needs a complete design, something simple.

[brson]

Nominating.

[brson]

Let's put it behind a feature flag until it matures, get into the habit of doing so for all new features.

[nikomatsakis]

cc me -- at some point I sketched out a design for this with @pcwalton, not sure if it ever got written up, can't recall, but I'm basically in favor of it. The rough point was to permit structs to extend other structs and to permit traits to extend a struct as well. If one struct S extends another struct T, then S is a substruct of T, and &S is a subtype of &T (as well as ~S <: ~T). S begins with all the fields of T. If a trait extends a struct S, it must be implemented by the struct S or some substruct of S.

[jdm]

There was some discussion at the 2/26 meeting: https://github.com/mozilla/rust/wiki/Meeting-weekly-2013-02-26

[bholley]

What's the plan for virtuals and method resolution? Supposing I have:

struct Element : Node { pub fn setAttribute(&mut self) {...}
struct HTMLElement : Element { }
struct HTMLIFrameElement : HTMLElement { pub fn setAttribute(&mut self) {...} }

HTMLIframeElement::setAttribute needs to do some special work (checking for 'src' sets) and then forward to Element::setAttribute. So we need two things:

(1) HTMLIframeElement's implementation needs a way to explicitly invoke Element's implementation on the same region of memory.

(2) If I have some |&Element foo|, invoking foo.setAttribute() needs to invoke the HTMLIframeElement version.

Do we need to introduce a |virtual| keyword?

[glaebhoerl]

@bholley the plan is to use traits. The separation between types and impls would be maintained as ever.

struct Element: Node { ... }
struct HTMLElement: Element { ... }
struct HTMLIFrameElement: HTMLElement { ... }

trait IElement: Element {
    fn setAttribute(&mut self);
}

Here you can only implement IElement for types which inherit Element. If you have an &IElement, you can access its Element fields directly, and setAttribute will be called 'virtually'. Forwarding to the "base class" implementation is an interesting question: I guess it might work by casting self to the appropriate ancestor type, then calling the method? But I'll defer to others here.

[bholley]

Ah, I see. So methods declared in a trait are virtual, and methods declared in a struct are non-virtual. And presumably we can invoke Element::setAttribute from HTMLIframeElement::setAttribute somehow?

I assume we're looking only at single inheritance for this stuff? We make extensive use of multiple inheritance in Gecko, but my gut feeling is that we can use entity patterns to solve those uses cases.

[glaebhoerl]

There is no such thing as "methods declared in a struct". Methods are declared in separate impl blocks. But yes, methods in impl MyType are non-virtual, while methods in impl MyTrait for MyType are virtual if invoked through a pointer-to-MyTrait ("object").

And yes, only single inheritance of structs.

[thestinger]

are virtual if invoked through a pointer-to-MyTrait ("object").

To clarify, using trait methods via the type itself or generics is still just static dispatch. It's only dynamic dispatch via a trait object.

[catamorphism]

high priority, no milestone

[nikomatsakis]

http://smallcultfollowing.com/babysteps/blog/2013/10/24/single-inheritance/

[nrc]

I'm working on this (at least starting to)

[bholley]

\o/

[nikomatsakis]

@nick29581 good place to draw up a complete RFC :)

[nrc]

@nikomatsakis plan is to implement the 'obvious' bit - inheritance for structs (no trait/struct mixing, no subtyping), feature gated - then do an RFC for the rest.

[glaebhoerl]

Unfortunately I have a counterproposal.

I was thinking about how subtype relationships might be precisely specified, as well as potential subtype relationships between some built-in types, and along the way stumbled into the realization that we might be better served by a plan modelled after GHC's Coercible.

Motivation

The first issue is that if you were to have struct B: A { ... }, the relationship between B and A is very different from the relationship between &B and &A. The latter two have exactly the same representation (so &B is a proper subtype of &A), but B's representation only starts with A. This is surprising to no one (it was covered in @nikomatsakis's blog post), but it's awkward syntactically: how do you distinguish the two in constraints? Both are valuable: T starts-with U implies, for instance, that &T may be safely transmuted to &U, while T is-a-proper-subtype-of U has stronger implications, for example that &[T] may be safely transmuted to &[U].

The larger issue is that while we might think we want single inheritance and subtypes, what we actually want is safe zero-cost conversions between binary compatible types, of which subtypes induced by single inheritance are only a smallish subset.

It went like this. I was thinking: hmm... wouldn't it be nice if [T, ..n] were considered a subtype of [T, ..m], provided n > m? And wouldn't it be nice if (A, B, C) were considered a subtype of (A, B)? And these seemed like interesting possibilities, but they made me a little bit uncomfortable. And then I realized that you also might like to coerce &[T, ..n] to &T, and to coerce between T and [T, ..1] and (T,) (the singleton tuple), and stipulating a subtype relationship of any sort between these is plainly preposterous. I then realized that there's much, much more: including conversions between any two out of a type and any newtypes of that type, conversions between same-sized numeric types (like int and uint), and conversions which are akin to mass-borrowing, such as &'s [~T] to &'s [&'s T]. I then thought of GHC's Coercible, which does similar things.

So hopefully well-motivated, here's the plan.

Interface

The user-facing interface would be exposed as a trait and a function/method:

trait Coercible<T> { }
#[inline(always)]
fn coerce<U, T: Coercible<U>>(x: T) -> U { unsafe { transmute(x) } }

The trait would be wired-in to the compiler, and user-defined impls of it would be illegal. coerce() would coerce between any two types where the target type "is a proper subtype of" the input type. Note that coerce is never a virtual call, as it is not a method of Coercible: Coercible<T> doesn't have a vtable, and could be considered a built-in "kind" alongside Freeze, Send, etc.

Where single inheritance and subtyping conflate many different ideas, among them transparent access to superstruct fields, zero-cost conversion from sub- to supertypes, and these conversions being implicit/automatic, Coercible captures and exposes only the thing which is truly important: the zero-cost conversions, and for a much wider range of scenarios.

There would be another such wired-in trait which I'm going to call HasPrefix. T: HasPrefix<U> corresponds to T starts-with U from above, while T: Coercible<U> corresponds to T is-a-proper-subtype-of U.

trait HasPrefix<T> { }

The only reason HasPrefix is important is because it gives rise to Coercible relationships, as in the example above: T: HasPrefix<U> => &T: Coercible<&U>.

The most important aspect of the single inheritance proposal is that you could abstract over it, as with traits: traits could specify that they could only be implemented by structs inheriting a given struct, and therefore fields of that struct could be accessed through trait objects without any additional overhead. Here you could accomplish the equivalent by making HasPrefix<Foo> a supertrait of your trait. Perhaps more flexibly, if syntax allows, you could also put it in the "kinds" list: &MyTrait:HasPrefix<Foo>. Accessing fields of the struct would be syntactically noisier, as you would need to insert explicit calls to coerce(), but in performance terms it would be exactly the same. In general, anything you could express as substruct or subtype relationships in the single inheritance proposal could be expressed as HasPrefix and/or Coercible bounds, while the reverse is not true.

In terms of surface syntax, we could have a function or method like coerce() or cast() as I've been assuming above, or perhaps we could tie it into as. I prefer the former, because it allows the target type to be inferred, while still allowing it to be specified explicitly using type application, or once we gain type ascription anywhere, more ergonomically as foo.cast(): TargetType.

Implementation

As with GHC's Coercible (see previous link), these might not actually be implemented by having honest-to-god wired-in impls of them, but it's easier to explain if you pretend that they would. So pretend that things of the following nature would also be wired-in.

For any two types A and B out of a base type and any newtypes of it (meaning a struct with a single member), and also any two numeric types of the same size, and also any two zero-sized types:

impl Coercible<A> for B { }
impl Coercible<B> for A { }

For singleton arrays and their element:

impl<T> Coercible<T> for [T, ..1] { }
impl<T> Coercible<[T, ..1]> for T { }

For tuples of a given size with all elements of the same type, and fixed-length arrays of that size and type:

impl<T, static N: uint> Coercible<[T, ..N]> for (T, T, .. times N) { } // fake syntax
impl<T, static N: uint> Coercible<(T, T, .. times N)> for [T, ..N] { }

For any struct B and its first field A (single inheritance would be a subset of this single case!):

impl HasPrefix<A> for B { }

For tuples and longer tuples:

impl<A, B, ..X, Y> HasPrefix<(A, B, ..X)> for (A, B, ..X, Y) { }

For arrays and longer arrays:

impl<T, static M: uint, static N: uint> where N > M HasPrefix<[T, ..M]> for [T, ..N] { }

The following is for all types and their prefixes, and all generic types with covariant "pointer-like" type parameter contexts. It's what takes you from "U is a substruct of T" to "&U is a proper subtype of &T". I'm going to make this idea of a "pointer-like" context more precise in another RFC I'm working on, but for now let's just say that it's any generic type whose shallow in-memory representation is independent of the identity of T, such as pointer/reference types. Importantly, a type parameter of any type with a destructor would be considered invariant, which means that ~T could not be coerced to ~U, as desired. (I'm not sure if this is precisely the right rule - are there type with destructors where we would want to permit it? Are there types without destructors where we wouldn't? - but it seems like a good first stab at the problem.)

impl<U, T: HasPrefix<U>, R<covariant pointer-like context>> Coercible<R<U>> for R<T> { }

Vice versa for contravariant contexts:

impl<U, T: HasPrefix<U>, R<contravariant pointer-like context>> Coercible<R<T>> for R<U> { }

For proper subtypes we can coerce across all covariant contexts, not just pointer-like ones, meaning for instance that we can can coerce a whole array at once (&[T] -> &[U], with R = &[]):

impl<U, T: Coercible<U>, R<covariant context>> Coercible<R<U>> for R<T> { }

Again, vice versa for contravariant:

impl<U, T: Coercible<U>, R<contravariant context>> Coercible<R<T>> for R<U> { }

Now some special-cased coercions for mass-borrowing. We can't directly coerce from ~T to &'s T because we have no idea what 's should be, but it works if the whole thing is frozen for 's by an outer reference. I don't have the stamina right now to think through whether the converses would also be valid in the contravariant case (though I suspect they would). How to extend this to library-defined smart pointers is also left to future work.

impl<'s,     T, R<covariant context>> Coercible<&'s R<&'s T>>         for &'s R<~T> { }
impl<'s,     T, R<covariant context>> Coercible<&'s mut R<&'s mut T>> for &'s mut R<~T> { }
impl<'s, 't, T, R<covariant context>> Coercible<&'s R<&'t T>>         for &'s R<&'t mut T> { }

Reflexivity:

impl<T> HasPrefix<T> for T { }
impl<T> Coercible<T> for T { }

Transitivity:

impl<A, B: HasPrefix<A>, C: HasPrefix<B>> HasPrefix<A> for C { }
impl<A, B: Coercible<A>, C: Coercible<B>> Coercible<A> for C { }

Whew! That's all I could think of right now. Unlike GHC, we do not have symmetry in general: a whole lot of conversions are in one direction only.

As in GHC, these make-believe impls are wildly overlapping and incoherent, but that doesn't matter, because we don't care which impl is selected (they have no vtable), only whether or not one exists.

And also as in GHC, to preserve abstraction boundaries, as a general principle, for those impls which involve conversions between user-defined types, they would only "be in scope" when the means to do the conversion manually are in scope. This means that you could only cast &Struct to &FirstFieldOfStruct if the first field of the struct is visible to you, you could only cast Foo to NewTypeOfFoo if its constructor is visible, and other similar rules along these lines.

Conclusion

I believe this proposal would have many beneficial aspects. By jettisoning those parts of single inheritance and subtyping which are not truly important and concentrating on the ones which are, it would allow greater power and flexibility, while also hopefully allowing a simpler implementation which localizes the logic related to zero-cost conversions to a single part of the language, the built-in Coercible and HasPrefix traits (as opposed to every potential assignment, function call, etc. being subject to implicit subtyping rules). The drawback, which may also be seen as an advantage, is that coercions need to be explicitly invoked by the programmer. In exchange, the scope of possible coercions is far greater.

[emberian]

cc me

[pnkfelix]

cc me

[nikomatsakis]

On Tue, Feb 25, 2014 at 03:43:20PM -0800, Gábor Lehel wrote:

Unfortunately I have a counterproposal.

This is very interesting. =) A lot to chew on here! I have certainly
noticed that there are a wide variety of simple coercions (e.g. &T
to &[T, ..1] and so forth) that people do in C and which are
sometimes convenient in Rust. I'm also somewhat intrigued by the
notion that coherence rules can be looser for zero-method traits.

[ariasuni]

@glaebhoerl: can you give some real life examples for humans (:p) please? I’d like to better understand.

[glaebhoerl]

I'm also somewhat intrigued by the notion that coherence rules can be looser for zero-method traits.

I never thought of doing this in general (built-in traits can do what they want), but I guess it might be an interesting possibility to think about on a side track. Can you think of any use cases?

@sinma: There was some further explication on reddit, but otherwise... what kind of examples would you like to see?

[ariasuni]

@glaebhoerl: I found the explanations a bit abstract. :) I think of little examples that shows how «traditionnal» inheritance translates into Rust with this proposal, as well as concrete case where it’s way more practical than traditionnal inheritance (I don’t know Rust well but I know a bit C/C++/Java/Python/etc). I’ll read it again tomorrow I think, and examples helps verify if I understand correctly. :p

[nikomatsakis]

On Wed, Feb 26, 2014 at 03:10:42PM -0800, Gábor Lehel wrote:

I'm also somewhat intrigued by the notion that coherence rules can be looser for zero-method traits.

I never thought of doing this in general (built-in traits can do what they want), but I guess it might be an interesting possibility to think about on a side track. Can you think of any use cases?

Any user-defined trait that represents a property of a type that must
be tested might benefit from such a rule, no?

[nrc]

After some discussion with Lars and Patrick, we think that the motivation for any kind of struct-struct struct-trait inheritance or subtyping is not as pressing as it was. Is there any other use case or motivation for having something like this in the language? Probably looking at something post-1.0 or maybe never.

[emberian]

It's needed to do COM nicely, and it helps with certain game architectures
afaik (@dobkeratops would need to speak to that)

On Mon, Mar 3, 2014 at 7:00 PM, Nick Cameron notifications@github.comwrote:

After some discussion with Lars and Patrick, we think that the motivation
for any kind of struct-struct struct-trait inheritance or subtyping is not
as pressing as it was. Is there any other use case or motivation for having
something like this in the language? Probably looking at something post-1.0
or maybe never.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/9912#issuecomment-36576809
.

http://octayn.net/

[eddyb]

Could COM use @glaebhoerl's coercions or fixed-position "virtual" (yet free, because the offsets are fixed in the trait definition) fields in traits?

[dobkeratops]

IMO, Single inheritance works very well in many common,wellknown situations - for a start I beleive its absence makes your AST code harder to navigate. (having it reduces naming& navigation effort and this is a REALLY big deal without an IDE). Many node types would just derive from 'SpannedNode' etc, less having to remember 'which submember is this in' .. and with less reused names between different structs its easier to find the element in question.

Given that the feature seems simple i haven't worried about its absence - I know there are many conflicting demands for language features.. but I do worry if you proclaim that it isn't important or its 'never' :(

I think it does often work well for game entity layouts, and does work well for UI scene descriptiions aswell. So a programmer familiar with these patterns will find Rust code feels clunky :(
"bullet.pos" vs "bullet.ent.frame.matrix.pos " // arghh, its my most common property and now it has the longest name
"bullet.radius" vs "bullet.ent.radius" etc // ah which nesting level is that property at.. etc

It has a very simple low level representation - its possible to do single inheritance easily in ASM by just by reusing slot offsets ... so it makes sense for a low level language to represent it, IMO.

You still have the option of using composition where needed - its not like having the feature proclaims that programmers must use inheritance hierarchies; and Rust already has superior ways of doing interfaces so I dont think having it will make Rust programmers suddenly succumb to poor OOP patterns or anything.

[kobi2187]

Hi, a newcomer here, I saw this issue, and thought of chipping in my thoughts.
I think there could be a simple implementation, by using the 'decorator pattern'
it means that a class contains a few objects, and "proxies" methods to those inner objects. (from the outside it looks like the class inherits multiple classes, though they're actually just inner objects).
It can be hidden from the user, as a simple implementation, or exposed to his heart's desires.
An example "exposed" syntax (just as inspiration)

wraps obj1
    include *
    exclude such_and_such, such2
    rename method1 to meth1
end

so basically those methods get generated, and the implementation is just a one liner, forwarding to the inner objects.
in this way you get a simple implementation of pseudo multiple-inheritence.
you may need a few more adjustments, what I had in mind is how the eiffel language tackled the user api.

[visionscaper]

cc me

[kaisellgren]

So, how would one design Git's object structure in Rust? It would look something like this:

struct ObjectId { ... }
struct ObjectHeader { ... }

struct GitObject {
  id: ObjectId,
  header: ObjectHeader
}

struct Commit /* : GitObject */ { ... }
struct Note /* : GitObject */ { ... }
struct Blob /* : GitObject */ { ... }
struct Tag /* : GitObject */ { ... }
struct Tree /* : GitObject */ { ... }

How do the five Git objects inherit GitObject's two fields? Or is there a different way to approach this problem other than inheritance assuming we do not copy-paste the fields to each Git object type?

Edit: it looks like we might be getting virtual structs.

[jansegre]

@kaisellgren well, you can always do it C like, from the official sources:

struct object { ... };
struct commit {
    struct object object;
    ...
};

Thought I'd really like to understand better @glaebhoerl's proposal.

[kaisellgren]

@jansegre Yes, via composition. That will work, although I was hoping for some nicer solution.

[vojtechkral]

Hello, newcomer here, I stumbled upon this thread recently. (It's top or one of the top Google results for queries the likes of "rust inheritance".)

There is some very interesting reading here, esp. by @nikomatsakis and @glaebhoerl . However, both proposals make me uncomfortable. Both of them are quite complex and it's not immediately obvious what the use case would be like.

@nikomatsakis 's proposal breaks the separation between traits and structs, which is something I've always regarded as a great virtue of Rust. Traits extending structs? IMHO it's a concept too reminiscent of class known from C++/Java/C#/... -type of languages.

@glaebhoerl 's proposal introduces two new 'magical' (ie. compiler-special) traits, which by itself is not necessarily a bad thing, however I don't feel it's justified even by wider applicability. Do we actually need to convert [T, ..1] to T via an explicit syntax rather than a different already-existing explicit syntax? The same thing applies to [T, ..n] → [T, ..m] coercion - don't we already have slice for that sort of thing?

Couldn't this be done in some kind of a KISS (Keep It Simple, Stupid) way? I'm not sure I have enough theoretical foundation to propose a solution myself, so the following might be a complete nonsense, but I'm giving it a try anyway:

struct Foo: Bar {...} defines a struct Foo inheriting struct Bar via following principles:

1. layout-wise, Foo is the same as Bar with Foo-specific elements appended at the end.
2. All traits implemented for Foo are also automatically implemented for Bar. In consequence, any &Foo could be used with the same traits as &Bar. Note that this actually avoids the sort of relationships described by @glaebhoerl - Foo is, strictly speaking, in no way related to Bar and the same applies to &Foo and &Bar, the only relation is that they share implementation of traits. This also implies that there would be no casting between the two - see below for notes.

How would dynamic dispatch be done? Since traits already provide that and they also already provide possibility for partial implementation (albeit somewhat limited) it would only make sense to use these features for dynamic dispatch in the context of inheritance. The only thing needed would be to allow partial re-implementations of traits that are defined for parent. Basically, when defining impl of a trait for a descendant, the impl of this trait for parent would be considered default for the impl for descendant.

No upcasting/downcasting? That's bad. Well, there are pros and cons. For example, if you needed to create a vector of polymorphed objects, it would need to be Vec<&BarTrait> where BarTrait is a trait implemented for Bar (and consequently also Foo). The pros are:

• Using traits like this is probably already fairly familiar with Rust programmers
• There is no need for any special casting and casting-related magic whatsoever

Cons:

• There always is a performance overhead of the vtable. It takes some pondering to tell how serious a problem this is. I've seen reports that a vtable lookup only takes an instruction or two tops (in C++, using GCC - frankly I don't know how many it is in Rust). Anyway, in cases where avoiding vtable lookup is necessary a custom-tailored solution might be used, it would probably not be that hard.
• There is no downcasting. However, downcasting is pretty much just one of applications of RTTI, which I'd expect to rather be designed separately from inheritance (for the most part) along with a discussion whether it is really a useful thing in the first place.

I'm well aware that this is a very simplistic approach and that I've probably overlooked a thing or twenty, so feel free to criticize anything :)

Regardless, whatever approach ends up being featured in the language (if any), I'd be really glad if it:

• Did not break the nice separation between structs and traits
• Were simple enough to understand and use - for instance, Trait based inheritance rfcs#223 is IMHO ridiculously complicated
• Involved as few magical traits, functions, operators, etc. as possible ("magical" meaning with special behaviour defined by the compiler). Again, this is a reason why I really dislike Trait based inheritance rfcs#223 , as it involves 1 compiler directive, 1 global function and some 5 special types ... Are they being serious!?

So, yeah, that'd be my two cents..

[jansegre]

@vojtechkral I've been playing with Rust for the last couple of weeks and I'm really comfortable with the fact that there is no struct inheritance, it's been a while that I'm less inclined to use traditional OO, I find that most of the time there's better alternative, and that may be why I'm fond of how Rust does it with structs and traits.

However for the few cases that a more traditional OO approach actually helps I think it is a very good thing that you pay for it with some syntax, so it won't be what you want to try first and hopefully you'll only use it if you need it. Therefore I'm completely in favor of @glaebhoerl's proposal now that I have some better understanding of it after reading about GHC's Coercible.

[steveklabnik]

@vojtechkral @jansegre you both may want to read http://discuss.rust-lang.org/t/summary-of-efficient-inheritance-rfcs/494/6

[CloudiDust]

@vojtechkral, I think the reason RFC PR 223 has many traits is because it decouples the traditional "components" of inheritance support from each other, giving the programmer maximum flexibility. I believe most people will use sugars (macros) built upon those "low-level" building blocks.

The advantage of this approach is that we will not be constrained by any specific flavor of inheritance. This will be handy when interop with other languages (mainly C++, I think) is needed.

[vojtechkral]

@jansegre Yes, despite the complaints I actually like glaebhoerl's proposal the best out of the others...

[rust-highfive]

This issue has been moved to the RFCs repo: rust-lang/rfcs#299