1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
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<TyCtxt<'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<TyCtxt<'tcx>> for ParameterCollector {
fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
match *t.kind() {
ty::Alias(..) 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
///
/// ```ignore (illustrative)
/// 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::Clause<'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::ClauseKind::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
);
}
}