src/librustc_typeck/constrained_type_params.rs

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