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.

[lcnr]

slightly more readable for me 🤔

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, T> IndexWithIter<I, M, T>
where
    M: Mappable<T>,
    M::Output: Mappable2<T, Output = M>,
    I: Generic<M>,
{
    fn new(x: I) {
        IndexWithIter::<_, _, _>::new(x);
    }
}

this is somehow caused by the order in which we evaluate nested goals and also subtyping, but I don't fully understand why this is happening yet.

[lcnr]

yeah, I am also unable to reproduce the overflow in poke_search and similari, so they may be spurious due to order dependence in the old trait solver wrt to overflow depth

[apps4uco]

I have encountered an issue that may be related to this issue, report filed at: geoarrow/geoarrow-rs#716

The compile error that only occurs with nightly + release build, the code compiles for nightly + debug builds, and stable + release.

the error message starts

Compiling geoarrow v0.2.0
error[E0275]: overflow evaluating the requirement `<impl GeometryTrait<T = f64> as geo_traits::geometry::GeometryTrait>::GeometryCollection<'_>: geo_traits::geometry_collection::GeometryCollectionTrait`
    |
    = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`geoarrow`)
note: required for `GeometryCollectionIterator<'_, f64, ..., ...>` to implement `Iterator`
   --> /Users/andy/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geoarrow-0.2.0/src/geo_traits/iterator.rs:38:15
    |

Full message and attached file in the linked issue

[theemathas]

Outdated comment

Somewhat minimized test case from geoarrow-rs (very bizarre):

Command to reproduce (yes, you need to build it in release mode)

cargo +nightly build --release

Cargo.toml

[package]
name = "geoarrow" # Renaming this package *sometimes* causes the code to compile
edition = "2021"

src/lib.rs

// Deleting this trait makes the code compile.
pub trait Irrelevant {}

pub struct GeometryCollection {}
pub trait GeometryCollectionTrait: Sized {
    type T;
    type ItemType: GeometryTrait<T = Self::T>;

    fn geometries(&self) -> GeometryCollectionIterator<Self::T, Self::ItemType, Self> {
        unimplemented!()
    }
}
impl GeometryCollectionTrait for GeometryCollection {
    type T = f64;
    type ItemType = Geometry;
}
pub enum Geometry {}
pub trait GeometryTrait {
    type T;
    type GeometryCollection: GeometryCollectionTrait<T = Self::T>;

    fn as_type(&self) -> Self::GeometryCollection {
        unimplemented!()
    }
}
impl<'a> GeometryTrait for Geometry {
    type T = f64;
    type GeometryCollection = GeometryCollection;
}
impl<'a> GeometryTrait for &'a Geometry {
    type T = f64;
    type GeometryCollection = GeometryCollection;
}

pub struct GeometryCollectionIterator<
    T,
    ItemType: GeometryTrait<T = T>,
    G: GeometryCollectionTrait<T = T, ItemType = ItemType>,
> {
    _geom: G,
}
impl<T, ItemType: GeometryTrait<T = T>, G: GeometryCollectionTrait<T = T, ItemType = ItemType>>
    Iterator for GeometryCollectionIterator<T, ItemType, G>
{
    type Item = ItemType;
    fn next(&mut self) -> Option<Self::Item> {
        unimplemented!()
    }
}

fn geometry_eq<T>(left: &impl GeometryTrait<T = T>, right: &impl GeometryTrait<T = T>) {
    let l = left.as_type();
    let r = right.as_type();
    geometry_collection_eq(&l, &r);
}

fn geometry_collection_eq<T>(
    left: &impl GeometryCollectionTrait<T = T>,
    right: &impl GeometryCollectionTrait<T = T>,
) {
    let left_geometry = left.geometries().next().unwrap();
    let right_geometry = right.geometries().next().unwrap();
    geometry_eq(&left_geometry, &right_geometry);
}

impl Geometry {
    // Renaming this function *sometimes* makes the code compile.
    pub fn eq<G: GeometryTrait<T = f64>>(&self, other: &G) {
        geometry_eq(self, other);
    }
}

Output of `rustc +nightly --version --verbose`

rustc 1.82.0-nightly (515395af0 2024-08-26)
binary: rustc
commit-hash: 515395af0efdbdd657ff08a1f6d28e553856654f
commit-date: 2024-08-26
host: aarch64-apple-darwin
release: 1.82.0-nightly
LLVM version: 19.1.0

[Noratrieb]

Without actually verifying it, I suspect that this is due to MIR inlining causing instantiations that overflow. MIR inlining depends on the crate hash/defpath hash, so is affected by changes to the crate name.
To verify this, you can try using -Zinline-mir=no.

[theemathas]

Outdated comment

