compiler/rustc_trait_selection/src/solve/fulfill.rs

   1 use std::mem;
   2
   3 use rustc_data_structures::fx::FxHashMap;
   4 use rustc_infer::{
   5     infer::{canonical::OriginalQueryValues, InferCtxt},
   6     traits::{
   7         query::NoSolution, FulfillmentError, FulfillmentErrorCode, PredicateObligation,
   8         SelectionError, TraitEngine,
   9     },
  10 };
  11 use rustc_middle::ty;
  12
  13 use super::{Certainty, EvalCtxt};
  14
  15 /// A trait engine using the new trait solver.
  16 ///
  17 /// This is mostly identical to how `evaluate_all` works inside of the
  18 /// solver, except that the requirements are slightly different.
  19 ///
  20 /// Unlike `evaluate_all` it is possible to add new obligations later on
  21 /// and we also have to track diagnostics information by using `Obligation`
  22 /// instead of `Goal`.
  23 ///
  24 /// It is also likely that we want to use slightly different datastructures
  25 /// here as this will have to deal with far more root goals than `evaluate_all`.
  26 pub struct FulfillmentCtxt<'tcx> {
  27     obligations: Vec<PredicateObligation<'tcx>>,
  28 }
  29
  30 impl<'tcx> FulfillmentCtxt<'tcx> {
  31     pub fn new() -> FulfillmentCtxt<'tcx> {
  32         FulfillmentCtxt { obligations: Vec::new() }
  33     }
  34 }
  35
  36 impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
  37     fn register_predicate_obligation(
  38         &mut self,
  39         _infcx: &InferCtxt<'tcx>,
  40         obligation: PredicateObligation<'tcx>,
  41     ) {
  42         self.obligations.push(obligation);
  43     }
  44
  45     fn select_all_or_error(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> {
  46         let errors = self.select_where_possible(infcx);
  47         if !errors.is_empty() {
  48             return errors;
  49         }
  50
  51         self.obligations
  52             .drain(..)
  53             .map(|obligation| FulfillmentError {
  54                 obligation: obligation.clone(),
  55                 code: FulfillmentErrorCode::CodeSelectionError(SelectionError::Unimplemented),
  56                 root_obligation: obligation,
  57             })
  58             .collect()
  59     }
  60
  61     fn select_where_possible(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> {
  62         let mut errors = Vec::new();
  63         for i in 0.. {
  64             if !infcx.tcx.recursion_limit().value_within_limit(i) {
  65                 unimplemented!("overflowed on pending obligations: {:?}", self.obligations);
  66             }
  67
  68             let mut has_changed = false;
  69             for obligation in mem::take(&mut self.obligations) {
  70                 let goal = obligation.clone().into();
  71
  72                 // FIXME: Add a better API for that '^^
  73                 let mut orig_values = OriginalQueryValues::default();
  74                 let canonical_goal = infcx.canonicalize_query(goal, &mut orig_values);
  75                 let (changed, certainty) = match EvalCtxt::evaluate_canonical_goal(
  76                     infcx.tcx,
  77                     &mut super::search_graph::SearchGraph::new(infcx.tcx),
  78                     canonical_goal,
  79                 ) {
  80                     Ok(canonical_response) => {
  81                         (
  82                             true, // FIXME: check whether `var_values` are an identity substitution.
  83                             super::instantiate_canonical_query_response(
  84                                 infcx,
  85                                 &orig_values,
  86                                 canonical_response,
  87                             ),
  88                         )
  89                     }
  90                     Err(NoSolution) => {
  91                         errors.push(FulfillmentError {
  92                             obligation: obligation.clone(),
  93                             code: FulfillmentErrorCode::CodeAmbiguity,
  94                             root_obligation: obligation,
  95                         });
  96                         continue;
  97                     }
  98                 };
  99
 100                 has_changed |= changed;
 101                 match certainty {
 102                     Certainty::Yes => {}
 103                     Certainty::Maybe(_) => self.obligations.push(obligation),
 104                 }
 105             }
 106
 107             if !has_changed {
 108                 break;
 109             }
 110         }
 111
 112         errors
 113     }
 114
 115     fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> {
 116         self.obligations.clone()
 117     }
 118
 119     fn relationships(&mut self) -> &mut FxHashMap<ty::TyVid, ty::FoundRelationships> {
 120         unimplemented!("Should be moved out of `TraitEngine`")
 121     }
 122 }