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