]>
Commit | Line | Data |
---|---|---|
8faf50e0 | 1 | //! Provider for the `implied_outlives_bounds` query. |
ba9703b0 XL |
2 | //! Do not call this query directory. See |
3 | //! [`rustc_trait_selection::traits::query::type_op::implied_outlives_bounds`]. | |
8faf50e0 | 4 | |
dfeec247 | 5 | use rustc_hir as hir; |
74b04a01 XL |
6 | use rustc_infer::infer::canonical::{self, Canonical}; |
7 | use rustc_infer::infer::{InferCtxt, TyCtxtInferExt}; | |
ba9703b0 XL |
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}; | |
dfeec247 | 12 | use rustc_span::source_map::DUMMY_SP; |
ba9703b0 XL |
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; | |
dfeec247 | 19 | use smallvec::{smallvec, SmallVec}; |
8faf50e0 | 20 | |
f035d41b | 21 | crate fn provide(p: &mut Providers) { |
dfeec247 | 22 | *p = Providers { implied_outlives_bounds, ..*p }; |
8faf50e0 XL |
23 | } |
24 | ||
25 | fn implied_outlives_bounds<'tcx>( | |
dc9dc135 | 26 | tcx: TyCtxt<'tcx>, |
8faf50e0 XL |
27 | goal: CanonicalTyGoal<'tcx>, |
28 | ) -> Result< | |
dc9dc135 XL |
29 | &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>, |
30 | NoSolution, | |
8faf50e0 | 31 | > { |
dfeec247 XL |
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) | |
35 | }) | |
8faf50e0 XL |
36 | } |
37 | ||
38 | fn compute_implied_outlives_bounds<'tcx>( | |
dc9dc135 | 39 | infcx: &InferCtxt<'_, 'tcx>, |
8faf50e0 | 40 | param_env: ty::ParamEnv<'tcx>, |
dc9dc135 | 41 | ty: Ty<'tcx>, |
8faf50e0 XL |
42 | ) -> Fallible<Vec<OutlivesBound<'tcx>>> { |
43 | let tcx = infcx.tcx; | |
44 | ||
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. | |
f035d41b | 50 | let mut wf_args = vec![ty.into()]; |
8faf50e0 XL |
51 | |
52 | let mut implied_bounds = vec![]; | |
53 | ||
54 | let mut fulfill_cx = FulfillmentContext::new(); | |
55 | ||
f035d41b XL |
56 | while let Some(arg) = wf_args.pop() { |
57 | // Compute the obligations for `arg` to be well-formed. If `arg` is | |
8faf50e0 XL |
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 = | |
f035d41b | 65 | wf::obligations(infcx, param_env, hir::CRATE_HIR_ID, arg, DUMMY_SP).unwrap_or(vec![]); |
8faf50e0 | 66 | |
0731742a | 67 | // N.B., all of these predicates *ought* to be easily proven |
8faf50e0 XL |
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: | |
71 | // | |
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). | |
83 | // | |
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( | |
89 | infcx, | |
74b04a01 | 90 | obligations.iter().filter(|o| o.predicate.has_infer_types_or_consts()).cloned(), |
8faf50e0 XL |
91 | ); |
92 | ||
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| { | |
a1dfa0c6 | 96 | assert!(!obligation.has_escaping_bound_vars()); |
f9f354fc | 97 | match obligation.predicate.kind() { |
3dfed10e XL |
98 | &ty::PredicateKind::ForAll(..) => vec![], |
99 | &ty::PredicateKind::Atom(atom) => match atom { | |
100 | ty::PredicateAtom::Trait(..) | |
101 | | ty::PredicateAtom::Subtype(..) | |
102 | | ty::PredicateAtom::Projection(..) | |
103 | | ty::PredicateAtom::ClosureKind(..) | |
104 | | ty::PredicateAtom::ObjectSafe(..) | |
105 | | ty::PredicateAtom::ConstEvaluatable(..) | |
106 | | ty::PredicateAtom::ConstEquate(..) => vec![], | |
107 | ty::PredicateAtom::WellFormed(arg) => { | |
108 | wf_args.push(arg); | |
109 | vec![] | |
110 | } | |
8faf50e0 | 111 | |
3dfed10e | 112 | ty::PredicateAtom::RegionOutlives(ty::OutlivesPredicate(r_a, r_b)) => { |
8faf50e0 XL |
113 | vec![OutlivesBound::RegionSubRegion(r_b, r_a)] |
114 | } | |
8faf50e0 | 115 | |
3dfed10e | 116 | ty::PredicateAtom::TypeOutlives(ty::OutlivesPredicate(ty_a, r_b)) => { |
dc9dc135 | 117 | let ty_a = infcx.resolve_vars_if_possible(&ty_a); |
a1dfa0c6 XL |
118 | let mut components = smallvec![]; |
119 | tcx.push_outlives_components(ty_a, &mut components); | |
8faf50e0 XL |
120 | implied_bounds_from_components(r_b, components) |
121 | } | |
122 | }, | |
123 | } | |
124 | })); | |
125 | } | |
126 | ||
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), | |
132 | } | |
133 | } | |
134 | ||
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>, | |
a1dfa0c6 | 141 | sup_components: SmallVec<[Component<'tcx>; 4]>, |
8faf50e0 XL |
142 | ) -> Vec<OutlivesBound<'tcx>> { |
143 | sup_components | |
144 | .into_iter() | |
a1dfa0c6 | 145 | .filter_map(|component| { |
8faf50e0 | 146 | match component { |
dfeec247 XL |
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)), | |
8faf50e0 XL |
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. | |
dfeec247 XL |
159 | { |
160 | None | |
161 | } | |
162 | Component::UnresolvedInferenceVariable(..) => None, | |
8faf50e0 XL |
163 | } |
164 | }) | |
165 | .collect() | |
166 | } |