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
10 pub mod error_reporting
;
23 use crate::infer
::outlives
::env
::OutlivesEnvironment
;
24 use crate::infer
::{InferCtxt, RegionckMode, TyCtxtInferExt}
;
25 use crate::traits
::error_reporting
::InferCtxtExt
as _
;
26 use crate::traits
::query
::evaluate_obligation
::InferCtxtExt
as _
;
27 use rustc_errors
::ErrorReported
;
29 use rustc_hir
::def_id
::DefId
;
30 use rustc_middle
::middle
::region
;
31 use rustc_middle
::ty
::fold
::TypeFoldable
;
32 use rustc_middle
::ty
::subst
::{InternalSubsts, SubstsRef}
;
33 use rustc_middle
::ty
::{self, GenericParamDefKind, ToPredicate, Ty, TyCtxt, WithConstness}
;
38 pub use self::FulfillmentErrorCode
::*;
39 pub use self::ObligationCauseCode
::*;
40 pub use self::SelectionError
::*;
41 pub use self::Vtable
::*;
43 pub use self::coherence
::{add_placeholder_note, orphan_check, overlapping_impls}
;
44 pub use self::coherence
::{OrphanCheckErr, OverlapResult}
;
45 pub use self::engine
::TraitEngineExt
;
46 pub use self::fulfill
::{FulfillmentContext, PendingPredicateObligation}
;
47 pub use self::object_safety
::astconv_object_safety_violations
;
48 pub use self::object_safety
::is_vtable_safe_method
;
49 pub use self::object_safety
::MethodViolationCode
;
50 pub use self::object_safety
::ObjectSafetyViolation
;
51 pub use self::on_unimplemented
::{OnUnimplementedDirective, OnUnimplementedNote}
;
52 pub use self::project
::{
53 normalize
, normalize_projection_type
, normalize_to
, poly_project_and_unify_type
,
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
::type_marked_structural
;
62 pub use self::structural_match
::NonStructuralMatchTy
;
63 pub use self::util
::{elaborate_predicates, elaborate_trait_ref, elaborate_trait_refs}
;
64 pub use self::util
::{expand_trait_aliases, TraitAliasExpander}
;
66 get_vtable_index_of_object_method
, impl_item_is_final
, predicate_for_trait_def
, upcast_choices
,
69 supertrait_def_ids
, supertraits
, transitive_bounds
, SupertraitDefIds
, Supertraits
,
72 pub use rustc_infer
::traits
::*;
74 /// Whether to skip the leak check, as part of a future compatibility warning step.
75 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
76 pub enum SkipLeakCheck
{
82 fn is_yes(self) -> bool
{
83 self == SkipLeakCheck
::Yes
87 /// The "default" for skip-leak-check corresponds to the current
88 /// behavior (do not skip the leak check) -- not the behavior we are
89 /// transitioning into.
90 impl Default
for SkipLeakCheck
{
91 fn default() -> Self {
96 /// The mode that trait queries run in.
97 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
98 pub enum TraitQueryMode
{
99 // Standard/un-canonicalized queries get accurate
100 // spans etc. passed in and hence can do reasonable
101 // error reporting on their own.
103 // Canonicalized queries get dummy spans and hence
104 // must generally propagate errors to
105 // pre-canonicalization callsites.
109 /// Creates predicate obligations from the generic bounds.
110 pub fn predicates_for_generics
<'tcx
>(
111 cause
: ObligationCause
<'tcx
>,
112 param_env
: ty
::ParamEnv
<'tcx
>,
113 generic_bounds
: ty
::InstantiatedPredicates
<'tcx
>,
114 ) -> impl Iterator
<Item
= PredicateObligation
<'tcx
>> {
115 util
::predicates_for_generics(cause
, 0, param_env
, generic_bounds
)
118 /// Determines whether the type `ty` is known to meet `bound` and
119 /// returns true if so. Returns false if `ty` either does not meet
120 /// `bound` or is not known to meet bound (note that this is
121 /// conservative towards *no impl*, which is the opposite of the
122 /// `evaluate` methods).
123 pub fn type_known_to_meet_bound_modulo_regions
<'a
, 'tcx
>(
124 infcx
: &InferCtxt
<'a
, 'tcx
>,
125 param_env
: ty
::ParamEnv
<'tcx
>,
131 "type_known_to_meet_bound_modulo_regions(ty={:?}, bound={:?})",
133 infcx
.tcx
.def_path_str(def_id
)
136 let trait_ref
= ty
::TraitRef { def_id, substs: infcx.tcx.mk_substs_trait(ty, &[]) }
;
137 let obligation
= Obligation
{
139 cause
: ObligationCause
::misc(span
, hir
::CRATE_HIR_ID
),
141 predicate
: trait_ref
.without_const().to_predicate(),
144 let result
= infcx
.predicate_must_hold_modulo_regions(&obligation
);
146 "type_known_to_meet_ty={:?} bound={} => {:?}",
148 infcx
.tcx
.def_path_str(def_id
),
152 if result
&& ty
.has_infer_types_or_consts() {
153 // Because of inference "guessing", selection can sometimes claim
154 // to succeed while the success requires a guess. To ensure
155 // this function's result remains infallible, we must confirm
156 // that guess. While imperfect, I believe this is sound.
158 // The handling of regions in this area of the code is terrible,
159 // see issue #29149. We should be able to improve on this with
161 let mut fulfill_cx
= FulfillmentContext
::new_ignoring_regions();
163 // We can use a dummy node-id here because we won't pay any mind
164 // to region obligations that arise (there shouldn't really be any
166 let cause
= ObligationCause
::misc(span
, hir
::CRATE_HIR_ID
);
168 fulfill_cx
.register_bound(infcx
, param_env
, ty
, def_id
, cause
);
170 // Note: we only assume something is `Copy` if we can
171 // *definitively* show that it implements `Copy`. Otherwise,
172 // assume it is move; linear is always ok.
173 match fulfill_cx
.select_all_or_error(infcx
) {
176 "type_known_to_meet_bound_modulo_regions: ty={:?} bound={} success",
178 infcx
.tcx
.def_path_str(def_id
)
184 "type_known_to_meet_bound_modulo_regions: ty={:?} bound={} errors={:?}",
186 infcx
.tcx
.def_path_str(def_id
),
197 fn do_normalize_predicates
<'tcx
>(
199 region_context
: DefId
,
200 cause
: ObligationCause
<'tcx
>,
201 elaborated_env
: ty
::ParamEnv
<'tcx
>,
202 predicates
: Vec
<ty
::Predicate
<'tcx
>>,
203 ) -> Result
<Vec
<ty
::Predicate
<'tcx
>>, ErrorReported
> {
205 "do_normalize_predicates(predicates={:?}, region_context={:?}, cause={:?})",
206 predicates
, region_context
, cause
,
208 let span
= cause
.span
;
209 tcx
.infer_ctxt().enter(|infcx
| {
210 // FIXME. We should really... do something with these region
211 // obligations. But this call just continues the older
212 // behavior (i.e., doesn't cause any new bugs), and it would
213 // take some further refactoring to actually solve them. In
214 // particular, we would have to handle implied bounds
215 // properly, and that code is currently largely confined to
216 // regionck (though I made some efforts to extract it
219 // @arielby: In any case, these obligations are checked
220 // by wfcheck anyway, so I'm not sure we have to check
221 // them here too, and we will remove this function when
222 // we move over to lazy normalization *anyway*.
223 let fulfill_cx
= FulfillmentContext
::new_ignoring_regions();
225 match fully_normalize(&infcx
, fulfill_cx
, cause
, elaborated_env
, &predicates
) {
226 Ok(predicates
) => predicates
,
228 infcx
.report_fulfillment_errors(&errors
, None
, false);
229 return Err(ErrorReported
);
233 debug
!("do_normalize_predictes: normalized predicates = {:?}", predicates
);
235 let region_scope_tree
= region
::ScopeTree
::default();
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(
245 RegionckMode
::default(),
248 let predicates
= match infcx
.fully_resolve(&predicates
) {
249 Ok(predicates
) => predicates
,
251 // If we encounter a fixup error, it means that some type
252 // variable wound up unconstrained. I actually don't know
253 // if this can happen, and I certainly don't expect it to
254 // happen often, but if it did happen it probably
255 // represents a legitimate failure due to some kind of
256 // unconstrained variable, and it seems better not to ICE,
257 // all things considered.
258 tcx
.sess
.span_err(span
, &fixup_err
.to_string());
259 return Err(ErrorReported
);
262 if predicates
.needs_infer() {
263 tcx
.sess
.delay_span_bug(span
, "encountered inference variables after `fully_resolve`");
271 // FIXME: this is gonna need to be removed ...
272 /// Normalizes the parameter environment, reporting errors if they occur.
273 pub fn normalize_param_env_or_error
<'tcx
>(
275 region_context
: DefId
,
276 unnormalized_env
: ty
::ParamEnv
<'tcx
>,
277 cause
: ObligationCause
<'tcx
>,
278 ) -> ty
::ParamEnv
<'tcx
> {
279 // I'm not wild about reporting errors here; I'd prefer to
280 // have the errors get reported at a defined place (e.g.,
281 // during typeck). Instead I have all parameter
282 // environments, in effect, going through this function
283 // and hence potentially reporting errors. This ensures of
284 // course that we never forget to normalize (the
285 // alternative seemed like it would involve a lot of
286 // manual invocations of this fn -- and then we'd have to
287 // deal with the errors at each of those sites).
289 // In any case, in practice, typeck constructs all the
290 // parameter environments once for every fn as it goes,
291 // and errors will get reported then; so after typeck we
292 // can be sure that no errors should occur.
295 "normalize_param_env_or_error(region_context={:?}, unnormalized_env={:?}, cause={:?})",
296 region_context
, unnormalized_env
, cause
299 let mut predicates
: Vec
<_
> =
300 util
::elaborate_predicates(tcx
, unnormalized_env
.caller_bounds
.into_iter().cloned())
301 .map(|obligation
| obligation
.predicate
)
304 debug
!("normalize_param_env_or_error: elaborated-predicates={:?}", predicates
);
306 let elaborated_env
= ty
::ParamEnv
::new(
307 tcx
.intern_predicates(&predicates
),
308 unnormalized_env
.reveal
,
309 unnormalized_env
.def_id
,
312 // HACK: we are trying to normalize the param-env inside *itself*. The problem is that
313 // normalization expects its param-env to be already normalized, which means we have
316 // The way we handle this is by normalizing the param-env inside an unnormalized version
317 // of the param-env, which means that if the param-env contains unnormalized projections,
318 // we'll have some normalization failures. This is unfortunate.
320 // Lazy normalization would basically handle this by treating just the
321 // normalizing-a-trait-ref-requires-itself cycles as evaluation failures.
323 // Inferred outlives bounds can create a lot of `TypeOutlives` predicates for associated
324 // types, so to make the situation less bad, we normalize all the predicates *but*
325 // the `TypeOutlives` predicates first inside the unnormalized parameter environment, and
326 // then we normalize the `TypeOutlives` bounds inside the normalized parameter environment.
328 // This works fairly well because trait matching does not actually care about param-env
329 // TypeOutlives predicates - these are normally used by regionck.
330 let outlives_predicates
: Vec
<_
> = predicates
331 .drain_filter(|predicate
| match predicate
{
332 ty
::Predicate
::TypeOutlives(..) => true,
338 "normalize_param_env_or_error: predicates=(non-outlives={:?}, outlives={:?})",
339 predicates
, outlives_predicates
341 let non_outlives_predicates
= match do_normalize_predicates(
348 Ok(predicates
) => predicates
,
349 // An unnormalized env is better than nothing.
350 Err(ErrorReported
) => {
351 debug
!("normalize_param_env_or_error: errored resolving non-outlives predicates");
352 return elaborated_env
;
356 debug
!("normalize_param_env_or_error: non-outlives predicates={:?}", non_outlives_predicates
);
358 // Not sure whether it is better to include the unnormalized TypeOutlives predicates
359 // here. I believe they should not matter, because we are ignoring TypeOutlives param-env
360 // predicates here anyway. Keeping them here anyway because it seems safer.
361 let outlives_env
: Vec
<_
> =
362 non_outlives_predicates
.iter().chain(&outlives_predicates
).cloned().collect();
364 ty
::ParamEnv
::new(tcx
.intern_predicates(&outlives_env
), unnormalized_env
.reveal
, None
);
365 let outlives_predicates
= match do_normalize_predicates(
372 Ok(predicates
) => predicates
,
373 // An unnormalized env is better than nothing.
374 Err(ErrorReported
) => {
375 debug
!("normalize_param_env_or_error: errored resolving outlives predicates");
376 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
);
385 tcx
.intern_predicates(&predicates
),
386 unnormalized_env
.reveal
,
387 unnormalized_env
.def_id
,
391 pub fn fully_normalize
<'a
, 'tcx
, T
>(
392 infcx
: &InferCtxt
<'a
, 'tcx
>,
393 mut fulfill_cx
: FulfillmentContext
<'tcx
>,
394 cause
: ObligationCause
<'tcx
>,
395 param_env
: ty
::ParamEnv
<'tcx
>,
397 ) -> Result
<T
, Vec
<FulfillmentError
<'tcx
>>>
399 T
: TypeFoldable
<'tcx
>,
401 debug
!("fully_normalize_with_fulfillcx(value={:?})", value
);
402 let selcx
= &mut SelectionContext
::new(infcx
);
403 let Normalized { value: normalized_value, obligations }
=
404 project
::normalize(selcx
, param_env
, cause
, value
);
406 "fully_normalize: normalized_value={:?} obligations={:?}",
407 normalized_value
, obligations
409 for obligation
in obligations
{
410 fulfill_cx
.register_predicate_obligation(selcx
.infcx(), obligation
);
413 debug
!("fully_normalize: select_all_or_error start");
414 fulfill_cx
.select_all_or_error(infcx
)?
;
415 debug
!("fully_normalize: select_all_or_error complete");
416 let resolved_value
= infcx
.resolve_vars_if_possible(&normalized_value
);
417 debug
!("fully_normalize: resolved_value={:?}", resolved_value
);
421 /// Normalizes the predicates and checks whether they hold in an empty
422 /// environment. If this returns false, then either normalize
423 /// encountered an error or one of the predicates did not hold. Used
424 /// when creating vtables to check for unsatisfiable methods.
425 pub fn normalize_and_test_predicates
<'tcx
>(
427 predicates
: Vec
<ty
::Predicate
<'tcx
>>,
429 debug
!("normalize_and_test_predicates(predicates={:?})", predicates
);
431 let result
= tcx
.infer_ctxt().enter(|infcx
| {
432 let param_env
= ty
::ParamEnv
::reveal_all();
433 let mut selcx
= SelectionContext
::new(&infcx
);
434 let mut fulfill_cx
= FulfillmentContext
::new();
435 let cause
= ObligationCause
::dummy();
436 let Normalized { value: predicates, obligations }
=
437 normalize(&mut selcx
, param_env
, cause
.clone(), &predicates
);
438 for obligation
in obligations
{
439 fulfill_cx
.register_predicate_obligation(&infcx
, obligation
);
441 for predicate
in predicates
{
442 let obligation
= Obligation
::new(cause
.clone(), param_env
, predicate
);
443 fulfill_cx
.register_predicate_obligation(&infcx
, obligation
);
446 fulfill_cx
.select_all_or_error(&infcx
).is_ok()
448 debug
!("normalize_and_test_predicates(predicates={:?}) = {:?}", predicates
, result
);
452 fn substitute_normalize_and_test_predicates
<'tcx
>(
454 key
: (DefId
, SubstsRef
<'tcx
>),
456 debug
!("substitute_normalize_and_test_predicates(key={:?})", key
);
458 let predicates
= tcx
.predicates_of(key
.0).instantiate(tcx
, key
.1).predicates
;
459 let result
= normalize_and_test_predicates(tcx
, predicates
);
461 debug
!("substitute_normalize_and_test_predicates(key={:?}) = {:?}", key
, result
);
465 /// Given a trait `trait_ref`, iterates the vtable entries
466 /// that come from `trait_ref`, including its supertraits.
467 #[inline] // FIXME(#35870): avoid closures being unexported due to `impl Trait`.
468 fn vtable_methods
<'tcx
>(
470 trait_ref
: ty
::PolyTraitRef
<'tcx
>,
471 ) -> &'tcx
[Option
<(DefId
, SubstsRef
<'tcx
>)>] {
472 debug
!("vtable_methods({:?})", trait_ref
);
474 tcx
.arena
.alloc_from_iter(supertraits(tcx
, trait_ref
).flat_map(move |trait_ref
| {
475 let trait_methods
= tcx
476 .associated_items(trait_ref
.def_id())
477 .in_definition_order()
478 .filter(|item
| item
.kind
== ty
::AssocKind
::Fn
);
480 // Now list each method's DefId and InternalSubsts (for within its trait).
481 // If the method can never be called from this object, produce None.
482 trait_methods
.map(move |trait_method
| {
483 debug
!("vtable_methods: trait_method={:?}", trait_method
);
484 let def_id
= trait_method
.def_id
;
486 // Some methods cannot be called on an object; skip those.
487 if !is_vtable_safe_method(tcx
, trait_ref
.def_id(), &trait_method
) {
488 debug
!("vtable_methods: not vtable safe");
492 // The method may have some early-bound lifetimes; add regions for those.
493 let substs
= trait_ref
.map_bound(|trait_ref
| {
494 InternalSubsts
::for_item(tcx
, def_id
, |param
, _
| match param
.kind
{
495 GenericParamDefKind
::Lifetime
=> tcx
.lifetimes
.re_erased
.into(),
496 GenericParamDefKind
::Type { .. }
| GenericParamDefKind
::Const
=> {
497 trait_ref
.substs
[param
.index
as usize]
502 // The trait type may have higher-ranked lifetimes in it;
503 // erase them if they appear, so that we get the type
504 // at some particular call site.
506 tcx
.normalize_erasing_late_bound_regions(ty
::ParamEnv
::reveal_all(), &substs
);
508 // It's possible that the method relies on where-clauses that
509 // do not hold for this particular set of type parameters.
510 // Note that this method could then never be called, so we
511 // do not want to try and codegen it, in that case (see #23435).
512 let predicates
= tcx
.predicates_of(def_id
).instantiate_own(tcx
, substs
);
513 if !normalize_and_test_predicates(tcx
, predicates
.predicates
) {
514 debug
!("vtable_methods: predicates do not hold");
518 Some((def_id
, substs
))
523 pub fn provide(providers
: &mut ty
::query
::Providers
<'_
>) {
524 object_safety
::provide(providers
);
525 *providers
= ty
::query
::Providers
{
526 specialization_graph_of
: specialize
::specialization_graph_provider
,
527 specializes
: specialize
::specializes
,
528 codegen_fulfill_obligation
: codegen
::codegen_fulfill_obligation
,
530 substitute_normalize_and_test_predicates
,