can't store static references in a Unique indirectly

[blaenk]

EDIT: Removed talk of variance, since it doesn't seem to be the cause and it was unnecessarily longer due to it.

It seems to me like 801bc48 is an attempt to introduce the second approach from the unresolved questions of RFC 738.

Rewrite safe abstractions to use *const (or even usize) instead of *mut, casting to *mut only they have a &mut self method. This is probably the most conservative option.

It seems to me that the commit is actually a breaking change, because it broke my code without my changing it. Consider this reduced example (thanks to @p1start for helping me to reduce it further).

pub struct Node<V> {
    vals: V,
    edges: ::std::ptr::Unique<Node<V>>,
}

fn is_send<T: Send>() {}

fn main() {
    is_send::<Node<&'static ()>>();
}

This overflows on the recursive requirement evaluation:

<anon>:16:5: 16:33 error: overflow evaluating the requirement `Node<&()> : core::marker::Send` [E0275]
<anon>:16     is_send::<Node<&'static ()>>();
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
<anon>:16:5: 16:33 note: consider adding a `#![recursion_limit="128"]` attribute to your crate
<anon>:16     is_send::<Node<&'static ()>>();
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
<anon>:16:5: 16:33 note: required because it appears within the type `Node<&()>`
<anon>:16     is_send::<Node<&'static ()>>();
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
<anon>:16:5: 16:33 note: required because it appears within the type `Node<&()>`
<anon>:16     is_send::<Node<&'static ()>>();
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
<anon>:16:5: 16:33 note: required because it appears within the type `Node<&()>`
<anon>:16     is_send::<Node<&'static ()>>();
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
<anon>:16:5: 16:33 note: required because it appears within the type `Node<&()>`
<anon>:16     is_send::<Node<&'static ()>>();
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
<anon>:16:5: 16:33 note: required because it appears within the type `Node<&()>`
<anon>:16     is_send::<Node<&'static ()>>();
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
[... truncated ...]

I attempted to bump the recursion limit to 2046 even and it just told me to try again with 4096, so I figure it's just going to infinitely recurse if allowed.

This only seems to happen if I use a &'static reference, so I think that has something to do with it.

@p1start came up with an example that actually hangs rustc completely when using a recursive type:

pub struct Node<V> {
    vals: V,
    edges: ::std::ptr::Unique<Node<V>>,
}

struct Foo<'a> {
    x: Box<Option<Node<(&'a (), Foo<'a>)>>>
}

fn is_send<T: Send>() {}

fn main() {
    is_send::<Foo>();
}

The real-world scenario that led me to this bug was a BTreeMap with &'static str keys:

use std::collections::BTreeMap;

fn is_send<T: Send>() {}

fn main() {
    is_send::<BTreeMap<&'static (), ()>>();
}

[blaenk]

cc @nikomatsakis @pnkfelix

[blaenk]

My suspicion (which I removed from the first post because I'm not quite sure if it's the reason) is that it has to do with variance. Creating my own Unique similar to the one in rust but with a *mut T instead of a *const T, OR with PhantomData<*mut T> instead of PhantomData<T> seemed to solve the issue, but again I'm not sure if that's the reason. I figured it was because *const T is ok to have as a covariant but *mut T must be an invariant, from my limited understanding of variance.

[nikomatsakis]

(More) reduced test case (reduced in that it's isolated from the stdlib):

use std::marker::PhantomData;

unsafe impl<T: Send + ?Sized> Send for Unique<T> { }
unsafe impl<T: Sync + ?Sized> Sync for Unique<T> { }

pub struct Unique<T:?Sized> {
    pointer: *const T,
    _marker: PhantomData<T>,
}

pub struct Node<V> {
    vals: V,
    edges: Unique<Node<V>>,
}

fn is_send<T: Send>() {}

fn main() {
    is_send::<Node<&'static ()>>();
}

there is in fact an interaction with variance. The problem is that the "infinite cycle" detection doesn't seem to be kicking in here because an endless set of new region variables are being generated. This is probably due to the variance of Send. I have to think on this a second.

[nikomatsakis]

(Er, the variance of various things. :)

[nikomatsakis]

So I've kind of thought this through. I think the right fix is to enhance the trait matching system to understand that there is in fact no need to keep generating new constraints. This seems to be a bit complicated (it interacts with, among other things, #21974).

The short-term pragmatic fix is probably to modify MarkerTrait to be invariant, not contravariant. This is stricter than necessary but probably not terrible. The implication is that if one knows that e.g. &'static T : Send holds, that alone would not be enough to conclude that &'a T : Send. It is probably possible for us to loosen this in the future, even after 1.0, though strictly speaking it would not be backwards compatible. (I guess a more limited fix would just be to change the variance of Send and Sync specifically.) (The reason it is not 100% backwards compat is because impls that are not overlapping for an invariant trait can overlap for a contravariant trait; but this is unlikely to occur except for with object types.)

[nikomatsakis]

I plan to work around this problem for now by changing the definition of MarkerTrait. The underlying issue has been splintered off into #22806.