Self-referential struct with Cow<[Self]> as the last field errors

[mbartlett21]

I tried this code:

use std::borrow::Cow;

struct Element<'a> {
    arr: Cow<'a, [Element<'a>]>,
}

// So that `ToOwned` *should* be implemented for `[Element<'a>]`.
impl<'a> Clone for Element<'a> {
    fn clone(&self) -> Self {
        todo!()
    }
}

Compiling it, I got these errors:

error[E0277]: the trait bound `[Element<'a>]: ToOwned` is not satisfied
   --> src/lib.rs:4:10
    |
4   |     arr: Cow<'a, [Element<'a>]>,
    |          ^^^^^^^^^^^^^^^^^^^^^^ the trait `ToOwned` is not implemented for `[Element<'a>]`
    |
    = help: the following implementations were found:
              <[T] as ToOwned>

(this is presumably because there is a reference to the struct)

error[E0277]: the trait bound `[Element<'a>]: ToOwned` is not satisfied in `Element<'a>`
   --> src/lib.rs:7:10
    |
7   | impl<'a> Clone for Element<'a> {
    |          ^^^^^ within `Element<'a>`, the trait `ToOwned` is not implemented for `[Element<'a>]`
    |
    = help: the following implementations were found:
              <[T] as ToOwned>

note: required because it appears within the type `Element<'a>`
   --> src/lib.rs:3:8
    |
3   | struct Element<'a> {
    |        ^^^^^^^

A "fix"

Changing line 4 to use an Option works for no obvious reason, and will also add an extra cost to using the field:

  struct Element<'a> {
<     arr: Cow<'a, [Element<'a>]>,
>     arr: Option<Cow<'a, [Element<'a>]>>,
  }

Meta

rustc --version --verbose:

rustc 1.57.0-nightly (dfc5add91 2021-10-13)
binary: rustc
commit-hash: dfc5add915e8bf4accbb7cf4de00351a7c6126a1
commit-date: 2021-10-13
host: x86_64-pc-windows-msvc
release: 1.57.0-nightly
LLVM version: 13.0.0

[mbartlett21]

For some reason, it works when I do it without using ToOwned:

Examples

Not Working:

use std::borrow::ToOwned;

struct Element<'a> {
    arr: CowVec<'a, Element<'a>>,
}

impl Clone for Element<'_> {
    fn clone(&self) -> Self { todo!() }
}

enum CowVec<'a, B> 
where
    B: 'a + Clone, 
 {
    Borrowed(&'a [B]),
    Owned(<[B] as ToOwned>::Owned),
}

(playground)

Changing CowVec::Owned to use a Vec fixes it:

      Borrowed(&'a [B]),
-     Owned(<[B] as ToOwned>::Owned),
+     Owned(Vec<B>),
  }

(playground)

[oberien]

It also happens in a simpler example with the 'static lifetime:

use std::borrow::Cow;

#[derive(Clone)]
struct Foo {
    foo: Cow<'static, [Foo]>,
}

This results in the following error:

error[E0277]: the trait bound `[Foo]: ToOwned` is not satisfied in `Foo`
 --> src/lib.rs:5:23
  |
5 |     foo: Cow<'static, [Foo]>,
  |                       ^^^^^ within `Foo`, the trait `ToOwned` is not implemented for `[Foo]`
  |
  = help: the following implementations were found:
            <[T] as ToOwned>
note: required because it appears within the type `Foo`
 --> src/lib.rs:4:8
  |
4 | struct Foo {
  |        ^^^
  = note: slice and array elements must have `Sized` type

error[E0277]: the trait bound `[Foo]: ToOwned` is not satisfied in `Foo`
   --> src/lib.rs:3:10
    |
3   | #[derive(Clone)]
    |          ^^^^^ within `Foo`, the trait `ToOwned` is not implemented for `[Foo]`
    |
    = help: the following implementations were found:
              <[T] as ToOwned>
note: required because it appears within the type `Foo`
   --> src/lib.rs:4:8
    |
4   | struct Foo {
    |        ^^^
note: required by a bound in `Clone`
    = note: this error originates in the derive macro `Clone` (in Nightly builds, run with -Z macro-backtrace for more info)

[de-vri-es]

This only seems to happen when the Cow<'a, [Self]> is the last field in a struct:

For example, this compiles (playground):

use std::borrow::Cow;

#[derive(Clone)]
struct Foo<'a> {
    children: Cow<'a, [Self]>,
    _foo: (),
}

But this does not (playground):

use std::borrow::Cow;

#[derive(Clone)]
struct Foo<'a> {
    children: Cow<'a, [Self]>,
}

It almost looks like the compiler is wrongly determining that the second Foo is variable sized, and hence can not implement Clone (and then ToOwned is not implemented for [Self]).

---

If you write it out like this:

use std::borrow::Cow;

struct Foo<'a> {
    children: Cow<'a, [Self]>,
}

impl<'a> Clone for Foo<'a> {
    fn clone(&self) -> Self {
        let children = match self.children {
            Cow::Owned(x) => Cow::Owned(x.clone()),
            Cow::Borrowed(x) => Cow::Borrowed(x),
        };
        Self { children }
    }
}

You get the last compiler error pointing at an unsatisfied Sized bound:

   Compiling foo v0.1.0 (/tmp/2022-01-10-16-11-09/foo)
error[E0277]: the trait bound `[Foo<'a>]: ToOwned` is not satisfied
   --> src/lib.rs:4:15
    |
