Deriving Clone with a recursive Cow slice

[jongiddy]

The following code:

#[derive(Clone)]
struct B<'a> {
    cs: std::borrow::Cow<'a, [C<'a>]>,
}

#[derive(Clone)]
struct C<'a> {
    // b: &'a bool  // works if b is not recursive
    b: B<'a>
}

expands to

struct B<'a> {
    cs: std::borrow::Cow<'a, [C<'a>]>,
}
impl<'a> ::core::clone::Clone for B<'a> {
    #[inline]
    fn clone(&self) -> B<'a> {
        match *self {
            B { cs: ref __self_0_0 } =>  // __self_0_0: &Cow<[C]>
                B { cs: ::core::clone::Clone::clone(&(*__self_0_0)) },
        }
    }
}

struct C<'a> {
    b: B<'a>,
}
impl<'a> ::core::clone::Clone for C<'a> {
    #[inline]
    fn clone(&self) -> C<'a> {
        match *self {
            C { b: ref __self_0_0 } =>  // __self_0_0: &B
                C { b: ::core::clone::Clone::clone(&(*__self_0_0)) },
        }
    }
}

but fails with the following error:

error[E0277]: the trait bound `[C<'a>]: ToOwned` is not satisfied
   --> src/lib.rs:4:9
    |
4   |     cs: std::borrow::Cow<'a, [C<'a>]>,
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `ToOwned` is not implemented for `[C<'a>]`
    |
    = help: the following implementations were found:
              <[T] as ToOwned>
note: required by a bound in `Cow`

This looks to me like it meets all the required trait bounds, but am I missing something? Is it possible to derive Clone for a recursive data structure?

[steffahn]

Apparently, rustc is unable to figure out that C<'a>: Sized here, but the error message is super confusing because it doesn't talk about sizedness at all. If you simplify to

#[derive(Clone)]
struct B {
    cs: std::borrow::Cow<'static, [C]>,
}

#[derive(Clone)]
struct C {
    b: B,
}

it talks about note: slice and array elements must have Sized type. If instead you switch to an older compiler version up until 1.48 it errored with overflow evaluating the requirement `C<'a>: Sized.

The complication AFAICT (playing compiler myself, not trying to understand the error message) is that:

1. for [C<'a>] to be valid, C<'a> needs to be Sized
2. in order for C<'a> to be Sized, its field’s type B<'a> needs to be Sized
3. in order for B<'a> to be Sized, Cow<'a, [C<'a>]> needs to be Sized
   • Cow<'a, [C<'a>]> has a variant with a <[C<'a>] as ToOwned>::Owned type, so:
4. in order for Cow<'a, [C<'a>]> to be Sized, <[C<'a>] as ToOwned>::Owned needs to be Sized
5. in order for rustc to know that <[C<'a>] as ToOwned>::Owned is sized, it needs to know what the type is, so it needs to find an implementation fo ToOwned for [C<'a>]
   • there is a generic implementation of ToOwned for [T] for types T: Clone + Sized
6. in order for the generic implementation of ToOwned for [T] for types T: Clone + Sized to apply to the case T == C<'a>, C<'a> needs to be Sized
7. back to step 2.

Ultimately, C<'a> is only sized if it is sized, and apparently the compiler doesn’t like to decide in favor of C<'a> being sized in this case. A simpler example would be code like this

trait Foo {
    type Ty;
}

impl<T> Foo for T {
    type Ty = ();
}

struct B {
    b: <B as Foo>::Ty,
}

---

Edit: Wait… there’s a way simpler approach the compiler could solve this: The associated type Owned in the ToOwned trait always has to be sized anyways, because it’s not declared as type Owned: ?Sized + Borrow<Self>. The same thing applies to the trait Foo { type Ty; } example above. It seems annoying that that apparently doesn’t happen…

[quinedot]

overflow evaluating the requirement ...

Workaround:

#[derive(Clone)]
struct Dummy<T>(T);

#[derive(Clone)]
struct B<'a> {
    cs: Dummy<std::borrow::Cow<'a, [C<'a>]>>,
}

See also.