3 files changed, 178 insertions, 59 deletions

diff --git a/compiler/rustc_middle/src/traits/solve/cache.rs b/compiler/rustc_middle/src/traits/solve/cache.rs
new file mode 100644
index 000000000..9898b0019
--- /dev/null
+++ b/compiler/rustc_middle/src/traits/solve/cache.rs
@@ -0,0 +1,100 @@
+use super::{CanonicalInput, QueryResult};
+use crate::ty::TyCtxt;
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::sync::Lock;
+use rustc_query_system::cache::WithDepNode;
+use rustc_query_system::dep_graph::DepNodeIndex;
+use rustc_session::Limit;
+/// The trait solver cache used by `-Ztrait-solver=next`.
+///
+/// FIXME(@lcnr): link to some official documentation of how
+/// this works.
+#[derive(Default)]
+pub struct EvaluationCache<'tcx> {
+    map: Lock<FxHashMap<CanonicalInput<'tcx>, CacheEntry<'tcx>>>,
+}
+
+pub struct CacheData<'tcx> {
+    pub result: QueryResult<'tcx>,
+    pub reached_depth: usize,
+    pub encountered_overflow: bool,
+}
+
+impl<'tcx> EvaluationCache<'tcx> {
+    /// Insert a final result into the global cache.
+    pub fn insert(
+        &self,
+        key: CanonicalInput<'tcx>,
+        reached_depth: usize,
+        did_overflow: bool,
+        cycle_participants: FxHashSet<CanonicalInput<'tcx>>,
+        dep_node: DepNodeIndex,
+        result: QueryResult<'tcx>,
+    ) {
+        let mut map = self.map.borrow_mut();
+        let entry = map.entry(key).or_default();
+        let data = WithDepNode::new(dep_node, result);
+        entry.cycle_participants.extend(cycle_participants);
+        if did_overflow {
+            entry.with_overflow.insert(reached_depth, data);
+        } else {
+            entry.success = Some(Success { data, reached_depth });
+        }
+    }
+
+    /// Try to fetch a cached result, checking the recursion limit
+    /// and handling root goals of coinductive cycles.
+    ///
+    /// If this returns `Some` the cache result can be used.
+    pub fn get(
+        &self,
+        tcx: TyCtxt<'tcx>,
+        key: CanonicalInput<'tcx>,
+        cycle_participant_in_stack: impl FnOnce(&FxHashSet<CanonicalInput<'tcx>>) -> bool,
+        available_depth: Limit,
+    ) -> Option<CacheData<'tcx>> {
+        let map = self.map.borrow();
+        let entry = map.get(&key)?;
+
+        if cycle_participant_in_stack(&entry.cycle_participants) {
+            return None;
+        }
+
+        if let Some(ref success) = entry.success {
+            if available_depth.value_within_limit(success.reached_depth) {
+                return Some(CacheData {
+                    result: success.data.get(tcx),
+                    reached_depth: success.reached_depth,
+                    encountered_overflow: false,
+                });
+            }
+        }
+
+        entry.with_overflow.get(&available_depth.0).map(|e| CacheData {
+            result: e.get(tcx),
+            reached_depth: available_depth.0,
+            encountered_overflow: true,
+        })
+    }
+}
+
+struct Success<'tcx> {
+    data: WithDepNode<QueryResult<'tcx>>,
+    reached_depth: usize,
+}
+
+/// The cache entry for a goal `CanonicalInput`.
+///
+/// This contains results whose computation never hit the
+/// recursion limit in `success`, and all results which hit
+/// the recursion limit in `with_overflow`.
+#[derive(Default)]
+struct CacheEntry<'tcx> {
+    success: Option<Success<'tcx>>,
+    /// We have to be careful when caching roots of cycles.
+    ///
+    /// See the doc comment of `StackEntry::cycle_participants` for more
+    /// details.
+    cycle_participants: FxHashSet<CanonicalInput<'tcx>>,
+    with_overflow: FxHashMap<usize, WithDepNode<QueryResult<'tcx>>>,
+}
diff --git a/compiler/rustc_middle/src/traits/solve/inspect.rs b/compiler/rustc_middle/src/traits/solve/inspect.rs
index 527afa005..4e2af3816 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect.rs
@@ -32,7 +32,7 @@ pub enum GoalEvaluationKind<'tcx> {
 }
 impl Debug for GoalEvaluation<'_> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        ProofTreeFormatter { f, on_newline: true }.format_goal_evaluation(self)
+        ProofTreeFormatter::new(f).format_goal_evaluation(self)
     }
 }
 
@@ -43,7 +43,7 @@ pub struct AddedGoalsEvaluation<'tcx> {
 }
 impl Debug for AddedGoalsEvaluation<'_> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        ProofTreeFormatter { f, on_newline: true }.format_nested_goal_evaluation(self)
+        ProofTreeFormatter::new(f).format_nested_goal_evaluation(self)
     }
 }
 
