1 //! Provider for the `implied_outlives_bounds` query.
2 //! Do not call this query directory. See [`rustc::traits::query::implied_outlives_bounds`].
4 use rustc::infer::canonical::{self, Canonical};
5 use rustc::infer::InferCtxt;
6 use rustc::traits::query::outlives_bounds::OutlivesBound;
7 use rustc::traits::query::{CanonicalTyGoal, Fallible, NoSolution};
9 use rustc::traits::FulfillmentContext;
10 use rustc::traits::{TraitEngine, TraitEngineExt};
11 use rustc::ty::outlives::Component;
12 use rustc::ty::query::Providers;
13 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
15 use rustc_span::source_map::DUMMY_SP;
16 use smallvec::{smallvec, SmallVec};
18 crate fn provide(p: &mut Providers<'_>) {
19 *p = Providers { implied_outlives_bounds, ..*p };
22 fn implied_outlives_bounds<'tcx>(
24 goal: CanonicalTyGoal<'tcx>,
26 &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>,
29 tcx.infer_ctxt().enter_canonical_trait_query(&goal, |infcx, _fulfill_cx, key| {
30 let (param_env, ty) = key.into_parts();
31 compute_implied_outlives_bounds(&infcx, param_env, ty)
35 fn compute_implied_outlives_bounds<'tcx>(
36 infcx: &InferCtxt<'_, 'tcx>,
37 param_env: ty::ParamEnv<'tcx>,
39 ) -> Fallible<Vec<OutlivesBound<'tcx>>> {
42 // Sometimes when we ask what it takes for T: WF, we get back that
43 // U: WF is required; in that case, we push U onto this stack and
44 // process it next. Currently (at least) these resulting
45 // predicates are always guaranteed to be a subset of the original
46 // type, so we need not fear non-termination.
47 let mut wf_types = vec![ty];
49 let mut implied_bounds = vec![];
51 let mut fulfill_cx = FulfillmentContext::new();
53 while let Some(ty) = wf_types.pop() {
54 // Compute the obligations for `ty` to be well-formed. If `ty` is
55 // an unresolved inference variable, just substituted an empty set
56 // -- because the return type here is going to be things we *add*
57 // to the environment, it's always ok for this set to be smaller
58 // than the ultimate set. (Note: normally there won't be
59 // unresolved inference variables here anyway, but there might be
60 // during typeck under some circumstances.)
62 wf::obligations(infcx, param_env, hir::DUMMY_HIR_ID, ty, DUMMY_SP).unwrap_or(vec![]);
64 // N.B., all of these predicates *ought* to be easily proven
65 // true. In fact, their correctness is (mostly) implied by
66 // other parts of the program. However, in #42552, we had
67 // an annoying scenario where:
69 // - Some `T::Foo` gets normalized, resulting in a
70 // variable `_1` and a `T: Trait<Foo=_1>` constraint
71 // (not sure why it couldn't immediately get
72 // solved). This result of `_1` got cached.
73 // - These obligations were dropped on the floor here,
74 // rather than being registered.
75 // - Then later we would get a request to normalize
76 // `T::Foo` which would result in `_1` being used from
77 // the cache, but hence without the `T: Trait<Foo=_1>`
78 // constraint. As a result, `_1` never gets resolved,
79 // and we get an ICE (in dropck).
81 // Therefore, we register any predicates involving
82 // inference variables. We restrict ourselves to those
83 // involving inference variables both for efficiency and
84 // to avoids duplicate errors that otherwise show up.
85 fulfill_cx.register_predicate_obligations(
87 obligations.iter().filter(|o| o.predicate.has_infer_types()).cloned(),
90 // From the full set of obligations, just filter down to the
91 // region relationships.
92 implied_bounds.extend(obligations.into_iter().flat_map(|obligation| {
93 assert!(!obligation.has_escaping_bound_vars());
94 match obligation.predicate {
95 ty::Predicate::Trait(..)
96 | ty::Predicate::Subtype(..)
97 | ty::Predicate::Projection(..)
98 | ty::Predicate::ClosureKind(..)
99 | ty::Predicate::ObjectSafe(..)
100 | ty::Predicate::ConstEvaluatable(..) => vec![],
102 ty::Predicate::WellFormed(subty) => {
103 wf_types.push(subty);
107 ty::Predicate::RegionOutlives(ref data) => match data.no_bound_vars() {
109 Some(ty::OutlivesPredicate(r_a, r_b)) => {
110 vec![OutlivesBound::RegionSubRegion(r_b, r_a)]
114 ty::Predicate::TypeOutlives(ref data) => match data.no_bound_vars() {
116 Some(ty::OutlivesPredicate(ty_a, r_b)) => {
117 let ty_a = infcx.resolve_vars_if_possible(&ty_a);
118 let mut components = smallvec![];
119 tcx.push_outlives_components(ty_a, &mut components);
120 implied_bounds_from_components(r_b, components)
127 // Ensure that those obligations that we had to solve
128 // get solved *here*.
129 match fulfill_cx.select_all_or_error(infcx) {
130 Ok(()) => Ok(implied_bounds),
131 Err(_) => Err(NoSolution),
135 /// When we have an implied bound that `T: 'a`, we can further break
136 /// this down to determine what relationships would have to hold for
137 /// `T: 'a` to hold. We get to assume that the caller has validated
138 /// those relationships.
139 fn implied_bounds_from_components(
140 sub_region: ty::Region<'tcx>,
141 sup_components: SmallVec<[Component<'tcx>; 4]>,
142 ) -> Vec<OutlivesBound<'tcx>> {
145 .filter_map(|component| {
147 Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)),
148 Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)),
149 Component::Projection(p) => Some(OutlivesBound::RegionSubProjection(sub_region, p)),
150 Component::EscapingProjection(_) =>
151 // If the projection has escaping regions, don't
152 // try to infer any implied bounds even for its
153 // free components. This is conservative, because
154 // the caller will still have to prove that those
155 // free components outlive `sub_region`. But the
156 // idea is that the WAY that the caller proves
157 // that may change in the future and we want to
158 // give ourselves room to get smarter here.
162 Component::UnresolvedInferenceVariable(..) => None,