1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use rustc::ty::{self, Ty};
12 use rustc::ty::fold::{TypeFoldable, TypeVisitor};
13 use rustc::util::nodemap::FxHashSet;
15 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
16 pub struct Parameter(pub u32);
18 impl From<ty::ParamTy> for Parameter {
19 fn from(param: ty::ParamTy) -> Self { Parameter(param.idx) }
22 impl From<ty::EarlyBoundRegion> for Parameter {
23 fn from(param: ty::EarlyBoundRegion) -> Self { Parameter(param.index) }
26 /// Return the set of parameters constrained by the impl header.
27 pub fn parameters_for_impl<'tcx>(impl_self_ty: Ty<'tcx>,
28 impl_trait_ref: Option<ty::TraitRef<'tcx>>)
29 -> FxHashSet<Parameter>
31 let vec = match impl_trait_ref {
32 Some(tr) => parameters_for(&tr, false),
33 None => parameters_for(&impl_self_ty, false),
35 vec.into_iter().collect()
38 /// If `include_projections` is false, returns the list of parameters that are
39 /// constrained by `t` - i.e. the value of each parameter in the list is
40 /// uniquely determined by `t` (see RFC 447). If it is true, return the list
41 /// of parameters whose values are needed in order to constrain `ty` - these
42 /// differ, with the latter being a superset, in the presence of projections.
43 pub fn parameters_for<'tcx, T>(t: &T,
44 include_nonconstraining: bool)
46 where T: TypeFoldable<'tcx>
49 let mut collector = ParameterCollector {
51 include_nonconstraining: include_nonconstraining
53 t.visit_with(&mut collector);
57 struct ParameterCollector {
58 parameters: Vec<Parameter>,
59 include_nonconstraining: bool
62 impl<'tcx> TypeVisitor<'tcx> for ParameterCollector {
63 fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
65 ty::TyProjection(..) | ty::TyAnon(..) if !self.include_nonconstraining => {
66 // projections are not injective
69 ty::TyParam(data) => {
70 self.parameters.push(Parameter::from(data));
75 t.super_visit_with(self)
78 fn visit_region(&mut self, r: &'tcx ty::Region) -> bool {
80 ty::ReEarlyBound(data) => {
81 self.parameters.push(Parameter::from(data));
89 pub fn identify_constrained_type_params<'tcx>(predicates: &[ty::Predicate<'tcx>],
90 impl_trait_ref: Option<ty::TraitRef<'tcx>>,
91 input_parameters: &mut FxHashSet<Parameter>)
93 let mut predicates = predicates.to_owned();
94 setup_constraining_predicates(&mut predicates, impl_trait_ref, input_parameters);
98 /// Order the predicates in `predicates` such that each parameter is
99 /// constrained before it is used, if that is possible, and add the
100 /// paramaters so constrained to `input_parameters`. For example,
101 /// imagine the following impl:
103 /// impl<T: Debug, U: Iterator<Item=T>> Trait for U
105 /// The impl's predicates are collected from left to right. Ignoring
106 /// the implicit `Sized` bounds, these are
109 /// * <U as Iterator>::Item = T -- a desugared ProjectionPredicate
111 /// When we, for example, try to go over the trait-reference
112 /// `IntoIter<u32> as Trait`, we substitute the impl parameters with fresh
113 /// variables and match them with the impl trait-ref, so we know that
114 /// `$U = IntoIter<u32>`.
116 /// However, in order to process the `$T: Debug` predicate, we must first
117 /// know the value of `$T` - which is only given by processing the
118 /// projection. As we occasionally want to process predicates in a single
119 /// pass, we want the projection to come first. In fact, as projections
120 /// can (acyclically) depend on one another - see RFC447 for details - we
121 /// need to topologically sort them.
123 /// We *do* have to be somewhat careful when projection targets contain
124 /// projections themselves, for example in
125 /// impl<S,U,V,W> Trait for U where
126 /// /* 0 */ S: Iterator<Item=U>,
127 /// /* - */ U: Iterator,
128 /// /* 1 */ <U as Iterator>::Item: ToOwned<Owned=(W,<V as Iterator>::Item)>
129 /// /* 2 */ W: Iterator<Item=V>
131 /// we have to evaluate the projections in the order I wrote them:
132 /// `V: Debug` requires `V` to be evaluated. The only projection that
133 /// *determines* `V` is 2 (1 contains it, but *does not determine it*,
134 /// as it is only contained within a projection), but that requires `W`
135 /// which is determined by 1, which requires `U`, that is determined
136 /// by 0. I should probably pick a less tangled example, but I can't
138 pub fn setup_constraining_predicates<'tcx>(predicates: &mut [ty::Predicate<'tcx>],
139 impl_trait_ref: Option<ty::TraitRef<'tcx>>,
140 input_parameters: &mut FxHashSet<Parameter>)
142 // The canonical way of doing the needed topological sort
143 // would be a DFS, but getting the graph and its ownership
144 // right is annoying, so I am using an in-place fixed-point iteration,
145 // which is `O(nt)` where `t` is the depth of type-parameter constraints,
146 // remembering that `t` should be less than 7 in practice.
148 // Basically, I iterate over all projections and swap every
149 // "ready" projection to the start of the list, such that
150 // all of the projections before `i` are topologically sorted
151 // and constrain all the parameters in `input_parameters`.
153 // In the example, `input_parameters` starts by containing `U` - which
154 // is constrained by the trait-ref - and so on the first pass we
155 // observe that `<U as Iterator>::Item = T` is a "ready" projection that
156 // constrains `T` and swap it to front. As it is the sole projection,
157 // no more swaps can take place afterwards, with the result being
158 // * <U as Iterator>::Item = T
161 debug!("setup_constraining_predicates: predicates={:?} \
162 impl_trait_ref={:?} input_parameters={:?}",
163 predicates, impl_trait_ref, input_parameters);
165 let mut changed = true;
169 for j in i..predicates.len() {
170 if let ty::Predicate::Projection(ref poly_projection) = predicates[j] {
171 // Note that we can skip binder here because the impl
172 // trait ref never contains any late-bound regions.
173 let projection = poly_projection.skip_binder();
175 // Special case: watch out for some kind of sneaky attempt
176 // to project out an associated type defined by this very
178 let unbound_trait_ref = &projection.projection_ty.trait_ref;
179 if Some(unbound_trait_ref.clone()) == impl_trait_ref {
183 // A projection depends on its input types and determines its output
184 // type. For example, if we have
185 // `<<T as Bar>::Baz as Iterator>::Output = <U as Iterator>::Output`
186 // Then the projection only applies if `T` is known, but it still
187 // does not determine `U`.
189 let inputs = parameters_for(&projection.projection_ty.trait_ref, true);
190 let relies_only_on_inputs = inputs.iter().all(|p| input_parameters.contains(&p));
191 if !relies_only_on_inputs {
194 input_parameters.extend(parameters_for(&projection.ty, false));
198 // fancy control flow to bypass borrow checker
199 predicates.swap(i, j);
203 debug!("setup_constraining_predicates: predicates={:?} \
204 i={} impl_trait_ref={:?} input_parameters={:?}",
205 predicates, i, impl_trait_ref, input_parameters);