Justin Restivo | HOME | ABOUT | CONTACT | PROJECTS | LINKEDIN | GITHUB | MISC MUSINGS

Subtyping with associated types on traits in Rust

1 Motivating the Problem

In short, we have no trait subtyping relationship that preserves associated types. It would be great if this were possible. But alas, Rust doesn't allow for this (yet!). This post is aimed at working around this.

In Rust, suppose we have a lot of generics, with arbitrary constraints. For example, suppose we wish to build many types of animals. Each animal has Ears Ears , Mouth Mouth , Legs Legs , and Lungs Lungs . Each of these implement some traits. The normal ones like Clone Clone , as well as Send + Sync Send + Sync to send between threads.

The first pass stab at this might look like:


pub trait Fluffy {};
pub trait Taste {};
pub trait Legs {};
pub trait Lungs {};



pub trait Animal<Ears, Mouth, Legs, Lungs>
where
  Ears: Clone + Send + Sync + Fluffy,
  Mouth: Clone + Send + Sync + Taste,
  Legs: Clone + Send + Sync + Fast,
  Lungs: Clone + Send + Sync + Breathe,
{}

pub trait Fluffy {};
pub trait Taste {};
pub trait Legs {};
pub trait Lungs {};



pub trait Animal<Ears, Mouth, Legs, Lungs>
where
  Ears: Clone + Send + Sync + Fluffy,
  Mouth: Clone + Send + Sync + Taste,
  Legs: Clone + Send + Sync + Fast,
  Lungs: Clone + Send + Sync + Breathe,
{}

Suppose we wish to implement this and type constrain it. Any impl block is going require this awkward set of type constraints.

impl<ANIMAL, EARS, MOUTH, LEGS, LUNGS>
where
  EARS: Clone + Send + Sync + Fluffy,
  MOUTH: Clone + Send + Sync + Taste,
  LEGS: Clone + Send + Sync + Fast,
  LUNGS: Clone + Send + Sync + Breathe,
  ANIMAL: Animal<Ears, Mouth, Legs, Lungs>
{

}
impl<ANIMAL, EARS, MOUTH, LEGS, LUNGS>
where
  EARS: Clone + Send + Sync + Fluffy,
  MOUTH: Clone + Send + Sync + Taste,
  LEGS: Clone + Send + Sync + Fast,
  LUNGS: Clone + Send + Sync + Breathe,
  ANIMAL: Animal<Ears, Mouth, Legs, Lungs>
{

}

This is gross. It doesn't scale. It's very easy to mis-order the generics. Luckily, Rust has a way around this: associated types. We instead have something like:

pub trait Animal : Clone + Send + Sync {
  type Ears: Clone + Send + Sync + Fluffy;
  type Mouth: Clone + Send + Sync + Taste;
  type Legs: Clone + Send + Sync + Fast;
  type Lungs: Clone + Send + Sync + Breathe;
}
pub trait Animal : Clone + Send + Sync {
  type Ears: Clone + Send + Sync + Fluffy;
  type Mouth: Clone + Send + Sync + Taste;
  type Legs: Clone + Send + Sync + Fast;
  type Lungs: Clone + Send + Sync + Breathe;
}

Then, our impl block looks like:

impl<ANIMAL: Animal>
{

}
impl<ANIMAL: Animal>
{

}

And, we can have an implementation for an arbitrary struct:

pub struct AnimalImpl<Ears, Mouth, Legs, Lungs>{
  _pd_0: PhantomData<Ears>,
  _pd_1: PhantomData<Mouth>,
  _pd_2: PhantomData<Legs>,
  _pd_3: PhantomData<Lungs>,
}

impl<EARS, MOUTH, LEGS, LUNGS> Animal for AnimalImpl<EARS, MOUTH, LEGS, LUNGS>
where
  EARS: Clone + Send + Sync + Fluffy,
  MOUTH: Clone + Send + Sync + Taste,
  LEGS: Clone + Send + Sync + Fast,
  LUNGS: Clone + Send + Sync + Breathe,
{
  type Ears = EARS;
  type Mouth = MOUTH;
  type Legs = LEGS;
  type Lungs = LUNGS;
}
pub struct AnimalImpl<Ears, Mouth, Legs, Lungs>{
  _pd_0: PhantomData<Ears>,
  _pd_1: PhantomData<Mouth>,
  _pd_2: PhantomData<Legs>,
  _pd_3: PhantomData<Lungs>,
}

