Skip to content

regression: cycle detected when computing whether impls specialize one another #125197

New issue

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

#

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

Already on GitHub? # to your account

Jump to bottom
Closed
BoxyUwU opened this issue May 17, 2024 · 8 comments
Closed

regression: cycle detected when computing whether impls specialize one another #125197

BoxyUwU opened this issue May 17, 2024 · 8 comments
Assignees
@compiler-errors
Labels
A-specialization Area: Trait impl specialization F-specialization `#![feature(specialization)]` regression-from-stable-to-beta Performance or correctness regression from stable to beta. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Milestone
1.79.0

Comments

@BoxyUwU
Copy link
Member

BoxyUwU commented May 17, 2024 

[INFO] [stdout] error[E0391]: cycle detected when computing whether impls specialize one another
[INFO] [stdout]   --> /opt/rustwide/workdir/src/lib.rs:54:1
[INFO] [stdout]    |
[INFO] [stdout] 54 | impl<T: Identifier> PartialEq<T> for AnyId {
[INFO] [stdout]    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[INFO] [stdout]    |
@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 May 17, 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 May 17, 2024
@BoxyUwU BoxyUwU mentioned this issue May 17, 2024
Closed
@BoxyUwU BoxyUwU added this to the 1.79.0 milestone May 17, 2024
@compiler-errors
Copy link
Member

Bisecting this...

@compiler-errors
Copy link
Member

This bisected in #122791. This crate is using specialization, which we don't stably support.

This has some interactions with specialization, and so breaks a few UI tests that I don't agree should've ever worked in the first place, and also breaks a handful of crates in a way that I don't believe is a problem.

@compiler-errors compiler-errors added P-low Low priority and removed I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels May 17, 2024
@Noratrieb Noratrieb added A-specialization Area: Trait impl specialization F-specialization `#![feature(specialization)]` and removed needs-triage This issue may need triage. Remove it if it has been sufficiently triaged. labels May 17, 2024
@Mark-Simulacrum
Copy link
Member

@compiler-errors How is that not feature gated? I don't see feature gates in the repos above and presumably it built on stable in order to regress here?

@compiler-errors
Copy link
Member

compiler-errors commented Jun 7, 2024 •
edited
Loading

I am mistaken then, @Mark-Simulacrum. I thought I looked at these crates, but perhaps I was looking at the wrong one.

@compiler-errors
Copy link
Member

I'll look back into this...

@compiler-errors compiler-errors self-assigned this Jun 7, 2024
@compiler-errors compiler-errors mentioned this issue Jun 7, 2024
Merged
@compiler-errors
Copy link
Member

Opened a PR for this and nominated for beta.

bors added a commit to rust-lang-ci/rust that referenced this issue Jun 7, 2024
@bors
Auto merge of rust-lang#126139 - compiler-errors:specializes, r=<try>
20182a9 
Only compute `specializes` query if (min)specialization is enabled in the crate of the specializing impl

Fixes (after backport) rust-lang#125197

### What

rust-lang#122791 makes it so that inductive cycles are no longer hard errors. That means that when we are testing, for example, whether these impls overlap:

```rust
impl PartialEq<Self> for AnyId {
    fn eq(&self, _: &Self) -> bool {
        todo!()
    }
}

impl<T: Identifier> PartialEq<T> for AnyId {
    fn eq(&self, _: &T) -> bool {
        todo!()
    }
}
```

...given...

```rust
pub trait Identifier: Display + 'static {}

impl<T> Identifier for T where T: PartialEq + Display + 'static {}
```

Then we try to see if the second impl holds given `T = AnyId`. That requires `AnyId: Identifier`, which requires that `AnyId: PartialEq`, which is satisfied by these two impl candidates... The `PartialEq<T>` impl is a cycle, and we used to winnow it when we used to treat inductive cycles as errors.

However, now that we don't winnow it, this means that we *now* try calling `candidate_should_be_dropped_in_favor_of`, which tries to check whether one of the impls specializes the other: the `specializes` query. In that query, we currently bail early if the impl is local:

However, in a foreign crate, we try to compute if the two impls specialize each other by doing trait solving. This may itself lead to the same situation where we call `specializes`, which will lead to a query cycle.

### How does this fix the problem

We now record whether specialization is enabled in foreign crates, and extend this early-return behavior to foreign impls too. This means that we can only encounter these cycles if we truly have a specializing impl from a crate with specialization enabled.

-----

r? `@oli-obk` or `@lcnr`
@compiler-errors compiler-errors added I-prioritize Issue: Indicates that prioritization has been requested for this issue. and removed P-low Low priority labels Jun 7, 2024
bors added a commit to rust-lang-ci/rust that referenced this issue Jun 11, 2024
@bors
Auto merge of rust-lang#126139 - compiler-errors:specializes, r=lcnr
336e6ab 
Only compute `specializes` query if (min)specialization is enabled in the crate of the specializing impl

Fixes (after backport) rust-lang#125197

### What

rust-lang#122791 makes it so that inductive cycles are no longer hard errors. That means that when we are testing, for example, whether these impls overlap:

```rust
impl PartialEq<Self> for AnyId {
    fn eq(&self, _: &Self) -> bool {
        todo!()
    }
}

impl<T: Identifier> PartialEq<T> for AnyId {
    fn eq(&self, _: &T) -> bool {
        todo!()
    }
}
```

...given...

```rust
pub trait Identifier: Display + 'static {}

impl<T> Identifier for T where T: PartialEq + Display + 'static {}
```

Then we try to see if the second impl holds given `T = AnyId`. That requires `AnyId: Identifier`, which requires that `AnyId: PartialEq`, which is satisfied by these two impl candidates... The `PartialEq<T>` impl is a cycle, and we used to winnow it when we used to treat inductive cycles as errors.

However, now that we don't winnow it, this means that we *now* try calling `candidate_should_be_dropped_in_favor_of`, which tries to check whether one of the impls specializes the other: the `specializes` query. In that query, we currently bail early if the impl is local.

However, in a foreign crate, we try to compute if the two impls specialize each other by doing trait solving. This may itself lead to the same situation where we call `specializes`, which will lead to a query cycle.

### How does this fix the problem

We now record whether specialization is enabled in foreign crates, and extend this early-return behavior to foreign impls too. This means that we can only encounter these cycles if we truly have a specializing impl from a crate with specialization enabled.

-----

r? `@oli-obk` or `@lcnr`
@apiraino apiraino removed the I-prioritize Issue: Indicates that prioritization has been requested for this issue. label Jun 11, 2024
github-actions bot pushed a commit to rust-lang/miri that referenced this issue Jun 13, 2024
@bors
Auto merge of #126139 - compiler-errors:specializes, r=lcnr
5cc316c 
Only compute `specializes` query if (min)specialization is enabled in the crate of the specializing impl

Fixes (after backport) rust-lang/rust#125197

### What

rust-lang/rust#122791 makes it so that inductive cycles are no longer hard errors. That means that when we are testing, for example, whether these impls overlap:

```rust
impl PartialEq<Self> for AnyId {
    fn eq(&self, _: &Self) -> bool {
        todo!()
    }
}

impl<T: Identifier> PartialEq<T> for AnyId {
    fn eq(&self, _: &T) -> bool {
        todo!()
    }
}
```

...given...

```rust
pub trait Identifier: Display + 'static {}

impl<T> Identifier for T where T: PartialEq + Display + 'static {}
```

Then we try to see if the second impl holds given `T = AnyId`. That requires `AnyId: Identifier`, which requires that `AnyId: PartialEq`, which is satisfied by these two impl candidates... The `PartialEq<T>` impl is a cycle, and we used to winnow it when we used to treat inductive cycles as errors.

However, now that we don't winnow it, this means that we *now* try calling `candidate_should_be_dropped_in_favor_of`, which tries to check whether one of the impls specializes the other: the `specializes` query. In that query, we currently bail early if the impl is local.

However, in a foreign crate, we try to compute if the two impls specialize each other by doing trait solving. This may itself lead to the same situation where we call `specializes`, which will lead to a query cycle.

### How does this fix the problem

We now record whether specialization is enabled in foreign crates, and extend this early-return behavior to foreign impls too. This means that we can only encounter these cycles if we truly have a specializing impl from a crate with specialization enabled.

-----

r? `@oli-obk` or `@lcnr`
flip1995 pushed a commit to flip1995/rust-clippy that referenced this issue Jun 28, 2024
@bors
Auto merge of #126139 - compiler-errors:specializes, r=lcnr
5d295a2 
Only compute `specializes` query if (min)specialization is enabled in the crate of the specializing impl

Fixes (after backport) rust-lang/rust#125197

### What

rust-lang/rust#122791 makes it so that inductive cycles are no longer hard errors. That means that when we are testing, for example, whether these impls overlap:

```rust
impl PartialEq<Self> for AnyId {
    fn eq(&self, _: &Self) -> bool {
        todo!()
    }
}

impl<T: Identifier> PartialEq<T> for AnyId {
    fn eq(&self, _: &T) -> bool {
        todo!()
    }
}
```

...given...

```rust
pub trait Identifier: Display + 'static {}

impl<T> Identifier for T where T: PartialEq + Display + 'static {}
```

Then we try to see if the second impl holds given `T = AnyId`. That requires `AnyId: Identifier`, which requires that `AnyId: PartialEq`, which is satisfied by these two impl candidates... The `PartialEq<T>` impl is a cycle, and we used to winnow it when we used to treat inductive cycles as errors.

However, now that we don't winnow it, this means that we *now* try calling `candidate_should_be_dropped_in_favor_of`, which tries to check whether one of the impls specializes the other: the `specializes` query. In that query, we currently bail early if the impl is local.

However, in a foreign crate, we try to compute if the two impls specialize each other by doing trait solving. This may itself lead to the same situation where we call `specializes`, which will lead to a query cycle.

### How does this fix the problem

We now record whether specialization is enabled in foreign crates, and extend this early-return behavior to foreign impls too. This means that we can only encounter these cycles if we truly have a specializing impl from a crate with specialization enabled.

-----

r? `@oli-obk` or `@lcnr`
@apiraino
Copy link
Contributor

apiraino commented Aug 5, 2024

#126772 was merged, so can this be closed as fixed? cc @BoxyUwU

@compiler-errors
Copy link
Member

ya this was fixed

# for free to join this conversation on GitHub. Already have an account? # to comment
Assignees

@compiler-errors compiler-errors

Labels
A-specialization Area: Trait impl specialization F-specialization `#![feature(specialization)]` regression-from-stable-to-beta Performance or correctness regression from stable to beta. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Milestone
1.79.0
Development

No branches or pull requests
6 participants
@compiler-errors @Mark-Simulacrum @apiraino @BoxyUwU @rustbot @Noratrieb