Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Some std::collections types are unnecessarily invariant #30642

Open
apasel422 opened this issue Dec 30, 2015 · 4 comments
Open

Some std::collections types are unnecessarily invariant #30642

apasel422 opened this issue Dec 30, 2015 · 4 comments
Labels
A-collections Area: `std::collection` C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@apasel422
Copy link
Contributor

apasel422 commented Dec 30, 2015

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.

@Gankra
Copy link
Contributor

Gankra commented Dec 30, 2015

I expect the BTreeMap ones will be fixed by #30426

Drain is an interesting case because it's semantically an &mut Collection, 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.

@apasel422
Copy link
Contributor Author

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.

bors added a commit that referenced this issue Apr 1, 2016
Make HashMap, HashSet, and their iterators properly covariant

See #30642. `Drain` is the only type left invariant.
@steveklabnik steveklabnik added T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. and removed A-libs labels Mar 24, 2017
@stepancheg
Copy link
Contributor

vec_deque::Drain is made covariant in bf592ce.

@Mark-Simulacrum Mark-Simulacrum added the C-enhancement Category: An issue proposing an enhancement or a PR with one. label Jul 24, 2017
@steveklabnik
Copy link
Member

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-collections Area: `std::collection` C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests

5 participants