Slightly minimized further than before. Same Cargo.toml.

src/lib.rs

pub trait Irrelevant {}
pub struct IrrelevantFoo;
impl Foo for IrrelevantFoo {
    type T = f64;
    type BarType = IrrelevantBar;
}
pub struct IrrelevantBar;
impl<'a> Bar for IrrelevantBar {
    type T = f64;
    type FooType = IrrelevantFoo;
}
impl<'a> Bar for &'a IrrelevantBar {
    type T = f64;
    type FooType = IrrelevantFoo;
}
// Deleting the stuff above makes the code compile.

pub trait Foo {
    type T;
    type BarType: Bar<T = Self::T>;
}
pub trait Bar {
    type T;
    type FooType: Foo<T = Self::T>;
}

pub struct BarProducer<T, ItemType: Bar<T = T>> {
    _dummy: ItemType,
}
trait Producer {
    type Item;
    fn produce(&mut self) -> Self::Item {
        unimplemented!()
    }
}
impl<T, ItemType: Bar<T = T>> Producer for BarProducer<T, ItemType> {
    type Item = ItemType;
}

#[allow(unconditional_recursion)]
fn recurse<T, G: Bar<T = T>>() {
    let mut producer: BarProducer<T, <G::FooType as Foo>::BarType> = conjure();
    producer.produce();
    recurse::<_, <G::FooType as Foo>::BarType>();
}

fn conjure<T>() -> T {
    unimplemented!()
}

pub struct Something;
impl Something {
    // Renaming this function *sometimes* makes the code compile.
    pub fn eq<G: Bar<T = f64>>() {
        recurse::<_, G>();
    }
}

[apps4uco]

Without actually verifying it, I suspect that this is due to MIR inlining causing instantiations that overflow. MIR inlining depends on the crate hash/defpath hash, so is affected by changes to the crate name. To verify this, you can try using -Zinline-mir=no.

Hi, thanks for looking into this.

I tried your suggestion on the original crate, (actually the commit 46554582089404faca5da8dfdde6f871cb1378e2 from the geoarrow repo) as well as geoarrow v0.2.0

RUSTFLAGS="-Zinline-mir" cargo build --release

However the same error occurs

Compiling geoarrow v0.2.0 .... OR ....   Compiling geoarrow v0.3.0-beta.2 (/opt/git/geoarrow-rs)

error[E0275]: overflow evaluating the requirement `impl GeometryCollectionTrait<T = f64>: geo_traits::geometry_collection::GeometryCollectionTrait`

rustc +nightly --version --verbose
rustc 1.82.0-nightly (4074d49 2024-08-23)
binary: rustc
commit-hash: 4074d49
commit-date: 2024-08-23
host: aarch64-apple-darwin
release: 1.82.0-nightly
LLVM version: 19.1.0

[theemathas]

@apps4uco Your build command is incorrect.

I can confirm that, on commit 2089a0189a16a8959605791fbbc2cc48113f1ccf (tag rust-v0.2.0), and also on my minimized test case, compiling with the following command compiles fine without an error:

RUSTFLAGS='-Zinline-mir=no' cargo +nightly build --release

While the following command produces an error:

cargo +nightly build --release

[theemathas]

This version of the issue (minimized from geoarrow-rs) has now been fixed in #129714.

Final minimized reproduction from the geoarrow-rs case.

Commands that produce errors

cargo +beta build --release
cargo +nightly build --release

Commands that run successfully without errors:

cargo +beta build 
cargo +nightly build
RUSTFLAGS='-Zinline-mir=no' cargo +nightly build --release

Cargo.toml

[package]
name = "b"       # Renaming this package *sometimes* causes the code to compile
edition = "2021"

src/lib.rs

pub trait Foo {
    type Associated;
    type Chain: Foo<Associated = Self::Associated>;
}

trait FooExt {
    fn do_ext() {}
}
impl<T: Foo<Associated = f64>> FooExt for T {}

#[allow(unconditional_recursion)]
fn recurse<T: Foo<Associated = f64>>() {
    T::do_ext();
    recurse::<T::Chain>();
}

// Renaming this function *sometimes* makes the code compile.
pub fn lol<T: Foo<Associated = f64>>() {
    recurse::<T>();
}

Output of `rustc +nightly --version --verbose`

rustc 1.82.0-nightly (515395af0 2024-08-26)
binary: rustc
commit-hash: 515395af0efdbdd657ff08a1f6d28e553856654f
commit-date: 2024-08-26
host: aarch64-apple-darwin
release: 1.82.0-nightly
LLVM version: 19.1.0

This seems... bad

[apps4uco]

@apps4uco Your build command is incorrect.

I should have stated that the global configuration I have is

