]> git.lizzy.rs Git - rust.git/blob - compiler/rustc_trait_selection/src/traits/mod.rs
Merge commit '4c41a222ca5d1325fb4b6709395bd06e766cc042' into clippyup
[rust.git] / compiler / rustc_trait_selection / src / traits / mod.rs
1 //! Trait Resolution. See the [rustc dev guide] for more information on how this works.
2 //!
3 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html
4
5 pub mod auto_trait;
6 mod chalk_fulfill;
7 pub mod codegen;
8 mod coherence;
9 pub mod const_evaluatable;
10 mod engine;
11 pub mod error_reporting;
12 mod fulfill;
13 pub mod misc;
14 mod object_safety;
15 mod on_unimplemented;
16 mod project;
17 pub mod query;
18 mod select;
19 mod specialize;
20 mod structural_match;
21 mod util;
22 pub mod wf;
23
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;
29 use rustc_hir as hir;
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, ToPredicate, Ty, TyCtxt, VtblEntry, WithConstness,
35     COMMON_VTABLE_ENTRIES,
36 };
37 use rustc_span::Span;
38
39 use std::fmt::Debug;
40
41 pub use self::FulfillmentErrorCode::*;
42 pub use self::ImplSource::*;
43 pub use self::ObligationCauseCode::*;
44 pub use self::SelectionError::*;
45
46 pub use self::coherence::{add_placeholder_note, orphan_check, overlapping_impls};
47 pub use self::coherence::{OrphanCheckErr, OverlapResult};
48 pub use self::engine::TraitEngineExt;
49 pub use self::fulfill::{FulfillmentContext, PendingPredicateObligation};
50 pub use self::object_safety::astconv_object_safety_violations;
51 pub use self::object_safety::is_vtable_safe_method;
52 pub use self::object_safety::MethodViolationCode;
53 pub use self::object_safety::ObjectSafetyViolation;
54 pub use self::on_unimplemented::{OnUnimplementedDirective, OnUnimplementedNote};
55 pub use self::project::{normalize, normalize_projection_type, normalize_to};
56 pub use self::select::{EvaluationCache, SelectionCache, SelectionContext};
57 pub use self::select::{EvaluationResult, IntercrateAmbiguityCause, OverflowError};
58 pub use self::specialize::specialization_graph::FutureCompatOverlapError;
59 pub use self::specialize::specialization_graph::FutureCompatOverlapErrorKind;
60 pub use self::specialize::{specialization_graph, translate_substs, OverlapError};
61 pub use self::structural_match::search_for_structural_match_violation;
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};
65 pub use self::util::{
66     get_vtable_index_of_object_method, impl_item_is_final, predicate_for_trait_def, upcast_choices,
67 };
68 pub use self::util::{
69     supertrait_def_ids, supertraits, transitive_bounds, transitive_bounds_that_define_assoc_type,
70     SupertraitDefIds, Supertraits,
71 };
72
73 pub use self::chalk_fulfill::FulfillmentContext as ChalkFulfillmentContext;
74
75 pub use rustc_infer::traits::*;
76
77 /// Whether to skip the leak check, as part of a future compatibility warning step.
78 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
79 pub enum SkipLeakCheck {
80     Yes,
81     No,
82 }
83
84 impl SkipLeakCheck {
85     fn is_yes(self) -> bool {
86         self == SkipLeakCheck::Yes
87     }
88 }
89
90 /// The "default" for skip-leak-check corresponds to the current
91 /// behavior (do not skip the leak check) -- not the behavior we are
92 /// transitioning into.
93 impl Default for SkipLeakCheck {
94     fn default() -> Self {
95         SkipLeakCheck::No
96     }
97 }
98
99 /// The mode that trait queries run in.
100 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
101 pub enum TraitQueryMode {
102     /// Standard/un-canonicalized queries get accurate
103     /// spans etc. passed in and hence can do reasonable
104     /// error reporting on their own.
105     Standard,
106     /// Canonicalized queries get dummy spans and hence
107     /// must generally propagate errors to
108     /// pre-canonicalization callsites.
109     Canonical,
110 }
111
112 /// Creates predicate obligations from the generic bounds.
113 pub fn predicates_for_generics<'tcx>(
114     cause: ObligationCause<'tcx>,
115     param_env: ty::ParamEnv<'tcx>,
116     generic_bounds: ty::InstantiatedPredicates<'tcx>,
117 ) -> impl Iterator<Item = PredicateObligation<'tcx>> {
118     util::predicates_for_generics(cause, 0, param_env, generic_bounds)
119 }
120
121 /// Determines whether the type `ty` is known to meet `bound` and
122 /// returns true if so. Returns false if `ty` either does not meet
123 /// `bound` or is not known to meet bound (note that this is
124 /// conservative towards *no impl*, which is the opposite of the
125 /// `evaluate` methods).
126 pub fn type_known_to_meet_bound_modulo_regions<'a, 'tcx>(
127     infcx: &InferCtxt<'a, 'tcx>,
128     param_env: ty::ParamEnv<'tcx>,
129     ty: Ty<'tcx>,
130     def_id: DefId,
131     span: Span,
132 ) -> bool {
133     debug!(
134         "type_known_to_meet_bound_modulo_regions(ty={:?}, bound={:?})",
135         ty,
136         infcx.tcx.def_path_str(def_id)
137     );
138
139     let trait_ref = ty::TraitRef { def_id, substs: infcx.tcx.mk_substs_trait(ty, &[]) };
140     let obligation = Obligation {
141         param_env,
142         cause: ObligationCause::misc(span, hir::CRATE_HIR_ID),
143         recursion_depth: 0,
144         predicate: trait_ref.without_const().to_predicate(infcx.tcx),
145     };
146
147     let result = infcx.predicate_must_hold_modulo_regions(&obligation);
148     debug!(
149         "type_known_to_meet_ty={:?} bound={} => {:?}",
150         ty,
151         infcx.tcx.def_path_str(def_id),
152         result
153     );
154
155     if result && ty.has_infer_types_or_consts() {
156         // Because of inference "guessing", selection can sometimes claim
157         // to succeed while the success requires a guess. To ensure
158         // this function's result remains infallible, we must confirm
159         // that guess. While imperfect, I believe this is sound.
160
161         // The handling of regions in this area of the code is terrible,
162         // see issue #29149. We should be able to improve on this with
163         // NLL.
164         let mut fulfill_cx = FulfillmentContext::new_ignoring_regions();
165
166         // We can use a dummy node-id here because we won't pay any mind
167         // to region obligations that arise (there shouldn't really be any
168         // anyhow).
169         let cause = ObligationCause::misc(span, hir::CRATE_HIR_ID);
170
171         fulfill_cx.register_bound(infcx, param_env, ty, def_id, cause);
172
173         // Note: we only assume something is `Copy` if we can
174         // *definitively* show that it implements `Copy`. Otherwise,
175         // assume it is move; linear is always ok.
176         match fulfill_cx.select_all_or_error(infcx) {
177             Ok(()) => {
178                 debug!(
179                     "type_known_to_meet_bound_modulo_regions: ty={:?} bound={} success",
180                     ty,
181                     infcx.tcx.def_path_str(def_id)
182                 );
183                 true
184             }
185             Err(e) => {
186                 debug!(
187                     "type_known_to_meet_bound_modulo_regions: ty={:?} bound={} errors={:?}",
188                     ty,
189                     infcx.tcx.def_path_str(def_id),
190                     e
191                 );
192                 false
193             }
194         }
195     } else {
196         result
197     }
198 }
199
200 fn do_normalize_predicates<'tcx>(
201     tcx: TyCtxt<'tcx>,
202     region_context: DefId,
203     cause: ObligationCause<'tcx>,
204     elaborated_env: ty::ParamEnv<'tcx>,
205     predicates: Vec<ty::Predicate<'tcx>>,
206 ) -> Result<Vec<ty::Predicate<'tcx>>, ErrorReported> {
207     debug!(
208         "do_normalize_predicates(predicates={:?}, region_context={:?}, cause={:?})",
209         predicates, region_context, cause,
210     );
211     let span = cause.span;
212     tcx.infer_ctxt().enter(|infcx| {
213         // FIXME. We should really... do something with these region
214         // obligations. But this call just continues the older
215         // behavior (i.e., doesn't cause any new bugs), and it would
216         // take some further refactoring to actually solve them. In
217         // particular, we would have to handle implied bounds
218         // properly, and that code is currently largely confined to
219         // regionck (though I made some efforts to extract it
220         // out). -nmatsakis
221         //
222         // @arielby: In any case, these obligations are checked
223         // by wfcheck anyway, so I'm not sure we have to check
224         // them here too, and we will remove this function when
225         // we move over to lazy normalization *anyway*.
226         let fulfill_cx = FulfillmentContext::new_ignoring_regions();
227         let predicates =
228             match fully_normalize(&infcx, fulfill_cx, cause, elaborated_env, predicates) {
229                 Ok(predicates) => predicates,
230                 Err(errors) => {
231                     infcx.report_fulfillment_errors(&errors, None, false);
232                     return Err(ErrorReported);
233                 }
234             };
235
236         debug!("do_normalize_predictes: normalized predicates = {:?}", predicates);
237
238         // We can use the `elaborated_env` here; the region code only
239         // cares about declarations like `'a: 'b`.
240         let outlives_env = OutlivesEnvironment::new(elaborated_env);
241
242         infcx.resolve_regions_and_report_errors(
243             region_context,
244             &outlives_env,
245             RegionckMode::default(),
246         );
247
248         let predicates = match infcx.fully_resolve(predicates) {
249             Ok(predicates) => predicates,
250             Err(fixup_err) => {
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);
260             }
261         };
262         if predicates.needs_infer() {
263             tcx.sess.delay_span_bug(span, "encountered inference variables after `fully_resolve`");
264             Err(ErrorReported)
265         } else {
266             Ok(predicates)
267         }
268     })
269 }
270
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>(
274     tcx: TyCtxt<'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).
288     //
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.
293
294     debug!(
295         "normalize_param_env_or_error(region_context={:?}, unnormalized_env={:?}, cause={:?})",
296         region_context, unnormalized_env, cause
297     );
298
299     let mut predicates: Vec<_> =
300         util::elaborate_predicates(tcx, unnormalized_env.caller_bounds().into_iter())
301             .map(|obligation| obligation.predicate)
302             .collect();
303
304     debug!("normalize_param_env_or_error: elaborated-predicates={:?}", predicates);
305
306     let elaborated_env =
307         ty::ParamEnv::new(tcx.intern_predicates(&predicates), unnormalized_env.reveal());
308
309     // HACK: we are trying to normalize the param-env inside *itself*. The problem is that
310     // normalization expects its param-env to be already normalized, which means we have
311     // a circularity.
312     //
313     // The way we handle this is by normalizing the param-env inside an unnormalized version
314     // of the param-env, which means that if the param-env contains unnormalized projections,
315     // we'll have some normalization failures. This is unfortunate.
316     //
317     // Lazy normalization would basically handle this by treating just the
318     // normalizing-a-trait-ref-requires-itself cycles as evaluation failures.
319     //
320     // Inferred outlives bounds can create a lot of `TypeOutlives` predicates for associated
321     // types, so to make the situation less bad, we normalize all the predicates *but*
322     // the `TypeOutlives` predicates first inside the unnormalized parameter environment, and
323     // then we normalize the `TypeOutlives` bounds inside the normalized parameter environment.
324     //
325     // This works fairly well because trait matching  does not actually care about param-env
326     // TypeOutlives predicates - these are normally used by regionck.
327     let outlives_predicates: Vec<_> = predicates
328         .drain_filter(|predicate| {
329             matches!(predicate.kind().skip_binder(), ty::PredicateKind::TypeOutlives(..))
330         })
331         .collect();
332
333     debug!(
334         "normalize_param_env_or_error: predicates=(non-outlives={:?}, outlives={:?})",
335         predicates, outlives_predicates
336     );
337     let non_outlives_predicates = match do_normalize_predicates(
338         tcx,
339         region_context,
340         cause.clone(),
341         elaborated_env,
342         predicates,
343     ) {
344         Ok(predicates) => predicates,
345         // An unnormalized env is better than nothing.
346         Err(ErrorReported) => {
347             debug!("normalize_param_env_or_error: errored resolving non-outlives predicates");
348             return elaborated_env;
349         }
350     };
351
352     debug!("normalize_param_env_or_error: non-outlives predicates={:?}", non_outlives_predicates);
353
354     // Not sure whether it is better to include the unnormalized TypeOutlives predicates
355     // here. I believe they should not matter, because we are ignoring TypeOutlives param-env
356     // predicates here anyway. Keeping them here anyway because it seems safer.
357     let outlives_env: Vec<_> =
358         non_outlives_predicates.iter().chain(&outlives_predicates).cloned().collect();
359     let outlives_env =
360         ty::ParamEnv::new(tcx.intern_predicates(&outlives_env), unnormalized_env.reveal());
361     let outlives_predicates = match do_normalize_predicates(
362         tcx,
363         region_context,
364         cause,
365         outlives_env,
366         outlives_predicates,
367     ) {
368         Ok(predicates) => predicates,
369         // An unnormalized env is better than nothing.
370         Err(ErrorReported) => {
371             debug!("normalize_param_env_or_error: errored resolving outlives predicates");
372             return elaborated_env;
373         }
374     };
375     debug!("normalize_param_env_or_error: outlives predicates={:?}", outlives_predicates);
376
377     let mut predicates = non_outlives_predicates;
378     predicates.extend(outlives_predicates);
379     debug!("normalize_param_env_or_error: final predicates={:?}", predicates);
380     ty::ParamEnv::new(tcx.intern_predicates(&predicates), unnormalized_env.reveal())
381 }
382
383 pub fn fully_normalize<'a, 'tcx, T>(
384     infcx: &InferCtxt<'a, 'tcx>,
385     mut fulfill_cx: FulfillmentContext<'tcx>,
386     cause: ObligationCause<'tcx>,
387     param_env: ty::ParamEnv<'tcx>,
388     value: T,
389 ) -> Result<T, Vec<FulfillmentError<'tcx>>>
390 where
391     T: TypeFoldable<'tcx>,
392 {
393     debug!("fully_normalize_with_fulfillcx(value={:?})", value);
394     let selcx = &mut SelectionContext::new(infcx);
395     let Normalized { value: normalized_value, obligations } =
396         project::normalize(selcx, param_env, cause, value);
397     debug!(
398         "fully_normalize: normalized_value={:?} obligations={:?}",
399         normalized_value, obligations
400     );
401     for obligation in obligations {
402         fulfill_cx.register_predicate_obligation(selcx.infcx(), obligation);
403     }
404
405     debug!("fully_normalize: select_all_or_error start");
406     fulfill_cx.select_all_or_error(infcx)?;
407     debug!("fully_normalize: select_all_or_error complete");
408     let resolved_value = infcx.resolve_vars_if_possible(normalized_value);
409     debug!("fully_normalize: resolved_value={:?}", resolved_value);
410     Ok(resolved_value)
411 }
412
413 /// Normalizes the predicates and checks whether they hold in an empty environment. If this
414 /// returns true, then either normalize encountered an error or one of the predicates did not
415 /// hold. Used when creating vtables to check for unsatisfiable methods.
416 pub fn impossible_predicates<'tcx>(
417     tcx: TyCtxt<'tcx>,
418     predicates: Vec<ty::Predicate<'tcx>>,
419 ) -> bool {
420     debug!("impossible_predicates(predicates={:?})", predicates);
421
422     let result = tcx.infer_ctxt().enter(|infcx| {
423         let param_env = ty::ParamEnv::reveal_all();
424         let mut selcx = SelectionContext::new(&infcx);
425         let mut fulfill_cx = FulfillmentContext::new();
426         let cause = ObligationCause::dummy();
427         let Normalized { value: predicates, obligations } =
428             normalize(&mut selcx, param_env, cause.clone(), predicates);
429         for obligation in obligations {
430             fulfill_cx.register_predicate_obligation(&infcx, obligation);
431         }
432         for predicate in predicates {
433             let obligation = Obligation::new(cause.clone(), param_env, predicate);
434             fulfill_cx.register_predicate_obligation(&infcx, obligation);
435         }
436
437         fulfill_cx.select_all_or_error(&infcx).is_err()
438     });
439     debug!("impossible_predicates = {:?}", result);
440     result
441 }
442
443 fn subst_and_check_impossible_predicates<'tcx>(
444     tcx: TyCtxt<'tcx>,
445     key: (DefId, SubstsRef<'tcx>),
446 ) -> bool {
447     debug!("subst_and_check_impossible_predicates(key={:?})", key);
448
449     let mut predicates = tcx.predicates_of(key.0).instantiate(tcx, key.1).predicates;
450     predicates.retain(|predicate| !predicate.needs_subst());
451     let result = impossible_predicates(tcx, predicates);
452
453     debug!("subst_and_check_impossible_predicates(key={:?}) = {:?}", key, result);
454     result
455 }
456
457 /// Given a trait `trait_ref`, iterates the vtable entries
458 /// that come from `trait_ref`, including its supertraits.
459 fn vtable_entries<'tcx>(
460     tcx: TyCtxt<'tcx>,
461     trait_ref: ty::PolyTraitRef<'tcx>,
462 ) -> &'tcx [VtblEntry<'tcx>] {
463     debug!("vtable_entries({:?})", trait_ref);
464
465     let entries = COMMON_VTABLE_ENTRIES.iter().cloned().chain(
466         supertraits(tcx, trait_ref).flat_map(move |trait_ref| {
467             let trait_methods = tcx
468                 .associated_items(trait_ref.def_id())
469                 .in_definition_order()
470                 .filter(|item| item.kind == ty::AssocKind::Fn);
471
472             // Now list each method's DefId and InternalSubsts (for within its trait).
473             // If the method can never be called from this object, produce `Vacant`.
474             trait_methods.map(move |trait_method| {
475                 debug!("vtable_entries: trait_method={:?}", trait_method);
476                 let def_id = trait_method.def_id;
477
478                 // Some methods cannot be called on an object; skip those.
479                 if !is_vtable_safe_method(tcx, trait_ref.def_id(), &trait_method) {
480                     debug!("vtable_entries: not vtable safe");
481                     return VtblEntry::Vacant;
482                 }
483
484                 // The method may have some early-bound lifetimes; add regions for those.
485                 let substs = trait_ref.map_bound(|trait_ref| {
486                     InternalSubsts::for_item(tcx, def_id, |param, _| match param.kind {
487                         GenericParamDefKind::Lifetime => tcx.lifetimes.re_erased.into(),
488                         GenericParamDefKind::Type { .. } | GenericParamDefKind::Const { .. } => {
489                             trait_ref.substs[param.index as usize]
490                         }
491                     })
492                 });
493
494                 // The trait type may have higher-ranked lifetimes in it;
495                 // erase them if they appear, so that we get the type
496                 // at some particular call site.
497                 let substs =
498                     tcx.normalize_erasing_late_bound_regions(ty::ParamEnv::reveal_all(), substs);
499
500                 // It's possible that the method relies on where-clauses that
501                 // do not hold for this particular set of type parameters.
502                 // Note that this method could then never be called, so we
503                 // do not want to try and codegen it, in that case (see #23435).
504                 let predicates = tcx.predicates_of(def_id).instantiate_own(tcx, substs);
505                 if impossible_predicates(tcx, predicates.predicates) {
506                     debug!("vtable_entries: predicates do not hold");
507                     return VtblEntry::Vacant;
508                 }
509
510                 VtblEntry::Method(def_id, substs)
511             })
512         }),
513     );
514
515     tcx.arena.alloc_from_iter(entries)
516 }
517
518 /// Find slot base for trait methods within vtable entries of another trait
519 fn vtable_trait_first_method_offset<'tcx>(
520     tcx: TyCtxt<'tcx>,
521     key: (
522         ty::PolyTraitRef<'tcx>, // trait_to_be_found
523         ty::PolyTraitRef<'tcx>, // trait_owning_vtable
524     ),
525 ) -> usize {
526     let (trait_to_be_found, trait_owning_vtable) = key;
527
528     let mut supertraits = util::supertraits(tcx, trait_owning_vtable);
529
530     // For each of the non-matching predicates that
531     // we pass over, we sum up the set of number of vtable
532     // entries, so that we can compute the offset for the selected
533     // trait.
534     let vtable_base = ty::COMMON_VTABLE_ENTRIES.len()
535         + supertraits
536             .by_ref()
537             .take_while(|t| *t != trait_to_be_found)
538             .map(|t| util::count_own_vtable_entries(tcx, t))
539             .sum::<usize>();
540
541     vtable_base
542 }
543
544 pub fn provide(providers: &mut ty::query::Providers) {
545     object_safety::provide(providers);
546     structural_match::provide(providers);
547     *providers = ty::query::Providers {
548         specialization_graph_of: specialize::specialization_graph_provider,
549         specializes: specialize::specializes,
550         codegen_fulfill_obligation: codegen::codegen_fulfill_obligation,
551         vtable_entries,
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)
557             } else {
558                 const_evaluatable::mir_abstract_const(tcx, ty::WithOptConstParam::unknown(def_id))
559             }
560         },
561         mir_abstract_const_of_const_arg: |tcx, (did, param_did)| {
562             const_evaluatable::mir_abstract_const(
563                 tcx,
564                 ty::WithOptConstParam { did, const_param_did: Some(param_did) },
565             )
566         },
567         try_unify_abstract_consts: const_evaluatable::try_unify_abstract_consts,
568         ..*providers
569     };
570 }