Aaron Turon

Blog | Academic | Music | About


Project maintained by aturon Hosted on GitHub Pages — Theme by mattgraham

Specialize to reuse

TL;DR: specialization supports clean, inheritance-like patterns out of the box. This post explains how, and discusses the interaction with the “virtual structs” saga.

Table of contents

Overview

I’ve been working for a while with Niko Matsakis and Nick Cameron on another round of design for handling type hierarchies like those found in the DOM, in GUI frameworks, and even the compiler’s AST. The Rust community has gone through many iterations of design in this space, having identified the following goals for a type hierarchy design:

  • 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;
  • syntactically lightweight or implicit upcasting;
  • calling functions through smart pointers, e.g. fn foo(JSRef<T>, ...);
  • static dispatch of methods.

Two important constraints are missing from this prior list, one technical and one philosophical:

  • reusable constructor code at every level of the hierarchy;
  • fits well into the language, either by smoothly extending existing features, or by adding orthogonal concepts.

In the design I’ve been pursuing, impl specialization plays a key role. That’s appealing because specialization is something we’ve long wanted for other reasons, and is a natural deepening of our trait system. But it’s not quite enough, by itself, to meet all of the constraints above.

I’m going to start by recapping the specialization design. Then I’ll explore two competing avenues for building on specialization to meet the design constraints, choose-your-own-adventure style. At the end, I’ll give my current opinions on where we ought to go.

Specialization as proposed

Specialization allows overlapping trait (and inherent) impls, so long as there is always a “most specific” impl that applies to a given concrete type. The more general impl uses default to signal which items can be specialized – sort of the opposite of final in Java, or a bit like virtual in C++.

One of the major intended uses is to support true zero-cost abstraction, by allowing you to customize the impl for specific cases to match performance of non-abstract impls, while maintaining the abstraction for clients. To quote from the RFC:

Traits today can provide static dispatch in Rust, but they can still impose an abstraction tax. For example, consider the Extend trait:

pub trait Extend<A> {
    fn extend<T>(&mut self, iterable: T) where T: IntoIterator<Item=A>;
}

Collections that implement the trait are able to insert data from arbitrary iterators. Today, that means that the implementation can assume nothing about the argument iterable that it’s given except that it can be transformed into an iterator. That means the code must work by repeatedly calling next and inserting elements one at a time.

But in specific cases, like extending a vector with a slice, a much more efficient implementation is possible – and the optimizer isn’t always capable of producing it automatically. In such cases, specialization can be used to get the best of both worlds: retaining the abstraction of extend while providing custom code for specific cases.

The design in this RFC relies on multiple, overlapping trait impls, so to take advantage for Extend we need to refactor a bit:

pub trait Extend<A, T: IntoIterator<Item=A>> {
    fn extend(&mut self, iterable: T);
}

// The generic implementation
impl<A, T> Extend<A, T> for Vec<A> where T: IntoIterator<Item=A> {
    // the `default` qualifier allows this method to be specialized below
    default fn extend(&mut self, iterable: T) {
        ... // implementation using push (like today's extend)
    }
}

// A specialized implementation for slices
impl<'a, A> Extend<A, &'a [A]> for Vec<A> {
    fn extend(&mut self, iterable: &'a [A]) {
        ... // implementation using ptr::write (like push_all)
    }
}

Because the generic impl uses default for its implementation of extend, it’s permitted to give a more specialized impl block that overrides it. (The block is more specialized because it applies to a subset of the types the generic one applies to.)

A specialized impl doesn’t have to provide all the items for a trait; whatever it doesn’t provide is automatically inherited from the generic impl it’s specializing. And conversely, it can only override items marked default.

Going a bit farther, it’s possible to specialize not just impls for a trait, but also defaults for a trait. This is done via partial impl blocks, which are impls that provide some, but not all, of the items required by a trait. Again quoting the RFC:

For example, consider a design for overloading + and +=, such that they are always overloaded together:

trait Add<Rhs=Self> {
    type Output;
    fn add(self, rhs: Rhs) -> Self::Output;
    fn add_assign(&mut self, Rhs);
}

