Rust grammar supplement

Subtyping and Variance - The Rustonomicon

The Dark Arts of Advanced and Unsafe Rust Programming

https://doc.rust-lang.org/nomicon/subtyping.html

Generic Data Types - The Rust Programming Language

We use generics to create definitions for items like function signatures or structs, which we can then use with many different concrete data types. Let’s first look at how to define functions, structs, enums, and methods using generics. Then we’ll discuss how generics affect code performance.

https://doc.rust-lang.org/book/ch10-01-syntax.html

PhantomData - The Rustonomicon

The Dark Arts of Advanced and Unsafe Rust Programming

https://doc.rust-lang.org/nomicon/phantom-data.html

Generic Data Types In Function Definitions In Struct Definitions Subtyping and Variance Subtyping Variance PhantomData Generic parameters and drop-checking

When defining a function that uses generics, we place the generics in the signature of the function where we would usually specify the data types of the parameters and return value. Doing so makes our code more flexible and provides more functionality to callers of our function while preventing code duplication.

Continuing with our largest function, Listing 10-4 shows two functions that both find the largest value in a slice. We'll then combine these into a single function that uses generics.

Filename: src/main.rs

Listing 10-4: Two functions that differ only in their names and the types in their signatures

The largest_i32 function is the one we extracted in Listing 10-3 that finds the largest i32 in a slice. The largest_char function finds the largest char in a slice. The function bodies have the same code, so let’s eliminate the duplication by introducing a generic type parameter in a single function.

To parameterize the types in a new single function, we need to name the type parameter, just as we do for the value parameters to a function. You can use any identifier as a type parameter name. But we’ll use T because, by convention, type parameter names in Rust are short, often just a letter, and Rust’s type-naming convention is UpperCamelCase. Short for “type,” T is the default choice of most Rust programmers.

When we use a parameter in the body of the function, we have to declare the parameter name in the signature so the compiler knows what that name means. Similarly, when we use a type parameter name in a function signature, we have to declare the type parameter name before we use it. To define the generic largest function, place type name declarations inside angle brackets, <>, between the name of the function and the parameter list, like this:

We read this definition as: the function largest is generic over some type T. This function has one parameter named list, which is a slice of values of type T. The largest function will return a reference to a value of the same type T.

Listing 10-5 shows the combined largest function definition using the generic data type in its signature. The listing also shows how we can call the function with either a slice of i32 values or char values. Note that this code won’t compile yet, but we’ll fix it later in this chapter.

Filename: src/main.rs

Listing 10-5: The largest function using generic type parameters; this doesn’t yet compile

If we compile this code right now, we’ll get this error:

The help text mentions std::cmp::PartialOrd, which is a trait, and we’re going to talk about traits in the next section. For now, know that this error states that the body of largest won’t work for all possible types that T could be. Because we want to compare values of type T in the body, we can only use types whose values can be ordered. To enable comparisons, the standard library has the std::cmp::PartialOrd trait that you can implement on types (see Appendix C for more on this trait). By following the help text's suggestion, we restrict the types valid for T to only those that implement PartialOrd and this example will compile, because the standard library implements PartialOrd on both i32 and char.

In Struct Definitions

We can also define structs to use a generic type parameter in one or more fields using the <> syntax. Listing 10-6 defines a Point<T> struct to hold x and y coordinate values of any type.

Filename: src/main.rs

Listing 10-6: A Point<T> struct that holds x and y values of type T

The syntax for using generics in struct definitions is similar to that used in function definitions. First, we declare the name of the type parameter inside angle brackets just after the name of the struct. Then we use the generic type in the struct definition where we would otherwise specify concrete data types.

Note that because we’ve used only one generic type to define Point<T>, this definition says that the Point<T> struct is generic over some type T, and the fields x and y are both that same type, whatever that type may be. If we create an instance of a Point<T> that has values of different types, as in Listing 10-7, our code won’t compile. Filename: src/main.rs

Listing 10-7: The fields x and y must be the same type because both have the same generic data type T.

In this example, when we assign the integer value 5 to x, we let the compiler know that the generic type T will be an integer for this instance of Point<T>. Then when we specify 4.0 for y, which we’ve defined to have the same type as x, we’ll get a type mismatch error like this:

To define a Point struct where x and y are both generics but could have different types, we can use multiple generic type parameters. For example, in Listing 10-8, we change the definition of Point to be generic over types T and U where x is of type T and y is of type U.

Filename: src/main.rs

Listing 10-8: A Point<T, U> generic over two types so that x and y can be values of different types

Now all the instances of Point shown are allowed! You can use as many generic type parameters in a definition as you want, but using more than a few makes your code hard to read. If you're finding you need lots of generic types in your code, it could indicate that your code needs restructuring into smaller pieces.

Subtyping and Variance

