compiler/rustc_trait_selection/src/solve/overflow.rs

   1 use rustc_infer::infer::canonical::Canonical;
   2 use rustc_infer::traits::query::NoSolution;
   3 use rustc_middle::ty::TyCtxt;
   4 use rustc_session::Limit;
   5
   6 use super::cache::response_no_constraints;
   7 use super::{Certainty, EvalCtxt, MaybeCause, QueryResult};
   8
   9 /// When detecting a solver overflow, we return ambiguity. Overflow can be
  10 /// *hidden* by either a fatal error in an **AND** or a trivial success in an **OR**.
  11 ///
  12 /// This is in issue in case of exponential blowup, e.g. if each goal on the stack
  13 /// has multiple nested (overflowing) candidates. To deal with this, we reduce the limit
  14 /// used by the solver when hitting the default limit for the first time.
  15 ///
  16 /// FIXME: Get tests where always using the `default_limit` results in a hang and refer
  17 /// to them here. We can also improve the overflow strategy if necessary.
  18 pub(super) struct OverflowData {
  19     default_limit: Limit,
  20     current_limit: Limit,
  21     /// When proving an **AND** we have to repeatedly iterate over the yet unproven goals.
  22     ///
  23     /// Because of this each iteration also increases the depth in addition to the stack
  24     /// depth.
  25     additional_depth: usize,
  26 }
  27
  28 impl OverflowData {
  29     pub(super) fn new(tcx: TyCtxt<'_>) -> OverflowData {
  30         let default_limit = tcx.recursion_limit();
  31         OverflowData { default_limit, current_limit: default_limit, additional_depth: 0 }
  32     }
  33
  34     #[inline]
  35     pub(super) fn did_overflow(&self) -> bool {
  36         self.default_limit.0 != self.current_limit.0
  37     }
  38
  39     #[inline]
  40     pub(super) fn has_overflow(&self, depth: usize) -> bool {
  41         !self.current_limit.value_within_limit(depth + self.additional_depth)
  42     }
  43
  44     /// Updating the current limit when hitting overflow.
  45     fn deal_with_overflow(&mut self) {
  46         // When first hitting overflow we reduce the overflow limit
  47         // for all future goals to prevent hangs if there's an exponental
  48         // blowup.
  49         self.current_limit.0 = self.default_limit.0 / 8;
  50     }
  51 }
  52
  53 impl<'tcx> EvalCtxt<'tcx> {
  54     pub(super) fn deal_with_overflow(
  55         &mut self,
  56         goal: Canonical<'tcx, impl Sized>,
  57     ) -> QueryResult<'tcx> {
  58         self.overflow_data.deal_with_overflow();
  59         response_no_constraints(self.tcx, goal, Certainty::Maybe(MaybeCause::Overflow))
  60     }
  61
  62     /// A `while`-loop which tracks overflow.
  63     pub(super) fn repeat_while_none(
  64         &mut self,
  65         mut loop_body: impl FnMut(&mut Self) -> Option<Result<Certainty, NoSolution>>,
  66     ) -> Result<Certainty, NoSolution> {
  67         let start_depth = self.overflow_data.additional_depth;
  68         let depth = self.provisional_cache.current_depth();
  69         while !self.overflow_data.has_overflow(depth) {
  70             if let Some(result) = loop_body(self) {
  71                 self.overflow_data.additional_depth = start_depth;
  72                 return result;
  73             }
  74
  75             self.overflow_data.additional_depth += 1;
  76         }
  77         self.overflow_data.additional_depth = start_depth;
  78         self.overflow_data.deal_with_overflow();
  79         Ok(Certainty::Maybe(MaybeCause::Overflow))
  80     }
  81 }