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