Using Cow with the Vec/slice ToOwned impl for creating a recursive type fails to typecheck due to overflow

[sdroege]

See the following code

use std::borrow::Cow;

// Does not work either: #[derive(Clone)]
enum Foo<'a> {
    // Does not work:
    Bar(Cow<'a, [Foo<'static>]>),
    // Works: Bar(Vec<Foo<'a>>),
    Baz(&'a str),
}

impl<'a> Clone for Foo<'a> {
    fn clone(&self) -> Self {
        unimplemented!();
    }
}

fn main() {}

This currently fails to compile with

error[E0275]: overflow evaluating the requirement `<[Foo<'a>] as std::borrow::ToOwned>::Owned`
 --> test.rs:5:9
  |
5 |     Bar(Cow<'a, [Foo<'a>]>),
  |         ^^^^^^^^^^^^^^^^^^^
  |
  = note: required because it appears within the type `Foo<'a>`
  = note: required because of the requirements on the impl of `std::borrow::ToOwned` for `[Foo<'a>]`
  = note: required because it appears within the type `std::borrow::Cow<'a, [Foo<'a>]>`
  = note: only the last field of a struct may have a dynamically sized type

However in the end the Cow here is just an enum that is either a &[Foo] or a Vec (the ToOwned instance of [T] uses Vec for the owned variant), both having a known size and thus this all should really work, or am I missing something?

Is this a bug, a missing feature or can't this possibly work?

[sdroege]

Something like

    BarOwned(Vec<Foo<'static>>),
    BarBorrowed(&'a [Foo<'a>]),

