Function rustc_hir_analysis::constrained_generic_params::setup_constraining_predicates

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