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:

rust/src/librustc_typeck/check/generator_interior.rs

Lines 124 to 144 in 9b9d2af

	// The types in the generator interior contain lifetimes local to the generator itself,
	// which should not be exposed outside of the generator. Therefore, we replace these
	// lifetimes with existentially-bound lifetimes, which reflect the exact value of the
	// lifetimes not being known by users.
	//
	// These lifetimes are used in auto trait impl checking (for example,
	// if a Sync generator contains an &'α T, we need to check whether &'α T: Sync),
	// so knowledge of the exact relationships between them isn't particularly important.
	debug!("types in generator {:?}, span = {:?}", type_list, body.value.span);
	// Replace all regions inside the generator interior with late bound regions
	// Note that each region slot in the types gets a new fresh late bound region,
	// which means that none of the regions inside relate to any other, even if
	// typeck had previously found constraints that would cause them to be related.
	let mut counter = 0;
	let type_list = fcx.tcx.fold_regions(&type_list, &mut false, |_, current_depth| {
	counter += 1;
	fcx.tcx.mk_region(ty::ReLateBound(current_depth, ty::BrAnon(counter)))
	});

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`