Merge from rust-lang/rust

4 files changed, 62 insertions, 18 deletions

diff --git a/compiler/rustc_data_structures/src/flat_map_in_place.rs b/compiler/rustc_data_structures/src/flat_map_in_place.rs
index e66b00b7557..6d718059f9c 100644
--- a/compiler/rustc_data_structures/src/flat_map_in_place.rs
+++ b/compiler/rustc_data_structures/src/flat_map_in_place.rs
@@ -1,4 +1,4 @@
-use std::ptr;
+use std::{mem, ptr};
 
 use smallvec::{Array, SmallVec};
 use thin_vec::ThinVec;
@@ -13,39 +13,44 @@ pub trait FlatMapInPlace<T>: Sized {
 // The implementation of this method is syntactically identical for all the
 // different vector types.
 macro_rules! flat_map_in_place {
-    () => {
+    ($vec:ident $( where T: $bound:path)?) => {
         fn flat_map_in_place<F, I>(&mut self, mut f: F)
         where
             F: FnMut(T) -> I,
             I: IntoIterator<Item = T>,
         {
+            struct LeakGuard<'a, T $(: $bound)?>(&'a mut $vec<T>);
+
+            impl<'a, T $(: $bound)?> Drop for LeakGuard<'a, T> {
+                fn drop(&mut self) {
+                    unsafe {
+                        self.0.set_len(0); // make sure we just leak elements in case of panic
+                    }
+                }
+            }
+
+            let this = LeakGuard(self);
+
             let mut read_i = 0;
             let mut write_i = 0;
             unsafe {
-                let mut old_len = self.len();
-                self.set_len(0); // make sure we just leak elements in case of panic
-
-                while read_i < old_len {
+                while read_i < this.0.len() {
                     // move the read_i'th item out of the vector and map it
                     // to an iterator
-                    let e = ptr::read(self.as_ptr().add(read_i));
+                    let e = ptr::read(this.0.as_ptr().add(read_i));
                     let iter = f(e).into_iter();
                     read_i += 1;
 
                     for e in iter {
                         if write_i < read_i {
-                            ptr::write(self.as_mut_ptr().add(write_i), e);
+                            ptr::write(this.0.as_mut_ptr().add(write_i), e);
                             write_i += 1;
                         } else {
                             // If this is reached we ran out of space
                             // in the middle of the vector.
                             // However, the vector is in a valid state here,
                             // so we just do a somewhat inefficient insert.
-                            self.set_len(old_len);
-                            self.insert(write_i, e);
-
-                            old_len = self.len();
-                            self.set_len(0);
+                            this.0.insert(write_i, e);
 
                             read_i += 1;
                             write_i += 1;
@@ -54,20 +59,23 @@ macro_rules! flat_map_in_place {
                 }
 
                 // write_i tracks the number of actually written new items.
-                self.set_len(write_i);
+                this.0.set_len(write_i);
+
+                // The ThinVec is in a sane state again. Prevent the LeakGuard from leaking the data.
+                mem::forget(this);
             }
         }
     };
 }
 
 impl<T> FlatMapInPlace<T> for Vec<T> {
-    flat_map_in_place!();
+    flat_map_in_place!(Vec);
 }
 
 impl<T, A: Array<Item = T>> FlatMapInPlace<T> for SmallVec<A> {
-    flat_map_in_place!();
+    flat_map_in_place!(SmallVec where T: Array);
 }
 
 impl<T> FlatMapInPlace<T> for ThinVec<T> {
-    flat_map_in_place!();
+    flat_map_in_place!(ThinVec);
 }
diff --git a/compiler/rustc_data_structures/src/sharded.rs b/compiler/rustc_data_structures/src/sharded.rs
index 65488c73d3c..5a53f8af5f8 100644
--- a/compiler/rustc_data_structures/src/sharded.rs
+++ b/compiler/rustc_data_structures/src/sharded.rs
@@ -143,6 +143,9 @@ pub fn shards() -> usize {
 pub type ShardedHashMap<K, V> = Sharded<FxHashMap<K, V>>;
 
 impl<K: Eq, V> ShardedHashMap<K, V> {
+    pub fn with_capacity(cap: usize) -> Self {
+        Self::new(|| FxHashMap::with_capacity_and_hasher(cap, rustc_hash::FxBuildHasher::default()))
+    }
     pub fn len(&self) -> usize {
         self.lock_shards().map(|shard| shard.len()).sum()
     }
diff --git a/compiler/rustc_data_structures/src/sorted_map.rs b/compiler/rustc_data_structures/src/sorted_map.rs
index 066ea03b4ac..a01a420dfbd 100644
--- a/compiler/rustc_data_structures/src/sorted_map.rs
+++ b/compiler/rustc_data_structures/src/sorted_map.rs
@@ -1,4 +1,5 @@
 use std::borrow::Borrow;
+use std::cmp::Ordering;
 use std::fmt::Debug;
 use std::mem;
 use std::ops::{Bound, Index, IndexMut, RangeBounds};
@@ -156,6 +157,38 @@ impl<K: Ord, V> SortedMap<K, V> {
         &self.data[start..end]
     }
 
+    /// `sm.range_is_empty(r)` == `sm.range(r).is_empty()`, but is faster.
+    #[inline]
+    pub fn range_is_empty<R>(&self, range: R) -> bool
+    where
+        R: RangeBounds<K>,
+    {
+        // `range` must (via `range_slice_indices`) search for the start and
+        // end separately. But here we can do a single binary search for the
+        // entire range. If a single `x` matching `range` is found then the
+        // range is *not* empty.
+        self.data
+            .binary_search_by(|(x, _)| {
+                // Is `x` below `range`?
+                match range.start_bound() {
+                    Bound::Included(start) if x < start => return Ordering::Less,
+                    Bound::Excluded(start) if x <= start => return Ordering::Less,
+                    _ => {}
+                };
+
+                // Is `x` above `range`?
+                match range.end_bound() {
+                    Bound::Included(end) if x > end => return Ordering::Greater,
+                    Bound::Excluded(end) if x >= end => return Ordering::Greater,
+                    _ => {}
+                };
+
+                // `x` must be within `range`.
+                Ordering::Equal
+            })
+            .is_err()
+    }
+
     #[inline]
     pub fn remove_range<R>(&mut self, range: R)
     where
diff --git a/compiler/rustc_data_structures/src/sorted_map/index_map.rs b/compiler/rustc_data_structures/src/sorted_map/index_map.rs
index 1654867739f..b38b09d60eb 100644
--- a/compiler/rustc_data_structures/src/sorted_map/index_map.rs
+++ b/compiler/rustc_data_structures/src/sorted_map/index_map.rs
@@ -147,7 +147,7 @@ impl<I: Idx, K: Ord, V> FromIterator<(K, V)> for SortedIndexMultiMap<I, K, V> {
     where
         J: IntoIterator<Item = (K, V)>,
     {
-        let items = IndexVec::from_iter(iter);
+        let items = IndexVec::<I, _>::from_iter(iter);
         let mut idx_sorted_by_item_key: Vec<_> = items.indices().collect();
 
         // `sort_by_key` is stable, so insertion order is preserved for duplicate items.