In this case, there’s no natural way to provide a default implementation of add_assign, since we do not want to restrict the Add trait to Clone data.

The specialization design in this RFC also allows for partial implementations, which can provide specialized defaults without actually providing a full trait implementation:

partial impl<T: Clone, Rhs> Add<Rhs> for T {
    // the `default` qualifier allows further specialization
    default fn add_assign(&mut self, rhs: R) {
        let tmp = self.clone() + rhs;
        *self = tmp;
    }
}

This partial impl does not mean that Add is implemented for all Clone data, but jut that when you do impl Add and Self: Clone, you can leave off add_assign:

#[derive(Copy, Clone)]
struct Complex {
    // ...
}

impl Add<Complex> for Complex {
    type Output = Complex;
    fn add(self, rhs: Complex) {
        // ...
    }
    // no fn add_assign necessary
}

A small addendum

The specialization RFC touches on, but doesn’t actually specify, a way to “access” the implementation you’re overriding (akin to super in the OO world).

For the sake of this post, I’ll assume we’ve added such a mechanism by way of a UFCS-like use of default:

trait Foo {
    fn foo(&self);
}

impl<T> Foo for T {
    default fn foo(&self) {
        // do some complicated stuff
    }
}

impl<T: Debug> Foo {
    fn foo(&self) {
        println!("About to `foo` on {:?}", self);
        default::foo(self);
    }
}

The idea is that the default:: prefix accessing the generic impl that’s being overridden, and works like UFCS (in that methods become functions taking self explicitly).

The details here aren’t so important, as long as specialization supports some mechanism like this (which was always the intent).

Ending 1: the trait-based approach

It should already be clear that specialization has a connection to inheritance, because items left off of a specialized impl are inherited from the impl (partial or otherwise) it is specializing. As it turns out, that’s already enough to code up something like traditional type hierarchies in OO languages. You can get pretty far!

This general approach is, in some ways, inspired by eddyb and Kimundi’s proposal from last time around, but using specialization rather than a targeted feature for default refinement. And of course many of the fine points of the design here have been explored by others in the community as well.

Here’s an example, using a lightly simplified extract from Servo’s DOM implementation.

// Node ////////////////////////////////////////////////////////////////////////

trait Node {
    fn parse_plain_attribute(&self, name: &Atom, value: DomString) -> AttrValue {
        AttrValue::String(value)
    }
    // additional virtual methods for Node
}

// non-virtual methods for Node
impl Node {
    fn is_parent_of(&self, child: &Node) -> bool {
        // ...
    }
    // additional methods here
}

// Element /////////////////////////////////////////////////////////////////////

trait Element: Node {
    fn as_activatable(&self) -> Option<&Activatable> {
        None
    }
    // additional Element methods
}

// non-virtual methods for Element
impl Element {
    fn nearest_activable_element(&self) -> Option<&Element> {
        // ...
    }
}

partial impl<T: Element> Node for T {
    default fn parse_plain_attribute(&self, name: &Atom, value: DomString) -> AttrValue {
        match name {
            &atom!("id") => AttrValue::from_atomic(value),
            &atom!("class") => AttrValue::from_serialized_tokenlist(value),
            _ => default::parse_plain_attribute(self, name, value),
        }
    }
}

// Activatable /////////////////////////////////////////////////////////////////

trait Activatable: Element {
    // moar methods
}

partial impl<T: Activatable> Element for T {
    fn as_activatable(&self) -> Option<&Activatable> {
        Some(self)
    }
}

// HtmlAnchorElement ///////////////////////////////////////////////////////////

struct HtmlAnchorElement {
    rel_list: DomTokenList,
    // moar fields
}

impl Node for HtmlAnchorElement {
    fn parse_plain_attribute(&self, name: &Atom, value: DOMString) -> AttrValue {
        match name {
            &atom!("rel") => AttrValue::from_serialized_tokenlist(value),
            _ => default::parse_plain_attribute(self, name, value),
        }
    }
}

