compiler/rustc_trait_selection/src/traits/chalk_fulfill.rs

   1 //! Defines a Chalk-based `TraitEngine`
   2
   3 use crate::infer::canonical::OriginalQueryValues;
   4 use crate::infer::InferCtxt;
   5 use crate::traits::query::NoSolution;
   6 use crate::traits::{
   7     ChalkEnvironmentAndGoal, FulfillmentError, FulfillmentErrorCode, ObligationCause,
   8     PredicateObligation, SelectionError, TraitEngine,
   9 };
  10 use rustc_data_structures::fx::{FxHashMap, FxIndexSet};
  11 use rustc_middle::ty::{self, Ty, TypeFoldable};
  12
  13 pub struct FulfillmentContext<'tcx> {
  14     obligations: FxIndexSet<PredicateObligation<'tcx>>,
  15
  16     relationships: FxHashMap<ty::TyVid, ty::FoundRelationships>,
  17 }
  18
  19 impl FulfillmentContext<'_> {
  20     pub(crate) fn new() -> Self {
  21         FulfillmentContext {
  22             obligations: FxIndexSet::default(),
  23             relationships: FxHashMap::default(),
  24         }
  25     }
  26 }
  27
  28 impl<'tcx> TraitEngine<'tcx> for FulfillmentContext<'tcx> {
  29     fn normalize_projection_type(
  30         &mut self,
  31         infcx: &InferCtxt<'_, 'tcx>,
  32         _param_env: ty::ParamEnv<'tcx>,
  33         projection_ty: ty::ProjectionTy<'tcx>,
  34         _cause: ObligationCause<'tcx>,
  35     ) -> Ty<'tcx> {
  36         infcx.tcx.mk_ty(ty::Projection(projection_ty))
  37     }
  38
  39     fn register_predicate_obligation(
  40         &mut self,
  41         infcx: &InferCtxt<'_, 'tcx>,
  42         obligation: PredicateObligation<'tcx>,
  43     ) {
  44         assert!(!infcx.is_in_snapshot());
  45         let obligation = infcx.resolve_vars_if_possible(obligation);
  46
  47         super::relationships::update(self, infcx, &obligation);
  48
  49         self.obligations.insert(obligation);
  50     }
  51
  52     fn select_all_or_error(&mut self, infcx: &InferCtxt<'_, 'tcx>) -> Vec<FulfillmentError<'tcx>> {
  53         {
  54             let errors = self.select_where_possible(infcx);
  55
  56             if !errors.is_empty() {
  57                 return errors;
  58             }
  59         }
  60
  61         // any remaining obligations are errors
  62         self.obligations
  63             .iter()
  64             .map(|obligation| FulfillmentError {
  65                 obligation: obligation.clone(),
  66                 code: FulfillmentErrorCode::CodeAmbiguity,
  67                 // FIXME - does Chalk have a notation of 'root obligation'?
  68                 // This is just for diagnostics, so it's okay if this is wrong
  69                 root_obligation: obligation.clone(),
  70             })
  71             .collect()
  72     }
  73
  74     fn select_where_possible(
  75         &mut self,
  76         infcx: &InferCtxt<'_, 'tcx>,
  77     ) -> Vec<FulfillmentError<'tcx>> {
  78         assert!(!infcx.is_in_snapshot());
  79
  80         let mut errors = Vec::new();
  81         let mut next_round = FxIndexSet::default();
  82         let mut making_progress;
  83
  84         loop {
  85             making_progress = false;
  86
  87             // We iterate over all obligations, and record if we are able
  88             // to unambiguously prove at least one obligation.
  89             for obligation in self.obligations.drain(..) {
  90                 let obligation = infcx.resolve_vars_if_possible(obligation);
  91                 let environment = obligation.param_env.caller_bounds();
  92                 let goal = ChalkEnvironmentAndGoal { environment, goal: obligation.predicate };
  93                 let mut orig_values = OriginalQueryValues::default();
  94                 if goal.references_error() {
  95                     continue;
  96                 }
  97
  98                 let canonical_goal =
  99                     infcx.canonicalize_query_preserving_universes(goal, &mut orig_values);
 100
 101                 match infcx.tcx.evaluate_goal(canonical_goal) {
 102                     Ok(response) => {
 103                         if response.is_proven() {
 104                             making_progress = true;
 105
 106                             match infcx.instantiate_query_response_and_region_obligations(
 107                                 &obligation.cause,
 108                                 obligation.param_env,
 109                                 &orig_values,
 110                                 &response,
 111                             ) {
 112                                 Ok(infer_ok) => next_round.extend(
 113                                     infer_ok.obligations.into_iter().map(|obligation| {
 114                                         assert!(!infcx.is_in_snapshot());
 115                                         infcx.resolve_vars_if_possible(obligation)
 116                                     }),
 117                                 ),
 118
 119                                 Err(_err) => errors.push(FulfillmentError {
 120                                     obligation: obligation.clone(),
 121                                     code: FulfillmentErrorCode::CodeSelectionError(
 122                                         SelectionError::Unimplemented,
 123                                     ),
 124                                     // FIXME - does Chalk have a notation of 'root obligation'?
 125                                     // This is just for diagnostics, so it's okay if this is wrong
 126                                     root_obligation: obligation,
 127                                 }),
 128                             }
 129                         } else {
 130                             // Ambiguous: retry at next round.
 131                             next_round.insert(obligation);
 132                         }
 133                     }
 134
 135                     Err(NoSolution) => errors.push(FulfillmentError {
 136                         obligation: obligation.clone(),
 137                         code: FulfillmentErrorCode::CodeSelectionError(
 138                             SelectionError::Unimplemented,
 139                         ),
 140                         // FIXME - does Chalk have a notation of 'root obligation'?
 141                         // This is just for diagnostics, so it's okay if this is wrong
 142                         root_obligation: obligation,
 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         errors
 154     }
 155
 156     fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> {
 157         self.obligations.iter().cloned().collect()
 158     }
 159
 160     fn relationships(&mut self) -> &mut FxHashMap<ty::TyVid, ty::FoundRelationships> {
 161         &mut self.relationships
 162     }
 163 }