Rust: Lifetime bounds in auto trait impls prevent trait from being implemented on generators

[leo60228]

use std::collections::{BTreeMap, HashMap};
use std::sync::Arc;

fn needs_send<T: Send>(_val: T) {}
async fn async_fn_a(_num: u32) {}
async fn async_fn_b(map: Arc<BTreeMap<u32, &'static u32>>) {
    for (_i, v) in &*map {
        async_fn_a(**v).await;
    }
}
async fn async_fn_c(map: Arc<HashMap<u32, &'static u32>>) {
    for (_i, v) in &*map {
        async_fn_a(**v).await;
    }
}

fn main() {
    // this works...
    let map: Arc<HashMap<u32, &'static u32>> = Arc::new(HashMap::new());
    needs_send(async_fn_c(map.clone()));

    // but this doesn't
    let map: Arc<BTreeMap<u32, &'static u32>> = Arc::new(BTreeMap::new());
    needs_send(async_fn_b(map.clone()));
}

(playground)

error: implementation of `std::marker::Send` is not general enough
  --> src/main.rs:24:5
   |
24 |     needs_send(async_fn_b(map.clone()));
   |     ^^^^^^^^^^
   |
   = note: `std::marker::Send` would have to be implemented for the type `alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Immut<'0>, u32, &'1 u32, alloc::collections::btree::node::marker::Leaf>`, for any two lifetimes `'0` and `'1`
   = note: but `std::marker::Send` is actually implemented for the type `alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Immut<'2>, u32, &u32, alloc::collections::btree::node::marker::Leaf>`, for some specific lifetime `'2`

[Aaron1011]

Minimized:

fn needs_send<T: Send>(_val: T) {}
async fn use_async<T>(_val: T) {}

struct MyStruct<'a, T: 'a> {
    val: &'a T
}

unsafe impl<'a, T: 'a> Send for MyStruct<'a, T> {} 

async fn use_my_struct(val: MyStruct<'static, &'static u8>) {
    use_async(val).await;
}

fn main() {
    let first_struct: MyStruct<'static, &'static u8> = MyStruct { val: &&26 };
    let second_struct: MyStruct<'static, &'static u8> = MyStruct { val: &&27 };

    needs_send(first_struct);
    needs_send(use_my_struct(second_struct)); // ERROR
}

It seems as though the manual Send impl is confusing some async-related code. The code compiles if you remove unsafe impl<'a, T: 'a> Send for MyStruct<'a, T> {}, even though it's not actually adding any additional region constraints.

[Aaron1011]

I think the bug occurs here: https://github.com/rust-lang/rust/blob/9b9d2aff8de4d499b4ba7ca406e000f8d3754ea7/src/librustc_typeck/check/generator_interior.rs#L124-L144

I believe that 'knowledge of the exact relationships between them isn't particularly important' is incorrect. If an auto trait impl imposes region constraints (as with MyStruct), then the relationship between regions does matter.

For this particular issue, leaving 'static unmodified (i.e. not replacing it with a region variable) should be sufficient to allow the code to compile.

In the general case, I think a full solution would require some notion of 'higher-ranked' region constraints. For example, consider the function:

async fn use_my_struct<'a, 'b: 'a>(val: MyStruct<'a, &'b u8>) {
    use_async(val).await;
}

The returned generator should implement Send, because MyStruct<'a, &'b u8> implements Send. However, proving this requires us to know that 'b: 'a holds when we're inspecting the generator witness.

[Aaron1011]

Concretely, I think we could implement this as follows:

1. Add a List<RegionOutlivesPredicate> to GeneratorWitness. This would store a list of predicates involving any 'internal' regions variables. This list would be created here by recording all known relationships between interior region variables.
2. Modify collect_predicates_for_types to take into account the original type we're determining the auto impl for. If it's a GeneratorWitness, we extend the ParamEnv for the newly created sub-obligations with all of the RegionOutlivesPredicate from our generator witness. Effectively, a GeneratorWitness causes us to learn something new - however, this knowledge only applies to to the interior region variables.

This should only affect auto-trait resolution for generators. Users cannot implement any traits on the underlying generator type (in fact, they cannot even name it). This should ensure that these RegionOutlivesPredicate cannot affect any code external to the generator, except to the extent that they allow us to prove that an auto-trait impl applies. It should be impossible user code to observe these regions in any way, since the generator can only be interacted with via Generator::Resume and the .await syntax.

cc @nikomatsakis @tmandry

[dtolnay]

I haven't seen a "me too" yet so I thought I'd mention that I hit this as well, to help assess how frequent this bug is.

use futures::future;
use futures::stream::{self, StreamExt};

struct Thing;

async fn genfoo(t: &[Thing]) {
    let _ = stream::iter(t)
        .map(future::ready)
        .buffer_unordered(10)
        .collect::<Vec<_>>()
        .await;
}

fn foo<'a>(t: &'a [Thing]) -> impl Send + 'a {
    genfoo(t)
}

