pub fn setup_constraining_predicates<'tcx>(
tcx: TyCtxt<'tcx>,
predicates: &mut [(Clause<'tcx>, Span)],
impl_trait_ref: Option<TraitRef<'tcx>>,
input_parameters: &mut FxHashSet<Parameter>
)
Expand description
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.