impl<EARS, MOUTH, LEGS, LUNGS> Animal for AnimalImpl<EARS, MOUTH, LEGS, LUNGS>
where
  EARS: Clone + Send + Sync + Fluffy,
  MOUTH: Clone + Send + Sync + Taste,
  LEGS: Clone + Send + Sync + Fast,
  LUNGS: Clone + Send + Sync + Breathe,
{
  type Ears = EARS;
  type Mouth = MOUTH;
  type Legs = LEGS;
  type Lungs = LUNGS;
}

Unfortunately we have to awkwardly copy type constraints. But still, this is much cleaner, since our impl blocks will only be generic over Animal Animal . It scales with the number of generics quite nicely.

2 The Problem

This is all great until we want to build off this Animal Animal trait while avoding having to copy around type constraints. Our very explicit goal is to keep all type constraints in the same place and repeated as few times as possible.

Suppose we wish to express types associated with a Dinosaur Dinosaur . Our Dinosaur Dinosaur is an animal, but we have additional requirements on its associated types. Its associated types must all must implement Prehistoric Prehistoric . A first attempt at this using associated types might look like:

pub trait Prehistoric {}

pub trait Dinosaur : Clone + Send + Sync {
  type Ears: Clone + Send + Sync + Fluffy + Prehistoric;
  type Mouth: Clone + Send + Sync + Taste + Prehistoric;
  type Legs: Clone + Send + Sync + Fast + Prehistoric;
  type Lungs: Clone + Send + Sync + Breathe + Prehistoric;
}
pub trait Prehistoric {}

pub trait Dinosaur : Clone + Send + Sync {
  type Ears: Clone + Send + Sync + Fluffy + Prehistoric;
  type Mouth: Clone + Send + Sync + Taste + Prehistoric;
  type Legs: Clone + Send + Sync + Fast + Prehistoric;
  type Lungs: Clone + Send + Sync + Breathe + Prehistoric;
}

This works great! Except…we are now copying over all the type constraints from Animal Animal into our Dinosaur Dinosaur trait. We can refactor out traits a bit:

pub trait AnimalPart: Clone + Send + Sync

pub trait AnimalEars: AnimalPart + Fluffy;
pub trait AnimalMouth: AnimalPart + Taste;
pub trait AnimalLegs: AnimalPart + Fast;
pub trait AnimalLungs: AnimalPart + Breathe;

pub trait Animal
{
  type Ears: AnimalEars;
  type Mouth: AnimalMouth;
  type Legs: AnimalLegs;
  type Lungs: AnimalLungs;
}

pub trait Dinosaur {
  type Ears: AnimalEars + Prehistoric;
  type Mouth: AnimalMouth + Prehistoric;
  type Legs: AnimalLegs + Prehistoric;
  type Lungs: AnimalLungs + Prehistoric;
}
pub trait AnimalPart: Clone + Send + Sync

pub trait AnimalEars: AnimalPart + Fluffy;
pub trait AnimalMouth: AnimalPart + Taste;
pub trait AnimalLegs: AnimalPart + Fast;
pub trait AnimalLungs: AnimalPart + Breathe;

pub trait Animal
{
  type Ears: AnimalEars;
  type Mouth: AnimalMouth;
  type Legs: AnimalLegs;
  type Lungs: AnimalLungs;
}

pub trait Dinosaur {
  type Ears: AnimalEars + Prehistoric;
  type Mouth: AnimalMouth + Prehistoric;
  type Legs: AnimalLegs + Prehistoric;
  type Lungs: AnimalLungs + Prehistoric;
}

This is almost what we want. Except, we really would like Dinosaur Dinosaur to implement Animal Animal . Suppose Animal Animal has an associated function pub fn do_animal_things() pub fn do_animal_things() that we would like to call. Then we could have Dinosaur Dinosaur implement Animal Animal :

pub trait Animal
{
  type Ears: AnimalEars;
  type Mouth: AnimalMouth;
  type Legs: AnimalLegs;
  type Lungs: AnimalLungs;

  pub fn do_animal_things();
}

pub trait Dinosaur {
  type Ears: AnimalEars + Prehistoric;
  type Mouth: AnimalMouth + Prehistoric;
  type Legs: AnimalLegs + Prehistoric;
  type Lungs: AnimalLungs + Prehistoric;
}
pub trait Animal
{
  type Ears: AnimalEars;
  type Mouth: AnimalMouth;
  type Legs: AnimalLegs;
  type Lungs: AnimalLungs;

  pub fn do_animal_things();
}

pub trait Dinosaur {
  type Ears: AnimalEars + Prehistoric;
  type Mouth: AnimalMouth + Prehistoric;
  type Legs: AnimalLegs + Prehistoric;
  type Lungs: AnimalLungs + Prehistoric;
}