Also works FWIW (and then implementing Clone accordingly). Is the compiler for whatever reason evaluating the plain [Foo<'static>] here, although the traits never use it directly?

Independent of that, I also see another problem here when using Cow: the lifetime of Foo. For the Borrowed variant of Cow it should be 'a (&'a [Foo<'a>]), for the Owned variant it should be 'static (i.e. Vec<Foo<'static>>, it's cloned after all). This does not seem to be possible at all currently

[sdleffler]

@sdroege the lifetime of Foo shouldn't be 'static, especially if you're nesting Cows - because you want to be able to have Cows which are borrowed within that nested Foo.

In any case, I'm also running into this problem in my code. I have several hypotheses on what's causing this, and (fair warning) I'm about to ramble on about all of them.

One thing that's pretty clear is that the problem is being triggered by the ToOwned bound on T in Cow<'a, T>. I see a couple of things which make me a little iffy w.r.t. ToOwned: the first is that ToOwned has an impl for T where T: Clone, and then in turn Clone has an impl for T where T: ToOwned. However, I don't see how that could possibly be the problem here, because the overflow is specifically on calculating the associated type <Foo<'a> as ToOwned>::Owned. And there does not (to me) appear to be any reason <Foo<'a> as ToOwned>::Owned should be calculated - note the following code sample:

pub enum Cow<'a, B: ?Sized + 'a>
    where B: ToOwned
{
    Borrowed(&'a B),
    Owned(<B as ToOwned>::Owned),
}

pub struct Foo<'a>(Cow<'a, [Foo<'a>]>);

This is the definition of Cow copied nearly verbatim from the source code in std, and just this - as you can see here - fails to compile (the playground was set to Stable here but it also fails on Nightly.) If you ask me, this code should fail to compile because of a lack of implementation of Clone; but instead it overflows. This, I suspect (hypothesis number one) could be due to the specialization-driven implementation of ToOwned for T: Clone, which could potentially cause an overflow w.r.t. the implementation of Clone for T: ToOwned... That cycle really does feel suspicious to me. But that cycle doesn't look like it's being triggered, according to the resulting error:

rustc 1.18.0 (03fc9d622 2017-06-06)
error[E0275]: overflow evaluating the requirement `<[Foo<'a>] as std::borrow::ToOwned>::Owned`
  --> <anon>:12:20
   |
12 | pub struct Foo<'a>(Cow<'a, [Foo<'a>]>);
   |                    ^^^^^^^^^^^^^^^^^^^
   |
   = note: required because it appears within the type `Foo<'a>`
   = note: required because of the requirements on the impl of `std::borrow::ToOwned` for `[Foo<'a>]`
   = note: required because it appears within the type `Foo<'a>`
   = note: required because of the requirements on the impl of `std::borrow::ToOwned` for `[Foo<'a>]`
   = note: required by `Cow`

error: aborting due to previous error

...well, maybe not. Suppose that the cause of the error is the cycle between ToOwned and Clone. Specifically, suppose we're trying to calculate that Cow<'a, [Foo<'a>]> is a valid type to use at all. The compiler has to verify several things, according to the definition of Cow<'a, [Foo<'a>]>:

• Foo<'a> must be sized (because Foo<'a> is within a slice type.) This doesn't look relevant here.
• [Foo<'a>] must outlive 'a. This should work because of how lifetimes for types are calculated - Foo<'a> is obviously 'a and [Foo<'a>] takes on the lifetime of its parameter.
• [Foo<'a>] must implement ToOwned. This is where the problem appears to start.

rustc begins to dive down the rabbit-hole. It finds ToOwned for [T] where T: Clone, where here T == Foo<'a>. Is Foo<'a>: Clone? Obviously not. Clone has not been implemented for Foo<'a>. So things should stop here with an error. But it doesn't. Why?

Hypothesis number two: when rustc finds Foo<'a> and tries to check whether or not it is Clone, it proceeds as if it has an automatic impl of Clone for Foo<'a>, which would then retrigger the Foo<'a>: ToOwned check. But that wouldn't explain why the Owned associated type is being calculated, because the Cow<'a, T> impl for Clone doesn't rely on T::Owned: Clone or anything like that - instead it uses .borrow().to_owned(). So this one seems very far-fetched, not in the least because it assumes that rustc might try out compiling with an automatic impl of something (which would be crazy and probably very computationally expensive.)

Hypothesis number three: when rustc finds Foo<'a> and tries to check whether or not it is Clone, it ends up triggering yet another check to see whether or not Foo<'a> is a valid type at all, and tries to validate all its internal trait bounds again. This would entail checking [Foo<'a>]'s ToOwned-ness again, which would result in checking for Clone for Foo<'a>, hence completing the cycle. If this is the case, it seems like it would be a bug, which could potentially be seen as an unnecessary strictness of Rust's trait checking; we are already checking to see whether [Foo<'a>] is ToOwned, so there is no reason to check it again. It is part of the inductive hypothesis.

Out of all of these I feel that the last is the most likely, while still somewhat improbable. It is supported somewhat by the way the error says "within the type Foo<'a>", indicating that it is reexamining Foo<'a> for validity. Again, however, the fact that the trace seems to be calculating ::Owned gets in the way.... No clue why that's happening. Or...

Hypothesis number four: rustc is actually checking to be certain that Foo<'a> is Sized. This entails checking that every "ingredient" of the inductive datatype is also Sized. And thus, Cow<'a, [Foo<'a>]> must be Sized. When is it sized? Internally Cow is defined with two variants we must consider, Borrowed and Owned. Borrowed has an &'a T so it's Sized, no questions asked. But Owned is <[Foo<'a>] as ToOwned>::Owned. When is this Sized? It's Sized whenever Vec<Foo<'a>> is Sized. Which is always. But now we run into another problem which is that Foo<'a> must be sized as required by the bounds on [Foo<'a>] and Vec<Foo<'a>>. Which completes the loop.

Number four feels like the smoking gun for this overflow. It deals with Sized, explaining why in your (@sdroege) error message the bit about dynamically-sized types shows up. It explains why ::Owned is being calculated. It explains why rustc appears to be recursively checking the insides of types for validity of some kind (because in this case it would be.) I think some more investigation is needed but I'm pretty certain about this one.

[sdleffler]

In addition, this seems to show that indeed, overflows are happening calculating the Sized bound. This bug has succeeded in irritating me to a level I did not know was previously possible and I think I'm going to grab some coffee and smash rustc with a hammer until it behaves.

[arielb1]

Variant that works:

use std::borrow::Cow;

// Does not work either: #[derive(Clone)]
enum Foo<'a> {
    // Does not work:
    Bar(Cow<'a, [Foo<'static>]>, ()),
    // Works: Bar(Vec<Foo<'a>>),
    Baz(&'a str),
}

impl<'a> Clone for Foo<'a> {
    fn clone(&self) -> Self {
        unimplemented!();
    }
}

fn main() {}

[arielb1]

It's a bit surprising I accidentally allowed possibly-infinite structs back with sized_constraint - cc @nikomatsakis

[nikomatsakis]

@arielb1

It's a bit surprising I accidentally allowed possibly-infinite structs back with sized_constraint

I don't quite follow what you mean by this -- do you mean it is surprising that you chose to do that? Or surprising that the error interacts with that?

[arielb1]

@nikomatsakis

I didn't realize I accidentally re-allowed infinite structs when I implemented that.

[RReverser]

Just ran across this too. I had unrelated thought few days ago which seems could help here too: would it be possible to change Cow to accept any two types instead of one, like

pub enum Cow<'a, B, O = <B as ToOwned>::Owned> where
    B: 'a + ?Sized,
    O: Borrow<B>
{
    Borrowed(&'a B),
    Owned(O),
}

Note that this change is backwards-compatible thanks to default generics still having ToOwned constraint in case custom owned type is not provided:

// works as it did before
let old_style: Cow<[u8]>;

But it also enables interesting new cases:

// works now too despite [u8]::ToOwned being Vec<u8> not Box<[u8]>
let new_style: Cow<[u8], Box<[u8]>>;

and

struct A {}

struct B(A);

impl Borrow<A> for B {
    fn borrow(&self) -> &A {
        &self.0
    }
}

// works despite A not having ToOwned
let d: Cow<A, B>;

And even allows to work around this particular issue:

enum Foo<'a> {
    // works now too thanks to the explicit owned type
    Bar(Cow<'a, [Foo<'a>], Vec<Foo<'a>>>),

    // can do even this now
    Baz(Cow<'a, Foo<'a>, Box<Foo<'a>>>),
}

@nikomatsakis @arielb1 @sdleffler What do you think?

[sdleffler]

@RReverser you'd need an extra trait bound on O = <B as ToOwned>::Owned; something along the lines of O: for<'a> From<&'a B>, which complicates things. ToOwned provides a way to create a ToOwned::Owned from an &B through ToOwned::to_owned, so for an arbitrary owned representation O, there must be some sort of analogous path from &B.

I'm not sure if there's a stdlib trait right now which represents this accurately. ToOwned was a generalization of Clone; we then would need a generalization of ToOwned which gives us this hypothetical trait. Does this already exist, and if not, does it have any potential use outside of this?

In any case, I feel that using such a workaround for this is the wrong approach, as this is pretty clearly a bug (some sort of missing inductive hypothesis inside the is-this-type-sized checker.) Would still be interesting to have a generalized Cow though.

[RReverser]

@sdleffler

you'd need an extra trait bound on O = <B as ToOwned>::Owned; something along the lines of O: for<'a> From<&'a B>, which complicates things.

That's already covered by Borrow constraint if I understand your concern correctly. Or do you mean that O has to be constructive from B? That's not necessary for such type to contain data in general, only few impls will need it.

ToOwned was a generalization of Clone; we then would need a generalization of ToOwned which gives us this hypothetical trait.

That's the beauty of having second type param - it doesn't have to implement any built-in trait as long as O can be borrowed as B.

In any case, I feel that using such a workaround for this is the wrong approach

Yeah, as I said, it's mostly unrelated (I need it to deal with boxed slices and with custom reference / owned type pairs), it just happens to help with this bug as well.

[sdleffler]

@RReverser no, it's not covered by Borrow. Borrow says, "I can take the owned type O and borrow B from it"; it provides a single method, fn borrow(&self) -> &Borrowed. But that doesn't get you a way to construct an O from a B, just a way to get a B from an O. With the setup you have there, it's impossible to implement .to_mut(); there's no way to take the borrowed version and make it owned.

i.e. there is no way to construct an owned version O from a borrowed version B under your scheme; that's my concern.

[sdleffler]

@RReverser I suppose the impact of not being able to construct an O from a B isn't as bad as I thought. The base read-only functionality has no issues, and the other impls which depend on it are all specialized to specific types (Vec/[T], String/str.)

[RReverser]

The base read-only functionality has no issues, and the other impls which depend on it are all specialized to specific types (Vec/[T], String/str.)

Yup :) Thanks for confirmation.