regression: overflow evaluating the requirement

[BoxyUwU]

• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/gh/DanielGilchrist.poke_search_cli/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/reg/triangulate-0.2.0/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/reg/similari-0.26.2/log.txt

[INFO] [stdout] error[E0275]: overflow evaluating the requirement `NaturePokeathlonStatAffect: Unpin`
[INFO] [stdout]      |
[INFO] [stdout]      = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`poke_search`)
[INFO] [stdout] note: required because it appears within the type `PhantomData<NaturePokeathlonStatAffect>`
[INFO] [stdout]     --> /rustc/08328a323ecd80b443a8fcc72c6b1071f48e233f/library/core/src/marker.rs:740:12

[compiler-errors]

This regressed in #126128, cc @lcnr

[lcnr]

Alright, it would be very useful to get a minimization of the underlying pattern here. I think we likely want to accept this breakage 🤔

[theemathas]

Outdated comment

Somewhat minimized from the triangulate crate:

Code (109 lines)

use std::{convert::TryInto, marker::PhantomData};

struct PolygonElement<Index>(Index);

trait PolygonList<'p>: 'p {
    type Vertex: 'p;
    type Index: 'p;
    type IntoItem: Into<PolygonElement<Self::Index>>;
    type Iter<'i>: Iterator<Item = Self::IntoItem>
    where
        Self: 'i,
        Self::Vertex: 'i,
        'p: 'i;

    fn iter_indices<'i>(&'i self) -> Self::Iter<'i>
    where
        Self: 'i,
        Self::Vertex: 'i,
        'p: 'i;
}

struct IndexWithIter<'i, Iter, OldIndex: Mappable<Old>, New: TryInto<Old>, Old: TryInto<New>> {
    iter: Iter,
    _phantom: PhantomData<&'i (OldIndex, New, Old)>,
}

impl<'i, Iter: Iterator + 'i, OldIndex: Mappable<Old>, New: TryInto<Old>, Old: TryInto<New>>
    IndexWithIter<'i, Iter, OldIndex, New, Old>
where
    Iter::Item: Into<PolygonElement<OldIndex>>,
    OldIndex::Output<New>: Mappable<New, Output<Old> = OldIndex>,
{
    fn new(iter: Iter) -> Self {
        unimplemented!()
    }
}

impl<'i, Iter: Iterator + 'i, OldIndex: Mappable<New>, In: TryInto<New>, New: TryInto<In>> Iterator
    for IndexWithIter<'i, Iter, OldIndex, In, New>
{
    type Item = PolygonElement<OldIndex::Output<In>>;

    fn next(&mut self) -> Option<Self::Item> {
        unimplemented!()
    }
}

struct IndexWith<
    'p,
    P: PolygonList<'p, Index = OldIndex>,
    OldIndex: Mappable<Old>,
    Old: TryInto<New>,
    New: TryInto<Old>,
>(P, PhantomData<&'p (OldIndex, Old, New)>)
where
    OldIndex::Output<New>: Mappable<New, Output<Old> = OldIndex>;

impl<
        'p,
        P: PolygonList<'p, Index = OldIndex>,
        OldIndex: Mappable<Old>,
        New: TryInto<Old>,
        Old: TryInto<New>,
    > PolygonList<'p> for IndexWith<'p, P, OldIndex, Old, New>
where
    OldIndex::Output<New>: Mappable<New, Output<Old> = OldIndex>,
{
    type Vertex = P::Vertex;
    type Index = OldIndex::Output<New>;
    type IntoItem = PolygonElement<Self::Index>;
    type Iter<'i> = IndexWithIter<'i, P::Iter<'i>, OldIndex, New, Old>
    where Self: 'i, 'p: 'i;

    fn iter_indices<'i>(&'i self) -> Self::Iter<'i>
    where
        Self: 'i,
        Self::Vertex: 'i,
        'p: 'i,
    {
        unimplemented!()
    }
}

fn foo<
    'p,
    'i,
    P: PolygonList<'p, Index = OldIndex>,
    OldIndex: Mappable<Old>,
    New: TryInto<Old>,
    Old: TryInto<New>,
>(
    x: IndexWith<'p, P, OldIndex, Old, New>,
) where
    IndexWith<'p, P, OldIndex, Old, New>: 'i,
    P::Vertex: 'i,
    'p: 'i,
    OldIndex::Output<New>: Mappable<New, Output<Old> = OldIndex>,
{
    IndexWithIter::new(x.0.iter_indices());
}

pub trait Mappable<T> {
    type Output<U>;
}

impl<T> Mappable<T> for T {
    type Output<U> = U;
}

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-high

Alright, it would be very useful to get a minimization of the underlying pattern here. I think we likely want to accept this breakage 🤔

Depending on the result of the investigation, could #126128 end up in the release notes, correct? (just mentioning so we dont forget to label it as such)

[theemathas]

Minimized from the triangulate crate (I'm unable to make it any smaller):

pub trait Mappable<T> {
    type Output;
}

pub trait Mappable2<T> {
    type Output;
}

// Deleting this impl makes it compile on beta
impl<T> Mappable2<T> for T {
    type Output = i32;
}

pub trait Generic<M> {}

// Deleting the `: Mappable<T>` makes it error on stable.
pub struct IndexWithIter<I, M: Mappable<T>, T>(I, M, T);

// Changing the where clause to be an inline bound (`impl<I: Generic<M>, ....`) causes it to compile on beta
impl<I, M: Mappable<T, Output: Mappable2<T, Output = M>>, T> IndexWithIter<I, M, T>
where
    I: Generic<M>,
{
    fn new(_: I) {}
}

pub fn foo<M: Mappable<T, Output: Mappable2<T, Output = M>>, T>(x: impl Generic<M>) {
    IndexWithIter::new(x);
}

Compiles on stable. Gives the following error on beta:

   Compiling playground v0.0.1 (/playground)
error[E0275]: overflow evaluating the requirement `<M as Mappable<_>>::Output: Mappable2<_>`
  --> src/lib.rs:28:5
   |
28 |     IndexWithIter::new(x);
   |     ^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`playground`)
note: required by a bound in `IndexWithIter::<I, M, T>::new`
  --> src/lib.rs:20:45
   |
20 | impl<I, M: Mappable<T, Output: Mappable2<T, Output = M>>, T> IndexWithIter<I, M, T>
   |                                             ^^^^^^^^^^ required by this bound in `IndexWithIter::<I, M, T>::new`
...
24 |     fn new(_: I) {}
   |        --- required by a bound in this associated function

For more information about this error, try `rustc --explain E0275`.
error: could not compile `playground` (lib) due to 1 previous error

[theemathas]

I am unable to reproduce the issues with poke_search_cli or similari on my computer.