Why do I get "overflow evaluating the requirement `Sized`" when using tokio_io's read_exact with a Rc?

Question

There are quite a few similar errors already posted:

"Overflow evaluating the requirement" but that kind of recursion should not happen at all
What does "Overflow evaluating the requirement" mean and how can I fix it?

My case is much more simple and looks innocent:

extern crate tokio_core;
extern crate tokio_io;

use std::{borrow::Borrow, rc::Rc};
use tokio_core::net::TcpStream;
use tokio_io::io::read_exact;

fn read_one(conn: Rc<TcpStream>) {
    read_exact(conn.borrow(), [0u8]);
}

It gives this error:

error[E0275]: overflow evaluating the requirement `_: std::marker::Sized`
 --> src/main.rs:9:5
  |
9 |     read_exact(conn.borrow(), [0u8]);
  |     ^^^^^^^^^^
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
  = note: required because of the requirements on the impl of `std::io::Read` for `&tokio_core::reactor::poll_evented2::PollEvented<_>`
  = note: required because of the requirements on the impl of `std::io::Read` for `&tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<_>>`
  = note: required because of the requirements on the impl of `std::io::Read` for `&tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<_>>>`
[... snip ...]
  = note: required because of the requirements on the impl of `std::io::Read` for `&tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<_>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
  = note: required because of the requirements on the impl of `tokio_io::AsyncRead` for `&tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<tokio_core::reactor::poll_evented2::PollEvented<_>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
  = note: required by `tokio_io::io::read_exact`

What is going on?

I know the following works and it is simpler than the above:

read_exact(&*conn, [0u8]);

I believe conn.borrow should work as well, I just don't understand why we have this error.

This `read_exact::<&TcpStream, _>(conn.borrow(), [0u8]);` would work, I don't have the knowledge to explain it but it's similar to the answers of the questions you link. "This results in an overflow and general sadness. Rust never finds a disproof, so can't ever guarantee it's going down the wrong path." — Stargateur, May 05 '18 at 14:30
Right. I feel like the reason behind is the same. But if this is a bug in the compiler that is not easy to fix, shall I blame `tokio`? If my own libraries run into this issue, how to avoid the user from getting confused like this? — Earth Engine, May 06 '18 at 09:41
Maybe you should search or open an issue on the github of rust compiler, they will be able to answer you properly (and after don't forget to come here with the answer ;)) — Stargateur, May 07 '18 at 13:26

score 4 · Accepted Answer · edited May 12 '18 at 17:05

The difference between &*conn and conn.borrow() is that a type may have multiple Borrow impls.

use std::borrow::Borrow;

fn main() {
    let input = vec![1, 2, 3];

    let _slice:   &[u8]    = input.borrow(); // ok
    let _vec_ref: &Vec<u8> = input.borrow(); // also ok 

    let _slice:   &[u8]    = &*input; // ok
//  let _vec_ref: &Vec<u8> = &*input; // error!
}

The &*conn expression uses the Deref trait, where each type can only have a single Deref implementation. However, a type can have multiple Borrow<X> implementations for different Xs.

When you write

read_exact(conn.borrow(), [0u8]);

The compiler needs to solve the following obligations:

Rc<TcpStream>: Borrow<X1> due to use of borrow()
&X1: AsyncRead due to read_exact

Note that X1 is an unknown type. The compiler will need to find out all potential X1s and see if anyone can fit into both obligations. Obligation 2 somehow got evaluated first, which ends up with these candidates:

impl<X2> AsyncRead for &PollEvented<X2> where &X2: Read
impl AsyncRead for &TcpStream
impl AsyncRead for &[u8] and probably more unimportant candidates...

Again, somehow candidate 1 is selected before candidate 2. This leads to the following new set of obligations after candidate 1 is selected:

Rc<TcpStream>: Borrow<PollEvented<X2>>
~~&PollEvented<X2>: AsyncRead~~ solved!
&X2: Read

which then leads to impl<X3> Read for &PollEvented<X3> where &X3: Read being selected, and from this point the solver got stuck in an infinite loop and eventually gave up.

Details about how the compiler solves these equations can be found in the Rust Compiler Guide.

The good news is that the trait system is being revamped to use standard logic inference techniques (like Prolog) which allows OP's program to be inferred correctly.

However, before the new trait engine is implemented, if you must use borrow you could help the compiler a little bit by telling it what X1 should be:

read_exact::<&TcpStream, _>(conn.borrow(), [u8]);
//           ^~~~~~~~~~ forces &X1 = &TcpStream

In case you're interested, the following chalk program proves that the new solver can typecheck OP's example

trait Borrow<T> {}
trait AsyncRead {}
trait Read {}

struct Ref<T> {} // meaning &T

struct Rc<T> {}
impl<T> Borrow<T> for Rc<T> {}

struct TcpStream {}
impl Read for TcpStream {}
impl AsyncRead for TcpStream {}
impl Read for Ref<TcpStream> {}
impl AsyncRead for Ref<TcpStream> {}

struct PollEvented<E> {}
impl<E> AsyncRead for Ref<PollEvented<E>> where Ref<E>: Read {}
impl<E> Read for Ref<PollEvented<E>> where Ref<E>: Read {}

// Verify:
// 
// ?- exists<X> { Ref<X>: AsyncRead, Rc<TcpStream>: Borrow<X> }
// Unique; substitution [?0 := TcpStream], lifetime constraints []

While I was researching this problem, a compiler developer told me that there's some special case for resolving references that allows the infinite recursion. I'm not sure if it's the reference in `&X1: AsyncRead` or one of the ones in `impl AsyncRead for &PollEvented where &X2: Read` that triggers this special case though. — Shepmaster, May 12 '18 at 17:07
*allows OP's program to be inferred correctly* — do you know *how*? There's still a possible infinite loop with `AsyncRead`; does it now take into account that there's only the one implementation of `Borrow` for `Rc`? — Shepmaster, May 12 '18 at 17:10
@Shepmaster I think you'll need to ask niko for "how", I just know it works Perhaps via some methods written in http://smallcultfollowing.com/babysteps/blog/2017/09/12/tabling-handling-cyclic-queries-in-chalk/ — kennytm, May 12 '18 at 17:19
I was thought that `x.borrow()` is equivalent to `&*x`, but if I know `&*x` is actually equivalent to `x.deref()` I would use this instead if possible. Just a but dislike magical symbol operators. — Earth Engine, May 13 '18 at 07:21
@kennytm So the new engine is just the same (I mean, does the same thing, maybe in a different way) as the old, but uses BFS rather than DFS so it will not being trapped in a circle, am I right? — Earth Engine, May 13 '18 at 07:23
@EarthEngine Sort of [(yes the search is BFS)](http://smallcultfollowing.com/babysteps/blog/2018/01/31/an-on-demand-slg-solver-for-chalk/). Also, by expressing the trait system in terms of logic, it also allows us to support more complex features like GATs more naturally. — kennytm, May 13 '18 at 07:55

Why do I get "overflow evaluating the requirement `Sized`" when using tokio_io's read_exact with a Rc?

1 Answers1

Linked