Merge from rust-lang/rust

5 files changed, 94 insertions, 85 deletions

diff --git a/compiler/rustc_data_structures/src/graph/dominators/tests.rs b/compiler/rustc_data_structures/src/graph/dominators/tests.rs
index ef82193a4b9..6c078ca7c6e 100644
--- a/compiler/rustc_data_structures/src/graph/dominators/tests.rs
+++ b/compiler/rustc_data_structures/src/graph/dominators/tests.rs
@@ -15,17 +15,10 @@ fn diamond() {
 #[test]
 fn paper() {
     // example from the paper:
-    let graph = TestGraph::new(6, &[
-        (6, 5),
-        (6, 4),
-        (5, 1),
-        (4, 2),
-        (4, 3),
-        (1, 2),
-        (2, 3),
-        (3, 2),
-        (2, 1),
-    ]);
+    let graph = TestGraph::new(
+        6,
+        &[(6, 5), (6, 4), (5, 1), (4, 2), (4, 3), (1, 2), (2, 3), (3, 2), (2, 1)],
+    );
 
     let d = dominators(&graph);
     assert_eq!(d.immediate_dominator(0), None); // <-- note that 0 is not in graph
@@ -40,19 +33,10 @@ fn paper() {
 #[test]
 fn paper_slt() {
     // example from the paper:
-    let graph = TestGraph::new(1, &[
-        (1, 2),
-        (1, 3),
-        (2, 3),
-        (2, 7),
-        (3, 4),
-        (3, 6),
-        (4, 5),
-        (5, 4),
-        (6, 7),
-        (7, 8),
-        (8, 5),
-    ]);
+    let graph = TestGraph::new(
+        1,
+        &[(1, 2), (1, 3), (2, 3), (2, 7), (3, 4), (3, 6), (4, 5), (5, 4), (6, 7), (7, 8), (8, 5)],
+    );
 
     dominators(&graph);
 }
@@ -69,21 +53,24 @@ fn immediate_dominator() {
 
 #[test]
 fn transitive_dominator() {
-    let graph = TestGraph::new(0, &[
-        // First tree branch.
-        (0, 1),
-        (1, 2),
-        (2, 3),
-        (3, 4),
-        // Second tree branch.
-        (1, 5),
-        (5, 6),
-        // Third tree branch.
-        (0, 7),
-        // These links make 0 the dominator for 2 and 3.
-        (7, 2),
-        (5, 3),
-    ]);
+    let graph = TestGraph::new(
+        0,
+        &[
+            // First tree branch.
+            (0, 1),
+            (1, 2),
+            (2, 3),
+            (3, 4),
+            // Second tree branch.
+            (1, 5),
+            (5, 6),
+            // Third tree branch.
+            (0, 7),
+            // These links make 0 the dominator for 2 and 3.
+            (7, 2),
+            (5, 3),
+        ],
+    );
 
     let d = dominators(&graph);
     assert_eq!(d.immediate_dominator(2), Some(0));
diff --git a/compiler/rustc_data_structures/src/graph/implementation/tests.rs b/compiler/rustc_data_structures/src/graph/implementation/tests.rs
index 7a240f4e58b..32a6d9ec881 100644
--- a/compiler/rustc_data_structures/src/graph/implementation/tests.rs
+++ b/compiler/rustc_data_structures/src/graph/implementation/tests.rs
@@ -110,10 +110,13 @@ fn each_adjacent_from_a() {
 #[test]
 fn each_adjacent_from_b() {
     let graph = create_graph();
-    test_adjacent_edges(&graph, NodeIndex(1), "B", &[("FB", "F"), ("AB", "A")], &[
-        ("BD", "D"),
-        ("BC", "C"),
-    ]);
+    test_adjacent_edges(
+        &graph,
+        NodeIndex(1),
+        "B",
+        &[("FB", "F"), ("AB", "A")],
+        &[("BD", "D"), ("BC", "C")],
+    );
 }
 
 #[test]
diff --git a/compiler/rustc_data_structures/src/graph/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs
index 92035e8bc48..4a1e5db6768 100644
--- a/compiler/rustc_data_structures/src/graph/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/mod.rs
@@ -14,7 +14,23 @@ mod tests;
 pub trait DirectedGraph {
     type Node: Idx;
 
+    /// Returns the total number of nodes in this graph.
+    ///
+    /// Several graph algorithm implementations assume that every node ID is
+    /// strictly less than the number of nodes, i.e. nodes are densely numbered.
+    /// That assumption allows them to use `num_nodes` to allocate per-node
+    /// data structures, indexed by node.
     fn num_nodes(&self) -> usize;
+
+    /// Iterates over all nodes of a graph in ascending numeric order.
+    ///
+    /// Assumes that nodes are densely numbered, i.e. every index in
+    /// `0..num_nodes` is a valid node.
+    fn iter_nodes(
+        &self,
+    ) -> impl Iterator<Item = Self::Node> + DoubleEndedIterator + ExactSizeIterator {
+        (0..self.num_nodes()).map(<Self::Node as Idx>::new)
+    }
 }
 
 pub trait NumEdges: DirectedGraph {
diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs
index 06fedef00fc..93f6192b10b 100644
--- a/compiler/rustc_data_structures/src/graph/scc/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs
@@ -333,8 +333,8 @@ where
             to_annotation,
         };
 
-        let scc_indices = (0..num_nodes)
-            .map(G::Node::new)
+        let scc_indices = graph
+            .iter_nodes()
             .map(|node| match this.start_walk_from(node) {
                 WalkReturn::Complete { scc_index, .. } => scc_index,
                 WalkReturn::Cycle { min_depth, .. } => {
diff --git a/compiler/rustc_data_structures/src/graph/scc/tests.rs b/compiler/rustc_data_structures/src/graph/scc/tests.rs
index 7c876c82af2..373f87bfdbc 100644
--- a/compiler/rustc_data_structures/src/graph/scc/tests.rs
+++ b/compiler/rustc_data_structures/src/graph/scc/tests.rs
@@ -326,46 +326,49 @@ fn test_bug_max_leak_minimised() {
 
 #[test]
 fn test_bug_max_leak() {
-    let graph = TestGraph::new(8, &[
-        (0, 0),
-        (0, 18),
-        (0, 19),
-        (0, 1),
-        (0, 2),
-        (0, 7),
-        (0, 8),
-        (0, 23),
-        (18, 0),
-        (18, 12),
-        (19, 0),
-        (19, 25),
-        (12, 18),
-        (12, 3),
-        (12, 5),
-        (3, 12),
-        (3, 21),
-        (3, 22),
-        (5, 13),
-        (21, 3),
-        (22, 3),
-        (13, 5),
-        (13, 4),
-        (4, 13),
-        (4, 0),
-        (2, 11),
-        (7, 6),
-        (6, 20),
-        (20, 6),
-        (8, 17),
-        (17, 9),
-        (9, 16),
-        (16, 26),
-        (26, 15),
-        (15, 10),
-        (10, 14),
-        (14, 27),
-        (23, 24),
-    ]);
+    let graph = TestGraph::new(
+        8,
+        &[
+            (0, 0),
+            (0, 18),
+            (0, 19),
+            (0, 1),
+            (0, 2),
+            (0, 7),
+            (0, 8),
+            (0, 23),
+            (18, 0),
+            (18, 12),
+            (19, 0),
+            (19, 25),
+            (12, 18),
+            (12, 3),
+            (12, 5),
+            (3, 12),
+            (3, 21),
+            (3, 22),
+            (5, 13),
+            (21, 3),
+            (22, 3),
+            (13, 5),
+            (13, 4),
+            (4, 13),
+            (4, 0),
+            (2, 11),
+            (7, 6),
+            (6, 20),
+            (20, 6),
+            (8, 17),
+            (17, 9),
+            (9, 16),
+            (16, 26),
+            (26, 15),
+            (15, 10),
+            (10, 14),
+            (14, 27),
+            (23, 24),
+        ],
+    );
     let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, |w| match w {
         22 => MaxReached(1),
         24 => MaxReached(2),