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