src/librustc_typeck/constrained_type_params.rs

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