# new solver hangs

## rigid alias as potentially non-rigid

https://github.com/rust-lang/trait-system-refactor-initiative/issues/109

two ideas:

#### eagerly reject definitely rigid aliases in normalizes-to

https://github.com/rust-lang/rust/pull/125334

does not work for rayon as rayon has a blanket impl whose nested goals fail instead

pub trait ParallelIterator {
    type Item;
}

trait Trait {}

macro_rules! multizip_impl {
    ($($T:ident),+) => {
        impl<$( $T, )+> Trait for ($( $T, )+)
        where
            $(
                $T: ParallelIterator,
                $T::Item: ParallelIterator<Item = u32>,
            )+
        {}
    }
}

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

fn main() {}

how this proceeds...

* proving `A: ParallelIterator`...
* we try `A::Item: ParallelIterator` and normalize `A::Item -> A`
* to do that normalization we look to show that `A: ParallelIterator`
* direct cycle
* we try `B::Item: ParallelIterator` and normalize `B::Item -> A`
* to do that normalization we look to show that `B: ParallelIterator`
* in the environment we find `B: ParallelIterator` but also `A::Item: ParallelIterator`, `C`, .. `L`
* same for `C`

...so we do `O(n!)` work.

Note that in original version there was no `Item = u32`.

in old solver:

* we do param-env normalization
* at each step, we assume that the existing where-clauses are rigid

where is it fruitful

// very easy

fn foo<A, B>()
where
    A: Iterator<Item = B>,
    A::Item: Iterator,
{}

// ---

// indirect, requires combining blanket impl with environment

fn foo<A, B>()
where
    A: Iterator<Item = B>,
    <A as IntoIterator>::Item: Iterator,
{}

impl<I: Iterator> IntoIterator for I {
    type Item = <I as Iterator>::Item;
}

// ---

trait IteratorWithUnusedArg<T: ?Sized> {
    type Item: ?Sized;
}

trait IntoIterator {
    type Item: ?Sized;
}

fn foo<A, B>()
where
    A: IteratorWithUnusedArg<<A as IntoIterator>::Item, Item = B>,
    <A as IntoIterator>::Item: IteratorWithUnusedArg<u32>,
{}

impl<I: ?Sized + IteratorWithUnusedArg<<I as IntoIterator>::Item>> IntoIterator for I {
    type Item = <I as IteratorWithUnusedArg<<I as IntoIterator>::Item>>::Item;
}

Hypothesis:

* The only way that normalizing `T = <P0 as Iterator<P1..Pn>>::Foo` can yield `Q` (where `Q` not free in `T`) is if there is some other thing in the environment that normalizes to a type `U` including `Q` ?
* this is what is impl'd in #124852
* but it cannot rule out `P0::Item = P0::OtherItem`, as in the impl in https://github.com/rust-lang/rust/issues/125269 (even if the cause of that hang is different)
* would be helped by the "is_rigid_alias" test described at first
* concern: currently have `for<'a> fn(&'a <?x as Subtrait<'a>>::Assoc)` will be `for<'a> where { ?x: Subtrait<'a> } fn(&'a <?x as Subtrait<'a>>::Assoc)`, with where-clauses on binders we end up putting `?x: Subtrait<'a>` into the environment inside of this function pointer, elaborating that could put `?x: Supertrait<Assoc = ?x>` into the env?
* Prolly not an issue in practice, have bigger issues with that anyways :3

#### eagerly fail "rigid-ty alias-relate alias" if the rigid type contains a placeholder not nameable by the alias

https://github.com/rust-lang/rust/pull/124852

Both fix some, but not all issues of this kind

## ambig alias != infer var weakens cycle detection

https://github.com/rust-lang/rust/issues/125269

- can be fixed by eagerly normalizing before evaluating nested goals: https://github.com/rust-lang/rust/pull/125343

## separate: highly involved cycles requiring >1 fixpoint iterations

- most notably fuchsia

Currently working on a search graph PR. Found another issue :<

*edit: 2 minutes ago I ended up questioning whether this is sound at all :3*

- `?t: Trait` with 2 candidates
- `impl<T> Trait for Vec<T> where T: Trait`
- first iteration, inductive cycle -> error
- `impl Trait for u32 {}`
- ok: `?t = u32`
- result of first iteration: `OK: ?t = u32`
- `impl<T> Trait for Vec<T> where T: Trait`
- first iteration, inductive cycle -> ok `?t: u32`
- result `?t = Vec<u32>`
- `impl Trait for u32 {}`
- ok: `?t = u32`
- result of second iteration `Ambig`

constraints from fixpoints aren't monotonically increasing :skull: