rustc_trait_selection/traits/wf.rs
1//! Core logic responsible for determining what it means for various type system
2//! primitives to be "well formed". Actually checking whether these primitives are
3//! well formed is performed elsewhere (e.g. during type checking or item well formedness
4//! checking).
5
6use std::iter;
7
8use rustc_hir as hir;
9use rustc_hir::def::DefKind;
10use rustc_hir::lang_items::LangItem;
11use rustc_infer::traits::{ObligationCauseCode, PredicateObligations};
12use rustc_middle::bug;
13use rustc_middle::ty::{
14 self, GenericArgsRef, Term, TermKind, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable,
15 TypeVisitableExt, TypeVisitor,
16};
17use rustc_session::parse::feature_err;
18use rustc_span::def_id::{DefId, LocalDefId};
19use rustc_span::{Span, sym};
20use tracing::{debug, instrument, trace};
21
22use crate::infer::InferCtxt;
23use crate::traits;
24
25/// Returns the set of obligations needed to make `arg` well-formed.
26/// If `arg` contains unresolved inference variables, this may include
27/// further WF obligations. However, if `arg` IS an unresolved
28/// inference variable, returns `None`, because we are not able to
29/// make any progress at all. This is to prevent cycles where we
30/// say "?0 is WF if ?0 is WF".
31pub fn obligations<'tcx>(
32 infcx: &InferCtxt<'tcx>,
33 param_env: ty::ParamEnv<'tcx>,
34 body_id: LocalDefId,
35 recursion_depth: usize,
36 term: Term<'tcx>,
37 span: Span,
38) -> Option<PredicateObligations<'tcx>> {
39 // Handle the "cycle" case (see comment above) by bailing out if necessary.
40 let term = match term.kind() {
41 TermKind::Ty(ty) => {
42 match ty.kind() {
43 ty::Infer(ty::TyVar(_)) => {
44 let resolved_ty = infcx.shallow_resolve(ty);
45 if resolved_ty == ty {
46 // No progress, bail out to prevent cycles.
47 return None;
48 } else {
49 resolved_ty
50 }
51 }
52 _ => ty,
53 }
54 .into()
55 }
56 TermKind::Const(ct) => {
57 match ct.kind() {
58 ty::ConstKind::Infer(_) => {
59 let resolved = infcx.shallow_resolve_const(ct);
60 if resolved == ct {
61 // No progress, bail out to prevent cycles.
62 return None;
63 } else {
64 resolved
65 }
66 }
67 _ => ct,
68 }
69 .into()
70 }
71 };
72
73 let mut wf = WfPredicates {
74 infcx,
75 param_env,
76 body_id,
77 span,
78 out: PredicateObligations::new(),
79 recursion_depth,
80 item: None,
81 };
82 wf.add_wf_preds_for_term(term);
83 debug!("wf::obligations({:?}, body_id={:?}) = {:?}", term, body_id, wf.out);
84
85 let result = wf.normalize(infcx);
86 debug!("wf::obligations({:?}, body_id={:?}) ~~> {:?}", term, body_id, result);
87 Some(result)
88}
89
90/// Compute the predicates that are required for a type to be well-formed.
91///
92/// This is only intended to be used in the new solver, since it does not
93/// take into account recursion depth or proper error-reporting spans.
94pub fn unnormalized_obligations<'tcx>(
95 infcx: &InferCtxt<'tcx>,
96 param_env: ty::ParamEnv<'tcx>,
97 term: Term<'tcx>,
98 span: Span,
99 body_id: LocalDefId,
100) -> Option<PredicateObligations<'tcx>> {
101 debug_assert_eq!(term, infcx.resolve_vars_if_possible(term));
102
103 // However, if `arg` IS an unresolved inference variable, returns `None`,
104 // because we are not able to make any progress at all. This is to prevent
105 // cycles where we say "?0 is WF if ?0 is WF".
106 if term.is_infer() {
107 return None;
108 }
109
110 let mut wf = WfPredicates {
111 infcx,
112 param_env,
113 body_id,
114 span,
115 out: PredicateObligations::new(),
116 recursion_depth: 0,
117 item: None,
118 };
119 wf.add_wf_preds_for_term(term);
120 Some(wf.out)
121}
122
123/// Returns the obligations that make this trait reference
124/// well-formed. For example, if there is a trait `Set` defined like
125/// `trait Set<K: Eq>`, then the trait bound `Foo: Set<Bar>` is WF
126/// if `Bar: Eq`.
127pub fn trait_obligations<'tcx>(
128 infcx: &InferCtxt<'tcx>,
129 param_env: ty::ParamEnv<'tcx>,
130 body_id: LocalDefId,
131 trait_pred: ty::TraitPredicate<'tcx>,
132 span: Span,
133 item: &'tcx hir::Item<'tcx>,
134) -> PredicateObligations<'tcx> {
135 let mut wf = WfPredicates {
136 infcx,
137 param_env,
138 body_id,
139 span,
140 out: PredicateObligations::new(),
141 recursion_depth: 0,
142 item: Some(item),
143 };
144 wf.add_wf_preds_for_trait_pred(trait_pred, Elaborate::All);
145 debug!(obligations = ?wf.out);
146 wf.normalize(infcx)
147}
148
149/// Returns the requirements for `clause` to be well-formed.
150///
151/// For example, if there is a trait `Set` defined like
152/// `trait Set<K: Eq>`, then the trait bound `Foo: Set<Bar>` is WF
153/// if `Bar: Eq`.
154#[instrument(skip(infcx), ret)]
155pub fn clause_obligations<'tcx>(
156 infcx: &InferCtxt<'tcx>,
157 param_env: ty::ParamEnv<'tcx>,
158 body_id: LocalDefId,
159 clause: ty::Clause<'tcx>,
160 span: Span,
161) -> PredicateObligations<'tcx> {
162 let mut wf = WfPredicates {
163 infcx,
164 param_env,
165 body_id,
166 span,
167 out: PredicateObligations::new(),
168 recursion_depth: 0,
169 item: None,
170 };
171
172 // It's ok to skip the binder here because wf code is prepared for it
173 match clause.kind().skip_binder() {
174 ty::ClauseKind::Trait(t) => {
175 wf.add_wf_preds_for_trait_pred(t, Elaborate::None);
176 }
177 ty::ClauseKind::HostEffect(..) => {
178 // Technically the well-formedness of this predicate is implied by
179 // the corresponding trait predicate it should've been generated beside.
180 }
181 ty::ClauseKind::RegionOutlives(..) => {}
182 ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(ty, _reg)) => {
183 wf.add_wf_preds_for_term(ty.into());
184 }
185 ty::ClauseKind::Projection(t) => {
186 wf.add_wf_preds_for_alias_term(t.projection_term);
187 wf.add_wf_preds_for_term(t.term);
188 }
189 ty::ClauseKind::ConstArgHasType(ct, ty) => {
190 wf.add_wf_preds_for_term(ct.into());
191 wf.add_wf_preds_for_term(ty.into());
192 }
193 ty::ClauseKind::WellFormed(term) => {
194 wf.add_wf_preds_for_term(term);
195 }
196
197 ty::ClauseKind::ConstEvaluatable(ct) => {
198 wf.add_wf_preds_for_term(ct.into());
199 }
200 }
201
202 wf.normalize(infcx)
203}
204
205struct WfPredicates<'a, 'tcx> {
206 infcx: &'a InferCtxt<'tcx>,
207 param_env: ty::ParamEnv<'tcx>,
208 body_id: LocalDefId,
209 span: Span,
210 out: PredicateObligations<'tcx>,
211 recursion_depth: usize,
212 item: Option<&'tcx hir::Item<'tcx>>,
213}
214
215/// Controls whether we "elaborate" supertraits and so forth on the WF
216/// predicates. This is a kind of hack to address #43784. The
217/// underlying problem in that issue was a trait structure like:
218///
219/// ```ignore (illustrative)
220/// trait Foo: Copy { }
221/// trait Bar: Foo { }
222/// impl<T: Bar> Foo for T { }
223/// impl<T> Bar for T { }
224/// ```
225///
226/// Here, in the `Foo` impl, we will check that `T: Copy` holds -- but
227/// we decide that this is true because `T: Bar` is in the
228/// where-clauses (and we can elaborate that to include `T:
229/// Copy`). This wouldn't be a problem, except that when we check the
230/// `Bar` impl, we decide that `T: Foo` must hold because of the `Foo`
231/// impl. And so nowhere did we check that `T: Copy` holds!
232///
233/// To resolve this, we elaborate the WF requirements that must be
234/// proven when checking impls. This means that (e.g.) the `impl Bar
235/// for T` will be forced to prove not only that `T: Foo` but also `T:
236/// Copy` (which it won't be able to do, because there is no `Copy`
237/// impl for `T`).
238#[derive(Debug, PartialEq, Eq, Copy, Clone)]
239enum Elaborate {
240 All,
241 None,
242}
243
244/// Points the cause span of a super predicate at the relevant associated type.
245///
246/// Given a trait impl item:
247///
248/// ```ignore (incomplete)
249/// impl TargetTrait for TargetType {
250/// type Assoc = SomeType;
251/// }
252/// ```
253///
254/// And a super predicate of `TargetTrait` that has any of the following forms:
255///
256/// 1. `<OtherType as OtherTrait>::Assoc == <TargetType as TargetTrait>::Assoc`
257/// 2. `<<TargetType as TargetTrait>::Assoc as OtherTrait>::Assoc == OtherType`
258/// 3. `<TargetType as TargetTrait>::Assoc: OtherTrait`
259///
260/// Replace the span of the cause with the span of the associated item:
261///
262/// ```ignore (incomplete)
263/// impl TargetTrait for TargetType {
264/// type Assoc = SomeType;
265/// // ^^^^^^^^ this span
266/// }
267/// ```
268///
269/// Note that bounds that can be expressed as associated item bounds are **not**
270/// super predicates. This means that form 2 and 3 from above are only relevant if
271/// the [`GenericArgsRef`] of the projection type are not its identity arguments.
272fn extend_cause_with_original_assoc_item_obligation<'tcx>(
273 tcx: TyCtxt<'tcx>,
274 item: Option<&hir::Item<'tcx>>,
275 cause: &mut traits::ObligationCause<'tcx>,
276 pred: ty::Predicate<'tcx>,
277) {
278 debug!(?item, ?cause, ?pred, "extended_cause_with_original_assoc_item_obligation");
279 let (items, impl_def_id) = match item {
280 Some(hir::Item { kind: hir::ItemKind::Impl(impl_), owner_id, .. }) => {
281 (impl_.items, *owner_id)
282 }
283 _ => return,
284 };
285
286 let ty_to_impl_span = |ty: Ty<'_>| {
287 if let ty::Alias(ty::Projection, projection_ty) = ty.kind()
288 && let Some(&impl_item_id) =
289 tcx.impl_item_implementor_ids(impl_def_id).get(&projection_ty.def_id)
290 && let Some(impl_item) =
291 items.iter().find(|item| item.id.owner_id.to_def_id() == impl_item_id)
292 {
293 Some(tcx.hir_impl_item(impl_item.id).expect_type().span)
294 } else {
295 None
296 }
297 };
298
299 // It is fine to skip the binder as we don't care about regions here.
300 match pred.kind().skip_binder() {
301 ty::PredicateKind::Clause(ty::ClauseKind::Projection(proj)) => {
302 // Form 1: The obligation comes not from the current `impl` nor the `trait` being
303 // implemented, but rather from a "second order" obligation, where an associated
304 // type has a projection coming from another associated type.
305 // See `tests/ui/traits/assoc-type-in-superbad.rs` for an example.
306 if let Some(term_ty) = proj.term.as_type()
307 && let Some(impl_item_span) = ty_to_impl_span(term_ty)
308 {
309 cause.span = impl_item_span;
310 }
311
312 // Form 2: A projection obligation for an associated item failed to be met.
313 // We overwrite the span from above to ensure that a bound like
314 // `Self::Assoc1: Trait<OtherAssoc = Self::Assoc2>` gets the same
315 // span for both obligations that it is lowered to.
316 if let Some(impl_item_span) = ty_to_impl_span(proj.self_ty()) {
317 cause.span = impl_item_span;
318 }
319 }
320
321 ty::PredicateKind::Clause(ty::ClauseKind::Trait(pred)) => {
322 // Form 3: A trait obligation for an associated item failed to be met.
323 debug!("extended_cause_with_original_assoc_item_obligation trait proj {:?}", pred);
324 if let Some(impl_item_span) = ty_to_impl_span(pred.self_ty()) {
325 cause.span = impl_item_span;
326 }
327 }
328 _ => {}
329 }
330}
331
332impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
333 fn tcx(&self) -> TyCtxt<'tcx> {
334 self.infcx.tcx
335 }
336
337 fn cause(&self, code: traits::ObligationCauseCode<'tcx>) -> traits::ObligationCause<'tcx> {
338 traits::ObligationCause::new(self.span, self.body_id, code)
339 }
340
341 fn normalize(self, infcx: &InferCtxt<'tcx>) -> PredicateObligations<'tcx> {
342 // Do not normalize `wf` obligations with the new solver.
343 //
344 // The current deep normalization routine with the new solver does not
345 // handle ambiguity and the new solver correctly deals with unnnormalized goals.
346 // If the user relies on normalized types, e.g. for `fn implied_outlives_bounds`,
347 // it is their responsibility to normalize while avoiding ambiguity.
348 if infcx.next_trait_solver() {
349 return self.out;
350 }
351
352 let cause = self.cause(ObligationCauseCode::WellFormed(None));
353 let param_env = self.param_env;
354 let mut obligations = PredicateObligations::with_capacity(self.out.len());
355 for mut obligation in self.out {
356 assert!(!obligation.has_escaping_bound_vars());
357 let mut selcx = traits::SelectionContext::new(infcx);
358 // Don't normalize the whole obligation, the param env is either
359 // already normalized, or we're currently normalizing the
360 // param_env. Either way we should only normalize the predicate.
361 let normalized_predicate = traits::normalize::normalize_with_depth_to(
362 &mut selcx,
363 param_env,
364 cause.clone(),
365 self.recursion_depth,
366 obligation.predicate,
367 &mut obligations,
368 );
369 obligation.predicate = normalized_predicate;
370 obligations.push(obligation);
371 }
372 obligations
373 }
374
375 /// Pushes the obligations required for `trait_ref` to be WF into `self.out`.
376 fn add_wf_preds_for_trait_pred(
377 &mut self,
378 trait_pred: ty::TraitPredicate<'tcx>,
379 elaborate: Elaborate,
380 ) {
381 let tcx = self.tcx();
382 let trait_ref = trait_pred.trait_ref;
383
384 // Negative trait predicates don't require supertraits to hold, just
385 // that their args are WF.
386 if trait_pred.polarity == ty::PredicatePolarity::Negative {
387 self.add_wf_preds_for_negative_trait_pred(trait_ref);
388 return;
389 }
390
391 // if the trait predicate is not const, the wf obligations should not be const as well.
392 let obligations = self.nominal_obligations(trait_ref.def_id, trait_ref.args);
393
394 debug!("compute_trait_pred obligations {:?}", obligations);
395 let param_env = self.param_env;
396 let depth = self.recursion_depth;
397
398 let item = self.item;
399
400 let extend = |traits::PredicateObligation { predicate, mut cause, .. }| {
401 if let Some(parent_trait_pred) = predicate.as_trait_clause() {
402 cause = cause.derived_cause(
403 parent_trait_pred,
404 traits::ObligationCauseCode::WellFormedDerived,
405 );
406 }
407 extend_cause_with_original_assoc_item_obligation(tcx, item, &mut cause, predicate);
408 traits::Obligation::with_depth(tcx, cause, depth, param_env, predicate)
409 };
410
411 if let Elaborate::All = elaborate {
412 let implied_obligations = traits::util::elaborate(tcx, obligations);
413 let implied_obligations = implied_obligations.map(extend);
414 self.out.extend(implied_obligations);
415 } else {
416 self.out.extend(obligations);
417 }
418
419 self.out.extend(
420 trait_ref
421 .args
422 .iter()
423 .enumerate()
424 .filter_map(|(i, arg)| arg.as_term().map(|t| (i, t)))
425 .filter(|(_, term)| !term.has_escaping_bound_vars())
426 .map(|(i, term)| {
427 let mut cause = traits::ObligationCause::misc(self.span, self.body_id);
428 // The first arg is the self ty - use the correct span for it.
429 if i == 0 {
430 if let Some(hir::ItemKind::Impl(hir::Impl { self_ty, .. })) =
431 item.map(|i| &i.kind)
432 {
433 cause.span = self_ty.span;
434 }
435 }
436 traits::Obligation::with_depth(
437 tcx,
438 cause,
439 depth,
440 param_env,
441 ty::ClauseKind::WellFormed(term),
442 )
443 }),
444 );
445 }
446
447 // Compute the obligations that are required for `trait_ref` to be WF,
448 // given that it is a *negative* trait predicate.
449 fn add_wf_preds_for_negative_trait_pred(&mut self, trait_ref: ty::TraitRef<'tcx>) {
450 for arg in trait_ref.args {
451 if let Some(term) = arg.as_term() {
452 self.add_wf_preds_for_term(term);
453 }
454 }
455 }
456
457 /// Pushes the obligations required for an alias (except inherent) to be WF
458 /// into `self.out`.
459 fn add_wf_preds_for_alias_term(&mut self, data: ty::AliasTerm<'tcx>) {
460 // A projection is well-formed if
461 //
462 // (a) its predicates hold (*)
463 // (b) its args are wf
464 //
465 // (*) The predicates of an associated type include the predicates of
466 // the trait that it's contained in. For example, given
467 //
468 // trait A<T>: Clone {
469 // type X where T: Copy;
470 // }
471 //
472 // The predicates of `<() as A<i32>>::X` are:
473 // [
474 // `(): Sized`
475 // `(): Clone`
476 // `(): A<i32>`
477 // `i32: Sized`
478 // `i32: Clone`
479 // `i32: Copy`
480 // ]
481 let obligations = self.nominal_obligations(data.def_id, data.args);
482 self.out.extend(obligations);
483
484 self.add_wf_preds_for_projection_args(data.args);
485 }
486
487 /// Pushes the obligations required for an inherent alias to be WF
488 /// into `self.out`.
489 // FIXME(inherent_associated_types): Merge this function with `fn compute_alias`.
490 fn add_wf_preds_for_inherent_projection(&mut self, data: ty::AliasTerm<'tcx>) {
491 // An inherent projection is well-formed if
492 //
493 // (a) its predicates hold (*)
494 // (b) its args are wf
495 //
496 // (*) The predicates of an inherent associated type include the
497 // predicates of the impl that it's contained in.
498
499 if !data.self_ty().has_escaping_bound_vars() {
500 // FIXME(inherent_associated_types): Should this happen inside of a snapshot?
501 // FIXME(inherent_associated_types): This is incompatible with the new solver and lazy norm!
502 let args = traits::project::compute_inherent_assoc_term_args(
503 &mut traits::SelectionContext::new(self.infcx),
504 self.param_env,
505 data,
506 self.cause(ObligationCauseCode::WellFormed(None)),
507 self.recursion_depth,
508 &mut self.out,
509 );
510 let obligations = self.nominal_obligations(data.def_id, args);
511 self.out.extend(obligations);
512 }
513
514 data.args.visit_with(self);
515 }
516
517 fn add_wf_preds_for_projection_args(&mut self, args: GenericArgsRef<'tcx>) {
518 let tcx = self.tcx();
519 let cause = self.cause(ObligationCauseCode::WellFormed(None));
520 let param_env = self.param_env;
521 let depth = self.recursion_depth;
522
523 self.out.extend(
524 args.iter()
525 .filter_map(|arg| arg.as_term())
526 .filter(|term| !term.has_escaping_bound_vars())
527 .map(|term| {
528 traits::Obligation::with_depth(
529 tcx,
530 cause.clone(),
531 depth,
532 param_env,
533 ty::ClauseKind::WellFormed(term),
534 )
535 }),
536 );
537 }
538
539 fn require_sized(&mut self, subty: Ty<'tcx>, cause: traits::ObligationCauseCode<'tcx>) {
540 if !subty.has_escaping_bound_vars() {
541 let cause = self.cause(cause);
542 let trait_ref = ty::TraitRef::new(
543 self.tcx(),
544 self.tcx().require_lang_item(LangItem::Sized, cause.span),
545 [subty],
546 );
547 self.out.push(traits::Obligation::with_depth(
548 self.tcx(),
549 cause,
550 self.recursion_depth,
551 self.param_env,
552 ty::Binder::dummy(trait_ref),
553 ));
554 }
555 }
556
557 /// Pushes all the predicates needed to validate that `term` is WF into `out`.
558 #[instrument(level = "debug", skip(self))]
559 fn add_wf_preds_for_term(&mut self, term: Term<'tcx>) {
560 term.visit_with(self);
561 debug!(?self.out);
562 }
563
564 #[instrument(level = "debug", skip(self))]
565 fn nominal_obligations(
566 &mut self,
567 def_id: DefId,
568 args: GenericArgsRef<'tcx>,
569 ) -> PredicateObligations<'tcx> {
570 // PERF: `Sized`'s predicates include `MetaSized`, but both are compiler implemented marker
571 // traits, so `MetaSized` will always be WF if `Sized` is WF and vice-versa. Determining
572 // the nominal obligations of `Sized` would in-effect just elaborate `MetaSized` and make
573 // the compiler do a bunch of work needlessly.
574 if self.tcx().is_lang_item(def_id, LangItem::Sized) {
575 return Default::default();
576 }
577
578 let predicates = self.tcx().predicates_of(def_id);
579 let mut origins = vec![def_id; predicates.predicates.len()];
580 let mut head = predicates;
581 while let Some(parent) = head.parent {
582 head = self.tcx().predicates_of(parent);
583 origins.extend(iter::repeat(parent).take(head.predicates.len()));
584 }
585
586 let predicates = predicates.instantiate(self.tcx(), args);
587 trace!("{:#?}", predicates);
588 debug_assert_eq!(predicates.predicates.len(), origins.len());
589
590 iter::zip(predicates, origins.into_iter().rev())
591 .map(|((pred, span), origin_def_id)| {
592 let code = ObligationCauseCode::WhereClause(origin_def_id, span);
593 let cause = self.cause(code);
594 traits::Obligation::with_depth(
595 self.tcx(),
596 cause,
597 self.recursion_depth,
598 self.param_env,
599 pred,
600 )
601 })
602 .filter(|pred| !pred.has_escaping_bound_vars())
603 .collect()
604 }
605
606 fn add_wf_preds_for_dyn_ty(
607 &mut self,
608 ty: Ty<'tcx>,
609 data: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>,
610 region: ty::Region<'tcx>,
611 ) {
612 // Imagine a type like this:
613 //
614 // trait Foo { }
615 // trait Bar<'c> : 'c { }
616 //
617 // &'b (Foo+'c+Bar<'d>)
618 // ^
619 //
620 // In this case, the following relationships must hold:
621 //
622 // 'b <= 'c
623 // 'd <= 'c
624 //
625 // The first conditions is due to the normal region pointer
626 // rules, which say that a reference cannot outlive its
627 // referent.
628 //
629 // The final condition may be a bit surprising. In particular,
630 // you may expect that it would have been `'c <= 'd`, since
631 // usually lifetimes of outer things are conservative
632 // approximations for inner things. However, it works somewhat
633 // differently with trait objects: here the idea is that if the
634 // user specifies a region bound (`'c`, in this case) it is the
635 // "master bound" that *implies* that bounds from other traits are
636 // all met. (Remember that *all bounds* in a type like
637 // `Foo+Bar+Zed` must be met, not just one, hence if we write
638 // `Foo<'x>+Bar<'y>`, we know that the type outlives *both* 'x and
639 // 'y.)
640 //
641 // Note: in fact we only permit builtin traits, not `Bar<'d>`, I
642 // am looking forward to the future here.
643 if !data.has_escaping_bound_vars() && !region.has_escaping_bound_vars() {
644 let implicit_bounds = object_region_bounds(self.tcx(), data);
645
646 let explicit_bound = region;
647
648 self.out.reserve(implicit_bounds.len());
649 for implicit_bound in implicit_bounds {
650 let cause = self.cause(ObligationCauseCode::ObjectTypeBound(ty, explicit_bound));
651 let outlives =
652 ty::Binder::dummy(ty::OutlivesPredicate(explicit_bound, implicit_bound));
653 self.out.push(traits::Obligation::with_depth(
654 self.tcx(),
655 cause,
656 self.recursion_depth,
657 self.param_env,
658 outlives,
659 ));
660 }
661
662 // We don't add any wf predicates corresponding to the trait ref's generic arguments
663 // which allows code like this to compile:
664 // ```rust
665 // trait Trait<T: Sized> {}
666 // fn foo(_: &dyn Trait<[u32]>) {}
667 // ```
668 }
669 }
670
671 fn add_wf_preds_for_pat_ty(&mut self, base_ty: Ty<'tcx>, pat: ty::Pattern<'tcx>) {
672 let tcx = self.tcx();
673 match *pat {
674 ty::PatternKind::Range { start, end } => {
675 let mut check = |c| {
676 let cause = self.cause(ObligationCauseCode::Misc);
677 self.out.push(traits::Obligation::with_depth(
678 tcx,
679 cause.clone(),
680 self.recursion_depth,
681 self.param_env,
682 ty::Binder::dummy(ty::PredicateKind::Clause(
683 ty::ClauseKind::ConstArgHasType(c, base_ty),
684 )),
685 ));
686 if !tcx.features().generic_pattern_types() {
687 if c.has_param() {
688 if self.span.is_dummy() {
689 self.tcx()
690 .dcx()
691 .delayed_bug("feature error should be reported elsewhere, too");
692 } else {
693 feature_err(
694 &self.tcx().sess,
695 sym::generic_pattern_types,
696 self.span,
697 "wraparound pattern type ranges cause monomorphization time errors",
698 )
699 .emit();
700 }
701 }
702 }
703 };
704 check(start);
705 check(end);
706 }
707 ty::PatternKind::Or(patterns) => {
708 for pat in patterns {
709 self.add_wf_preds_for_pat_ty(base_ty, pat)
710 }
711 }
712 }
713 }
714}
715
716impl<'a, 'tcx> TypeVisitor<TyCtxt<'tcx>> for WfPredicates<'a, 'tcx> {
717 fn visit_ty(&mut self, t: Ty<'tcx>) -> Self::Result {
718 debug!("wf bounds for t={:?} t.kind={:#?}", t, t.kind());
719
720 let tcx = self.tcx();
721
722 match *t.kind() {
723 ty::Bool
724 | ty::Char
725 | ty::Int(..)
726 | ty::Uint(..)
727 | ty::Float(..)
728 | ty::Error(_)
729 | ty::Str
730 | ty::CoroutineWitness(..)
731 | ty::Never
732 | ty::Param(_)
733 | ty::Bound(..)
734 | ty::Placeholder(..)
735 | ty::Foreign(..) => {
736 // WfScalar, WfParameter, etc
737 }
738
739 // Can only infer to `ty::Int(_) | ty::Uint(_)`.
740 ty::Infer(ty::IntVar(_)) => {}
741
742 // Can only infer to `ty::Float(_)`.
743 ty::Infer(ty::FloatVar(_)) => {}
744
745 ty::Slice(subty) => {
746 self.require_sized(subty, ObligationCauseCode::SliceOrArrayElem);
747 }
748
749 ty::Array(subty, len) => {
750 self.require_sized(subty, ObligationCauseCode::SliceOrArrayElem);
751 // Note that the len being WF is implicitly checked while visiting.
752 // Here we just check that it's of type usize.
753 let cause = self.cause(ObligationCauseCode::ArrayLen(t));
754 self.out.push(traits::Obligation::with_depth(
755 tcx,
756 cause,
757 self.recursion_depth,
758 self.param_env,
759 ty::Binder::dummy(ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(
760 len,
761 tcx.types.usize,
762 ))),
763 ));
764 }
765
766 ty::Pat(base_ty, pat) => {
767 self.require_sized(base_ty, ObligationCauseCode::Misc);
768 self.add_wf_preds_for_pat_ty(base_ty, pat);
769 }
770
771 ty::Tuple(tys) => {
772 if let Some((_last, rest)) = tys.split_last() {
773 for &elem in rest {
774 self.require_sized(elem, ObligationCauseCode::TupleElem);
775 }
776 }
777 }
778
779 ty::RawPtr(_, _) => {
780 // Simple cases that are WF if their type args are WF.
781 }
782
783 ty::Alias(ty::Projection | ty::Opaque | ty::Free, data) => {
784 let obligations = self.nominal_obligations(data.def_id, data.args);
785 self.out.extend(obligations);
786 }
787 ty::Alias(ty::Inherent, data) => {
788 self.add_wf_preds_for_inherent_projection(data.into());
789 return; // Subtree handled by compute_inherent_projection.
790 }
791
792 ty::Adt(def, args) => {
793 // WfNominalType
794 let obligations = self.nominal_obligations(def.did(), args);
795 self.out.extend(obligations);
796 }
797
798 ty::FnDef(did, args) => {
799 // HACK: Check the return type of function definitions for
800 // well-formedness to mostly fix #84533. This is still not
801 // perfect and there may be ways to abuse the fact that we
802 // ignore requirements with escaping bound vars. That's a
803 // more general issue however.
804 let fn_sig = tcx.fn_sig(did).instantiate(tcx, args);
805 fn_sig.output().skip_binder().visit_with(self);
806
807 let obligations = self.nominal_obligations(did, args);
808 self.out.extend(obligations);
809 }
810
811 ty::Ref(r, rty, _) => {
812 // WfReference
813 if !r.has_escaping_bound_vars() && !rty.has_escaping_bound_vars() {
814 let cause = self.cause(ObligationCauseCode::ReferenceOutlivesReferent(t));
815 self.out.push(traits::Obligation::with_depth(
816 tcx,
817 cause,
818 self.recursion_depth,
819 self.param_env,
820 ty::Binder::dummy(ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(
821 ty::OutlivesPredicate(rty, r),
822 ))),
823 ));
824 }
825 }
826
827 ty::Coroutine(did, args, ..) => {
828 // Walk ALL the types in the coroutine: this will
829 // include the upvar types as well as the yield
830 // type. Note that this is mildly distinct from
831 // the closure case, where we have to be careful
832 // about the signature of the closure. We don't
833 // have the problem of implied bounds here since
834 // coroutines don't take arguments.
835 let obligations = self.nominal_obligations(did, args);
836 self.out.extend(obligations);
837 }
838
839 ty::Closure(did, args) => {
840 // Note that we cannot skip the generic types
841 // types. Normally, within the fn
842 // body where they are created, the generics will
843 // always be WF, and outside of that fn body we
844 // are not directly inspecting closure types
845 // anyway, except via auto trait matching (which
846 // only inspects the upvar types).
847 // But when a closure is part of a type-alias-impl-trait
848 // then the function that created the defining site may
849 // have had more bounds available than the type alias
850 // specifies. This may cause us to have a closure in the
851 // hidden type that is not actually well formed and
852 // can cause compiler crashes when the user abuses unsafe
853 // code to procure such a closure.
854 // See tests/ui/type-alias-impl-trait/wf_check_closures.rs
855 let obligations = self.nominal_obligations(did, args);
856 self.out.extend(obligations);
857 // Only check the upvar types for WF, not the rest
858 // of the types within. This is needed because we
859 // capture the signature and it may not be WF
860 // without the implied bounds. Consider a closure
861 // like `|x: &'a T|` -- it may be that `T: 'a` is
862 // not known to hold in the creator's context (and
863 // indeed the closure may not be invoked by its
864 // creator, but rather turned to someone who *can*
865 // verify that).
866 //
867 // The special treatment of closures here really
868 // ought not to be necessary either; the problem
869 // is related to #25860 -- there is no way for us
870 // to express a fn type complete with the implied
871 // bounds that it is assuming. I think in reality
872 // the WF rules around fn are a bit messed up, and
873 // that is the rot problem: `fn(&'a T)` should
874 // probably always be WF, because it should be
875 // shorthand for something like `where(T: 'a) {
876 // fn(&'a T) }`, as discussed in #25860.
877 let upvars = args.as_closure().tupled_upvars_ty();
878 return upvars.visit_with(self);
879 }
880
881 ty::CoroutineClosure(did, args) => {
882 // See the above comments. The same apply to coroutine-closures.
883 let obligations = self.nominal_obligations(did, args);
884 self.out.extend(obligations);
885 let upvars = args.as_coroutine_closure().tupled_upvars_ty();
886 return upvars.visit_with(self);
887 }
888
889 ty::FnPtr(..) => {
890 // Let the visitor iterate into the argument/return
891 // types appearing in the fn signature.
892 }
893 ty::UnsafeBinder(ty) => {
894 // FIXME(unsafe_binders): For now, we have no way to express
895 // that a type must be `ManuallyDrop` OR `Copy` (or a pointer).
896 if !ty.has_escaping_bound_vars() {
897 self.out.push(traits::Obligation::new(
898 self.tcx(),
899 self.cause(ObligationCauseCode::Misc),
900 self.param_env,
901 ty.map_bound(|ty| {
902 ty::TraitRef::new(
903 self.tcx(),
904 self.tcx().require_lang_item(
905 LangItem::BikeshedGuaranteedNoDrop,
906 self.span,
907 ),
908 [ty],
909 )
910 }),
911 ));
912 }
913
914 // We recurse into the binder below.
915 }
916
917 ty::Dynamic(data, r, _) => {
918 // WfObject
919 //
920 // Here, we defer WF checking due to higher-ranked
921 // regions. This is perhaps not ideal.
922 self.add_wf_preds_for_dyn_ty(t, data, r);
923
924 // FIXME(#27579) RFC also considers adding trait
925 // obligations that don't refer to Self and
926 // checking those
927 if let Some(principal) = data.principal_def_id() {
928 self.out.push(traits::Obligation::with_depth(
929 tcx,
930 self.cause(ObligationCauseCode::WellFormed(None)),
931 self.recursion_depth,
932 self.param_env,
933 ty::Binder::dummy(ty::PredicateKind::DynCompatible(principal)),
934 ));
935 }
936 }
937
938 // Inference variables are the complicated case, since we don't
939 // know what type they are. We do two things:
940 //
941 // 1. Check if they have been resolved, and if so proceed with
942 // THAT type.
943 // 2. If not, we've at least simplified things (e.g., we went
944 // from `Vec?0>: WF` to `?0: WF`), so we can
945 // register a pending obligation and keep
946 // moving. (Goal is that an "inductive hypothesis"
947 // is satisfied to ensure termination.)
948 // See also the comment on `fn obligations`, describing cycle
949 // prevention, which happens before this can be reached.
950 ty::Infer(_) => {
951 let cause = self.cause(ObligationCauseCode::WellFormed(None));
952 self.out.push(traits::Obligation::with_depth(
953 tcx,
954 cause,
955 self.recursion_depth,
956 self.param_env,
957 ty::Binder::dummy(ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(
958 t.into(),
959 ))),
960 ));
961 }
962 }
963
964 t.super_visit_with(self)
965 }
966
967 fn visit_const(&mut self, c: ty::Const<'tcx>) -> Self::Result {
968 let tcx = self.tcx();
969
970 match c.kind() {
971 ty::ConstKind::Unevaluated(uv) => {
972 if !c.has_escaping_bound_vars() {
973 let predicate = ty::Binder::dummy(ty::PredicateKind::Clause(
974 ty::ClauseKind::ConstEvaluatable(c),
975 ));
976 let cause = self.cause(ObligationCauseCode::WellFormed(None));
977 self.out.push(traits::Obligation::with_depth(
978 tcx,
979 cause,
980 self.recursion_depth,
981 self.param_env,
982 predicate,
983 ));
984
985 if tcx.def_kind(uv.def) == DefKind::AssocConst
986 && tcx.def_kind(tcx.parent(uv.def)) == (DefKind::Impl { of_trait: false })
987 {
988 self.add_wf_preds_for_inherent_projection(uv.into());
989 return; // Subtree is handled by above function
990 } else {
991 let obligations = self.nominal_obligations(uv.def, uv.args);
992 self.out.extend(obligations);
993 }
994 }
995 }
996 ty::ConstKind::Infer(_) => {
997 let cause = self.cause(ObligationCauseCode::WellFormed(None));
998
999 self.out.push(traits::Obligation::with_depth(
1000 tcx,
1001 cause,
1002 self.recursion_depth,
1003 self.param_env,
1004 ty::Binder::dummy(ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(
1005 c.into(),
1006 ))),
1007 ));
1008 }
1009 ty::ConstKind::Expr(_) => {
1010 // FIXME(generic_const_exprs): this doesn't verify that given `Expr(N + 1)` the
1011 // trait bound `typeof(N): Add<typeof(1)>` holds. This is currently unnecessary
1012 // as `ConstKind::Expr` is only produced via normalization of `ConstKind::Unevaluated`
1013 // which means that the `DefId` would have been typeck'd elsewhere. However in
1014 // the future we may allow directly lowering to `ConstKind::Expr` in which case
1015 // we would not be proving bounds we should.
1016
1017 let predicate = ty::Binder::dummy(ty::PredicateKind::Clause(
1018 ty::ClauseKind::ConstEvaluatable(c),
1019 ));
1020 let cause = self.cause(ObligationCauseCode::WellFormed(None));
1021 self.out.push(traits::Obligation::with_depth(
1022 tcx,
1023 cause,
1024 self.recursion_depth,
1025 self.param_env,
1026 predicate,
1027 ));
1028 }
1029
1030 ty::ConstKind::Error(_)
1031 | ty::ConstKind::Param(_)
1032 | ty::ConstKind::Bound(..)
1033 | ty::ConstKind::Placeholder(..) => {
1034 // These variants are trivially WF, so nothing to do here.
1035 }
1036 ty::ConstKind::Value(..) => {
1037 // FIXME: Enforce that values are structurally-matchable.
1038 }
1039 }
1040
1041 c.super_visit_with(self)
1042 }
1043
1044 fn visit_predicate(&mut self, _p: ty::Predicate<'tcx>) -> Self::Result {
1045 bug!("predicate should not be checked for well-formedness");
1046 }
1047}
1048
1049/// Given an object type like `SomeTrait + Send`, computes the lifetime
1050/// bounds that must hold on the elided self type. These are derived
1051/// from the declarations of `SomeTrait`, `Send`, and friends -- if
1052/// they declare `trait SomeTrait : 'static`, for example, then
1053/// `'static` would appear in the list.
1054///
1055/// N.B., in some cases, particularly around higher-ranked bounds,
1056/// this function returns a kind of conservative approximation.
1057/// That is, all regions returned by this function are definitely
1058/// required, but there may be other region bounds that are not
1059/// returned, as well as requirements like `for<'a> T: 'a`.
1060///
1061/// Requires that trait definitions have been processed so that we can
1062/// elaborate predicates and walk supertraits.
1063pub fn object_region_bounds<'tcx>(
1064 tcx: TyCtxt<'tcx>,
1065 existential_predicates: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>,
1066) -> Vec<ty::Region<'tcx>> {
1067 let erased_self_ty = tcx.types.trait_object_dummy_self;
1068
1069 let predicates =
1070 existential_predicates.iter().map(|predicate| predicate.with_self_ty(tcx, erased_self_ty));
1071
1072 traits::elaborate(tcx, predicates)
1073 .filter_map(|pred| {
1074 debug!(?pred);
1075 match pred.kind().skip_binder() {
1076 ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(ref t, ref r)) => {
1077 // Search for a bound of the form `erased_self_ty
1078 // : 'a`, but be wary of something like `for<'a>
1079 // erased_self_ty : 'a` (we interpret a
1080 // higher-ranked bound like that as 'static,
1081 // though at present the code in `fulfill.rs`
1082 // considers such bounds to be unsatisfiable, so
1083 // it's kind of a moot point since you could never
1084 // construct such an object, but this seems
1085 // correct even if that code changes).
1086 if t == &erased_self_ty && !r.has_escaping_bound_vars() {
1087 Some(*r)
1088 } else {
1089 None
1090 }
1091 }
1092 ty::ClauseKind::Trait(_)
1093 | ty::ClauseKind::HostEffect(..)
1094 | ty::ClauseKind::RegionOutlives(_)
1095 | ty::ClauseKind::Projection(_)
1096 | ty::ClauseKind::ConstArgHasType(_, _)
1097 | ty::ClauseKind::WellFormed(_)
1098 | ty::ClauseKind::ConstEvaluatable(_) => None,
1099 }
1100 })
1101 .collect()
1102}