From 54d7b327e5182b97fcdb8d90bf7853ffe54364c3 Mon Sep 17 00:00:00 2001
From: Andrew Xie <ndrew.xie@gmail.com>
Date: Thu, 8 Jun 2023 00:38:50 -0400
Subject: Removed stable/unstable sort arg from into_sorted_stable_ord, fixed a
 few misc issues, added collect to UnordItems

---
 .../rustc_data_structures/src/stable_hasher.rs     | 45 ++++++++++++++++++----
 compiler/rustc_data_structures/src/unord.rs        |  8 +++-
 2 files changed, 43 insertions(+), 10 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 a895e28c822..0c1fb7518fa 100644
--- a/compiler/rustc_data_structures/src/stable_hasher.rs
+++ b/compiler/rustc_data_structures/src/stable_hasher.rs
@@ -233,7 +233,17 @@ pub trait ToStableHashKey<HCX> {
 ///  - `DefIndex`, `CrateNum`, `LocalDefId`, because their concrete
 ///    values depend on state that might be different between
 ///    compilation sessions.
-pub unsafe trait StableOrd: Ord {}
+///
+/// The associated constant `CAN_USE_UNSTABLE_SORT` denotes whether
+/// unstable sorting can be used for this type. Set to true if and
+/// only if `a == b` implies `a` and `b` are fully indistinguishable.
+pub unsafe trait StableOrd: Ord {
+    const CAN_USE_UNSTABLE_SORT: bool;
+}
+
+unsafe impl<T: StableOrd> StableOrd for &T {
+    const CAN_USE_UNSTABLE_SORT: bool = T::CAN_USE_UNSTABLE_SORT;
+}
 
 /// Implement HashStable by just calling `Hash::hash()`. Also implement `StableOrd` for the type since
 /// that has the same requirements.
@@ -253,7 +263,9 @@ macro_rules! impl_stable_traits_for_trivial_type {
             }
         }
 
-        unsafe impl $crate::stable_hasher::StableOrd for $t {}
+        unsafe impl $crate::stable_hasher::StableOrd for $t {
+            const CAN_USE_UNSTABLE_SORT: bool = true;
+        }
     };
 }
 
@@ -339,7 +351,9 @@ impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2)
     }
 }
 
-unsafe impl<T1: StableOrd, T2: StableOrd> StableOrd for (T1, T2) {}
+unsafe impl<T1: StableOrd, T2: StableOrd> StableOrd for (T1, T2) {
+    const CAN_USE_UNSTABLE_SORT: bool = T1::CAN_USE_UNSTABLE_SORT && T2::CAN_USE_UNSTABLE_SORT;
+}
 
 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
 where
@@ -355,7 +369,10 @@ where
     }
 }
 
-unsafe impl<T1: StableOrd, T2: StableOrd, T3: StableOrd> StableOrd for (T1, T2, T3) {}
+unsafe impl<T1: StableOrd, T2: StableOrd, T3: StableOrd> StableOrd for (T1, T2, T3) {
+    const CAN_USE_UNSTABLE_SORT: bool =
+        T1::CAN_USE_UNSTABLE_SORT && T2::CAN_USE_UNSTABLE_SORT && T3::CAN_USE_UNSTABLE_SORT;
+}
 
 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
 where
@@ -376,6 +393,10 @@ where
 unsafe impl<T1: StableOrd, T2: StableOrd, T3: StableOrd, T4: StableOrd> StableOrd
     for (T1, T2, T3, T4)
 {
+    const CAN_USE_UNSTABLE_SORT: bool = T1::CAN_USE_UNSTABLE_SORT
+        && T2::CAN_USE_UNSTABLE_SORT
+        && T3::CAN_USE_UNSTABLE_SORT
+        && T4::CAN_USE_UNSTABLE_SORT;
 }
 
 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
@@ -468,7 +489,9 @@ impl<CTX> HashStable<CTX> for str {
     }
 }
 
-unsafe impl StableOrd for &str {}
+unsafe impl StableOrd for &str {
+    const CAN_USE_UNSTABLE_SORT: bool = true;
+}
 
 impl<CTX> HashStable<CTX> for String {
     #[inline]
@@ -479,7 +502,9 @@ impl<CTX> HashStable<CTX> for String {
 
 // Safety: String comparison only depends on their contents and the
 // contents are not changed by (de-)serialization.
-unsafe impl StableOrd for String {}
+unsafe impl StableOrd for String {
+    const CAN_USE_UNSTABLE_SORT: bool = true;
+}
 
 impl<HCX> ToStableHashKey<HCX> for String {
     type KeyType = String;
@@ -505,7 +530,9 @@ impl<CTX> HashStable<CTX> for bool {
 }
 
 // Safety: sort order of bools is not changed by (de-)serialization.
-unsafe impl StableOrd for bool {}
+unsafe impl StableOrd for bool {
+    const CAN_USE_UNSTABLE_SORT: bool = true;
+}
 
 impl<T, CTX> HashStable<CTX> for Option<T>
 where
@@ -523,7 +550,9 @@ where
 }
 
 // Safety: the Option wrapper does not add instability to comparison.
-unsafe impl<T: StableOrd> StableOrd for Option<T> {}
+unsafe impl<T: StableOrd> StableOrd for Option<T> {
+    const CAN_USE_UNSTABLE_SORT: bool = T::CAN_USE_UNSTABLE_SORT;
+}
 
 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
 where
diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs
index 6c8d5414631..e18c7b415f6 100644
--- a/compiler/rustc_data_structures/src/unord.rs
+++ b/compiler/rustc_data_structures/src/unord.rs
@@ -140,12 +140,12 @@ impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> {
     }
 
     #[inline]
-    pub fn into_sorted_stable_ord(self, use_stable_sort: bool) -> Vec<T>
+    pub fn into_sorted_stable_ord(self) -> Vec<T>
     where
         T: Ord + StableOrd,
     {
         let mut items: Vec<T> = self.0.collect();
-        if use_stable_sort {
+        if !T::CAN_USE_UNSTABLE_SORT {
             items.sort();
         } else {
             items.sort_unstable()
@@ -161,6 +161,10 @@ impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> {
         items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx));
         items
     }
+
+    pub fn collect<C: From<UnordItems<T, I>>>(self) -> C {
+        self.into()
+    }
 }
 
 /// This is a set collection type that tries very hard to not expose
-- 
cgit 1.4.1-3-g733a5