// option. This file may not be copied, modified, or distributed
// except according to those terms.
-use middle::subst;
-use middle::ty::{self, Ty};
-
-use std::collections::HashSet;
-use std::rc::Rc;
+use rustc::ty::{self, Ty, TyCtxt};
+use rustc::ty::fold::{TypeFoldable, TypeVisitor};
+use rustc::util::nodemap::FxHashSet;
+use syntax::source_map::Span;
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
-pub enum Parameter {
- Type(ty::ParamTy),
- Region(ty::EarlyBoundRegion),
+pub struct Parameter(pub u32);
+
+impl From<ty::ParamTy> for Parameter {
+ fn from(param: ty::ParamTy) -> Self { Parameter(param.idx) }
}
-pub fn parameters_for_type<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> {
- ty.walk()
- .flat_map(|ty| parameters_for_type_shallow(ty).into_iter())
- .collect()
+impl From<ty::EarlyBoundRegion> for Parameter {
+ fn from(param: ty::EarlyBoundRegion) -> Self { Parameter(param.index) }
}
-pub fn parameters_for_trait_ref<'tcx>(trait_ref: &Rc<ty::TraitRef<'tcx>>) -> Vec<Parameter> {
- let mut region_parameters =
- parameters_for_regions_in_substs(&trait_ref.substs);
+/// Return 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()
+}
- let type_parameters =
- trait_ref.substs.types.iter()
- .flat_map(|ty| parameters_for_type(ty).into_iter());
+/// If `include_projections` 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>(t: &T,
+ include_nonconstraining: bool)
+ -> Vec<Parameter>
+ where T: TypeFoldable<'tcx>
+{
- region_parameters.extend(type_parameters);
+ let mut collector = ParameterCollector {
+ parameters: vec![],
+ include_nonconstraining,
+ };
+ t.visit_with(&mut collector);
+ collector.parameters
+}
- region_parameters
+struct ParameterCollector {
+ parameters: Vec<Parameter>,
+ include_nonconstraining: bool
}
-fn parameters_for_type_shallow<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> {
- match ty.sty {
- ty::ty_param(ref d) =>
- vec![Parameter::Type(d.clone())],
- ty::ty_rptr(region, _) =>
- parameters_for_region(region).into_iter().collect(),
- ty::ty_struct(_, substs) |
- ty::ty_enum(_, substs) =>
- parameters_for_regions_in_substs(substs),
- ty::ty_trait(ref data) =>
- parameters_for_regions_in_substs(&data.principal.skip_binder().substs),
- _ =>
- vec![],
+impl<'tcx> TypeVisitor<'tcx> for ParameterCollector {
+ fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
+ match t.sty {
+ ty::Projection(..) | ty::Opaque(..) if !self.include_nonconstraining => {
+ // projections are not injective
+ return false;
+ }
+ ty::Param(data) => {
+ self.parameters.push(Parameter::from(data));
+ }
+ _ => {}
+ }
+
+ t.super_visit_with(self)
}
-}
-fn parameters_for_regions_in_substs(substs: &subst::Substs) -> Vec<Parameter> {
- substs.regions()
- .iter()
- .filter_map(|r| parameters_for_region(r))
- .collect()
+ fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
+ if let ty::ReEarlyBound(data) = *r {
+ self.parameters.push(Parameter::from(data));
+ }
+ false
+ }
}
-fn parameters_for_region(region: &ty::Region) -> Option<Parameter> {
- match *region {
- ty::ReEarlyBound(data) => Some(Parameter::Region(data)),
- _ => None,
- }
+pub fn identify_constrained_type_params<'tcx>(tcx: TyCtxt<'_, 'tcx, 'tcx>,
+ predicates: &ty::GenericPredicates<'tcx>,
+ impl_trait_ref: Option<ty::TraitRef<'tcx>>,
+ input_parameters: &mut FxHashSet<Parameter>)
+{
+ let mut predicates = predicates.predicates.clone();
+ setup_constraining_predicates(tcx, &mut predicates, impl_trait_ref, input_parameters);
}
-pub fn identify_constrained_type_params<'tcx>(_tcx: &ty::ctxt<'tcx>,
- predicates: &[ty::Predicate<'tcx>],
- impl_trait_ref: Option<Rc<ty::TraitRef<'tcx>>>,
- input_parameters: &mut HashSet<Parameter>)
+
+/// 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:
+///
+/// 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,
+ predicates: &mut [(ty::Predicate<'tcx>, Span)],
+ impl_trait_ref: Option<ty::TraitRef<'tcx>>,
+ input_parameters: &mut FxHashSet<Parameter>)
{
- loop {
- let num_inputs = input_parameters.len();
-
- let poly_projection_predicates = // : iterator over PolyProjectionPredicate
- predicates.iter()
- .filter_map(|predicate| {
- match *predicate {
- ty::Predicate::Projection(ref data) => Some(data.clone()),
- _ => None,
- }
- });
-
- for poly_projection in poly_projection_predicates {
- // Note that we can skip binder here because the impl
- // trait ref never contains any late-bound regions.
- let projection = poly_projection.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;
- if Some(unbound_trait_ref.clone()) == impl_trait_ref {
+ // 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() {
+ if let ty::Predicate::Projection(ref poly_projection) = predicates[j].0 {
+ // Note that we can skip binder here because the impl
+ // trait ref never contains any late-bound regions.
+ let projection = poly_projection.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.clone()) == 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.trait_ref(tcx), 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.ty, false));
+ } else {
continue;
}
-
- let inputs = parameters_for_trait_ref(&projection.projection_ty.trait_ref);
- let relies_only_on_inputs = inputs.iter().all(|p| input_parameters.contains(&p));
- if relies_only_on_inputs {
- input_parameters.extend(parameters_for_type(projection.ty));
- }
- }
-
- if input_parameters.len() == num_inputs {
- break;
+ // 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);
}
}
projects / rustc.git / blobdiff