Cell is unsound around variance

[pcwalton]

The following creates a dangling pointer to an outer stack frame:

use std::cell::Cell;

struct Foo<'a> {
    x: int,
    y: Cell<Option<&'a int>>,
}

fn f() -> Foo {
    Foo {
        x: 1,
        y: Cell::new(None),
    }
}

fn g<'a>(x: &'a Foo<'a>) {
    x.y.set(Some(&x.x));
}

fn h() -> Foo {
    let x = f();
    g(&x);
    x
}

fn main() {
    let x = h();
    // kaboom
}

This manifested as a rustc segfault.

[pcwalton]

cc @nikomatsakis

[bblum]

part of #3598

[nikomatsakis]

this is the surprising function, really:

fn h() -> Foo {
    let x = f();
    g(&x);
    x
}

Clearly this function ought not to type check. I'm not sure if this is due to some interaction with variance inference or something else, though I seem to recall another similar bug. I'll try to find some time to dig into this a bit.

[bblum]

i attempted converting this to not use cell:

struct Foo<'a> {
    x: int,
    y: Option<&'a int>,
}

fn f() -> Foo {
    Foo {
        x: 1,
        y: None,
    }
}

fn g<'a>(x: &'a mut Foo<'a>) {
    x.y = Some(&x.x);
}

fn h() -> Foo {
    let mut x = f();
    g(&mut x);
    x
}

fn main() {
    let _x = h();
}

and, as @pcwalton predicted, it wouldn't compile:

test.rs:19:7: 19:13 error: borrowed value does not live long enough
test.rs:19     g(&mut x);
                 ^~~~~~

but i don't understand why changing the mutability affects how the lifetime inference behaves.

[pnkfelix]

Accepted for 1.0, P-backcompat-lang.

[nikomatsakis]

Indeed inference is incorrect yielding contravariant for 'a rather than invariant. Not sure why yet.

[nikomatsakis]

Ah! I understand why. Interesting. Actually the inference is CORRECT, but it is being fed incorrect information. It does not know that cell mutates its value and thus is invariant. I had assumed this would be ok as we are generally invariant (right now, anyway) with respect to all type parameters, but the inference in fact computes variance correctly, and thus infers that Option and Cell are covariant with respect to their type parameter. It's just that the type system enforces a stricter standard. I remember thinking that this would be sound, but of course it's not when we haven't added proper variance notations to types like Cell. That is work which is overdue and fairly straightforward, so I'll try to do it. In some sense this is thus a dup of #10834 but I will leave it open since it reflects a specific failure we should test for.