1 //! Defines a Chalk-based `TraitEngine`
3 use crate::infer::canonical::OriginalQueryValues;
4 use crate::infer::InferCtxt;
5 use crate::traits::query::NoSolution;
7 ChalkEnvironmentAndGoal, ChalkEnvironmentClause, FulfillmentError, FulfillmentErrorCode,
8 ObligationCause, PredicateObligation, SelectionError, TraitEngine,
10 use rustc_data_structures::fx::FxIndexSet;
11 use rustc_hir::def_id::DefId;
12 use rustc_middle::ty::{self, Ty, TyCtxt};
14 pub struct FulfillmentContext<'tcx> {
15 obligations: FxIndexSet<PredicateObligation<'tcx>>,
18 impl FulfillmentContext<'tcx> {
19 crate fn new() -> Self {
20 FulfillmentContext { obligations: FxIndexSet::default() }
27 ) -> &'tcx ty::List<ChalkEnvironmentClause<'tcx>> {
28 use rustc_hir::{ForeignItemKind, ImplItemKind, ItemKind, Node, TraitItemKind};
29 use rustc_middle::ty::subst::GenericArgKind;
31 debug!("environment(def_id = {:?})", def_id);
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);
38 // Compute the bounds on `Self` and the type parameters.
39 let ty::InstantiatedPredicates { predicates, .. } =
40 tcx.predicates_of(def_id).instantiate_identity(tcx);
42 let clauses = predicates.into_iter().map(ChalkEnvironmentClause::Predicate);
44 let hir_id = tcx.hir().as_local_hir_id(def_id.expect_local());
45 let node = tcx.hir().get(hir_id);
54 let node_kind = match node {
55 Node::TraitItem(item) => match item.kind {
56 TraitItemKind::Fn(..) => NodeKind::Fn,
60 Node::ImplItem(item) => match item.kind {
61 ImplItemKind::Fn(..) => NodeKind::Fn,
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,
72 Node::ForeignItem(item) => match item.kind {
73 ForeignItemKind::Fn(..) => NodeKind::Fn,
81 // FIXME(eddyb) isn't the unordered nature of this a hazard?
82 let mut inputs = FxIndexSet::default();
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");
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());
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());
102 // In an fn, we assume that the arguments and all their constituents are
105 let fn_sig = tcx.fn_sig(def_id);
106 let fn_sig = tcx.liberate_late_bound_regions(def_id, &fn_sig);
108 inputs.extend(fn_sig.inputs().iter().flat_map(|ty| ty.walk()));
111 NodeKind::Other => (),
113 let input_clauses = inputs.into_iter().filter_map(|arg| {
115 GenericArgKind::Type(ty) => Some(ChalkEnvironmentClause::TypeFromEnv(ty)),
117 // FIXME(eddyb) no WF conditions from lifetimes?
118 GenericArgKind::Lifetime(_) => None,
120 // FIXME(eddyb) support const generics in Chalk
121 GenericArgKind::Const(_) => None,
125 tcx.mk_chalk_environment_clause_list(clauses.chain(input_clauses))
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`).
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);
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(),
147 ChalkEnvironmentAndGoal { environment, goal: obligation.predicate }
150 impl TraitEngine<'tcx> for FulfillmentContext<'tcx> {
151 fn normalize_projection_type(
153 infcx: &InferCtxt<'_, 'tcx>,
154 _param_env: ty::ParamEnv<'tcx>,
155 projection_ty: ty::ProjectionTy<'tcx>,
156 _cause: ObligationCause<'tcx>,
158 infcx.tcx.mk_ty(ty::Projection(projection_ty))
161 fn register_predicate_obligation(
163 infcx: &InferCtxt<'_, 'tcx>,
164 obligation: PredicateObligation<'tcx>,
166 assert!(!infcx.is_in_snapshot());
167 let obligation = infcx.resolve_vars_if_possible(&obligation);
169 self.obligations.insert(obligation);
172 fn select_all_or_error(
174 infcx: &InferCtxt<'_, 'tcx>,
175 ) -> Result<(), Vec<FulfillmentError<'tcx>>> {
176 self.select_where_possible(infcx)?;
178 if self.obligations.is_empty() {
184 .map(|obligation| FulfillmentError {
185 obligation: obligation.clone(),
186 code: FulfillmentErrorCode::CodeAmbiguity,
187 points_at_arg_span: false,
194 fn select_where_possible(
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;
203 making_progress = false;
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();
211 infcx.canonicalize_query(&goal_in_environment, &mut orig_values);
213 match infcx.tcx.evaluate_goal(canonical_goal) {
215 if response.is_proven() {
216 making_progress = true;
218 match infcx.instantiate_query_response_and_region_obligations(
220 obligation.param_env,
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)
231 Err(_err) => errors.push(FulfillmentError {
233 code: FulfillmentErrorCode::CodeSelectionError(
234 SelectionError::Unimplemented,
236 points_at_arg_span: false,
240 // Ambiguous: retry at next round.
241 next_round.insert(obligation);
245 Err(NoSolution) => errors.push(FulfillmentError {
247 code: FulfillmentErrorCode::CodeSelectionError(
248 SelectionError::Unimplemented,
250 points_at_arg_span: false,
254 next_round = std::mem::replace(&mut self.obligations, next_round);
256 if !making_progress {
261 if errors.is_empty() { Ok(()) } else { Err(errors) }
264 fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> {
265 self.obligations.iter().cloned().collect()