Summary

This document is an analysis of Rust issue #42940. The issue is surprising but in the end boils down to being unable to name an appropriate lifetime when substituting for the generic parameters of an opaque type.

Background

Rust issue #42940 reports, in essence, the following odd discrepancy when 1) an opaque type captures a type parameter 2) but the hidden type does not use it and 3) the type parameter is substituted with a type that contains a reference created locally.

Opaque type outlives outer lifetime

This code works OK:

// Example 1.1
fn capture<'o, T>(_t: T) -> impl Send + 'o { () }

fn outlives<'a, T: 'a>(_t: T) {}
fn test<'o>(x: &'o ()) {
    outlives::<'o>(capture::<'o, &'_ &'o ()>(&x)); // OK!
}

Playground link

Rust is telling us that the returned opaque type outlives 'o, which is what we would expect, even though the opaque type captures T and, consequently, the reference created locally in the function, since the opaque type is specifically bounded by 'o and the hidden type is 'static.

Opaque type can escape caller dynamically

This code also works OK:

// Example 1.2
fn capture<'o, T>(_t: T) -> impl Send + 'o { () }

fn test<'o>(x: &'o ()) -> Box<dyn Send + 'o> {
    Box::new(capture::<'o, &'_ &'o ()>(&x)) // OK!
}

Playground link

Rust is willing to let the value escape to the heap and to let the corresponding Box escape up the stack. This makes intuitive sense given that the hidden type does not reference any local data from the function and the opaque type of capture has a specified bound that matches the bound on the dyn opaque type that we're returning from test.

Opaque type cannot escape caller statically

However, this seemingly similar code fails:

// Example 1.3
fn capture<'o, T>(_t: T) -> impl Send + 'o { () }

fn test<'o>(x: &'o ()) -> impl Send + 'o {
    capture::<'o, &'_ &'o ()>(&x)
//                            ^^
// ERROR: Borrowed value does not live long enough.
}

Playground link

That seems strange.

Analysis

The real problem

Let's break down that last example using type alias impl Trait (TAIT).

// Example 2.1
#![feature(type_alias_impl_trait)]

struct Dummy;

type PhantomCapture<'o, T> = impl Send + 'o;
fn capture<'o, T>(_t: T) -> PhantomCapture<'o, T> { () }

fn test<'o>(x: &'o ()) -> PhantomCapture<'o, Dummy> {
    //                                       ^^^^^
    //                  What should go here? ^
    capture::<'o, &'_ &'o ()>(&x)
}

Playground link

Immediately we can see the problem. There's no way to name the lifetime that we need to fill in for the type parameter T. The actual lifetime is only valid within the function.

Here's how to look at this:

The hidden type must outlive the lifetime specified in the bound of the opaque type. Since the hidden type is (), and (): 'static, and 'static: 'o, we can prove this is true.

To prove that the returned opaque type outlives some other lifetime, it's enough to prove that the specified bound on the opaque type outlives that lifetime. Does the returned opaque type outlive 'o? Since 'o: 'o, this is trivially provable.

The value returned by test does not reference any data owned by the current function. The error message is just wrong about that.

However, the type returned by test does reference a lifetime that's only valid within the current function. That's the real problem here.

Why boxing works

Continuing our example:

// Example 2.2
#![feature(type_alias_impl_trait)]

type PhantomCapture<'o, T> = impl Send + 'o;
fn capture<'o, T>(_t: T) -> PhantomCapture<'o, T> { () }

fn test<'o>(x: &'o ()) -> Box<dyn Send + 'o> {
    Box::new(capture::<'o, &'_ &'o ()>(&x))
}

Playground link

This code works for precisely the reason the earlier example does not. The problem was that we were returning a type that referenced a lifetime only valid within the current function. By using Box<dyn Trait>, we're erasing the type that contains this problem lifetime. Since the value itself does not contain any references to data from the local function, and since the opaque type does outlive 'o, this value is allowed to escape.

The practical solution: TAIT

Before we go on, we should mention the practical solution: capture less. For example:

// Example 2.3
#![feature(type_alias_impl_trait)]

pub type PhantomCapture<'o> = impl Send + 'o;
pub fn capture_less<'o, T>(_t: T) -> PhantomCapture<'o> { () }

fn test<'o>(x: &'o ()) -> PhantomCapture<'o> {
    capture_less::<'o, &'_ &'o ()>(&x)
}

Playground link

If we don't capture the type parameter T, then the problem goes away. Using TAIT we can express this (and without TAIT, we cannot).

An imaginary fix

To explore what we're actually trying to express here (setting aside just capturing less), let's imagine that Rust had a new feature.

