Implied bounds / well-formedness of references treats contravariant lifetimes the same as covariant

[Manishearth]

Potentially related to #25860 . The issues seem related but the examples are pretty different so I figured I'd file this as separate.

I'm not yet sure if I can craft an actual self-contained soundness bug out of this, but it does cause a soundness bug in Yoke which relies on for<'a> working correctly: unicode-org/icu4x#2926. I have multiple potential fixes for the yoke issue, but it's worth at least noting.

TLDR: Rust currently correctly implies a 'inner: 'outer bound when you have &'outer &'inner _. It is also incorrectly implying this for &'outer fn(&'inner _)

The reduced example is as follows:

// A function that forces the closure to work for ALL lifetimes
// ... or does it?  };-)
fn attach<C, F>(cart: Box<C>, transform: F) where F: for<'all> FnOnce(&'all C) -> &'all str {
    // could call f(&cart);, etc
}

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

fn contra_shorter<'contra, 's: 'contra>(param_contra: Contra<'contra>, param_s: &'s str) {
    let contravariant_cart = Box::new(param_contra);
    attach(contravariant_cart, |_| param_s);
    
}

(playpen)

This should not compile. F requires the returned string to be valid for ALL lifetimes 'all, whereas we're returning a string of lifetime 's

This code is behaving the same as this code:

fn co_shorter<'co, 's: 'co>(param_co: &'co u8, param_s: &'s str) {
    let covariant_cart = Box::new(param_co);
    attach(covariant_cart, |_| param_s);
}

where the concrete type of F is for<'all> FnOnce(&'all &'co u8) -> &'all str, and well-formedness implies that 'all must be shorter than 'co, so you end up getting a 'co: 'all bound, and 's: 'co ends up giving us 's: 'all, so even though there is a for<'all>, the 'all is actually artificially restricted to being "for all shorter than 'co" and returning data of lifetime 's is valid there.

(the 's: 'co is actually not necessary for co_shorter() to compile, but it's easier to explain that way)

---

Basically, for &'outer Foo<'inner>, the implied bound probably should be:

• For covariant Foo: 'inner: 'outer
• For contravariant Foo: Nothing
• For invariant Foo: 'inner: 'outer, or nothing

Basically the implied bound is safe when things are guaranteed to not be contravariant. It's actually fine to have the implied bound for e.g. the invariant case of &'outer Cell<'inner _>, because a cell is logically a tuple of a covariant getter and contravariant setter, and the setter implies no bounds but the getter can imply bounds.

This does give me some pause since typically we tend to believe that code that works on invariant types will also work on contravariant types, and here's a situation where it won't; so perhaps it's safer to also opt invariant lifetimes out of this. Idk.

Contravariant types could imply the bound 'outer: 'inner because function parameters can't live for less than the function does, but I'm not sure this implied bound is ever useful. Does lead to a nice symmetry though.

The Yoke bug (unicode-org/icu4x#2926) only shows up for contravariance due to how Yoke is structured. It's not clear to me that there's a way to write an unsafe abstraction that relies on for<'a> being truly universal where an implied bound coming from an invariant type may cause unsoundness. But I could be wrong.

---

A further exploration can be found in this code (playpen):

Show code

// A function that forces the closure to work for ALL lifetimes
// ... or does it?  };-)
fn attach<C, F>(cart: Box<C>, transform: F) where F: for<'all> FnOnce(&'all C) -> &'all str {
    // could call f(&cart);, etc
}

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


