]>
Commit | Line | Data |
---|---|---|
dfeec247 | 1 | use rustc_data_structures::fx::FxHashSet; |
064997fb | 2 | use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor}; |
ba9703b0 | 3 | use rustc_middle::ty::{self, Ty, TyCtxt}; |
dfeec247 | 4 | use rustc_span::source_map::Span; |
29967ef6 | 5 | use std::ops::ControlFlow; |
85aaf69f | 6 | |
9346a6ac | 7 | #[derive(Clone, PartialEq, Eq, Hash, Debug)] |
9e0c209e SL |
8 | pub struct Parameter(pub u32); |
9 | ||
10 | impl From<ty::ParamTy> for Parameter { | |
dfeec247 XL |
11 | fn from(param: ty::ParamTy) -> Self { |
12 | Parameter(param.index) | |
13 | } | |
9e0c209e SL |
14 | } |
15 | ||
16 | impl From<ty::EarlyBoundRegion> for Parameter { | |
dfeec247 XL |
17 | fn from(param: ty::EarlyBoundRegion) -> Self { |
18 | Parameter(param.index) | |
19 | } | |
9346a6ac AL |
20 | } |
21 | ||
532ac7d7 | 22 | impl From<ty::ParamConst> for Parameter { |
dfeec247 XL |
23 | fn from(param: ty::ParamConst) -> Self { |
24 | Parameter(param.index) | |
25 | } | |
532ac7d7 XL |
26 | } |
27 | ||
9fa01778 | 28 | /// Returns the set of parameters constrained by the impl header. |
e1599b0c XL |
29 | pub fn parameters_for_impl<'tcx>( |
30 | impl_self_ty: Ty<'tcx>, | |
31 | impl_trait_ref: Option<ty::TraitRef<'tcx>>, | |
32 | ) -> FxHashSet<Parameter> { | |
476ff2be | 33 | let vec = match impl_trait_ref { |
5099ac24 FG |
34 | Some(tr) => parameters_for(&tr, false), |
35 | None => parameters_for(&impl_self_ty, false), | |
476ff2be SL |
36 | }; |
37 | vec.into_iter().collect() | |
38 | } | |
39 | ||
ba9703b0 | 40 | /// If `include_nonconstraining` is false, returns the list of parameters that are |
0731742a | 41 | /// constrained by `t` - i.e., the value of each parameter in the list is |
5bcae85e | 42 | /// uniquely determined by `t` (see RFC 447). If it is true, return the list |
92a42be0 SL |
43 | /// of parameters whose values are needed in order to constrain `ty` - these |
44 | /// differ, with the latter being a superset, in the presence of projections. | |
e1599b0c | 45 | pub fn parameters_for<'tcx>( |
064997fb | 46 | t: &impl TypeVisitable<'tcx>, |
e1599b0c XL |
47 | include_nonconstraining: bool, |
48 | ) -> Vec<Parameter> { | |
5099ac24 | 49 | let mut collector = ParameterCollector { parameters: vec![], include_nonconstraining }; |
5bcae85e SL |
50 | t.visit_with(&mut collector); |
51 | collector.parameters | |
9346a6ac AL |
52 | } |
53 | ||
5099ac24 | 54 | struct ParameterCollector { |
5bcae85e | 55 | parameters: Vec<Parameter>, |
dfeec247 | 56 | include_nonconstraining: bool, |
9346a6ac AL |
57 | } |
58 | ||
5099ac24 | 59 | impl<'tcx> TypeVisitor<'tcx> for ParameterCollector { |
fc512014 | 60 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
1b1a35ee | 61 | match *t.kind() { |
04454e1e | 62 | ty::Projection(..) if !self.include_nonconstraining => { |
5bcae85e | 63 | // projections are not injective |
29967ef6 | 64 | return ControlFlow::CONTINUE; |
5bcae85e | 65 | } |
b7449926 | 66 | ty::Param(data) => { |
9e0c209e | 67 | self.parameters.push(Parameter::from(data)); |
5bcae85e SL |
68 | } |
69 | _ => {} | |
70 | } | |
9346a6ac | 71 | |
5bcae85e SL |
72 | t.super_visit_with(self) |
73 | } | |
9346a6ac | 74 | |
fc512014 | 75 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { |
0bf4aa26 XL |
76 | if let ty::ReEarlyBound(data) = *r { |
77 | self.parameters.push(Parameter::from(data)); | |
5bcae85e | 78 | } |
29967ef6 | 79 | ControlFlow::CONTINUE |
9346a6ac | 80 | } |
532ac7d7 | 81 | |
5099ac24 | 82 | fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
923072b8 | 83 | match c.kind() { |
ba9703b0 XL |
84 | ty::ConstKind::Unevaluated(..) if !self.include_nonconstraining => { |
85 | // Constant expressions are not injective | |
5099ac24 | 86 | return c.ty().visit_with(self); |
ba9703b0 XL |
87 | } |
88 | ty::ConstKind::Param(data) => { | |
89 | self.parameters.push(Parameter::from(data)); | |
90 | } | |
91 | _ => {} | |
532ac7d7 | 92 | } |
ba9703b0 XL |
93 | |
94 | c.super_visit_with(self) | |
532ac7d7 | 95 | } |
9346a6ac AL |
96 | } |
97 | ||
dc9dc135 XL |
98 | pub fn identify_constrained_generic_params<'tcx>( |
99 | tcx: TyCtxt<'tcx>, | |
e74abb32 | 100 | predicates: ty::GenericPredicates<'tcx>, |
dc9dc135 XL |
101 | impl_trait_ref: Option<ty::TraitRef<'tcx>>, |
102 | input_parameters: &mut FxHashSet<Parameter>, | |
103 | ) { | |
e74abb32 | 104 | let mut predicates = predicates.predicates.to_vec(); |
041b39d2 | 105 | setup_constraining_predicates(tcx, &mut predicates, impl_trait_ref, input_parameters); |
92a42be0 | 106 | } |
85aaf69f | 107 | |
92a42be0 SL |
108 | /// Order the predicates in `predicates` such that each parameter is |
109 | /// constrained before it is used, if that is possible, and add the | |
3b2f2976 | 110 | /// parameters so constrained to `input_parameters`. For example, |
92a42be0 | 111 | /// imagine the following impl: |
04454e1e FG |
112 | /// ```ignore (illustrative) |
113 | /// impl<T: Debug, U: Iterator<Item = T>> Trait for U | |
114 | /// ``` | |
92a42be0 SL |
115 | /// The impl's predicates are collected from left to right. Ignoring |
116 | /// the implicit `Sized` bounds, these are | |
2b03887a FG |
117 | /// * `T: Debug` |
118 | /// * `U: Iterator` | |
119 | /// * `<U as Iterator>::Item = T` -- a desugared ProjectionPredicate | |
92a42be0 SL |
120 | /// |
121 | /// When we, for example, try to go over the trait-reference | |
122 | /// `IntoIter<u32> as Trait`, we substitute the impl parameters with fresh | |
123 | /// variables and match them with the impl trait-ref, so we know that | |
124 | /// `$U = IntoIter<u32>`. | |
125 | /// | |
126 | /// However, in order to process the `$T: Debug` predicate, we must first | |
127 | /// know the value of `$T` - which is only given by processing the | |
128 | /// projection. As we occasionally want to process predicates in a single | |
129 | /// pass, we want the projection to come first. In fact, as projections | |
130 | /// can (acyclically) depend on one another - see RFC447 for details - we | |
131 | /// need to topologically sort them. | |
132 | /// | |
133 | /// We *do* have to be somewhat careful when projection targets contain | |
134 | /// projections themselves, for example in | |
2b03887a FG |
135 | /// |
136 | /// ```ignore (illustrative) | |
92a42be0 | 137 | /// impl<S,U,V,W> Trait for U where |
9fa01778 | 138 | /// /* 0 */ S: Iterator<Item = U>, |
92a42be0 SL |
139 | /// /* - */ U: Iterator, |
140 | /// /* 1 */ <U as Iterator>::Item: ToOwned<Owned=(W,<V as Iterator>::Item)> | |
9fa01778 | 141 | /// /* 2 */ W: Iterator<Item = V> |
92a42be0 | 142 | /// /* 3 */ V: Debug |
2b03887a FG |
143 | /// ``` |
144 | /// | |
92a42be0 SL |
145 | /// we have to evaluate the projections in the order I wrote them: |
146 | /// `V: Debug` requires `V` to be evaluated. The only projection that | |
147 | /// *determines* `V` is 2 (1 contains it, but *does not determine it*, | |
148 | /// as it is only contained within a projection), but that requires `W` | |
149 | /// which is determined by 1, which requires `U`, that is determined | |
150 | /// by 0. I should probably pick a less tangled example, but I can't | |
151 | /// think of any. | |
dc9dc135 | 152 | pub fn setup_constraining_predicates<'tcx>( |
dfeec247 | 153 | tcx: TyCtxt<'tcx>, |
dc9dc135 XL |
154 | predicates: &mut [(ty::Predicate<'tcx>, Span)], |
155 | impl_trait_ref: Option<ty::TraitRef<'tcx>>, | |
156 | input_parameters: &mut FxHashSet<Parameter>, | |
157 | ) { | |
92a42be0 SL |
158 | // The canonical way of doing the needed topological sort |
159 | // would be a DFS, but getting the graph and its ownership | |
160 | // right is annoying, so I am using an in-place fixed-point iteration, | |
161 | // which is `O(nt)` where `t` is the depth of type-parameter constraints, | |
162 | // remembering that `t` should be less than 7 in practice. | |
163 | // | |
164 | // Basically, I iterate over all projections and swap every | |
165 | // "ready" projection to the start of the list, such that | |
166 | // all of the projections before `i` are topologically sorted | |
167 | // and constrain all the parameters in `input_parameters`. | |
168 | // | |
169 | // In the example, `input_parameters` starts by containing `U` - which | |
170 | // is constrained by the trait-ref - and so on the first pass we | |
171 | // observe that `<U as Iterator>::Item = T` is a "ready" projection that | |
172 | // constrains `T` and swap it to front. As it is the sole projection, | |
173 | // no more swaps can take place afterwards, with the result being | |
174 | // * <U as Iterator>::Item = T | |
175 | // * T: Debug | |
176 | // * U: Iterator | |
dfeec247 XL |
177 | debug!( |
178 | "setup_constraining_predicates: predicates={:?} \ | |
9e0c209e | 179 | impl_trait_ref={:?} input_parameters={:?}", |
dfeec247 XL |
180 | predicates, impl_trait_ref, input_parameters |
181 | ); | |
92a42be0 SL |
182 | let mut i = 0; |
183 | let mut changed = true; | |
184 | while changed { | |
185 | changed = false; | |
186 | ||
187 | for j in i..predicates.len() { | |
3dfed10e XL |
188 | // Note that we don't have to care about binders here, |
189 | // as the impl trait ref never contains any late-bound regions. | |
5869c6ff XL |
190 | if let ty::PredicateKind::Projection(projection) = predicates[j].0.kind().skip_binder() |
191 | { | |
92a42be0 SL |
192 | // Special case: watch out for some kind of sneaky attempt |
193 | // to project out an associated type defined by this very | |
194 | // trait. | |
041b39d2 | 195 | let unbound_trait_ref = projection.projection_ty.trait_ref(tcx); |
dfeec247 | 196 | if Some(unbound_trait_ref) == impl_trait_ref { |
92a42be0 SL |
197 | continue; |
198 | } | |
199 | ||
200 | // A projection depends on its input types and determines its output | |
201 | // type. For example, if we have | |
202 | // `<<T as Bar>::Baz as Iterator>::Output = <U as Iterator>::Output` | |
203 | // Then the projection only applies if `T` is known, but it still | |
204 | // does not determine `U`. | |
5099ac24 | 205 | let inputs = parameters_for(&projection.projection_ty, true); |
c295e0f8 | 206 | let relies_only_on_inputs = inputs.iter().all(|p| input_parameters.contains(p)); |
92a42be0 SL |
207 | if !relies_only_on_inputs { |
208 | continue; | |
209 | } | |
5099ac24 | 210 | input_parameters.extend(parameters_for(&projection.term, false)); |
92a42be0 SL |
211 | } else { |
212 | continue; | |
213 | } | |
214 | // fancy control flow to bypass borrow checker | |
215 | predicates.swap(i, j); | |
216 | i += 1; | |
217 | changed = true; | |
85aaf69f | 218 | } |
dfeec247 XL |
219 | debug!( |
220 | "setup_constraining_predicates: predicates={:?} \ | |
9e0c209e | 221 | i={} impl_trait_ref={:?} input_parameters={:?}", |
dfeec247 XL |
222 | predicates, i, impl_trait_ref, input_parameters |
223 | ); | |
85aaf69f SL |
224 | } |
225 | } |