When can a type be covariant

[Wildstorm1]

I’ve been descending down a rabbit hole after reading this in the documentation for NonNull:

If you’re not sure if you should use NonNull<T> , just use *mut T !

I understand that making your type invariant by default is the safest option, and have read that for an interior mutable type to be sound it must be invariant, but it leaves me with the question: when can a type be covariant? If I am implementing something with NonNull, what should I be considering to determine whether I should allow the type to be covariant? When should a type be invariant?

[steffahn]

For completeness of your options:

• the safe approach if you really aren’t sure would generally be to make T invariant
• when you want to have the niche for non-null-pointers (e.g. a type using NonNull can be wrapped in an Option without any space overhead, because the pointer’s null-value can be used for None), you can still have invariance by adding an additional PhantomData<*mut T> field for example

Furthermore, if your type’s API is very similar / comparable to existing API from the standard library, you could follow those examples for variance. E.g. &mut T is invariant; &T is covariant; Box<T> is also covariant (in all cases, I’m talking about the variance with respect to T).

Covariance for T is generally usable when the T value is either immutably borrowed or uniquely owned. Shared mutable access (or interior mutability) usually means you need invariance.

---

Let’s look at the general pattern of unsoundness, with a type Foo<T> that offers mutable access to T and can be shared.

First, for context, what is covariance here?

• subtyping e.g. of &'static u8 being a subtype of &'a u8 (here, 'a denotes some shorter lifetime that isn’t 'static) allows for no-op coercion in one direction
  • you are allowed to convert &'static u8 into &'a u8
  • you are not allowed to convert &'a u8 into &'static u8
    • if you were allowed, you could easily access a reference after its target might have already been freed or otherwise invalidated
• using for T these types &'static u8 and &'a u8, the Foo<T> being covariant means, by definition, that the compiler allows no-op coercion in the same direction as the subtyping of the types used in the position of T do, i.e.
  • you are allowed to convert Foo<&'static u8> into Foo<&'a u8>
  • you are not allowed to convert Foo<&'a u8> into Foo<&'static u8>
• by contrast, if Foo<T> is invariant (with respect to T) then coercions between Foo<&'static u8> and Foo<&'a u8> become impossible; and contravariance would mean that coercion in the opposite direction^[1] would be allowed

Now, with shared mutable access and covariance combined: do note that Foo<T> giving mutable access to T is supposed to mean that Foo<&'static u8> is giving access to the whole &u8 reference, it’s not about the u8.

1. Create a value of type let foo1: Foo<&'static u8>, putting some dummy &'static u8 reference into the Foo struct
2. Create a second let foo2: Foo<&'static u8> that shares mutable access to the same &'static u8 value as foo1 has
3. Use the coercion permitted by covariance to convert one of the two, say foo2, to the type Foo<&'a u8>
4. Use the mutable access to put a new short-lived reference so some short-lived data into the shared location via the coerced foo2: Foo<&'a u8>
5. Use the access provided through foo1: Foo<&'static u8> to read/copy out that same reference, but not with an incorrectly lengthened lifetime

(and then, to get actual UB…)

6. Drop foo2: Foo<&'a u8> so that the lifetime 'a is allowed to end
7. The short-lived data can be freed, since the type of foo1: Foo<&'static u8> doesn’t involve its lifetime anymore, and foo2 is gone
8. Use the &'static u8 reference that still points to the freed data.

---

But it’s not just shared mutability… Rust’s normal mutable references do offer unique/unaliased access; but they support “reborrowing”, so while two &mut T references to the same target can’t be used at the same time, they can still exist at the same time. In the step-by-step above, foo1 is completely unused after step 1 and until before step 5; and foo2 only exist in exactly this time foo1 is unused. So we can follow the same pattern whilst using unique, but re-borrowable mutable access.

---

If you’re interested, why don’t you go ahead and write a little test program; for me that’s always a fun exercise: (click to expand)

• use NonNull<T> in a struct that models &'a mut T, let’s call it struct MyMutableReference<'a, T>.
• give it some small, but reasonable API, including DerefMut and a conversion from &'a mut T
• write it in a way that ”forgets“ to make T invariant
• then write a program that uses this API to follow the 8 steps above for triggering UB
  • the type of MyMutableReference<'a, T> takes the role of Foo<T>
    • the lifetime 'a here is not the same lifetime as the lifetime 'a of &'a u8 in the abstract step-by-step Foo example above
    • the inner lifetime parameter of the &'a u8 will likely not have any name at all in your program; you can probably just let type inference do its thing, at most needing something like a re-assignment of let foo2: MyMutableReference<'_, &u8> = foo2 to allow the coercion
    • only DerefMut and conversion from &'a mut T might not be enough; feel free to add more API as needed^[2]
  • you can use the tool miri can help detecting less obvious cases of UB
  • just for fun, try to find a setting where there’s also some very clear actual UB, e.g. printing of corrupted data
    • or a segfault?
