Make untracked incr. comp. information inaccessible

[cjgillot]

When iterating over a collection, be it a Vec, a HashMap or an IndexMap, the order of items influences the value of the resulting hash: [a, b] and [b, a] have different hashes.

Meanwhile, there is some information we do not want to track. This is the case of the value of LocalDefId. Inserting a function in a file will change other functions LocalDefId, but it will not change their DefPathHash.

My concern is about controlling this information flow. In order to do that ToStableHashKey trait replaces the iteration order of the collection (which for hash maps is based on the key and the allocated memory capacity and should be irrelevant to the compilation), by the order of a stable hash key (the DefPathHash when the key is LocalDefId). By sorting the vectors by stable key, we manage the information flow.

Using IndexMap, the iteration order is the insertion order. Normally, this insertion order should only depend on tracked information obtained by depending on another query. For instance, a HIR visitor will create a query dependency on hir_owner_nodes, which hashes the in-code declaration order of functions. However, and this is my concern, the order of LocalDefId is freely available without using a query and is purposely untracked.

In order to make IndexMaps safe for incr. comp., we need to ensure untracked information is inaccessible.

Known issues:

• Stop implementing PartialOrd and Ord on DefId;
• Stop implementing PartialOrd, Ord and Idx for LocalDefId;
• Stop implementing PartialOrd, Ord and Idx for LocalExpnId;
• Stop implementing PartialOrd and Ord for SyntaxContext;
• Enforce that UNTRACKED options are not accessed within a query.

Originally posted by @cjgillot in #90253 (comment)

[pierwill]

• Stop implementing PartialOrd and Ord on DefId...

Can these items be done one at a time?

[cjgillot]

Of course!

[pierwill]

Will give this a go and see what happens. @rustbot claim

[pierwill]

I started experimenting with LocalDefId. I wonder if the DefId work might end up being slightly less complex. 🤔

[pierwill]

I wonder if the DefId work might end up being slightly less complex. 🤔

Update: No. 😄

[pierwill]

Looks like removing Ord, PartialOrd for ExpnId and LocalExpnId might require changes to the macro rustc_index::newtype_index because of this line:

rust/compiler/rustc_index/src/vec.rs

Line 107 in 473eaa4

#[derive(Copy, PartialEq, Eq, Hash, PartialOrd, Ord, $($derives),*)]

[bjorn3]

Track accesses to command-line options;
Track accesses to debugging command-line options.

Most of them are already "tracked" by discarding the entire incr comp cache if they change. The ones that aren't tracked are explicitly not tracked. See the UNTRACKED mentions in https://github.com/rust-lang/rust/blob/d22dd65835190278f315e06442614142653ec98f/compiler/rustc_session/src/options.rs A couple of them should be marked as TRACKED though I think.

[pierwill]

Here's where we'd be if we merge #90408:

• Stop implementing PartialOrd, Ord for HirId
• Stop implementing PartialOrd, Ord for DefId
• Stop implementing PartialOrd, Ord for LocalDefId
• Stop implementing Idx for LocalDefId
• Stop implementing PartialOrd, Ord for ExpnId
• Stop implementing PartialOrd, Ord for LocalExpnId
• Stop implementing Idx for LocalExpnId