Covariant, invariant and PhantomData; Why does this compile?

help
1 
use std::sync::atomic::{AtomicBool, AtomicPtr};
use std::marker::PhantomData;

#[allow(unused)]
#[derive(Default)]
struct Node<'b> {
    locked: AtomicBool,
    next: AtomicPtr<Node<'b>>,
    // _marker: PhantomData<*const ()>,
}

fn accept<'a, 'b>(_: &'a Node<'b>) {}

fn main() {
    let node: &'static Node<'static> = Box::leak(Box::new(Node::default()));
    accept(node);
}

hi, without this marker shouldn't the entire struct Node be invariant in T as AtomicPtr is placed inside the struct? the code still compiles tho, with the _marker field commented as it is currently shown...

2

that is incorrect. an additional field(like a marker) can only restrict the variance of a struct, never relax it.
so no matter wether you add the marker or not, the struct Node<'a> will always be invariant in 'a.

the code compiles no matter wether Node is invariant or not. it actually would compile even if references were invariant in their lifetime (they are not).
when you call accept, you are simply calling accept<'static, 'static>.

if you wantt to test variance, you should try something like the following :

fn check_covariant<'short>(_: &Node<'short>, _ : &'short mut u8) {}

that you call like so check_covariant(node, &mut 0)

3

The best check for covariance, IMO, is attempting to coerce *const *const Node<'long> to *const *const Node<'short>. The only coercion that can do that is a subtyping coercion relying on covariance.

4

"Why does this compile" has been answered, but I'll add some detail about how variance is determined.

The variance of 'b in Node<'b> is determined based on how 'b is used in the struct. PhantomData<*const ()> doesn't use 'b, so it doesn't influence the variance of 'b at all.

In this case, 'b is invariant in Node<'b> because AtomicPtr<T> is invariant in T.

If you replace the AtomicPtr<T> with Box<T>, which is covariant in T, you would get an error. Currently the error says 'b is unused, but the real error is that the compiler couldn't infer if 'b was invariant, covariant, or contravariant, because the definition has become recursive with 'b in a covariant position.[1]

  1. Technically it infers the lifetime as bivariant, but disallows bivariant lifetime parameters. ↩︎

5

If 'b is invariant in Node<'b> then this shouldn't compile, right? As 'short is something definitely smaller than 'static and if 'b was invariant in Node<'b> then in this case the compiler would require a lifetime that is exactly 'short (cause invariant), right?

use std::sync::atomic::{AtomicBool, AtomicPtr};
use std::marker::PhantomData;

#[allow(unused)]
#[derive(Default)]
struct Node<'b> {
    locked: AtomicBool,
    next: AtomicPtr<Node<'b>>,
    // _marker: PhantomData<*const ()>,
}

fn check_covariant<'short>(_: &Node<'short>, _ : &'short mut u8) {}

fn main() {
    let node = &Node::default(); // &'something Node<'something>
    let temp: &'static mut _ = Box::leak(Box::new(0)); 
    check_covariant(node, temp); 
}
6

i think you missed the part where i wrote

your temp is &'static mut, which is the opposite of short.
so when you call check_covariant, temp can implicitly get coerced to the lifetime of the node without issue, because &'a mut u8 is covariant in 'a.

Moreover, // &'something Node<'something> is incorrect, there is no reason to for the lifetimes to be linked in any way.
it is more
// &'local_stack Node<'anything_the_compiler wants>

and the 'anything_the_compiler wants is crucial : because you called default(), the compiler can choose any lifetimes, as long as it never changes, so it could just be 'static, so actually even if &'a mut u8 was also invariant in 'a it would still work

7

here is a version you can't use incorrectly as long as you don't try customizing it :

// only compiles if Node is covariant
fn check_covariant<'a>(r: *const *const Node<'a>, _ : &'a mut u8) {
    if false { check_covariant(r, &mut 0) }
}

no need to call it, just put it in your code, and if it compiles you're good. thanks @robofinch for the advice

8

No, 'short is a generic parameter. It can take on the "value" 'static, or any other duration. The only requirements in this code is that the duration of the outside reference is no longer than 'short...

//                            v call the elided lifetime `'r`
fn check_covariant<'short>(_: &Node<'short>, _ : &'short mut u8) {}
// There's an implied `'short: 'r` bound

(which is trivial to satisfy due to variance), and that the two 'short durations are equal.

In the call to the function:

    let node = &Node::default(); // &'something Node<'something>
    let temp: &'static mut _ = Box::leak(Box::new(0)); 
    check_covariant(node, temp);

'something is invariant in Node<'something> but otherwise needs only be valid at the call site, temp can be reborrowed or coerced to produce a &'something mut u8 due to variance, and the outer "'r" lifetime can be anything shorter than 'something.[1]

You can force 'something to be 'static with an annotation and it will still work.

The call requires temp to be reborrowed as or coerced to a &'something mut u8, but that's no problem since it's a &'static mut u8 and the lifetime of a &'_ mut T is covariant.[2] It can coerce to something with any lifetime, no matter how short.

Here's a version where the requirements that the two lifetimes be the same causes a compilation failure.

fn check<'short>(_: &Node<'short>, _ : &'short mut u8) {}

fn main() {
    let node = &Node::<'static>::default();
    let mut local = 0;
    let temp = &mut local;
    check(node, temp); 
}

The invariance of Node combined with the equality requirement means that the call requires temp to be a &'static mut u8, but that in turn would mean that local was still borrowed when it goes out of scope. The end result is a borrow checker error.

(As others discussed there are better setups for testing variance, but perhaps this will help you understand how the signature in question works.)

  1. there's nothing forcing it to be 'something exactly, incidentally; not at the declaration and not in the call ↩︎

  2. The T is invariant, but that's irrelevant here; u8 has no subtypes besides itself. ↩︎

9

there's actually a temporary value dropped while borrowed error...that's why I was always creating a temp hehe
also, this is *const T, so any lifetime that appears in T (which in this case is 'a) is covariant, right?

10

Could you please elaborate a bit more on this: why should both 'short durations be equal? thanks!

11

The fact they they are both 'short means that they are equal.

Why do x and y here have the same type?

fn example<T>(x: T, y: T) {}

Because they are both T.

Same idea.

Perhaps this confuses you:

fn check_covariant<'short>(_: &Node<'short>, _ : &'short mut u8) {}

fn example<'can_be_non_static>() {
    let node = &Node::<'can_be_non_static>::default();
    let temp: &'static mut _ = Box::leak(Box::new(0)); 
    // compiles successfully
    check_covariant(node, temp); 
}

When you pass in temp, a reborrow &mut *temp with lifetime 'can_be_non_static gets implicitly created. This happens because the caller is required to pass in two types with the same lifetime for some lifetime 'short -- that's what the check_covariant function signature requires. (Because of Node's invariance, 'short has to be 'can_be_non_static at the call site.)

It is not the case that you pass in a &Node<'can_be_non_static> and a &'static mut u8, even if it looks that way on the surface -- because that wouldn't meet the requirements of the function signature.

(Some learning material tries to explain borrow checking as if you were passing in different lifetimes for cases like this, but they are just trying to get the general idea across in a simple way, and not faithfully explaining how borrow checking and/or variance actually work.)

12

you have an error when Node is invariant, and no error when it is covariant, that's the whole point.

so the test for covariance correctly showed your struct was not covariant, and so you broke it ?

sounds counterproductive

no, *const T is just covariant over T.
so *const X<'a> is covariant over 'a if and only if X<'a> is covariant over 'a

13

what's the difference between being covariant over a type T vs being covariant over a lifetime thanks!

14

your explanations are always fantastic! thanks a lot!