| // Copyright 2015 The Rust Project Developers. See the COPYRIGHT |
| // file at the top-level directory of this distribution and at |
| // http://rust-lang.org/COPYRIGHT. |
| // |
| // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or |
| // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license |
| // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your |
| // option. This file may not be copied, modified, or distributed |
| // except according to those terms. |
| |
| use rustc::ty::{self, Ty}; |
| use rustc::ty::fold::{TypeFoldable, TypeVisitor}; |
| use std::collections::HashSet; |
| |
| #[derive(Clone, PartialEq, Eq, Hash, Debug)] |
| pub enum Parameter { |
| Type(ty::ParamTy), |
| Region(ty::EarlyBoundRegion), |
| } |
| |
| /// If `include_projections` is false, returns the list of parameters that are |
| /// constrained by `t` - i.e. the value of each parameter in the list is |
| /// uniquely determined by `t` (see RFC 447). If it is true, return the list |
| /// of parameters whose values are needed in order to constrain `ty` - these |
| /// differ, with the latter being a superset, in the presence of projections. |
| pub fn parameters_for<'tcx, T>(t: &T, |
| include_nonconstraining: bool) |
| -> Vec<Parameter> |
| where T: TypeFoldable<'tcx> |
| { |
| |
| let mut collector = ParameterCollector { |
| parameters: vec![], |
| include_nonconstraining: include_nonconstraining |
| }; |
| t.visit_with(&mut collector); |
| collector.parameters |
| } |
| |
| struct ParameterCollector { |
| parameters: Vec<Parameter>, |
| include_nonconstraining: bool |
| } |
| |
| impl<'tcx> TypeVisitor<'tcx> for ParameterCollector { |
| fn visit_ty(&mut self, t: Ty<'tcx>) -> bool { |
| match t.sty { |
| ty::TyProjection(..) if !self.include_nonconstraining => { |
| // projections are not injective |
| return false; |
| } |
| ty::TyParam(ref d) => { |
| self.parameters.push(Parameter::Type(d.clone())); |
| } |
| _ => {} |
| } |
| |
| t.super_visit_with(self) |
| } |
| |
| fn visit_region(&mut self, r: ty::Region) -> bool { |
| match r { |
| ty::ReEarlyBound(data) => { |
| self.parameters.push(Parameter::Region(data)); |
| } |
| _ => {} |
| } |
| false |
| } |
| } |
| |
| pub fn identify_constrained_type_params<'tcx>(predicates: &[ty::Predicate<'tcx>], |
| impl_trait_ref: Option<ty::TraitRef<'tcx>>, |
| input_parameters: &mut HashSet<Parameter>) |
| { |
| let mut predicates = predicates.to_owned(); |
| setup_constraining_predicates(&mut predicates, impl_trait_ref, input_parameters); |
| } |
| |
| |
| /// Order the predicates in `predicates` such that each parameter is |
| /// constrained before it is used, if that is possible, and add the |
| /// paramaters so constrained to `input_parameters`. For example, |
| /// imagine the following impl: |
| /// |
| /// impl<T: Debug, U: Iterator<Item=T>> Trait for U |
| /// |
| /// The impl's predicates are collected from left to right. Ignoring |
| /// the implicit `Sized` bounds, these are |
| /// * T: Debug |
| /// * U: Iterator |
| /// * <U as Iterator>::Item = T -- a desugared ProjectionPredicate |
| /// |
| /// When we, for example, try to go over the trait-reference |
| /// `IntoIter<u32> as Trait`, we substitute the impl parameters with fresh |
| /// variables and match them with the impl trait-ref, so we know that |
| /// `$U = IntoIter<u32>`. |
| /// |
| /// However, in order to process the `$T: Debug` predicate, we must first |
| /// know the value of `$T` - which is only given by processing the |
| /// projection. As we occasionally want to process predicates in a single |
| /// pass, we want the projection to come first. In fact, as projections |
| /// can (acyclically) depend on one another - see RFC447 for details - we |
| /// need to topologically sort them. |
| /// |
| /// We *do* have to be somewhat careful when projection targets contain |
| /// projections themselves, for example in |
| /// impl<S,U,V,W> Trait for U where |
| /// /* 0 */ S: Iterator<Item=U>, |
| /// /* - */ U: Iterator, |
| /// /* 1 */ <U as Iterator>::Item: ToOwned<Owned=(W,<V as Iterator>::Item)> |
| /// /* 2 */ W: Iterator<Item=V> |
| /// /* 3 */ V: Debug |
| /// we have to evaluate the projections in the order I wrote them: |
| /// `V: Debug` requires `V` to be evaluated. The only projection that |
| /// *determines* `V` is 2 (1 contains it, but *does not determine it*, |
| /// as it is only contained within a projection), but that requires `W` |
| /// which is determined by 1, which requires `U`, that is determined |
| /// by 0. I should probably pick a less tangled example, but I can't |
| /// think of any. |
| pub fn setup_constraining_predicates<'tcx>(predicates: &mut [ty::Predicate<'tcx>], |
| impl_trait_ref: Option<ty::TraitRef<'tcx>>, |
| input_parameters: &mut HashSet<Parameter>) |
| { |
| // The canonical way of doing the needed topological sort |
| // would be a DFS, but getting the graph and its ownership |
| // right is annoying, so I am using an in-place fixed-point iteration, |
| // which is `O(nt)` where `t` is the depth of type-parameter constraints, |
| // remembering that `t` should be less than 7 in practice. |
| // |
| // Basically, I iterate over all projections and swap every |
| // "ready" projection to the start of the list, such that |
| // all of the projections before `i` are topologically sorted |
| // and constrain all the parameters in `input_parameters`. |
| // |
| // In the example, `input_parameters` starts by containing `U` - which |
| // is constrained by the trait-ref - and so on the first pass we |
| // observe that `<U as Iterator>::Item = T` is a "ready" projection that |
| // constrains `T` and swap it to front. As it is the sole projection, |
| // no more swaps can take place afterwards, with the result being |
| // * <U as Iterator>::Item = T |
| // * T: Debug |
| // * U: Iterator |
| let mut i = 0; |
| let mut changed = true; |
| while changed { |
| changed = false; |
| |
| for j in i..predicates.len() { |
| |
| if let ty::Predicate::Projection(ref poly_projection) = predicates[j] { |
| // Note that we can skip binder here because the impl |
| // trait ref never contains any late-bound regions. |
| let projection = poly_projection.skip_binder(); |
| |
| // Special case: watch out for some kind of sneaky attempt |
| // to project out an associated type defined by this very |
| // trait. |
| let unbound_trait_ref = &projection.projection_ty.trait_ref; |
| if Some(unbound_trait_ref.clone()) == impl_trait_ref { |
| continue; |
| } |
| |
| // A projection depends on its input types and determines its output |
| // type. For example, if we have |
| // `<<T as Bar>::Baz as Iterator>::Output = <U as Iterator>::Output` |
| // Then the projection only applies if `T` is known, but it still |
| // does not determine `U`. |
| |
| let inputs = parameters_for(&projection.projection_ty.trait_ref, true); |
| let relies_only_on_inputs = inputs.iter().all(|p| input_parameters.contains(&p)); |
| if !relies_only_on_inputs { |
| continue; |
| } |
| input_parameters.extend(parameters_for(&projection.ty, false)); |
| } else { |
| continue; |
| } |
| // fancy control flow to bypass borrow checker |
| predicates.swap(i, j); |
| i += 1; |
| changed = true; |
| } |
| } |
| } |