Contravariance and borrow checking

1

Shower thought:

Consider a method with a signature like

// lifetimes shown for clarity
fn method<'a>(&'a self) -> TypeWithLifetime<'a>;

The borrow-checker considers the TypeWithLifetime<'a> to extend the "loan" associated with &'a self for as long as the TypeWithLifetime is alive, preventing anything else from mutably borrowing self during that time.

But why? From the signature alone, there's no way of telling why this lifetime appears in TypeWithLifetime, so who says it carries anything with that lifetime? Does the compiler simply assume that every lifetime in the output of a function must extend borrows with those lifetimes from the input arguments?

Are there cases where this does not occur? Perhaps if...
...perhaps if TypeWithLifetime<'a> is contravariant over 'a?

Indeed, after testing it, it appears that this is the case.

Here's some types with variance types of various types of variance:

type Cov<'a> = &'a ();
type Contra<'a> = fn(&'a ());

 // compile-time tests just to make sure
fn verify_covariance<'a, 'b:'a>(c: Cov<'b>) -> Cov<'a> { c }
fn verify_contravariance<'a, 'b:'a>(c: Contra<'a>) -> Contra<'b> { c }

// and some methods
struct Struct;
impl Struct {
    fn cov_mut(&mut self) -> Cov { &() }
    fn contra_mut(&mut self) -> Contra { |_| () }
}

We can see that cov_mut and contra_mut are held to different standards by the borrow checker:

fn main() {
    let mut x = Struct;

    {
        // This is forbidden. `a` and `b` both borrow from `x`.
        let a = x.cov_mut();
        let b = x.cov_mut();
    }

    {
        // This is okay. `a` and `b` do not borrow from `x`.
        let _a = x.contra_mut();
        let _b = x.contra_mut();
    }
}

Unless I am misinterpreting these results, the borrow checker indeed uses variance to determine whether a returned type extends the borrow.

This appeals to my intuition as a PL enthusiast; there is some inherent connection between covariance and the availability of data (i.e. supplying some type T), while contravariance tends to indicate a sort of "data hole" (i.e. demanding some type T). But I'm still surprised to see the borrow checker make this connection, and I almost can't help but wonder if there is some way to fool it...

Any thoughts on this?

2

It is pretty cool - and I've no idea how it is dealt with in the compiler. But I don't think it's a new problem to be solved - any language with generics, subtypes, and types which can be contravariant (or invariant) already has to deal with this.

I wonder if there's any value in type declarations including whether their parameters are co/contra/in-variant? It would take some of the mystery out of using them. It's also not a syntax feature I've seen in any language before.

3

Subtyping and Variance makes it sound as though variance of standard library items are just hand-coded, and that it's not possible for user code to introduce any further contra-/invariance? From the last paragraph:

A struct, informally speaking, inherits the variance of its fields. If a struct Foo has a generic argument A that is used in a field a, then Foo's variance over A is exactly a's variance. However this is complicated if A is used in multiple fields.

  • If all uses of A are variant, then Foo is variant over A
  • Otherwise, Foo is invariant over A
4

Scala explicitly annotates variance of generics. Variances | Tour of Scala | Scala Documentation

class Foo[+A] // A covariant class
class Bar[-A] // A contravariant class
class Baz[A]  // An invariant class

// Covariant
trait Iterator[+A] {
  def hasNext(): Boolean
  def next(): A
}

// Contravariant
abstract class Printer[-A] {
  def print(value: A): Unit
}

// Invariant
class Container[A](value: A) {
  private var _value: A = value
  def getValue: A = _value
  def setValue(value: A): Unit = {
    _value = value
  }
}
1 Like
5

