| //! Defines a Chalk-based `TraitEngine` |
| |
| use crate::infer::canonical::OriginalQueryValues; |
| use crate::infer::InferCtxt; |
| use crate::traits::query::NoSolution; |
| use crate::traits::{ |
| ChalkEnvironmentAndGoal, ChalkEnvironmentClause, FulfillmentError, FulfillmentErrorCode, |
| ObligationCause, PredicateObligation, SelectionError, TraitEngine, |
| }; |
| use rustc_data_structures::fx::FxIndexSet; |
| use rustc_hir::def_id::DefId; |
| use rustc_middle::ty::{self, Ty, TyCtxt}; |
| |
| pub struct FulfillmentContext<'tcx> { |
| obligations: FxIndexSet<PredicateObligation<'tcx>>, |
| } |
| |
| impl FulfillmentContext<'tcx> { |
| crate fn new() -> Self { |
| FulfillmentContext { obligations: FxIndexSet::default() } |
| } |
| } |
| |
| fn environment<'tcx>( |
| tcx: TyCtxt<'tcx>, |
| def_id: DefId, |
| ) -> &'tcx ty::List<ChalkEnvironmentClause<'tcx>> { |
| use rustc_hir::{ForeignItemKind, ImplItemKind, ItemKind, Node, TraitItemKind}; |
| use rustc_middle::ty::subst::GenericArgKind; |
| |
| debug!("environment(def_id = {:?})", def_id); |
| |
| // The environment of an impl Trait type is its defining function's environment. |
| if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) { |
| return environment(tcx, parent); |
| } |
| |
| // Compute the bounds on `Self` and the type parameters. |
| let ty::InstantiatedPredicates { predicates, .. } = |
| tcx.predicates_of(def_id).instantiate_identity(tcx); |
| |
| let clauses = predicates.into_iter().map(ChalkEnvironmentClause::Predicate); |
| |
| let hir_id = tcx.hir().as_local_hir_id(def_id.expect_local()); |
| let node = tcx.hir().get(hir_id); |
| |
| enum NodeKind { |
| TraitImpl, |
| InherentImpl, |
| Fn, |
| Other, |
| }; |
| |
| let node_kind = match node { |
| Node::TraitItem(item) => match item.kind { |
| TraitItemKind::Fn(..) => NodeKind::Fn, |
| _ => NodeKind::Other, |
| }, |
| |
| Node::ImplItem(item) => match item.kind { |
| ImplItemKind::Fn(..) => NodeKind::Fn, |
| _ => NodeKind::Other, |
| }, |
| |
| Node::Item(item) => match item.kind { |
| ItemKind::Impl { of_trait: Some(_), .. } => NodeKind::TraitImpl, |
| ItemKind::Impl { of_trait: None, .. } => NodeKind::InherentImpl, |
| ItemKind::Fn(..) => NodeKind::Fn, |
| _ => NodeKind::Other, |
| }, |
| |
| Node::ForeignItem(item) => match item.kind { |
| ForeignItemKind::Fn(..) => NodeKind::Fn, |
| _ => NodeKind::Other, |
| }, |
| |
| // FIXME: closures? |
| _ => NodeKind::Other, |
| }; |
| |
| // FIXME(eddyb) isn't the unordered nature of this a hazard? |
| let mut inputs = FxIndexSet::default(); |
| |
| match node_kind { |
| // In a trait impl, we assume that the header trait ref and all its |
| // constituents are well-formed. |
| NodeKind::TraitImpl => { |
| let trait_ref = tcx.impl_trait_ref(def_id).expect("not an impl"); |
| |
| // FIXME(chalk): this has problems because of late-bound regions |
| //inputs.extend(trait_ref.substs.iter().flat_map(|arg| arg.walk())); |
| inputs.extend(trait_ref.substs.iter()); |
| } |
| |
| // In an inherent impl, we assume that the receiver type and all its |
| // constituents are well-formed. |
| NodeKind::InherentImpl => { |
| let self_ty = tcx.type_of(def_id); |
| inputs.extend(self_ty.walk()); |
| } |
| |
| // In an fn, we assume that the arguments and all their constituents are |
| // well-formed. |
| NodeKind::Fn => { |
| let fn_sig = tcx.fn_sig(def_id); |
| let fn_sig = tcx.liberate_late_bound_regions(def_id, &fn_sig); |
| |
| inputs.extend(fn_sig.inputs().iter().flat_map(|ty| ty.walk())); |
| } |
| |
| NodeKind::Other => (), |
| } |
| let input_clauses = inputs.into_iter().filter_map(|arg| { |
| match arg.unpack() { |
| GenericArgKind::Type(ty) => Some(ChalkEnvironmentClause::TypeFromEnv(ty)), |
| |
| // FIXME(eddyb) no WF conditions from lifetimes? |
| GenericArgKind::Lifetime(_) => None, |
| |
| // FIXME(eddyb) support const generics in Chalk |
| GenericArgKind::Const(_) => None, |
| } |
| }); |
| |
| tcx.mk_chalk_environment_clause_list(clauses.chain(input_clauses)) |
| } |
| |
| /// We need to wrap a `ty::Predicate` in an elaborated environment *before* we |
| /// canonicalize. This is due to the fact that we insert extra clauses into the |
| /// environment for all input types (`FromEnv`). |
| fn in_environment( |
| infcx: &InferCtxt<'_, 'tcx>, |
| obligation: &PredicateObligation<'tcx>, |
| ) -> ChalkEnvironmentAndGoal<'tcx> { |
| assert!(!infcx.is_in_snapshot()); |
| let obligation = infcx.resolve_vars_if_possible(obligation); |
| |
| let environment = match obligation.param_env.def_id { |
| Some(def_id) => environment(infcx.tcx, def_id), |
| None if obligation.param_env.caller_bounds().is_empty() => ty::List::empty(), |
| // FIXME(chalk): this is hit in ui/where-clauses/where-clause-constraints-are-local-for-trait-impl |
| // and ui/generics/generic-static-methods |
| //_ => bug!("non-empty `ParamEnv` with no def-id"), |
| _ => ty::List::empty(), |
| }; |
| |
| ChalkEnvironmentAndGoal { environment, goal: obligation.predicate } |
| } |
| |
| impl TraitEngine<'tcx> for FulfillmentContext<'tcx> { |
| fn normalize_projection_type( |
| &mut self, |
| infcx: &InferCtxt<'_, 'tcx>, |
| _param_env: ty::ParamEnv<'tcx>, |
| projection_ty: ty::ProjectionTy<'tcx>, |
| _cause: ObligationCause<'tcx>, |
| ) -> Ty<'tcx> { |
| infcx.tcx.mk_ty(ty::Projection(projection_ty)) |
| } |
| |
| fn register_predicate_obligation( |
| &mut self, |
| infcx: &InferCtxt<'_, 'tcx>, |
| obligation: PredicateObligation<'tcx>, |
| ) { |
| assert!(!infcx.is_in_snapshot()); |
| let obligation = infcx.resolve_vars_if_possible(&obligation); |
| |
| self.obligations.insert(obligation); |
| } |
| |
| fn select_all_or_error( |
| &mut self, |
| infcx: &InferCtxt<'_, 'tcx>, |
| ) -> Result<(), Vec<FulfillmentError<'tcx>>> { |
| self.select_where_possible(infcx)?; |
| |
| if self.obligations.is_empty() { |
| Ok(()) |
| } else { |
| let errors = self |
| .obligations |
| .iter() |
| .map(|obligation| FulfillmentError { |
| obligation: obligation.clone(), |
| code: FulfillmentErrorCode::CodeAmbiguity, |
| points_at_arg_span: false, |
| }) |
| .collect(); |
| Err(errors) |
| } |
| } |
| |
| fn select_where_possible( |
| &mut self, |
| infcx: &InferCtxt<'_, 'tcx>, |
| ) -> Result<(), Vec<FulfillmentError<'tcx>>> { |
| let mut errors = Vec::new(); |
| let mut next_round = FxIndexSet::default(); |
| let mut making_progress; |
| |
| loop { |
| making_progress = false; |
| |
| // We iterate over all obligations, and record if we are able |
| // to unambiguously prove at least one obligation. |
| for obligation in self.obligations.drain(..) { |
| let goal_in_environment = in_environment(infcx, &obligation); |
| let mut orig_values = OriginalQueryValues::default(); |
| let canonical_goal = |
| infcx.canonicalize_query(&goal_in_environment, &mut orig_values); |
| |
| match infcx.tcx.evaluate_goal(canonical_goal) { |
| Ok(response) => { |
| if response.is_proven() { |
| making_progress = true; |
| |
| match infcx.instantiate_query_response_and_region_obligations( |
| &obligation.cause, |
| obligation.param_env, |
| &orig_values, |
| &response, |
| ) { |
| Ok(infer_ok) => next_round.extend( |
| infer_ok.obligations.into_iter().map(|obligation| { |
| assert!(!infcx.is_in_snapshot()); |
| infcx.resolve_vars_if_possible(&obligation) |
| }), |
| ), |
| |
| Err(_err) => errors.push(FulfillmentError { |
| obligation, |
| code: FulfillmentErrorCode::CodeSelectionError( |
| SelectionError::Unimplemented, |
| ), |
| points_at_arg_span: false, |
| }), |
| } |
| } else { |
| // Ambiguous: retry at next round. |
| next_round.insert(obligation); |
| } |
| } |
| |
| Err(NoSolution) => errors.push(FulfillmentError { |
| obligation, |
| code: FulfillmentErrorCode::CodeSelectionError( |
| SelectionError::Unimplemented, |
| ), |
| points_at_arg_span: false, |
| }), |
| } |
| } |
| next_round = std::mem::replace(&mut self.obligations, next_round); |
| |
| if !making_progress { |
| break; |
| } |
| } |
| |
| if errors.is_empty() { Ok(()) } else { Err(errors) } |
| } |
| |
| fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> { |
| self.obligations.iter().cloned().collect() |
| } |
| } |