Rust uses lifetimes to track the relationships between borrows and ownership. However, a naive implementation of lifetimes would be either too restrictive, or permit undefined behavior.

In order to allow flexible usage of lifetimes while also preventing their misuse, Rust uses subtyping and variance.

Let's start with an example.

In a conservative implementation of lifetimes, since hello and world have different lifetimes, we might see the following error:

This would be rather unfortunate. In this case, what we want is to accept any type that lives at least as long as 'world. Let's try using subtyping with our lifetimes.

Subtyping

Subtyping is the idea that one type can be used in place of another.

Let's define that Sub is a subtype of Super (we'll be using the notation Sub <: Super throughout this chapter).

What this is suggesting to us is that the set of requirements that Super defines are completely satisfied by Sub. Sub may then have more requirements.

Now, in order to use subtyping with lifetimes, we need to define the requirement of a lifetime:

'a defines a region of code.

Now that we have a defined set of requirements for lifetimes, we can define how they relate to each other:

'long <: 'short if and only if 'long defines a region of code that completely contains 'short.

'long may define a region larger than 'short, but that still fits our definition.

As we will see throughout the rest of this chapter, 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.

Going back to our example above, we can say that 'static <: 'world. For now, let's also accept the idea that subtypes of lifetimes can be passed through references (more on this in Variance), e.g. &'static str is a subtype of &'world str, then we can "downgrade" &'static str into a &'world str. With that, the example above will compile:

Variance

Above, we glossed over the fact that 'static <: 'b implied that &'static T <: &'b T. This uses a property known as variance. It's not always as simple as this example, though. To understand that, let's try to extend this example a bit:

In assign, we are setting the hello reference to point to world. But then world goes out of scope, before the later use of hello in the println!

This is a classic use-after-free bug!

Our first instinct might be to blame the assign impl, but there's really nothing wrong here. It shouldn't be surprising that we might want to assign a T into a T. The problem is that we cannot assume that &mut &'static str and &mut &'b str are compatible. This means that &mut &'static str cannot be a subtype of &mut &'b str, even if 'static is a subtype of 'b.

Variance is the concept that Rust borrows to define relationships about subtypes through their generic parameters.

NOTE: For convenience we will define a generic type F<T> so that we can easily talk about T. Hopefully this is clear in context.

The type F's variance is how the subtyping of its inputs affects the subtyping of its outputs. There are three kinds of variance in Rust. Given two types Sub and Super, where Sub is a subtype of Super:

F is covariant if F<Sub> is a subtype of F<Super> (the subtype property is passed through)

F is contravariant if F<Super> is a subtype of F<Sub> (the subtype property is "inverted")

F is invariant otherwise (no subtyping relationship exists)

If we remember from the above examples, it was ok for us to treat &'a T as a subtype of &'b T if 'a <: 'b, therefore we can say that &'a T is covariant over 'a. Also, we saw that it was not ok for us to treat &mut &'a U as a subtype of &mut &'b U, therefore we can say that &mut T is invariant over T

Here is a table of some other generic types and their variances:

ㅤ	'a	T	U
`&'a T`	covariant	covariant	ㅤ
`&'a mut T`	covariant	invariant	ㅤ
`Box<T>`	ㅤ	covariant	ㅤ
`Vec<T>`	ㅤ	covariant	ㅤ
`UnsafeCell<T>`	ㅤ	invariant	ㅤ
`Cell<T>`	ㅤ	invariant	ㅤ
`fn(T) -> U`	ㅤ	contravariant	covariant
`*const T`	ㅤ	covariant	ㅤ
`*mut T`	ㅤ	invariant	ㅤ

Some of these can be explained simply in relation to the others:

Vec<T> and all other owning pointers and collections follow the same logic as Box<T>

Cell<T> and all other interior mutability types follow the same logic as UnsafeCell<T>

UnsafeCell<T> having interior mutability gives it the same variance properties as &mut T

const T follows the logic of &T

mut T follows the logic of &mut T (or UnsafeCell<T>)

NOTE: the only source of contravariance in the language is the arguments to a function, which is why it really doesn't come up much in practice. Invoking contravariance involves higher-order programming with function pointers that take references with specific lifetimes (as opposed to the usual "any lifetime", which gets into higher rank lifetimes, which work independently of subtyping).

Now that we have some more formal understanding of variance, let's go through some more examples in more detail.

And what do we get when we run this?

Good, it doesn't compile! Let's break down what's happening here in detail.

First let's look at the assign function:

All it does is take a mutable reference and a value and overwrite the referent with it. What's important about this function is that it creates a type equality constraint. It clearly says in its signature the referent and the value must be the exact same type.

Meanwhile, in the caller we pass in &mut &'static str and &'world str.

Because &mut T is invariant over T, the compiler concludes it can't apply any subtyping to the first argument, and so T must be exactly &'static str.