impl Element for HtmlAnchorElement {
    // ...
}

impl Activatable for HtmlAnchorElement {
    // ...
}

// HtmlImageElement ////////////////////////////////////////////////////////////

struct HtmlImageElement {
    url: Option<Url>,
    image: Option<Arc<Image>>,
    // moar fields
}

impl Node for HtmlImageElement {
    fn parse_plain_attribute(&self, name: &Atom, value: DOMString) -> AttrValue {
        match name {
            &atom!("name") => AttrValue::from_atomic(value),
            &atom!("width") | &atom!("height") |
            &atom!("hspace") | &atom!("vspace") => AttrValue::from_u32(value, 0),
            _ => default::parse_plain_attribute(self, name, value),
        }
    }
}

impl Element for HtmlImageElement {
    // ...
}

This example is following a basic pattern:

“Abstract base classes” turn into traits.

  • Their virtual methods become methods in the traits (e.g. parse_plain_attribute).

    • They will be virtually dispatched when using trait objects, and statically dispatched when used directly on a type implementing the trait (as usual). In practice that means that after the first virtual call, additional calls on self are statically-dispatched.
  • Their non-virtual methods become inherent methods for the trait, DST style (e.g. is_parent_of). These are always statically-dispatched. (Note: it may be preferable to write these as extension traits with blanket impls, to gain further static dispatch through monomorphization, at a cost in code size.)

  • Default implementations of methods can be done via … defaulted methods!

“Concrete classes” turn into structs.

  • The structs implement all of the traits for the abstract base classes above them.

  • In this case, “overriding” generally just means supplying an impl when a default was available.

Methods can be overridden at any point in the hierarchy.

  • This is done via a blanket (partial) impl, like partial impl<T: Element> Node for T.

  • When one abstract base class overrides its parent, it generally uses partial impl. This is because there are usually still some “abstract” aka “pure virtual” methods for the parent (which are just required methods on the trait).

  • If further overriding should be allowed, these (partial) impls should use default.

    • For example, the as_activatable method is overridden for T: Activatable with a “final” version that cannot be further overridden.

And that’s it. This entire vision of OO-ish programming rests on using the existing system of dynamic dispatch through traits, and gets reuse/inheritance via specialization.

Let’s take stock of the design constraints:

  • cheap field access from internal methods;
    • No: traits have no way to talk about fields directly, and accessors require virtual dispatch (much more expensive than a fixed offset).
  • cheap dynamic dispatch of methods;
    • Yes: covered via the trait system.
  • cheap downcasting;
    • Sort of: see the as_activatable pattern. But not as fast as a type tag check. (The latter can be encoded if we have fields, however.)
  • thin pointers;
    • No: trait objects use fat pointers.
  • sharing of fields and methods between definitions;
    • Yes for methods (via specialization), No for fields.
  • safe, i.e., doesn’t require a bunch of transmutes or other unsafe code to be usable;
    • Yes.
  • syntactically lightweight or implicit upcasting;
    • Yes, once we have it for super-traits in general (an already-slated, highly desired, simple feature).
  • calling functions through smart pointers, e.g. fn foo(JSRef<T>, ...);
    • Yes, via existing coercion/Deref mechanisms.
  • static dispatch of methods;
    • Yes, as discussed avove.
  • reusable constructor code at every level of the hierarchy;
    • No, because fields are not addressed.
  • fits well into the language, either by smoothly extending existing features, or by adding orthogonal concepts.
    • Yes: we didn’t have to add anything beyond specialization (which we’re taking for granted here).

So, we essentially met all but two requirements: thin pointers, and field access/inheritance. What’s the simplest way we could accommodate those?

Thin pointers

Recall that today, trait objects are “fat pointers”: a pointer to some data, and a pointer to a vtable containing methods for operating on that data.