But how do we force the associated types on Animal Animal to match those on Dinosaur Dinosaur ? What if Animal Animal has requirements not expressed in Dinosaur Dinosaur ? We really want to force Dinosaur Dinosaur to implement Animal Animal . A naive attempt to do this:

pub trait Dinosaur : Animal<Ears = Self::Ears, Mouth = Self::Mouth, Legs = Self::Legs, Lungs = Self::Lungs>{
  type Ears: AnimalEars + Prehistoric;
  type Mouth: AnimalMouth + Prehistoric;
  type Legs: AnimalLegs + Prehistoric;
  type Lungs: AnimalLungs + Prehistoric;
}
pub trait Dinosaur : Animal<Ears = Self::Ears, Mouth = Self::Mouth, Legs = Self::Legs, Lungs = Self::Lungs>{
  type Ears: AnimalEars + Prehistoric;
  type Mouth: AnimalMouth + Prehistoric;
  type Legs: AnimalLegs + Prehistoric;
  type Lungs: AnimalLungs + Prehistoric;
}

But alas! We end up with an error:

cycle detected when computing the super traits of `Dinosaur` with associated type name `Ears`
cycle detected when computing the super traits of `Dinosaur` with associated type name `Ears`

Now what?

3 The Solution

The best way I could come up to do this is to add another associated type:

pub trait Dinosaur {
  type Ears: AnimalEars + Prehistoric;
  type Mouth: AnimalMouth + Prehistoric;
  type Legs: AnimalLegs + Prehistoric;
  type Lungs: AnimalLungs + Prehistoric;

  type Animal: Animal<Ears = Self::Ears, Mouth = Self::Mouth, Legs = Self::Legs, Lungs = Self::Lungs>
}
pub trait Dinosaur {
  type Ears: AnimalEars + Prehistoric;
  type Mouth: AnimalMouth + Prehistoric;
  type Legs: AnimalLegs + Prehistoric;
  type Lungs: AnimalLungs + Prehistoric;

  type Animal: Animal<Ears = Self::Ears, Mouth = Self::Mouth, Legs = Self::Legs, Lungs = Self::Lungs>
}

This is annoying because another associated type has been added. But then, initialization is easy:

impl<EARS, MOUTH, LEGS, LUNGS> Animal for AnimalImpl<EARS, MOUTH, LEGS, LUNGS>
where
  EARS: AnimalEars,
  MOUTH: AnimalMouth,
  LEGS: AnimalLegs,
  LUNGS: AnimalLungs,
{
  type Ears = EARS;
  type Mouth = MOUTH;
  type Legs = LEGS;
  type Lungs = LUNGS;

  pub fn do_animal_things();
}

impl<EARS, MOUTH, LEGS, LUNGS> Dinosaur for AnimalImpl<EARS, MOUTH, LEGS, LUNGS>
where
  EARS: AnimalEars + Prehistoric,
  MOUTH: AnimalMouth + Prehistoric,
  LEGS: AnimalLegs + Prehistoric,
  LUNGS: AnimalLungs + Prehistoric,
{
  type Ears = EARS;
  type Mouth = MOUTH;
  type Legs = LEGS;
  type Lungs = LUNGS;

  type Animal = Self;
}
impl<EARS, MOUTH, LEGS, LUNGS> Animal for AnimalImpl<EARS, MOUTH, LEGS, LUNGS>
where
  EARS: AnimalEars,
  MOUTH: AnimalMouth,
  LEGS: AnimalLegs,
  LUNGS: AnimalLungs,
{
  type Ears = EARS;
  type Mouth = MOUTH;
  type Legs = LEGS;
  type Lungs = LUNGS;

  pub fn do_animal_things();
}

impl<EARS, MOUTH, LEGS, LUNGS> Dinosaur for AnimalImpl<EARS, MOUTH, LEGS, LUNGS>
where
  EARS: AnimalEars + Prehistoric,
  MOUTH: AnimalMouth + Prehistoric,
  LEGS: AnimalLegs + Prehistoric,
  LUNGS: AnimalLungs + Prehistoric,
{
  type Ears = EARS;
  type Mouth = MOUTH;
  type Legs = LEGS;
  type Lungs = LUNGS;

  type Animal = Self;
}

I don't see a cleaner way to do this (if you do, let me know!). But, this surely is cleaner than restating type constraints everywhere as one might do if Dinosaur Dinosaur did not implement Animal Animal . Or if we were using generics instead of associated types for both Dinosaur Dinosaur and Animal Animal .