diff options
Diffstat (limited to '')
-rw-r--r-- | compiler/rustc_typeck/src/constrained_generic_params.rs | 221 |
1 files changed, 221 insertions, 0 deletions
diff --git a/compiler/rustc_typeck/src/constrained_generic_params.rs b/compiler/rustc_typeck/src/constrained_generic_params.rs new file mode 100644 index 000000000..8428e4664 --- /dev/null +++ b/compiler/rustc_typeck/src/constrained_generic_params.rs @@ -0,0 +1,221 @@ +use rustc_data_structures::fx::FxHashSet; +use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor}; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_span::source_map::Span; +use std::ops::ControlFlow; + +#[derive(Clone, PartialEq, Eq, Hash, Debug)] +pub struct Parameter(pub u32); + +impl From<ty::ParamTy> for Parameter { + fn from(param: ty::ParamTy) -> Self { + Parameter(param.index) + } +} + +impl From<ty::EarlyBoundRegion> for Parameter { + fn from(param: ty::EarlyBoundRegion) -> Self { + Parameter(param.index) + } +} + +impl From<ty::ParamConst> for Parameter { + fn from(param: ty::ParamConst) -> Self { + Parameter(param.index) + } +} + +/// Returns the set of parameters constrained by the impl header. +pub fn parameters_for_impl<'tcx>( + impl_self_ty: Ty<'tcx>, + impl_trait_ref: Option<ty::TraitRef<'tcx>>, +) -> FxHashSet<Parameter> { + let vec = match impl_trait_ref { + Some(tr) => parameters_for(&tr, false), + None => parameters_for(&impl_self_ty, false), + }; + vec.into_iter().collect() +} + +/// If `include_nonconstraining` 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: &impl TypeVisitable<'tcx>, + include_nonconstraining: bool, +) -> Vec<Parameter> { + let mut collector = ParameterCollector { parameters: vec![], 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>) -> ControlFlow<Self::BreakTy> { + match *t.kind() { + ty::Projection(..) if !self.include_nonconstraining => { + // projections are not injective + return ControlFlow::CONTINUE; + } + ty::Param(data) => { + self.parameters.push(Parameter::from(data)); + } + _ => {} + } + + t.super_visit_with(self) + } + + fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { + if let ty::ReEarlyBound(data) = *r { + self.parameters.push(Parameter::from(data)); + } + ControlFlow::CONTINUE + } + + fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { + match c.kind() { + ty::ConstKind::Unevaluated(..) if !self.include_nonconstraining => { + // Constant expressions are not injective + return c.ty().visit_with(self); + } + ty::ConstKind::Param(data) => { + self.parameters.push(Parameter::from(data)); + } + _ => {} + } + + c.super_visit_with(self) + } +} + +pub fn identify_constrained_generic_params<'tcx>( + tcx: TyCtxt<'tcx>, + predicates: ty::GenericPredicates<'tcx>, + impl_trait_ref: Option<ty::TraitRef<'tcx>>, + input_parameters: &mut FxHashSet<Parameter>, +) { + let mut predicates = predicates.predicates.to_vec(); + setup_constraining_predicates(tcx, &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 +/// parameters so constrained to `input_parameters`. For example, +/// imagine the following impl: +/// ```ignore (illustrative) +/// 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>( + tcx: TyCtxt<'tcx>, + predicates: &mut [(ty::Predicate<'tcx>, Span)], + impl_trait_ref: Option<ty::TraitRef<'tcx>>, + input_parameters: &mut FxHashSet<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 + debug!( + "setup_constraining_predicates: predicates={:?} \ + impl_trait_ref={:?} input_parameters={:?}", + predicates, impl_trait_ref, input_parameters + ); + let mut i = 0; + let mut changed = true; + while changed { + changed = false; + + for j in i..predicates.len() { + // Note that we don't have to care about binders here, + // as the impl trait ref never contains any late-bound regions. + if let ty::PredicateKind::Projection(projection) = predicates[j].0.kind().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(tcx); + if Some(unbound_trait_ref) == 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, 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.term, false)); + } else { + continue; + } + // fancy control flow to bypass borrow checker + predicates.swap(i, j); + i += 1; + changed = true; + } + debug!( + "setup_constraining_predicates: predicates={:?} \ + i={} impl_trait_ref={:?} input_parameters={:?}", + predicates, i, impl_trait_ref, input_parameters + ); + } +} |