This representation is not an arbitrary choice. It goes hand-in-hand with an important aspect of traits: you can implement a new trait for an already-defined type. This makes traits quite unlike interfaces in languages like Java, C#, or Scala, which have to be applied when you define a type. Traits are flexible bits of glue that can be applied after the fact. But the tradeoff is that the vtable cannot be part of the Self type, at least not if you want separate compilation. After all, the crate defining a struct simply does not know what traits might eventually be applied.

On the other hand, these fat pointers have a drawback: space overhead. In particular, if you have a dense graph of trait objects that are pointing to each other, each pointer’s size is doubled, but the information being stored is often redundant (and the relevant traits are often implemented up front). For serious object graphs, this is a non-starter.

In Rust, when faced with representation tradeoffs, we have a simple tool: the repr attribute. So we can address the desire for thin pointers to traits by introducing #[repr(thin)]:

#[repr(thin)]
trait MyThinTrait {
    fn doit(&self);
}

struct MyType {
    // ...
}

impl MyThinTrait for MyType {
    fn doit(&self) { /* ... */ }
}

fn take_thin(t: &MyThinTrait) {
    t.doit()
}

Applying #[repr(thin)] to a trait like MyThinTrait has a few implications:

  • The representation of types like &MyThinTrait (used in take_thin) is a single pointer, which points to a vtable followed by the data.

  • You can only implement a thin trait for types you define in your crate.

  • If you implement multiple thin traits for a given type, they must form a hierarchy. That ensures consistent layout of the vtable.

Thin traits are a useful representation for Rust to offer regardless of any notion of “inheritance”.

Incorporating fields

Now all that’s left to handle is fields. To get maximal performance, we need some way for a trait to require that Self provides specific fields at statically-known locations (which is true for genuine inheritance hierarchies as one gets in languages like C++). In particular, accessing such fields through a trait is no more expensive than accessing them directly through a known struct: you just load the offset. But unlike a full struct definition, this only requires the existence of a specific field at a specific location; it doesn’t constrain other fields that might be available.

(Note: it may also be desirable to support fields in traits at dynamic offsets, which is still faster than a full dynamic dispatch, but that’s distinct from the requirements set out at the beginning of the post.)

In addition, it would be ideal if field definitions only have to be mentioned once, not repeated in every trait and struct definition that is talking about them.

There are likely a lot of ways we could accomplish these goals, but I’ll highlight a few promising ones, in order of increasing complexity: struct composition, struct inheritance, and trait fields.

Struct composition

There’s a very simple way, in today’s Rust, for one struct to contain all of the information of another struct: simply include the other struct as a field!

struct NodeFields {
    event_target: EventTarget,
    parent_node: Arc<Node>, // Note: this refers to the Node *trait*! see below.
    first_child: Arc<Node>,
    last_child: Arc<Node>,
    next_sibling: Arc<Node>,
    prev_sibling: Arc<Node>,
    // ...
}

struct ElementFields {
    node_fields: NodeFields,
    local_name: Atom,
    namespace: Namespace,
    // ...
}

In this example, Element “inherits” the fields of Node simply by embedding them. This approach also neatly solves the problem of reusing constructors across the hierarchy: a Node here is already a partly-constructed Element.

So the remaining question is how to gain access to these fields in a trait. Here’s one possibility:

trait Node: NodeFields { /* ... */ }
trait Element: Node + ElementFields { /* ... */ }

The idea is that a trait can list any number of super-structs (including indirectly through super-traits), so long as those structs form a composition hierarchy: they must form a chain where each struct contains a leading field whose type is the next struct (like with ElementFields and NodeFields above). The chain then ends in the Self type implementing the trait.

So, to complete the DOM example, we’d have:

struct HtmlAnchorElement {
    element_fields: ElementFields, // internally, contains a leading NodeFields
    rel_list: DomTokenList,
    // moar fields
}

impl Node for HtmlAnchorElement { /* ... */ }
impl Element for HtmlAnchorElement { /* ... */ }

When the trait is in scope, it allows direct access to the fields as if they had been flattened into the struct:

fn parent_node_via_element(e: &Element) -> Arc<node> {
    e.parent_node.clone()
}

(A more verbose alternative might be some UFCS-style <self as NodeFields>::parent_node.clone().)

