Recent regression in diagnostics: "overflow evaluating the trait `core::kinds::Sized` for the type `<generic #139>`"

[japaric]

STR

trait Set<T> {
    fn contains(&self, T) -> bool;
    fn set(&mut self, T);
}

impl<'a, T, S> Set<&'a [T]> for S where
    T: Copy,
    S: Set<T>,
{
    fn contains(&self, bits: &[T]) -> bool {
        bits.iter().all(|&bit| self.contains(bit))
    }

    fn set(&mut self, bits: &[T]) {
        for &bit in bits.iter() {
            self.set(bit)
        }
    }
}

fn main() {
    let bits: &[_] = &[0, 1];

    0.contains(bits);
}

Output

overflow.rs:24:5: 24:21 error: overflow evaluating the trait `core::kinds::Sized` for the type `<generic #139>`
overflow.rs:24     0.contains(bits);
                   ^~~~~~~~~~~~~~~~
overflow.rs:24:5: 24:21 error: overflow evaluating the trait `core::kinds::Copy` for the type `<generic #139>`
overflow.rs:24     0.contains(bits);
                   ^~~~~~~~~~~~~~~~
overflow.rs:24:5: 24:21 error: overflow evaluating the trait `core::kinds::Sized` for the type `<generic integer #2>`
overflow.rs:24     0.contains(bits);
                   ^~~~~~~~~~~~~~~~
overflow.rs:24:5: 24:21 error: overflow evaluating the trait `Set<<generic #139>>` for the type `<generic integer #2>`
overflow.rs:24     0.contains(bits);
                   ^~~~~~~~~~~~~~~~
overflow.rs:24:16: 24:20 error: mismatched types: expected `&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[&[<generic #139>]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]`, found `&[<generic integer #0>]` (expected &-ptr, found integral variable)
overflow.rs:24     0.contains(bits);
                              ^~~~
error: aborting due to 5 previous errors

Version

rustc 0.13.0-dev (9a778bc55 2014-10-28 10:11:51 +0000)

---

Compare it to the output of the playpen:

<anon>:24:5: 24:21 error: the trait `Set<<generic integer #0>>` is not implemented for the type `<generic integer #2>`
<anon>:24     0.contains(bits);
              ^~~~~~~~~~~~~~~~
error: aborting due to previous error
playpen: application terminated with error code 101
Program ended.

@thestinger Do you know what's the playpen current rustc version?

According to rusti, the version is/was:

NOTICE: rustc 0.13.0-dev (2130f2221 2014-10-21 19:32:10 +0000)

cc @nikomatsakis

EDIT Added playpen version

[nikomatsakis]

Hmm, I'm not sure if there's a problem here. I mean, this is definitely a cyclic reasoning sort of situation. You're saying that "for any type S that implements Set for something copyable, I will implement it S for &[T] (which is also copyable)". And there are no other impls. So I can see why a cycle arises.

[japaric]

So I can see why a cycle arises.

Could you explain how the compiler ends in a cycle? I can sort of understand how the compiler ends up with the playpen version of the error message:

Facts

• (S).contains(&[T]) method call
• S and T are generic integers
• impl Set<&[T]> for S where T: Copy, S: Set<T>

Processing

• Search for impl that matches (self).contains(&[T])
• Only found impl Set<&[T]> for S
• Look at bounds:
  • T: Copy: OK
  • S: Set<T>: Bound not met
• Raise error: "Set<T> is not implemented by S"

[nikomatsakis]

@japaric what happens is that the compiler tries to determine if the impl applies to the type of the integral literal S. At that point it hasn't processed the arguments of the method call (we need to resolve the method before processing the arguments so we can provide type hints and so forth), and thus it actually only knows that the element type is some variable (let's call it $0).

It seems an impl that says "Set<&T> applies if S is a type that implements Set<T>", so it assumes that maybe $0=&$1 and goes off to look for an impl of Set<$1>. But this is just where we started, basically. (We were looking for an impl of `Set<$0>.) So we wind up repeating the same reasoning ad infinitum.