1 //! Provider for the `implied_outlives_bounds` query.
2 //! Do not call this query directory. See
3 //! [`rustc_trait_selection::traits::query::type_op::implied_outlives_bounds`].
6 use rustc_infer::infer::canonical::{self, Canonical};
7 use rustc_infer::infer::{InferCtxt, TyCtxtInferExt};
8 use rustc_infer::traits::TraitEngineExt as _;
9 use rustc_middle::ty::outlives::Component;
10 use rustc_middle::ty::query::Providers;
11 use rustc_middle::ty::{self, Ty, TyCtxt, TypeFoldable};
12 use rustc_span::source_map::DUMMY_SP;
13 use rustc_trait_selection::infer::InferCtxtBuilderExt;
14 use rustc_trait_selection::traits::query::outlives_bounds::OutlivesBound;
15 use rustc_trait_selection::traits::query::{CanonicalTyGoal, Fallible, NoSolution};
16 use rustc_trait_selection::traits::wf;
17 use rustc_trait_selection::traits::FulfillmentContext;
18 use rustc_trait_selection::traits::TraitEngine;
19 use smallvec::{smallvec, SmallVec};
21 crate fn provide(p: &mut Providers) {
22 *p = Providers { implied_outlives_bounds, ..*p };
25 fn implied_outlives_bounds<'tcx>(
27 goal: CanonicalTyGoal<'tcx>,
29 &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>,
32 tcx.infer_ctxt().enter_canonical_trait_query(&goal, |infcx, _fulfill_cx, key| {
33 let (param_env, ty) = key.into_parts();
34 compute_implied_outlives_bounds(&infcx, param_env, ty)
38 fn compute_implied_outlives_bounds<'tcx>(
39 infcx: &InferCtxt<'_, 'tcx>,
40 param_env: ty::ParamEnv<'tcx>,
42 ) -> Fallible<Vec<OutlivesBound<'tcx>>> {
45 // Sometimes when we ask what it takes for T: WF, we get back that
46 // U: WF is required; in that case, we push U onto this stack and
47 // process it next. Currently (at least) these resulting
48 // predicates are always guaranteed to be a subset of the original
49 // type, so we need not fear non-termination.
50 let mut wf_args = vec![ty.into()];
52 let mut implied_bounds = vec![];
54 let mut fulfill_cx = FulfillmentContext::new();
56 while let Some(arg) = wf_args.pop() {
57 // Compute the obligations for `arg` to be well-formed. If `arg` is
58 // an unresolved inference variable, just substituted an empty set
59 // -- because the return type here is going to be things we *add*
60 // to the environment, it's always ok for this set to be smaller
61 // than the ultimate set. (Note: normally there won't be
62 // unresolved inference variables here anyway, but there might be
63 // during typeck under some circumstances.)
64 let obligations = wf::obligations(infcx, param_env, hir::CRATE_HIR_ID, 0, arg, DUMMY_SP)
67 // N.B., all of these predicates *ought* to be easily proven
68 // true. In fact, their correctness is (mostly) implied by
69 // other parts of the program. However, in #42552, we had
70 // an annoying scenario where:
72 // - Some `T::Foo` gets normalized, resulting in a
73 // variable `_1` and a `T: Trait<Foo=_1>` constraint
74 // (not sure why it couldn't immediately get
75 // solved). This result of `_1` got cached.
76 // - These obligations were dropped on the floor here,
77 // rather than being registered.
78 // - Then later we would get a request to normalize
79 // `T::Foo` which would result in `_1` being used from
80 // the cache, but hence without the `T: Trait<Foo=_1>`
81 // constraint. As a result, `_1` never gets resolved,
82 // and we get an ICE (in dropck).
84 // Therefore, we register any predicates involving
85 // inference variables. We restrict ourselves to those
86 // involving inference variables both for efficiency and
87 // to avoids duplicate errors that otherwise show up.
88 fulfill_cx.register_predicate_obligations(
90 obligations.iter().filter(|o| o.predicate.has_infer_types_or_consts()).cloned(),
93 // From the full set of obligations, just filter down to the
94 // region relationships.
95 implied_bounds.extend(obligations.into_iter().flat_map(|obligation| {
96 assert!(!obligation.has_escaping_bound_vars());
97 match obligation.predicate.kind() {
98 &ty::PredicateKind::ForAll(binder)
99 if binder.skip_binder().has_escaping_bound_vars() =>
103 &ty::PredicateKind::ForAll(binder) => match binder.skip_binder() {
104 ty::PredicateAtom::Trait(..)
105 | ty::PredicateAtom::Subtype(..)
106 | ty::PredicateAtom::Projection(..)
107 | ty::PredicateAtom::ClosureKind(..)
108 | ty::PredicateAtom::ObjectSafe(..)
109 | ty::PredicateAtom::ConstEvaluatable(..)
110 | ty::PredicateAtom::ConstEquate(..)
111 | ty::PredicateAtom::TypeWellFormedFromEnv(..) => vec![],
112 ty::PredicateAtom::WellFormed(arg) => {
117 ty::PredicateAtom::RegionOutlives(ty::OutlivesPredicate(r_a, r_b)) => {
118 vec![OutlivesBound::RegionSubRegion(r_b, r_a)]
121 ty::PredicateAtom::TypeOutlives(ty::OutlivesPredicate(ty_a, r_b)) => {
122 let ty_a = infcx.resolve_vars_if_possible(ty_a);
123 let mut components = smallvec![];
124 tcx.push_outlives_components(ty_a, &mut components);
125 implied_bounds_from_components(r_b, components)
132 // Ensure that those obligations that we had to solve
133 // get solved *here*.
134 match fulfill_cx.select_all_or_error(infcx) {
135 Ok(()) => Ok(implied_bounds),
136 Err(_) => Err(NoSolution),
140 /// When we have an implied bound that `T: 'a`, we can further break
141 /// this down to determine what relationships would have to hold for
142 /// `T: 'a` to hold. We get to assume that the caller has validated
143 /// those relationships.
144 fn implied_bounds_from_components(
145 sub_region: ty::Region<'tcx>,
146 sup_components: SmallVec<[Component<'tcx>; 4]>,
147 ) -> Vec<OutlivesBound<'tcx>> {
150 .filter_map(|component| {
152 Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)),
153 Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)),
154 Component::Projection(p) => Some(OutlivesBound::RegionSubProjection(sub_region, p)),
155 Component::EscapingProjection(_) =>
156 // If the projection has escaping regions, don't
157 // try to infer any implied bounds even for its
158 // free components. This is conservative, because
159 // the caller will still have to prove that those
160 // free components outlive `sub_region`. But the
161 // idea is that the WAY that the caller proves
162 // that may change in the future and we want to
163 // give ourselves room to get smarter here.
167 Component::UnresolvedInferenceVariable(..) => None,