diff options
30 files changed, 256 insertions, 147 deletions
diff --git a/compiler/rustc_codegen_ssa/src/back/symbol_export.rs b/compiler/rustc_codegen_ssa/src/back/symbol_export.rs index 54b523cb6bd..94841ab7b33 100644 --- a/compiler/rustc_codegen_ssa/src/back/symbol_export.rs +++ b/compiler/rustc_codegen_ssa/src/back/symbol_export.rs @@ -3,7 +3,7 @@ use crate::base::allocator_kind_for_codegen; use std::collections::hash_map::Entry::*; use rustc_ast::expand::allocator::{ALLOCATOR_METHODS, NO_ALLOC_SHIM_IS_UNSTABLE}; -use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::unord::UnordMap; use rustc_hir::def::DefKind; use rustc_hir::def_id::{CrateNum, DefId, DefIdMap, LocalDefId, LOCAL_CRATE}; use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrFlags; @@ -393,10 +393,10 @@ fn exported_symbols_provider_local( fn upstream_monomorphizations_provider( tcx: TyCtxt<'_>, (): (), -) -> DefIdMap<FxHashMap<GenericArgsRef<'_>, CrateNum>> { +) -> DefIdMap<UnordMap<GenericArgsRef<'_>, CrateNum>> { let cnums = tcx.crates(()); - let mut instances: DefIdMap<FxHashMap<_, _>> = Default::default(); + let mut instances: DefIdMap<UnordMap<_, _>> = Default::default(); let drop_in_place_fn_def_id = tcx.lang_items().drop_in_place_fn(); @@ -445,7 +445,7 @@ fn upstream_monomorphizations_provider( fn upstream_monomorphizations_for_provider( tcx: TyCtxt<'_>, def_id: DefId, -) -> Option<&FxHashMap<GenericArgsRef<'_>, CrateNum>> { +) -> Option<&UnordMap<GenericArgsRef<'_>, CrateNum>> { debug_assert!(!def_id.is_local()); tcx.upstream_monomorphizations(()).get(&def_id) } @@ -656,7 +656,7 @@ fn maybe_emutls_symbol_name<'tcx>( } } -fn wasm_import_module_map(tcx: TyCtxt<'_>, cnum: CrateNum) -> FxHashMap<DefId, String> { +fn wasm_import_module_map(tcx: TyCtxt<'_>, cnum: CrateNum) -> DefIdMap<String> { // Build up a map from DefId to a `NativeLib` structure, where // `NativeLib` internally contains information about // `#[link(wasm_import_module = "...")]` for example. @@ -665,9 +665,9 @@ fn wasm_import_module_map(tcx: TyCtxt<'_>, cnum: CrateNum) -> FxHashMap<DefId, S let def_id_to_native_lib = native_libs .iter() .filter_map(|lib| lib.foreign_module.map(|id| (id, lib))) - .collect::<FxHashMap<_, _>>(); + .collect::<DefIdMap<_>>(); - let mut ret = FxHashMap::default(); + let mut ret = DefIdMap::default(); for (def_id, lib) in tcx.foreign_modules(cnum).iter() { let module = def_id_to_native_lib.get(def_id).and_then(|s| s.wasm_import_module()); let Some(module) = module else { continue }; diff --git a/compiler/rustc_codegen_ssa/src/target_features.rs b/compiler/rustc_codegen_ssa/src/target_features.rs index 031fcc0adb1..b6bb1607a09 100644 --- a/compiler/rustc_codegen_ssa/src/target_features.rs +++ b/compiler/rustc_codegen_ssa/src/target_features.rs @@ -1,8 +1,8 @@ use crate::errors; use rustc_ast::ast; use rustc_attr::InstructionSetAttr; -use rustc_data_structures::fx::FxHashMap; use rustc_data_structures::fx::FxIndexSet; +use rustc_data_structures::unord::UnordMap; use rustc_errors::Applicability; use rustc_hir::def::DefKind; use rustc_hir::def_id::DefId; @@ -18,7 +18,7 @@ use rustc_span::Span; pub fn from_target_feature( tcx: TyCtxt<'_>, attr: &ast::Attribute, - supported_target_features: &FxHashMap<String, Option<Symbol>>, + supported_target_features: &UnordMap<String, Option<Symbol>>, target_features: &mut Vec<Symbol>, ) { let Some(list) = attr.meta_item_list() else { return }; diff --git a/compiler/rustc_data_structures/src/stable_hasher.rs b/compiler/rustc_data_structures/src/stable_hasher.rs index 6d75b0fb8a0..afe26f80de8 100644 --- a/compiler/rustc_data_structures/src/stable_hasher.rs +++ b/compiler/rustc_data_structures/src/stable_hasher.rs @@ -245,6 +245,32 @@ unsafe impl<T: StableOrd> StableOrd for &T { const CAN_USE_UNSTABLE_SORT: bool = T::CAN_USE_UNSTABLE_SORT; } +/// This is a companion trait to `StableOrd`. Some types like `Symbol` can be +/// compared in a cross-session stable way, but their `Ord` implementation is +/// not stable. In such cases, a `StableOrd` implementation can be provided +/// to offer a lightweight way for stable sorting. (The more heavyweight option +/// is to sort via `ToStableHashKey`, but then sorting needs to have access to +/// a stable hashing context and `ToStableHashKey` can also be expensive as in +/// the case of `Symbol` where it has to allocate a `String`.) +/// +/// See the documentation of [StableOrd] for how stable sort order is defined. +/// The same definition applies here. Be careful when implementing this trait. +pub trait StableCompare { + const CAN_USE_UNSTABLE_SORT: bool; + + fn stable_cmp(&self, other: &Self) -> std::cmp::Ordering; +} + +/// `StableOrd` denotes that the type's `Ord` implementation is stable, so +/// we can implement `StableCompare` by just delegating to `Ord`. +impl<T: StableOrd> StableCompare for T { + const CAN_USE_UNSTABLE_SORT: bool = T::CAN_USE_UNSTABLE_SORT; + + fn stable_cmp(&self, other: &Self) -> std::cmp::Ordering { + self.cmp(other) + } +} + /// Implement HashStable by just calling `Hash::hash()`. Also implement `StableOrd` for the type since /// that has the same requirements. /// diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs index 47c56eba7ad..bd4dff6f62f 100644 --- a/compiler/rustc_data_structures/src/unord.rs +++ b/compiler/rustc_data_structures/src/unord.rs @@ -3,9 +3,8 @@ //! as required by the query system. use rustc_hash::{FxHashMap, FxHashSet}; -use smallvec::SmallVec; use std::{ - borrow::Borrow, + borrow::{Borrow, BorrowMut}, collections::hash_map::Entry, hash::Hash, iter::{Product, Sum}, @@ -14,7 +13,7 @@ use std::{ use crate::{ fingerprint::Fingerprint, - stable_hasher::{HashStable, StableHasher, StableOrd, ToStableHashKey}, + stable_hasher::{HashStable, StableCompare, StableHasher, ToStableHashKey}, }; /// `UnordItems` is the order-less version of `Iterator`. It only contains methods @@ -134,36 +133,78 @@ impl<'a, T: Copy + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> { } } -impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> { +impl<T, I: Iterator<Item = T>> UnordItems<T, I> { + #[inline] pub fn into_sorted<HCX>(self, hcx: &HCX) -> Vec<T> where T: ToStableHashKey<HCX>, { - let mut items: Vec<T> = self.0.collect(); - items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx)); - items + self.collect_sorted(hcx, true) } #[inline] pub fn into_sorted_stable_ord(self) -> Vec<T> where - T: Ord + StableOrd, + T: StableCompare, + { + self.collect_stable_ord_by_key(|x| x) + } + + #[inline] + pub fn into_sorted_stable_ord_by_key<K, C>(self, project_to_key: C) -> Vec<T> + where + K: StableCompare, + C: for<'a> Fn(&'a T) -> &'a K, { - let mut items: Vec<T> = self.0.collect(); - if !T::CAN_USE_UNSTABLE_SORT { - items.sort(); - } else { - items.sort_unstable() + self.collect_stable_ord_by_key(project_to_key) + } + + #[inline] + pub fn collect_sorted<HCX, C>(self, hcx: &HCX, cache_sort_key: bool) -> C + where + T: ToStableHashKey<HCX>, + C: FromIterator<T> + BorrowMut<[T]>, + { + let mut items: C = self.0.collect(); + + let slice = items.borrow_mut(); + if slice.len() > 1 { + if cache_sort_key { + slice.sort_by_cached_key(|x| x.to_stable_hash_key(hcx)); + } else { + slice.sort_by_key(|x| x.to_stable_hash_key(hcx)); + } } + items } - pub fn into_sorted_small_vec<HCX, const LEN: usize>(self, hcx: &HCX) -> SmallVec<[T; LEN]> + #[inline] + pub fn collect_stable_ord_by_key<K, C, P>(self, project_to_key: P) -> C where - T: ToStableHashKey<HCX>, + K: StableCompare, + P: for<'a> Fn(&'a T) -> &'a K, + C: FromIterator<T> + BorrowMut<[T]>, { - let mut items: SmallVec<[T; LEN]> = self.0.collect(); - items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx)); + let mut items: C = self.0.collect(); + + let slice = items.borrow_mut(); + if slice.len() > 1 { + if !K::CAN_USE_UNSTABLE_SORT { + slice.sort_by(|a, b| { + let a_key = project_to_key(a); + let b_key = project_to_key(b); + a_key.stable_cmp(b_key) + }); + } else { + slice.sort_unstable_by(|a, b| { + let a_key = project_to_key(a); + let b_key = project_to_key(b); + a_key.stable_cmp(b_key) + }); + } + } + items } } @@ -268,16 +309,30 @@ impl<V: Eq + Hash> UnordSet<V> { } /// Returns the items of this set in stable sort order (as defined by - /// `StableOrd`). This method is much more efficient than + /// `StableCompare`). This method is much more efficient than /// `into_sorted` because it does not need to transform keys to their /// `ToStableHashKey` equivalent. #[inline] - pub fn to_sorted_stable_ord(&self) -> Vec<V> + pub fn to_sorted_stable_ord(&self) -> Vec<&V> where - V: Ord + StableOrd + Clone, + V: StableCompare, { - let mut items: Vec<V> = self.inner.iter().cloned().collect(); - items.sort_unstable(); + let mut items: Vec<&V> = self.inner.iter().collect(); + items.sort_unstable_by(|a, b| a.stable_cmp(*b)); + items + } + + /// Returns the items of this set in stable sort order (as defined by + /// `StableCompare`). This method is much more efficient than + /// `into_sorted` because it does not need to transform keys to their + /// `ToStableHashKey` equivalent. + #[inline] + pub fn into_sorted_stable_ord(self) -> Vec<V> + where + V: StableCompare, + { + let mut items: Vec<V> = self.inner.into_iter().collect(); + items.sort_unstable_by(V::stable_cmp); items } @@ -483,16 +538,16 @@ impl<K: Eq + Hash, V> UnordMap<K, V> { to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&(k, _)| k) } - /// Returns the entries of this map in stable sort order (as defined by `StableOrd`). + /// Returns the entries of this map in stable sort order (as defined by `StableCompare`). /// This method can be much more efficient than `into_sorted` because it does not need /// to transform keys to their `ToStableHashKey` equivalent. #[inline] - pub fn to_sorted_stable_ord(&self) -> Vec<(K, &V)> + pub fn to_sorted_stable_ord(&self) -> Vec<(&K, &V)> where - K: Ord + StableOrd + Copy, + K: StableCompare, { - let mut items: Vec<(K, &V)> = self.inner.iter().map(|(&k, v)| (k, v)).collect(); - items.sort_unstable_by_key(|&(k, _)| k); + let mut items: Vec<_> = self.inner.iter().collect(); + items.sort_unstable_by(|(a, _), (b, _)| a.stable_cmp(*b)); items } @@ -510,6 +565,19 @@ impl<K: Eq + Hash, V> UnordMap<K, V> { to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |(k, _)| k) } + /// Returns the entries of this map in stable sort order (as defined by `StableCompare`). + /// This method can be much more efficient than `into_sorted` because it does not need + /// to transform keys to their `ToStableHashKey` equivalent. + #[inline] + pub fn into_sorted_stable_ord(self) -> Vec<(K, V)> + where + K: StableCompare, + { + let mut items: Vec<(K, V)> = self.inner.into_iter().collect(); + items.sort_unstable_by(|a, b| a.0.stable_cmp(&b.0)); + items + } + /// Returns the values of this map in stable sort order (as defined by K's /// `ToStableHashKey` implementation). /// diff --git a/compiler/rustc_hir_analysis/src/astconv/errors.rs b/compiler/rustc_hir_analysis/src/astconv/errors.rs index d22c4fe201d..5e1c29440a5 100644 --- a/compiler/rustc_hir_analysis/src/astconv/errors.rs +++ b/compiler/rustc_hir_analysis/src/astconv/errors.rs @@ -6,6 +6,7 @@ use crate::errors::{ use crate::fluent_generated as fluent; use crate::traits::error_reporting::report_object_safety_error; use rustc_data_structures::fx::{FxHashMap, FxIndexMap, FxIndexSet}; +use rustc_data_structures::unord::UnordMap; use rustc_errors::{pluralize, struct_span_err, Applicability, Diagnostic, ErrorGuaranteed}; use rustc_hir as hir; use rustc_hir::def_id::{DefId, LocalDefId}; @@ -673,7 +674,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o { })) }) .flatten() - .collect::<FxHashMap<Symbol, &ty::AssocItem>>(); + .collect::<UnordMap<Symbol, &ty::AssocItem>>(); let mut names = names .into_iter() @@ -709,7 +710,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o { let mut where_constraints = vec![]; let mut already_has_generics_args_suggestion = false; for (span, assoc_items) in &associated_types { - let mut names: FxHashMap<_, usize> = FxHashMap::default(); + let mut names: UnordMap<_, usize> = Default::default(); for item in assoc_items { types_count += 1; *names.entry(item.name).or_insert(0) += 1; diff --git a/compiler/rustc_hir_analysis/src/check/compare_impl_item.rs b/compiler/rustc_hir_analysis/src/check/compare_impl_item.rs index dbcaa244f29..cc4dc5aca0d 100644 --- a/compiler/rustc_hir_analysis/src/check/compare_impl_item.rs +++ b/compiler/rustc_hir_analysis/src/check/compare_impl_item.rs @@ -1,6 +1,6 @@ use super::potentially_plural_count; use crate::errors::LifetimesOrBoundsMismatchOnTrait; -use hir::def_id::{DefId, LocalDefId}; +use hir::def_id::{DefId, DefIdMap, LocalDefId}; use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexSet}; use rustc_errors::{pluralize, struct_span_err, Applicability, DiagnosticId, ErrorGuaranteed}; use rustc_hir as hir; @@ -478,7 +478,7 @@ fn compare_asyncness<'tcx>( pub(super) fn collect_return_position_impl_trait_in_trait_tys<'tcx>( tcx: TyCtxt<'tcx>, impl_m_def_id: LocalDefId, -) -> Result<&'tcx FxHashMap<DefId, ty::EarlyBinder<Ty<'tcx>>>, ErrorGuaranteed> { +) -> Result<&'tcx DefIdMap<ty::EarlyBinder<Ty<'tcx>>>, ErrorGuaranteed> { let impl_m = tcx.opt_associated_item(impl_m_def_id.to_def_id()).unwrap(); let trait_m = tcx.opt_associated_item(impl_m.trait_item_def_id.unwrap()).unwrap(); let impl_trait_ref = @@ -706,7 +706,7 @@ pub(super) fn collect_return_position_impl_trait_in_trait_tys<'tcx>( ); ocx.resolve_regions_and_report_errors(impl_m_def_id, &outlives_env)?; - let mut remapped_types = FxHashMap::default(); + let mut remapped_types = DefIdMap::default(); for (def_id, (ty, args)) in collected_types { match infcx.fully_resolve((ty, args)) { Ok((ty, args)) => { diff --git a/compiler/rustc_hir_analysis/src/collect.rs b/compiler/rustc_hir_analysis/src/collect.rs index 8aeab2ca67e..0a13949a688 100644 --- a/compiler/rustc_hir_analysis/src/collect.rs +++ b/compiler/rustc_hir_analysis/src/collect.rs @@ -16,6 +16,7 @@ use rustc_data_structures::captures::Captures; use rustc_data_structures::fx::{FxHashMap, FxHashSet}; +use rustc_data_structures::unord::UnordMap; use rustc_errors::{Applicability, DiagnosticBuilder, ErrorGuaranteed, StashKey}; use rustc_hir as hir; use rustc_hir::def::DefKind; @@ -979,7 +980,7 @@ fn trait_def(tcx: TyCtxt<'_>, def_id: LocalDefId) -> ty::TraitDef { }) // Check for duplicates .and_then(|list| { - let mut set: FxHashMap<Symbol, Span> = FxHashMap::default(); + let mut set: UnordMap<Symbol, Span> = Default::default(); let mut no_dups = true; for ident in &*list { diff --git a/compiler/rustc_hir_typeck/src/method/suggest.rs b/compiler/rustc_hir_typeck/src/method/suggest.rs index 560537b468b..58db2f10bd0 100644 --- a/compiler/rustc_hir_typeck/src/method/suggest.rs +++ b/compiler/rustc_hir_typeck/src/method/suggest.rs @@ -913,7 +913,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> { for ((span, add_where_or_comma), obligations) in type_params.into_iter() { restrict_type_params = true; // #74886: Sort here so that the output is always the same. - let obligations = obligations.to_sorted_stable_ord(); + let obligations = obligations.into_sorted_stable_ord(); err.span_suggestion_verbose( span, format!( diff --git a/compiler/rustc_hir_typeck/src/upvar.rs b/compiler/rustc_hir_typeck/src/upvar.rs index 47b9d5f6503..f6b05e1b35a 100644 --- a/compiler/rustc_hir_typeck/src/upvar.rs +++ b/compiler/rustc_hir_typeck/src/upvar.rs @@ -912,7 +912,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> { drop_order: bool, ) -> MigrationWarningReason { MigrationWarningReason { - auto_traits: auto_trait_reasons.to_sorted_stable_ord(), + auto_traits: auto_trait_reasons.into_sorted_stable_ord(), drop_order, } } diff --git a/compiler/rustc_hir_typeck/src/writeback.rs b/compiler/rustc_hir_typeck/src/writeback.rs index 719d85ed3db..c56a028321a 100644 --- a/compiler/rustc_hir_typeck/src/writeback.rs +++ b/compiler/rustc_hir_typeck/src/writeback.rs @@ -473,7 +473,7 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> { assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner); let fcx_coercion_casts = fcx_typeck_results.coercion_casts().to_sorted_stable_ord(); - for local_id in fcx_coercion_casts { + for &local_id in fcx_coercion_casts { self.typeck_results.set_coercion_cast(local_id); } } diff --git a/compiler/rustc_incremental/src/persist/save.rs b/compiler/rustc_incremental/src/persist/save.rs index bdc935a5e3b..08b7d08bcc0 100644 --- a/compiler/rustc_incremental/src/persist/save.rs +++ b/compiler/rustc_incremental/src/persist/save.rs @@ -103,7 +103,7 @@ pub fn save_work_product_index( // deleted during invalidation. Some object files don't change their // content, they are just not needed anymore. let previous_work_products = dep_graph.previous_work_products(); - for (id, wp) in previous_work_products.to_sorted_stable_ord().iter() { + for (id, wp) in previous_work_products.to_sorted_stable_ord() { if !new_work_products.contains_key(id) { work_product::delete_workproduct_files(sess, wp); debug_assert!( diff --git a/compiler/rustc_lint/src/foreign_modules.rs b/compiler/rustc_lint/src/foreign_modules.rs index 31d9c0d33fe..ecb7a157f39 100644 --- a/compiler/rustc_lint/src/foreign_modules.rs +++ b/compiler/rustc_lint/src/foreign_modules.rs @@ -1,5 +1,5 @@ -use rustc_data_structures::fx::{FxHashMap, FxHashSet}; use rustc_data_structures::stack::ensure_sufficient_stack; +use rustc_data_structures::unord::{UnordMap, UnordSet}; use rustc_hir as hir; use rustc_hir::def::DefKind; use rustc_middle::query::Providers; @@ -72,7 +72,7 @@ struct ClashingExternDeclarations { /// the symbol should be reported as a clashing declaration. // FIXME: Technically, we could just store a &'tcx str here without issue; however, the // `impl_lint_pass` macro doesn't currently support lints parametric over a lifetime. - seen_decls: FxHashMap<Symbol, hir::OwnerId>, + seen_decls: UnordMap<Symbol, hir::OwnerId>, } /// Differentiate between whether the name for an extern decl came from the link_name attribute or @@ -96,7 +96,7 @@ impl SymbolName { impl ClashingExternDeclarations { pub(crate) fn new() -> Self { - ClashingExternDeclarations { seen_decls: FxHashMap::default() } + ClashingExternDeclarations { seen_decls: Default::default() } } /// Insert a new foreign item into the seen set. If a symbol with the same name already exists @@ -209,12 +209,12 @@ fn structurally_same_type<'tcx>( b: Ty<'tcx>, ckind: types::CItemKind, ) -> bool { - let mut seen_types = FxHashSet::default(); + let mut seen_types = UnordSet::default(); structurally_same_type_impl(&mut seen_types, tcx, param_env, a, b, ckind) } fn structurally_same_type_impl<'tcx>( - seen_types: &mut FxHashSet<(Ty<'tcx>, Ty<'tcx>)>, + seen_types: &mut UnordSet<(Ty<'tcx>, Ty<'tcx>)>, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>, a: Ty<'tcx>, diff --git a/compiler/rustc_lint/src/non_ascii_idents.rs b/compiler/rustc_lint/src/non_ascii_idents.rs index 08b2bf6af37..3405dd3a916 100644 --- a/compiler/rustc_lint/src/non_ascii_idents.rs +++ b/compiler/rustc_lint/src/non_ascii_idents.rs @@ -4,7 +4,8 @@ use crate::lints::{ }; use crate::{EarlyContext, EarlyLintPass, LintContext}; use rustc_ast as ast; -use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::fx::FxIndexMap; +use rustc_data_structures::unord::UnordMap; use rustc_span::symbol::Symbol; declare_lint! { @@ -194,8 +195,8 @@ impl EarlyLintPass for NonAsciiIdents { } if has_non_ascii_idents && check_confusable_idents { - let mut skeleton_map: FxHashMap<Symbol, (Symbol, Span, bool)> = - FxHashMap::with_capacity_and_hasher(symbols.len(), Default::default()); + let mut skeleton_map: UnordMap<Symbol, (Symbol, Span, bool)> = + UnordMap::with_capacity(symbols.len()); let mut skeleton_buf = String::new(); for (&symbol, &sp) in symbols.iter() { @@ -248,8 +249,8 @@ impl EarlyLintPass for NonAsciiIdents { Verified, } - let mut script_states: FxHashMap<AugmentedScriptSet, ScriptSetUsage> = - FxHashMap::default(); + let mut script_states: FxIndexMap<AugmentedScriptSet, ScriptSetUsage> = + Default::default(); let latin_augmented_script_set = AugmentedScriptSet::for_char('A'); script_states.insert(latin_augmented_script_set, ScriptSetUsage::Verified); diff --git a/compiler/rustc_lint_defs/src/lib.rs b/compiler/rustc_lint_defs/src/lib.rs index a25cfe68e0d..eed35326c45 100644 --- a/compiler/rustc_lint_defs/src/lib.rs +++ b/compiler/rustc_lint_defs/src/lib.rs @@ -9,7 +9,9 @@ pub use self::Level::*; use rustc_ast::node_id::NodeId; use rustc_ast::{AttrId, Attribute}; use rustc_data_structures::fx::{FxIndexMap, FxIndexSet}; -use rustc_data_structures::stable_hasher::{HashStable, StableHasher, ToStableHashKey}; +use rustc_data_structures::stable_hasher::{ + HashStable, StableCompare, StableHasher, ToStableHashKey, +}; use rustc_error_messages::{DiagnosticMessage, MultiSpan}; use rustc_hir::HashStableContext; use rustc_hir::HirId; @@ -541,6 +543,14 @@ impl<HCX> ToStableHashKey<HCX> for LintId { } } +impl StableCompare for LintId { + const CAN_USE_UNSTABLE_SORT: bool = true; + + fn stable_cmp(&self, other: &Self) -> std::cmp::Ordering { + self.lint_name_raw().cmp(&other.lint_name_raw()) + } +} + #[derive(Debug)] pub struct AmbiguityErrorDiag { pub msg: String, diff --git a/compiler/rustc_metadata/src/rmeta/encoder.rs b/compiler/rustc_metadata/src/rmeta/encoder.rs index 5b296c098bc..1d12b853b53 100644 --- a/compiler/rustc_metadata/src/rmeta/encoder.rs +++ b/compiler/rustc_metadata/src/rmeta/encoder.rs @@ -2,10 +2,8 @@ use crate::errors::{FailCreateFileEncoder, FailWriteFile}; use crate::rmeta::*; use rustc_ast::Attribute; -use rustc_data_structures::fingerprint::Fingerprint; use rustc_data_structures::fx::FxIndexSet; use rustc_data_structures::memmap::{Mmap, MmapMut}; -use rustc_data_structures::stable_hasher::{HashStable, StableHasher}; use rustc_data_structures::sync::{join, par_for_each_in, Lrc}; use rustc_data_structures::temp_dir::MaybeTempDir; use rustc_hir as hir; @@ -1914,14 +1912,15 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> { empty_proc_macro!(self); let tcx = self.tcx; let lib_features = tcx.lib_features(LOCAL_CRATE); - self.lazy_array(lib_features.to_vec()) + self.lazy_array(lib_features.to_sorted_vec()) } fn encode_stability_implications(&mut self) -> LazyArray<(Symbol, Symbol)> { empty_proc_macro!(self); let tcx = self.tcx; let implications = tcx.stability_implications(LOCAL_CRATE); - self.lazy_array(implications.iter().map(|(k, v)| (*k, *v))) + let sorted = implications.to_sorted_stable_ord(); + self.lazy_array(sorted.into_iter().map(|(k, v)| (*k, *v))) } fn encode_diagnostic_items(&mut self) -> LazyArray<(Symbol, DefIndex)> { @@ -2033,14 +2032,10 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> { fn encode_incoherent_impls(&mut self) -> LazyArray<IncoherentImpls> { empty_proc_macro!(self); let tcx = self.tcx; - let mut all_impls: Vec<_> = tcx.crate_inherent_impls(()).incoherent_impls.iter().collect(); - tcx.with_stable_hashing_context(|mut ctx| { - all_impls.sort_by_cached_key(|&(&simp, _)| { - let mut hasher = StableHasher::new(); - simp.hash_stable(&mut ctx, &mut hasher); - hasher.finish::<Fingerprint>() - }) + let all_impls = tcx.with_stable_hashing_context(|hcx| { + tcx.crate_inherent_impls(()).incoherent_impls.to_sorted(&hcx, true) }); + let all_impls: Vec<_> = all_impls .into_iter() .map(|(&simp, impls)| { diff --git a/compiler/rustc_metadata/src/rmeta/mod.rs b/compiler/rustc_metadata/src/rmeta/mod.rs index 54ee50c2358..2f775882693 100644 --- a/compiler/rustc_metadata/src/rmeta/mod.rs +++ b/compiler/rustc_metadata/src/rmeta/mod.rs @@ -12,7 +12,7 @@ use rustc_attr as attr; use rustc_data_structures::svh::Svh; use rustc_hir as hir; use rustc_hir::def::{CtorKind, DefKind, DocLinkResMap}; -use rustc_hir::def_id::{CrateNum, DefId, DefIndex, DefPathHash, StableCrateId}; +use rustc_hir::def_id::{CrateNum, DefId, DefIdMap, DefIndex, DefPathHash, StableCrateId}; use rustc_hir::definitions::DefKey; use rustc_hir::lang_items::LangItem; use rustc_index::bit_set::BitSet; @@ -459,7 +459,7 @@ define_tables! { macro_definition: Table<DefIndex, LazyValue<ast::DelimArgs>>, proc_macro: Table<DefIndex, MacroKind>, deduced_param_attrs: Table<DefIndex, LazyArray<DeducedParamAttrs>>, - trait_impl_trait_tys: Table<DefIndex, LazyValue<FxHashMap<DefId, ty::EarlyBinder<Ty<'static>>>>>, + trait_impl_trait_tys: Table<DefIndex, LazyValue<DefIdMap<ty::EarlyBinder<Ty<'static>>>>>, doc_link_resolutions: Table<DefIndex, LazyValue<DocLinkResMap>>, doc_link_traits_in_scope: Table<DefIndex, LazyArray<DefId>>, assumed_wf_types_for_rpitit: Table<DefIndex, LazyArray<(Ty<'static>, Span)>>, diff --git a/compiler/rustc_middle/src/arena.rs b/compiler/rustc_middle/src/arena.rs index 52fd494a10d..0ab09dadf58 100644 --- a/compiler/rustc_middle/src/arena.rs +++ b/compiler/rustc_middle/src/arena.rs @@ -103,7 +103,7 @@ macro_rules! arena_types { [] dep_kind: rustc_middle::dep_graph::DepKindStruct<'tcx>, [decode] trait_impl_trait_tys: - rustc_data_structures::fx::FxHashMap< + rustc_data_structures::unord::UnordMap< rustc_hir::def_id::DefId, rustc_middle::ty::EarlyBinder<rustc_middle::ty::Ty<'tcx>> >, diff --git a/compiler/rustc_middle/src/middle/mod.rs b/compiler/rustc_middle/src/middle/mod.rs index 8c1b1ff12e9..bdb2270611a 100644 --- a/compiler/rustc_middle/src/middle/mod.rs +++ b/compiler/rustc_middle/src/middle/mod.rs @@ -4,7 +4,7 @@ pub mod dependency_format; pub mod exported_symbols; pub mod lang_items; pub mod lib_features { - use rustc_data_structures::fx::FxHashMap; + use rustc_data_structures::unord::UnordMap; use rustc_span::{symbol::Symbol, Span}; #[derive(Copy, Clone, Debug, PartialEq, Eq)] @@ -16,15 +16,16 @@ pub mod lib_features { #[derive(HashStable, Debug, Default)] pub struct LibFeatures { - pub stability: FxHashMap<Symbol, (FeatureStability, Span)>, + pub stability: UnordMap<Symbol, (FeatureStability, Span)>, } impl LibFeatures { - pub fn to_vec(&self) -> Vec<(Symbol, FeatureStability)> { - let mut all_features: Vec<_> = - self.stability.iter().map(|(&sym, &(stab, _))| (sym, stab)).collect(); - all_features.sort_unstable_by(|(a, _), (b, _)| a.as_str().cmp(b.as_str())); - all_features + pub fn to_sorted_vec(&self) -> Vec<(Symbol, FeatureStability)> { + self.stability + .to_sorted_stable_ord() + .iter() + .map(|(&sym, &(stab, _))| (sym, stab)) + .collect() } } } diff --git a/compiler/rustc_middle/src/middle/region.rs b/compiler/rustc_middle/src/middle/region.rs index b4dd8f6f4a7..5d6a7f75df8 100644 --- a/compiler/rustc_middle/src/middle/region.rs +++ b/compiler/rustc_middle/src/middle/region.rs @@ -7,12 +7,11 @@ //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/borrow_check.html use crate::ty::TyCtxt; -use rustc_data_structures::fx::{FxHashMap, FxIndexMap}; -use rustc_data_structures::stable_hasher::{HashStable, StableHasher}; +use rustc_data_structures::fx::FxIndexMap; +use rustc_data_structures::unord::UnordMap; use rustc_hir as hir; use rustc_hir::{HirIdMap, Node}; use rustc_macros::HashStable; -use rustc_query_system::ich::StableHashingContext; use rustc_span::{Span, DUMMY_SP}; use std::fmt; @@ -205,7 +204,7 @@ impl Scope { pub type ScopeDepth = u32; /// The region scope tree encodes information about region relationships. -#[derive(Default, Debug)] +#[derive(Default, Debug, HashStable)] pub struct ScopeTree { /// If not empty, this body is the root of this region hierarchy. pub root_body: Option<hir::HirId>, @@ -306,7 +305,7 @@ pub struct ScopeTree { /// The reason is that semantically, until the `box` expression returns, /// the values are still owned by their containing expressions. So /// we'll see that `&x`. - pub yield_in_scope: FxHashMap<Scope, Vec<YieldData>>, + pub yield_in_scope: UnordMap<Scope, Vec<YieldData>>, } /// Identifies the reason that a given expression is an rvalue candidate @@ -404,23 +403,3 @@ impl ScopeTree { self.yield_in_scope.get(&scope).map(Deref::deref) } } - -impl<'a> HashStable<StableHashingContext<'a>> for ScopeTree { - fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) { - let ScopeTree { - root_body, - ref parent_map, - ref var_map, - ref destruction_scopes, - ref rvalue_candidates, - ref yield_in_scope, - } = *self; - - root_body.hash_stable(hcx, hasher); - parent_map.hash_stable(hcx, hasher); - var_map.hash_stable(hcx, hasher); - destruction_scopes.hash_stable(hcx, hasher); - rvalue_candidates.hash_stable(hcx, hasher); - yield_in_scope.hash_stable(hcx, hasher); - } -} diff --git a/compiler/rustc_middle/src/middle/resolve_bound_vars.rs b/compiler/rustc_middle/src/middle/resolve_bound_vars.rs index c59704fc023..610afd95f3c 100644 --- a/compiler/rustc_middle/src/middle/resolve_bound_vars.rs +++ b/compiler/rustc_middle/src/middle/resolve_bound_vars.rs @@ -2,7 +2,7 @@ use crate::ty; -use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::fx::FxIndexMap; use rustc_errors::ErrorGuaranteed; use rustc_hir::def_id::DefId; use rustc_hir::{ItemLocalId, OwnerId}; @@ -51,7 +51,7 @@ pub enum ObjectLifetimeDefault { pub struct ResolveBoundVars { /// Maps from every use of a named (not anonymous) lifetime to a /// `Region` describing how that region is bound - pub defs: FxHashMap<OwnerId, FxHashMap<ItemLocalId, ResolvedArg>>, + pub defs: FxIndexMap<OwnerId, FxIndexMap<ItemLocalId, ResolvedArg>>, - pub late_bound_vars: FxHashMap<OwnerId, FxHashMap<ItemLocalId, Vec<ty::BoundVariableKind>>>, + pub late_bound_vars: FxIndexMap<OwnerId, FxIndexMap<ItemLocalId, Vec<ty::BoundVariableKind>>>, } diff --git a/compiler/rustc_middle/src/middle/stability.rs b/compiler/rustc_middle/src/middle/stability.rs index b2d1124b2ed..90b479cf2f4 100644 --- a/compiler/rustc_middle/src/middle/stability.rs +++ b/compiler/rustc_middle/src/middle/stability.rs @@ -8,11 +8,11 @@ use rustc_ast::NodeId; use rustc_attr::{ self as attr, ConstStability, DefaultBodyStability, DeprecatedSince, Deprecation, Stability, }; -use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::unord::UnordMap; use rustc_errors::{Applicability, Diagnostic}; use rustc_feature::GateIssue; use rustc_hir::def::DefKind; -use rustc_hir::def_id::{DefId, LocalDefId}; +use rustc_hir::def_id::{DefId, LocalDefId, LocalDefIdMap}; use rustc_hir::{self as hir, HirId}; use rustc_middle::ty::print::with_no_trimmed_paths; use rustc_session::lint::builtin::{DEPRECATED, DEPRECATED_IN_FUTURE, SOFT_UNSTABLE}; @@ -61,10 +61,10 @@ impl DeprecationEntry { pub struct Index { /// This is mostly a cache, except the stabilities of local items /// are filled by the annotator. - pub stab_map: FxHashMap<LocalDefId, Stability>, - pub const_stab_map: FxHashMap<LocalDefId, ConstStability>, - pub default_body_stab_map: FxHashMap<LocalDefId, DefaultBodyStability>, - pub depr_map: FxHashMap<LocalDefId, DeprecationEntry>, + pub stab_map: LocalDefIdMap<Stability>, + pub const_stab_map: LocalDefIdMap<ConstStability>, + pub default_body_stab_map: LocalDefIdMap<DefaultBodyStability>, + pub depr_map: LocalDefIdMap<DeprecationEntry>, /// Mapping from feature name to feature name based on the `implied_by` field of `#[unstable]` /// attributes. If a `#[unstable(feature = "implier", implied_by = "impliee")]` attribute /// exists, then this map will have a `impliee -> implier` entry. @@ -77,7 +77,7 @@ pub struct Index { /// to know that the feature implies another feature. If it were reversed, and the `#[stable]` /// attribute had an `implies` meta item, then a map would be necessary when avoiding a "use of /// unstable feature" error for a feature that was implied. - pub implications: FxHashMap<Symbol, Symbol>, + pub implications: UnordMap<Symbol, Symbol>, } impl Index { diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs index bf5e59ba78d..7d5abaceb20 100644 --- a/compiler/rustc_middle/src/query/mod.rs +++ b/compiler/rustc_middle/src/query/mod.rs @@ -57,11 +57,11 @@ use rustc_ast as ast; use rustc_ast::expand::{allocator::AllocatorKind, StrippedCfgItem}; use rustc_attr as attr; use rustc_data_structures::fingerprint::Fingerprint; -use rustc_data_structures::fx::{FxHashMap, FxIndexMap, FxIndexSet}; +use rustc_data_structures::fx::{FxIndexMap, FxIndexSet}; use rustc_data_structures::steal::Steal; use rustc_data_structures::svh::Svh; use rustc_data_structures::sync::Lrc; -use rustc_data_structures::unord::UnordSet; +use rustc_data_structures::unord::{UnordMap, UnordSet}; use rustc_errors::ErrorGuaranteed; use rustc_hir as hir; use rustc_hir::def::{DefKind, DocLinkResMap}; @@ -264,7 +264,7 @@ rustc_queries! { } query collect_return_position_impl_trait_in_trait_tys(key: DefId) - -> Result<&'tcx FxHashMap<DefId, ty::EarlyBinder<Ty<'tcx>>>, ErrorGuaranteed> + -> Result<&'tcx DefIdMap<ty::EarlyBinder<Ty<'tcx>>>, ErrorGuaranteed> { desc { "comparing an impl and trait method signature, inferring any hidden `impl Trait` types in the process" } cache_on_disk_if { key.is_local() } @@ -611,7 +611,7 @@ rustc_queries! { desc { "erasing regions from `{}`", ty } } - query wasm_import_module_map(_: CrateNum) -> &'tcx FxHashMap<DefId, String> { + query wasm_import_module_map(_: CrateNum) -> &'tcx DefIdMap<String> { arena_cache desc { "getting wasm import module map" } } @@ -1537,7 +1537,7 @@ rustc_queries! { /// added or removed in any upstream crate. Instead use the narrower /// `upstream_monomorphizations_for`, `upstream_drop_glue_for`, or, even /// better, `Instance::upstream_monomorphization()`. - query upstream_monomorphizations(_: ()) -> &'tcx DefIdMap<FxHashMap<GenericArgsRef<'tcx>, CrateNum>> { + query upstream_monomorphizations(_: ()) -> &'tcx DefIdMap<UnordMap<GenericArgsRef<'tcx>, CrateNum>> { arena_cache desc { "collecting available upstream monomorphizations" } } @@ -1550,7 +1550,7 @@ rustc_queries! { /// You likely want to call `Instance::upstream_monomorphization()` /// instead of invoking this query directly. query upstream_monomorphizations_for(def_id: DefId) - -> Option<&'tcx FxHashMap<GenericArgsRef<'tcx>, CrateNum>> + -> Option<&'tcx UnordMap<GenericArgsRef<'tcx>, CrateNum>> { desc { |tcx| "collecting available upstream monomorphizations for `{}`", @@ -1662,7 +1662,7 @@ rustc_queries! { desc { "resolving lifetimes" } } query named_variable_map(_: hir::OwnerId) -> - Option<&'tcx FxHashMap<ItemLocalId, ResolvedArg>> { + Option<&'tcx FxIndexMap<ItemLocalId, ResolvedArg>> { desc { "looking up a named region" } } query is_late_bound_map(_: hir::OwnerId) -> Option<&'tcx FxIndexSet<ItemLocalId>> { @@ -1678,7 +1678,7 @@ rustc_queries! { separate_provide_extern } query late_bound_vars_map(_: hir::OwnerId) - -> Option<&'tcx FxHashMap<ItemLocalId, Vec<ty::BoundVariableKind>>> { + -> Option<&'tcx FxIndexMap<ItemLocalId, Vec<ty::BoundVariableKind>>> { desc { "looking up late bound vars" } } @@ -1734,7 +1734,7 @@ rustc_queries! { separate_provide_extern arena_cache } - query stability_implications(_: CrateNum) -> &'tcx FxHashMap<Symbol, Symbol> { + query stability_implications(_: CrateNum) -> &'tcx UnordMap<Symbol, Symbol> { arena_cache desc { "calculating the implications between `#[unstable]` features defined in a crate" } separate_provide_extern @@ -1786,7 +1786,7 @@ rustc_queries! { } /// Collects the "trimmed", shortest accessible paths to all items for diagnostics. /// See the [provider docs](`rustc_middle::ty::print::trimmed_def_paths`) for more info. - query trimmed_def_paths(_: ()) -> &'tcx FxHashMap<DefId, Symbol> { + query trimmed_def_paths(_: ()) -> &'tcx DefIdMap<Symbol> { arena_cache desc { "calculating trimmed def paths" } } @@ -2077,7 +2077,7 @@ rustc_queries! { desc { "computing autoderef types for `{}`", goal.value.value } } - query supported_target_features(_: CrateNum) -> &'tcx FxHashMap<String, Option<Symbol>> { + query supported_target_features(_: CrateNum) -> &'tcx UnordMap<String, Option<Symbol>> { arena_cache eval_always desc { "looking up supported target features" } diff --git a/compiler/rustc_middle/src/query/on_disk_cache.rs b/compiler/rustc_middle/src/query/on_disk_cache.rs index 0577d22d850..8abf4a9e341 100644 --- a/compiler/rustc_middle/src/query/on_disk_cache.rs +++ b/compiler/rustc_middle/src/query/on_disk_cache.rs @@ -2,7 +2,7 @@ use rustc_data_structures::fx::{FxHashMap, FxIndexSet}; use rustc_data_structures::memmap::Mmap; use rustc_data_structures::sync::{HashMapExt, Lock, Lrc, RwLock}; use rustc_data_structures::unhash::UnhashMap; -use rustc_data_structures::unord::UnordSet; +use rustc_data_structures::unord::{UnordMap, UnordSet}; use rustc_hir::def_id::{CrateNum, DefId, DefIndex, LocalDefId, StableCrateId, LOCAL_CRATE}; use rustc_hir::definitions::DefPathHash; use rustc_index::{Idx, IndexVec}; @@ -764,7 +764,7 @@ impl<'a, 'tcx> Decodable<CacheDecoder<'a, 'tcx>> for &'tcx UnordSet<LocalDefId> } impl<'a, 'tcx> Decodable<CacheDecoder<'a, 'tcx>> - for &'tcx FxHashMap<DefId, ty::EarlyBinder<Ty<'tcx>>> + for &'tcx UnordMap<DefId, ty::EarlyBinder<Ty<'tcx>>> { #[inline] fn decode(d: &mut CacheDecoder<'a, 'tcx>) -> Self { diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs index 757d3337afc..4af82f12471 100644 --- a/compiler/rustc_middle/src/ty/mod.rs +++ b/compiler/rustc_middle/src/ty/mod.rs @@ -38,6 +38,7 @@ use rustc_data_structures::intern::Interned; use rustc_data_structures::stable_hasher::{HashStable, StableHasher}; use rustc_data_structures::steal::Steal; use rustc_data_structures::tagged_ptr::CopyTaggedPtr; +use rustc_data_structures::unord::UnordMap; use rustc_errors::{DiagnosticBuilder, ErrorGuaranteed, StashKey}; use rustc_hir as hir; use rustc_hir::def::{CtorKind, CtorOf, DefKind, DocLinkResMap, LifetimeRes, Res}; @@ -655,7 +656,7 @@ pub struct CratePredicatesMap<'tcx> { /// For each struct with outlive bounds, maps to a vector of the /// predicate of its outlive bounds. If an item has no outlives /// bounds, it will have no entry. - pub predicates: FxHashMap<DefId, &'tcx [(Clause<'tcx>, Span)]>, + pub predicates: DefIdMap<&'tcx [(Clause<'tcx>, Span)]>, } impl<'tcx> Clause<'tcx> { @@ -2658,7 +2659,7 @@ pub fn provide(providers: &mut Providers) { #[derive(Clone, Debug, Default, HashStable)] pub struct CrateInherentImpls { pub inherent_impls: LocalDefIdMap<Vec<DefId>>, - pub incoherent_impls: FxHashMap<SimplifiedType, Vec<LocalDefId>>, + pub incoherent_impls: UnordMap<SimplifiedType, Vec<LocalDefId>>, } #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, HashStable)] diff --git a/compiler/rustc_middle/src/ty/parameterized.rs b/compiler/rustc_middle/src/ty/parameterized.rs index a63a4eff5e1..47f9d9e61ad 100644 --- a/compiler/rustc_middle/src/ty/parameterized.rs +++ b/compiler/rustc_middle/src/ty/parameterized.rs @@ -1,6 +1,7 @@ -use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::unord::UnordMap; use rustc_hir::def_id::DefIndex; use rustc_index::{Idx, IndexVec}; +use std::hash::Hash; use crate::ty; @@ -24,8 +25,8 @@ impl<I: Idx + 'static, T: ParameterizedOverTcx> ParameterizedOverTcx for IndexVe type Value<'tcx> = IndexVec<I, T::Value<'tcx>>; } -impl<I: 'static, T: ParameterizedOverTcx> ParameterizedOverTcx for FxHashMap<I, T> { - type Value<'tcx> = FxHashMap<I, T::Value<'tcx>>; +impl<I: Hash + Eq + 'static, T: ParameterizedOverTcx> ParameterizedOverTcx for UnordMap<I, T> { + type Value<'tcx> = UnordMap<I, T::Value<'tcx>>; } impl<T: ParameterizedOverTcx> ParameterizedOverTcx for ty::Binder<'static, T> { diff --git a/compiler/rustc_middle/src/ty/print/pretty.rs b/compiler/rustc_middle/src/ty/print/pretty.rs index ebbd02e01bf..7f11f59b5ee 100644 --- a/compiler/rustc_middle/src/ty/print/pretty.rs +++ b/compiler/rustc_middle/src/ty/print/pretty.rs @@ -12,7 +12,7 @@ use rustc_apfloat::Float; use rustc_data_structures::fx::{FxHashMap, FxIndexMap}; use rustc_hir as hir; use rustc_hir::def::{self, CtorKind, DefKind, Namespace}; -use rustc_hir::def_id::{DefIdSet, ModDefId, CRATE_DEF_ID, LOCAL_CRATE}; +use rustc_hir::def_id::{DefIdMap, DefIdSet, ModDefId, CRATE_DEF_ID, LOCAL_CRATE}; use rustc_hir::definitions::{DefKey, DefPathDataName}; use rustc_hir::LangItem; use rustc_session::config::TrimmedDefPaths; @@ -3049,8 +3049,8 @@ fn for_each_def(tcx: TyCtxt<'_>, mut collect_fn: impl for<'b> FnMut(&'b Ident, N /// /// See also [`DelayDm`](rustc_error_messages::DelayDm) and [`with_no_trimmed_paths!`]. // this is pub to be able to intra-doc-link it -pub fn trimmed_def_paths(tcx: TyCtxt<'_>, (): ()) -> FxHashMap<DefId, Symbol> { - let mut map: FxHashMap<DefId, Symbol> = FxHashMap::default(); +pub fn trimmed_def_paths(tcx: TyCtxt<'_>, (): ()) -> DefIdMap<Symbol> { + let mut map: DefIdMap<Symbol> = Default::default(); if let TrimmedDefPaths::GoodPath = tcx.sess.opts.trimmed_def_paths { // Trimming paths is expensive and not optimized, since we expect it to only be used for error reporting. diff --git a/compiler/rustc_middle/src/ty/typeck_results.rs b/compiler/rustc_middle/src/ty/typeck_results.rs index 58699c934b6..ad41a674dd8 100644 --- a/compiler/rustc_middle/src/ty/typeck_results.rs +++ b/compiler/rustc_middle/src/ty/typeck_results.rs @@ -527,7 +527,7 @@ impl<'a, V> LocalTableInContext<'a, V> { } pub fn items_in_stable_order(&self) -> Vec<(ItemLocalId, &'a V)> { - self.data.to_sorted_stable_ord() + self.data.items().map(|(&k, v)| (k, v)).into_sorted_stable_ord_by_key(|(k, _)| k) } } diff --git a/compiler/rustc_passes/src/stability.rs b/compiler/rustc_passes/src/stability.rs index 87fdedc15ba..18b9ba0f042 100644 --- a/compiler/rustc_passes/src/stability.rs +++ b/compiler/rustc_passes/src/stability.rs @@ -6,7 +6,8 @@ use rustc_attr::{ self as attr, ConstStability, DeprecatedSince, Stability, StabilityLevel, StableSince, Unstable, UnstableReason, VERSION_PLACEHOLDER, }; -use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexMap}; +use rustc_data_structures::fx::FxIndexMap; +use rustc_data_structures::unord::{ExtendUnord, UnordMap, UnordSet}; use rustc_hir as hir; use rustc_hir::def::{DefKind, Res}; use rustc_hir::def_id::{LocalDefId, LocalModDefId, CRATE_DEF_ID, LOCAL_CRATE}; @@ -923,7 +924,7 @@ pub fn check_unused_or_stable_features(tcx: TyCtxt<'_>) { } let declared_lang_features = &tcx.features().declared_lang_features; - let mut lang_features = FxHashSet::default(); + let mut lang_features = UnordSet::default(); for &(feature, span, since) in declared_lang_features { if let Some(since) = since { // Warn if the user has enabled an already-stable lang feature. @@ -980,11 +981,11 @@ pub fn check_unused_or_stable_features(tcx: TyCtxt<'_>) { fn check_features<'tcx>( tcx: TyCtxt<'tcx>, remaining_lib_features: &mut FxIndexMap<&Symbol, Span>, - remaining_implications: &mut FxHashMap<Symbol, Symbol>, + remaining_implications: &mut UnordMap<Symbol, Symbol>, defined_features: &LibFeatures, - all_implications: &FxHashMap<Symbol, Symbol>, + all_implications: &UnordMap<Symbol, Symbol>, ) { - for (feature, since) in defined_features.to_vec() { + for (feature, since) in defined_features.to_sorted_vec() { if let FeatureStability::AcceptedSince(since) = since && let Some(span) = remaining_lib_features.get(&feature) { @@ -1021,7 +1022,8 @@ pub fn check_unused_or_stable_features(tcx: TyCtxt<'_>) { // `remaining_lib_features`. let mut all_implications = remaining_implications.clone(); for &cnum in tcx.crates(()) { - all_implications.extend(tcx.stability_implications(cnum)); + all_implications + .extend_unord(tcx.stability_implications(cnum).items().map(|(k, v)| (*k, *v))); } check_features( @@ -1050,10 +1052,7 @@ pub fn check_unused_or_stable_features(tcx: TyCtxt<'_>) { tcx.dcx().emit_err(errors::UnknownFeature { span, feature: *feature }); } - // We only use the hash map contents to emit errors, and the order of - // emitted errors do not affect query stability. - #[allow(rustc::potential_query_instability)] - for (implied_by, feature) in remaining_implications { + for (&implied_by, &feature) in remaining_implications.to_sorted_stable_ord() { let local_defined_features = tcx.lib_features(LOCAL_CRATE); let span = local_defined_features .stability diff --git a/compiler/rustc_span/src/def_id.rs b/compiler/rustc_span/src/def_id.rs index e397fab5459..9f1db227a7c 100644 --- a/compiler/rustc_span/src/def_id.rs +++ b/compiler/rustc_span/src/def_id.rs @@ -1,6 +1,8 @@ use crate::{HashStableContext, Symbol}; use rustc_data_structures::fingerprint::Fingerprint; -use rustc_data_structures::stable_hasher::{Hash64, HashStable, StableHasher, ToStableHashKey}; +use rustc_data_structures::stable_hasher::{ + Hash64, HashStable, StableHasher, StableOrd, ToStableHashKey, +}; use rustc_data_structures::unhash::Unhasher; use rustc_data_structures::AtomicRef; use rustc_index::Idx; @@ -132,6 +134,11 @@ impl Default for DefPathHash { } } +// Safety: `DefPathHash` sort order is not affected (de)serialization. +unsafe impl StableOrd for DefPathHash { + const CAN_USE_UNSTABLE_SORT: bool = true; +} + /// A [`StableCrateId`] is a 64-bit hash of a crate name, together with all /// `-Cmetadata` arguments, and some other data. It is to [`CrateNum`] what [`DefPathHash`] is to /// [`DefId`]. It is stable across compilation sessions. @@ -490,6 +497,15 @@ impl<CTX: HashStableContext> ToStableHashKey<CTX> for CrateNum { } } +impl<CTX: HashStableContext> ToStableHashKey<CTX> for DefPathHash { + type KeyType = DefPathHash; + + #[inline] + fn to_stable_hash_key(&self, _: &CTX) -> DefPathHash { + *self + } +} + macro_rules! typed_def_id { ($Name:ident, $LocalName:ident) => { #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Encodable, Decodable, HashStable_Generic)] diff --git a/compiler/rustc_span/src/symbol.rs b/compiler/rustc_span/src/symbol.rs index 9af81e06303..03af77cb3fb 100644 --- a/compiler/rustc_span/src/symbol.rs +++ b/compiler/rustc_span/src/symbol.rs @@ -4,7 +4,9 @@ use rustc_arena::DroplessArena; use rustc_data_structures::fx::FxIndexSet; -use rustc_data_structures::stable_hasher::{HashStable, StableHasher, ToStableHashKey}; +use rustc_data_structures::stable_hasher::{ + HashStable, StableCompare, StableHasher, ToStableHashKey, +}; use rustc_data_structures::sync::Lock; use rustc_macros::HashStable_Generic; use rustc_serialize::{Decodable, Decoder, Encodable, Encoder}; @@ -2104,6 +2106,14 @@ impl<CTX> ToStableHashKey<CTX> for Symbol { } } +impl StableCompare for Symbol { + const CAN_USE_UNSTABLE_SORT: bool = true; + + fn stable_cmp(&self, other: &Self) -> std::cmp::Ordering { + self.as_str().cmp(other.as_str()) + } +} + pub(crate) struct Interner(Lock<InternerInner>); // The `&'static str`s in this type actually point into the arena. |