Loop evaluating Cow<'a, T>: Sized in recursive structure

[ghost]

The example causes the checker to loop with build rustc 1.0.0-dev (81938ec58 2015-03-25) (built 2015-03-25):

src/lib.rs:1:1: 1:1 error: overflow evaluating the requirement `collections::borrow::Cow<'static, Foo> : core::marker::Sized` [E0275]

It does still work using the Rust playpen here. I'm not sure if something changed in the API or if it's a bug or something else. The docs show ToOwned::Owned: Sized so the requirement should be satisfied. /cc @aturon

use std::borrow::*;

enum Foo {
    Bar,
    Baz { cow: Cow<'static, Foo> }
}

impl ToOwned for Foo {
    type Owned = Box<Foo>;
    fn to_owned(&self) -> Box<Foo> {
        let res = match self {
            &Foo::Bar => {
                Foo::Bar
            },
            &Foo::Baz { ref cow } => {
                Foo::Baz { cow: cow.to_owned() }
            }
        };
        Box::new(res)
    }
}

impl Borrow<Foo> for Box<Foo> {
    fn borrow(&self) -> &Foo {
        &**self
    }
}

[aturon]

I believe that @nikomatsakis recently made a change that detected overflow, that may be related (I don't recall the details offhand).

[ghost]

I haven't pinpointed the commit which causes the issue but it is somewhere within 1be8fcb..c5c3de0.

[mitchmindtree]

I think #23707 might be related

[nikomatsakis]

so yes I think this is a dup of #23707 but the error was being swallowed somewhere

[nikomatsakis]

and I think #23707 is a dup of an older issue too :)

[nikomatsakis]

sorry I'm not sure if this is a dup of #23707 specifically; I was thinking of another issue

[jmgrosen]

Any progress here? I'm running into this as well.

[aturon]

Nominating for discussion at compiler team meeting.

[pnkfelix]

assigning P-medium

[eddyb]

This produces "error: overflow evaluating the requirement Foo: std::marker::Sized [E0275]":

use std::borrow::ToOwned;

enum Foo {
    Bar,
    Baz { cow: Result<&'static Foo, <Foo as ToOwned>::Owned> }
}

impl ToOwned for Foo {
    type Owned = Box<Foo>;
    fn to_owned(&self) -> Box<Foo> { loop {} }
}

However, this works:

use std::borrow::Borrow;

pub trait ToOwned {
    type Owned: Borrow<Self>;
    fn to_owned(&self) -> Self::Owned;
}

enum Foo {
    Bar,
    Baz { cow: Result<&'static Foo, <Foo as ToOwned>::Owned> }
}

impl ToOwned for Foo {
    type Owned = Box<Foo>;
    fn to_owned(&self) -> Box<Foo> { loop {} }
}

Does this have to do with coherence cross-crate interactions?

[jonas-schievink]

Both of @eddyb's examples compile now, while the code in the OP still fails.

[steveklabnik]

Triage: OP's code produces

error[E0119]: conflicting implementations of trait `std::borrow::Borrow<Foo>` for type `std::boxed::Box<Foo>`:
  --> src/main.rs:25:1
   |
25 | impl Borrow<Foo> for Box<Foo> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: conflicting implementation in crate `alloc`:
           - impl<T> std::borrow::Borrow<T> for std::boxed::Box<T>
             where T: ?Sized;

error[E0275]: overflow evaluating the requirement `<Foo as std::borrow::ToOwned>::Owned`
  |
  = note: required because it appears within the type `Foo`
  = note: required because of the requirements on the impl of `std::borrow::ToOwned` for `Foo`
  = note: required because it appears within the type `Foo`

[jonas-schievink]

FWIW the issues I had with this in jonas-schievink/xml-rpc-rs#10 are still very much there

[jonas-schievink]

Minimized example:

trait MyToOwned {
    type Owned;
}

// This has an implicit `T: Sized` bound
impl<'a, T> MyToOwned for &'a T {
    type Owned = ();
}

struct MyCow<B: MyToOwned + ?Sized> {
    _owned: <B as MyToOwned>::Owned,
}

struct Test {
    _f: MyCow<&'static Test>,
}

Adding T: ?Sized to the MyToOwned impl breaks the cycle. It seems that the Test definition will check wellformedness of MyCow<&'static Test>, which ends up requiring &'static Test: MyToOwned, which requires Test: Sized due to the MyToOwned impl. This then apparently requires wellformedness of Test again, or something similar.

I do not think this should be an error, since MyCow<B> is always Sized, regardless of B. It looks to me like Sized should maybe be treated more similarly to auto-traits like Send and Sync, but I'm not entirely sure either.

[jonas-schievink]

Interestingly this is accepted:

trait MyToOwned {
    type Owned;
}

// This has an implicit `T: Sized` bound
impl<'a, T> MyToOwned for &'a T {
    type Owned = ();
}

struct MyCow<O, B: MyToOwned<Owned = O> + ?Sized> {
    _owned: (O, B),
}

struct Test {
    _f: MyCow<<&'static Test as MyToOwned>::Owned, &'static Test>,
}

[sunjay]

Ran into this today with some code very similar to the original example. Reduced version below: (Rust Playground)

use std::borrow::Cow;

struct Element {
    children: Cow<'static, [Element]>,
}

I believe this should be accepted because the Cow ends up being an enum of either &[Element] or Vec<Element>, both of which are sized.

The error message is initially pretty confusing because ToOwned is implemented for all [T] so it works in other cases. I did eventually realize it was because rustc is having trouble determining the size of Element without overflowing:

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

For more information about this error, try `rustc --explain E0277`.

It's definitely an issue with the traits because this version that just uses simple types directly compiles with no issues: (Rust Playground)

enum Array<'a, T> {
    Borrowed(&'a [T]),
    Owned(Vec<T>),
}

struct Element {
    children: Array<'static, Element>,
}

Something like this is probably a reasonable workaround for anyone else running into something similar.

[ice1000]

@sunjay's example is exactly what I had when I ran into this issue. Writing my own cow array is not feasible because you not only need to define your own data type, but also all the operations, which is too much for me :(

[Enselic]

Triage: According to #129541 (comment) this has been fixed by accident. Now we just need a regression test(s) to close this issue.

[Enselic]

Triage: This should actually be covered by the test added via https://github.com/rust-lang/rust/pull/133473/files which belongs as another issue. Closing as obsolete.