fn main() {
    // create a Box<&'a _> with a longer lifetime than s ('a_longer; where `'a_longer: 's`)
    let local_longer = vec![1,2,3,4];
    let covariant_cart_longer: Box<&'_ [u32]> = Box::new(&*local_longer);
    
    // let's say this has lifetime 's
    let s = String::from("hello");
    
    
    // Create a Box<Contra<'contra>>, contravariant over 'contra
    let contravariant_cart: Box<Contra<'_>> = Box::new((|_| ()) as Contra);
    
    
    // Create a Box<_> that is fully owned
    let owned = vec![1,2,3,4];
    let owned_cart = Box::new(owned);
    
    // create a Box<&'a _> with a shorter lifetime than s ('a_shorter, where `'s: 'a_shorter`)
    let local_shorter = vec![1,2,3,4];
    let covariant_cart_shorter: Box<&'_ [u32]> = Box::new(&*local_shorter);  
    


    // does not compile, &s cannot produce &'all str for ALL 'all
    //
    // attach(owned_cart, |_| &s); 



    // This does compile, because in the bounds for F, `&'all C` is `&'all &'a_longer [u32]`, which forces
    // 'all to be shorter than 'a_shorter due to well-formedness / implied bounds (`'a_shorter: 'all`), reducing the for<'all> in scope
    // which works just fine for &s since 's is longer than 'a_shorter (`'s: 'a_shorter`) implying that `'s: 'all`
    attach(covariant_cart_shorter, |_| &s);
    
    
    
    // Seems like it shouldn't work, because the reason from before doesn't seem apply: even if 'all is forced to be shorter than 'a_longer,
    // there is still a period of time where 'a_longer is valid but 's is not, so the closure shouldn't compile.
    //
    // However, rustc is smart! It knows that it can make it work by squeezing 'a_longer *until* it is shorter than 's (`'s: 'a_longer`), and then WF rules force
    // us back into 'all being short (`'a_longer: 'all`), which brings us back to the previous situation; `'s: 'all`
    attach(covariant_cart_longer, |_| &s);
    

    // works, but shouldn't. 'contra is being selected to be *something*, and that somehow impacts WFness enough to
    // restrict the range of the for<'all>
    //
    // Without knowing WF rules for functions for sure, the clear answer is that *if* there are WF rules for functions, they would apply outside-in, not inside-out,
    // i.e. &'all fn(&'contra) would restrict 'contra to live at least as long as 'all, not vice versa.
    // This is unhelpful for us since we still have compiling code where &'s str is somehow a valid `for<'all> &'all str`; we MUST restrict 'all somehow
    //
    // To poke at this further without the problem of rustc picking some lifetime for 'contra, let's give it a named lifetime in two methods below:
    attach(contravariant_cart, |_| &s);
    
}

// First let's just give it a named lifetime
fn contra_longer<'a>(param_contra: Contra<'a>) {
    let contravariant_cart = Box::new(param_contra);
    let s = String::from("hello");
    // doesn't work, &s cannot produce &'all str for ALL 'all
    // huzzah!
    // attach(contravariant_cart, |_| &s);
    
}

// Now let's give it *and* s named lifetimes, and say that 's lives at least as long as 'contra
fn contra_shorter<'contra, 's: 'contra>(param_contra: Contra<'contra>, param_s: &'s str) {
    let contravariant_cart = Box::new(param_contra);
    // ... does work, but shouldn't
    // this is the same behavior as that for covariant lifetimes, clearly
    // the WF rules are assuming covariance somehow;
    //
    // the previous function fails to compile because 's lives 
    // less than 'contra, so we have a case similar to that of `covariant_cart_shorter` but this time the
    // covariance cannot come to the rescue
    attach(contravariant_cart, |_| param_s);
    
}

The line attach(contravariant_cart, |_| &s); should not compile, nor should the function contra_shorter(). contra_longer() happens to correctly fail to compile because the same variance trick that saves covariant_cart_shorter does not apply here.

cc @pnkfelix @lcnr

Thanks to @workingjubilee for rubberducking this with me.

[Manishearth]

From talking to @BoxyUwU; there's an alternate way to look at this:

