Implement HashStable for StableMap/StableSet instead of HashMap/HashSet

[Aaron1011]

The implementation of HashStable for HashSet uses ToStableHashKey to sort the entries before hashing:

rust/compiler/rustc_data_structures/src/stable_hasher.rs

Lines 537 to 552 in ccf1712

	pub fn hash_stable_hashmap<HCX, K, V, R, SK, F>(
	hcx: &mut HCX,
	hasher: &mut StableHasher,
	map: &::std::collections::HashMap<K, V, R>,
	to_stable_hash_key: F,
	) where
	K: Eq,
	V: HashStable<HCX>,
	R: BuildHasher,
	SK: HashStable<HCX> + Ord,
	F: Fn(&K, &HCX) -> SK,
	{
	let mut entries: Vec<_> = map.iter().map(|(k, v)| (to_stable_hash_key(k, hcx), v)).collect();
	entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
	entries.hash_stable(hcx, hasher);
	}

However, nothing ensures that a HashMap is used in an order-independent way by other code. In particular, a query could directly iterate over the entires, and produce different results for two HashMaps that have the same Fingerprint.

We should enforce this order independence by only implementing HashStable on a wrapper type that hides the underlying iteration order. We could probably use StableMap and StableSet, but we'll need the ability to customize the key used by into_sorted_vector (we'll want to sort using a stable key, not the Ord implementation of a DefId).

[jyn514]

@Aaron1011 can I add a StableSet::any(f: impl Fn() -> bool) -> bool function? Or does that defeat the point because it can observe the iteration order? This code seems a little silly:

        for id in defids.to_sorted_vec() {
            let CodegenFnAttrs { optimize, .. } = tcx.codegen_fn_attrs(*id);
            match optimize {
                attr::OptimizeAttr::None => continue,
                attr::OptimizeAttr::Size => continue,
                attr::OptimizeAttr::Speed => {
                    return for_speed;
                }
            }
        }

[jyn514]

Another piece of code that seems silly:

        self.typeck_results.add_coercion_casts(fcx_coercion_casts.to_sorted_vec());

coercion_casts is just a normal hashmap, the insertion order doesn't matter.

[jyn514]

I am not making much progress on this - I have some broken in changes in jyn514@f7f913c if you want to reuse them, but it might be easier to start from scratch.