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