Rust today supports existential types. What if we supported existential lifetimes? Pretend that something like this worked:

// Example 2.4
#![feature(type_alias_impl_trait)]

type PhantomCapture<'o, T> = impl Send + 'o;
fn capture<'o, T>(_t: T) -> PhantomCapture<'o, T> { () }

existential lifetime 'local;
//          ^^^^^^^^^^^^^^^
//          ^ This is make-believe.
fn test<'o>(x: &'o ()) -> PhantomCapture<'o, &'local ()> {
    capture(&x)
}

We want to say that the callee is going to pick a lifetime that will be part of the returned opaque type. For this to work, we'd obviously have to prove that the hidden type behind this opaque type does not contain this lifetime.

Is this at all reasonable? Could we make this sound? No idea.

Using associated types for analysis

Another way to look at this is through the lens of associated types. In the following examples, we'll use a dummy trait and an associated type to model the behavior seen above.

Using ATPIT

Let's first use associated type position impl Trait.

// Example 2.5
#![feature(impl_trait_in_assoc_type)]

struct Dummy;

trait PhantomCapture<'o, T> {
    //               ^^^^^
    //               ^ These represent the captured generic
    //               parameters.
    type Opaque: Send + 'o;
    fn capture(_t: T) -> Self::Opaque;
}

impl<'o, T> PhantomCapture<'o, T> for () {
    type Opaque = impl Send + 'o;
    fn capture(_t: T) -> Self::Opaque { () }
}

fn test<'o>(
    x: &'o ()
) -> <() as PhantomCapture<'o, Dummy>>::Opaque {
    //                         ^^^^^
    // This is the magic we want.  ^
    <() as PhantomCapture<'o, &'_ &'o ()>>::capture(&x)
//  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//  ^ ERROR: Expected Dummy, found &().
}

Playground link

This is essentially the TAIT example earlier converted to ATPIT.

Using associated types only

Let's remove impl Trait entirely and just model the situation with associated types.

// Example 2.6
struct Dummy;

trait PhantomCapture<'o, T> {
    //               ^^^^^
    //               ^ These represent the captured generic
    //               parameters.
    type FakeOpaque: Send + 'o;
    fn capture(_t: T) -> Self::FakeOpaque;
}

impl<'o, T> PhantomCapture<'o, T> for () {
    type FakeOpaque = ();
    fn capture(_t: T) -> Self::FakeOpaque { () }
}

fn test<'o>(
    x: &'o ()
) -> <() as PhantomCapture<'o, Dummy>>::FakeOpaque {
    //                         ^^^^^
    // This is the magic we want.  ^
    <() as PhantomCapture<'o, &'_ &'o ()>>::capture(&x)
//  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//  ^ This works.
}

Playground link

Through the magic of projection normalization and RFC 1214, this works.

Could the compiler do something spiritually similar to solve the problems above? No idea.

Appendix A: Why do things work this way?

After this analysis was published, Michael Goulet explained during a discussion why things work this way. We reproduce that explanation in this appendix:

So there's a distinction between:

1. Being allowed to name a lifetime (regardless of whether bounds on the item actually disallow this) – this is one sense of the word "captures", but I'll call it nameable… All lifetimes that are nameable in this sense must not dangle, and thus must be live until the drop of the opaque. That's the only restriction on these lifetimes.

2. Actually using a lifetime in the hidden type. This is the other sense of the word "captures". This type is required to uphold all the trait and lifetime bounds in the impl Sized + 'static (e.g.)…

In what situation would there be a reason to capture a lifetime in the first sense without capturing it in the second sense?

There's no reason philosophically. It's totally a technical one as far as I can tell. In the compiler, we determine which lifetimes are captured (in the first sense) pretty early on in the compiler (partly during lowering to HIR, and partly when computing the variances of items in the crate), and use that information as the fundamental representation of the opaque type internally in the compiler – all the way through to borrowck.

We only later infer the hidden type, where we'd be able to prove things about lifetimes that are captured in the second sense – and we wouldn't want to leak those through the opaque either.

…ideally, we'd be able to use something like a 'static bound an opaque to disqualify any captured lifetimes (in the first sense, nameable) that are shorter than that bound's lifetime, because we're able to conclude that that lifetime would never be able to actually show up in the hidden type of the opaque (i.e. captured in the second sense) without actually having to leak anything from the opaque.

This is really complicated by the order of operations of things in the compiler though.

Acknowledgments

Thanks to Michael Goulet (@compiler-errors) for helpful discussions and insights on this and other topics.

All errors and omissions remain those of the author alone.