src/librustc_trait_selection/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, ChalkEnvironmentClause, FulfillmentError, FulfillmentErrorCode,
   8     ObligationCause, PredicateObligation, SelectionError, TraitEngine,
   9 };
  10 use rustc_data_structures::fx::FxIndexSet;
  11 use rustc_hir::def_id::DefId;
  12 use rustc_middle::ty::{self, Ty, TyCtxt};
  13
  14 pub struct FulfillmentContext<'tcx> {
  15     obligations: FxIndexSet<PredicateObligation<'tcx>>,
  16 }
  17
  18 impl FulfillmentContext<'tcx> {
  19     crate fn new() -> Self {
  20         FulfillmentContext { obligations: FxIndexSet::default() }
  21     }
  22 }
  23
  24 fn environment<'tcx>(
  25     tcx: TyCtxt<'tcx>,
  26     def_id: DefId,
  27 ) -> &'tcx ty::List<ChalkEnvironmentClause<'tcx>> {
  28     use rustc_hir::{ForeignItemKind, ImplItemKind, ItemKind, Node, TraitItemKind};
  29     use rustc_middle::ty::subst::GenericArgKind;
  30
  31     debug!("environment(def_id = {:?})", def_id);
  32
  33     // The environment of an impl Trait type is its defining function's environment.
  34     if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) {
  35         return environment(tcx, parent);
  36     }
  37
  38     // Compute the bounds on `Self` and the type parameters.
  39     let ty::InstantiatedPredicates { predicates, .. } =
  40         tcx.predicates_of(def_id).instantiate_identity(tcx);
  41
  42     let clauses = predicates.into_iter().map(ChalkEnvironmentClause::Predicate);
  43
  44     let hir_id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
  45     let node = tcx.hir().get(hir_id);
  46
  47     enum NodeKind {
  48         TraitImpl,
  49         InherentImpl,
  50         Fn,
  51         Other,
  52     };
  53
  54     let node_kind = match node {
  55         Node::TraitItem(item) => match item.kind {
  56             TraitItemKind::Fn(..) => NodeKind::Fn,
  57             _ => NodeKind::Other,
  58         },
  59
  60         Node::ImplItem(item) => match item.kind {
  61             ImplItemKind::Fn(..) => NodeKind::Fn,
  62             _ => NodeKind::Other,
  63         },
  64
  65         Node::Item(item) => match item.kind {
  66             ItemKind::Impl { of_trait: Some(_), .. } => NodeKind::TraitImpl,
  67             ItemKind::Impl { of_trait: None, .. } => NodeKind::InherentImpl,
  68             ItemKind::Fn(..) => NodeKind::Fn,
  69             _ => NodeKind::Other,
  70         },
  71
  72         Node::ForeignItem(item) => match item.kind {
  73             ForeignItemKind::Fn(..) => NodeKind::Fn,
  74             _ => NodeKind::Other,
  75         },
  76
  77         // FIXME: closures?
  78         _ => NodeKind::Other,
  79     };
  80
  81     // FIXME(eddyb) isn't the unordered nature of this a hazard?
  82     let mut inputs = FxIndexSet::default();
  83
  84     match node_kind {
  85         // In a trait impl, we assume that the header trait ref and all its
  86         // constituents are well-formed.
  87         NodeKind::TraitImpl => {
  88             let trait_ref = tcx.impl_trait_ref(def_id).expect("not an impl");
  89
  90             // FIXME(chalk): this has problems because of late-bound regions
  91             //inputs.extend(trait_ref.substs.iter().flat_map(|arg| arg.walk()));
  92             inputs.extend(trait_ref.substs.iter());
  93         }
  94
  95         // In an inherent impl, we assume that the receiver type and all its
  96         // constituents are well-formed.
  97         NodeKind::InherentImpl => {
  98             let self_ty = tcx.type_of(def_id);
  99             inputs.extend(self_ty.walk());
 100         }
 101
 102         // In an fn, we assume that the arguments and all their constituents are
 103         // well-formed.
 104         NodeKind::Fn => {
 105             let fn_sig = tcx.fn_sig(def_id);
 106             let fn_sig = tcx.liberate_late_bound_regions(def_id, &fn_sig);
 107
 108             inputs.extend(fn_sig.inputs().iter().flat_map(|ty| ty.walk()));
 109         }
 110
 111         NodeKind::Other => (),
 112     }
 113     let input_clauses = inputs.into_iter().filter_map(|arg| {
 114         match arg.unpack() {
 115             GenericArgKind::Type(ty) => Some(ChalkEnvironmentClause::TypeFromEnv(ty)),
 116
 117             // FIXME(eddyb) no WF conditions from lifetimes?
 118             GenericArgKind::Lifetime(_) => None,
 119
 120             // FIXME(eddyb) support const generics in Chalk
 121             GenericArgKind::Const(_) => None,
 122         }
 123     });
 124
 125     tcx.mk_chalk_environment_clause_list(clauses.chain(input_clauses))
 126 }
 127
 128 /// We need to wrap a `ty::Predicate` in an elaborated environment *before* we
 129 /// canonicalize. This is due to the fact that we insert extra clauses into the
 130 /// environment for all input types (`FromEnv`).
 131 fn in_environment(
 132     infcx: &InferCtxt<'_, 'tcx>,
 133     obligation: &PredicateObligation<'tcx>,
 134 ) -> ChalkEnvironmentAndGoal<'tcx> {
 135     assert!(!infcx.is_in_snapshot());
 136     let obligation = infcx.resolve_vars_if_possible(obligation);
 137
 138     let environment = match obligation.param_env.def_id {
 139         Some(def_id) => environment(infcx.tcx, def_id),
 140         None if obligation.param_env.caller_bounds().is_empty() => ty::List::empty(),
 141         // FIXME(chalk): this is hit in ui/where-clauses/where-clause-constraints-are-local-for-trait-impl
 142         // and ui/generics/generic-static-methods
 143         //_ => bug!("non-empty `ParamEnv` with no def-id"),
 144         _ => ty::List::empty(),
 145     };
 146
 147     ChalkEnvironmentAndGoal { environment, goal: obligation.predicate }
 148 }
 149
 150 impl TraitEngine<'tcx> for FulfillmentContext<'tcx> {
 151     fn normalize_projection_type(
 152         &mut self,
 153         infcx: &InferCtxt<'_, 'tcx>,
 154         _param_env: ty::ParamEnv<'tcx>,
 155         projection_ty: ty::ProjectionTy<'tcx>,
 156         _cause: ObligationCause<'tcx>,
 157     ) -> Ty<'tcx> {
 158         infcx.tcx.mk_ty(ty::Projection(projection_ty))
 159     }
 160
 161     fn register_predicate_obligation(
 162         &mut self,
 163         infcx: &InferCtxt<'_, 'tcx>,
 164         obligation: PredicateObligation<'tcx>,
 165     ) {
 166         assert!(!infcx.is_in_snapshot());
 167         let obligation = infcx.resolve_vars_if_possible(&obligation);
 168
 169         self.obligations.insert(obligation);
 170     }
 171
 172     fn select_all_or_error(
 173         &mut self,
 174         infcx: &InferCtxt<'_, 'tcx>,
 175     ) -> Result<(), Vec<FulfillmentError<'tcx>>> {
 176         self.select_where_possible(infcx)?;
 177
 178         if self.obligations.is_empty() {
 179             Ok(())
 180         } else {
 181             let errors = self
 182                 .obligations
 183                 .iter()
 184                 .map(|obligation| FulfillmentError {
 185                     obligation: obligation.clone(),
 186                     code: FulfillmentErrorCode::CodeAmbiguity,
 187                     points_at_arg_span: false,
 188                 })
 189                 .collect();
 190             Err(errors)
 191         }
 192     }
 193
 194     fn select_where_possible(
 195         &mut self,
 196         infcx: &InferCtxt<'_, 'tcx>,
 197     ) -> Result<(), Vec<FulfillmentError<'tcx>>> {
 198         let mut errors = Vec::new();
 199         let mut next_round = FxIndexSet::default();
 200         let mut making_progress;
 201
 202         loop {
 203             making_progress = false;
 204
 205             // We iterate over all obligations, and record if we are able
 206             // to unambiguously prove at least one obligation.
 207             for obligation in self.obligations.drain(..) {
 208                 let goal_in_environment = in_environment(infcx, &obligation);
 209                 let mut orig_values = OriginalQueryValues::default();
 210                 let canonical_goal =
 211                     infcx.canonicalize_query(&goal_in_environment, &mut orig_values);
 212
 213                 match infcx.tcx.evaluate_goal(canonical_goal) {
 214                     Ok(response) => {
 215                         if response.is_proven() {
 216                             making_progress = true;
 217
 218                             match infcx.instantiate_query_response_and_region_obligations(
 219                                 &obligation.cause,
 220                                 obligation.param_env,
 221                                 &orig_values,
 222                                 &response,
 223                             ) {
 224                                 Ok(infer_ok) => next_round.extend(
 225                                     infer_ok.obligations.into_iter().map(|obligation| {
 226                                         assert!(!infcx.is_in_snapshot());
 227                                         infcx.resolve_vars_if_possible(&obligation)
 228                                     }),
 229                                 ),
 230
 231                                 Err(_err) => errors.push(FulfillmentError {
 232                                     obligation,
 233                                     code: FulfillmentErrorCode::CodeSelectionError(
 234                                         SelectionError::Unimplemented,
 235                                     ),
 236                                     points_at_arg_span: false,
 237                                 }),
 238                             }
 239                         } else {
 240                             // Ambiguous: retry at next round.
 241                             next_round.insert(obligation);
 242                         }
 243                     }
 244
 245                     Err(NoSolution) => errors.push(FulfillmentError {
 246                         obligation,
 247                         code: FulfillmentErrorCode::CodeSelectionError(
 248                             SelectionError::Unimplemented,
 249                         ),
 250                         points_at_arg_span: false,
 251                     }),
 252                 }
 253             }
 254             next_round = std::mem::replace(&mut self.obligations, next_round);
 255
 256             if !making_progress {
 257                 break;
 258             }
 259         }
 260
 261         if errors.is_empty() { Ok(()) } else { Err(errors) }
 262     }
 263
 264     fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> {
 265         self.obligations.iter().cloned().collect()
 266     }
 267 }