]>
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 | |
74b04a01 | 5 | use rustc_infer::infer::canonical::{self, Canonical}; |
c295e0f8 | 6 | use rustc_infer::infer::outlives::components::{push_outlives_components, Component}; |
487cf647 | 7 | use rustc_infer::infer::TyCtxtInferExt; |
c295e0f8 | 8 | use rustc_infer::traits::query::OutlivesBound; |
ba9703b0 | 9 | use rustc_middle::ty::query::Providers; |
9ffffee4 FG |
10 | use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt}; |
11 | use rustc_span::def_id::CRATE_DEF_ID; | |
dfeec247 | 12 | use rustc_span::source_map::DUMMY_SP; |
ba9703b0 | 13 | use rustc_trait_selection::infer::InferCtxtBuilderExt; |
ba9703b0 XL |
14 | use rustc_trait_selection::traits::query::{CanonicalTyGoal, Fallible, NoSolution}; |
15 | use rustc_trait_selection::traits::wf; | |
487cf647 | 16 | use rustc_trait_selection::traits::ObligationCtxt; |
dfeec247 | 17 | use smallvec::{smallvec, SmallVec}; |
8faf50e0 | 18 | |
923072b8 | 19 | pub(crate) fn provide(p: &mut Providers) { |
dfeec247 | 20 | *p = Providers { implied_outlives_bounds, ..*p }; |
8faf50e0 XL |
21 | } |
22 | ||
23 | fn implied_outlives_bounds<'tcx>( | |
dc9dc135 | 24 | tcx: TyCtxt<'tcx>, |
8faf50e0 XL |
25 | goal: CanonicalTyGoal<'tcx>, |
26 | ) -> Result< | |
dc9dc135 XL |
27 | &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>, |
28 | NoSolution, | |
8faf50e0 | 29 | > { |
487cf647 | 30 | tcx.infer_ctxt().enter_canonical_trait_query(&goal, |ocx, key| { |
dfeec247 | 31 | let (param_env, ty) = key.into_parts(); |
487cf647 | 32 | compute_implied_outlives_bounds(ocx, param_env, ty) |
dfeec247 | 33 | }) |
8faf50e0 XL |
34 | } |
35 | ||
36 | fn compute_implied_outlives_bounds<'tcx>( | |
487cf647 | 37 | ocx: &ObligationCtxt<'_, 'tcx>, |
8faf50e0 | 38 | param_env: ty::ParamEnv<'tcx>, |
dc9dc135 | 39 | ty: Ty<'tcx>, |
8faf50e0 | 40 | ) -> Fallible<Vec<OutlivesBound<'tcx>>> { |
487cf647 | 41 | let tcx = ocx.infcx.tcx; |
8faf50e0 XL |
42 | |
43 | // Sometimes when we ask what it takes for T: WF, we get back that | |
44 | // U: WF is required; in that case, we push U onto this stack and | |
064997fb FG |
45 | // process it next. Because the resulting predicates aren't always |
46 | // guaranteed to be a subset of the original type, so we need to store the | |
47 | // WF args we've computed in a set. | |
48 | let mut checked_wf_args = rustc_data_structures::fx::FxHashSet::default(); | |
f035d41b | 49 | let mut wf_args = vec![ty.into()]; |
8faf50e0 | 50 | |
f2b60f7d FG |
51 | let mut outlives_bounds: Vec<ty::OutlivesPredicate<ty::GenericArg<'tcx>, ty::Region<'tcx>>> = |
52 | vec![]; | |
8faf50e0 | 53 | |
f035d41b | 54 | while let Some(arg) = wf_args.pop() { |
064997fb FG |
55 | if !checked_wf_args.insert(arg) { |
56 | continue; | |
57 | } | |
58 | ||
f035d41b | 59 | // Compute the obligations for `arg` to be well-formed. If `arg` is |
8faf50e0 XL |
60 | // an unresolved inference variable, just substituted an empty set |
61 | // -- because the return type here is going to be things we *add* | |
62 | // to the environment, it's always ok for this set to be smaller | |
63 | // than the ultimate set. (Note: normally there won't be | |
64 | // unresolved inference variables here anyway, but there might be | |
65 | // during typeck under some circumstances.) | |
f2b60f7d FG |
66 | // |
67 | // FIXME(@lcnr): It's not really "always fine", having fewer implied | |
68 | // bounds can be backward incompatible, e.g. #101951 was caused by | |
69 | // us not dealing with inference vars in `TypeOutlives` predicates. | |
9ffffee4 FG |
70 | let obligations = wf::obligations(ocx.infcx, param_env, CRATE_DEF_ID, 0, arg, DUMMY_SP) |
71 | .unwrap_or_default(); | |
72 | ||
73 | for obligation in obligations { | |
74 | debug!(?obligation); | |
a1dfa0c6 | 75 | assert!(!obligation.has_escaping_bound_vars()); |
9ffffee4 FG |
76 | |
77 | // While these predicates should all be implied by other parts of | |
78 | // the program, they are still relevant as they may constrain | |
79 | // inference variables, which is necessary to add the correct | |
80 | // implied bounds in some cases, mostly when dealing with projections. | |
81 | // | |
82 | // Another important point here: we only register `Projection` | |
83 | // predicates, since otherwise we might register outlives | |
84 | // predicates containing inference variables, and we don't | |
85 | // learn anything new from those. | |
86 | if obligation.predicate.has_non_region_infer() { | |
87 | match obligation.predicate.kind().skip_binder() { | |
88 | ty::PredicateKind::Clause(ty::Clause::Projection(..)) | |
353b0b11 | 89 | | ty::PredicateKind::AliasRelate(..) => { |
9ffffee4 | 90 | ocx.register_obligation(obligation.clone()); |
3dfed10e | 91 | } |
9ffffee4 FG |
92 | _ => {} |
93 | } | |
94 | } | |
8faf50e0 | 95 | |
9ffffee4 FG |
96 | let pred = match obligation.predicate.kind().no_bound_vars() { |
97 | None => continue, | |
98 | Some(pred) => pred, | |
99 | }; | |
100 | match pred { | |
101 | ty::PredicateKind::Clause(ty::Clause::Trait(..)) | |
102 | // FIXME(const_generics): Make sure that `<'a, 'b, const N: &'a &'b u32>` is sound | |
103 | // if we ever support that | |
104 | | ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(..)) | |
105 | | ty::PredicateKind::Subtype(..) | |
106 | | ty::PredicateKind::Coerce(..) | |
107 | | ty::PredicateKind::Clause(ty::Clause::Projection(..)) | |
108 | | ty::PredicateKind::ClosureKind(..) | |
109 | | ty::PredicateKind::ObjectSafe(..) | |
110 | | ty::PredicateKind::ConstEvaluatable(..) | |
111 | | ty::PredicateKind::ConstEquate(..) | |
112 | | ty::PredicateKind::Ambiguous | |
353b0b11 | 113 | | ty::PredicateKind::AliasRelate(..) |
9ffffee4 | 114 | | ty::PredicateKind::TypeWellFormedFromEnv(..) => {} |
8faf50e0 | 115 | |
9ffffee4 FG |
116 | // We need to search through *all* WellFormed predicates |
117 | ty::PredicateKind::WellFormed(arg) => { | |
118 | wf_args.push(arg); | |
119 | } | |
120 | ||
121 | // We need to register region relationships | |
122 | ty::PredicateKind::Clause(ty::Clause::RegionOutlives(ty::OutlivesPredicate( | |
123 | r_a, | |
124 | r_b, | |
125 | ))) => outlives_bounds.push(ty::OutlivesPredicate(r_a.into(), r_b)), | |
126 | ||
127 | ty::PredicateKind::Clause(ty::Clause::TypeOutlives(ty::OutlivesPredicate( | |
128 | ty_a, | |
129 | r_b, | |
130 | ))) => outlives_bounds.push(ty::OutlivesPredicate(ty_a.into(), r_b)), | |
8faf50e0 | 131 | } |
9ffffee4 | 132 | } |
8faf50e0 XL |
133 | } |
134 | ||
487cf647 FG |
135 | // This call to `select_all_or_error` is necessary to constrain inference variables, which we |
136 | // use further down when computing the implied bounds. | |
137 | match ocx.select_all_or_error().as_slice() { | |
f2b60f7d FG |
138 | [] => (), |
139 | _ => return Err(NoSolution), | |
8faf50e0 | 140 | } |
f2b60f7d FG |
141 | |
142 | // We lazily compute the outlives components as | |
143 | // `select_all_or_error` constrains inference variables. | |
144 | let implied_bounds = outlives_bounds | |
145 | .into_iter() | |
146 | .flat_map(|ty::OutlivesPredicate(a, r_b)| match a.unpack() { | |
147 | ty::GenericArgKind::Lifetime(r_a) => vec![OutlivesBound::RegionSubRegion(r_b, r_a)], | |
148 | ty::GenericArgKind::Type(ty_a) => { | |
487cf647 | 149 | let ty_a = ocx.infcx.resolve_vars_if_possible(ty_a); |
f2b60f7d FG |
150 | let mut components = smallvec![]; |
151 | push_outlives_components(tcx, ty_a, &mut components); | |
152 | implied_bounds_from_components(r_b, components) | |
153 | } | |
154 | ty::GenericArgKind::Const(_) => unreachable!(), | |
155 | }) | |
156 | .collect(); | |
157 | ||
158 | Ok(implied_bounds) | |
8faf50e0 XL |
159 | } |
160 | ||
161 | /// When we have an implied bound that `T: 'a`, we can further break | |
162 | /// this down to determine what relationships would have to hold for | |
163 | /// `T: 'a` to hold. We get to assume that the caller has validated | |
164 | /// those relationships. | |
a2a8927a | 165 | fn implied_bounds_from_components<'tcx>( |
8faf50e0 | 166 | sub_region: ty::Region<'tcx>, |
a1dfa0c6 | 167 | sup_components: SmallVec<[Component<'tcx>; 4]>, |
8faf50e0 XL |
168 | ) -> Vec<OutlivesBound<'tcx>> { |
169 | sup_components | |
170 | .into_iter() | |
a1dfa0c6 | 171 | .filter_map(|component| { |
8faf50e0 | 172 | match component { |
dfeec247 XL |
173 | Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)), |
174 | Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)), | |
9c376795 FG |
175 | Component::Alias(p) => Some(OutlivesBound::RegionSubAlias(sub_region, p)), |
176 | Component::EscapingAlias(_) => | |
8faf50e0 XL |
177 | // If the projection has escaping regions, don't |
178 | // try to infer any implied bounds even for its | |
179 | // free components. This is conservative, because | |
180 | // the caller will still have to prove that those | |
181 | // free components outlive `sub_region`. But the | |
182 | // idea is that the WAY that the caller proves | |
183 | // that may change in the future and we want to | |
184 | // give ourselves room to get smarter here. | |
dfeec247 XL |
185 | { |
186 | None | |
187 | } | |
188 | Component::UnresolvedInferenceVariable(..) => None, | |
8faf50e0 XL |
189 | } |
190 | }) | |
191 | .collect() | |
192 | } |