]>
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}; |
487cf647 | 8 | use rustc_infer::infer::TyCtxtInferExt; |
c295e0f8 | 9 | use rustc_infer::traits::query::OutlivesBound; |
ba9703b0 | 10 | use rustc_middle::ty::query::Providers; |
064997fb | 11 | use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitable}; |
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. | |
487cf647 FG |
70 | let obligations = |
71 | wf::obligations(ocx.infcx, param_env, hir::CRATE_HIR_ID, 0, arg, DUMMY_SP) | |
72 | .unwrap_or_default(); | |
8faf50e0 | 73 | |
f2b60f7d FG |
74 | // While these predicates should all be implied by other parts of |
75 | // the program, they are still relevant as they may constrain | |
76 | // inference variables, which is necessary to add the correct | |
77 | // implied bounds in some cases, mostly when dealing with projections. | |
487cf647 | 78 | ocx.register_obligations( |
2b03887a | 79 | obligations.iter().filter(|o| o.predicate.has_non_region_infer()).cloned(), |
8faf50e0 XL |
80 | ); |
81 | ||
82 | // From the full set of obligations, just filter down to the | |
83 | // region relationships. | |
f2b60f7d | 84 | outlives_bounds.extend(obligations.into_iter().filter_map(|obligation| { |
a1dfa0c6 | 85 | assert!(!obligation.has_escaping_bound_vars()); |
5869c6ff | 86 | match obligation.predicate.kind().no_bound_vars() { |
f2b60f7d | 87 | None => None, |
5869c6ff | 88 | Some(pred) => match pred { |
487cf647 | 89 | ty::PredicateKind::Clause(ty::Clause::Trait(..)) |
5869c6ff | 90 | | ty::PredicateKind::Subtype(..) |
94222f64 | 91 | | ty::PredicateKind::Coerce(..) |
487cf647 | 92 | | ty::PredicateKind::Clause(ty::Clause::Projection(..)) |
5869c6ff XL |
93 | | ty::PredicateKind::ClosureKind(..) |
94 | | ty::PredicateKind::ObjectSafe(..) | |
95 | | ty::PredicateKind::ConstEvaluatable(..) | |
96 | | ty::PredicateKind::ConstEquate(..) | |
487cf647 | 97 | | ty::PredicateKind::Ambiguous |
f2b60f7d | 98 | | ty::PredicateKind::TypeWellFormedFromEnv(..) => None, |
5869c6ff | 99 | ty::PredicateKind::WellFormed(arg) => { |
3dfed10e | 100 | wf_args.push(arg); |
f2b60f7d | 101 | None |
3dfed10e | 102 | } |
8faf50e0 | 103 | |
487cf647 FG |
104 | ty::PredicateKind::Clause(ty::Clause::RegionOutlives( |
105 | ty::OutlivesPredicate(r_a, r_b), | |
106 | )) => Some(ty::OutlivesPredicate(r_a.into(), r_b)), | |
8faf50e0 | 107 | |
487cf647 FG |
108 | ty::PredicateKind::Clause(ty::Clause::TypeOutlives(ty::OutlivesPredicate( |
109 | ty_a, | |
110 | r_b, | |
111 | ))) => Some(ty::OutlivesPredicate(ty_a.into(), r_b)), | |
8faf50e0 XL |
112 | }, |
113 | } | |
114 | })); | |
115 | } | |
116 | ||
487cf647 FG |
117 | // This call to `select_all_or_error` is necessary to constrain inference variables, which we |
118 | // use further down when computing the implied bounds. | |
119 | match ocx.select_all_or_error().as_slice() { | |
f2b60f7d FG |
120 | [] => (), |
121 | _ => return Err(NoSolution), | |
8faf50e0 | 122 | } |
f2b60f7d FG |
123 | |
124 | // We lazily compute the outlives components as | |
125 | // `select_all_or_error` constrains inference variables. | |
126 | let implied_bounds = outlives_bounds | |
127 | .into_iter() | |
128 | .flat_map(|ty::OutlivesPredicate(a, r_b)| match a.unpack() { | |
129 | ty::GenericArgKind::Lifetime(r_a) => vec![OutlivesBound::RegionSubRegion(r_b, r_a)], | |
130 | ty::GenericArgKind::Type(ty_a) => { | |
487cf647 | 131 | let ty_a = ocx.infcx.resolve_vars_if_possible(ty_a); |
f2b60f7d FG |
132 | let mut components = smallvec![]; |
133 | push_outlives_components(tcx, ty_a, &mut components); | |
134 | implied_bounds_from_components(r_b, components) | |
135 | } | |
136 | ty::GenericArgKind::Const(_) => unreachable!(), | |
137 | }) | |
138 | .collect(); | |
139 | ||
140 | Ok(implied_bounds) | |
8faf50e0 XL |
141 | } |
142 | ||
143 | /// When we have an implied bound that `T: 'a`, we can further break | |
144 | /// this down to determine what relationships would have to hold for | |
145 | /// `T: 'a` to hold. We get to assume that the caller has validated | |
146 | /// those relationships. | |
a2a8927a | 147 | fn implied_bounds_from_components<'tcx>( |
8faf50e0 | 148 | sub_region: ty::Region<'tcx>, |
a1dfa0c6 | 149 | sup_components: SmallVec<[Component<'tcx>; 4]>, |
8faf50e0 XL |
150 | ) -> Vec<OutlivesBound<'tcx>> { |
151 | sup_components | |
152 | .into_iter() | |
a1dfa0c6 | 153 | .filter_map(|component| { |
8faf50e0 | 154 | match component { |
dfeec247 XL |
155 | Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)), |
156 | Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)), | |
9c376795 FG |
157 | Component::Alias(p) => Some(OutlivesBound::RegionSubAlias(sub_region, p)), |
158 | Component::EscapingAlias(_) => | |
8faf50e0 XL |
159 | // If the projection has escaping regions, don't |
160 | // try to infer any implied bounds even for its | |
161 | // free components. This is conservative, because | |
162 | // the caller will still have to prove that those | |
163 | // free components outlive `sub_region`. But the | |
164 | // idea is that the WAY that the caller proves | |
165 | // that may change in the future and we want to | |
166 | // give ourselves room to get smarter here. | |
dfeec247 XL |
167 | { |
168 | None | |
169 | } | |
170 | Component::UnresolvedInferenceVariable(..) => None, | |
8faf50e0 XL |
171 | } |
172 | }) | |
173 | .collect() | |
174 | } |