Rollup merge of #102680 - dtolnay:btreesend, r=thomcc

Fix overconstrained Send impls in btree internals

Fixes https://github.com/dtolnay/async-trait/issues/215.

Minimal repro:

```rust
use std::collections::btree_map::Iter;

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

fn main() {
    require_send(async {
        let _iter = None::<Iter<(), &()>>;
        async {}.await;
    });
}
```

```console
error: higher-ranked lifetime error
 --> src/main.rs:6:5
  |
6 | /     require_send(async {
7 | |         let _iter = None::<Iter<(), &()>>;
8 | |         async {}.await;
9 | |     });
  | |______^
  |
  = note: could not prove `impl Future<Output = ()>: Send`
```

Not-quite-so-minimal repro:

```rust
use std::collections::BTreeMap;
use std::future::Future;

fn spawn<T: Future + Send>(_: T) {}

async fn f() {
    let map = BTreeMap::<u32, Box<dyn Send + Sync>>::new();
    for _ in &map {
        async {}.await;
    }
}

fn main() {
    spawn(f());
}
```

```console
error: higher-ranked lifetime error
  --> src/main.rs:14:5
   |
14 |     spawn(f());
   |     ^^^^^^^^^^
   |
   = note: could not prove `impl Future<Output = ()>: Send`
```

I am not familiar with the btree internals, but it seems clear to me that the `async fn f` above should return a Send future. Using HashMap instead of BTreeMap in that code makes it already return a Send future.

The _"higher-ranked lifetime error"_ message may be a regression in Rust 1.63. Using older compilers the error message was more detailed:

