Merging upstream version 1.74.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 40 insertions, 70 deletions

diff --git a/compiler/rustc_middle/src/mir/traversal.rs b/compiler/rustc_middle/src/mir/traversal.rs
index ec16a8470..a1ff8410e 100644
--- a/compiler/rustc_middle/src/mir/traversal.rs
+++ b/compiler/rustc_middle/src/mir/traversal.rs
@@ -41,6 +41,12 @@ impl<'a, 'tcx> Preorder<'a, 'tcx> {
     }
 }
 
+/// Preorder traversal of a graph.
+///
+/// This function creates an iterator over the `Body`'s basic blocks, that
+/// returns basic blocks in a preorder.
+///
+/// See [`Preorder`]'s docs to learn what is preorder traversal.
 pub fn preorder<'a, 'tcx>(body: &'a Body<'tcx>) -> Preorder<'a, 'tcx> {
     Preorder::new(body, START_BLOCK)
 }
@@ -178,7 +184,7 @@ impl<'a, 'tcx> Postorder<'a, 'tcx> {
         // When we yield `C` and call `traverse_successor`, we push `B` to the stack, but
         // since we've already visited `E`, that child isn't added to the stack. The last
         // two iterations yield `B` and finally `A` for a final traversal of [E, D, C, B, A]
-        while let Some(&mut (_, ref mut iter)) = self.visit_stack.last_mut() && let Some(bb) = iter.next_back() {
+        while let Some(bb) = self.visit_stack.last_mut().and_then(|(_, iter)| iter.next_back()) {
             if self.visited.insert(bb) {
                 if let Some(term) = &self.basic_blocks[bb].terminator {
                     self.visit_stack.push((bb, term.successors()));
@@ -188,16 +194,14 @@ impl<'a, 'tcx> Postorder<'a, 'tcx> {
     }
 }
 
-impl<'a, 'tcx> Iterator for Postorder<'a, 'tcx> {
-    type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
+impl<'tcx> Iterator for Postorder<'_, 'tcx> {
+    type Item = BasicBlock;
 
-    fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
-        let next = self.visit_stack.pop();
-        if next.is_some() {
-            self.traverse_successor();
-        }
+    fn next(&mut self) -> Option<BasicBlock> {
+        let (bb, _) = self.visit_stack.pop()?;
+        self.traverse_successor();
 
-        next.map(|(bb, _)| (bb, &self.basic_blocks[bb]))
+        Some(bb)
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
@@ -215,10 +219,14 @@ impl<'a, 'tcx> Iterator for Postorder<'a, 'tcx> {
     }
 }
 
-/// Creates an iterator over the `Body`'s basic blocks, that:
+/// Postorder traversal of a graph.
+///
+/// This function creates an iterator over the `Body`'s basic blocks, that:
 /// - returns basic blocks in a postorder,
 /// - traverses the `BasicBlocks` CFG cache's reverse postorder backwards, and does not cache the
 ///   postorder itself.
+///
+/// See [`Postorder`]'s docs to learn what is postorder traversal.
 pub fn postorder<'a, 'tcx>(
     body: &'a Body<'tcx>,
 ) -> impl Iterator<Item = (BasicBlock, &'a BasicBlockData<'tcx>)> + ExactSizeIterator + DoubleEndedIterator
@@ -226,7 +234,28 @@ pub fn postorder<'a, 'tcx>(
     reverse_postorder(body).rev()
 }
 
-/// Reverse postorder traversal of a graph
+/// Returns an iterator over all basic blocks reachable from the `START_BLOCK` in no particular
+/// order.
+///
+/// This is clearer than writing `preorder` in cases where the order doesn't matter.
+pub fn reachable<'a, 'tcx>(
+    body: &'a Body<'tcx>,
+) -> impl 'a + Iterator<Item = (BasicBlock, &'a BasicBlockData<'tcx>)> {
+    preorder(body)
+}
+
+/// Returns a `BitSet` containing all basic blocks reachable from the `START_BLOCK`.
+pub fn reachable_as_bitset(body: &Body<'_>) -> BitSet<BasicBlock> {
+    let mut iter = preorder(body);
+    iter.by_ref().for_each(drop);
+    iter.visited
+}
+
+/// Reverse postorder traversal of a graph.
+///
+/// This function creates an iterator over the `Body`'s basic blocks, that:
+/// - returns basic blocks in a reverse postorder,
+/// - makes use of the `BasicBlocks` CFG cache's reverse postorder.
 ///
 /// Reverse postorder is the reverse order of a postorder traversal.
 /// This is different to a preorder traversal and represents a natural
@@ -246,65 +275,6 @@ pub fn postorder<'a, 'tcx>(
 /// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
 /// Note that for a graph containing no loops (i.e., A DAG), this is equivalent to
 /// a topological sort.
-///
-/// Construction of a `ReversePostorder` traversal requires doing a full
-/// postorder traversal of the graph, therefore this traversal should be
-/// constructed as few times as possible. Use the `reset` method to be able
-/// to re-use the traversal
-#[derive(Clone)]
-pub struct ReversePostorder<'a, 'tcx> {
-    body: &'a Body<'tcx>,
-    blocks: Vec<BasicBlock>,
-    idx: usize,
-}
-
-impl<'a, 'tcx> ReversePostorder<'a, 'tcx> {
-    pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> ReversePostorder<'a, 'tcx> {
-        let blocks: Vec<_> = Postorder::new(&body.basic_blocks, root).map(|(bb, _)| bb).collect();
-        let len = blocks.len();
-        ReversePostorder { body, blocks, idx: len }
-    }
-}
-
-impl<'a, 'tcx> Iterator for ReversePostorder<'a, 'tcx> {
-    type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
-
-    fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
-        if self.idx == 0 {
-            return None;
-        }
-        self.idx -= 1;
-
-        self.blocks.get(self.idx).map(|&bb| (bb, &self.body[bb]))
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        (self.idx, Some(self.idx))
-    }
-}
-
-impl<'a, 'tcx> ExactSizeIterator for ReversePostorder<'a, 'tcx> {}
-
-/// Returns an iterator over all basic blocks reachable from the `START_BLOCK` in no particular
-/// order.
-///
-/// This is clearer than writing `preorder` in cases where the order doesn't matter.
-pub fn reachable<'a, 'tcx>(
-    body: &'a Body<'tcx>,
-) -> impl 'a + Iterator<Item = (BasicBlock, &'a BasicBlockData<'tcx>)> {
-    preorder(body)
-}
-
-/// Returns a `BitSet` containing all basic blocks reachable from the `START_BLOCK`.
-pub fn reachable_as_bitset(body: &Body<'_>) -> BitSet<BasicBlock> {
-    let mut iter = preorder(body);
-    (&mut iter).for_each(drop);
-    iter.visited
-}
-
-/// Creates an iterator over the `Body`'s basic blocks, that:
-/// - returns basic blocks in a reverse postorder,
-/// - makes use of the `BasicBlocks` CFG cache's reverse postorder.
 pub fn reverse_postorder<'a, 'tcx>(
     body: &'a Body<'tcx>,
 ) -> impl Iterator<Item = (BasicBlock, &'a BasicBlockData<'tcx>)> + ExactSizeIterator + DoubleEndedIterator