Audit and handle remaining cases of rustc::potential_query_instability lint (iterating HashMaps)

[Aaron1011]

The iteration order of a HashMap depends on the Hash value of the keys. In rustc, the Hash value of a key can change between compilation sessions, even if the HashStable value remains the same (e.g. DefId, Symbol, etc.). This means that iterating over a HashMap can cause a query to produce different results given the same (as determined by HashStable) input. This can be quite subtle, as demonstrated by #82272 (comment)

To eliminate this source of issues, we should make an internal rustc-only lint for iterating over a HashMap in any way. This will need to cover explicit method calls (e.g. .keys() and .values()), as well as any usage of the IntoIterator impl for HashMap.

Note that we don't want to ban the usage of HashMaps with unstable keys - as long as they're only used for lookup (and not iteration), it's much more efficient than repeatedly converting to the stable form of a key (e.g. DefId -> DefPathHash or Symbol -> String).

[bjorn3]

Note that we don't want to ban the usage of HashMaps with unstable keys - as long as they're only used for lookup (and not iteration),

#64131 added the StableMap wrapper for FxHashMap that doesn't expose the iteration order.

[jyn514]

@bjorn3 see #84446

[cjgillot]

The lint exists since #89558, and has allowed on all compiler crates as rustc::potential_query_instability.
We now need to stop allowing it in the compiler.

Steps, for each crate except rustc_data_structures:

• remove the allow(rustc::potential_query_instability) in lib.rs;
• replace the FxHash{Map,Set} by FxIndex{Map,Set} where necessary.

Please reach out on zulip if there are any questions.

[fee1-dead]

@rustbot claim

@rustbot release-assignment

[NiklasJonsson]

It seems like no one is assigned to this and I'd like to give it a try so assigning myself.

@rustbot claim

[NiklasJonsson]

I was hoping to get back to this after vacation but I haven't had the time and I likely won't in the near future. I've converted some of the modules to use the stable hash containers but there is a decent amount left so it is probably possible to have multiple people working on this, assuming some coordination.

There are two outstanding PRs from me that I will finish up. The first is #99334 and seems ready to merge. Second one is #99065 which requires the get_many_mut feature to be merged for the stable hash containers indexmap-rs/indexmap#238, which in turn is waiting on the stabilization of the matching features on the standard hash containers (#97601).

@rustbot release-assignment

[CastilloDel]

I'm gonna give this a try
@rustbot claim

[ismailarilik]

This PR is for rustc_metadata: #131145

[ismailarilik]

The lint exists since #89558, and has allowed on all compiler crates as rustc::potential_query_instability. We now need to stop allowing it in the compiler.

Steps, for each crate except rustc_data_structures:

* remove the `allow(rustc::potential_query_instability)` in `lib.rs`;

* replace the `FxHash{Map,Set}` by `FxIndex{Map,Set}` where necessary.

Please reach out on zulip if there are any questions.

@cjgillot You specified rustc_data_structures as an exception here. So what should be done for it? Is it nothing or another approach?

BTW, with the PRs I recently opened, there is not much left to fix but I will open another PR for the remainings.

[cjgillot]

rustc_data_structures is a small crate with support code. The lint is meant to avoid accidentally introducing non-determinism in compiler code.

The only thing that would be needed for rustc_data_structures is to review all the places where there is an #[allow(rustc::potential_query_instability)] and put a comment there explaining why it's ok.

[ismailarilik]

rustc_data_structures is a small crate with support code. The lint is meant to avoid accidentally introducing non-determinism in compiler code.

The only thing that would be needed for rustc_data_structures is to review all the places where there is an #[allow(rustc::potential_query_instability)] and put a comment there explaining why it's ok.

@cjgillot there is just one #[allow(rustc::potential_query_instability)] for rustc_data_structures in lib.rs. Is your statement here is enough for rationale explanation? (I was thinking to add it as a comment above the allow statement.)

[ismailarilik]

For migrated ones, perf might be improved by removing some sort calls which were only added to provide order stability but I don't know how I can find them easily.