Of course, this proposal assumes that structs beginning with the same leading field always lay that field out in the same way – in particular, this rules out reordering of the field. If we don’t want to make such a guarantee, we could limit use of struct bounds to thin traits. Since thin traits are implemented for structs in the same crate defining those structs, they can impose additional representation constraints.

Struct inheritance

The above struct composition approach is, in some ways, pretty simple. It builds directly on current patterns for building hierarchies of structs. But it is perhaps too targeted and narrow.

A more expansive alternative is explicit struct inheritance. The basic idea here is very simple:

struct NodeFields {
    event_target: EventTarget,
    parent_node: Arc<Node>,
    // ...
}

// implicitly contains all of NodeFields fields
struct ElementFields: NodeFields {
    local_name: Atom,
    namespace: Namespace,
    // ...
}

The initializer sytax for child structs would then permit either providing all field explicitly, or extending from an instance of the parent structure:

// Style 1: all fields
let e1: ElementFields = ElementFields {
    event_target: /* ... */,
    parent_node: /* ... */,
    // more NodeFields fields
    local_name: /* ... */,
    namespace: /* ... */,
    // more ElementFields fields
};

// Style 2: using parent struct
let n: NodeFields = NodeFields {
    event_target: /* ... */,
    parent_node: /* ... */,
    // more NodeFields fields
};
let e2: ElementFields = ElementFields {
    local_name: /* ... */,
    namespace: /* ... */,
    // more ElementFields fields
    ..n
};

This covers the need for constructors at each level of the hierarchy. But what about hooking into traits?

With struct inheritance, we can treat structs in general as something you can write in a bound, e.g.:

fn take_node_descendant<T: NodeFields>(t: &T) -> Arc<Node> {
    t.parent_node.clone()
}

// same as writing `trait Node where Self: NodeFields`
trait Node: NodeFields { /* ... */ }

In all cases, using a struct as a bound like T: NodeFields means that T must inherit from NodeFields. For traits, that would immediately give you access to the fields, and would impose the fixed static offset requirement (giving maximal performance when accessing those fields). That is, given the definition of Node above, if we have n: &Node, we could write n.parent_node and that would compile as if we had n: NodeFields instead. Because inheritance is explicit at the point of struct definition, we don’t have the layout worries we had with struct composition; we can lay out child structs so that their parents are always consistent prefixes.

It’s plausible that struct inheritance is generally useful outside of OO-like hierarchies; certainly it avoids long chains like my_struct.parent1.parent2.actual_field one gets when using struct composition at scale, although the previous proposal does that as well.

While it’s not necessary to address our goals here, you could also imagine adding coercions from &ElementFields to &NodeFields.

Trait fields

Finally, we could imagine instead adding fields directly to traits:

trait Node {
    parent_node: Arc<Node>,
    // ...
}

This raises a few questions:

  • What do you have to say in an impl?
  • Can the fields be hooked up arbitrarily to Self, or must they form a prefix?
  • Can you avoid writing out copies of the field definitions in every struct in the hierarchy?

There are many ways we might answer these questions, and I won’t try to fully explore the space here. But a simple option is to say that the fields must form a prefix of the fields of Self, and you don’t have to say anything in an impl. Furthermore, if you write:

struct HtmlAnchorElement: Element {
    rel_list: DomTokenList,
    // moar fields
}

you automatically include the fields mentioned in the Element trait (including those from its super-trait Node) as leading fields in the struct.

If we furthermore want to provide reusable constructors at every level of the hierarchy, we have to also include some way of naming these intermediate structs and using them in initaializers, e.g.:

let n: Node::struct = Node::struct {
    event_target: /* ... */,
    parent_node: /* ... */,
    // more Node fields
};
let e: Element::struct = Element::struct {
    local_name: /* ... */,
    namespace: /* ... */,
    // more Element fields
    ..n
};
let h: HtmlAnchorElement = HtmlAnchorElement {
    rel_list: /* ... */,
    // more HtmlAnchorElement fields
    ..e
}

