Overflow evaluating requirement Sized

[Coder-256]

Over the past week I have been trying to solve a bizarre and fragile "overflow evaluating requirement" error; it seems to manifest with various different traits, and sometimes appears or disappears when I make seemingly unrelated changes.

For example, consider the following:

pub trait AsCustomRef {
    type CustomRef;
}
pub struct CustomBox<T: AsCustomRef>(T::CustomRef);
impl<T> AsCustomRef for Box<T> {
    type CustomRef = ();
}
impl<R: AsCustomRef> AsCustomRef for Option<R> {
    type CustomRef = R::CustomRef;
}

pub struct Node<T> {
    value: T,
    next: CustomBox<Option<Box<Node<T>>>>,
}

This gives the following error:

error[E0275]: overflow evaluating the requirement `Node<T>: Sized`
  --> src/lib.rs:14:11
   |
14 |     next: CustomBox<Option<Box<Node<T>>>>,
   |           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: required for `Box<Node<T>>` to implement `AsCustomRef`
  --> src/lib.rs:5:9
   |
5  | impl<T> AsCustomRef for Box<T> {
   |      -  ^^^^^^^^^^^     ^^^^^^
   |      |
   |      unsatisfied trait bound introduced here
   = note: 1 redundant requirement hidden
   = note: required for `Option<Box<Node<T>>>` to implement `AsCustomRef`
note: required by a bound in `CustomBox`
  --> src/lib.rs:4:25
   |
4  | pub struct CustomBox<T: AsCustomRef>(T::CustomRef);
   |                         ^^^^^^^^^^^ required by this bound in `CustomBox`

For more information about this error, try `rustc --explain E0275`.
error: could not compile `overflow-error` (lib) due to 1 previous error

HOWEVER, if the value and next fields are swapped (ie. literally swap lines 13 and 14), the error disappears. Or if I add another field to the struct after next, the error disappears.

In this case, this seems possibly related to how the last member of a struct can be unsized. However I've been having a very very similar problem with traits other than Sized as well (this is just the most bizarre and minimized case I could find). This has to be a bug, right?

My vague, uneducated guess: when performing certain trait bound checks like Node<T>: Sized, maybe the compiler has one approach that leads to an infinite recursion, and another approach that works successfully. Depending on which approach it happens to try first, compilation may succeed or fail?

[jumpnbrownweasel]

May be one of these:

E0275: Overflow evaluating the requirement with a generic impl

Hi, I'm trying to design a highly generic AST, which allows each expression/statement/etc. to have user-specified associated data, as well as user-specified IR statements and expressions. The general design I have is: A trait for functionality that is required from the associated data (how to Visit it with the visitor pattern) (AssociatedData). A trait consisting of associated types, one for each of the several IR items and associated data types (AstAssociations). Downstream crates create an …

Overflow evaluating the requirement with a where clause on associated type

[Coder-256]

I have looked at countless possible duplicate issues, in particular the ones here: rust - Why do I get an "overflow evaluating the requirement" error for a simple trait implementation? - Stack Overflow

This error message seems to crop up in a ton of places, under weird and fragile circumstances that are often super difficult to avoid. I am no rustc expert but I suspect it could have something to do with this logic

rust-lang/rust/blob/7caad6925314911eefe54b040d4bc5be940e8f92/compiler/rustc_trait_selection/src/error_reporting/traits/overflow.rs#L40-L45

This seems to state that overflows immediately halt compilation, rather than falling back to other checks. However I suspect there may be a lot of code that may or may not cause an overflow during trait solving, simply depending on the order that checks are performed, and this seems super fragile (such as this example). But I really don't know the internals of rustc super well and this is just a guess.

[quinedot]

I think for the OP it's basically, the next field type is valid only if Option<Box<Node<T>>>: AsCustomRef, and in order to solve that, you have to ultimately prove that Node<T> is Sized (so that impl<T> AsCustomRef for Box<T> can apply).

Ok, so, is Node<T>: Sized? It is iff the field type of next is Sized.... leading to a loop in the trait solver.

If you swap the fields or add a sized field after the recursive field, there is no loop. You can also add a where Node<T>: Sized constraint (so that it's a known pre-condition), but this is far from ideal, because you have to repeat that constraint everywhere.

If you relax the requirements for the Box<T> implementation so that it does not require T: Sized, that also works.

"Coinduction" is a term you can look for to find a lot of related discussion.

[Coder-256]

Thank you, I see, that helps a lot. In fact perhaps it's related to this: Loop evaluating Cow<'a, T>: Sized in recursive structure · Issue #23714 · rust-lang/rust · GitHub

Unfortunately I think that may only be possible for Sized; perhaps I should have focused on other traits originally. For example, if I try to bound on Sync (which is what I was originally trying to do in the actual project):

pub trait AsCustomRef: Sync {
    type CustomRef;
}
pub struct CustomBox<T: AsCustomRef>(T::CustomRef);
impl<T: Sync> AsCustomRef for Box<T> {
    type CustomRef = ();
}
impl<R: AsCustomRef> AsCustomRef for Option<R> {
    type CustomRef = R::CustomRef;
}

pub struct Node<T: Sync> {
    next: CustomBox<Option<Box<Node<T>>>>,
    value: T,
}

fn make_node() -> Node<u32> {
    Node {
        next: CustomBox(()),
        value: 123
    }
}

Is there some workaround I can use to get this to work?

Edit: Also the error is really weird, and seems to still involve the whole Sized issue despite having reordered the fields:

error[E0275]: overflow evaluating the requirement `CustomBox<Option<Box<Node<T>>>>: Sync`
  --> src/lib.rs:13:11
   |
13 |     next: CustomBox<Option<Box<Node<T>>>>,
   |           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: required because it appears within the type `Node<T>`
  --> src/lib.rs:12:12
   |
12 | pub struct Node<T: Sync> {
   |            ^^^^
note: required for `Box<Node<T>>` to implement `AsCustomRef`
  --> src/lib.rs:5:15
   |
5  | impl<T: Sync> AsCustomRef for Box<T> {
   |         ----  ^^^^^^^^^^^     ^^^^^^
   |         |
   |         unsatisfied trait bound introduced here
note: required because it appears within the type `CustomBox<Option<Box<Node<T>>>>`
  --> src/lib.rs:4:12
   |
4  | pub struct CustomBox<T: AsCustomRef>(T::CustomRef);
   |            ^^^^^^^^^
   = note: only the last field of a struct may have a dynamically sized type
   = help: change the field's type to have a statically known size
help: borrowed types always have a statically known size
   |
13 |     next: &CustomBox<Option<Box<Node<T>>>>,
   |           +
help: the `Box` type always has a statically known size and allocates its contents in the heap
   |
13 |     next: Box<CustomBox<Option<Box<Node<T>>>>>,
   |           ++++                               +

For more information about this error, try `rustc --explain E0275`.
error: could not compile `overflow-error` (lib) due to 1 previous error

[quinedot]

I think it's still in the realm of "proving auto-traits on a recursive type" causing cycles.

When would you expect Node<T>: Sync given T: Sized + Sync? It's an auto-trait based on the fields of Node<T>.

• T: Sync for value, sure, that's a precondition
• CustomBox<Option<Box<Node<T>>>>: Sync
  • Option<Box<Node<T>>>: Sized + AsCustomRef<CustomRef: Sync>
  • (Now we have bounds on associated types as a complication)
    • Box<Node<T>>: Sized + AsCustomRef<CustomRef: Sync>
    • (Assuming the compiler equalizes the associated types)
      • Node<T>: Sized + Sync, (): Sync, second is trivial

So Node<T>: Sync if Node<T>: Sync. (And it's possible for the Sized bound to still be a problem depending on if "couldn't prove this was well-formed" is considered Sized or not. IIUC.)

You can break this cycle by implementing Sync yourself (so the solver doesn't have to recurse into the fields).

// SAFETY: Uh... you prove it ;-)
unsafe impl<T: Sync> Sync for Node<T> {}

The indirection through an associated type makes me a bit nervous, because your CustomBox doesn't actually hold a T, it holds a <Option<Box<Node<T>>> as AsCustomRef>::CustomRef. I don't know that there's a way to ask the compiler to prove this for you on the implementation without reintroducing the cycles, so the safety of your implementation relies on keeping track of how the associated types tie together (what type(s) the field of next actually contains).

You could ease this burden by making Sync a requirement on the associated type.

Or perhaps with some test on the field instead:

fn _enforce_field_type<T: Sync>(node: Node<T>) {
    let cb @ CustomBox(()) = node.next;
    let _: &dyn Sync = &cb;
}

Rust Playground

[Coder-256]

Thanks for the insightful answer. I agree this is about auto-traits on recursive types. I had thought my use case was supported, though maybe it's not unfortunately. For example, in this simple struct, Rust does seem to infer that BasicNode<T>: Sync where T: Sync:

struct BasicNode<T> {
    value: T,
    next: Option<Box<BasicNode<T>>>,
}

I am starting to think this only works in simple, narrow cases; and perhaps in particular it doesn't work at all when associated types are involved. I definitely see your point that I could unsafely implement Sync; however I was hoping to allow end-users to write types such as Node<T> and let the compiler infer Sync. I think with better coinduction support this should definitely be possible; the only reason it's not working now is because of an overflow error, ie. the compiler can't prove the bounds are satisfied, even though theoretically it does have enough info to prove this. I guess maybe coinduction for auto traits just doesn't work well with associated types in current Rust with the current trait solver...

Even if I do provide e.g. unsafe impl<T: Sync> Sync for Node<T>, it doesn't work for user-created wrappers around Node<T>. And let's say a user wanted to implement something like a doubly-linked list instead of singly-linked, that would require the library to provide a node type with an unsafe impl, and other structures would need their own library-provided node types as well.

I also definitely see your point about indirection through the associated types looking questionable; don't worry, in the actual library, all the relevant traits are either sealed or unsafe trait. Making the associated types have a Sync bound is also definitely a good idea (but still faces the same issue; I need to enforce a stronger bound that R itself is Sync in addition to R::CustomRef; think I want to allow Arc<T> but not Rc<T>).

[quinedot]

Yeah, I don't know if it's due to the associated types, or just due to having to trait solving on implementations with bounds in general, or what. If you get rid of the supertrait Sync bound so you can get rid of the T: Sync condition on AsCustomRef for Box<T>, it also works out. I guess this is similar to removing the Sized bound in the OP.

I agree it feels like better coinduction would allow this case.

[riking]

@Coder-256

Is there some workaround I can use to get this to work?

Add a final: () field to the end of the structure to lift the Sized requirement to be checked earlier?

[Coder-256]

Thank you. I mentioned this workaround in my original post. However it doesn't answer the question of why changing the field order breaks the build (since it shouldn't matter in this example whether the struct is sized), and more importantly, this doesn't solve the issue for other auto traits like Send/Sync which I need for my project.