1 //! Trait Resolution. See the [rustc dev guide] for more information on how this works.
3 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html
6 pub(crate) mod coherence
;
7 pub mod const_evaluatable
;
9 pub mod error_reporting
;
13 pub mod outlives_bounds
;
16 #[allow(hidden_glob_reexports)]
20 mod structural_normalize
;
21 #[allow(hidden_glob_reexports)]
26 use crate::infer
::outlives
::env
::OutlivesEnvironment
;
27 use crate::infer
::{InferCtxt, TyCtxtInferExt}
;
28 use crate::traits
::error_reporting
::TypeErrCtxtExt
as _
;
29 use crate::traits
::query
::evaluate_obligation
::InferCtxtExt
as _
;
30 use rustc_errors
::ErrorGuaranteed
;
31 use rustc_middle
::query
::Providers
;
32 use rustc_middle
::ty
::fold
::TypeFoldable
;
33 use rustc_middle
::ty
::visit
::{TypeVisitable, TypeVisitableExt}
;
34 use rustc_middle
::ty
::{self, ToPredicate, Ty, TyCtxt, TypeFolder, TypeSuperVisitable}
;
35 use rustc_middle
::ty
::{GenericArgs, GenericArgsRef}
;
36 use rustc_span
::def_id
::DefId
;
40 use std
::ops
::ControlFlow
;
42 pub(crate) use self::project
::{needs_normalization, BoundVarReplacer, PlaceholderReplacer}
;
44 pub use self::coherence
::{add_placeholder_note, orphan_check, overlapping_impls}
;
45 pub use self::coherence
::{OrphanCheckErr, OverlapResult}
;
46 pub use self::engine
::{ObligationCtxt, TraitEngineExt}
;
47 pub use self::fulfill
::{FulfillmentContext, PendingPredicateObligation}
;
48 pub use self::object_safety
::astconv_object_safety_violations
;
49 pub use self::object_safety
::is_vtable_safe_method
;
50 pub use self::object_safety
::object_safety_violations_for_assoc_item
;
51 pub use self::object_safety
::ObjectSafetyViolation
;
52 pub use self::project
::NormalizeExt
;
53 pub use self::project
::{normalize_inherent_projection, normalize_projection_type}
;
54 pub use self::select
::{EvaluationCache, SelectionCache, SelectionContext}
;
55 pub use self::select
::{EvaluationResult, IntercrateAmbiguityCause, OverflowError}
;
56 pub use self::specialize
::specialization_graph
::FutureCompatOverlapError
;
57 pub use self::specialize
::specialization_graph
::FutureCompatOverlapErrorKind
;
58 pub use self::specialize
::{
59 specialization_graph
, translate_args
, translate_args_with_cause
, OverlapError
,
61 pub use self::structural_match
::search_for_structural_match_violation
;
62 pub use self::structural_normalize
::StructurallyNormalizeExt
;
63 pub use self::util
::elaborate
;
65 check_args_compatible
, supertrait_def_ids
, supertraits
, transitive_bounds
,
66 transitive_bounds_that_define_assoc_item
, SupertraitDefIds
,
68 pub use self::util
::{expand_trait_aliases, TraitAliasExpander}
;
69 pub use self::util
::{get_vtable_index_of_object_method, impl_item_is_final, upcast_choices}
;
71 pub use rustc_infer
::traits
::*;
73 /// Whether to skip the leak check, as part of a future compatibility warning step.
75 /// The "default" for skip-leak-check corresponds to the current
76 /// behavior (do not skip the leak check) -- not the behavior we are
77 /// transitioning into.
78 #[derive(Copy, Clone, PartialEq, Eq, Debug, Default)]
79 pub enum SkipLeakCheck
{
86 fn is_yes(self) -> bool
{
87 self == SkipLeakCheck
::Yes
91 /// The mode that trait queries run in.
92 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
93 pub enum TraitQueryMode
{
94 /// Standard/un-canonicalized queries get accurate
95 /// spans etc. passed in and hence can do reasonable
96 /// error reporting on their own.
98 /// Canonical queries get dummy spans and hence
99 /// must generally propagate errors to
100 /// pre-canonicalization callsites.
104 /// Creates predicate obligations from the generic bounds.
105 #[instrument(level = "debug", skip(cause, param_env))]
106 pub fn predicates_for_generics
<'tcx
>(
107 cause
: impl Fn(usize, Span
) -> ObligationCause
<'tcx
>,
108 param_env
: ty
::ParamEnv
<'tcx
>,
109 generic_bounds
: ty
::InstantiatedPredicates
<'tcx
>,
110 ) -> impl Iterator
<Item
= PredicateObligation
<'tcx
>> {
111 generic_bounds
.into_iter().enumerate().map(move |(idx
, (clause
, span
))| Obligation
{
112 cause
: cause(idx
, span
),
115 predicate
: clause
.as_predicate(),
119 /// Determines whether the type `ty` is known to meet `bound` and
120 /// returns true if so. Returns false if `ty` either does not meet
121 /// `bound` or is not known to meet bound (note that this is
122 /// conservative towards *no impl*, which is the opposite of the
123 /// `evaluate` methods).
124 pub fn type_known_to_meet_bound_modulo_regions
<'tcx
>(
125 infcx
: &InferCtxt
<'tcx
>,
126 param_env
: ty
::ParamEnv
<'tcx
>,
130 let trait_ref
= ty
::TraitRef
::new(infcx
.tcx
, def_id
, [ty
]);
131 pred_known_to_hold_modulo_regions(infcx
, param_env
, trait_ref
)
134 /// FIXME(@lcnr): this function doesn't seem right and shouldn't exist?
136 /// Ping me on zulip if you want to use this method and need help with finding
137 /// an appropriate replacement.
138 #[instrument(level = "debug", skip(infcx, param_env, pred), ret)]
139 fn pred_known_to_hold_modulo_regions
<'tcx
>(
140 infcx
: &InferCtxt
<'tcx
>,
141 param_env
: ty
::ParamEnv
<'tcx
>,
142 pred
: impl ToPredicate
<'tcx
>,
144 let obligation
= Obligation
::new(infcx
.tcx
, ObligationCause
::dummy(), param_env
, pred
);
146 let result
= infcx
.evaluate_obligation_no_overflow(&obligation
);
149 if result
.must_apply_modulo_regions() {
151 } else if result
.may_apply() {
152 // Sometimes obligations are ambiguous because the recursive evaluator
153 // is not smart enough, so we fall back to fulfillment when we're not certain
154 // that an obligation holds or not. Even still, we must make sure that
155 // the we do no inference in the process of checking this obligation.
156 let goal
= infcx
.resolve_vars_if_possible((obligation
.predicate
, obligation
.param_env
));
158 let ocx
= ObligationCtxt
::new(infcx
);
159 ocx
.register_obligation(obligation
);
161 let errors
= ocx
.select_all_or_error();
162 match errors
.as_slice() {
163 // Only known to hold if we did no inference.
164 [] => infcx
.shallow_resolve(goal
) == goal
,
177 #[instrument(level = "debug", skip(tcx, elaborated_env))]
178 fn do_normalize_predicates
<'tcx
>(
180 cause
: ObligationCause
<'tcx
>,
181 elaborated_env
: ty
::ParamEnv
<'tcx
>,
182 predicates
: Vec
<ty
::Clause
<'tcx
>>,
183 ) -> Result
<Vec
<ty
::Clause
<'tcx
>>, ErrorGuaranteed
> {
184 let span
= cause
.span
;
185 // FIXME. We should really... do something with these region
186 // obligations. But this call just continues the older
187 // behavior (i.e., doesn't cause any new bugs), and it would
188 // take some further refactoring to actually solve them. In
189 // particular, we would have to handle implied bounds
190 // properly, and that code is currently largely confined to
191 // regionck (though I made some efforts to extract it
194 // @arielby: In any case, these obligations are checked
195 // by wfcheck anyway, so I'm not sure we have to check
196 // them here too, and we will remove this function when
197 // we move over to lazy normalization *anyway*.
198 let infcx
= tcx
.infer_ctxt().ignoring_regions().build();
199 let predicates
= match fully_normalize(&infcx
, cause
, elaborated_env
, predicates
) {
200 Ok(predicates
) => predicates
,
202 let reported
= infcx
.err_ctxt().report_fulfillment_errors(errors
);
203 return Err(reported
);
207 debug
!("do_normalize_predicates: normalized predicates = {:?}", predicates
);
209 // We can use the `elaborated_env` here; the region code only
210 // cares about declarations like `'a: 'b`.
211 let outlives_env
= OutlivesEnvironment
::new(elaborated_env
);
213 // FIXME: It's very weird that we ignore region obligations but apparently
214 // still need to use `resolve_regions` as we need the resolved regions in
215 // the normalized predicates.
216 let errors
= infcx
.resolve_regions(&outlives_env
);
217 if !errors
.is_empty() {
218 tcx
.sess
.span_delayed_bug(
220 format
!("failed region resolution while normalizing {elaborated_env:?}: {errors:?}"),
224 match infcx
.fully_resolve(predicates
) {
225 Ok(predicates
) => Ok(predicates
),
227 // If we encounter a fixup error, it means that some type
228 // variable wound up unconstrained. I actually don't know
229 // if this can happen, and I certainly don't expect it to
230 // happen often, but if it did happen it probably
231 // represents a legitimate failure due to some kind of
232 // unconstrained variable.
234 // @lcnr: Let's still ICE here for now. I want a test case
238 "inference variables in normalized parameter environment: {}",
245 // FIXME: this is gonna need to be removed ...
246 /// Normalizes the parameter environment, reporting errors if they occur.
247 #[instrument(level = "debug", skip(tcx))]
248 pub fn normalize_param_env_or_error
<'tcx
>(
250 unnormalized_env
: ty
::ParamEnv
<'tcx
>,
251 cause
: ObligationCause
<'tcx
>,
252 ) -> ty
::ParamEnv
<'tcx
> {
253 // I'm not wild about reporting errors here; I'd prefer to
254 // have the errors get reported at a defined place (e.g.,
255 // during typeck). Instead I have all parameter
256 // environments, in effect, going through this function
257 // and hence potentially reporting errors. This ensures of
258 // course that we never forget to normalize (the
259 // alternative seemed like it would involve a lot of
260 // manual invocations of this fn -- and then we'd have to
261 // deal with the errors at each of those sites).
263 // In any case, in practice, typeck constructs all the
264 // parameter environments once for every fn as it goes,
265 // and errors will get reported then; so outside of type inference we
266 // can be sure that no errors should occur.
267 let mut predicates
: Vec
<_
> = util
::elaborate(
269 unnormalized_env
.caller_bounds().into_iter().map(|predicate
| {
270 if tcx
.features().generic_const_exprs
{
274 struct ConstNormalizer
<'tcx
>(TyCtxt
<'tcx
>);
276 impl<'tcx
> TypeFolder
<TyCtxt
<'tcx
>> for ConstNormalizer
<'tcx
> {
277 fn interner(&self) -> TyCtxt
<'tcx
> {
281 fn fold_const(&mut self, c
: ty
::Const
<'tcx
>) -> ty
::Const
<'tcx
> {
282 // While it is pretty sus to be evaluating things with an empty param env, it
283 // should actually be okay since without `feature(generic_const_exprs)` the only
284 // const arguments that have a non-empty param env are array repeat counts. These
285 // do not appear in the type system though.
286 c
.normalize(self.0, ty
::ParamEnv
::empty())
290 // This whole normalization step is a hack to work around the fact that
291 // `normalize_param_env_or_error` is fundamentally broken from using an
292 // unnormalized param env with a trait solver that expects the param env
295 // When normalizing the param env we can end up evaluating obligations
296 // that have been normalized but can only be proven via a where clause
297 // which is still in its unnormalized form. example:
299 // Attempting to prove `T: Trait<<u8 as Identity>::Assoc>` in a param env
300 // with a `T: Trait<<u8 as Identity>::Assoc>` where clause will fail because
301 // we first normalize obligations before proving them so we end up proving
302 // `T: Trait<u8>`. Since lazy normalization is not implemented equating `u8`
303 // with `<u8 as Identity>::Assoc` fails outright so we incorrectly believe that
304 // we cannot prove `T: Trait<u8>`.
306 // The same thing is true for const generics- attempting to prove
307 // `T: Trait<ConstKind::Unevaluated(...)>` with the same thing as a where clauses
308 // will fail. After normalization we may be attempting to prove `T: Trait<4>` with
309 // the unnormalized where clause `T: Trait<ConstKind::Unevaluated(...)>`. In order
310 // for the obligation to hold `4` must be equal to `ConstKind::Unevaluated(...)`
311 // but as we do not have lazy norm implemented, equating the two consts fails outright.
313 // Ideally we would not normalize consts here at all but it is required for backwards
314 // compatibility. Eventually when lazy norm is implemented this can just be removed.
315 // We do not normalize types here as there is no backwards compatibility requirement
318 // FIXME(-Znext-solver): remove this hack since we have deferred projection equality
319 predicate
.fold_with(&mut ConstNormalizer(tcx
))
324 debug
!("normalize_param_env_or_error: elaborated-predicates={:?}", predicates
);
326 let elaborated_env
= ty
::ParamEnv
::new(tcx
.mk_clauses(&predicates
), unnormalized_env
.reveal());
328 // HACK: we are trying to normalize the param-env inside *itself*. The problem is that
329 // normalization expects its param-env to be already normalized, which means we have
332 // The way we handle this is by normalizing the param-env inside an unnormalized version
333 // of the param-env, which means that if the param-env contains unnormalized projections,
334 // we'll have some normalization failures. This is unfortunate.
336 // Lazy normalization would basically handle this by treating just the
337 // normalizing-a-trait-ref-requires-itself cycles as evaluation failures.
339 // Inferred outlives bounds can create a lot of `TypeOutlives` predicates for associated
340 // types, so to make the situation less bad, we normalize all the predicates *but*
341 // the `TypeOutlives` predicates first inside the unnormalized parameter environment, and
342 // then we normalize the `TypeOutlives` bounds inside the normalized parameter environment.
344 // This works fairly well because trait matching does not actually care about param-env
345 // TypeOutlives predicates - these are normally used by regionck.
346 let outlives_predicates
: Vec
<_
> = predicates
347 .extract_if(|predicate
| {
348 matches
!(predicate
.kind().skip_binder(), ty
::ClauseKind
::TypeOutlives(..))
353 "normalize_param_env_or_error: predicates=(non-outlives={:?}, outlives={:?})",
354 predicates
, outlives_predicates
356 let Ok(non_outlives_predicates
) =
357 do_normalize_predicates(tcx
, cause
.clone(), elaborated_env
, predicates
)
359 // An unnormalized env is better than nothing.
360 debug
!("normalize_param_env_or_error: errored resolving non-outlives predicates");
361 return elaborated_env
;
364 debug
!("normalize_param_env_or_error: non-outlives predicates={:?}", non_outlives_predicates
);
366 // Not sure whether it is better to include the unnormalized TypeOutlives predicates
367 // here. I believe they should not matter, because we are ignoring TypeOutlives param-env
368 // predicates here anyway. Keeping them here anyway because it seems safer.
369 let outlives_env
= non_outlives_predicates
.iter().chain(&outlives_predicates
).cloned();
371 ty
::ParamEnv
::new(tcx
.mk_clauses_from_iter(outlives_env
), unnormalized_env
.reveal());
372 let Ok(outlives_predicates
) =
373 do_normalize_predicates(tcx
, cause
, outlives_env
, outlives_predicates
)
375 // An unnormalized env is better than nothing.
376 debug
!("normalize_param_env_or_error: errored resolving outlives predicates");
377 return elaborated_env
;
379 debug
!("normalize_param_env_or_error: outlives predicates={:?}", outlives_predicates
);
381 let mut predicates
= non_outlives_predicates
;
382 predicates
.extend(outlives_predicates
);
383 debug
!("normalize_param_env_or_error: final predicates={:?}", predicates
);
384 ty
::ParamEnv
::new(tcx
.mk_clauses(&predicates
), unnormalized_env
.reveal())
387 /// Normalize a type and process all resulting obligations, returning any errors.
389 /// FIXME(-Znext-solver): This should be replaced by `At::deeply_normalize`
390 /// which has the same behavior with the new solver. Because using a separate
391 /// fulfillment context worsens caching in the old solver, `At::deeply_normalize`
392 /// is still lazy with the old solver as it otherwise negatively impacts perf.
393 #[instrument(skip_all)]
394 pub fn fully_normalize
<'tcx
, T
>(
395 infcx
: &InferCtxt
<'tcx
>,
396 cause
: ObligationCause
<'tcx
>,
397 param_env
: ty
::ParamEnv
<'tcx
>,
399 ) -> Result
<T
, Vec
<FulfillmentError
<'tcx
>>>
401 T
: TypeFoldable
<TyCtxt
<'tcx
>>,
403 let ocx
= ObligationCtxt
::new(infcx
);
405 let normalized_value
= ocx
.normalize(&cause
, param_env
, value
);
406 debug
!(?normalized_value
);
407 debug
!("select_all_or_error start");
408 let errors
= ocx
.select_all_or_error();
409 if !errors
.is_empty() {
412 debug
!("select_all_or_error complete");
413 let resolved_value
= infcx
.resolve_vars_if_possible(normalized_value
);
414 debug
!(?resolved_value
);
418 /// Normalizes the predicates and checks whether they hold in an empty environment. If this
419 /// returns true, then either normalize encountered an error or one of the predicates did not
420 /// hold. Used when creating vtables to check for unsatisfiable methods.
421 pub fn impossible_predicates
<'tcx
>(tcx
: TyCtxt
<'tcx
>, predicates
: Vec
<ty
::Clause
<'tcx
>>) -> bool
{
422 debug
!("impossible_predicates(predicates={:?})", predicates
);
424 let infcx
= tcx
.infer_ctxt().build();
425 let param_env
= ty
::ParamEnv
::reveal_all();
426 let ocx
= ObligationCtxt
::new(&infcx
);
427 let predicates
= ocx
.normalize(&ObligationCause
::dummy(), param_env
, predicates
);
428 for predicate
in predicates
{
429 let obligation
= Obligation
::new(tcx
, ObligationCause
::dummy(), param_env
, predicate
);
430 ocx
.register_obligation(obligation
);
432 let errors
= ocx
.select_all_or_error();
434 let result
= !errors
.is_empty();
435 debug
!("impossible_predicates = {:?}", result
);
439 fn subst_and_check_impossible_predicates
<'tcx
>(
441 key
: (DefId
, GenericArgsRef
<'tcx
>),
443 debug
!("subst_and_check_impossible_predicates(key={:?})", key
);
445 let mut predicates
= tcx
.predicates_of(key
.0).instantiate(tcx
, key
.1).predicates
;
447 // Specifically check trait fulfillment to avoid an error when trying to resolve
449 if let Some(trait_def_id
) = tcx
.trait_of_item(key
.0) {
450 let trait_ref
= ty
::TraitRef
::from_method(tcx
, trait_def_id
, key
.1);
451 predicates
.push(ty
::Binder
::dummy(trait_ref
).to_predicate(tcx
));
454 predicates
.retain(|predicate
| !predicate
.has_param());
455 let result
= impossible_predicates(tcx
, predicates
);
457 debug
!("subst_and_check_impossible_predicates(key={:?}) = {:?}", key
, result
);
461 /// Checks whether a trait's associated item is impossible to reference on a given impl.
463 /// This only considers predicates that reference the impl's generics, and not
464 /// those that reference the method's generics.
465 fn is_impossible_associated_item(
467 (impl_def_id
, trait_item_def_id
): (DefId
, DefId
),
469 struct ReferencesOnlyParentGenerics
<'tcx
> {
471 generics
: &'tcx ty
::Generics
,
472 trait_item_def_id
: DefId
,
474 impl<'tcx
> ty
::TypeVisitor
<TyCtxt
<'tcx
>> for ReferencesOnlyParentGenerics
<'tcx
> {
476 fn visit_ty(&mut self, t
: Ty
<'tcx
>) -> ControlFlow
<Self::BreakTy
> {
477 // If this is a parameter from the trait item's own generics, then bail
478 if let ty
::Param(param
) = t
.kind()
479 && let param_def_id
= self.generics
.type_param(param
, self.tcx
).def_id
480 && self.tcx
.parent(param_def_id
) == self.trait_item_def_id
482 return ControlFlow
::Break(());
484 t
.super_visit_with(self)
486 fn visit_region(&mut self, r
: ty
::Region
<'tcx
>) -> ControlFlow
<Self::BreakTy
> {
487 if let ty
::ReEarlyParam(param
) = r
.kind()
488 && let param_def_id
= self.generics
.region_param(¶m
, self.tcx
).def_id
489 && self.tcx
.parent(param_def_id
) == self.trait_item_def_id
491 return ControlFlow
::Break(());
493 ControlFlow
::Continue(())
495 fn visit_const(&mut self, ct
: ty
::Const
<'tcx
>) -> ControlFlow
<Self::BreakTy
> {
496 if let ty
::ConstKind
::Param(param
) = ct
.kind()
497 && let param_def_id
= self.generics
.const_param(¶m
, self.tcx
).def_id
498 && self.tcx
.parent(param_def_id
) == self.trait_item_def_id
500 return ControlFlow
::Break(());
502 ct
.super_visit_with(self)
506 let generics
= tcx
.generics_of(trait_item_def_id
);
507 let predicates
= tcx
.predicates_of(trait_item_def_id
);
508 let impl_trait_ref
= tcx
509 .impl_trait_ref(impl_def_id
)
510 .expect("expected impl to correspond to trait")
511 .instantiate_identity();
512 let param_env
= tcx
.param_env(impl_def_id
);
514 let mut visitor
= ReferencesOnlyParentGenerics { tcx, generics, trait_item_def_id }
;
515 let predicates_for_trait
= predicates
.predicates
.iter().filter_map(|(pred
, span
)| {
516 pred
.visit_with(&mut visitor
).is_continue().then(|| {
519 ObligationCause
::dummy_with_span(*span
),
521 ty
::EarlyBinder
::bind(*pred
).instantiate(tcx
, impl_trait_ref
.args
),
526 let infcx
= tcx
.infer_ctxt().ignoring_regions().build();
527 for obligation
in predicates_for_trait
{
528 // Ignore overflow error, to be conservative.
529 if let Ok(result
) = infcx
.evaluate_obligation(&obligation
)
530 && !result
.may_apply()
538 pub fn provide(providers
: &mut Providers
) {
539 object_safety
::provide(providers
);
540 vtable
::provide(providers
);
541 *providers
= Providers
{
542 specialization_graph_of
: specialize
::specialization_graph_provider
,
543 specializes
: specialize
::specializes
,
544 subst_and_check_impossible_predicates
,
545 check_tys_might_be_eq
: misc
::check_tys_might_be_eq
,
546 is_impossible_associated_item
,