Auto merge of #113328 - michaelwoerister:no_hashmap_in_typeck, r=cjgillot,lcnr

Enable potential_query_instability lint in rustc_hir_typeck.

Fix linting errors by using `FxIndex(Map|Set)` and `Unord(Map|Set)` as appropriate. Part of [MCP 533](https://github.com/rust-lang/compiler-team/issues/533).

I really like the `potential_query_instability` lint!

r? `@lcnr`

1 files changed, 51 insertions, 22 deletions

diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs
index 2b21815b687..47c56eba7ad 100644
--- a/compiler/rustc_data_structures/src/unord.rs
+++ b/compiler/rustc_data_structures/src/unord.rs
@@ -31,6 +31,7 @@ use crate::{
 ///
 /// It's still possible to do the same thing with an `Fn` by using interior mutability,
 /// but the chance of doing it accidentally is reduced.
+#[derive(Clone)]
 pub struct UnordItems<T, I: Iterator<Item = T>>(I);
 
 impl<T, I: Iterator<Item = T>> UnordItems<T, I> {
@@ -167,6 +168,14 @@ impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> {
     }
 }
 
+/// A marker trait specifying that `Self` can consume `UnordItems<_>` without
+/// exposing any internal ordering.
+///
+/// Note: right now this is just a marker trait. It could be extended to contain
+/// some useful, common methods though, like `len`, `clear`, or the various
+/// kinds of `to_sorted`.
+trait UnordCollection {}
+
 /// This is a set collection type that tries very hard to not expose
 /// any internal iteration. This is a useful property when trying to
 /// uphold the determinism invariants imposed by the query system.
@@ -181,6 +190,8 @@ pub struct UnordSet<V: Eq + Hash> {
     inner: FxHashSet<V>,
 }
 
+impl<V: Eq + Hash> UnordCollection for UnordSet<V> {}
+
 impl<V: Eq + Hash> Default for UnordSet<V> {
     #[inline]
     fn default() -> Self {
@@ -195,6 +206,11 @@ impl<V: Eq + Hash> UnordSet<V> {
     }
 
     #[inline]
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self { inner: FxHashSet::with_capacity_and_hasher(capacity, Default::default()) }
+    }
+
+    #[inline]
     pub fn len(&self) -> usize {
         self.inner.len()
     }
@@ -258,9 +274,9 @@ impl<V: Eq + Hash> UnordSet<V> {
     #[inline]
     pub fn to_sorted_stable_ord(&self) -> Vec<V>
     where
-        V: Ord + StableOrd + Copy,
+        V: Ord + StableOrd + Clone,
     {
-        let mut items: Vec<V> = self.inner.iter().copied().collect();
+        let mut items: Vec<V> = self.inner.iter().cloned().collect();
         items.sort_unstable();
         items
     }
@@ -279,16 +295,28 @@ impl<V: Eq + Hash> UnordSet<V> {
         to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |x| x)
     }
 
-    // We can safely extend this UnordSet from a set of unordered values because that
-    // won't expose the internal ordering anywhere.
     #[inline]
-    pub fn extend_unord<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
-        self.inner.extend(items.0)
+    pub fn clear(&mut self) {
+        self.inner.clear();
     }
+}
+
+pub trait ExtendUnord<T> {
+    /// Extend this unord collection with the given `UnordItems`.
+    /// This method is called `extend_unord` instead of just `extend` so it
+    /// does not conflict with `Extend::extend`. Otherwise there would be many
+    /// places where the two methods would have to be explicitly disambiguated
+    /// via UFCS.
+    fn extend_unord<I: Iterator<Item = T>>(&mut self, items: UnordItems<T, I>);
+}
 
+// Note: it is important that `C` implements `UnordCollection` in addition to
+// `Extend`, otherwise this impl would leak the internal iteration order of
+// `items`, e.g. when calling `some_vec.extend_unord(some_unord_items)`.
+impl<C: Extend<T> + UnordCollection, T> ExtendUnord<T> for C {
     #[inline]
-    pub fn clear(&mut self) {
-        self.inner.clear();
+    fn extend_unord<I: Iterator<Item = T>>(&mut self, items: UnordItems<T, I>) {
+        self.extend(items.0)
     }
 }
 
@@ -312,6 +340,12 @@ impl<V: Hash + Eq> From<FxHashSet<V>> for UnordSet<V> {
     }
 }
 
+impl<V: Hash + Eq, I: Iterator<Item = V>> From<UnordItems<V, I>> for UnordSet<V> {
+    fn from(value: UnordItems<V, I>) -> Self {
+        UnordSet { inner: FxHashSet::from_iter(value.0) }
+    }
+}
+
 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> {
     #[inline]
     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
@@ -333,6 +367,8 @@ pub struct UnordMap<K: Eq + Hash, V> {
     inner: FxHashMap<K, V>,
 }
 
+impl<K: Eq + Hash, V> UnordCollection for UnordMap<K, V> {}
+
 impl<K: Eq + Hash, V> Default for UnordMap<K, V> {
     #[inline]
     fn default() -> Self {
@@ -363,6 +399,11 @@ impl<K: Hash + Eq, V, I: Iterator<Item = (K, V)>> From<UnordItems<(K, V), I>> fo
 
 impl<K: Eq + Hash, V> UnordMap<K, V> {
     #[inline]
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self { inner: FxHashMap::with_capacity_and_hasher(capacity, Default::default()) }
+    }
+
+    #[inline]
     pub fn len(&self) -> usize {
         self.inner.len()
     }
@@ -428,13 +469,6 @@ impl<K: Eq + Hash, V> UnordMap<K, V> {
         UnordItems(self.inner.into_iter())
     }
 
-    // We can safely extend this UnordMap from a set of unordered values because that
-    // won't expose the internal ordering anywhere.
-    #[inline]
-    pub fn extend<I: Iterator<Item = (K, V)>>(&mut self, items: UnordItems<(K, V), I>) {
-        self.inner.extend(items.0)
-    }
-
     /// Returns the entries of this map in stable sort order (as defined by `ToStableHashKey`).
     ///
     /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
@@ -554,15 +588,10 @@ impl<V> UnordBag<V> {
     pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
         UnordItems(self.inner.into_iter())
     }
-
-    // We can safely extend this UnordSet from a set of unordered values because that
-    // won't expose the internal ordering anywhere.
-    #[inline]
-    pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
-        self.inner.extend(items.0)
-    }
 }
 
+impl<T> UnordCollection for UnordBag<T> {}
+
 impl<T> Extend<T> for UnordBag<T> {
     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
         self.inner.extend(iter)