4   |     children: Cow<'a, [Self]>,
    |               ^^^^^^^^^^^^^^^ the trait `ToOwned` is not implemented for `[Foo<'a>]`
    |
    = help: the following implementations were found:
              <[T] as ToOwned>
note: required by a bound in `Cow`
   --> /home/maarten/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/borrow.rs:183:8
    |
183 |     B: ToOwned,
    |        ^^^^^^^ required by this bound in `Cow`

error[E0277]: the trait bound `[Foo<'a>]: ToOwned` is not satisfied in `Foo<'a>`
   --> src/lib.rs:7:10
    |
7   | impl<'a> Clone for Foo<'a> {
    |          ^^^^^ within `Foo<'a>`, the trait `ToOwned` is not implemented for `[Foo<'a>]`
    |
    = help: the following implementations were found:
              <[T] as ToOwned>
note: required because it appears within the type `Foo<'a>`
   --> src/lib.rs:3:8
    |
3   | struct Foo<'a> {
    |        ^^^
note: required by a bound in `Clone`
   --> /home/maarten/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/clone.rs:108:18
    |
108 | pub trait Clone: Sized {
    |                  ^^^^^ required by this bound in `Clone`

For more information about this error, try `rustc --explain E0277`.
error: could not compile `foo` due to 2 previous errors

[sosthene-nitrokey]

This also affects enums.

#[derive(Clone)]
enum Element {
    First( Cow<'static, [Element]>)
}

gives

Compiling playground v0.0.1 (/playground)
error[[E0277]](https://doc.rust-lang.org/nightly/error-index.html#E0277): the trait bound `[Element]: ToOwned` is not satisfied in `Element`
 --> src/lib.rs:5:25
  |
5 |     First( Cow<'static, [Element]>)
  |                         ^^^^^^^^^ within `Element`, the trait `ToOwned` is not implemented for `[Element]`
  |
  = help: the trait `ToOwned` is implemented for `[T]`
note: required because it appears within the type `Element`
 --> src/lib.rs:4:6
  |
4 | enum Element {
  |      ^^^^^^^
  = note: slice and array elements must have `Sized` type

error[[E0277]](https://doc.rust-lang.org/nightly/error-index.html#E0277): the trait bound `[Element]: ToOwned` is not satisfied in `Element`
 --> src/lib.rs:3:10
  |
3 | #[derive(Clone)]
  |          ^^^^^ within `Element`, the trait `ToOwned` is not implemented for `[Element]`
  |
  = help: the trait `ToOwned` is implemented for `[T]`
note: required because it appears within the type `Element`
 --> src/lib.rs:4:6
  |
4 | enum Element {
  |      ^^^^^^^
note: required by a bound in `Clone`
  = 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 `playground` due to 2 previous errors

Playground

And the trick of adding a field works also:

#[derive(Clone)]
enum Element {
    First( Cow<'static, [Element]>, ())
}

Compiles (playground )

[CAD97]

This gave a requirement evaluation overflow error on 1.48; 1.49 changed it to the [Self]: ToOwned obligation failure.

snippet

use std::borrow::ToOwned;

#[derive(Clone)]
pub enum Test {
    Owned(<[Test] as ToOwned>::Owned),
}

1.48

error[E0275]: overflow evaluating the requirement `Test: Sized`
 --> <source>:5:11
  |
5 |     Owned(<[Test] as ToOwned>::Owned),
  |           ^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: required because of the requirements on the impl of `ToOwned` for `[Test]`

error[E0275]: overflow evaluating the requirement `Test: Sized`
   --> <source>:3:10
    |
3   | #[derive(Clone)]
    |          ^^^^^
    |
    = note: this error originates in a derive macro (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to 2 previous errors

1.49

error[E0277]: the trait bound `[Test]: ToOwned` is not satisfied
 --> <source>:5:11
  |
5 |     Owned(<[Test] as ToOwned>::Owned),
  |           ^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `ToOwned` is not implemented for `[Test]`
  |
  = help: the following implementations were found:
            <[T] as ToOwned>

error[E0277]: the trait bound `[Test]: ToOwned` is not satisfied in `Test`
   --> <source>:3:10
    |
3   | #[derive(Clone)]
    |          ^^^^^ within `Test`, the trait `ToOwned` is not implemented for `[Test]`
    |
    = help: the following implementations were found:
              <[T] as ToOwned>
    = note: required because it appears within the type `Test`
    = note: this error originates in a derive macro (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to 2 previous errors

From the release notes, compatibility note Trait bounds are no longer inferred for associated types. seems highly relevant.

@rustbot modify labels: +D-confusing +D-incorrect +A-traits +E-needs-mcve

Also suggesting regression-from-stable-to-stable Performance or correctness regression from one stable version to another. since this is a regression in diagnostic clarity; an obligation loop is at least a correct and somewhat useful diagnostic; the current behavior is at best confusing.

Two more interesting observations: defining ToOwned locally seems to work (not error) [playground], and implementing the bound the error says is unsatisfied leads to a requirement evaluation cycle on Test: Sized [playground].

It appears that the underlying issue preventing this from working is that the field projection is not known to be Sized without resolving it, which recursively requires proving it to be Sized. My guess is that the implied Sized bound is taken into account for a local definition of ToOwned, which is why a local definition works, but that this bound isn't being taken advantage of before trying to resolve the projection when ToOwned is defined in a separate crate. When it isn't the last field, that is used as sufficient to assume that the type projection is Sized, and thus everything works out.

Replicating this without std involvement will help. Note this seems to require two crates, which makes this significantly more interesting.