compiler/rustc_trait_selection/src/solve/search_graph/mod.rs

   1 mod cache;
   2 mod overflow;
   3
   4 use self::cache::ProvisionalEntry;
   5 use super::{CanonicalGoal, Certainty, MaybeCause, QueryResult};
   6 use cache::ProvisionalCache;
   7 use overflow::OverflowData;
   8 use rustc_index::vec::IndexVec;
   9 use rustc_middle::ty::TyCtxt;
  10 use std::collections::hash_map::Entry;
  11
  12 rustc_index::newtype_index! {
  13     pub struct StackDepth {}
  14 }
  15
  16 struct StackElem<'tcx> {
  17     goal: CanonicalGoal<'tcx>,
  18     has_been_used: bool,
  19 }
  20
  21 pub(super) struct SearchGraph<'tcx> {
  22     /// The stack of goals currently being computed.
  23     ///
  24     /// An element is *deeper* in the stack if its index is *lower*.
  25     stack: IndexVec<StackDepth, StackElem<'tcx>>,
  26     overflow_data: OverflowData,
  27     provisional_cache: ProvisionalCache<'tcx>,
  28 }
  29
  30 impl<'tcx> SearchGraph<'tcx> {
  31     pub(super) fn new(tcx: TyCtxt<'tcx>) -> SearchGraph<'tcx> {
  32         Self {
  33             stack: Default::default(),
  34             overflow_data: OverflowData::new(tcx),
  35             provisional_cache: ProvisionalCache::empty(),
  36         }
  37     }
  38
  39     pub(super) fn is_empty(&self) -> bool {
  40         self.stack.is_empty()
  41             && self.provisional_cache.is_empty()
  42             && !self.overflow_data.did_overflow()
  43     }
  44
  45     /// Tries putting the new goal on the stack, returning an error if it is already cached.
  46     ///
  47     /// This correctly updates the provisional cache if there is a cycle.
  48     #[instrument(level = "debug", skip(self, tcx), ret)]
  49     pub(super) fn try_push_stack(
  50         &mut self,
  51         tcx: TyCtxt<'tcx>,
  52         goal: CanonicalGoal<'tcx>,
  53     ) -> Result<(), QueryResult<'tcx>> {
  54         // FIXME: start by checking the global cache
  55
  56         // Look at the provisional cache to check for cycles.
  57         let cache = &mut self.provisional_cache;
  58         match cache.lookup_table.entry(goal) {
  59             // No entry, simply push this goal on the stack after dealing with overflow.
  60             Entry::Vacant(v) => {
  61                 if self.overflow_data.has_overflow(self.stack.len()) {
  62                     return Err(self.deal_with_overflow(tcx, goal));
  63                 }
  64
  65                 let depth = self.stack.push(StackElem { goal, has_been_used: false });
  66                 let response = super::response_no_constraints(tcx, goal, Certainty::Yes);
  67                 let entry_index = cache.entries.push(ProvisionalEntry { response, depth, goal });
  68                 v.insert(entry_index);
  69                 Ok(())
  70             }
  71             // We have a nested goal which relies on a goal `root` deeper in the stack.
  72             //
  73             // We first store that we may have to rerun `evaluate_goal` for `root` in case the
  74             // provisional response is not equal to the final response. We also update the depth
  75             // of all goals which recursively depend on our current goal to depend on `root`
  76             // instead.
  77             //
  78             // Finally we can return either the provisional response for that goal if we have a
  79             // coinductive cycle or an ambiguous result if the cycle is inductive.
  80             Entry::Occupied(entry_index) => {
  81                 let entry_index = *entry_index.get();
  82
  83                 let stack_depth = cache.depth(entry_index);
  84                 debug!("encountered cycle with depth {stack_depth:?}");
  85
  86                 cache.add_dependency_of_leaf_on(entry_index);
  87
  88                 self.stack[stack_depth].has_been_used = true;
  89                 // NOTE: The goals on the stack aren't the only goals involved in this cycle.
  90                 // We can also depend on goals which aren't part of the stack but coinductively
  91                 // depend on the stack themselves. We already checked whether all the goals
  92                 // between these goals and their root on the stack. This means that as long as
  93                 // each goal in a cycle is checked for coinductivity by itself, simply checking
  94                 // the stack is enough.
  95                 if self.stack.raw[stack_depth.index()..]
  96                     .iter()
  97                     .all(|g| g.goal.value.predicate.is_coinductive(tcx))
  98                 {
  99                     Err(cache.provisional_result(entry_index))
 100                 } else {
 101                     Err(super::response_no_constraints(
 102                         tcx,
 103                         goal,
 104                         Certainty::Maybe(MaybeCause::Overflow),
 105                     ))
 106                 }
 107             }
 108         }
 109     }
 110
 111     /// We cannot simply store the result of [super::EvalCtxt::compute_goal] as we have to deal with
 112     /// coinductive cycles.
 113     ///
 114     /// When we encounter a coinductive cycle, we have to prove the final result of that cycle
 115     /// while we are still computing that result. Because of this we continously recompute the
 116     /// cycle until the result of the previous iteration is equal to the final result, at which
 117     /// point we are done.
 118     ///
 119     /// This function returns `true` if we were able to finalize the goal and `false` if it has
 120     /// updated the provisional cache and we have to recompute the current goal.
 121     ///
 122     /// FIXME: Refer to the rustc-dev-guide entry once it exists.
 123     #[instrument(level = "debug", skip(self, tcx, actual_goal), ret)]
 124     pub(super) fn try_finalize_goal(
 125         &mut self,
 126         tcx: TyCtxt<'tcx>,
 127         actual_goal: CanonicalGoal<'tcx>,
 128         response: QueryResult<'tcx>,
 129     ) -> bool {
 130         let StackElem { goal, has_been_used } = self.stack.pop().unwrap();
 131         assert_eq!(goal, actual_goal);
 132
 133         let cache = &mut self.provisional_cache;
 134         let provisional_entry_index = *cache.lookup_table.get(&goal).unwrap();
 135         let provisional_entry = &mut cache.entries[provisional_entry_index];
 136         let depth = provisional_entry.depth;
 137         // Was the current goal the root of a cycle and was the provisional response
 138         // different from the final one.
 139         if has_been_used && provisional_entry.response != response {
 140             // If so, update the provisional reponse for this goal...
 141             provisional_entry.response = response;
 142             // ...remove all entries whose result depends on this goal
 143             // from the provisional cache...
 144             //
 145             // That's not completely correct, as a nested goal can also
 146             // depend on a goal which is lower in the stack so it doesn't
 147             // actually depend on the current goal. This should be fairly
 148             // rare and is hopefully not relevant for performance.
 149             #[allow(rustc::potential_query_instability)]
 150             cache.lookup_table.retain(|_key, index| *index <= provisional_entry_index);
 151             cache.entries.truncate(provisional_entry_index.index() + 1);
 152
 153             // ...and finally push our goal back on the stack and reevaluate it.
 154             self.stack.push(StackElem { goal, has_been_used: false });
 155             false
 156         } else {
 157             // If not, we're done with this goal.
 158             //
 159             // Check whether that this goal doesn't depend on a goal deeper on the stack
 160             // and if so, move it and all nested goals to the global cache.
 161             //
 162             // Note that if any nested goal were to depend on something deeper on the stack,
 163             // this would have also updated the depth of the current goal.
 164             if depth == self.stack.next_index() {
 165                 for (i, entry) in cache.entries.drain_enumerated(provisional_entry_index.index()..)
 166                 {
 167                     let actual_index = cache.lookup_table.remove(&entry.goal);
 168                     debug_assert_eq!(Some(i), actual_index);
 169                     debug_assert!(entry.depth == depth);
 170                     cache::try_move_finished_goal_to_global_cache(
 171                         tcx,
 172                         &mut self.overflow_data,
 173                         &self.stack,
 174                         entry.goal,
 175                         entry.response,
 176                     );
 177                 }
 178             }
 179             true
 180         }
 181     }
 182 }