@@ -58,7 +58,7 @@ pub struct GoalEvaluationStep<'tcx> {
 }
 impl Debug for GoalEvaluationStep<'_> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        ProofTreeFormatter { f, on_newline: true }.format_evaluation_step(self)
+        ProofTreeFormatter::new(f).format_evaluation_step(self)
     }
 }
 
@@ -75,9 +75,16 @@ pub enum CandidateKind<'tcx> {
     NormalizedSelfTyAssembly,
     /// A normal candidate for proving a goal
     Candidate { name: String, result: QueryResult<'tcx> },
+    /// Used in the probe that wraps normalizing the non-self type for the unsize
+    /// trait, which is also structurally matched on.
+    UnsizeAssembly,
+    /// During upcasting from some source object to target object type, used to
+    /// do a probe to find out what projection type(s) may be used to prove that
+    /// the source type upholds all of the target type's object bounds.
+    UpcastProbe,
 }
 impl Debug for GoalCandidate<'_> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        ProofTreeFormatter { f, on_newline: true }.format_candidate(self)
+        ProofTreeFormatter::new(f).format_candidate(self)
     }
 }
diff --git a/compiler/rustc_middle/src/traits/solve/inspect/format.rs b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
index 2ee625674..8759fecb0 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect/format.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
@@ -1,17 +1,25 @@
 use super::*;
 
 pub(super) struct ProofTreeFormatter<'a, 'b> {
-    pub(super) f: &'a mut (dyn Write + 'b),
-    pub(super) on_newline: bool,
+    f: &'a mut (dyn Write + 'b),
 }
 
