1 files changed, 63 insertions, 0 deletions
diff --git a/compiler/rustc_middle/src/mir/graph_cyclic_cache.rs b/compiler/rustc_middle/src/mir/graph_cyclic_cache.rs
new file mode 100644
index 000000000..f97bf2883
--- /dev/null
+++ b/compiler/rustc_middle/src/mir/graph_cyclic_cache.rs
@@ -0,0 +1,63 @@
+use rustc_data_structures::graph::{
+    self, DirectedGraph, WithNumNodes, WithStartNode, WithSuccessors,
+};
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
+use rustc_data_structures::sync::OnceCell;
+use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
+
+/// Helper type to cache the result of `graph::is_cyclic`.
+#[derive(Clone, Debug)]
+pub(super) struct GraphIsCyclicCache {
+    cache: OnceCell<bool>,
+}
+
+impl GraphIsCyclicCache {
+    #[inline]
+    pub(super) fn new() -> Self {
+        GraphIsCyclicCache { cache: OnceCell::new() }
+    }
+
+    pub(super) fn is_cyclic<G>(&self, graph: &G) -> bool
+    where
+        G: ?Sized + DirectedGraph + WithStartNode + WithSuccessors + WithNumNodes,
+    {
+        *self.cache.get_or_init(|| graph::is_cyclic(graph))
+    }
+
+    /// Invalidates the cache.
+    #[inline]
+    pub(super) fn invalidate(&mut self) {
+        // Invalidating the cache requires mutating the MIR, which in turn requires a unique
+        // reference (`&mut`) to the `mir::Body`. Because of this, we can assume that all
+        // callers of `invalidate` have a unique reference to the MIR and thus to the
+        // cache. This means we never need to do synchronization when `invalidate` is called,
+        // we can simply reinitialize the `OnceCell`.
+        self.cache = OnceCell::new();
+    }
+}
+
+impl<S: Encoder> Encodable<S> for GraphIsCyclicCache {
+    #[inline]
+    fn encode(&self, s: &mut S) {
+        Encodable::encode(&(), s);
+    }
+}
+
+impl<D: Decoder> Decodable<D> for GraphIsCyclicCache {
+    #[inline]
+    fn decode(d: &mut D) -> Self {
+        let () = Decodable::decode(d);
+        Self::new()
+    }
+}
+
+impl<CTX> HashStable<CTX> for GraphIsCyclicCache {
+    #[inline]
+    fn hash_stable(&self, _: &mut CTX, _: &mut StableHasher) {
+        // do nothing
+    }
+}
+
+TrivialTypeTraversalAndLiftImpls! {
+    GraphIsCyclicCache,
+}