error: implementation of `std::iter::Iterator` is not general enough
    --> src/main.rs:14:31
     |
14   |   fn foo<'a>(t: &'a [Thing]) -> impl Send + 'a {
     |                                 ^^^^^^^^^^^^^^ implementation of `std::iter::Iterator` is not general enough
     |
     = note: `std::iter::Iterator` would have to be implemented for the type `std::slice::Iter<'0, Thing>`, for any lifetime `'0`...
     = note: ...but `std::iter::Iterator` is actually implemented for the type `std::slice::Iter<'1, Thing>`, for some specific lifetime `'1`

[tmandry]

I've marked #68950 and #68759 as duplicates of this issue, since they seem to have the same underlying cause. We should include their examples as regression tests in the fix for this bug (or reopen them if they are not fixed).

[Aaron1011]

Another instance of this (partially minimized from https://github.com/tokio-rs/tokio/issues/1835):

use futures::{
    TryStream,
    Stream,
    stream::{iter},
    StreamExt,
};
use std::future::Future;
use std::task::{Poll, Context};
use std::pin::Pin;

pub(crate) type BoxedFutureTask = Pin<Box<dyn Future<Output = ()> + 'static + Send>>;

pub fn require_send<T: Send>(_: T) {}

struct MyFut<V>(V::Ok) where V: TryStream;
impl<V, Good, Bad> Future for MyFut<V> where
    V: Stream<Item = Result<Good, Bad>> {

    type Output = ();
    fn poll(self: Pin<&mut Self>, _: &mut Context) -> Poll<Self::Output> {
        panic!()
    }
}


fn my_send_all<St>(stream: &mut St) -> MyFut<St> where St: TryStream<Error = ()>
{
    panic!()
}

async fn dummy() {}

async fn inner() {
    let mut tasks = iter(
        std::iter::once(Ok(Box::pin(async {}) as BoxedFutureTask))
    ).map(|val| val);
    my_send_all(&mut tasks).await;
}

fn main() {
    require_send(inner())
}

gives:

error[E0308]: mismatched types
  --> src/main.rs:41:5
   |
41 |     require_send(inner())
   |     ^^^^^^^^^^^^ one type is more general than the other
   |
   = note: expected type `std::ops::FnOnce<(std::result::Result<std::pin::Pin<std::boxed::Box<dyn core::future::future::Future<Output = ()> + std::marker::Send>>, ()>,)>`
              found type `std::ops::FnOnce<(std::result::Result<std::pin::Pin<std::boxed::Box<dyn core::future::future::Future<Output = ()> + std::marker::Send>>, ()>,)>`

This error is particularly unhelpful because it doesn't even mention that the Send requirement is the root cause.

[jonhere]

One workaround is an explicit Send wrapper.

pub struct IamSend<F: Future> {
    f: F,
}
impl<F: Future> IamSend<F> {
    pub unsafe fn new(f: F) -> Self {
        IamSend { f }
    }
}
unsafe impl<F: Future> Send for IamSend<F> {}
impl<F: Future> Future for IamSend<F> {
    type Output = F::Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output> {
        unsafe { self.map_unchecked_mut(|s| &mut s.f).poll(cx) }
    }
}

[TheEnbyperor]

One workaround is an explicit Send wrapper.

pub struct IamSend<F: Future> {
    f: F,
}
impl<F: Future> IamSend<F> {
    pub unsafe fn new(f: F) -> Self {
        IamSend { f }
    }
}
unsafe impl<F: Future> Send for IamSend<F> {}
impl<F: Future> Future for IamSend<F> {
    type Output = F::Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output> {
        unsafe { self.map_unchecked_mut(|s| &mut s.f).poll(cx) }
    }
}

Any specifics on how/where to use this? Tried to use it to fix #72063 and caused absolutely no change.

[tmandry]

Removing assignments, since there doesn't seem to be any work on this issue lately. If you (or someone else) still want to work on this, feel free to claim it!

[shssoichiro]

I encountered this when making changes to a warp-based webapp. I discovered it was caused by importing itertools::Itertools at the top level of a module. I'm guessing something from the Itertools trait is colliding with the futures library. Unfortunately I don't know if I can reasonably minify my case, but hoped this might provide some insight anyway.

error: implementation of `std::iter::Iterator` is not general enough
    --> src/controllers/admin.rs:18:10
     |
18   |           .and_then(api_admin_get)
     |            ^^^^^^^^ implementation of `std::iter::Iterator` is not general enough
     | 
    ::: /home/soichiro/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/iter/traits/iterator.rs:96:1
     |
96   | / pub trait Iterator {
97   | |     /// The type of the elements being iterated over.
98   | |     #[stable(feature = "rust1", since = "1.0.0")]
99   | |     type Item;
...    |
3276 | |     }
3277 | | }
     | |_- trait `std::iter::Iterator` defined here
     |
     = note: `std::iter::Iterator` would have to be implemented for the type `std::slice::Iter<'0, models::series_tag::SeriesTag>`, for any lifetime `'0`...
     = note: ...but `std::iter::Iterator` is actually implemented for the type `std::slice::Iter<'1, models::series_tag::SeriesTag>`, for some specific lifetime `'1`

