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
9 pub mod const_evaluatable
;
11 pub mod error_reporting
;
24 use crate::infer
::outlives
::env
::OutlivesEnvironment
;
25 use crate::infer
::{InferCtxt, RegionckMode, TyCtxtInferExt}
;
26 use crate::traits
::error_reporting
::InferCtxtExt
as _
;
27 use crate::traits
::query
::evaluate_obligation
::InferCtxtExt
as _
;
28 use rustc_errors
::ErrorReported
;
30 use rustc_hir
::def_id
::DefId
;
31 use rustc_middle
::ty
::fold
::TypeFoldable
;
32 use rustc_middle
::ty
::subst
::{InternalSubsts, SubstsRef}
;
33 use rustc_middle
::ty
::{
34 self, GenericParamDefKind
, ParamEnv
, ToPredicate
, Ty
, TyCtxt
, WithConstness
,
40 pub use self::FulfillmentErrorCode
::*;
41 pub use self::ImplSource
::*;
42 pub use self::ObligationCauseCode
::*;
43 pub use self::SelectionError
::*;
45 pub use self::coherence
::{add_placeholder_note, orphan_check, overlapping_impls}
;
46 pub use self::coherence
::{OrphanCheckErr, OverlapResult}
;
47 pub use self::engine
::TraitEngineExt
;
48 pub use self::fulfill
::{FulfillmentContext, PendingPredicateObligation}
;
49 pub use self::object_safety
::astconv_object_safety_violations
;
50 pub use self::object_safety
::is_vtable_safe_method
;
51 pub use self::object_safety
::MethodViolationCode
;
52 pub use self::object_safety
::ObjectSafetyViolation
;
53 pub use self::on_unimplemented
::{OnUnimplementedDirective, OnUnimplementedNote}
;
54 pub use self::project
::{normalize, normalize_projection_type, normalize_to}
;
55 pub use self::select
::{EvaluationCache, SelectionCache, SelectionContext}
;
56 pub use self::select
::{EvaluationResult, IntercrateAmbiguityCause, OverflowError}
;
57 pub use self::specialize
::specialization_graph
::FutureCompatOverlapError
;
58 pub use self::specialize
::specialization_graph
::FutureCompatOverlapErrorKind
;
59 pub use self::specialize
::{specialization_graph, translate_substs, OverlapError}
;
60 pub use self::structural_match
::search_for_structural_match_violation
;
61 pub use self::structural_match
::NonStructuralMatchTy
;
62 pub use self::util
::{elaborate_predicates, elaborate_trait_ref, elaborate_trait_refs}
;
63 pub use self::util
::{expand_trait_aliases, TraitAliasExpander}
;
65 get_vtable_index_of_object_method
, impl_item_is_final
, predicate_for_trait_def
, upcast_choices
,
68 supertrait_def_ids
, supertraits
, transitive_bounds
, transitive_bounds_that_define_assoc_type
,
69 SupertraitDefIds
, Supertraits
,
72 pub use self::chalk_fulfill
::FulfillmentContext
as ChalkFulfillmentContext
;
74 pub use rustc_infer
::traits
::*;
76 /// Whether to skip the leak check, as part of a future compatibility warning step.
77 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
78 pub enum SkipLeakCheck
{
84 fn is_yes(self) -> bool
{
85 self == SkipLeakCheck
::Yes
89 /// The "default" for skip-leak-check corresponds to the current
90 /// behavior (do not skip the leak check) -- not the behavior we are
91 /// transitioning into.
92 impl Default
for SkipLeakCheck
{
93 fn default() -> Self {
98 /// The mode that trait queries run in.
99 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
100 pub enum TraitQueryMode
{
101 /// Standard/un-canonicalized queries get accurate
102 /// spans etc. passed in and hence can do reasonable
103 /// error reporting on their own.
105 /// Canonicalized queries get dummy spans and hence
106 /// must generally propagate errors to
107 /// pre-canonicalization callsites.
111 /// Creates predicate obligations from the generic bounds.
112 pub fn predicates_for_generics
<'tcx
>(
113 cause
: ObligationCause
<'tcx
>,
114 param_env
: ty
::ParamEnv
<'tcx
>,
115 generic_bounds
: ty
::InstantiatedPredicates
<'tcx
>,
116 ) -> impl Iterator
<Item
= PredicateObligation
<'tcx
>> {
117 util
::predicates_for_generics(cause
, 0, param_env
, generic_bounds
)
120 /// Determines whether the type `ty` is known to meet `bound` and
121 /// returns true if so. Returns false if `ty` either does not meet
122 /// `bound` or is not known to meet bound (note that this is
123 /// conservative towards *no impl*, which is the opposite of the
124 /// `evaluate` methods).
125 pub fn type_known_to_meet_bound_modulo_regions
<'a
, 'tcx
>(
126 infcx
: &InferCtxt
<'a
, 'tcx
>,
127 param_env
: ty
::ParamEnv
<'tcx
>,
133 "type_known_to_meet_bound_modulo_regions(ty={:?}, bound={:?})",
135 infcx
.tcx
.def_path_str(def_id
)
138 let trait_ref
= ty
::TraitRef { def_id, substs: infcx.tcx.mk_substs_trait(ty, &[]) }
;
139 let obligation
= Obligation
{
141 cause
: ObligationCause
::misc(span
, hir
::CRATE_HIR_ID
),
143 predicate
: trait_ref
.without_const().to_predicate(infcx
.tcx
),
146 let result
= infcx
.predicate_must_hold_modulo_regions(&obligation
);
148 "type_known_to_meet_ty={:?} bound={} => {:?}",
150 infcx
.tcx
.def_path_str(def_id
),
154 if result
&& ty
.has_infer_types_or_consts() {
155 // Because of inference "guessing", selection can sometimes claim
156 // to succeed while the success requires a guess. To ensure
157 // this function's result remains infallible, we must confirm
158 // that guess. While imperfect, I believe this is sound.
160 // The handling of regions in this area of the code is terrible,
161 // see issue #29149. We should be able to improve on this with
163 let mut fulfill_cx
= FulfillmentContext
::new_ignoring_regions();
165 // We can use a dummy node-id here because we won't pay any mind
166 // to region obligations that arise (there shouldn't really be any
168 let cause
= ObligationCause
::misc(span
, hir
::CRATE_HIR_ID
);
170 fulfill_cx
.register_bound(infcx
, param_env
, ty
, def_id
, cause
);
172 // Note: we only assume something is `Copy` if we can
173 // *definitively* show that it implements `Copy`. Otherwise,
174 // assume it is move; linear is always ok.
175 match fulfill_cx
.select_all_or_error(infcx
) {
178 "type_known_to_meet_bound_modulo_regions: ty={:?} bound={} success",
180 infcx
.tcx
.def_path_str(def_id
)
186 "type_known_to_meet_bound_modulo_regions: ty={:?} bound={} errors={:?}",
188 infcx
.tcx
.def_path_str(def_id
),
199 fn do_normalize_predicates
<'tcx
>(
201 region_context
: DefId
,
202 cause
: ObligationCause
<'tcx
>,
203 elaborated_env
: ty
::ParamEnv
<'tcx
>,
204 predicates
: Vec
<ty
::Predicate
<'tcx
>>,
205 ) -> Result
<Vec
<ty
::Predicate
<'tcx
>>, ErrorReported
> {
207 "do_normalize_predicates(predicates={:?}, region_context={:?}, cause={:?})",
208 predicates
, region_context
, cause
,
210 let span
= cause
.span
;
211 tcx
.infer_ctxt().enter(|infcx
| {
212 // FIXME. We should really... do something with these region
213 // obligations. But this call just continues the older
214 // behavior (i.e., doesn't cause any new bugs), and it would
215 // take some further refactoring to actually solve them. In
216 // particular, we would have to handle implied bounds
217 // properly, and that code is currently largely confined to
218 // regionck (though I made some efforts to extract it
221 // @arielby: In any case, these obligations are checked
222 // by wfcheck anyway, so I'm not sure we have to check
223 // them here too, and we will remove this function when
224 // we move over to lazy normalization *anyway*.
225 let fulfill_cx
= FulfillmentContext
::new_ignoring_regions();
227 match fully_normalize(&infcx
, fulfill_cx
, cause
, elaborated_env
, predicates
) {
228 Ok(predicates
) => predicates
,
230 infcx
.report_fulfillment_errors(&errors
, None
, false);
231 return Err(ErrorReported
);
235 debug
!("do_normalize_predictes: normalized predicates = {:?}", predicates
);
237 // We can use the `elaborated_env` here; the region code only
238 // cares about declarations like `'a: 'b`.
239 let outlives_env
= OutlivesEnvironment
::new(elaborated_env
);
241 infcx
.resolve_regions_and_report_errors(
244 RegionckMode
::default(),
247 let predicates
= match infcx
.fully_resolve(predicates
) {
248 Ok(predicates
) => predicates
,
250 // If we encounter a fixup error, it means that some type
251 // variable wound up unconstrained. I actually don't know
252 // if this can happen, and I certainly don't expect it to
253 // happen often, but if it did happen it probably
254 // represents a legitimate failure due to some kind of
255 // unconstrained variable, and it seems better not to ICE,
256 // all things considered.
257 tcx
.sess
.span_err(span
, &fixup_err
.to_string());
258 return Err(ErrorReported
);
261 if predicates
.needs_infer() {
262 tcx
.sess
.delay_span_bug(span
, "encountered inference variables after `fully_resolve`");
270 // FIXME: this is gonna need to be removed ...
271 /// Normalizes the parameter environment, reporting errors if they occur.
272 pub fn normalize_param_env_or_error
<'tcx
>(
274 region_context
: DefId
,
275 unnormalized_env
: ty
::ParamEnv
<'tcx
>,
276 cause
: ObligationCause
<'tcx
>,
277 ) -> ty
::ParamEnv
<'tcx
> {
278 // I'm not wild about reporting errors here; I'd prefer to
279 // have the errors get reported at a defined place (e.g.,
280 // during typeck). Instead I have all parameter
281 // environments, in effect, going through this function
282 // and hence potentially reporting errors. This ensures of
283 // course that we never forget to normalize (the
284 // alternative seemed like it would involve a lot of
285 // manual invocations of this fn -- and then we'd have to
286 // deal with the errors at each of those sites).
288 // In any case, in practice, typeck constructs all the
289 // parameter environments once for every fn as it goes,
290 // and errors will get reported then; so after typeck we
291 // can be sure that no errors should occur.
294 "normalize_param_env_or_error(region_context={:?}, unnormalized_env={:?}, cause={:?})",
295 region_context
, unnormalized_env
, cause
298 let mut predicates
: Vec
<_
> =
299 util
::elaborate_predicates(tcx
, unnormalized_env
.caller_bounds().into_iter())
300 .map(|obligation
| obligation
.predicate
)
303 debug
!("normalize_param_env_or_error: elaborated-predicates={:?}", predicates
);
306 ty
::ParamEnv
::new(tcx
.intern_predicates(&predicates
), unnormalized_env
.reveal());
308 // HACK: we are trying to normalize the param-env inside *itself*. The problem is that
309 // normalization expects its param-env to be already normalized, which means we have
312 // The way we handle this is by normalizing the param-env inside an unnormalized version
313 // of the param-env, which means that if the param-env contains unnormalized projections,
314 // we'll have some normalization failures. This is unfortunate.
316 // Lazy normalization would basically handle this by treating just the
317 // normalizing-a-trait-ref-requires-itself cycles as evaluation failures.
319 // Inferred outlives bounds can create a lot of `TypeOutlives` predicates for associated
320 // types, so to make the situation less bad, we normalize all the predicates *but*
321 // the `TypeOutlives` predicates first inside the unnormalized parameter environment, and
322 // then we normalize the `TypeOutlives` bounds inside the normalized parameter environment.
324 // This works fairly well because trait matching does not actually care about param-env
325 // TypeOutlives predicates - these are normally used by regionck.
326 let outlives_predicates
: Vec
<_
> = predicates
327 .drain_filter(|predicate
| {
328 matches
!(predicate
.kind().skip_binder(), ty
::PredicateKind
::TypeOutlives(..))
333 "normalize_param_env_or_error: predicates=(non-outlives={:?}, outlives={:?})",
334 predicates
, outlives_predicates
336 let non_outlives_predicates
= match do_normalize_predicates(
343 Ok(predicates
) => predicates
,
344 // An unnormalized env is better than nothing.
345 Err(ErrorReported
) => {
346 debug
!("normalize_param_env_or_error: errored resolving non-outlives predicates");
347 return elaborated_env
;
351 debug
!("normalize_param_env_or_error: non-outlives predicates={:?}", non_outlives_predicates
);
353 // Not sure whether it is better to include the unnormalized TypeOutlives predicates
354 // here. I believe they should not matter, because we are ignoring TypeOutlives param-env
355 // predicates here anyway. Keeping them here anyway because it seems safer.
356 let outlives_env
: Vec
<_
> =
357 non_outlives_predicates
.iter().chain(&outlives_predicates
).cloned().collect();
359 ty
::ParamEnv
::new(tcx
.intern_predicates(&outlives_env
), unnormalized_env
.reveal());
360 let outlives_predicates
= match do_normalize_predicates(
367 Ok(predicates
) => predicates
,
368 // An unnormalized env is better than nothing.
369 Err(ErrorReported
) => {
370 debug
!("normalize_param_env_or_error: errored resolving outlives predicates");
371 return elaborated_env
;
374 debug
!("normalize_param_env_or_error: outlives predicates={:?}", outlives_predicates
);
376 let mut predicates
= non_outlives_predicates
;
377 predicates
.extend(outlives_predicates
);
378 debug
!("normalize_param_env_or_error: final predicates={:?}", predicates
);
379 ty
::ParamEnv
::new(tcx
.intern_predicates(&predicates
), unnormalized_env
.reveal())
382 pub fn fully_normalize
<'a
, 'tcx
, T
>(
383 infcx
: &InferCtxt
<'a
, 'tcx
>,
384 mut fulfill_cx
: FulfillmentContext
<'tcx
>,
385 cause
: ObligationCause
<'tcx
>,
386 param_env
: ty
::ParamEnv
<'tcx
>,
388 ) -> Result
<T
, Vec
<FulfillmentError
<'tcx
>>>
390 T
: TypeFoldable
<'tcx
>,
392 debug
!("fully_normalize_with_fulfillcx(value={:?})", value
);
393 let selcx
= &mut SelectionContext
::new(infcx
);
394 let Normalized { value: normalized_value, obligations }
=
395 project
::normalize(selcx
, param_env
, cause
, value
);
397 "fully_normalize: normalized_value={:?} obligations={:?}",
398 normalized_value
, obligations
400 for obligation
in obligations
{
401 fulfill_cx
.register_predicate_obligation(selcx
.infcx(), obligation
);
404 debug
!("fully_normalize: select_all_or_error start");
405 fulfill_cx
.select_all_or_error(infcx
)?
;
406 debug
!("fully_normalize: select_all_or_error complete");
407 let resolved_value
= infcx
.resolve_vars_if_possible(normalized_value
);
408 debug
!("fully_normalize: resolved_value={:?}", resolved_value
);
412 /// Normalizes the predicates and checks whether they hold in an empty environment. If this
413 /// returns true, then either normalize encountered an error or one of the predicates did not
414 /// hold. Used when creating vtables to check for unsatisfiable methods.
415 pub fn impossible_predicates
<'tcx
>(
417 predicates
: Vec
<ty
::Predicate
<'tcx
>>,
419 debug
!("impossible_predicates(predicates={:?})", predicates
);
421 let result
= tcx
.infer_ctxt().enter(|infcx
| {
422 let param_env
= ty
::ParamEnv
::reveal_all();
423 let mut selcx
= SelectionContext
::new(&infcx
);
424 let mut fulfill_cx
= FulfillmentContext
::new();
425 let cause
= ObligationCause
::dummy();
426 let Normalized { value: predicates, obligations }
=
427 normalize(&mut selcx
, param_env
, cause
.clone(), predicates
);
428 for obligation
in obligations
{
429 fulfill_cx
.register_predicate_obligation(&infcx
, obligation
);
431 for predicate
in predicates
{
432 let obligation
= Obligation
::new(cause
.clone(), param_env
, predicate
);
433 fulfill_cx
.register_predicate_obligation(&infcx
, obligation
);
436 fulfill_cx
.select_all_or_error(&infcx
).is_err()
438 debug
!("impossible_predicates = {:?}", result
);
442 fn subst_and_check_impossible_predicates
<'tcx
>(
444 key
: (DefId
, SubstsRef
<'tcx
>),
446 debug
!("subst_and_check_impossible_predicates(key={:?})", key
);
448 let mut predicates
= tcx
.predicates_of(key
.0).instantiate(tcx
, key
.1).predicates
;
449 predicates
.retain(|predicate
| !predicate
.needs_subst());
450 let result
= impossible_predicates(tcx
, predicates
);
452 debug
!("subst_and_check_impossible_predicates(key={:?}) = {:?}", key
, result
);
456 /// Given a trait `trait_ref`, iterates the vtable entries
457 /// that come from `trait_ref`, including its supertraits.
458 fn vtable_methods
<'tcx
>(
460 trait_ref
: ty
::PolyTraitRef
<'tcx
>,
461 ) -> &'tcx
[Option
<(DefId
, SubstsRef
<'tcx
>)>] {
462 debug
!("vtable_methods({:?})", trait_ref
);
464 tcx
.arena
.alloc_from_iter(supertraits(tcx
, trait_ref
).flat_map(move |trait_ref
| {
465 let trait_methods
= tcx
466 .associated_items(trait_ref
.def_id())
467 .in_definition_order()
468 .filter(|item
| item
.kind
== ty
::AssocKind
::Fn
);
470 // Now list each method's DefId and InternalSubsts (for within its trait).
471 // If the method can never be called from this object, produce None.
472 trait_methods
.map(move |trait_method
| {
473 debug
!("vtable_methods: trait_method={:?}", trait_method
);
474 let def_id
= trait_method
.def_id
;
476 // Some methods cannot be called on an object; skip those.
477 if !is_vtable_safe_method(tcx
, trait_ref
.def_id(), &trait_method
) {
478 debug
!("vtable_methods: not vtable safe");
482 // The method may have some early-bound lifetimes; add regions for those.
483 let substs
= trait_ref
.map_bound(|trait_ref
| {
484 InternalSubsts
::for_item(tcx
, def_id
, |param
, _
| match param
.kind
{
485 GenericParamDefKind
::Lifetime
=> tcx
.lifetimes
.re_erased
.into(),
486 GenericParamDefKind
::Type { .. }
| GenericParamDefKind
::Const { .. }
=> {
487 trait_ref
.substs
[param
.index
as usize]
492 // The trait type may have higher-ranked lifetimes in it;
493 // erase them if they appear, so that we get the type
494 // at some particular call site.
496 tcx
.normalize_erasing_late_bound_regions(ty
::ParamEnv
::reveal_all(), substs
);
498 // It's possible that the method relies on where-clauses that
499 // do not hold for this particular set of type parameters.
500 // Note that this method could then never be called, so we
501 // do not want to try and codegen it, in that case (see #23435).
502 let predicates
= tcx
.predicates_of(def_id
).instantiate_own(tcx
, substs
);
503 if impossible_predicates(tcx
, predicates
.predicates
) {
504 debug
!("vtable_methods: predicates do not hold");
508 Some((def_id
, substs
))
513 /// Check whether a `ty` implements given trait(trait_def_id).
515 /// NOTE: Always return `false` for a type which needs inference.
516 fn type_implements_trait
<'tcx
>(
519 DefId
, // trait_def_id,
525 let (trait_def_id
, ty
, params
, param_env
) = key
;
528 "type_implements_trait: trait_def_id={:?}, type={:?}, params={:?}, param_env={:?}",
529 trait_def_id
, ty
, params
, param_env
532 let trait_ref
= ty
::TraitRef { def_id: trait_def_id, substs: tcx.mk_substs_trait(ty, params) }
;
534 let obligation
= Obligation
{
535 cause
: ObligationCause
::dummy(),
538 predicate
: trait_ref
.without_const().to_predicate(tcx
),
540 tcx
.infer_ctxt().enter(|infcx
| infcx
.predicate_must_hold_modulo_regions(&obligation
))
543 pub fn provide(providers
: &mut ty
::query
::Providers
) {
544 object_safety
::provide(providers
);
545 structural_match
::provide(providers
);
546 *providers
= ty
::query
::Providers
{
547 specialization_graph_of
: specialize
::specialization_graph_provider
,
548 specializes
: specialize
::specializes
,
549 codegen_fulfill_obligation
: codegen
::codegen_fulfill_obligation
,
551 type_implements_trait
,
552 subst_and_check_impossible_predicates
,
553 mir_abstract_const
: |tcx
, def_id
| {
554 let def_id
= def_id
.expect_local();
555 if let Some(def
) = ty
::WithOptConstParam
::try_lookup(def_id
, tcx
) {
556 tcx
.mir_abstract_const_of_const_arg(def
)
558 const_evaluatable
::mir_abstract_const(tcx
, ty
::WithOptConstParam
::unknown(def_id
))
561 mir_abstract_const_of_const_arg
: |tcx
, (did
, param_did
)| {
562 const_evaluatable
::mir_abstract_const(
564 ty
::WithOptConstParam { did, const_param_did: Some(param_did) }
,
567 try_unify_abstract_consts
: const_evaluatable
::try_unify_abstract_consts
,