compiler/rustc_typeck/src/constrained_generic_params.rs

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