src/librustc/traits/chalk_fulfill.rs

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