$ rustup default
nightly-aarch64-apple-darwin (default)

So it should be the same command as you had, or am I missing something?

It seems like a very weird edge case that we have hit.

What produced an error for me yesterday compiles fine today with the same command. Could that be related to the order cargo is compiling the crates?

Thanks once again for looking into this.

[theemathas]

Current status: The issue from geoarrow-rs has been fixed in #129714. The issue from the triangulate crate is still unfixed, and might end up in stable rust version 1.81.0.

Maybe this should go on the release notes?

[lcnr]

thinking through this:

The change in #126128 changes the equate of the self type IndexWithIter::<?0, ?1, ?2> with the instantiated impl self type IndexWithIter<?I, ?M, ?T> to subtyping.

Where this previously equated the inference variables, resulting in ?0 = ?I, ?1 = ?M and ?2 = ?T, this now emits Subtype obligations which get processed in the main fulfillment loop. This means that constraining ?0-2 doesn't immediately constrain ?I, ?M, or ?T.

Trying to prove <M as Mappable<?T>>::Output: Mappable2<?T, Output = M>, overflows, while proving <M as Mappable<T>>::Output: Mappable2<T, Output = M> with T inferred does not. For why it overflows, see #128887 (comment)

We first constrain ?0 to I, then prove subtype obligations, and then prove the where-bounds on the self-type IndexWithIter. This means we prove M: Mappable<?2>. This constrains ?2 to T, but with #126128 does not constrain ?T to T as well.

We then first prove the projection predicate which overflows and then the M: Mappable<T> predicate. We always move projection predicates before trait predicates, so adding a projection predicate to M: Mappable<T> fixes the overflow (depending on the order of where-clauses) by first proving this one:

• wrong order -> overflow: https://rust.godbolt.org/z/3cGnET81e
• right order -> no overflow: https://rust.godbolt.org/z/ax1EGxE7n

[lcnr]

this regression therefore doesn't need an associated type bound on Mappable2: https://play.rust-lang.org/?version=beta&mode=debug&edition=2021&gist=13e05a9fbba710cc556bd6366b292846

[lcnr]

so what's going on here is the following change from the old behavior:

• constrain ?Mimpl and ?Mtype via I: Generic<?Mimpl>
• prove M: Mappable<?Ttype> which constrains ?Timpl and ?Ttype
• prove <M as Mappable<T>>::Output: Bound<T>

to the new behavior

• constrain ?Mimpl via I: Generic<?Mimpl>
• prove the subtype ?Mimpl ?Mtype which also constrains ?Mtype
• prove M: Mappable<?Ttype> which constrains ?Ttype, but not ?Timpl
• we do not reprove the subtype obligations here
• prove <M as Mappable<?Timpl>>::Output: Bound<?Timpl> which overflows

so, assuming that the fact that <M as Mappable<?t>>::Output: Bound<?t> should overflow, this change seems like an unfortunate, but acceptable inference breakage.

[lcnr]

The reason that <M as Mappable<?t>>::Output: Bound<?t> overflows is due to the generalizer emitting Projection obligations in case there's an occurs check failure inside of an alias.

using #128887 (comment)

trait Mappable<T> {
    type Output;
}

pub trait Bound<T> {}
// Deleting this impl makes it compile on beta
impl<T> Bound<T> for T {}

trait Generic<M> {}

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

impl<I, M, T> IndexWithIter<I, M, T>
where
    <M as Mappable<T>>::Output: Bound<T>,
    // flipping these where bounds causes this to succeed, even when removing
    // the where-clause on the struct definition.
    M: Mappable<T>,
    I: Generic<M>,
{
    fn new(x: I) {
        IndexWithIter::<_, _, _>::new(x);
    }
}

• trying to prove <M as Mappable<?t>>::Output: Bound<?t> via the impl equates <M as Mappable<?t>>::Output and ?t
• instantiating ?t fails the occurs check and emits a Projection(<M as Mappable<?t>>::Output, ?t) goal. As <M as Mappable<?t>>::Output is a rigid projection, we equate it with ?t yet again, causing overflow.

We could in theory fix this by reverting occurs check failures back to a hard error in case the projection does not reference bound variables or placeholders (as we should have eagerly replaced all such projections with inference variables), however, this feels subtle and not worth it imo.

With this, I think we should not do anything here. I expect that #129073 will fix this again. THe underlying issue of fatal overflow introducing order dependence still persists however. cc @compiler-errors please test the minimization

[apiraino]

OK, I assume them we want to keep this issue open until merge of #129073

(else, LMK if it can be closed)

[wesleywiser]

#129073 has merged and seems to fix the reproducer @lcnr left here. I believe we just need that added as a regression test and then this can be closed.