I suspect (but don't know for sure) that the notion of inheriting variance from fields is probably something well-understood in PL theory. My guess is that this gives the maximal amount of flexibility for a product or sum type.

Technically speaking, a user can further restrict the variance of their type through the effective use of PhantomData fields; to my understanding, this is one of the main reasons why PhantomData exists in the first place. (the other being for auto traits) However, usually these are private, making variance one of the very few "invisible backcompat hazards" in rust that can cause build failures in a downstream crate without affecting any public signatures in the upstream crate.

(in practice, I think that changing the variance of a type parameter in rust is such an exceedingly rare event that this is not really a problem. Even if you replaced some private field of type ConcreteThing<T> with an assocated type <T as Trait>::Something (which is invariant in T), you'll probably need to add T: Trait to the type's public signature)

6

No, the compiler devs are brilliant.

Playing around a bit I seemed to make code that defied basic lexical lifetime of variable. (It instead gets its borrow lifetime restriction from a higher variable.)

(I wonder if there is much use of non-hrtb contravariance functions.)

7

FYI, I think the exact rules governing the behavior you’re seeing are part of the ‘well-formedness’ rabbit hole:

https://github.com/rust-lang/rfcs/blob/master/text/1214-projections-lifetimes-and-wf.md

...But I’m not really sure, because based on that RFC I’d expect the contravariant version to fail as well, despite (at least seemingly) not being unsound.

1 Like
8

What part of that RFC leads you to believe that?

9

Auto traits don’t need PhantomData AFAIK. PhantomData exists so you can express the variance of types and lifetimes that are purely type level - there’s no field that uses them. That, in turn, is needed so the compiler can understand the variance of the type.

10

I’m curious why you think this is surprising given the contravariant version returns a type that doesn’t borrow from the input, as you mentioned. In other words, how is it really different from fn foo(&mut self) -> String? The contravariant version does bound the lifetime of the argument that the fn accepts but otherwise it seems fairly expected that borrow of self is not extended. Or did I miss some subtlety you were expressing?

11

I was referring to the practice of using a PhantomData<Rc<()>> field to opt-out of Send and Sync. cpython uses this trick in its type for the GIL (global interpreter lock).

12

Yes that’s used sometimes. You can also just impl !Send and !Sync for the type so it’s not strictly needed.

13

No you can't. Try it.

14

Ah you’re right - requires nightly + feature gate :frowning:

15

I’m curious why you think this is surprising given the contravariant version returns a type that doesn’t borrow from the input, as you mentioned.

Both functions have the same form.

fn function_1<'a>(&'a mut self) -> Type1<'a>;
fn function_2<'a>(&'a mut self) -> Type2<'a>;

Since there aren't many things that rust decides through global analysis, in most cases in rust that would almost certainly mean that the functions are interchangeable in any caller, as long as you use the output in a way that imposes no constraints on its type. (i.e. like store it in a local and never touch it...)

We can see that this is not the case here. How does the borrow checker determine that one of the output types borrows the data, and the other does not? Clearly, it must be relying on one of those few properties that isn't reflected in the signature. I assume it is variance. (Perhaps it is something else even more subtle than variance. That sounds scary!)

fn function_1<'a>(&'a mut self) -> Type1<(+)'a>;
fn function_2<'a>(&'a mut self) -> Type2<(−)'a>;

Assuming my conclusion is correct, I am simply surprised to see that variance directly plays a role in deciding whether Type1 and Type2 are considered to hold a borrow with lifetime 'a.

16

Can you show me the two types like that? I don’t think such a thing exists - your original example uses an fn which has higher rank lifetimes so to speak. But I don’t think you can create structs Type1<'a> and Type2<'a> that do not extend the borrow short of using the same fn inside of them. But that fn inside (presumably) just means that the struct has no borrow of anything itself but rather a higher rank like aspect to it - similar to how String has no borrow of anything although it doesn’t have a lifetime parameter at all.

17

Can you show me the two types like that?

struct Cov<'a>(&'a ());
struct Contra<'a>(fn(&'a ()));

impl Struct {
    fn cov_mut(&mut self) -> Cov { Cov(&()) }
    fn contra_mut(&mut self) -> Contra { Contra(|_| ()) }
}

All other things kept the same

18

Right - I mentioned above that the struct should not just hold an fn.

19

To my knowledge, fn is the only way to create contravariance.

As far as I know, fn(&'a ()) is not higher-ranked. Note there is another type, for<'a> fn (&'a ()) (yes, this is stable syntax, using HRTB to describe a type and not a trait bound!), which is higher-ranked.

20

By the way, did you look at @Jonh's playground? At the bottom he has an example of tying a borrow to the 'a in a contravariant type, and using it to produce a "borrowed while mutably borrowed" error.

I think.