• &'outer C implies C: 'outer
• C: 'outer implies Contra<'inner>: 'outer when C is Contra<'inner> (fn(&'inner _))
• Contra<'inner>: 'outer implies 'inner: 'outer

This all makes sense and is consistent. The tricky thing is the first line: implied bounds come from well-formedness, and there's not an actual WF reason for contravariant lifetimes to behave that way: &'outer fn(&'inner _) does not need any particular bounds to be valid.

In fact, the syntax C: 'outer when lifetimes contained in C are contravariant is itself kinda tricky, because it both means "all lifetimes contained in C outlive 'outer" and it means "all borrows contained in C outlive 'outer", but these mean different things when you're talking about contravariant lifetimes. In general in Rust it means the former, but the ambiguity can be confusing.

I think the real issue here is:

• Implied bounds are completely undocumented, but they come from "well formedness"
• There is obviously a WF reason for &'outer &'inner _ to imply 'inner: 'outer. There is not one for the equivalent contravariant type. T
• Implied bounds do affect universal quantification
• Unsafe code may rely on universal quantification in ways that implied bounds will mess with it

We should probably better document implied bounds, and consider relaxing how they work around contravariant lifetimes.

(as far as the Yoke issue, I do have a fix I can apply; though I'd rather not have to, I know it's going to take a while for there to be motion on this in any direction)

[Manishearth]

FWIW I'm happy to sit down and document WF/implied bounds if someone can tell me where it should go and help me with specifics, like, which things are WFness and which bounds are implied.

[aliemjay]

• There is obviously a WF reason for &'outer &'inner _ to imply 'inner: 'outer. There is not one for the equivalent contravariant type.

I don't think this is an issue with variance. The real issue here is that all lifetimes that appear on trait objects and fn pointers are treated as "outlives components" of the underlying type. This can occur with invariant and covariant lifetimes as well. Here is an example with invariant lifetime 'a:

trait Trait<'a> {}
fn test<'a>(_: &'static dyn Trait<'a>) { // implies 'a: 'static !!
    None::<&'static &'a ()>; // check 'a: 'static
}

This might not be desired and can lead to surprising behavior, like dyn Fn(&'a str) -> &'a str + 'static is not really static unless 'a: 'static, but it's not really a soundness bug, I believe.

• Implied bounds do affect universal quantification

• Unsafe code may rely on universal quantification in ways that implied bounds will mess with it

Universal quantifiers for trait bounds is bounded by the condition that trait input types must be well-formed. For example, the trait bound for<'a> Fn(&'a T) actually means for any lifetime 'a such that &'a T is well formed, and this may not include 'static.

[workingjubilee]

I don't think this is an issue with variance. The real issue here is that all lifetimes that appear on trait objects and fn pointers are treated as "outlives components" of the underlying type.

That is in fact what is being referred to here with respect to "variance", as the actual way of expressing this conversation involves wheeling out predicates in a language that is not Rust (logic) because Rust only interprets lifetime bounds in contextual manners... i.e. variance... and thus having an overly consistent behavior in terms of creating outlives requirements here is inconsistent with how the lifetimes in question are read and written.

That is a problem whether or not it is a strict "soundness issue" in the compiler, because the underlying thesis of Rust is that the combination of unsafe code with lifetimes can be used to create programs that constrain behavior to what is sound. And that means it needs to, as much as possible, not fall down into a pile of miserable edge-cases when it comes to actually trying to do that.

[workingjubilee]

I have fixed the tags. The categories are made for humanity, humanity was not made for the categories. Let's not bog down this issue's comment thread with further haggling over whether it is "unsound" or merely "surprising", please.

[steffahn]

I don’t see good ways to change the current behavior here, but feel free to point out where I might not be seeing the way out.

The proposition of this issue – or perhaps feature request – is that for<'a> FnOnce(&'a Foo<'b>) should mean, in some sort of pseudo-syntax adding where clauses to the for:

• for<'a, where 'b: 'a> FnOnce(&'a Foo<'b>) if Foo<'b> is covariant in 'b (unchanged case, as is status quo),
• for<'a /* unbounded, for all 'a */> FnOnce(&'a Foo<'b>) if Foo<'b> is contravariant in 'b (instead of the status quo, where this case is the same as the covariant case), and
• something sensible for the invariant case.

If the invariant case where for<'a, where 'b: 'a> FnOnce(&'a Foo<'b>) as well, then changing Foo<'b> from being invariant to being contravariant in 'b would become a breaking change, because the body a closure implementing this trait bound could stop compiling if it relies on the 'b: 'a bound. Turning a type from invariant into contravariant is not supposed to be breaking AFAIK, so that would be problematic.

So I guess the invariant case would need to become for<'a /* unbounded, for all 'a */> FnOnce(&'a Foo<'b>), too?

But then implementing such a closure could become next to impossible in the invariant case: If the closure body did not get to infer 'b: 'a, then &'a Foo<'b> might not be a well-formed type at all; so how are we able to have it in the signature, or have variables of the same type, or of related types in the closure body?

As far as I can tell, the proposed argument here might be that we want something like fn(&'a ()): 'static to be universally true, which is something that I’ve seen in previous discussions, but as far as I remember it was more about a “fn-pointers are special” kind of idea, and less of a “contravariant lifetimes are special” idea.

Even if we made sure that every contravariant (in 'b) type Foo<'b> would not require 'b: 'a for &'a Foo<'b> to be well-formed, the same will be impossible for invariant types Foo<'b>, because those can actually really contain references of that specific lifetime.

For illustration: For example, if struct Struct<'b>(fn(&'b (), &'b i32) (which is invariant in 'b) did not require 'b: 'a for a &'a Struct<'b> reference type to be allowed, then either

• a impl Struct<'_> { fn bar(&self) -> &i32 { self.1 } } method couldn’t be called on such a reference without requiring 'b: 'a after all, in which case a for<'a> FnOnce(&'a Struct<'b>) closure implementation that calls bar (with the full lifetime of the &'a Struct<'b>) would break / no longer compile
• a impl Struct<'_> { fn bar(&self) -> &i32 { self.1 } } method could be called on &'a Struct<'b> references without 'b: 'a bound, but would most likely be unsound (unless other language changes would rule out all straightforward ways of exploiting this; though I don’t quite see how that could be done without yet-again causing breaking changes somewhere (for existing and reasonable code).