compiler/rustc_trait_selection/src/solve/overflow.rs

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