Merge from rust-lang/rust

7 files changed, 104 insertions, 30 deletions

diff --git a/compiler/rustc_data_structures/src/flock.rs b/compiler/rustc_data_structures/src/flock.rs
index d423d8acefd..60ae7ad115a 100644
--- a/compiler/rustc_data_structures/src/flock.rs
+++ b/compiler/rustc_data_structures/src/flock.rs
@@ -4,7 +4,18 @@
 //! green/native threading. This is just a bare-bones enough solution for
 //! librustdoc, it is not production quality at all.
 
-cfg_match! {
+// cfg(bootstrap)
+macro_rules! cfg_select_dispatch {
+    ($($tokens:tt)*) => {
+        #[cfg(bootstrap)]
+        cfg_match! { $($tokens)* }
+
+        #[cfg(not(bootstrap))]
+        cfg_select! { $($tokens)* }
+    };
+}
+
+cfg_select_dispatch! {
     target_os = "linux" => {
         mod linux;
         use linux as imp;
diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs
index 865424fd6bb..eb3817a80a7 100644
--- a/compiler/rustc_data_structures/src/lib.rs
+++ b/compiler/rustc_data_structures/src/lib.rs
@@ -10,6 +10,8 @@
 #![allow(internal_features)]
 #![allow(rustc::default_hash_types)]
 #![allow(rustc::potential_query_instability)]
+#![cfg_attr(bootstrap, feature(cfg_match))]
+#![cfg_attr(not(bootstrap), feature(cfg_select))]
 #![deny(unsafe_op_in_unsafe_fn)]
 #![doc(html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/")]
 #![doc(rust_logo)]
@@ -19,12 +21,10 @@
 #![feature(ascii_char_variants)]
 #![feature(assert_matches)]
 #![feature(auto_traits)]
-#![feature(cfg_match)]
 #![feature(core_intrinsics)]
 #![feature(dropck_eyepatch)]
 #![feature(extend_one)]
 #![feature(file_buffered)]
-#![feature(macro_metavar_expr)]
 #![feature(map_try_insert)]
 #![feature(min_specialization)]
 #![feature(negative_impls)]
diff --git a/compiler/rustc_data_structures/src/profiling.rs b/compiler/rustc_data_structures/src/profiling.rs
index 60f007083ba..e3a01e4035c 100644
--- a/compiler/rustc_data_structures/src/profiling.rs
+++ b/compiler/rustc_data_structures/src/profiling.rs
@@ -859,8 +859,19 @@ fn get_thread_id() -> u32 {
     std::thread::current().id().as_u64().get() as u32
 }
 
+// cfg(bootstrap)
+macro_rules! cfg_select_dispatch {
+    ($($tokens:tt)*) => {
+        #[cfg(bootstrap)]
+        cfg_match! { $($tokens)* }
+
+        #[cfg(not(bootstrap))]
+        cfg_select! { $($tokens)* }
+    };
+}
+
 // Memory reporting
-cfg_match! {
+cfg_select_dispatch! {
     windows => {
         pub fn get_resident_set_size() -> Option<usize> {
             use windows::{
diff --git a/compiler/rustc_data_structures/src/transitive_relation.rs b/compiler/rustc_data_structures/src/transitive_relation.rs
index 33ac279f3e0..31abea93819 100644
--- a/compiler/rustc_data_structures/src/transitive_relation.rs
+++ b/compiler/rustc_data_structures/src/transitive_relation.rs
@@ -354,6 +354,20 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
             .collect()
     }
 
+    /// Given an element A, elements B with the lowest index such that `A R B`
+    /// and `B R A`, or `A` if no such element exists.
+    pub fn minimal_scc_representative(&self, a: T) -> T {
+        match self.index(a) {
+            Some(a_i) => self.with_closure(|closure| {
+                closure
+                    .iter(a_i.0)
+                    .find(|i| closure.contains(*i, a_i.0))
+                    .map_or(a, |i| self.elements[i])
+            }),
+            None => a,
+        }
+    }
+
     fn with_closure<OP, R>(&self, op: OP) -> R
     where
         OP: FnOnce(&BitMatrix<usize, usize>) -> R,
diff --git a/compiler/rustc_data_structures/src/transitive_relation/tests.rs b/compiler/rustc_data_structures/src/transitive_relation/tests.rs
index e756c546e41..cba14b5b64b 100644
--- a/compiler/rustc_data_structures/src/transitive_relation/tests.rs
+++ b/compiler/rustc_data_structures/src/transitive_relation/tests.rs
@@ -376,3 +376,44 @@ fn parent() {
     let p = relation.postdom_parent(3);
     assert_eq!(p, Some(0));
 }
+
+#[test]
+fn minimal_scc_representative_1() {
+    //      +---------+
+    //      v         |
+    // a -> c -> d -> e
+    //           ^    ^
+    //           |    |
+    //           b ---+
+
+    // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
+    let mut relation = TransitiveRelationBuilder::default();
+    relation.add("a", "c");
+    relation.add("c", "d");
+    relation.add("d", "e");
+    relation.add("e", "c");
+    relation.add("b", "d");
+    relation.add("b", "e");
+    let relation = relation.freeze();
+
+    assert_eq!(relation.minimal_scc_representative("a"), "a");
+    assert_eq!(relation.minimal_scc_representative("b"), "b");
+    assert_eq!(relation.minimal_scc_representative("c"), "c");
+    assert_eq!(relation.minimal_scc_representative("d"), "c");
+    assert_eq!(relation.minimal_scc_representative("e"), "c");
+}
+
+#[test]
+fn minimal_scc_representative_2() {
+    // "digraph { a -> b; a -> a; b -> a; c -> c}",
+    let mut relation = TransitiveRelationBuilder::default();
+    relation.add("a", "b");
+    relation.add("b", "a");
+    relation.add("a", "a");
+    relation.add("c", "c");
+    let relation = relation.freeze();
+
+    assert_eq!(relation.minimal_scc_representative("a"), "a");
+    assert_eq!(relation.minimal_scc_representative("b"), "a");
+    assert_eq!(relation.minimal_scc_representative("c"), "c");
+}
diff --git a/compiler/rustc_data_structures/src/vec_cache.rs b/compiler/rustc_data_structures/src/vec_cache.rs
index 2ff60ab7f36..3b448c056b7 100644
--- a/compiler/rustc_data_structures/src/vec_cache.rs
+++ b/compiler/rustc_data_structures/src/vec_cache.rs
@@ -68,22 +68,22 @@ impl SlotIndex {
     // slots (see `slot_index_exhaustive` in tests).
     #[inline]
     const fn from_index(idx: u32) -> Self {
-        let mut bucket = match idx.checked_ilog2() {
-            Some(x) => x as usize,
-            None => 0,
-        };
-        let entries;
-        let running_sum;
-        if bucket <= 11 {
-            entries = 1 << 12;
-            running_sum = 0;
-            bucket = 0;
-        } else {
-            entries = 1 << bucket;
-            running_sum = entries;
-            bucket = bucket - 11;
+        const FIRST_BUCKET_SHIFT: usize = 12;
+        if idx < (1 << FIRST_BUCKET_SHIFT) {
+            return SlotIndex {
+                bucket_idx: 0,
+                entries: 1 << FIRST_BUCKET_SHIFT,
+                index_in_bucket: idx as usize,
+            };
+        }
+        // SAFETY: We already ruled out idx 0, so `checked_ilog2` can't return `None`.
+        let bucket = unsafe { idx.checked_ilog2().unwrap_unchecked() as usize };
+        let entries = 1 << bucket;
+        SlotIndex {
+            bucket_idx: bucket - FIRST_BUCKET_SHIFT + 1,
+            entries,
+            index_in_bucket: idx as usize - entries,
         }
-        SlotIndex { bucket_idx: bucket, entries, index_in_bucket: idx as usize - running_sum }
     }
 
     // SAFETY: Buckets must be managed solely by functions here (i.e., get/put on SlotIndex) and
diff --git a/compiler/rustc_data_structures/src/vec_cache/tests.rs b/compiler/rustc_data_structures/src/vec_cache/tests.rs
index 3b65c14162e..9b60913ec92 100644
--- a/compiler/rustc_data_structures/src/vec_cache/tests.rs
+++ b/compiler/rustc_data_structures/src/vec_cache/tests.rs
@@ -75,24 +75,21 @@ fn slot_index_exhaustive() {
     for idx in 0..=u32::MAX {
         buckets[SlotIndex::from_index(idx).bucket_idx] += 1;
     }
-    let mut prev = None::<SlotIndex>;
-    for idx in 0..=u32::MAX {
+    let slot_idx = SlotIndex::from_index(0);
+    assert_eq!(slot_idx.index_in_bucket, 0);
+    assert_eq!(slot_idx.bucket_idx, 0);
+    let mut prev = slot_idx;
+    for idx in 1..=u32::MAX {
         let slot_idx = SlotIndex::from_index(idx);
-        if let Some(p) = prev {
-            if p.bucket_idx == slot_idx.bucket_idx {
-                assert_eq!(p.index_in_bucket + 1, slot_idx.index_in_bucket);
-            } else {
-                assert_eq!(slot_idx.index_in_bucket, 0);
-            }
+        if prev.bucket_idx == slot_idx.bucket_idx {
+            assert_eq!(prev.index_in_bucket + 1, slot_idx.index_in_bucket);
         } else {
-            assert_eq!(idx, 0);
             assert_eq!(slot_idx.index_in_bucket, 0);
-            assert_eq!(slot_idx.bucket_idx, 0);
         }
 
         assert_eq!(buckets[slot_idx.bucket_idx], slot_idx.entries as u32);
         assert_eq!(ENTRIES_BY_BUCKET[slot_idx.bucket_idx], slot_idx.entries, "{}", idx);
 
-        prev = Some(slot_idx);
+        prev = slot_idx;
     }
 }