Merge from rustc

5 files changed, 42 insertions, 16 deletions

diff --git a/compiler/rustc_data_structures/src/graph/implementation/mod.rs b/compiler/rustc_data_structures/src/graph/linked_graph/mod.rs
index a80365938b9..ecb0095626b 100644
--- a/compiler/rustc_data_structures/src/graph/implementation/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/linked_graph/mod.rs
@@ -1,4 +1,4 @@
-//! A graph module for use in dataflow, region resolution, and elsewhere.
+//! See [`LinkedGraph`].
 //!
 //! # Interface details
 //!
@@ -28,7 +28,23 @@ use tracing::debug;
 #[cfg(test)]
 mod tests;
 
-pub struct Graph<N, E> {
+/// A concrete graph implementation that supports:
+/// - Nodes and/or edges labelled with custom data types (`N` and `E` respectively).
+/// - Incremental addition of new nodes/edges (but not removal).
+/// - Flat storage of node/edge data in a pair of vectors.
+/// - Iteration over any node's out-edges or in-edges, via linked lists
+///   threaded through the node/edge data.
+///
+/// # Caution
+/// This is an older graph implementation that is still used by some pieces
+/// of diagnostic/debugging code. New code that needs a graph data structure
+/// should consider using `VecGraph` instead, or implementing its own
+/// special-purpose graph with the specific features needed.
+///
+/// This graph implementation predates the later [graph traits](crate::graph),
+/// and does not implement those traits, so it has its own implementations of a
+/// few basic graph algorithms.
+pub struct LinkedGraph<N, E> {
     nodes: Vec<Node<N>>,
     edges: Vec<Edge<E>>,
 }
@@ -71,13 +87,13 @@ impl NodeIndex {
     }
 }
 
-impl<N: Debug, E: Debug> Graph<N, E> {
-    pub fn new() -> Graph<N, E> {
-        Graph { nodes: Vec::new(), edges: Vec::new() }
+impl<N: Debug, E: Debug> LinkedGraph<N, E> {
+    pub fn new() -> Self {
+        Self { nodes: Vec::new(), edges: Vec::new() }
     }
 
-    pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> {
-        Graph { nodes: Vec::with_capacity(nodes), edges: Vec::with_capacity(edges) }
+    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
+        Self { nodes: Vec::with_capacity(nodes), edges: Vec::with_capacity(edges) }
     }
 
     // # Simple accessors
@@ -249,7 +265,7 @@ impl<N: Debug, E: Debug> Graph<N, E> {
 // # Iterators
 
 pub struct AdjacentEdges<'g, N, E> {
-    graph: &'g Graph<N, E>,
+    graph: &'g LinkedGraph<N, E>,
     direction: Direction,
     next: EdgeIndex,
 }
@@ -285,7 +301,7 @@ impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
 }
 
 pub struct DepthFirstTraversal<'g, N, E> {
-    graph: &'g Graph<N, E>,
+    graph: &'g LinkedGraph<N, E>,
     stack: Vec<NodeIndex>,
     visited: DenseBitSet<usize>,
     direction: Direction,
@@ -293,7 +309,7 @@ pub struct DepthFirstTraversal<'g, N, E> {
 
 impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
     pub fn with_start_node(
-        graph: &'g Graph<N, E>,
+        graph: &'g LinkedGraph<N, E>,
         start_node: NodeIndex,
         direction: Direction,
     ) -> Self {
diff --git a/compiler/rustc_data_structures/src/graph/implementation/tests.rs b/compiler/rustc_data_structures/src/graph/linked_graph/tests.rs
index 32a6d9ec881..357aa81a57c 100644
--- a/compiler/rustc_data_structures/src/graph/implementation/tests.rs
+++ b/compiler/rustc_data_structures/src/graph/linked_graph/tests.rs
@@ -1,11 +1,11 @@
 use tracing::debug;
 
-use crate::graph::implementation::*;
+use super::{Debug, LinkedGraph, NodeIndex};
 
-type TestGraph = Graph<&'static str, &'static str>;
+type TestGraph = LinkedGraph<&'static str, &'static str>;
 
 fn create_graph() -> TestGraph {
-    let mut graph = Graph::new();
+    let mut graph = LinkedGraph::new();
 
     // Create a simple graph
     //
@@ -56,7 +56,7 @@ fn each_edge() {
 }
 
 fn test_adjacent_edges<N: PartialEq + Debug, E: PartialEq + Debug>(
-    graph: &Graph<N, E>,
+    graph: &LinkedGraph<N, E>,
     start_index: NodeIndex,
     start_data: N,
     expected_incoming: &[(E, N)],
diff --git a/compiler/rustc_data_structures/src/graph/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs
index 4a1e5db6768..20416b472b2 100644
--- a/compiler/rustc_data_structures/src/graph/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/mod.rs
@@ -1,8 +1,8 @@
 use rustc_index::Idx;
 
 pub mod dominators;
-pub mod implementation;
 pub mod iterate;
+pub mod linked_graph;
 mod reference;
 pub mod reversed;
 pub mod scc;
diff --git a/compiler/rustc_data_structures/src/sync.rs b/compiler/rustc_data_structures/src/sync.rs
index 80d49effbf8..b28c333d860 100644
--- a/compiler/rustc_data_structures/src/sync.rs
+++ b/compiler/rustc_data_structures/src/sync.rs
@@ -43,7 +43,7 @@ pub use self::freeze::{FreezeLock, FreezeReadGuard, FreezeWriteGuard};
 pub use self::lock::{Lock, LockGuard, Mode};
 pub use self::mode::{is_dyn_thread_safe, set_dyn_thread_safe_mode};
 pub use self::parallel::{
-    join, par_for_each_in, par_map, parallel_guard, scope, spawn, try_par_for_each_in,
+    broadcast, join, par_for_each_in, par_map, parallel_guard, scope, spawn, try_par_for_each_in,
 };
 pub use self::vec::{AppendOnlyIndexVec, AppendOnlyVec};
 pub use self::worker_local::{Registry, WorkerLocal};
diff --git a/compiler/rustc_data_structures/src/sync/parallel.rs b/compiler/rustc_data_structures/src/sync/parallel.rs
index 64db39cc4c6..ab65c7f3a6b 100644
--- a/compiler/rustc_data_structures/src/sync/parallel.rs
+++ b/compiler/rustc_data_structures/src/sync/parallel.rs
@@ -237,3 +237,13 @@ pub fn par_map<I: DynSend, T: IntoIterator<Item = I>, R: DynSend, C: FromIterato
         }
     })
 }
+
+pub fn broadcast<R: DynSend>(op: impl Fn(usize) -> R + DynSync) -> Vec<R> {
+    if mode::is_dyn_thread_safe() {
+        let op = FromDyn::from(op);
+        let results = rayon_core::broadcast(|context| op.derive(op(context.index())));
+        results.into_iter().map(|r| r.into_inner()).collect()
+    } else {
+        vec![op(0)]
+    }
+}