Edit: Looks like I still get this error if I move the use statement even into as narrow of a scope as possible. For example, this causes the error:

pub fn api_admin(db: PgPool) -> impl Filter<Extract = impl Reply, Error = Rejection> + Clone {
    warp::path!("api" / "admin")
        .and(warp::get())
        .and(require_admin(db.clone()))
        .and(with_db(db))
        .and_then(api_admin_get)
}

async fn api_admin_get(_admin: User, db: PgPool) -> Result<impl Reply, Infallible> {
    ...

    let tags = try_or_500!({
        use itertools::Itertools;
        Tag::find_all_in_list(
            &mut conn,
            &series_tags
                .iter()
                .map(|st| st.tag_id)
                .unique()
                .collect::<Vec<_>>(),
        )
        .await
    });

    ...

    Ok(...)
}

However, if I comment out the use statement and the .unique() call from itertools, compilation succeeds.

Edit 2: Seems in another controller, I have a method that continues failing compilation with this unhelpful error message even if I remove itertools. :cry:

Edit 3: Looks like there was a usage of Itertools in _another method in another module_, and the controller calling to this other method in the other module was causing this weird error to trigger. :confused:

[SergioBenitez]

I've hit this issue (which appears to underly #71723) many, _many_ times while transition Rocket to async/await.

Here's a simplified version (playground) of where I hit it last:

use std::future::Future;

struct Response<'r>(&'r str);
struct Request<'i>(&'i str);

trait Handler<'r> {
    type Output: Future<Output = Response<'r>>;
    fn call(&self, request: &'r Request<'_>) -> Self::Output;
}

impl<'r, F, Fut> Handler<'r> for F
    where F: Fn(&'r Request<'_>) -> Fut, Fut: Future<Output = Response<'r>>
{
    type Output = Fut;

    fn call(&self, request: &'r Request<'_>) -> Self::Output {
        self(request)
    }
}

fn check<H: for<'r> Handler<'r>>(_handler: H) { }

fn main() {

    fn handler<'r>(request: &'r Request<'_>) -> impl Future<Output = Response<'r>> {
        async move {
            Response(&request.0)
        }
    }

    async fn _handler3<'r>(request: &'r Request<'_>) -> Response<'r> {
        Response(&request.0)
    }

    check(handler);
    check(_handler3); // FIXME: Why doesn't this work? What lifetimes does the generated `Future` have?
}

This results in:

error: implementation of `std::ops::FnOnce` is not general enough
   --> src/main.rs:36:5
    |
36  |       check(_handler3); // FIXME: Why doesn't this work? What lifetimes does the generated `Future` have?
    |       ^^^^^ implementation of `std::ops::FnOnce` is not general enough
    |
    = note: `std::ops::FnOnce<(&Request<'0>,)>` would have to be implemented for the type `for<'r, '_> fn(&'r Request<'_>) -> impl std::future::Future {main::_handler3}`, for some specific lifetime `'0`...
    = note: ...but `std::ops::FnOnce<(&Request<'_>,)>` is actually implemented for the type `for<'r, '_> fn(&'r Request<'_>) -> impl std::future::Future {main::_handler3}`

I find it _very_ surprising that two functions below are not equivalent:

fn f1<'r>(request: &'r Foo) -> impl Future<Output = Bar<'r>> {
    async move { f(request) }
}

async fn f1<'r>(request: &'r Foo) -> Bar<'r> {
    f(request)
}

This bug has made it impossible, in many instances, to have higher-ordered functions that take async fns.

[rocallahan]

I spend hours trying to figure out an instance of this today :-(. My case minimized to

use futures::stream::{self, *};
use futures::future;
pub trait Whelk: Send {}
fn needs_send<T: Send>(_: T) {}
fn main() {
    let f = async move {
        let mut results = stream::empty().map(move |r: Box<dyn Whelk>| {
            future::ready(())
        })
        .buffered(5);
        future::ready(()).await
    };
    needs_send(f);
}

I eventually figured out how to work around it by boxing the stream to hide its inferred type:

        let mut results: std::pin::Pin<Box<dyn Stream<Item = _> + Send>> = Box::pin(stream::empty().map(move |r: Box<dyn Whelk>| {
            future::ready(())
        })
        .buffered(5));

[withoutboats]

We looked at this in lang triage and retagged it as T-compiler; since its not a soundness bug and seems like strictly an implementation issue, we don't think it needs lang input.

[nikomatsakis]

I wasn't at the lang team triage meeting, but I do think that's largely right. It's basically a question of implementation doing "the best it can"

[tmandry]

@rustbot assign @csmoe