The main advantage of this approach over the previous ones is that you avoid the need to explicitly name structs corresponding to “abstract base classes” (like NodeFields and ElementFields); instead, these are implicit via the ::struct associated type. But there remain questions about using this syntax more flexibly, for mapping trait fields in more arbitrary ways to struct fields, without giving up performance in the fixed-offset case.

A downside is the question of visibility: currently all items in a trait are considered public, but this is not necessarily desirable for fields, so we’d likely need some way to express visibility choices. Fitting that into the existing syntax is not going to be easy. Whereas with struct composition or inheritance, it just “falls out” of the struct definitions.

Ending 2: the enum-based approach

Whew! So all of the proposals we just saw took traits as the sole source of dynamic dispatch and tried to close remaining gaps through slight enrichments of traits and structs.

A radically different approach takes the perspective that Rust already has two forms of dynamic dispatch today – traits and match expressions – corresponding to “open” (extensible) and closed sets of types respectively.

Niko Matsakis outlined a substantial expansion to enums in his recent post, which is part of the original design he, Nick Cameron, and I had been working on. The missing piece in that post is how to tie it together with specialization and thereby get something more like inheritance.

I won’t recap the whole proposal here (it’s worth a read in full!), but in short it makes enums into full-blown hierarchies, defining types at every level (and structs at the leaves):

enum Node {
  // where this node is positioned after layout
  position: Rectangle,
  ...
}

enum Element: Node {
  ...
}

struct TextElement: Element {
  ...
}

struct ParagraphElement: Element {
  ...
}

...

Given such a hierarchy, you can write:

fn takes_any_node<T: Node>(n: &T) { ... }

That is, you can use an enum as a bound, which stands for “any type under this point in the hierarchy”, but will be statically resolved via monomorphization.

This immediately opens the door to specialization for reuse:

trait ParsePlainAttribute {
    fn parse_plain_attribute(&self, name: &Atom, value: DomString) -> AttrValue;
}

impl<T: Node> ParsePlainAttribute for T {
    default fn parse_plain_attribute(&self, name: &Atom, value: DomString) -> AttrValue {
        AttrValue::String(value)
    }
}

impl<T: Element> ParsePlainAttribute for T {
    default fn parse_plain_attribute(&self, name: &Atom, value: DomString) -> AttrValue {
        match name {
            &atom!("id") => AttrValue::from_atomic(value),
            &atom!("class") => AttrValue::from_serialized_tokenlist(value),
            _ => default::parse_plain_attribute(self, name, value),
        }
    }
}

impl ParsePlainAttribute for HtmlAnchorElement {
    fn parse_plain_attribute(&self, name: &Atom, value: DOMString) -> AttrValue {
        match name {
            &atom!("rel") => AttrValue::from_serialized_tokenlist(value),
            _ => default::parse_plain_attribute(self, name, value),
        }
    }
}

This pattern of specialization, trying to match the example at the beginning of the post, almost works: if you call parse_plain_attribute on an HtmlAnchorElement, you’ll get the correct behavior.

But if you’ve upcasted to an Element or Node, the behavior will revert to the defaults for those types! That’s because you’re not getting dynamic dispatch here, which for enums we said should go through match.

The solution is to instead write the code as follows:

impl ParsePlainAttribute for Node {
    default fn parse_plain_attribute(&self, name: &Atom, value: DomString) -> AttrValue {
        AttrValue::String(value)
    }
}

impl ParsePlainAttribute for Element {
    default fn parse_plain_attribute(&self, name: &Atom, value: DomString) -> AttrValue {
        match name {
            &atom!("id") => AttrValue::from_atomic(value),
            &atom!("class") => AttrValue::from_serialized_tokenlist(value),
            _ => default::parse_plain_attribute(self, name, value),
        }
    }
}

impl ParsePlainAttribute for HtmlAnchorElement {
    fn parse_plain_attribute(&self, name: &Atom, value: DOMString) -> AttrValue {
        match name {
            &atom!("rel") => AttrValue::from_serialized_tokenlist(value),
            _ => default::parse_plain_attribute(self, name, value),
        }
    }
}