• finally, make the necessary change to achieve invariance in T
• check that your exploiting program now fails to compile

---

As a slight generalization, you also need to look out for possible API-usage patterns that involve multiple types, i.e. foo1 and foo2 have different types, which do however still offer shared mutable access.

Also note that foo1 didn’t need to give us any mutable access itself; it was used read-only in step 5; on the other hand, foo2 didn’t need to give us any read access, it was used write-only in step 4. Finally, only the covariance of foo2, the value with write-access, was problematic. So if they do have distinct types, foo1 is allowed to be covariant.

---

Some interesting examples for subtle cases I’ve had to think about recently:

#1: In the context of Rc & Arc: (click to expand)

• the types Rc<T> and Arc<T> do offer mutable access to the contained value in certain cases, but they are covariant
  • they achieve soundness by only allowing mutable access when the reference-count is exactly 1, preventing the sharing part
  • these APIs do need to consider (and do consider) Weak pointers^[3]. If you were allowed to mutate through Arc, and then read through an upgraded, aliasing Weak, the 5-step (or 8-step) exploitation from above works again
  • this stuff is subtle; just recently, a new (unstable) API needed some fixing because it didn’t consider the Weak pointers sufficiently

#2: In the context of Vec and the iterator struct that its .drain() method returns: (click to expand)

• the type vec::Drain<T> is covariant in T, but also (re-)borrows mutably from another Vec; this sounds dangerous, and it does become subtle again
  • the API soundness relies on the argument that while the whole Vec is shared, the ownership story of the Vec elements is simpler: they are owned by the Drain and have no way of staying in the Vec after the draining… (even when the Drain is leaked; they do some leak-propagation)
  • update time!! along comes a new, shiny unstable API .keep_rest(); with it, some non-drained elements can be left in the original Vec.
    • however, the API of Drain doesn’t actually offer full mutable access to the elements; the only kind of mutation is “consume an element from the Vec” (through the iterator interface), so the ownership of each element is still simple; it starts out in a shared, but immutable (through the vec::Drain struct) state, and then you can transfer ownership of each element once per element only, one-way (through the iterator API)
    • the access to not-yet-transferred APIs really are accessible, because there’s another relevant point of API, a .as_slice() method. When it was created, the sentiment was that an .as_slice_mut() version of this method would be doable, too (just there wasn’t demand for it at the time), but if you could follow the discussion so far, you might be able to see why – at least in combination with .keep_rest() – that would no longer be sound
      • bonus question: would you think, .as_slice_mut() is also unsound without the .keep_rest() method present?^[4]

These examples are admitedly complicated,^[5] but I hope to be able to demonstrate that things in fact can be complicated, and it’s good to be cautions ~ if there’s any hint of sharing or reborrowing going on across your API, and there’s also some form of mutable access that’s allowed, then invariance can be a good safe choice.

In many cases you do have examples where your NonNull<T> is just used in a relatively straightforward manner; perhaps it’s uniquely-accessed like Box; or used only immutably; or on the contrary, there can be some very clear aspect of shared/reborrowed mutable access in your API.

They demonstrate how multiple types being involved can complicate the situation. As always, when using unsafe in Rust, the ultimate relevant definition is the notion of “soundness”. For answering “can my type be covariant?”^[6] then you really need to be answering “can my type be covariant soundly?” And soundness means that your whole public API, combined with the public API of the standard library, and most of the ecosystem, can be (ab-)used by any (possibly quite complicated, and intentionally exploitative) safe Rust code (that is, “safe” as in: the user code not using unsafe)^[7] to cause UB. Which is like really really hard to be actually sure of; and also often subtle because often, only combining multiple individually-sound parts of an ABI will be what introduces unsoundness.

---

1. with contravariance, it would be allowed to convert Foo<&'a u8> into Foo<&'static u8> ↩︎

2. or try to build a multi-type version – see the “slight generalization” in the next section – to create a program that really needs only those two points of API ↩︎

3. either failing on their presence or irreversibly disabling all remaining Weak pointers ↩︎

4. you can find the answer here ↩︎

5. I find them fun to think about though; and they are things I have interacted with relatively recently – but they are also quite subtle (though you don’t need to be able to discove such issues yet, just in order to understand it, when it’s pointed out and explained slowly) ↩︎

6. if your code also uses unsafe ~ but with NonNull that’s usually a given ↩︎

7. though more generally, by “safe code” one might also want to include any clearly sound unsafe code; in particular usage of unsafe functions that clearly upholds all documented preconditions for those APIs ↩︎