```console
error: implementation of `Send` is not general enough
  --> src/main.rs:14:5
   |
14 |     spawn(f());
   |     ^^^^^ implementation of `Send` is not general enough
   |
   = note: `Send` would have to be implemented for the type `alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Immut<'0>, u32, Box<(dyn Send + Sync + '1)>, alloc::collections::btree::node::marker::LeafOrInternal>`, for any two lifetimes `'0` and `'1`...
   = note: ...but `Send` is actually implemented for the type `alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Immut<'2>, u32, Box<dyn Send + Sync>, alloc::collections::btree::node::marker::LeafOrInternal>`, for some specific lifetime `'2`

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

3 files changed, 300 insertions, 3 deletions

diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs
index f1d2d3b30d9..da766b67a32 100644
--- a/library/alloc/src/collections/btree/node.rs
+++ b/library/alloc/src/collections/btree/node.rs
@@ -206,9 +206,9 @@ impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
 
 unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {}
 
-unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {}
-unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {}
-unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::ValMut<'a>, K, V, Type> {}
+unsafe impl<K: Sync, V: Sync, Type> Send for NodeRef<marker::Immut<'_>, K, V, Type> {}
+unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Mut<'_>, K, V, Type> {}
+unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::ValMut<'_>, K, V, Type> {}
 unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {}
 unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Dying, K, V, Type> {}
 
diff --git a/library/alloc/tests/autotraits.rs b/library/alloc/tests/autotraits.rs
new file mode 100644
index 00000000000..8ff5f0abe73
--- /dev/null
+++ b/library/alloc/tests/autotraits.rs
@@ -0,0 +1,293 @@
+fn require_sync<T: Sync>(_: T) {}
+fn require_send_sync<T: Send + Sync>(_: T) {}
+
+struct NotSend(*const ());
+unsafe impl Sync for NotSend {}
+
+#[test]
+fn test_btree_map() {
+    // Tests of this form are prone to https://github.com/rust-lang/rust/issues/64552.
+    //
+    // In theory the async block's future would be Send if the value we hold
+    // across the await point is Send, and Sync if the value we hold across the
+    // await point is Sync.
+    //
+    // We test autotraits in this convoluted way, instead of a straightforward
+    // `require_send_sync::<TypeIWantToTest>()`, because the interaction with
+    // generators exposes some current limitations in rustc's ability to prove a
+    // lifetime bound on the erased generator witness types. See the above link.
+    //
+    // A typical way this would surface in real code is:
+    //
+    //     fn spawn<T: Future + Send>(_: T) {}
+    //
+    //     async fn f() {
+    //         let map = BTreeMap::<u32, Box<dyn Send + Sync>>::new();
+    //         for _ in &map {
+    //             async {}.await;
+    //         }
+    //     }
+    //
+    //     fn main() {
+    //         spawn(f());
+    //     }
+    //
+    // where with some unintentionally overconstrained Send impls in liballoc's
+    // internals, the future might incorrectly not be Send even though every
+    // single type involved in the program is Send and Sync.
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::Iter<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    // Testing like this would not catch all issues that the above form catches.
+    require_send_sync(None::<alloc::collections::btree_map::Iter<'_, &u32, &u32>>);
+
+    require_sync(async {
+        let _v = None::<alloc::collections::btree_map::Iter<'_, u32, NotSend>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::BTreeMap<&u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<
+            alloc::collections::btree_map::DrainFilter<
+                '_,
+                &u32,
+                &u32,
+                fn(&&u32, &mut &u32) -> bool,
+            >,
+        >;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::Entry<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::IntoIter<&u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::IntoKeys<&u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::IntoValues<&u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::Iter<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::IterMut<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::Keys<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::OccupiedEntry<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::OccupiedError<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::Range<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::RangeMut<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::VacantEntry<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::Values<'_, &u32, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_map::ValuesMut<'_, &u32, &u32>>;
+        async {}.await;
+    });
+}
+
+#[test]
+fn test_btree_set() {
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_set::BTreeSet<&u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_set::Difference<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_set::DrainFilter<'_, &u32, fn(&&u32) -> bool>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_set::Intersection<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_set::IntoIter<&u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_set::Iter<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_set::Range<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_set::SymmetricDifference<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::btree_set::Union<'_, &u32>>;
+        async {}.await;
+    });
+}
+
+#[test]
+fn test_binary_heap() {
+    require_send_sync(async {
+        let _v = None::<alloc::collections::binary_heap::BinaryHeap<&u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::binary_heap::Drain<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::binary_heap::DrainSorted<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::binary_heap::IntoIter<&u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::binary_heap::IntoIterSorted<&u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::binary_heap::Iter<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::binary_heap::PeekMut<'_, &u32>>;
+        async {}.await;
+    });
+}
+
+#[test]
+fn test_linked_list() {
+    require_send_sync(async {
+        let _v = None::<alloc::collections::linked_list::Cursor<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::linked_list::CursorMut<'_, &u32>>;
+        async {}.await;
+    });
+
+    // FIXME
+    /*
+    require_send_sync(async {
+        let _v =
+            None::<alloc::collections::linked_list::DrainFilter<'_, &u32, fn(&mut &u32) -> bool>>;
+        async {}.await;
+    });
+    */
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::linked_list::IntoIter<&u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::linked_list::Iter<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::linked_list::IterMut<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::linked_list::LinkedList<&u32>>;
+        async {}.await;
+    });
+}
+
+#[test]
+fn test_vec_deque() {
+    require_send_sync(async {
+        let _v = None::<alloc::collections::vec_deque::Drain<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::vec_deque::IntoIter<&u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::vec_deque::Iter<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::vec_deque::IterMut<'_, &u32>>;
+        async {}.await;
+    });
+
+    require_send_sync(async {
+        let _v = None::<alloc::collections::vec_deque::VecDeque<&u32>>;
+        async {}.await;
+    });
+}
diff --git a/library/alloc/tests/lib.rs b/library/alloc/tests/lib.rs
index f30ebd77e24..ffc5ca7a5c6 100644
--- a/library/alloc/tests/lib.rs
+++ b/library/alloc/tests/lib.rs
@@ -2,6 +2,7 @@
 #![feature(alloc_layout_extra)]
 #![feature(assert_matches)]
 #![feature(box_syntax)]
+#![feature(btree_drain_filter)]
 #![feature(cow_is_borrowed)]
 #![feature(const_box)]
 #![feature(const_convert)]
@@ -14,6 +15,8 @@
 #![feature(core_intrinsics)]
 #![feature(drain_filter)]
 #![feature(exact_size_is_empty)]
+#![feature(linked_list_cursors)]
+#![feature(map_try_insert)]
 #![feature(new_uninit)]
 #![feature(pattern)]
 #![feature(trusted_len)]
@@ -49,6 +52,7 @@ use std::collections::hash_map::DefaultHasher;
 use std::hash::{Hash, Hasher};
 
 mod arc;
+mod autotraits;
 mod borrow;
 mod boxed;
 mod btree_set_hash;