Note that we’re now using specialization without any explicit blanket impls. In this proposal, when the Self type is an enum, it’s as if you had written a blanket impl like the ones above, except that when the function is invoked on the enum type, it will use a match to dispatch to most specialized implementation. That is, it’s as if we’d written the following for Node:

// Fully generic *default* impl
impl<T: Node> ParsePlainAttribute for T {
    default fn parse_plain_attribute(&self, name: &Atom, value: DomString) -> AttrValue {
        AttrValue::String(value)
    }
}

// Specialized impl for the `Node` type itself
impl ParsePlainAttribute for Node {
    fn parse_plain_attribute(&self, name: &Atom, value: DomString) -> AttrValue {
        match *self {
            // NOTE: `this` has a different type in each arm!
            ref this@Node::HtmlAnchorElement => this.parse_plain_attribute(name, value),
            ref this@Node::HtmlImageElement => this.parse_plain_attribute(name, value),
            // ...
        }
    }
}

And of course:

  • It’s nicer to write the impls directly against the enum type than using an explicit blanket;
  • This is also almost certainly the behavior you wanted anyway: you always get the most specific impl, whether dynamically or statically dispatched.

But the desugaring only triggers when Self is a direct enum type.

Getting opinionated

If you’ve stuck with me until this point, first of all: thanks! That was a long haul.

So, what should we do? To recap, we have two major routes, both of which start with specialization.

  • The first takes a minimalistic approach, adding a couple of minor (and independently motivated) features to traits and structs to get to our goal. There are a few options for dealing with fields, in particular.

  • The second combines specialization with another major set of enhancements to enums, which are also independently motivated, but are much more complex. It then adds a bit of sugar on top to tie the two together.

The trait approach allows for open-ended hierarchies (extensible by downstream crates), while the enum approach is closed. On the flip side, that means that downcasting can be somewhat more awkward (and is a code smell) for the trait approach, while it’s completely natural (just a match) for the enum approach.

Initially, I was very excited about the latter, enum-centric approach, because the work on enum hierarchies seems like such a natural extension to Rust. But I am worried about a few things. First of all, getting the proposal that Niko laid out to work will require substantially reworking our type inference to account for subtyping. Making this happen backwards-compatibly with our existing enums is not going to be easy, and may not even be possible. It also makes subtyping much more important in Rust, which is likely to be a complexity multiplier as it interacts with every other aspect of the type system. There are also various dark syntactic corners that come out of the partial unification of enums and structs (e.g., how do you specify visibility of shared fields in an in-line enum?) Finally, the key bit of sugar at the apex that ties enum hierarchies and specialization together is a bit subtle, and only covers the most obvious cases of Self.

In short, I see a lot of known risks, and worry about unknown risks, with the enum hierarchy route.

In contrast, the struct/trait-centric proposals feel much less risky; they don’t introduce fundamental new complexity that interacts with the rest of the type system, and they have a smaller overall footprint. I also like the way that specialization is used very explicitly to get inheritance, rather than through a layer of sugar on top.

And of the struct proposals, I think that struct inheritance strikes the best balance between minimalism, flexibility, and “fit” with the existing language.

The main downside of my preferred struct/trait approach is that there’s some amount of boilerplate: “abstract base classes” like Node turn into a Node trait and a NodeFields struct. That detail could easily be hidden behind a macro, but it might also argue in favor of the more complex traits-with-fields variant.

(I should mention: it’s possible that in the long run, we’ll want subtyping and not just coercions with any approach we take. But still, enum hierarchies want this to happen for our existing enums in a way that may require breakage.)

If we do go with a struct/trait approach, I think we should carefully check that the design is compatible with a future expansion of enums along the lines Niko laid out in his post, since we may still want enum hierarchies in the long run. I’ve given this a fair amount of thought, and likewise think that struct inheritance is the best fit. In particular, it could replace the somewhat magical proposal for “common fields” (which included an associated MyEnum::struct type).