This is counter to the &T case:

where similarly a and b must have the same type T. But since &'a T is covariant over 'a, we are allowed to perform subtyping. So the compiler decides that &'static str can become &'b str if and only if &'static str is a subtype of &'b str, which will hold if 'static <: 'b. This is true, so the compiler is happy to continue compiling this code.

As it turns out, the argument for why it's ok for Box (and Vec, HashMap, etc.) to be covariant is pretty similar to the argument for why it's ok for lifetimes to be covariant: as soon as you try to stuff them in something like a mutable reference, they inherit invariance and you're prevented from doing anything bad.

However Box makes it easier to focus on the by-value aspect of references that we partially glossed over.

Unlike a lot of languages which allow values to be freely aliased at all times, Rust has a very strict rule: if you're allowed to mutate or move a value, you are guaranteed to be the only one with access to it.

Consider the following code:

There is no problem at all with the fact that we have forgotten that hello was alive for 'static, because as soon as we moved hello to a variable that only knew it was alive for 'b, we destroyed the only thing in the universe that remembered it lived for longer!

Only one thing left to explain: function pointers.

To see why fn(T) -> U should be covariant over U, consider the following signature:

This function claims to produce a str bound by some lifetime 'a. As such, it is perfectly valid to provide a function with the following signature instead:

So when the function is called, all it's expecting is a &str which lives at least the lifetime of 'a, it doesn't matter if the value actually lives longer.

However, the same logic does not apply to arguments. Consider trying to satisfy:

with:

The first function can accept any string reference as long as it lives at least for 'a, but the second cannot accept a string reference that lives for any duration less than 'static, which would cause a conflict. Covariance doesn't work here. But if we flip it around, it actually does work! If we need a function that can handle &'static str, a function that can handle any reference lifetime will surely work fine.

Let's see this in practice

And that's why function types, unlike anything else in the language, are contravariant over their arguments.

Now, this is all well and good for the types the standard library provides, but how is variance determined for types that you define? A struct, informally speaking, inherits the variance of its fields. If a struct MyType has a generic argument A that is used in a field a, then MyType's variance over A is exactly a's variance over A.

However if A is used in multiple fields:

If all uses of A are covariant, then MyType is covariant over A

If all uses of A are contravariant, then MyType is contravariant over A

Otherwise, MyType is invariant over A

PhantomData

When working with unsafe code, we can often end up in a situation where types or lifetimes are logically associated with a struct, but not actually part of a field. This most commonly occurs with lifetimes. For instance, the Iter for &'a [T] is (approximately) defined as follows:

However because 'a is unused within the struct's body, it's unbounded. Because of the troubles this has historically caused, unbounded lifetimes and types are forbidden in struct definitions. Therefore we must somehow refer to these types in the body. Correctly doing this is necessary to have correct variance and drop checking.

We do this using PhantomData, which is a special marker type. PhantomData consumes no space, but simulates a field of the given type for the purpose of static analysis. This was deemed to be less error-prone than explicitly telling the type-system the kind of variance that you want, while also providing other useful things such as auto traits and the information needed by drop check.

Iter logically contains a bunch of &'a Ts, so this is exactly what we tell the PhantomData to simulate:

and that's it. The lifetime will be bounded, and your iterator will be covariant over 'a and T. Everything Just Works.

Generic parameters and drop-checking

In the past, there used to be another thing to take into consideration.

This very documentation used to say:

Another important example is Vec, which is (approximately) defined as follows:
Unlike the previous example, it appears that everything is exactly as we want. Every generic argument to Vec shows up in at least one field. Good to go!
Nope.
The drop checker will generously determine that Vec<T> does not own any values of type T. This will in turn make it conclude that it doesn't need to worry about Vec dropping any T's in its destructor for determining drop check soundness. This will in turn allow people to create unsoundness using Vec's destructor.
In order to tell the drop checker that we do own values of type T, and therefore may drop some T's when we drop, we must add an extra PhantomData saying exactly that:

But ever since RFC 1238, this is no longer true nor necessary.

If you were to write:

then the existence of that impl<T> Drop for Vec<T> makes it so Rust will consider that that Vec<T> owns values of type T (more precisely: may use values of type T in its Drop implementation), and Rust will thus not allow them to dangle should a Vec<T> be dropped.

When a type already has a Drop impl, adding an extra _owns_T: PhantomData<T> field is thus superfluous and accomplishes nothing, dropck-wise (it still affects variance and auto-traits).

(advanced edge case: if the type containing the PhantomData has no Drop impl at all, but still has drop glue (by having another field with drop glue), then the dropck/#[may_dangle] considerations mentioned herein do apply as well: a PhantomData<T> field will then require T to be droppable whenever the containing type goes out of scope).

for more, refer to the link at the beginning of the page.