Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

regression: overflow evaluating the requirement #128887

Open
BoxyUwU opened this issue Aug 9, 2024 · 26 comments
Open

regression: overflow evaluating the requirement #128887

BoxyUwU opened this issue Aug 9, 2024 · 26 comments
Labels
E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. P-medium Medium priority regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Milestone

Comments

@BoxyUwU
Copy link
Member

BoxyUwU commented Aug 9, 2024

[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
@BoxyUwU BoxyUwU added T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. regression-from-stable-to-beta Performance or correctness regression from stable to beta. labels Aug 9, 2024
@rustbot rustbot added I-prioritize Issue: Indicates that prioritization has been requested for this issue. needs-triage This issue may need triage. Remove it if it has been sufficiently triaged. labels Aug 9, 2024
@BoxyUwU BoxyUwU removed the needs-triage This issue may need triage. Remove it if it has been sufficiently triaged. label Aug 9, 2024
@compiler-errors
Copy link
Member

This regressed in #126128, cc @lcnr

@lcnr lcnr added the E-needs-mcve Call for participation: This issue has a repro, but needs a Minimal Complete and Verifiable Example label Aug 12, 2024
@lcnr
Copy link
Contributor

lcnr commented Aug 12, 2024

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
Copy link
Contributor

theemathas commented Aug 12, 2024

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
Copy link
Contributor

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)

@rustbot rustbot added P-high High priority and removed I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Aug 12, 2024
@theemathas
Copy link
Contributor

theemathas commented Aug 12, 2024

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
Copy link
Contributor

theemathas commented Aug 12, 2024

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

@lcnr
Copy link
Contributor

lcnr commented Aug 12, 2024

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
Copy link
Contributor

lcnr commented Aug 13, 2024

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
Copy link

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
Copy link
Contributor

theemathas commented Aug 27, 2024

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
Copy link
Member

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
Copy link
Contributor

theemathas commented Aug 27, 2024

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
Copy link

apps4uco commented Aug 27, 2024

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
Copy link
Contributor

@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
Copy link
Contributor

theemathas commented Aug 28, 2024

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
Copy link

@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.

bors added a commit to rust-lang-ci/rust that referenced this issue Aug 29, 2024
…r-errors

Use a reduced recursion limit in the MIR inliner's cycle breaker

This probably papers over rust-lang#128887, but primarily I'm opening this PR because multiple compiler people have thought about making this change which probably means it's a good idea.

r? compiler-errors
github-actions bot pushed a commit to rust-lang/miri that referenced this issue Aug 30, 2024
Use a reduced recursion limit in the MIR inliner's cycle breaker

This probably papers over rust-lang/rust#128887, but primarily I'm opening this PR because multiple compiler people have thought about making this change which probably means it's a good idea.

r? compiler-errors
workingjubilee added a commit to workingjubilee/rustc that referenced this issue Aug 31, 2024
…ler-errors

Add a test for trait solver overflow in MIR inliner cycle detection

This test is a combination of the reproducer posted here: rust-lang#128887 (comment) and the existing test for polymorphic recursion: https://github.com/rust-lang/rust/blob/784d444733d65c3d305ce5edcbb41e3d0d0aee2e/tests/mir-opt/inline/polymorphic_recursion.rs

r? `@compiler-errors`
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Aug 31, 2024
…ler-errors

Add a test for trait solver overflow in MIR inliner cycle detection

This test is a combination of the reproducer posted here: rust-lang#128887 (comment) and the existing test for polymorphic recursion: https://github.com/rust-lang/rust/blob/784d444733d65c3d305ce5edcbb41e3d0d0aee2e/tests/mir-opt/inline/polymorphic_recursion.rs

r? ``@compiler-errors``
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Aug 31, 2024
…ler-errors

Add a test for trait solver overflow in MIR inliner cycle detection

This test is a combination of the reproducer posted here: rust-lang#128887 (comment) and the existing test for polymorphic recursion: https://github.com/rust-lang/rust/blob/784d444733d65c3d305ce5edcbb41e3d0d0aee2e/tests/mir-opt/inline/polymorphic_recursion.rs

r? ```@compiler-errors```
rust-timer added a commit to rust-lang-ci/rust that referenced this issue Aug 31, 2024
Rollup merge of rust-lang#129757 - saethlin:half-a-recursion, r=compiler-errors

Add a test for trait solver overflow in MIR inliner cycle detection

This test is a combination of the reproducer posted here: rust-lang#128887 (comment) and the existing test for polymorphic recursion: https://github.com/rust-lang/rust/blob/784d444733d65c3d305ce5edcbb41e3d0d0aee2e/tests/mir-opt/inline/polymorphic_recursion.rs

r? ```@compiler-errors```
github-actions bot pushed a commit to rust-lang/miri that referenced this issue Sep 1, 2024
Add a test for trait solver overflow in MIR inliner cycle detection

