Gankra/subtyping2.md

## subtyping2.md

      
    Raw
  

              subtyping2.md
            
          
    Subtyping and Variance

Subtyping is a relationship between types that allows statically typed
languages to be a bit more flexible and permissive.
Subtyping in Rust is a bit different from subtyping in other languages. This leads
to examples of subtyping being a bit convoluted. This is especially unforunate
because subtyping, and especially variance, are actually really hard to
understand properly. As in, even compiler writers mess it up all the time.
In order to make examples that are simple and concise, this section will consider a
small extension to the Rust language to introduce subtyping in a way that is more
similar to other languages. After establishing concepts and issues under this simpler
system, we will then relate it back to how subtyping actually occurs in Rust.
So here's our simple extension, Objective Rust, featuring three new types:
trait Animal {
    fn snuggle(&self);
    fn eat(&mut self);
}

trait Cat: Animal {
    fn meow(&self);
}

trait Dog: Animal {
    fn bark(&self);
}
But unlike normal traits, we can use them as concrete and sized types, just like structs.
Now, say we have a very simple function that takes an Animal, like this:
fn love(pet: Animal) {
    pet.snuggle();
}
By default, static types must match exactly for a program to compile. As such,
this code won't compile:
let mr_snuggles: Cat = ...;
love(mr_snuggles);         // ERROR: expected Animal, found Cat
Mr. Snuggles is a Cat, and Cats aren't exactly Animals, so we can't love him! 😿
This is especially annoying because Cats are Animals. They support every operation
an Animal supports, so intuitively love shouldn't care if we pass it a Cat.
Or, to put it another way, we should be able to just forget the non-animal
parts of our Cat, as they aren't necessary to love it.
This is exactly the problem that subtyping is intended to fix. Because Cats are just
Animals and more, we say Cat is a subtype of Animal (because Cats are a subset
of all the Animals). Equivalently, we can say that Animal is a supertype of Cat.
With subtypes, we can tweak our overly strict static type system
with a simple rule: anywhere a value of some type T is expected, we also accept
values that are subtypes of T.
Or more concretely: anywhere an Animal is expected, a Cat or Dog will also work.
As we will see throughout the rest of this section, subtyping is a lot more complicated
and subtle than this, but this simple rule is a very good 99% intuition. And unless you
write unsafe code, the compiler will automatically handle all the corner cases for you.
But this is the Rustonomicon. We're writing unsafe code, so we need to understand how
this stuff really works, and how we can mess it up.
The core problem is that this rule, naively applied, will lead to Meowing Dogs. That is,
we can convince someone that a Dog is actually a Cat. This completely destroys the fabric
of our static type system, making it worse than useless (and leading to Undefined Behaviour).
Here's a simple example of this happening when we apply subtyping in a completely naive
"find and replace" way.
fn evil_feeder(pet: &mut Animal) {
    // EVIL PLAN: replace all pets with dogs!
    let spike: Dog = ...;

    // `pet` is an Animal, and Dog is a subtype of Animal,
    // so this should be fine, right..?
    let new_pet: Animal = spike;
    *pet = new_pet;

    pet.feed();
}

fn main() {
    let mut mr_snuggles: Cat = ...;

    // Replaces mr_snuggles with a Dog!
    evil_feeder(&mut mr_snuggles);

    // mr_snuggles has type Cat, so make it meow!
    mr_snuggles.meow(); // OH NO, MEOWING DOG!
}
Clearly, we need a more robust system than "always let subtyping work". That system is variance,
the rules governing how subtyping composes. The rest of this section will be focusing on what
variance is, and how it works.
But before we get into variance, let's take a quick peek at where subtyping actually occurs in
Rust: lifetimes!
Lifetimes are just regions of code, and regions can be partially ordered with the contains
(outlives) relationship. Subtyping on lifetimes is in terms of that relationship:
if 'big: 'small ("big contains small" or "big outlives small"), then 'big is a subtype
of 'small. This is a large source of confusion, because it seems backwards
to many: the bigger region is a subtype of the smaller region. But it makes
sense if you consider our Animal example: Cat is an Animal and more,
just as 'big is 'small and more.
Put another way, if someone wants a reference that lives for 'small,
usually what they actually mean is that they want a reference that lives
for at least 'small. They don't actually care if the lifetimes match
exactly. So it should be ok for us to forget that we live for 'big.
For this reason 'static, the forever lifetime, is a subtype of every lifetime.
Higher-ranked lifetimes
(for<'a>, or more commonly, the 'a in fn eq<'a>(&'a T, &'a T) -> bool)
are also subtypes of every concrete lifetime. This is because something which
can handle "any lifetime" can certainly handle "some lifetime".

NOTE: The typed-ness of lifetimes is a fairly arbitrary construct that some
disagree with. However it simplifies our analysis to treat lifetimes
and types uniformly.

With all that said, we still have no idea how to actually use subtyping of lifetimes,
because nothing ever has type 'a. Lifetimes only occur as part of some larger type
like &'a u32 or IterMut<'a, u32>. To apply lifetime subtyping, we need to know
how to compose subtyping. Once again, we need variance.
Variance

Much the same as before, but leaning more on Objective Rust(TM) for examples.