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:
Originally posted by @cjgillot in #90253 (comment)
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 functionsLocalDefId, but it will not change theirDefPathHash.My concern is about controlling this information flow. In order to do that
ToStableHashKeytrait 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 (theDefPathHashwhen the key isLocalDefId). 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 onhir_owner_nodes, which hashes the in-code declaration order of functions. However, and this is my concern, the order ofLocalDefIdis 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:
PartialOrdandOrdonDefId;PartialOrd,OrdandIdxforLocalDefId;PartialOrd,OrdandIdxforLocalExpnId;PartialOrdandOrdforSyntaxContext;Originally posted by @cjgillot in #90253 (comment)