Inference poisoned by presence of unrelated impl

[Manishearth]

The following code compiles fine:

extern crate serde;
use std::borrow::Cow;

pub fn dothing<'data, V>(
) -> Cow<'data, V>
where
    V: ?Sized + ToOwned ,
    for<'de> Box<V>: serde::Deserialize<'de>,
{
    unimplemented!()
}


pub fn dothing_str<'data>(
) -> Cow<'data, str>
where
{
    dothing()
}

Here, dothing_str() simply uses return type inference to resolve dothing() to dothing::<str>(). Quite straightforward, nothing fancy.

However, if you add in the following type, inference gets poisoned:

pub struct Poison<T: ?Sized> {
    x: T
}


impl<'de, T> serde::Deserialize<'de> for Box<Poison<T>>
where
    T: ?Sized,
    Box<T>: serde::Deserialize<'de>,
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        unimplemented!()
    }
}

Instead of trying to resolve Box<str>: Deserialize (reasonable), it tries to resolve Box<Poison<Poison<Poison<Poison<Poison<Poison<Poison<Poison<Poison<Poison<Poison<Poison<...>>>>>>>>>>>>>: Deserialize. Note that this happens even if you replace the for<'de> ... Deserialize<'de> with Deserialize<'static>, this isn't Yet Another HRTB issue.

Full error

error[E0275]: overflow evaluating the requirement `Box<[_]>: Deserialize<'_>`
  --> src/lib.rs:37:5
   |
37 |     dothing()
   |     ^^^^^^^^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`playground`)
note: required for `Box<Poison<[_]>>` to implement `Deserialize<'_>`
  --> src/lib.rs:9:14
   |
9  | impl<'de, T> serde::Deserialize<'de> for Box<Poison<T>>
   |              ^^^^^^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^
...
12 |     Box<T>: serde::Deserialize<'de>,
   |             ----------------------- unsatisfied trait bound introduced here
   = note: 126 redundant requirements hidden
   = note: required for `Box<Poison<Poison<Poison<Poison<Poison<Poison<Poison<Poison<Poison<Poison<Poison<Poison<...>>>>>>>>>>>>>` to implement `for<'de> Deserialize<'de>`
note: required by a bound in `dothing`
  --> src/lib.rs:27:22
   |
23 | pub fn dothing<'data, V>(
   |        ------- required by a bound in this function
...
27 |     for<'de> Box<V>: serde::Deserialize<'de>,
   |                      ^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `dothing`
   = note: the full name for the type has been written to '/playground/target/debug/deps/playground-dd3320ba655b84a9.long-type-390055455354675765.txt'
   = note: consider using `--verbose` to print the full type name to the console

The poisoning is fixed by explicitly invoking dothing::<str>(). It's the return type inference that's getting grossly misled here, and it's really unclear as to why.

[compiler-errors]

I wouldn't really call this "poisoning" here, or at least saying that inference is being messed up is focusing on the wrong thing here.

What's happening here is that method selection doesn't take into account the return type when probing for methods, and when it's filtering out methods with impossible-to-satisfy where clauses, it's trying to prove Box<?0>: Bar which recurses on ?0 = Poison<?1> = Poison<Poison<?2>> = Poison<Poison<Poison<?3>>>, etc., which then fails with fatal overflow. This all happens before the compiler has a chance to constrain the V variable of dothing to str.

Overflow being fatal in the old trait solver is a general issue, unfortunately.

Here's a minimal repro:

struct W<T>(T);

trait Bar {}

impl<T> Bar for Box<W<T>> where Box<T>: Bar {}

impl Bar for Box<i32> {}

fn dothing<V>() -> V
where
    Box<V>: Bar,
{
    todo!()
}

fn main() {
    let x: i32 = dothing();
}

This should be fixed by the new trait solver.