Some std::collections types are unnecessarily invariant

8e8fc50
Opened by Andrew Paseltiner at 2019-12-25 16:23:24

The following std::collections types are unnecessarily invariant in their type parameters:

  • ~~binary_heap::Drain~~
  • ~~btree_map::{Keys, Values}~~
  • ~~btree_set::{IntoIter, Iter, Range}~~
  • btree_set::{Difference, Intersection, SymmetricDifference, Union}
  • ~~hash_map::{IntoIter, Iter, Keys, Values}~~
  • hash_map::Drain
  • ~~hash_set::{Difference, Intersection, IntoIter, Iter, SymmetricDifference, Union}~~
  • hash_set::Drain
  • ~~linked_list::{IntoIter, Iter, LinkedList}~~
  • ~~vec::Drain~~
  • ~~vec_deque::Drain~~

Some, like btree_map::Keys, are invariant due to the use of iter::Map with fn(T) -> U being invariant over T, while others, like LinkedList, are due to the ultimate use of *mut T, and the rest are wrappers around other invariant iterators.

Of these, the most important to fix is probably LinkedList, as the rest are iterators. Given the issue with iter::Map, it is likely that some other iterators in std have the same problem.

  1. I expect the BTreeMap ones will be fixed by #30426

    Drain is an interesting case because it's semantically an &mut Collection<T>, but it doesn't enable T's to be written to, only read out.

    Fixing LinkedList may be as simple as using Shared for RawLink.

    Aria Desires at 2015-12-30 17:47:23

  2. It appears that the remaining btree_set iterators are invariant due to the use of Peekable. With no other indication of why this would be an issue, I'm guessing it's related to Peekable's use of an associated type projection.

    Andrew Paseltiner at 2016-02-06 23:03:11

  3. vec_deque::Drain is made covariant in bf592cefde3.

    Stepan Koltsov at 2017-06-12 12:27:18

  4. Triage: with the last comment, only two still are.

    Steve Klabnik at 2019-12-25 16:23:24