rayon hangs

[compiler-errors]

pub trait ParallelIterator {
    type Item;
}

macro_rules! multizip_impls {
    ($(
        $Tuple:ident {
            $(($idx:tt) -> $T:ident)+
        }
    )+) => {
        $(
            impl<$( $T, )+> ParallelIterator for ($( $T, )+)
            where
                $(
                    $T: ParallelIterator,
                    $T::Item: ParallelIterator,
                )+
            {
                type Item = ();
            }
        )*
    }
}

multizip_impls! {
    Tuple1 {
        (0) -> A
    }
    Tuple2 {
        (0) -> A
        (1) -> B
    }
    Tuple3 {
        (0) -> A
        (1) -> B
        (2) -> C
    }
    Tuple4 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
    }
    Tuple5 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
    }
    Tuple6 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
    }
    Tuple7 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
    }
    Tuple8 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
        (7) -> H
    }
    Tuple9 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
        (7) -> H
        (8) -> I
    }
    Tuple10 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
        (7) -> H
        (8) -> I
        (9) -> J
    }
    Tuple11 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
        (7) -> H
        (8) -> I
        (9) -> J
        (10) -> K
    }
    Tuple12 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
        (7) -> H
        (8) -> I
        (9) -> J
        (10) -> K
        (11) -> L
    }
}

fn main() {}

[compiler-errors]

Some sort of combinatorial blow up when we are trying to prove the WC on each impl are well-formed -- I think we might be trying prove things like A::Item: ParallelIterator via B::Item: ParallelIterator leading to way too many alias-relate goals being emitted even though they're effectively useless.

[lcnr]

this very much makes sense to me🤔 can chat about it tomorrow, I guess we may want to assume (for completeness, not soundness) that all self-types of ParamEnv are normalized, and then do a structural lookup when considering param env candidates, similar to impls

edit: or well, unsure how this interacts with normalizing in an unnormalized env xx

also, how to avoid this hang when first normalizing the env

[lcnr]

rayon has a blanket impl of ParallelIterator

pub trait IntoParallelIterator {
    type Item;
}

trait ParallelIterator {}
impl<T: ParallelIterator> IntoParallelIterator for T {
    type Item = T;
}

macro_rules! multizip_impls {
    ($(
        $Tuple:ident {
            $(($idx:tt) -> $T:ident)+
        }
    )+) => {
        $(
            impl<$( $T, )+> IntoParallelIterator for ($( $T, )+)
            where
                $(
                    $T: IntoParallelIterator,
                    $T::Item: ParallelIterator,
                )+
            {
                type Item = ();
            }
        )*
    }
}

multizip_impls! {
    Tuple1 {
        (0) -> A
    }
    Tuple2 {
        (0) -> A
        (1) -> B
    }
    Tuple3 {
        (0) -> A
        (1) -> B
        (2) -> C
    }
    Tuple4 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
    }
    Tuple5 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
    }
    Tuple6 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
    }
    Tuple7 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
    }
    Tuple8 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
        (7) -> H
    }
    Tuple9 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
        (7) -> H
        (8) -> I
    }
    Tuple10 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
        (7) -> H
        (8) -> I
        (9) -> J
    }
    Tuple11 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
        (7) -> H
        (8) -> I
        (9) -> J
        (10) -> K
    }
    Tuple12 {
        (0) -> A
        (1) -> B
        (2) -> C
        (3) -> D
        (4) -> E
        (5) -> F
        (6) -> G
        (7) -> H
        (8) -> I
        (9) -> J
        (10) -> K
        (11) -> L
    }
}

fn main() {}

[lcnr]

rayon has a blanket impl of ParallelIterator

This minimization is still insufficient (now). With rust-lang/rust#124852 this test compiles but rayon hangs

[lcnr]

The hang occurs in fn check_type_bounds: minimization without relying on this:

