From 1a23a6fd8b27943ffdbac2d5e4eb088cdecb06ff Mon Sep 17 00:00:00 2001
From: Zalathar <Zalathar@users.noreply.github.com>
Date: Sun, 12 Jan 2025 12:40:03 +1100
Subject: Add wrapper type `ReversedGraph` for swapping successors/predecessors

---
 compiler/rustc_data_structures/src/graph/mod.rs    |  1 +
 .../rustc_data_structures/src/graph/reversed.rs    | 42 ++++++++++++++++++++++
 2 files changed, 43 insertions(+)
 create mode 100644 compiler/rustc_data_structures/src/graph/reversed.rs

(limited to 'compiler/rustc_data_structures/src/graph')

diff --git a/compiler/rustc_data_structures/src/graph/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs
index 103ddd917bf..92035e8bc48 100644
--- a/compiler/rustc_data_structures/src/graph/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/mod.rs
@@ -4,6 +4,7 @@ pub mod dominators;
 pub mod implementation;
 pub mod iterate;
 mod reference;
+pub mod reversed;
 pub mod scc;
 pub mod vec_graph;
 
diff --git a/compiler/rustc_data_structures/src/graph/reversed.rs b/compiler/rustc_data_structures/src/graph/reversed.rs
new file mode 100644
index 00000000000..9b726deaa15
--- /dev/null
+++ b/compiler/rustc_data_structures/src/graph/reversed.rs
@@ -0,0 +1,42 @@
+use crate::graph::{DirectedGraph, Predecessors, Successors};
+
+/// View that reverses the direction of edges in its underlying graph, so that
+/// successors become predecessors and vice-versa.
+///
+/// Because of `impl<G: Graph> Graph for &G`, the underlying graph can be
+/// wrapped by-reference instead of by-value if desired.
+#[derive(Clone, Copy, Debug)]
+pub struct ReversedGraph<G> {
+    pub inner: G,
+}
+
+impl<G> ReversedGraph<G> {
+    pub fn new(inner: G) -> Self {
+        Self { inner }
+    }
+}
+
+impl<G: DirectedGraph> DirectedGraph for ReversedGraph<G> {
+    type Node = G::Node;
+
+    fn num_nodes(&self) -> usize {
+        self.inner.num_nodes()
+    }
+}
+
+// Implementing `StartNode` is not possible in general, because the start node
+// of an underlying graph is instead an _end_ node in the reversed graph.
+// But would be possible to define another wrapper type that adds an explicit
+// start node to its underlying graph, if desired.
+
+impl<G: Predecessors> Successors for ReversedGraph<G> {
+    fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
+        self.inner.predecessors(node)
+    }
+}
+
+impl<G: Successors> Predecessors for ReversedGraph<G> {
+    fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
+        self.inner.successors(node)
+    }
+}
-- 
cgit 1.4.1-3-g733a5