From 739e5ef49e28ea4b2ab20bd28251a2299bd6889c Mon Sep 17 00:00:00 2001 From: Michael Woerister Date: Thu, 21 Dec 2023 10:27:34 +0100 Subject: Split StableCompare trait out of StableOrd trait. StableCompare 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`.) --- .../rustc_data_structures/src/stable_hasher.rs | 26 +++++++ compiler/rustc_data_structures/src/unord.rs | 80 ++++++++++++++++++---- 2 files changed, 91 insertions(+), 15 deletions(-) (limited to 'compiler/rustc_data_structures/src') 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 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 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..2475713012d 100644 --- a/compiler/rustc_data_structures/src/unord.rs +++ b/compiler/rustc_data_structures/src/unord.rs @@ -14,7 +14,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,7 +134,7 @@ impl<'a, T: Copy + 'a, I: Iterator> UnordItems<&'a T, I> { } } -impl> UnordItems { +impl> UnordItems { pub fn into_sorted(self, hcx: &HCX) -> Vec where T: ToStableHashKey, @@ -147,13 +147,36 @@ impl> UnordItems { #[inline] pub fn into_sorted_stable_ord(self) -> Vec where - T: Ord + StableOrd, + T: StableCompare, { let mut items: Vec = self.0.collect(); if !T::CAN_USE_UNSTABLE_SORT { - items.sort(); + items.sort_by(T::stable_cmp); + } else { + items.sort_unstable_by(T::stable_cmp) + } + items + } + + #[inline] + pub fn into_sorted_stable_ord_by_key(self, project_to_key: C) -> Vec + where + K: StableCompare, + C: for<'a> Fn(&'a T) -> &'a K, + { + let mut items: Vec = self.0.collect(); + if !K::CAN_USE_UNSTABLE_SORT { + items.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 { - items.sort_unstable() + items.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 +291,30 @@ impl UnordSet { } /// 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 + pub fn to_sorted_stable_ord(&self) -> Vec<&V> where - V: Ord + StableOrd + Clone, + V: StableCompare, { - let mut items: Vec = 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 + where + V: StableCompare, + { + let mut items: Vec = self.inner.into_iter().collect(); + items.sort_unstable_by(V::stable_cmp); items } @@ -483,16 +520,16 @@ impl UnordMap { 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 +547,19 @@ impl UnordMap { 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). /// -- cgit 1.4.1-3-g733a5 From 900a11bbec52fdae89012ccb3ea4045edddc3995 Mon Sep 17 00:00:00 2001 From: Michael Woerister Date: Fri, 22 Dec 2023 10:46:28 +0100 Subject: Provide generalized collect methods for UnordItems --- compiler/rustc_data_structures/src/unord.rs | 74 ++++++++++++++++++----------- 1 file changed, 45 insertions(+), 29 deletions(-) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs index 2475713012d..476ea432a0c 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}, @@ -135,13 +134,12 @@ impl<'a, T: Copy + 'a, I: Iterator> UnordItems<&'a T, I> { } impl> UnordItems { + #[inline] pub fn into_sorted(self, hcx: &HCX) -> Vec where T: ToStableHashKey, { - let mut items: Vec = self.0.collect(); - items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx)); - items + self.collect_sorted(hcx, true) } #[inline] @@ -149,13 +147,7 @@ impl> UnordItems { where T: StableCompare, { - let mut items: Vec = self.0.collect(); - if !T::CAN_USE_UNSTABLE_SORT { - items.sort_by(T::stable_cmp); - } else { - items.sort_unstable_by(T::stable_cmp) - } - items + self.collect_stable_ord_by_key(|x| x) } #[inline] @@ -164,29 +156,53 @@ impl> UnordItems { K: StableCompare, C: for<'a> Fn(&'a T) -> &'a K, { - let mut items: Vec = self.0.collect(); - if !K::CAN_USE_UNSTABLE_SORT { - items.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 { - items.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) - }); + self.collect_stable_ord_by_key(project_to_key) + } + + pub fn collect_sorted(self, hcx: &HCX, cache_sort_key: bool) -> C + where + T: ToStableHashKey, + C: FromIterator + 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(self, hcx: &HCX) -> SmallVec<[T; LEN]> + pub fn collect_stable_ord_by_key(self, project_to_key: P) -> C where - T: ToStableHashKey, + K: StableCompare, + P: for<'a> Fn(&'a T) -> &'a K, + C: FromIterator + 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 } } -- cgit 1.4.1-3-g733a5 From 077540cedf836b3c6e17db39de21e2278bae90fc Mon Sep 17 00:00:00 2001 From: Michael Woerister Date: Thu, 4 Jan 2024 13:51:06 +0100 Subject: Address review comments and add back some #[inline] attrs from removed commits. --- compiler/rustc_data_structures/src/unord.rs | 2 ++ compiler/rustc_passes/src/stability.rs | 2 -- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs index 476ea432a0c..bd4dff6f62f 100644 --- a/compiler/rustc_data_structures/src/unord.rs +++ b/compiler/rustc_data_structures/src/unord.rs @@ -159,6 +159,7 @@ impl> UnordItems { self.collect_stable_ord_by_key(project_to_key) } + #[inline] pub fn collect_sorted(self, hcx: &HCX, cache_sort_key: bool) -> C where T: ToStableHashKey, @@ -178,6 +179,7 @@ impl> UnordItems { items } + #[inline] pub fn collect_stable_ord_by_key(self, project_to_key: P) -> C where K: StableCompare, diff --git a/compiler/rustc_passes/src/stability.rs b/compiler/rustc_passes/src/stability.rs index adf4c231f78..18b9ba0f042 100644 --- a/compiler/rustc_passes/src/stability.rs +++ b/compiler/rustc_passes/src/stability.rs @@ -1052,8 +1052,6 @@ 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. 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 -- cgit 1.4.1-3-g733a5