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.unpack() {
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, Some(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 let predicates = self.tcx().predicates_of(def_id);
571 let mut origins = vec![def_id; predicates.predicates.len()];
572 let mut head = predicates;
573 while let Some(parent) = head.parent {
574 head = self.tcx().predicates_of(parent);
575 origins.extend(iter::repeat(parent).take(head.predicates.len()));
576 }
577
578 let predicates = predicates.instantiate(self.tcx(), args);
579 trace!("{:#?}", predicates);
580 debug_assert_eq!(predicates.predicates.len(), origins.len());
581
582 iter::zip(predicates, origins.into_iter().rev())
583 .map(|((pred, span), origin_def_id)| {
584 let code = ObligationCauseCode::WhereClause(origin_def_id, span);
585 let cause = self.cause(code);
586 traits::Obligation::with_depth(
587 self.tcx(),
588 cause,
589 self.recursion_depth,
590 self.param_env,
591 pred,
592 )
593 })
594 .filter(|pred| !pred.has_escaping_bound_vars())
595 .collect()
596 }
597
598 fn add_wf_preds_for_dyn_ty(
599 &mut self,
600 ty: Ty<'tcx>,
601 data: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>,
602 region: ty::Region<'tcx>,
603 ) {
604 // Imagine a type like this:
605 //
606 // trait Foo { }
607 // trait Bar<'c> : 'c { }
608 //
609 // &'b (Foo+'c+Bar<'d>)
610 // ^
611 //
612 // In this case, the following relationships must hold:
613 //
614 // 'b <= 'c
615 // 'd <= 'c
616 //
617 // The first conditions is due to the normal region pointer
618 // rules, which say that a reference cannot outlive its
619 // referent.
620 //
621 // The final condition may be a bit surprising. In particular,
622 // you may expect that it would have been `'c <= 'd`, since
623 // usually lifetimes of outer things are conservative
624 // approximations for inner things. However, it works somewhat
625 // differently with trait objects: here the idea is that if the
626 // user specifies a region bound (`'c`, in this case) it is the
627 // "master bound" that *implies* that bounds from other traits are
628 // all met. (Remember that *all bounds* in a type like
629 // `Foo+Bar+Zed` must be met, not just one, hence if we write
630 // `Foo<'x>+Bar<'y>`, we know that the type outlives *both* 'x and
631 // 'y.)
632 //
633 // Note: in fact we only permit builtin traits, not `Bar<'d>`, I
634 // am looking forward to the future here.
635 if !data.has_escaping_bound_vars() && !region.has_escaping_bound_vars() {
636 let implicit_bounds = object_region_bounds(self.tcx(), data);
637
638 let explicit_bound = region;
639
640 self.out.reserve(implicit_bounds.len());
641 for implicit_bound in implicit_bounds {
642 let cause = self.cause(ObligationCauseCode::ObjectTypeBound(ty, explicit_bound));
643 let outlives =
644 ty::Binder::dummy(ty::OutlivesPredicate(explicit_bound, implicit_bound));
645 self.out.push(traits::Obligation::with_depth(
646 self.tcx(),
647 cause,
648 self.recursion_depth,
649 self.param_env,
650 outlives,
651 ));
652 }
653
654 // We don't add any wf predicates corresponding to the trait ref's generic arguments
655 // which allows code like this to compile:
656 // ```rust
657 // trait Trait<T: Sized> {}
658 // fn foo(_: &dyn Trait<[u32]>) {}
659 // ```
660 }
661 }
662
663 fn add_wf_preds_for_pat_ty(&mut self, base_ty: Ty<'tcx>, pat: ty::Pattern<'tcx>) {
664 let tcx = self.tcx();
665 match *pat {
666 ty::PatternKind::Range { start, end } => {
667 let mut check = |c| {
668 let cause = self.cause(ObligationCauseCode::Misc);
669 self.out.push(traits::Obligation::with_depth(
670 tcx,
671 cause.clone(),
672 self.recursion_depth,
673 self.param_env,
674 ty::Binder::dummy(ty::PredicateKind::Clause(
675 ty::ClauseKind::ConstArgHasType(c, base_ty),
676 )),
677 ));
678 if !tcx.features().generic_pattern_types() {
679 if c.has_param() {
680 if self.span.is_dummy() {
681 self.tcx()
682 .dcx()
683 .delayed_bug("feature error should be reported elsewhere, too");
684 } else {
685 feature_err(
686 &self.tcx().sess,
687 sym::generic_pattern_types,
688 self.span,
689 "wraparound pattern type ranges cause monomorphization time errors",
690 )
691 .emit();
692 }
693 }
694 }
695 };
696 check(start);
697 check(end);
698 }
699 ty::PatternKind::Or(patterns) => {
700 for pat in patterns {
701 self.add_wf_preds_for_pat_ty(base_ty, pat)
702 }
703 }
704 }
705 }
706}
707
708impl<'a, 'tcx> TypeVisitor<TyCtxt<'tcx>> for WfPredicates<'a, 'tcx> {
709 fn visit_ty(&mut self, t: Ty<'tcx>) -> Self::Result {
710 debug!("wf bounds for t={:?} t.kind={:#?}", t, t.kind());
711
712 let tcx = self.tcx();
713
714 match *t.kind() {
715 ty::Bool
716 | ty::Char
717 | ty::Int(..)
718 | ty::Uint(..)
719 | ty::Float(..)
720 | ty::Error(_)
721 | ty::Str
722 | ty::CoroutineWitness(..)
723 | ty::Never
724 | ty::Param(_)
725 | ty::Bound(..)
726 | ty::Placeholder(..)
727 | ty::Foreign(..) => {
728 // WfScalar, WfParameter, etc
729 }
730
731 // Can only infer to `ty::Int(_) | ty::Uint(_)`.
732 ty::Infer(ty::IntVar(_)) => {}
733
734 // Can only infer to `ty::Float(_)`.
735 ty::Infer(ty::FloatVar(_)) => {}
736
737 ty::Slice(subty) => {
738 self.require_sized(subty, ObligationCauseCode::SliceOrArrayElem);
739 }
740
741 ty::Array(subty, len) => {
742 self.require_sized(subty, ObligationCauseCode::SliceOrArrayElem);
743 // Note that the len being WF is implicitly checked while visiting.
744 // Here we just check that it's of type usize.
745 let cause = self.cause(ObligationCauseCode::ArrayLen(t));
746 self.out.push(traits::Obligation::with_depth(
747 tcx,
748 cause,
749 self.recursion_depth,
750 self.param_env,
751 ty::Binder::dummy(ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(
752 len,
753 tcx.types.usize,
754 ))),
755 ));
756 }
757
758 ty::Pat(base_ty, pat) => {
759 self.require_sized(base_ty, ObligationCauseCode::Misc);
760 self.add_wf_preds_for_pat_ty(base_ty, pat);
761 }
762
763 ty::Tuple(tys) => {
764 if let Some((_last, rest)) = tys.split_last() {
765 for &elem in rest {
766 self.require_sized(elem, ObligationCauseCode::TupleElem);
767 }
768 }
769 }
770
771 ty::RawPtr(_, _) => {
772 // Simple cases that are WF if their type args are WF.
773 }
774
775 ty::Alias(ty::Projection | ty::Opaque | ty::Free, data) => {
776 let obligations = self.nominal_obligations(data.def_id, data.args);
777 self.out.extend(obligations);
778 }
779 ty::Alias(ty::Inherent, data) => {
780 self.add_wf_preds_for_inherent_projection(data.into());
781 return; // Subtree handled by compute_inherent_projection.
782 }
783
784 ty::Adt(def, args) => {
785 // WfNominalType
786 let obligations = self.nominal_obligations(def.did(), args);
787 self.out.extend(obligations);
788 }
789
790 ty::FnDef(did, args) => {
791 // HACK: Check the return type of function definitions for
792 // well-formedness to mostly fix #84533. This is still not
793 // perfect and there may be ways to abuse the fact that we
794 // ignore requirements with escaping bound vars. That's a
795 // more general issue however.
796 let fn_sig = tcx.fn_sig(did).instantiate(tcx, args);
797 fn_sig.output().skip_binder().visit_with(self);
798
799 let obligations = self.nominal_obligations(did, args);
800 self.out.extend(obligations);
801 }
802
803 ty::Ref(r, rty, _) => {
804 // WfReference
805 if !r.has_escaping_bound_vars() && !rty.has_escaping_bound_vars() {
806 let cause = self.cause(ObligationCauseCode::ReferenceOutlivesReferent(t));
807 self.out.push(traits::Obligation::with_depth(
808 tcx,
809 cause,
810 self.recursion_depth,
811 self.param_env,
812 ty::Binder::dummy(ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(
813 ty::OutlivesPredicate(rty, r),
814 ))),
815 ));
816 }
817 }
818
819 ty::Coroutine(did, args, ..) => {
820 // Walk ALL the types in the coroutine: this will
821 // include the upvar types as well as the yield
822 // type. Note that this is mildly distinct from
823 // the closure case, where we have to be careful
824 // about the signature of the closure. We don't
825 // have the problem of implied bounds here since
826 // coroutines don't take arguments.
827 let obligations = self.nominal_obligations(did, args);
828 self.out.extend(obligations);
829 }
830
831 ty::Closure(did, args) => {
832 // Note that we cannot skip the generic types
833 // types. Normally, within the fn
834 // body where they are created, the generics will
835 // always be WF, and outside of that fn body we
836 // are not directly inspecting closure types
837 // anyway, except via auto trait matching (which
838 // only inspects the upvar types).
839 // But when a closure is part of a type-alias-impl-trait
840 // then the function that created the defining site may
841 // have had more bounds available than the type alias
842 // specifies. This may cause us to have a closure in the
843 // hidden type that is not actually well formed and
844 // can cause compiler crashes when the user abuses unsafe
845 // code to procure such a closure.
846 // See tests/ui/type-alias-impl-trait/wf_check_closures.rs
847 let obligations = self.nominal_obligations(did, args);
848 self.out.extend(obligations);
849 // Only check the upvar types for WF, not the rest
850 // of the types within. This is needed because we
851 // capture the signature and it may not be WF
852 // without the implied bounds. Consider a closure
853 // like `|x: &'a T|` -- it may be that `T: 'a` is
854 // not known to hold in the creator's context (and
855 // indeed the closure may not be invoked by its
856 // creator, but rather turned to someone who *can*
857 // verify that).
858 //
859 // The special treatment of closures here really
860 // ought not to be necessary either; the problem
861 // is related to #25860 -- there is no way for us
862 // to express a fn type complete with the implied
863 // bounds that it is assuming. I think in reality
864 // the WF rules around fn are a bit messed up, and
865 // that is the rot problem: `fn(&'a T)` should
866 // probably always be WF, because it should be
867 // shorthand for something like `where(T: 'a) {
868 // fn(&'a T) }`, as discussed in #25860.
869 let upvars = args.as_closure().tupled_upvars_ty();
870 return upvars.visit_with(self);
871 }
872
873 ty::CoroutineClosure(did, args) => {
874 // See the above comments. The same apply to coroutine-closures.
875 let obligations = self.nominal_obligations(did, args);
876 self.out.extend(obligations);
877 let upvars = args.as_coroutine_closure().tupled_upvars_ty();
878 return upvars.visit_with(self);
879 }
880
881 ty::FnPtr(..) => {
882 // Let the visitor iterate into the argument/return
883 // types appearing in the fn signature.
884 }
885 ty::UnsafeBinder(ty) => {
886 // FIXME(unsafe_binders): For now, we have no way to express
887 // that a type must be `ManuallyDrop` OR `Copy` (or a pointer).
888 if !ty.has_escaping_bound_vars() {
889 self.out.push(traits::Obligation::new(
890 self.tcx(),
891 self.cause(ObligationCauseCode::Misc),
892 self.param_env,
893 ty.map_bound(|ty| {
894 ty::TraitRef::new(
895 self.tcx(),
896 self.tcx().require_lang_item(
897 LangItem::BikeshedGuaranteedNoDrop,
898 Some(self.span),
899 ),
900 [ty],
901 )
902 }),
903 ));
904 }
905
906 // We recurse into the binder below.
907 }
908
909 ty::Dynamic(data, r, _) => {
910 // WfObject
911 //
912 // Here, we defer WF checking due to higher-ranked
913 // regions. This is perhaps not ideal.
914 self.add_wf_preds_for_dyn_ty(t, data, r);
915
916 // FIXME(#27579) RFC also considers adding trait
917 // obligations that don't refer to Self and
918 // checking those
919 if let Some(principal) = data.principal_def_id() {
920 self.out.push(traits::Obligation::with_depth(
921 tcx,
922 self.cause(ObligationCauseCode::WellFormed(None)),
923 self.recursion_depth,
924 self.param_env,
925 ty::Binder::dummy(ty::PredicateKind::DynCompatible(principal)),
926 ));
927 }
928 }
929
930 // Inference variables are the complicated case, since we don't
931 // know what type they are. We do two things:
932 //
933 // 1. Check if they have been resolved, and if so proceed with
934 // THAT type.
935 // 2. If not, we've at least simplified things (e.g., we went
936 // from `Vec?0>: WF` to `?0: WF`), so we can
937 // register a pending obligation and keep
938 // moving. (Goal is that an "inductive hypothesis"
939 // is satisfied to ensure termination.)
940 // See also the comment on `fn obligations`, describing cycle
941 // prevention, which happens before this can be reached.
942 ty::Infer(_) => {
943 let cause = self.cause(ObligationCauseCode::WellFormed(None));
944 self.out.push(traits::Obligation::with_depth(
945 tcx,
946 cause,
947 self.recursion_depth,
948 self.param_env,
949 ty::Binder::dummy(ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(
950 t.into(),
951 ))),
952 ));
953 }
954 }
955
956 t.super_visit_with(self)
957 }
958
959 fn visit_const(&mut self, c: ty::Const<'tcx>) -> Self::Result {
960 let tcx = self.tcx();
961
962 match c.kind() {
963 ty::ConstKind::Unevaluated(uv) => {
964 if !c.has_escaping_bound_vars() {
965 let predicate = ty::Binder::dummy(ty::PredicateKind::Clause(
966 ty::ClauseKind::ConstEvaluatable(c),
967 ));
968 let cause = self.cause(ObligationCauseCode::WellFormed(None));
969 self.out.push(traits::Obligation::with_depth(
970 tcx,
971 cause,
972 self.recursion_depth,
973 self.param_env,
974 predicate,
975 ));
976
977 if tcx.def_kind(uv.def) == DefKind::AssocConst
978 && tcx.def_kind(tcx.parent(uv.def)) == (DefKind::Impl { of_trait: false })
979 {
980 self.add_wf_preds_for_inherent_projection(uv.into());
981 return; // Subtree is handled by above function
982 } else {
983 let obligations = self.nominal_obligations(uv.def, uv.args);
984 self.out.extend(obligations);
985 }
986 }
987 }
988 ty::ConstKind::Infer(_) => {
989 let cause = self.cause(ObligationCauseCode::WellFormed(None));
990
991 self.out.push(traits::Obligation::with_depth(
992 tcx,
993 cause,
994 self.recursion_depth,
995 self.param_env,
996 ty::Binder::dummy(ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(
997 c.into(),
998 ))),
999 ));
1000 }
1001 ty::ConstKind::Expr(_) => {
1002 // FIXME(generic_const_exprs): this doesn't verify that given `Expr(N + 1)` the
1003 // trait bound `typeof(N): Add<typeof(1)>` holds. This is currently unnecessary
1004 // as `ConstKind::Expr` is only produced via normalization of `ConstKind::Unevaluated`
1005 // which means that the `DefId` would have been typeck'd elsewhere. However in
1006 // the future we may allow directly lowering to `ConstKind::Expr` in which case
1007 // we would not be proving bounds we should.
1008
1009 let predicate = ty::Binder::dummy(ty::PredicateKind::Clause(
1010 ty::ClauseKind::ConstEvaluatable(c),
1011 ));
1012 let cause = self.cause(ObligationCauseCode::WellFormed(None));
1013 self.out.push(traits::Obligation::with_depth(
1014 tcx,
1015 cause,
1016 self.recursion_depth,
1017 self.param_env,
1018 predicate,
1019 ));
1020 }
1021
1022 ty::ConstKind::Error(_)
1023 | ty::ConstKind::Param(_)
1024 | ty::ConstKind::Bound(..)
1025 | ty::ConstKind::Placeholder(..) => {
1026 // These variants are trivially WF, so nothing to do here.
1027 }
1028 ty::ConstKind::Value(..) => {
1029 // FIXME: Enforce that values are structurally-matchable.
1030 }
1031 }
1032
1033 c.super_visit_with(self)
1034 }
1035
1036 fn visit_predicate(&mut self, _p: ty::Predicate<'tcx>) -> Self::Result {
1037 bug!("predicate should not be checked for well-formedness");
1038 }
1039}
1040
1041/// Given an object type like `SomeTrait + Send`, computes the lifetime
1042/// bounds that must hold on the elided self type. These are derived
1043/// from the declarations of `SomeTrait`, `Send`, and friends -- if
1044/// they declare `trait SomeTrait : 'static`, for example, then
1045/// `'static` would appear in the list.
1046///
1047/// N.B., in some cases, particularly around higher-ranked bounds,
1048/// this function returns a kind of conservative approximation.
1049/// That is, all regions returned by this function are definitely
1050/// required, but there may be other region bounds that are not
1051/// returned, as well as requirements like `for<'a> T: 'a`.
1052///
1053/// Requires that trait definitions have been processed so that we can
1054/// elaborate predicates and walk supertraits.
1055pub fn object_region_bounds<'tcx>(
1056 tcx: TyCtxt<'tcx>,
1057 existential_predicates: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>,
1058) -> Vec<ty::Region<'tcx>> {
1059 let erased_self_ty = tcx.types.trait_object_dummy_self;
1060
1061 let predicates =
1062 existential_predicates.iter().map(|predicate| predicate.with_self_ty(tcx, erased_self_ty));
1063
1064 traits::elaborate(tcx, predicates)
1065 .filter_map(|pred| {
1066 debug!(?pred);
1067 match pred.kind().skip_binder() {
1068 ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(ref t, ref r)) => {
1069 // Search for a bound of the form `erased_self_ty
1070 // : 'a`, but be wary of something like `for<'a>
1071 // erased_self_ty : 'a` (we interpret a
1072 // higher-ranked bound like that as 'static,
1073 // though at present the code in `fulfill.rs`
1074 // considers such bounds to be unsatisfiable, so
1075 // it's kind of a moot point since you could never
1076 // construct such an object, but this seems
1077 // correct even if that code changes).
1078 if t == &erased_self_ty && !r.has_escaping_bound_vars() {
1079 Some(*r)
1080 } else {
1081 None
1082 }
1083 }
1084 ty::ClauseKind::Trait(_)
1085 | ty::ClauseKind::HostEffect(..)
1086 | ty::ClauseKind::RegionOutlives(_)
1087 | ty::ClauseKind::Projection(_)
1088 | ty::ClauseKind::ConstArgHasType(_, _)
1089 | ty::ClauseKind::WellFormed(_)
1090 | ty::ClauseKind::ConstEvaluatable(_) => None,
1091 }
1092 })
1093 .collect()
1094}