src/librustc/traits/chalk_fulfill.rs

   1 use crate::infer::canonical::{Canonical, OriginalQueryValues};
   2 use crate::infer::InferCtxt;
   3 use crate::traits::query::NoSolution;
   4 use crate::traits::{
   5     Environment, FulfillmentError, FulfillmentErrorCode, InEnvironment, ObligationCause,
   6     PredicateObligation, SelectionError, TraitEngine,
   7 };
   8 use crate::ty::{self, Ty};
   9 use rustc_data_structures::fx::FxHashSet;
  10
  11 pub type CanonicalGoal<'tcx> = Canonical<'tcx, InEnvironment<'tcx, ty::Predicate<'tcx>>>;
  12
  13 pub struct FulfillmentContext<'tcx> {
  14     obligations: FxHashSet<InEnvironment<'tcx, PredicateObligation<'tcx>>>,
  15 }
  16
  17 impl FulfillmentContext<'tcx> {
  18     crate fn new() -> Self {
  19         FulfillmentContext { obligations: FxHashSet::default() }
  20     }
  21 }
  22
  23 fn in_environment(
  24     infcx: &InferCtxt<'_, 'tcx>,
  25     obligation: PredicateObligation<'tcx>,
  26 ) -> InEnvironment<'tcx, PredicateObligation<'tcx>> {
  27     assert!(!infcx.is_in_snapshot());
  28     let obligation = infcx.resolve_vars_if_possible(&obligation);
  29
  30     let environment = match obligation.param_env.def_id {
  31         Some(def_id) => infcx.tcx.environment(def_id),
  32         None if obligation.param_env.caller_bounds.is_empty() => {
  33             Environment { clauses: ty::List::empty() }
  34         }
  35         _ => bug!("non-empty `ParamEnv` with no def-id"),
  36     };
  37
  38     InEnvironment { environment, goal: obligation }
  39 }
  40
  41 impl TraitEngine<'tcx> for FulfillmentContext<'tcx> {
  42     fn normalize_projection_type(
  43         &mut self,
  44         infcx: &InferCtxt<'_, 'tcx>,
  45         _param_env: ty::ParamEnv<'tcx>,
  46         projection_ty: ty::ProjectionTy<'tcx>,
  47         _cause: ObligationCause<'tcx>,
  48     ) -> Ty<'tcx> {
  49         infcx.tcx.mk_ty(ty::Projection(projection_ty))
  50     }
  51
  52     fn register_predicate_obligation(
  53         &mut self,
  54         infcx: &InferCtxt<'_, 'tcx>,
  55         obligation: PredicateObligation<'tcx>,
  56     ) {
  57         self.obligations.insert(in_environment(infcx, obligation));
  58     }
  59
  60     fn select_all_or_error(
  61         &mut self,
  62         infcx: &InferCtxt<'_, 'tcx>,
  63     ) -> Result<(), Vec<FulfillmentError<'tcx>>> {
  64         self.select_where_possible(infcx)?;
  65
  66         if self.obligations.is_empty() {
  67             Ok(())
  68         } else {
  69             let errors = self
  70                 .obligations
  71                 .iter()
  72                 .map(|obligation| FulfillmentError {
  73                     obligation: obligation.goal.clone(),
  74                     code: FulfillmentErrorCode::CodeAmbiguity,
  75                     points_at_arg_span: false,
  76                 })
  77                 .collect();
  78             Err(errors)
  79         }
  80     }
  81
  82     fn select_where_possible(
  83         &mut self,
  84         infcx: &InferCtxt<'_, 'tcx>,
  85     ) -> Result<(), Vec<FulfillmentError<'tcx>>> {
  86         let mut errors = Vec::new();
  87         let mut next_round = FxHashSet::default();
  88         let mut making_progress;
  89
  90         loop {
  91             making_progress = false;
  92
  93             // We iterate over all obligations, and record if we are able
  94             // to unambiguously prove at least one obligation.
  95             for obligation in self.obligations.drain() {
  96                 let mut orig_values = OriginalQueryValues::default();
  97                 let canonical_goal = infcx.canonicalize_query(
  98                     &InEnvironment {
  99                         environment: obligation.environment,
 100                         goal: obligation.goal.predicate,
 101                     },
 102                     &mut orig_values,
 103                 );
 104
 105                 match infcx.tcx.evaluate_goal(canonical_goal) {
 106                     Ok(response) => {
 107                         if response.is_proven() {
 108                             making_progress = true;
 109
 110                             match infcx.instantiate_query_response_and_region_obligations(
 111                                 &obligation.goal.cause,
 112                                 obligation.goal.param_env,
 113                                 &orig_values,
 114                                 &response,
 115                             ) {
 116                                 Ok(infer_ok) => next_round.extend(
 117                                     infer_ok
 118                                         .obligations
 119                                         .into_iter()
 120                                         .map(|obligation| in_environment(infcx, obligation)),
 121                                 ),
 122
 123                                 Err(_err) => errors.push(FulfillmentError {
 124                                     obligation: obligation.goal,
 125                                     code: FulfillmentErrorCode::CodeSelectionError(
 126                                         SelectionError::Unimplemented,
 127                                     ),
 128                                     points_at_arg_span: false,
 129                                 }),
 130                             }
 131                         } else {
 132                             // Ambiguous: retry at next round.
 133                             next_round.insert(obligation);
 134                         }
 135                     }
 136
 137                     Err(NoSolution) => errors.push(FulfillmentError {
 138                         obligation: obligation.goal,
 139                         code: FulfillmentErrorCode::CodeSelectionError(
 140                             SelectionError::Unimplemented,
 141                         ),
 142                         points_at_arg_span: false,
 143                     }),
 144                 }
 145             }
 146             next_round = std::mem::replace(&mut self.obligations, next_round);
 147
 148             if !making_progress {
 149                 break;
 150             }
 151         }
 152
 153         if errors.is_empty() { Ok(()) } else { Err(errors) }
 154     }
 155
 156     fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> {
 157         self.obligations.iter().map(|obligation| obligation.goal.clone()).collect()
 158     }
 159 }