Auto merge of #3003 - rust-lang:rustup-2023-08-02, r=RalfJung

Automatic sync from rustc

5 files changed, 20 insertions, 60 deletions

diff --git a/compiler/rustc_data_structures/src/base_n.rs b/compiler/rustc_data_structures/src/base_n.rs
index 4567759c004..58704350706 100644
--- a/compiler/rustc_data_structures/src/base_n.rs
+++ b/compiler/rustc_data_structures/src/base_n.rs
@@ -16,22 +16,21 @@ const BASE_64: &[u8; MAX_BASE] =
 pub fn push_str(mut n: u128, base: usize, output: &mut String) {
     debug_assert!(base >= 2 && base <= MAX_BASE);
     let mut s = [0u8; 128];
-    let mut index = 0;
+    let mut index = s.len();
 
     let base = base as u128;
 
     loop {
+        index -= 1;
         s[index] = BASE_64[(n % base) as usize];
-        index += 1;
         n /= base;
 
         if n == 0 {
             break;
         }
     }
-    s[0..index].reverse();
 
-    output.push_str(str::from_utf8(&s[0..index]).unwrap());
+    output.push_str(str::from_utf8(&s[index..]).unwrap());
 }
 
 #[inline]
diff --git a/compiler/rustc_data_structures/src/binary_search_util/mod.rs b/compiler/rustc_data_structures/src/binary_search_util/mod.rs
index d40172a2e2f..bc8a6b9eac0 100644
--- a/compiler/rustc_data_structures/src/binary_search_util/mod.rs
+++ b/compiler/rustc_data_structures/src/binary_search_util/mod.rs
@@ -10,41 +10,17 @@ pub fn binary_search_slice<'d, E, K>(data: &'d [E], key_fn: impl Fn(&E) -> K, ke
 where
     K: Ord,
 {
-    let Ok(mid) = data.binary_search_by_key(key, &key_fn) else {
+    let size = data.len();
+    let start = data.partition_point(|x| key_fn(x) < *key);
+    // At this point `start` either points at the first entry with equal or
+    // greater key or is equal to `size` in case all elements have smaller keys
+    if start == size || key_fn(&data[start]) != *key {
         return &[];
     };
-    let size = data.len();
-
-    // We get back *some* element with the given key -- so do
-    // a galloping search backwards to find the *first* one.
-    let mut start = mid;
-    let mut previous = mid;
-    let mut step = 1;
-    loop {
-        start = start.saturating_sub(step);
-        if start == 0 || key_fn(&data[start]) != *key {
-            break;
-        }
-        previous = start;
-        step *= 2;
-    }
-    step = previous - start;
-    while step > 1 {
-        let half = step / 2;
-        let mid = start + half;
-        if key_fn(&data[mid]) != *key {
-            start = mid;
-        }
-        step -= half;
-    }
-    // adjust by one if we have overshot
-    if start < size && key_fn(&data[start]) != *key {
-        start += 1;
-    }
 
     // Now search forward to find the *last* one.
-    let mut end = mid;
-    let mut previous = mid;
+    let mut end = start;
+    let mut previous = start;
     let mut step = 1;
     loop {
         end = end.saturating_add(step).min(size);
diff --git a/compiler/rustc_data_structures/src/sorted_map.rs b/compiler/rustc_data_structures/src/sorted_map.rs
index 9409057d484..60b343afbed 100644
--- a/compiler/rustc_data_structures/src/sorted_map.rs
+++ b/compiler/rustc_data_structures/src/sorted_map.rs
@@ -49,12 +49,11 @@ impl<K: Ord, V> SortedMap<K, V> {
     }
 
     #[inline]
-    pub fn insert(&mut self, key: K, mut value: V) -> Option<V> {
+    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
         match self.lookup_index_for(&key) {
             Ok(index) => {
                 let slot = unsafe { self.data.get_unchecked_mut(index) };
-                mem::swap(&mut slot.1, &mut value);
-                Some(value)
+                Some(mem::replace(&mut slot.1, value))
             }
             Err(index) => {
                 self.data.insert(index, (key, value));
diff --git a/compiler/rustc_data_structures/src/sync/vec.rs b/compiler/rustc_data_structures/src/sync/vec.rs
index e36dded9e5e..314496ce9f0 100644
--- a/compiler/rustc_data_structures/src/sync/vec.rs
+++ b/compiler/rustc_data_structures/src/sync/vec.rs
@@ -43,37 +43,23 @@ impl<I: Idx, T: Copy> AppendOnlyIndexVec<I, T> {
 
 #[derive(Default)]
 pub struct AppendOnlyVec<T: Copy> {
-    #[cfg(not(parallel_compiler))]
-    vec: elsa::vec::FrozenVec<T>,
-    #[cfg(parallel_compiler)]
-    vec: elsa::sync::LockFreeFrozenVec<T>,
+    vec: parking_lot::RwLock<Vec<T>>,
 }
 
 impl<T: Copy> AppendOnlyVec<T> {
     pub fn new() -> Self {
-        Self {
-            #[cfg(not(parallel_compiler))]
-            vec: elsa::vec::FrozenVec::new(),
-            #[cfg(parallel_compiler)]
-            vec: elsa::sync::LockFreeFrozenVec::new(),
-        }
+        Self { vec: Default::default() }
     }
 
     pub fn push(&self, val: T) -> usize {
-        #[cfg(not(parallel_compiler))]
-        let i = self.vec.len();
-        #[cfg(not(parallel_compiler))]
-        self.vec.push(val);
-        #[cfg(parallel_compiler)]
-        let i = self.vec.push(val);
-        i
+        let mut v = self.vec.write();
+        let n = v.len();
+        v.push(val);
+        n
     }
 
     pub fn get(&self, i: usize) -> Option<T> {
-        #[cfg(not(parallel_compiler))]
-        return self.vec.get_copy(i);
-        #[cfg(parallel_compiler)]
-        return self.vec.get(i);
+        self.vec.read().get(i).copied()
     }
 
     pub fn iter_enumerated(&self) -> impl Iterator<Item = (usize, T)> + '_ {
diff --git a/compiler/rustc_data_structures/src/sync/worker_local.rs b/compiler/rustc_data_structures/src/sync/worker_local.rs
index d61bb55be68..8c84daf4f16 100644
--- a/compiler/rustc_data_structures/src/sync/worker_local.rs
+++ b/compiler/rustc_data_structures/src/sync/worker_local.rs
@@ -116,7 +116,7 @@ pub struct WorkerLocal<T> {
 
 // This is safe because the `deref` call will return a reference to a `T` unique to each thread
 // or it will panic for threads without an associated local. So there isn't a need for `T` to do
-// it's own synchronization. The `verify` method on `RegistryId` has an issue where the the id
+// it's own synchronization. The `verify` method on `RegistryId` has an issue where the id
 // can be reused, but `WorkerLocal` has a reference to `Registry` which will prevent any reuse.
 #[cfg(parallel_compiler)]
 unsafe impl<T: Send> Sync for WorkerLocal<T> {}