(Anti-)regression between Rust 1.78.0 and Rust 1.79.0 with struct containing `Cow<[Self]>`

zachs18 commented 2 months ago

Code

I tried this code:

#![allow(unused)]
#[derive(Clone)] // nothing substantial changes if this is replaced with a manual impl Clone for Test
struct Hello {
    a: std::borrow::Cow<'static, [Self]>,
}
fn main(){}

I expected to see this happen: On 1.78 and below, this fails to compile with several E0277s (trait bound not satisfied)

full error message

```Rust error[E0277]: the trait bound `[Hello]: ToOwned` is not satisfied in `Hello` --> src/main.rs:4:32 | 4 | a: std::borrow::Cow<'static, [Self]>, | ^^^^^^ within `Hello`, the trait `ToOwned` is not implemented for `[Hello]`, which is required by `Hello: Sized` | = help: the trait `ToOwned` is implemented for `[T]` note: required because it appears within the type `Hello` --> src/main.rs:3:8 | 3 | struct Hello { | ^^^^^ = note: slice and array elements must have `Sized` type error[E0277]: the trait bound `[Hello]: ToOwned` is not satisfied in `Hello` --> src/main.rs:2:10 | 2 | #[derive(Clone)] | ^^^^^ within `Hello`, the trait `ToOwned` is not implemented for `[Hello]`, which is required by `Hello: Sized` | = help: the trait `ToOwned` is implemented for `[T]` note: required because it appears within the type `Hello` --> src/main.rs:3:8 | 3 | struct Hello { | ^^^^^ note: required by a bound in `Clone` --> /rustc/9b00956e56009bab2aa15d7bff10916599e3d6d6/library/core/src/clone.rs:147:1 = note: this error originates in the derive macro `Clone` (in Nightly builds, run with -Z macro-backtrace for more info) error[E0277]: the trait bound `[Hello]: ToOwned` is not satisfied in `Hello` --> src/main.rs:2:10 | 2 | #[derive(Clone)] | ^^^^^ within `Hello`, the trait `ToOwned` is not implemented for `[Hello]`, which is required by `Hello: Sized` | = help: the trait `ToOwned` is implemented for `[T]` note: required because it appears within the type `Hello` --> src/main.rs:3:8 | 3 | struct Hello { | ^^^^^ = note: the return type of a function must have a statically known size = note: this error originates in the derive macro `Clone` (in Nightly builds, run with -Z macro-backtrace for more info) error[E0277]: the trait bound `[Hello]: ToOwned` is not satisfied in `Cow<'_, [Hello]>` --> src/main.rs:4:3 | 2 | #[derive(Clone)] | ----- in this derive macro expansion 3 | struct Hello { 4 | a: std::borrow::Cow<'static, [Self]>, | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ within `Cow<'_, [Hello]>`, the trait `ToOwned` is not implemented for `[Hello]`, which is required by `Cow<'_, [Hello]>: Sized` | = help: the trait `ToOwned` is implemented for `[T]` note: required because it appears within the type `Cow<'_, [Hello]>` --> /rustc/9b00956e56009bab2aa15d7bff10916599e3d6d6/library/alloc/src/borrow.rs:180:10 note: required by a bound in `clone` --> /rustc/9b00956e56009bab2aa15d7bff10916599e3d6d6/library/core/src/clone.rs:160:5 = note: this error originates in the derive macro `Clone` (in Nightly builds, run with -Z macro-backtrace for more info) For more information about this error, try `rustc --explain E0277`. error: could not compile `bisectee` (bin "bisectee") due to 4 previous errors ```

Instead, this happened: On Rust 1.79 and above, it compiles without error

Version it didn't work on

It most recently didn't work on: Rust 1.78.0

Version with anti-regression

rustc --version --verbose:

rustc 1.79.0 (129f3b996 2024-06-10)
binary: rustc
commit-hash: 129f3b9964af4d4a709d1383930ade12dfe7c081
commit-date: 2024-06-10
host: x86_64-unknown-linux-gnu
release: 1.79.0
LLVM version: 18.1.7

Bisection:

searched nightlies: from nightly-2024-03-16 to nightly-2024-04-28 regressed nightly: nightly-2024-03-20 searched commit range: https://github.com/rust-lang/rust/compare/3c85e56249b0b1942339a6a989a971bf6f1c9e0f...a7e4de13c1785819f4d61da41f6704ed69d5f203 regressed commit: https://github.com/rust-lang/rust/commit/196ff446d20088406b9d69978dddccc4682bd006

bisected with cargo-bisect-rustc v0.6.9

Host triple: x86_64-unknown-linux-gnu Reproduce with: ```bash cargo bisect-rustc --start=1.78.0 --end=1.79.0 --regress success --preserve ```

cc @lukas-code The description of https://github.com/rust-lang/rust/pull/122493 says "This should not make more or less code compile, but it can change error output in some rare cases."

Probably nothing to do but add a test to make sure this keeps compiling in the future?

theemathas commented 2 months ago

The code you show has Self but the error has [Self]. Is this intentional?

workingjubilee commented 2 months ago

Fixed. The gression did indeed happen for [Self]:

https://rust.godbolt.org/z/4TY7a54Ps

compiler-errors commented 2 months ago

So I expect this code to compile, especially given that Cow<'_, [T]> is Sized, so this struct is coinductively Sized. There's a slight "risk" w/ this code compiling wrt the way we handle coinduction the solver, but I'll leave that to @lcnr to judge.

It would be interesting to know what specifically about #122493 caused this to compile, though I haven't looked at all about it.

WaffleLapkin commented 2 months ago

I think this is more about Clone rather than Sized-ness by itself. (for Sized there is an example which compiled since forever, Cow<[T]> doesn't require coinduction to be Sized -- it contains a &[T] (trivially sized) and <[T] as ToOwned>::Owned (which has an implicit : Sized bound)).

What I think happened is that #[derive(Clone)] expansion requires Cow<'static, [Self]>: Clone which requires Cow<'static, [Self]>: Sized which, before https://github.com/rust-lang/rust/pull/122493, required wf(Cow<'static, [Self]>) which requires [Self]: ToOwned which requires Self: Clone which requires Cow<'static, [Self]>: Clone making a cycle.

I think some details in my explanation are wrong (particularly the last step?), because I'm not familiar enough with type checking in rustc; but. I do think that "not requiring wf(Enum) when evaluating Enum: Sized" makes it so we don't evaluate bounds which lead to a cycle.

lukas-code commented 2 months ago

This was properly fixed in https://github.com/rust-lang/rust/pull/122791, which also landed in 1.78.0.

That PR also allows this similar code to compile, which still fails after https://github.com/rust-lang/rust/pull/122493:

#[derive(Clone)]
struct Hello {
    a: <[Hello] as ToOwned>::Owned,
}

This happens, because normalizing <Hello as ToOwned>::Owned in this example involves a cycle during candidate selection, which is no longer an error after https://github.com/rust-lang/rust/pull/122791:

normalize <[Hello] as ToOwned>::Owned
    candidate #1: impl ToOwned for T where T: Sized [+ Clone]
        requires [Hello]: Sized
        -> error (unimplemented)
    candidate #2: impl ToOwned for [T] where T: Sized [+ Clone]
        requires Hello: Sized
            requires <[Hello] as ToOwned>::Owned: Sized
                normalize <[Hello] as ToOwned>::Owned
        -> ambiguous (cycle)
    -> candidate #2 is ambiguous, but it is the only applicable candidate
-> normalized to Vec<Hello> via candidate #2

The Code in the OP compiles with just https://github.com/rust-lang/rust/pull/122493, because that PR changed Cow<T>: Sized to always hold and not require checking <T as ToOwned>::Owned: Sized and therefore avoid the cycle.

marmeladema commented 2 months ago

I think this has solved https://github.com/rust-lang/rust/issues/100347

apiraino commented 2 months ago

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-medium

mbartlett21 commented 2 months ago

Issues resolved include #23714, #47032, #89940, #100347 and #107481.

lcnr commented 2 months ago

https://github.com/rust-lang/rust/issues/129541#issuecomment-2308823537 this uncovers a case where we forget ambiguity. Even if we're able to use an ambiguous candidate to normalize, this should force the goal to be ambiguous. This currently fails with the new solver and should do so until we've changed our cycle handling.

https://rust.godbolt.org/z/sYGY15Gv5

I don't fully understand why this happens and whether this hides a more serious issue. I want to look more deeply into the code once I am back home next week. Thanks @zachs18 for opening this issue and thanks @lukas-code for looking into this.

workingjubilee commented 2 months ago

I was actually hoping for unsized unions to remain possible, honestly, so I'm somewhat disappointed by this event being caused by #122493, since that makes it impossible to even explore adding such support without it then being a regression.

lukas-code commented 2 months ago

I was actually hoping for unsized unions to remain possible, honestly, so I'm somewhat disappointed by this event being caused by #122493, since that makes it impossible to even explore adding such support without it then being a regression.

Before #122493, unions would only be unsized if the last field was unsized, e.g.

// This was unsized before.
union Foo {
    a: (),
    b: [u8],
}

// This was always sized.
union Bar {
    a: [u8],
    b: (),
}

That's probably not the semantics that we want for unsized unions and the same can already be achieved with a sized union and a struct. So it seemed fine to me to remove this weird special case.

I'm actually more concerned about the future of unsized enums now, because I thought we could just revert the relevant changes if they ever become a thing, but this issue shows that that's evidently not the case.

workingjubilee commented 2 months ago

I agree that that rule for unions seems like the wrong semantics! To be clear, I was hoping for something like this becoming possible:

#[repr(C)]
union Varlena {
    pack: (u8, [u8]),
    full: (u32, [u8]),
}

Which would be quite useful for binding against C code with various kinds of "we have enums at home" solutions.

lcnr commented 2 months ago

#129541 (comment) this uncovers a case where we forget ambiguity. Even if we're able to use an ambiguous candidate to normalize, this should force the goal to be ambiguous. This currently fails with the new solver and should do so until we've changed our cycle handling.

https://rust.godbolt.org/z/sYGY15Gv5

I don't fully understand why this happens and whether this hides a more serious issue. I want to look more deeply into the code once I am back home next week. Thanks @zachs18 for opening this issue and thanks @lukas-code for looking into this.

ah, this is #106040 :sweat_smile: that's good as this issue is already known and something we'll have to handle regardless.

lcnr commented 2 months ago

Okay, so this issue contains 2 unintended changes:

122493: for an enum Hello, when checking Hello: Sized we no-longer check whether the last field of each variant is Sized . This caused an error if normalizing the last field ends up recursively requiring Hello: Sized. We now only check that the last field is Sized in the item wfcheck, avoiding this cycle. When using the new solver, this currently causes a query cycle when computing the layout of <[Hello] as Normalize>::Assoc but this feels like a bug in the new solver, opened https://github.com/rust-lang/trait-system-refactor-initiative/issues/123: https://rust.godbolt.org/z/cz4ce7j84.
https://github.com/rust-lang/rust/pull/122791: we treat inductive cycles as ambiguity instead of a hard error. This means that cycles while eagerly normalizing change from an error to succeeding while returning Hello: Sized. Due to another existing issue #106040, evaluation/fulfillment then doesn't treat the normalization as part of the cycle, causing the cycle is to be treated as coinductive. As candidate selection only evaluates nested goals if there are multiple candidates, explicit normalization already succeeded if there was only a single normalization candidate.
- changed behavior: https://rust.godbolt.org/z/eqqoMqxxa
- single candidate, no change: https://rust.godbolt.org/z/GMGKzYPEx

I think these changes in behavior are acceptable and desirable. They will be automatically supported once we've implemented the new cycle semantics. I believe we were already forced to handle #106040 in the new solver even before https://github.com/rust-lang/rust/pull/122791 made it easier to exploit.

I propose that we accept this accidental stabilization (given that it's already stable since for 2 versions) and close this issue after adding regression tests.

rfcbot commented 2 months ago

Team member @lcnr has proposed to close this. The next step is review by the rest of the tagged team members:

[ ] @BoxyUwU
[ ] @compiler-errors
[ ] @jackh726
[x] @lcnr
[ ] @nikomatsakis
[ ] @oli-obk
[ ] @spastorino

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

lcnr commented 2 months ago

@rfcbot fcp cancel

rfcbot commented 2 months ago

@lcnr proposal cancelled.

lcnr commented 2 months ago

see https://github.com/rust-lang/rust/issues/129541#issuecomment-2325789416

@rfcbot fcp merge

rfcbot commented 2 months ago

Team member @lcnr has proposed to merge this. The next step is review by the rest of the tagged team members:

[ ] @BoxyUwU
[x] @compiler-errors
[x] @jackh726
[x] @lcnr
[ ] @nikomatsakis
[x] @oli-obk
[x] @spastorino

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

workingjubilee commented 2 months ago

We now only check that the last field is Sized in the item wfcheck, avoiding this cycle.

Ah, so this doesn't actually make it so the Sizedness of the type isn't checked for, it only dodges a cycle? Cool.

rfcbot commented 1 month ago

:bell: This is now entering its final comment period, as per the review above. :bell:

rfcbot commented 1 month ago

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

This will be merged soon.

lcnr commented 1 month ago

please also add the 3 tests from https://github.com/rust-lang/rust/issues/129541#issuecomment-2325789416

rust-lang / rust