Infinite "recursive requirements" compiler error

[rosscanning]

When compiling this program, the compiler fails with an infinitely recursive error message. The message makes no sense, as it contains types that aren't even in the program.

use std::ops::{Add, Sub};

struct Point2d<T> {
    pub x: T,
    pub y: T,
}

impl<'a, T> Sub<&'a Point2d<T>> for &'a Point2d<T>
where &'a T: Sub<&'a T, Output=T>,
{
    type Output = Point2d<T>;
    fn sub(self, other: &'a Point2d<T>) -> Self::Output { unimplemented!();  }
}

fn f1<'a, I>(x: &'a I)
where &'a I: Sub<Output=I> {   unimplemented!(); }

fn main() {
    let a = 123;
    f1(&a);
}

This code won't do anything, but it should compile (I think). Instead, the compiler emits an infinite series of error messages like:

error[E0275]: overflow evaluating the requirement `&hashbrown::set::HashSet<_, _>: std::ops::Sub`
  --> src\main.rs:28:5
   |
28 |     f1(&a);
   |     ^^
   |
   = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
   = note: required because of the requirements on the impl of `std::ops::Sub` for `&Point2d<hashbrown::set::HashSet<_, _>>`
   = note: required because of the requirements on the impl of `std::ops::Sub` for `&Point2d<Point2d<hashbrown::set::HashSet<_, _>>>`
   = note: required because of the requirements on the impl of `std::ops::Sub` for `&Point2d<Point2d<Point2d<hashbrown::set::HashSet<_, _>>>>`
   = note: required because of the requirements on the impl of `std::ops::Sub` for `&Point2d<Point2d<Point2d<Point2d<hashbrown::set::HashSet<_, _>>>>>`

This program doesn't even use HashSet.

rustc 1.36.0-nightly (d628c2e 2019-05-05)
binary: rustc
commit-hash: d628c2e
commit-date: 2019-05-05
host: x86_64-pc-windows-msvc
release: 1.36.0-nightly
LLVM version: 8.0

[jonas-schievink]

Wat. Nominating. HashSet isn't even using the Add or Sub trait.

[jonas-schievink]

In Rust 1.12.0 it displays BTreeSet instead:

error[E0275]: overflow evaluating the requirement `_: std::cmp::Ord`
  --> test.rs:20:5
   |
20 |     f1(&a);
   |     ^^
   |
   = note: consider adding a `#![recursion_limit="128"]` attribute to your crate
   = note: required because of the requirements on the impl of `std::ops::Sub` for `&std::collections::BTreeSet<_>`
   = note: required because ...
   ...

[nikomatsakis]

The diagnostics are poor -- but the error is probably real. The trait solver is basically trying hard to find some type for T that it can use, and it's substituting with types from impls that it finds (including, I suppose, one for hashset). At least that's my guess. I'm going to mark this as P-medium.

triage: P-medium

[oli-obk]

Diagnostics triage: not really a diagnostics issue per se, but a trait solver issue. Marking as hard.

[dhardy]

and it's substituting with types from impls that it finds

I have a simpler example of the same thing. This time it's obvious what's wrong: repeatedly taking a & reference does not make the type &mut. (Replacing f(&mut self) with f(&self) fixes.) But the error message is quite poor, to the point that it's unclear that trying to call data.f() is the issue. (This code also checks clean but fails to build, like #56711.)

use std::ops::Deref;

pub trait X {
    fn f(&mut self);
}

impl<T> X for [T] {
    fn f(&mut self) {}
}

impl<T: X + ?Sized> X for &T {
    fn f(&mut self) {
        self.deref().f()
    }
}

const DATA: &[u8] = &[0, 1];

fn main() {
    let mut data: &'static [u8] = DATA;
    data.f();
}

Output:

error[E0275]: overflow evaluating the requirement `&[u8]: X`
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`filter_list`)
note: required because of the requirements on the impl of `X` for `&&[u8]`
  --> examples/filter-list.rs:17:21
   |
17 | impl<T: X + ?Sized> X for &T {
   |                     ^     ^^
   = note: 128 redundant requirements hidden
   = note: required because of the requirements on the impl of `X` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[u8]`