-impl Write for ProofTreeFormatter<'_, '_> {
+/// A formatter which adds 4 spaces of indentation to its input before
+/// passing it on to its nested formatter.
+///
+/// We can use this for arbitrary levels of indentation by nesting it.
+struct Indentor<'a, 'b> {
+    f: &'a mut (dyn Write + 'b),
+    on_newline: bool,
+}
+
+impl Write for Indentor<'_, '_> {
     fn write_str(&mut self, s: &str) -> std::fmt::Result {
-        for line in s.split_inclusive("\n") {
+        for line in s.split_inclusive('\n') {
             if self.on_newline {
                 self.f.write_str("    ")?;
             }
-            self.on_newline = line.ends_with("\n");
+            self.on_newline = line.ends_with('\n');
             self.f.write_str(line)?;
         }
 
@@ -19,49 +27,52 @@ impl Write for ProofTreeFormatter<'_, '_> {
     }
 }
 
-impl ProofTreeFormatter<'_, '_> {
-    fn nested(&mut self) -> ProofTreeFormatter<'_, '_> {
-        ProofTreeFormatter { f: self, on_newline: true }
+impl<'a, 'b> ProofTreeFormatter<'a, 'b> {
+    pub(super) fn new(f: &'a mut (dyn Write + 'b)) -> Self {
+        ProofTreeFormatter { f }
     }
 
-    pub(super) fn format_goal_evaluation(&mut self, goal: &GoalEvaluation<'_>) -> std::fmt::Result {
-        let f = &mut *self.f;
+    fn nested<F, R>(&mut self, func: F) -> R
+    where
+        F: FnOnce(&mut ProofTreeFormatter<'_, '_>) -> R,
+    {
+        func(&mut ProofTreeFormatter { f: &mut Indentor { f: self.f, on_newline: true } })
+    }
 
+    pub(super) fn format_goal_evaluation(&mut self, goal: &GoalEvaluation<'_>) -> std::fmt::Result {
         let goal_text = match goal.is_normalizes_to_hack {
             IsNormalizesToHack::Yes => "NORMALIZES-TO HACK GOAL",
             IsNormalizesToHack::No => "GOAL",
         };
 
-        writeln!(f, "{}: {:?}", goal_text, goal.uncanonicalized_goal,)?;
-        writeln!(f, "CANONICALIZED: {:?}", goal.canonicalized_goal)?;
+        writeln!(self.f, "{}: {:?}", goal_text, goal.uncanonicalized_goal)?;
+        writeln!(self.f, "CANONICALIZED: {:?}", goal.canonicalized_goal)?;
 
         match &goal.kind {
             GoalEvaluationKind::CacheHit(CacheHit::Global) => {
-                writeln!(f, "GLOBAL CACHE HIT: {:?}", goal.result)
+                writeln!(self.f, "GLOBAL CACHE HIT: {:?}", goal.result)
             }
             GoalEvaluationKind::CacheHit(CacheHit::Provisional) => {
-                writeln!(f, "PROVISIONAL CACHE HIT: {:?}", goal.result)
+                writeln!(self.f, "PROVISIONAL CACHE HIT: {:?}", goal.result)
             }
             GoalEvaluationKind::Uncached { revisions } => {
                 for (n, step) in revisions.iter().enumerate() {
-                    let f = &mut *self.f;
-                    writeln!(f, "REVISION {n}: {:?}", step.result)?;
-                    let mut f = self.nested();
-                    f.format_evaluation_step(step)?;
+                    writeln!(self.f, "REVISION {n}: {:?}", step.result)?;
+                    self.nested(|this| this.format_evaluation_step(step))?;
                 }
-
-                let f = &mut *self.f;
-                writeln!(f, "RESULT: {:?}", goal.result)
+                writeln!(self.f, "RESULT: {:?}", goal.result)
             }
         }?;
 
         if goal.returned_goals.len() > 0 {
-            let f = &mut *self.f;
-            writeln!(f, "NESTED GOALS ADDED TO CALLER: [")?;
-            let mut f = self.nested();
-            for goal in goal.returned_goals.iter() {
-                writeln!(f, "ADDED GOAL: {:?},", goal)?;
-            }
+            writeln!(self.f, "NESTED GOALS ADDED TO CALLER: [")?;
+            self.nested(|this| {
+                for goal in goal.returned_goals.iter() {
+                    writeln!(this.f, "ADDED GOAL: {goal:?},")?;
+                }
+                Ok(())
+            })?;
+
             writeln!(self.f, "]")?;
         }
 
@@ -72,58 +83,59 @@ impl ProofTreeFormatter<'_, '_> {
         &mut self,
         evaluation_step: &GoalEvaluationStep<'_>,
     ) -> std::fmt::Result {
-        let f = &mut *self.f;
-        writeln!(f, "INSTANTIATED: {:?}", evaluation_step.instantiated_goal)?;
+        writeln!(self.f, "INSTANTIATED: {:?}", evaluation_step.instantiated_goal)?;
 
         for candidate in &evaluation_step.candidates {
-            let mut f = self.nested();
-            f.format_candidate(candidate)?;
+            self.nested(|this| this.format_candidate(candidate))?;
         }
-        for nested_goal_evaluation in &evaluation_step.nested_goal_evaluations {
-            let mut f = self.nested();
-            f.format_nested_goal_evaluation(nested_goal_evaluation)?;
+        for nested in &evaluation_step.nested_goal_evaluations {
+            self.nested(|this| this.format_nested_goal_evaluation(nested))?;
         }
 
         Ok(())
     }
 
     pub(super) fn format_candidate(&mut self, candidate: &GoalCandidate<'_>) -> std::fmt::Result {
-        let f = &mut *self.f;
-
         match &candidate.kind {
             CandidateKind::NormalizedSelfTyAssembly => {
-                writeln!(f, "NORMALIZING SELF TY FOR ASSEMBLY:")
+                writeln!(self.f, "NORMALIZING SELF TY FOR ASSEMBLY:")
+            }
+            CandidateKind::UnsizeAssembly => {
+                writeln!(self.f, "ASSEMBLING CANDIDATES FOR UNSIZING:")
+            }
+            CandidateKind::UpcastProbe => {
+                writeln!(self.f, "PROBING FOR PROJECTION COMPATIBILITY FOR UPCASTING:")
             }
             CandidateKind::Candidate { name, result } => {
-                writeln!(f, "CANDIDATE {}: {:?}", name, result)
+                writeln!(self.f, "CANDIDATE {name}: {result:?}")
             }
         }?;
 
-        let mut f = self.nested();
-        for candidate in &candidate.candidates {
-            f.format_candidate(candidate)?;
-        }
-        for nested_evaluations in &candidate.nested_goal_evaluations {
-            f.format_nested_goal_evaluation(nested_evaluations)?;
-        }
-
-        Ok(())
+        self.nested(|this| {
+            for candidate in &candidate.candidates {
+                this.format_candidate(candidate)?;
+            }
+            for nested in &candidate.nested_goal_evaluations {
+                this.format_nested_goal_evaluation(nested)?;
+            }
+            Ok(())
+        })
     }
 
     pub(super) fn format_nested_goal_evaluation(
         &mut self,
         nested_goal_evaluation: &AddedGoalsEvaluation<'_>,
     ) -> std::fmt::Result {
-        let f = &mut *self.f;
-        writeln!(f, "TRY_EVALUATE_ADDED_GOALS: {:?}", nested_goal_evaluation.result)?;
+        writeln!(self.f, "TRY_EVALUATE_ADDED_GOALS: {:?}", nested_goal_evaluation.result)?;
 
         for (n, revision) in nested_goal_evaluation.evaluations.iter().enumerate() {
-            let f = &mut *self.f;
-            writeln!(f, "REVISION {n}")?;
-            let mut f = self.nested();
-            for goal_evaluation in revision {
-                f.format_goal_evaluation(goal_evaluation)?;
-            }
+            writeln!(self.f, "REVISION {n}")?;
+            self.nested(|this| {
+                for goal_evaluation in revision {
+                    this.format_goal_evaluation(goal_evaluation)?;
+                }
+                Ok(())
+            })?;
         }
 
         Ok(())