trait ParallelIterator: Sized {
    type Item;
}
trait IntoParallelIterator {
    type Iter: ParallelIterator<Item = Self::Item>;
    type Item;
}
impl<T: ParallelIterator> IntoParallelIterator for T {
    type Iter = T;
    type Item = T::Item;
}

macro_rules! multizip_impls {
    ($($T:ident),+) => {
       fn foo<$( $T, )+>() where
        $(
            $T: IntoParallelIterator,
            $T::Iter: ParallelIterator,
        )+
            ($( $T, )+): IntoParallelIterator<Item = ($( $T::Item, )+)>,
        {}
    }
}

multizip_impls! { A, B, C, D, E, F, G, H, I, J, K, L }

The added ($( $T, )+): IntoParallelIterator<Item = ($( $T::Item, )+)> where-clause disables the alias-relate fast path optimization

[lcnr]

To fix this we can either strengthen rust-lang/rust#124852 which feels fairly hacky.

I'd like to instead look into making fn rebase_provisional_cache_entries far more powerful so that we don't need rust-lang/rust#124852 at all.

[lcnr]

Avoiding the blowup when dealing with multiple <T as Trait>::Assoc: Trait bounds is harder than I thought.

Improving fn rebase_provisional_cache_entries is insufficient as we sadly have to rerun cycle heads multiple times when dealing with rigid aliases:

• normalizes_to(<T as Trait>::Assoc, ?x)
  • ...
    • normalizes_to(<T as Trait>::Assoc, ?x) cycle with initial provisional result: Err(NoSolution)
  • result: treat as RigidAlias: Certainty::Yes, constrain ?x to T::Assoc
  • differs from initial provisional result, need to rerun :x

normalizes_to(<T as Trait>::Assoc, ?x) tries to prove T: Trait which then tries to use any of the other 11 <U as Trait>::Assoc: Trait where-bounds, which results in a nested normalizes_to(<T as Trait>::Assoc, ?y) goal which once again cycles with itself. This results in 2^12 reruns due to changed initial provisional results

[lcnr]

I've extended rust-lang/rust#124852 to only use where-bounds to extend the number of "nameable placeholders" if their projection term itself is nameable. This fixes rayon again

[lcnr]

Let's look at a minimized repro and its proof tree

trait IsAssoc {}
trait ParamOrIndir {
    type Assoc: ?Sized;
}
impl<T: IsAssoc + ?Sized> ParamOrIndir for T {
    type Assoc = ();
}

fn foo<A, B>()
where 
    A: ParamOrIndir,
    B: ParamOrIndir,
    <A as ParamOrIndir>::Assoc: IsAssoc,
    <B as ParamOrIndir>::Assoc: IsAssoc,
{}

• A: ParamOrIndir
  • impl cand A: IsAssoc¹
    • where-bound A::Assoc: IsAssoc
      • normalize A::Assoc
        • via impl (ignored: A: ParamOrIndir via a ParamEnv candidate)
          • A: IsAssoc -> cycle overflow
        • rigid
    • where-bound B::Assoc: IsAssoc
      • normalize B::Assoc²
        • via impl (ignored: B: ParamOrIndir via a ParamEnv candidate)
          • B: IsAssoc
            • where-bound A::Assoc: IsAssoc
              • normalize A::Assoc -> cycle overflow
            • where-bound B::Assoc: IsAssoc
              • normalize B::Assoc -> cycle overflow
        • rigid
    • NoSolution
  • where-bound -> trivial

One fix would be to only assemble candidates which matter! If we start by looking at trivial builtin and env candidates and only consider impl candidates if no preferred candidates exist, we'd avoid these hangs. This does not hang with rust-lang/rust@11e8a21. Another alternative would be to evaluate all goals, but when dropping candidates during winnowing, track in the search graph that cycles were not relevant for the final result.

Footnotes

1. Does not hold, is used in the ignored impl candidate when normalizing A::Assoc, needs rerun ↩

2. Results in a rigid alias, is used in the ignored impl candidate, needs rerun ↩