This test is a combination of the reproducer posted here: rust-lang/rust#128887 (comment) and the existing test for polymorphic recursion: https://github.com/rust-lang/rust/blob/784d444733d65c3d305ce5edcbb41e3d0d0aee2e/tests/mir-opt/inline/polymorphic_recursion.rs

r? ```@compiler-errors```
@theemathas
Copy link
Contributor

theemathas commented Sep 3, 2024

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
Copy link
Contributor

lcnr commented Sep 3, 2024

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:

@lcnr
Copy link
Contributor

lcnr commented Sep 3, 2024

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
Copy link
Contributor

lcnr commented Sep 3, 2024

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.

@Mark-Simulacrum Mark-Simulacrum added this to the 1.81.0 milestone Sep 3, 2024
@lcnr
Copy link
Contributor

lcnr commented Sep 3, 2024

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
Copy link
Contributor

apiraino commented Sep 4, 2024

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

(else, LMK if it can be closed)

@wesleywiser
Copy link
Member

#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.

@wesleywiser wesleywiser added E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. and removed E-needs-mcve Call for participation: This issue has a repro, but needs a Minimal Complete and Verifiable Example labels Sep 19, 2024
lnicola pushed a commit to lnicola/rust-analyzer that referenced this issue Sep 25, 2024
Add a test for trait solver overflow in MIR inliner cycle detection

This test is a combination of the reproducer posted here: rust-lang/rust#128887 (comment) and the existing test for polymorphic recursion: https://github.com/rust-lang/rust/blob/784d444733d65c3d305ce5edcbb41e3d0d0aee2e/tests/mir-opt/inline/polymorphic_recursion.rs

r? ```@compiler-errors```
@apiraino
Copy link
Contributor

Downgrading priority to get it off my radar

@rustbot label -P-high +P-medium

@rustbot rustbot added P-medium Medium priority and removed P-high High priority labels Oct 10, 2024
@Mark-Simulacrum Mark-Simulacrum added regression-from-stable-to-stable Performance or correctness regression from one stable version to another. and removed regression-from-stable-to-beta Performance or correctness regression from stable to beta. labels Oct 11, 2024
@kylebarron
Copy link

My crate geoarrow compiled fine for 1.81 but no longer compiles on rust 1.82 because of this issue.

git clone https://github.com/geoarrow/geoarrow-rs
cd geoarrow-rs
git checkout 0b6715c6a56f0115f9078803fae945700713b22f

Compiles fine:

rustup run 1.81 cargo build --release

Fails to compile:

rustup run 1.82 cargo build --release
error[E0275]: overflow evaluating the requirement `<G 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, <<... as GeometryTrait>::GeometryCollection<'_> as GeometryCollectionTrait>::ItemType<'_>, ...>` to implement `Iterator`
   --> src/geo_traits/iterator.rs:39:15
    |
37  |                   ItemType: 'a + $item_trait<T = T>,
    |                                              ----- unsatisfied trait bound introduced here
38  |                   G: $self_trait<T = T, ItemType<'a> = ItemType>,
39  |               > Iterator for $struct_name<'a, T, ItemType, G>
    |                 ^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
109 | / impl_iterator!(
110 | |     GeometryCollectionIterator,
111 | |     GeometryCollectionTrait,
112 | |     GeometryTrait,
113 | |     geometry_unchecked
114 | | );
    | |_- in this macro invocation
    = note: required for `GeometryCollectionIterator<'_, f64, <<... as GeometryTrait>::GeometryCollection<'_> as GeometryCollectionTrait>::ItemType<'_>, ...>` to implement `IntoIterator`
    = note: the full name for the type has been written to '/Users/kyle/github/geoarrow/geoarrow-rs/target/release/deps/geoarrow-d23c01f6fb33c633.long-type-3599692272401749992.txt'
    = note: consider using `--verbose` to print the full type name to the console
    = note: the full name for the type has been written to '/Users/kyle/github/geoarrow/geoarrow-rs/target/release/deps/geoarrow-d23c01f6fb33c633.long-type-3599692272401749992.txt'
    = note: consider using `--verbose` to print the full type name to the console
    = note: this error originates in the macro `impl_iterator` (in Nightly builds, run with -Z macro-backtrace for more info)

For more information about this error, try `rustc --explain E0275`.
warning: `geoarrow` (lib) generated 3 warnings
error: could not compile `geoarrow` (lib) due to 1 previous error; 3 warnings emitted

FWIW it does compile with

RUSTFLAGS='-Zinline-mir=no' rustup run nightly cargo build --release

@theemathas
Copy link
Contributor

I've split the latest geoarrow regression to a separate issue in #131960, to reduce confusion.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. P-medium Medium priority regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests