rust-lang
Deterministic `FxHashSet` wrapper
r? @nagisa
(rust-highfive has picked a reviewer for you, use r? to override)
Right now it seems that StableSet doesn't implement Decodable. I wonder if it might be worth it to implement HashStable for FxHashSet directly, and remove the implementation for HashSet.
I had a couple of questions:
-
Decodablealso seems to requireHashand notHashStable. Is that an issue here? - I suspect I might come across this issue in multiple places, how do I decide for each one?
The job mingw-check failed! Check out the build log: (web) (plain)
Click to see the possible cause of the failure (guessed by this bot)
Checking rustc_ast_lowering v0.0.0 (/checkout/compiler/rustc_ast_lowering)
Checking rustc_ast_passes v0.0.0 (/checkout/compiler/rustc_ast_passes)
Checking rustc_expand v0.0.0 (/checkout/compiler/rustc_expand)
Checking rustc_builtin_macros v0.0.0 (/checkout/compiler/rustc_builtin_macros)
error[E0599]: the method `hash_stable` exists for reference `&std::sync::Arc<HashSet<rustc_span::def_id::LocalDefId, BuildHasherDefault<FxHasher>>>`, but its trait bounds were not satisfied
--> compiler/rustc_middle/src/ty/context.rs:807:32
|
807 | used_trait_imports.hash_stable(hcx, hasher);
| ^^^^^^^^^^^ method cannot be called on `&std::sync::Arc<HashSet<rustc_span::def_id::LocalDefId, BuildHasherDefault<FxHasher>>>` due to unsatisfied trait bounds
::: /checkout/library/std/src/collections/hash/set.rs:112:1
|
|
112 | pub struct HashSet<T, S = RandomState> {
| -------------------------------------- doesn't satisfy `_: HashStable<_>`
::: /checkout/library/alloc/src/sync.rs:235:1
|
|
235 | pub struct Arc<T: ?Sized> {
| ------------------------- doesn't satisfy `_: HashStable<_>`
= note: the following trait bounds were not satisfied:
= note: the following trait bounds were not satisfied:
`HashSet<rustc_span::def_id::LocalDefId, BuildHasherDefault<FxHasher>>: HashStable<_>`
which is required by `std::sync::Arc<HashSet<rustc_span::def_id::LocalDefId, BuildHasherDefault<FxHasher>>>: HashStable<_>`
`std::sync::Arc<HashSet<rustc_span::def_id::LocalDefId, BuildHasherDefault<FxHasher>>>: HashStable<_>`
which is required by `&std::sync::Arc<HashSet<rustc_span::def_id::LocalDefId, BuildHasherDefault<FxHasher>>>: HashStable<_>`
error[E0599]: the method `hash_stable` exists for reference `&HashSet<rustc_span::def_id::DefId, BuildHasherDefault<FxHasher>>`, but its trait bounds were not satisfied
--> compiler/rustc_middle/src/ty/context.rs:809:35
|
809 | concrete_opaque_types.hash_stable(hcx, hasher);
| ^^^^^^^^^^^ method cannot be called on `&HashSet<rustc_span::def_id::DefId, BuildHasherDefault<FxHasher>>` due to unsatisfied trait bounds
::: /checkout/library/std/src/collections/hash/set.rs:112:1
|
|
112 | pub struct HashSet<T, S = RandomState> {
| -------------------------------------- doesn't satisfy `_: HashStable<_>`
= note: the following trait bounds were not satisfied:
= note: the following trait bounds were not satisfied:
`HashSet<rustc_span::def_id::DefId, BuildHasherDefault<FxHasher>>: HashStable<_>`
which is required by `&HashSet<rustc_span::def_id::DefId, BuildHasherDefault<FxHasher>>: HashStable<_>`
error[E0599]: the method `hash_stable` exists for reference `&HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>`, but its trait bounds were not satisfied
|
9 | #[derive(HashStable, Debug)]
| ^^^^^^^^^^
| |
| |
| method cannot be called on `&HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>` due to unsatisfied trait bounds
|
::: /checkout/library/std/src/collections/hash/set.rs:112:1
|
|
112 | pub struct HashSet<T, S = RandomState> {
| -------------------------------------- doesn't satisfy `_: HashStable<_>`
::: /cargo/registry/src/github.com-1ecc6299db9ec823/synstructure-0.12.6/src/macros.rs:94:9
|
94 | / pub fn $derives(
95 | | i: $crate::macros::TokenStream
95 | | i: $crate::macros::TokenStream
96 | | ) -> $crate::macros::TokenStream {
| |________________________________________- in this expansion of `#[derive(HashStable)]`
|
= note: the following trait bounds were not satisfied:
`HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>: HashStable<_>`
which is required by `&HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>: HashStable<_>`
error[E0599]: the method `hash_stable` exists for reference `&HashMap<rustc_span::def_id::LocalDefId, HashSet<rustc_hir::ItemLocalId, BuildHasherDefault<FxHasher>>, BuildHasherDefault<FxHasher>>`, but its trait bounds were not satisfied
|
90 | #[derive(Default, HashStable, Debug)]
| ^^^^^^^^^^
| |
| |
| method cannot be called on `&HashMap<rustc_span::def_id::LocalDefId, HashSet<rustc_hir::ItemLocalId, BuildHasherDefault<FxHasher>>, BuildHasherDefault<FxHasher>>` due to unsatisfied trait bounds
|
::: /checkout/library/std/src/collections/hash/map.rs:209:1
|
|
209 | pub struct HashMap<K, V, S = RandomState> {
| ----------------------------------------- doesn't satisfy `_: HashStable<_>`
::: /checkout/library/std/src/collections/hash/set.rs:112:1
|
|
112 | pub struct HashSet<T, S = RandomState> {
| -------------------------------------- doesn't satisfy `_: HashStable<_>`
::: /cargo/registry/src/github.com-1ecc6299db9ec823/synstructure-0.12.6/src/macros.rs:94:9
|
94 | / pub fn $derives(
95 | | i: $crate::macros::TokenStream
95 | | i: $crate::macros::TokenStream
96 | | ) -> $crate::macros::TokenStream {
| |________________________________________- in this expansion of `#[derive(HashStable)]`
|
= note: the following trait bounds were not satisfied:
`HashSet<rustc_hir::ItemLocalId, BuildHasherDefault<FxHasher>>: HashStable<_>`
which is required by `HashMap<rustc_span::def_id::LocalDefId, HashSet<rustc_hir::ItemLocalId, BuildHasherDefault<FxHasher>>, BuildHasherDefault<FxHasher>>: HashStable<_>`
`HashMap<rustc_span::def_id::LocalDefId, HashSet<rustc_hir::ItemLocalId, BuildHasherDefault<FxHasher>>, BuildHasherDefault<FxHasher>>: HashStable<_>`
which is required by `&HashMap<rustc_span::def_id::LocalDefId, HashSet<rustc_hir::ItemLocalId, BuildHasherDefault<FxHasher>>, BuildHasherDefault<FxHasher>>: HashStable<_>`
error[E0599]: the method `hash_stable` exists for reference `&HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>`, but its trait bounds were not satisfied
|
59 | #[derive(HashStable, Debug)]
| ^^^^^^^^^^
| |
| |
| method cannot be called on `&HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>` due to unsatisfied trait bounds
|
::: /checkout/library/std/src/collections/hash/set.rs:112:1
|
|
112 | pub struct HashSet<T, S = RandomState> {
| -------------------------------------- doesn't satisfy `_: HashStable<_>`
::: /cargo/registry/src/github.com-1ecc6299db9ec823/synstructure-0.12.6/src/macros.rs:94:9
|
94 | / pub fn $derives(
95 | | i: $crate::macros::TokenStream
95 | | i: $crate::macros::TokenStream
96 | | ) -> $crate::macros::TokenStream {
| |________________________________________- in this expansion of `#[derive(HashStable)]`
|
= note: the following trait bounds were not satisfied:
`HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>: HashStable<_>`
which is required by `&HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>: HashStable<_>`
error[E0277]: the trait bound `StableSet<rustc_hir::ItemLocalId>: Encodable<__E>` is not satisfied
--> compiler/rustc_middle/src/ty/context.rs:351:10
|
351 | #[derive(TyEncodable, TyDecodable, Debug)]
| |
| |
| the trait `Encodable<__E>` is not implemented for `StableSet<rustc_hir::ItemLocalId>`
|
::: /cargo/registry/src/github.com-1ecc6299db9ec823/synstructure-0.12.6/src/macros.rs:94:9
|
94 | / pub fn $derives(
94 | / pub fn $derives(
95 | | i: $crate::macros::TokenStream
96 | | ) -> $crate::macros::TokenStream {
| |________________________________________- in this expansion of `#[derive(TyEncodable)]`
error[E0277]: the trait bound `StableSet<rustc_hir::ItemLocalId>: Decodable<__D>` is not satisfied
--> compiler/rustc_middle/src/ty/context.rs:459:5
|
459 | coercion_casts: ItemLocalSet,
| ^^^^^^^^^^^^^^ the trait `Decodable<__D>` is not implemented for `StableSet<rustc_hir::ItemLocalId>`
error[E0277]: the trait bound `StableSet<rustc_hir::ItemLocalId>: Decodable<__D>` is not satisfied
--> compiler/rustc_middle/src/ty/context.rs:351:23
|
351 | #[derive(TyEncodable, TyDecodable, Debug)]
| |
| |
| the trait `Decodable<__D>` is not implemented for `StableSet<rustc_hir::ItemLocalId>`
|
::: /cargo/registry/src/github.com-1ecc6299db9ec823/synstructure-0.12.6/src/macros.rs:94:9
|
94 | / pub fn $derives(
94 | / pub fn $derives(
95 | | i: $crate::macros::TokenStream
96 | | ) -> $crate::macros::TokenStream {
| |________________________________________- in this expansion of `#[derive(TyDecodable)]`
error[E0277]: the trait bound `StableSet<rustc_hir::ItemLocalId>: Decodable<__D>` is not satisfied
--> compiler/rustc_middle/src/ty/context.rs:511:9
|
511 | pub treat_byte_string_as_slice: ItemLocalSet,
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Decodable<__D>` is not implemented for `StableSet<rustc_hir::ItemLocalId>`
Some errors have detailed explanations: E0277, E0599.
For more information about an error, try `rustc --explain E0277`.
error: could not compile `rustc_middle` due to 9 previous errors
warning: build failed, waiting for other jobs to finish...
I wonder if it might be worth it to implement HashStable for FxHashSet directly, and remove the implementation for HashSet.
FxHashSet is just an alias for the regular HashSet (with a different hash algorithm), so it should not implement HashStable either.
Decodable also seems to require Hash and not HashStable. Is that an issue here?
It's not a problem for a type to implement both Hash and HashStable. You should be able just #[derive(Encodable, Decodable)] for StableSet. We'll definitely need to be able encode and decode these for incremental compilation.
It's not a problem for a type to implement both
HashandHashStable.
Ah, since it was a wrapper I assumed we wanted to drop some methods and traits, but wasn't sure which ones.
The job mingw-check failed! Check out the build log: (web) (plain)
Click to see the possible cause of the failure (guessed by this bot)
Checking rustc_builtin_macros v0.0.0 (/checkout/compiler/rustc_builtin_macros)
error[E0599]: no method named `iter` found for struct `StableSet` in the current scope
--> compiler/rustc_middle/src/middle/mod.rs:22:38
|
22 | .chain(self.unstable.iter().map(|f| (*f, None)))
| ^^^^ method not found in `StableSet<rustc_span::Symbol>`
For more information about this error, try `rustc --explain E0599`.
error: could not compile `rustc_middle` due to previous error
warning: build failed, waiting for other jobs to finish...
error: build failed
The current problem is that some places require .iter(), I recognize that as one of the things we'd like to avoid in StableSet. I have a few suggestions, maybe you have better ones:
- Add an
unsafefunctioniter(), or call ititer_unstable()to avoid performance loss. - Use the
sorted_vector()'sinto_iter().
For point 2, I have a question: Where does one create or acquire HCX (I assume that's hashing context).
Where does one create or acquire HCX (I assume that's hashing context).
Using either tcx.create_stable_hashing_context or tcx.create_no_span_stable_hashing_context. The TyCtxt type is not available in rustc_data_structure, so the hashing context will have to be passed in as argument.
The job mingw-check failed! Check out the build log: (web) (plain)
Click to see the possible cause of the failure (guessed by this bot)
Checking rustc_save_analysis v0.0.0 (/checkout/compiler/rustc_save_analysis)
error[E0599]: no method named `extend` found for struct `StableSet` in the current scope
--> compiler/rustc_passes/src/liveness.rs:283:41
|
283 | shorthand_field_ids.extend(short.iter().map(|f| f.pat.hir_id));
| ^^^^^^ method not found in `StableSet<HirId>`
For more information about this error, try `rustc --explain E0599`.
error: could not compile `rustc_passes` due to previous error
warning: build failed, waiting for other jobs to finish...
warning: build failed, waiting for other jobs to finish...
error[E0277]: the trait bound `for<'a> HashSet<LocalDefId, BuildHasherDefault<FxHasher>>: rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` is not satisfied
--> compiler/rustc_query_impl/src/plumbing.rs:218:14
216 | / macro_rules! hash_result {
217 | | ([]) => {{
218 | | Some(dep_graph::hash_result)
218 | | Some(dep_graph::hash_result)
| | ^^^^^^^^^^^^^^^^^^^^^^ the trait `for<'a> rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` is not implemented for `HashSet<LocalDefId, BuildHasherDefault<FxHasher>>`
219 | | }};
... |
224 | | hash_result!([$($modifiers)*])
225 | | };
226 | | }
| | -
| | |
| | |
| |____in this expansion of `hash_result!` (#3)
| in this expansion of `hash_result!` (#4)
254 | / macro_rules! define_queries {
254 | / macro_rules! define_queries {
255 | | (<$tcx:tt>
256 | | $($(#[$attr:meta])*
257 | | [$($modifiers:tt)*] fn $name:ident($($K:tt)*) -> $V:ty,)*) => {
... |
355 | | hash_result: hash_result!([$($modifiers)*]),
... |
468 | | }
469 | | }
469 | | }
| |____- in this expansion of `define_queries!` (#2)
::: compiler/rustc_query_impl/src/lib.rs:55:1
|
55 | rustc_query_append! { [define_queries!][<'tcx>] }
| ------------------------------------------------- in this macro invocation (#1)
---
| | |
| |_in this expansion of `rustc_query_append!` (#1)
| in this macro invocation (#2)
|
= note: required because of the requirements on the impl of `for<'a> rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` for `(HashSet<LocalDefId, BuildHasherDefault<FxHasher>>, HashMap<LocalDefId, Vec<(DefId, DefId)>, BuildHasherDefault<FxHasher>>)`
note: required by a bound in `hash_result`
--> /checkout/compiler/rustc_query_system/src/dep_graph/graph.rs:101:8
|
101 | R: for<'a> HashStable<StableHashingContext<'a>>,
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `hash_result`
error[E0277]: the trait bound `for<'a> HashSet<LocalDefId, BuildHasherDefault<FxHasher>>: rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` is not satisfied
--> compiler/rustc_query_impl/src/plumbing.rs:218:14
216 | / macro_rules! hash_result {
217 | | ([]) => {{
218 | | Some(dep_graph::hash_result)
218 | | Some(dep_graph::hash_result)
| | ^^^^^^^^^^^^^^^^^^^^^^ the trait `for<'a> rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` is not implemented for `HashSet<LocalDefId, BuildHasherDefault<FxHasher>>`
219 | | }};
225 | | };
226 | | }
226 | | }
| |___- in this expansion of `hash_result!` (#3)
...
254 | / macro_rules! define_queries {
255 | | (<$tcx:tt>
256 | | $($(#[$attr:meta])*
257 | | [$($modifiers:tt)*] fn $name:ident($($K:tt)*) -> $V:ty,)*) => {
... |
355 | | hash_result: hash_result!([$($modifiers)*]),
... |
468 | | }
469 | | }
469 | | }
| |___- in this expansion of `define_queries!` (#2)
::: compiler/rustc_query_impl/src/lib.rs:55:1
|
55 | rustc_query_append! { [define_queries!][<'tcx>] }
| ------------------------------------------------- in this macro invocation (#1)
---
| | |
| |_in this expansion of `rustc_query_append!` (#1)
| in this macro invocation (#2)
|
= note: required because of the requirements on the impl of `for<'a> rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` for `&HashSet<LocalDefId, BuildHasherDefault<FxHasher>>`
note: required by a bound in `hash_result`
--> /checkout/compiler/rustc_query_system/src/dep_graph/graph.rs:101:8
|
101 | R: for<'a> HashStable<StableHashingContext<'a>>,
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `hash_result`
error[E0277]: the trait bound `for<'a> HashSet<LocalDefId, BuildHasherDefault<FxHasher>>: rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` is not satisfied
--> compiler/rustc_query_impl/src/plumbing.rs:218:14
216 | / macro_rules! hash_result {
217 | | ([]) => {{
218 | | Some(dep_graph::hash_result)
218 | | Some(dep_graph::hash_result)
| | ^^^^^^^^^^^^^^^^^^^^^^ the trait `for<'a> rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` is not implemented for `HashSet<LocalDefId, BuildHasherDefault<FxHasher>>`
219 | | }};
... |
224 | | hash_result!([$($modifiers)*])
225 | | };
226 | | }
| | -
| | |
| | |
| |____in this expansion of `hash_result!` (#3)
| in this expansion of `hash_result!` (#4)
254 | / macro_rules! define_queries {
254 | / macro_rules! define_queries {
255 | | (<$tcx:tt>
256 | | $($(#[$attr:meta])*
257 | | [$($modifiers:tt)*] fn $name:ident($($K:tt)*) -> $V:ty,)*) => {
... |
355 | | hash_result: hash_result!([$($modifiers)*]),
... |
468 | | }
469 | | }
469 | | }
| |____- in this expansion of `define_queries!` (#2)
::: compiler/rustc_query_impl/src/lib.rs:55:1
|
55 | rustc_query_append! { [define_queries!][<'tcx>] }
| ------------------------------------------------- in this macro invocation (#1)
---
|
note: required by a bound in `hash_result`
--> /checkout/compiler/rustc_query_system/src/dep_graph/graph.rs:101:8
|
101 | R: for<'a> HashStable<StableHashingContext<'a>>,
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `hash_result`
error[E0277]: the trait bound `for<'a> HashSet<ItemLocalId, BuildHasherDefault<FxHasher>>: rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` is not satisfied
--> compiler/rustc_query_impl/src/plumbing.rs:218:14
216 | / macro_rules! hash_result {
217 | | ([]) => {{
218 | | Some(dep_graph::hash_result)
218 | | Some(dep_graph::hash_result)
| | ^^^^^^^^^^^^^^^^^^^^^^ the trait `for<'a> rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` is not implemented for `HashSet<ItemLocalId, BuildHasherDefault<FxHasher>>`
219 | | }};
225 | | };
226 | | }
226 | | }
| |___- in this expansion of `hash_result!` (#3)
...
254 | / macro_rules! define_queries {
255 | | (<$tcx:tt>
256 | | $($(#[$attr:meta])*
257 | | [$($modifiers:tt)*] fn $name:ident($($K:tt)*) -> $V:ty,)*) => {
... |
355 | | hash_result: hash_result!([$($modifiers)*]),
... |
468 | | }
469 | | }
469 | | }
| |___- in this expansion of `define_queries!` (#2)
::: compiler/rustc_query_impl/src/lib.rs:55:1
|
55 | rustc_query_append! { [define_queries!][<'tcx>] }
| ------------------------------------------------- in this macro invocation (#1)
---
| | |
| |_in this expansion of `rustc_query_append!` (#1)
| in this macro invocation (#2)
|
= note: required because of the requirements on the impl of `for<'a> rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` for `&HashSet<ItemLocalId, BuildHasherDefault<FxHasher>>`
= note: 2 redundant requirements hidden
= note: required because of the requirements on the impl of `for<'a> rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` for `Option<(LocalDefId, &HashSet<ItemLocalId, BuildHasherDefault<FxHasher>>)>`
note: required by a bound in `hash_result`
--> /checkout/compiler/rustc_query_system/src/dep_graph/graph.rs:101:8
|
101 | R: for<'a> HashStable<StableHashingContext<'a>>,
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `hash_result`
error[E0277]: the trait bound `for<'a> HashSet<Symbol, BuildHasherDefault<FxHasher>>: rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` is not satisfied
--> compiler/rustc_query_impl/src/plumbing.rs:218:14
216 | / macro_rules! hash_result {
217 | | ([]) => {{
218 | | Some(dep_graph::hash_result)
218 | | Some(dep_graph::hash_result)
| | ^^^^^^^^^^^^^^^^^^^^^^ the trait `for<'a> rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` is not implemented for `HashSet<Symbol, BuildHasherDefault<FxHasher>>`
219 | | }};
225 | | };
226 | | }
226 | | }
| |___- in this expansion of `hash_result!` (#3)
...
254 | / macro_rules! define_queries {
255 | | (<$tcx:tt>
256 | | $($(#[$attr:meta])*
257 | | [$($modifiers:tt)*] fn $name:ident($($K:tt)*) -> $V:ty,)*) => {
... |
355 | | hash_result: hash_result!([$($modifiers)*]),
... |
468 | | }
469 | | }
469 | | }
| |___- in this expansion of `define_queries!` (#2)
::: compiler/rustc_query_impl/src/lib.rs:55:1
|
55 | rustc_query_append! { [define_queries!][<'tcx>] }
| ------------------------------------------------- in this macro invocation (#1)
---
| | |
| |_in this expansion of `rustc_query_append!` (#1)
| in this macro invocation (#2)
|
= note: required because of the requirements on the impl of `for<'a> rustc_data_structures::stable_hasher::HashStable<StableHashingContext<'a>>` for `&HashSet<Symbol, BuildHasherDefault<FxHasher>>`
note: required by a bound in `hash_result`
--> /checkout/compiler/rustc_query_system/src/dep_graph/graph.rs:101:8
|
101 | R: for<'a> HashStable<StableHashingContext<'a>>,
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `hash_result`
For more information about this error, try `rustc --explain E0277`.
error: build failed
Build completed unsuccessfully in 0:02:45
I have tried in vain to grok through the layers of macros here, I'm not entirely sure where the last compilation error is coming from. I've tried to grep for HashSet and FxHashSet in all of the files in that traceback, but nothing was found.
You are probably looking for https://github.com/rust-lang/rust/blob/master/compiler/rustc_middle/src/query/mod.rs
Yeah, those errors are really hard to decipher. @bjorn3 is right: https://github.com/rust-lang/rust/blob/master/compiler/rustc_middle/src/query/mod.rs defines all queries in the compiler. All query keys and results must implement HashStable -- and HashSet (which includes FxHashSet) doesn't anymore. So all occurrences of those must be replaced with StableSet in that file. Likewise, the "query prodivers" (i.e. the actual implementations of the queries defined in that file) must be update accordingly.
The current problem is that some places require .iter(), I recognize that as one of the things we'd like to avoid in StableSet. I have a few suggestions, maybe you have better ones:
In some cases I've seen, iter() is only used in a way that does not actually expose the order of the items in the set, e.g. my_set.iter().any(|x| x > 0). We could add those methods directly to StableSet. any() and all() come to mind.
Also, adding extend() to StableSet should be fine.
The job x86_64-gnu-llvm-12 failed! Check out the build log: (web) (plain)
Click to see the possible cause of the failure (guessed by this bot)
Compiling rustc_middle v0.0.0 (/checkout/compiler/rustc_middle)
Compiling rustc_ast_lowering v0.0.0 (/checkout/compiler/rustc_ast_lowering)
Compiling rustc_ast_passes v0.0.0 (/checkout/compiler/rustc_ast_passes)
Compiling rustc_expand v0.0.0 (/checkout/compiler/rustc_expand)
error[E0412]: cannot find type `FxHashSet` in this scope
|
18 | / rustc_queries! {
19 | | query trigger_delay_span_bug(key: DefId) -> () {
20 | | desc { "trigger a delay span bug" }
20 | | desc { "trigger a delay span bug" }
21 | | }
... |
1049 | | query asm_target_features(def_id: DefId) -> &'tcx FxHashSet<Symbol> {
| | ^^^^^^^^^ help: a type alias with a similar name exists: `FxHashMap`
1946 | | }
1947 | | }
| |_- in this expansion of `rustc_query_append!`
|
|
::: /cargo/registry/src/github.com-1ecc6299db9ec823/rustc-hash-1.1.0/src/lib.rs:43:1
|
43 | pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
| ----------------------------------------------------------------------- similarly named type alias `FxHashMap` defined here
::: compiler/rustc_middle/src/ty/query.rs:339:1
|
339 | rustc_query_append! { [define_callbacks!][<'tcx>] }
| --------------------------------------------------- in this macro invocation
| --------------------------------------------------- in this macro invocation
|
= note: consider importing one of these items:
crate::ty::FxHashSet
rustc_data_structures::stable_set::FxHashSet
Compiling rustc_builtin_macros v0.0.0 (/checkout/compiler/rustc_builtin_macros)
error[E0277]: the trait bound `rustc_data_structures::stable_set::StableSet<rustc_span::Symbol>: ArenaAllocatable<'_, _>` is not satisfied
--> compiler/rustc_middle/src/ty/context.rs:2988:25
|
2988 | tcx.arena.alloc(tcx.resolutions(()).glob_map.get(&id).cloned().unwrap_or_default())
| ----- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected an implementor of trait `ArenaAllocatable<'_, _>`
| required by a bound introduced by this call
|
|
= note: required because of the requirements on the impl of `ArenaAllocatable<'_, IsCopy>` for `rustc_data_structures::stable_set::StableSet<rustc_span::Symbol>`
note: required by a bound in `Arena::<'tcx>::alloc`
--> /checkout/compiler/rustc_arena/src/lib.rs:598:25
|
542 | / pub macro declare_arena([$($a:tt $name:ident: $ty:ty,)*]) {
544 | | pub struct Arena<'tcx> {
544 | | pub struct Arena<'tcx> {
545 | | pub dropless: $crate::DroplessArena,
... |
598 | | pub fn alloc<T: ArenaAllocatable<'tcx, C>, C>(&self, value: T) -> &mut T {
| | ^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Arena::<'tcx>::alloc`
617 | | }
618 | | }
618 | | }
| |__- in this expansion of `rustc_arena::declare_arena!` (#2)
|
::: compiler/rustc_middle/src/arena.rs:6:1
|
6 | / macro_rules! arena_types {
7 | | ($macro:path) => (
8 | | $macro!([
9 | || [] layout: rustc_target::abi::Layout,
9 | || [] layout: rustc_target::abi::Layout,
10 | || [] fn_abi: rustc_target::abi::call::FnAbi<'tcx, rustc_middle::ty::Ty<'tcx>>,
11 | || // AdtDef are interned and compared by address
... ||
104 | || [] dep_kind: rustc_middle::dep_graph::DepKindStruct,
| ||__________- in this macro invocation (#2)
106 | | )
107 | | }
107 | | }
| |_- in this expansion of `arena_types!` (#1)
108 |
109 | arena_types!(rustc_arena::declare_arena);
help: consider borrowing here
|
|
2988 | tcx.arena.alloc(&tcx.resolutions(()).glob_map.get(&id).cloned().unwrap_or_default())
error[E0283]: type annotations needed
--> compiler/rustc_middle/src/ty/query.rs:216:28
|
|
178 | / macro_rules! define_callbacks {
179 | | (<$tcx:tt>
180 | | $($(#[$attr:meta])*
181 | | [$($modifiers:tt)*] fn $name:ident($($K:tt)*) -> $V:ty,)*) => {
214 | | #[derive(Default)]
| | ------- in this derive macro expansion (#3)
| | ------- in this derive macro expansion (#3)
215 | | pub struct QueryCaches<$tcx> {
216 | | $($(#[$attr])* pub $name: QueryCacheStore<query_storage::$name<$tcx>>,)*
... |
324 | | };
325 | | }
325 | | }
| |___- in this expansion of `define_callbacks!` (#2)
339 | rustc_query_append! { [define_callbacks!][<'tcx>] }
| --------------------------------------------------- in this macro invocation (#1)
|
::: compiler/rustc_middle/src/query/mod.rs:18:1
The current compilation problem is that we need an implementation of ArenaAllocatable for StableSet. One is already provided for all types that impl IntoIterator, but we don't on purpose. We could either provide a bunch of implementations manually, or better, have a trait that all of our eventual types will implement. I like the second idea better, and I believe it'll work well even for HashMaps.
The job mingw-check failed! Check out the build log: (web) (plain)
Click to see the possible cause of the failure (guessed by this bot)
Checking rustc_ast_lowering v0.0.0 (/checkout/compiler/rustc_ast_lowering)
Checking rustc_ast_passes v0.0.0 (/checkout/compiler/rustc_ast_passes)
Checking rustc_expand v0.0.0 (/checkout/compiler/rustc_expand)
Checking rustc_builtin_macros v0.0.0 (/checkout/compiler/rustc_builtin_macros)
error[E0277]: the trait bound `rustc_data_structures::stable_set::StableSet<rustc_span::Symbol>: ArenaAllocatable<'_, _>` is not satisfied
--> compiler/rustc_middle/src/ty/context.rs:2988:25
|
2988 | tcx.arena.alloc(tcx.resolutions(()).glob_map.get(&id).cloned().unwrap_or_default())
| ----- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected an implementor of trait `ArenaAllocatable<'_, _>`
| required by a bound introduced by this call
|
|
= note: required because of the requirements on the impl of `ArenaAllocatable<'_, IsCopy>` for `rustc_data_structures::stable_set::StableSet<rustc_span::Symbol>`
note: required by a bound in `Arena::<'tcx>::alloc`
--> /checkout/compiler/rustc_arena/src/lib.rs:598:25
|
542 | / pub macro declare_arena([$($a:tt $name:ident: $ty:ty,)*]) {
544 | | pub struct Arena<'tcx> {
544 | | pub struct Arena<'tcx> {
545 | | pub dropless: $crate::DroplessArena,
... |
598 | | pub fn alloc<T: ArenaAllocatable<'tcx, C>, C>(&self, value: T) -> &mut T {
| | ^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Arena::<'tcx>::alloc`
617 | | }
618 | | }
618 | | }
| |__- in this expansion of `rustc_arena::declare_arena!` (#2)
|
::: compiler/rustc_middle/src/arena.rs:6:1
|
6 | / macro_rules! arena_types {
7 | | ($macro:path) => (
8 | | $macro!([
9 | || [] layout: rustc_target::abi::Layout,
9 | || [] layout: rustc_target::abi::Layout,
10 | || [] fn_abi: rustc_target::abi::call::FnAbi<'tcx, rustc_middle::ty::Ty<'tcx>>,
11 | || // AdtDef are interned and compared by address
... ||
104 | || [] dep_kind: rustc_middle::dep_graph::DepKindStruct,
| ||__________- in this macro invocation (#2)
106 | | )
107 | | }
107 | | }
| |_- in this expansion of `arena_types!` (#1)
108 |
109 | arena_types!(rustc_arena::declare_arena);
help: consider borrowing here
|
|
2988 | tcx.arena.alloc(&tcx.resolutions(()).glob_map.get(&id).cloned().unwrap_or_default())
For more information about this error, try `rustc --explain E0277`.
error: could not compile `rustc_middle` due to previous error
warning: build failed, waiting for other jobs to finish...
Where does one create or acquire HCX (I assume that's hashing context).
Using either
tcx.create_stable_hashing_contextortcx.create_no_span_stable_hashing_context. TheTyCtxttype is not available inrustc_data_structure, so the hashing context will have to be passed in as argument.
Another open question: Which one to use where? I could avoid compilation errors with either but I don't want to code in something that won't pass tests, or worse, cause silent bugs.
:umbrella: The latest upstream changes (presumably #94129) made this pull request unmergeable. Please resolve the merge conflicts.
One thing that I'm noticing here is that we probably can reduce the number of instances where StableSet is used. We only need to use StableSet for things that implement HashStable (which is mainly query keys and query results). However, we don't need to use it for intermediate values, even if those get turned into a StableSet later on. This is such a case: https://github.com/rust-lang/rust/pull/94188/files#diff-87880ceb989914cb25dc43961cb1cee5e7b07d8b04bcd9c967e7995cd85315d9R471
ResolveLifetimes needs to contain StableSets because it implements HashStable -- but NamedRegionMap is just an intermediate value, so it can use regular FxHashSets.
Thanks for all the tips! I'm fairly sure I got compilation errors for all the places, but I'll go back and try to refactor where appropriate.
@hameerabbasi Triage: Returning to author to address comments.
FYI: when a PR is ready for review, send a message containing
@rustbot ready to switch to S-waiting-on-review so the PR is in the reviewer's backlog.
@rustbot label: +S-waiting-on-author -S-waiting-on-review
The job mingw-check failed! Check out the build log: (web) (plain)
Click to see the possible cause of the failure (guessed by this bot)
Checking rustc_ast_lowering v0.0.0 (/checkout/compiler/rustc_ast_lowering)
Checking rustc_ast_passes v0.0.0 (/checkout/compiler/rustc_ast_passes)
Checking rustc_expand v0.0.0 (/checkout/compiler/rustc_expand)
Checking rustc_builtin_macros v0.0.0 (/checkout/compiler/rustc_builtin_macros)
error[E0277]: the trait bound `rustc_data_structures::stable_set::StableSet<rustc_span::Symbol>: ArenaAllocatable<'_, _>` is not satisfied
--> compiler/rustc_middle/src/ty/context.rs:2950:25
|
2950 | tcx.arena.alloc(tcx.resolutions(()).glob_map.get(&id).cloned().unwrap_or_default())
| ----- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected an implementor of trait `ArenaAllocatable<'_, _>`
| required by a bound introduced by this call
|
|
= note: required because of the requirements on the impl of `ArenaAllocatable<'_, IsCopy>` for `rustc_data_structures::stable_set::StableSet<rustc_span::Symbol>`
note: required by a bound in `Arena::<'tcx>::alloc`
--> /checkout/compiler/rustc_arena/src/lib.rs:598:25
|
542 | / pub macro declare_arena([$($a:tt $name:ident: $ty:ty,)*]) {
544 | | pub struct Arena<'tcx> {
544 | | pub struct Arena<'tcx> {
545 | | pub dropless: $crate::DroplessArena,
... |
598 | | pub fn alloc<T: ArenaAllocatable<'tcx, C>, C>(&self, value: T) -> &mut T {
| | ^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Arena::<'tcx>::alloc`
617 | | }
618 | | }
618 | | }
| |__- in this expansion of `rustc_arena::declare_arena!` (#2)
|
::: compiler/rustc_middle/src/arena.rs:6:1
|
6 | / macro_rules! arena_types {
7 | | ($macro:path) => (
8 | | $macro!([
| |________________-
9 | || [] layout: rustc_target::abi::LayoutS<'tcx>,
10 | || [] fn_abi: rustc_target::abi::call::FnAbi<'tcx, rustc_middle::ty::Ty<'tcx>>,
11 | || // AdtDef are interned and compared by address
... ||
104 | || [] dep_kind: rustc_middle::dep_graph::DepKindStruct,
| ||__________- in this macro invocation (#2)
106 | | )
107 | | }
107 | | }
| |_- in this expansion of `arena_types!` (#1)
108 |
109 | arena_types!(rustc_arena::declare_arena);
help: consider borrowing here
|
|
2950 | tcx.arena.alloc(&tcx.resolutions(()).glob_map.get(&id).cloned().unwrap_or_default())
For more information about this error, try `rustc --explain E0277`.
error: could not compile `rustc_middle` due to previous error
warning: build failed, waiting for other jobs to finish...
The job mingw-check failed! Check out the build log: (web) (plain)
Click to see the possible cause of the failure (guessed by this bot)
Checking rustc_builtin_macros v0.0.0 (/checkout/compiler/rustc_builtin_macros)
error[E0308]: mismatched types
--> compiler/rustc_middle/src/ty/context.rs:2950:9
|
2950 | tcx.arena.alloc(tcx.resolutions(()).glob_map.get(&id).cloned().unwrap_or_default())
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `rustc_data_structures::stable_set::StableSet`, found struct `HashSet`
= note: expected reference `&rustc_data_structures::stable_set::StableSet<rustc_span::Symbol>`
= note: expected reference `&rustc_data_structures::stable_set::StableSet<rustc_span::Symbol>`
found mutable reference `&mut HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>`
For more information about this error, try `rustc --explain E0308`.
error: could not compile `rustc_middle` due to previous error
warning: build failed, waiting for other jobs to finish...
error: build failed
Okay, I've rebased and applied some of the suggested changes, so I'll ask where I'm unsure.
NamedRegionMap is just an intermediate value, so it can use regular FxHashSets.
I never really changed anything explicitly about NamedRegionMap, I assume it's due to the changes in define_id_collections which are used to define HirIdSet, which is contained in NamedRegionMap. One way around this is to pass a bool into define_id_collections saying when we want the stable versions. Would you like me to do that change?
Also please look at comments: https://github.com/rust-lang/rust/pull/94188#discussion_r835914105 and https://github.com/rust-lang/rust/pull/94188#discussion_r835914156 in combination with the error log, maybe there's something simple I'm missing.
@rustbot ready
Edit: The compilation error is related to https://github.com/rust-lang/rust/pull/94188#issuecomment-1048870740.
I do realise this, but I think I'm missing some API design choice that signifies "hey, iterate over this, but the iteration order is unstable and you shouldn't depend on it".
:umbrella: The latest upstream changes (presumably #94081) made this pull request unmergeable. Please resolve the merge conflicts.
I resolved a few more compilation errors here: https://github.com/michaelwoerister/rust/commit/6cf3e797364abf1a7fa6e83344307eded0efd259
But yes, I think it would be good to come up with an API design that allows us to safely iterate over items without exposing the order and without causing additional runtime overhead. I don't know yet, what that would look like exactly. I'll need to do some experimentation in order to get a feel for it.
I never really changed anything explicitly about NamedRegionMap, I assume it's due to the changes in define_id_collections which are used to define HirIdSet, which is contained in NamedRegionMap. One way around this is to pass a bool into define_id_collections saying when we want the stable versions. Would you like me to do that change?
Maybe it would be best to let the macro define both kinds of collections, something like:
#[macro_export]
macro_rules! define_id_collections {
($map_name:ident, $set_name:ident, $stable_map_name:ident, $stable_set_name:ident, $key:ty) => {
pub type $map_name<T> = $crate::fx::FxHashMap<$key, T>;
pub type $set_name = $crate::fx::FxHashSet<$key>;
pub type $stable_map_name<T> = $crate::stable_set::StableMap<$key, T>;
pub type $stable_set_name = $crate::stable_set::StableSet<$key>;
};
}
Another note: It would probably be good if the serialized version of StableSet was also deterministic. It's not strictly necessary, especially for the incr. comp. -- but I think crate metadata we want to be deterministic at the binary level, and it would be kind of surprising if StableSet was a source of indeterminism there.
Iteration order for FxHashSet is only dependent on the exact set of operations performed on it. There is no randomness introduced. Serializing an FxHashSet in iteration order into the crate metadata is perfectly deterministic. However as the HashStable impl ignores iteration order, this can cause the incremental compilation system to incorrectly ignore changes.
I think the safe way to compare them would be to simply compare the contents of the pointers. Maybe what we need isn't really a wrapper -- But instead just to:
- Implement a custom version of
HashStablefor pointer-like objects such asInterned, as it's recursive, it might fix the problems we have instead of a wrapper. - Fix the serialization of
FxHashSetandFxHashMap.
Implement a custom version of HashStable for pointer-like objects such as Interned, as it's recursive, it might fix the problems we have instead of a wrapper.
HashStable is completely irrelevant for hashmap/hashset iteration order. They use Hash instead. Interned's HashStable implementation is already completely deterministic. Hash is not for performance reasons.
Fix the serialization of FxHashSet and FxHashMap.
That doesn't fix the iteration order problem.
Let me clarify: The argument for making the serialized version independent of iteration order is only about deterministic builds, not about incremental compilation. That is, if we have two compilation sessions that both serialize a set {a, b, c} into crate metadata, we could end up with any permutation of that set in the binary stream if we do serialization via just encoding in the order that .iter() gives us, because {a, b, c} could be in any order internally when using pointers as keys.
Iteration order for FxHashSet is only dependent on the exact set of operations performed on it. There is no randomness introduced. Serializing an FxHashSet in iteration order into the crate metadata is perfectly deterministic.
I agree. There's an interesting (but not immediately relevant) subtlety there: As far as I know, FxHashSet, and SwissTable-based hash maps in general, do not give a guarantee that some_set has the same iteration order as some_set.into_iter().collect::<FxHashSet>(), so serializing to a sequence and then collecting the sequence might reshuffle things, even when no pointers are involved. But, yes, I don't think that that is necessarily a problem for deterministic builds. It's mostly pointer-like hash keys that I'm worried about.
I think it would be good to come up with an API design that allows us to safely iterate over items without exposing the order and without causing additional runtime overhead. I don't know yet, what that would look like exactly. I'll need to do some experimentation in order to get a feel for it.
I did some experimentation, and this is what I came up with: https://gist.github.com/michaelwoerister/ca40793a8d68c8ee60ce9af49bea89d3
It basically adds an unordered version of Iterator that only has methods that don't depend on the order of items (like map). This way we can merge data from one StableSet into another StableSet (possibly doing transformations on the data in between), as in the example:
let mut src: StableMap<u32, u32> = Default::default();
src.insert(1, 2);
let mut dst: StableMap<u64, u64> = Default::default();
dst.extend(src.items().map(|(&k, &v)| (k as u64 + 1, v as u64 + 1)))
The hope is that this allows us to avoid unnecessarily sorting things if they end up in an unsorted context afterwards anyway. Does that make sense?
Okay, I've rebased and added the suggested API. I'm attempting to mirror parts of the API as I need them, but I have to change over some occurrences first.
The job mingw-check failed! Check out the build log: (web) (plain)
Click to see the possible cause of the failure (guessed by this bot)
Checking rustc_ast_lowering v0.0.0 (/checkout/compiler/rustc_ast_lowering)
Checking rustc_ast_passes v0.0.0 (/checkout/compiler/rustc_ast_passes)
Checking rustc_expand v0.0.0 (/checkout/compiler/rustc_expand)
Checking rustc_builtin_macros v0.0.0 (/checkout/compiler/rustc_builtin_macros)
error[E0277]: the trait bound `rustc_data_structures::stable_set::StableSet<_>: From<&mut HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>>` is not satisfied
--> compiler/rustc_middle/src/ty/context.rs:2955:10
2955 | &StableSet::from(
2955 | &StableSet::from(
| ^^^^^^^^^^^^^^^ the trait `From<&mut HashSet<rustc_span::Symbol, BuildHasherDefault<FxHasher>>>` is not implemented for `rustc_data_structures::stable_set::StableSet<_>`
= help: the following implementations were found:
= help: the following implementations were found:
<rustc_data_structures::stable_set::StableSet<T> as From<HashSet<T, BuildHasherDefault<FxHasher>>>>
For more information about this error, try `rustc --explain E0277`.
error: could not compile `rustc_middle` due to previous error
warning: build failed, waiting for other jobs to finish...
error: could not compile `rustc_middle` due to previous error
:umbrella: The latest upstream changes (presumably #95524) made this pull request unmergeable. Please resolve the merge conflicts.
Basec on this comment, I'll switch to waiting on author to implement suggested changes. Please feel free to request a review when ready, thanks!
@rustbot -S-waiting-on-review +S-waiting-on-author
I think it's okay if someone else takes over after this weekend. I'll try to resolve the comments already posted.
It seems StableSet and StableMap were removed, any alternatives I should be aware of? Or should I add them back?
Hi, after we recently ran into a critical issue that could have been prevented by this, I decided to try and make some progress more quickly. I opened https://github.com/rust-lang/compiler-team/issues/533, which suggests a replacement for StableMap and StableSet, very much like I proposed above (https://github.com/rust-lang/rust/pull/94188#issuecomment-1087699472). This is mostly implemented in https://github.com/michaelwoerister/rust/commit/694136d64332619d25180ec789577b476fbbb020 (although I'm going to rename UnorderedMap to UnordMap, as eddyb suggested elsewhere). I'll try to make a PR this week.
If you are still interested in this topic, @hameerabbasi, I can ping you when the new collection types have been merged. Then we can start using them in more cases. But I would suggest doing it in smaller pieces at a time.
I suggest closing this particular PR -- although I do think the work that has been done here was very important in exploring the design space!
@michaelwoerister Feel free to cc me when the PR is ready! I'll follow along from the sidelines, and probably leave a question/comment here and there.
Just so you're aware, my time to work on FOSS in general is limited to about 4-6 hours a week, due to a day job, a move to another country and the procedures surrounding that. If you feel slow progress is still useful progress, I'd like to spend time on this.