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