overlap check fails to prevent overlap

[nikomatsakis]

While writing a blog post exploring #23086, I found a bug in the overlap checker. I haven't decided yet on the best fix here, but these two files should yield an error somewhere (currently, compiling crate2.rs ICEs due to ambiguity):

// crate1.rs
#![crate_type="rlib"]

pub trait Sugar { fn dummy(&self) { } }
pub trait Sweet { fn dummy(&self) { } }
impl<T:Sugar> Sweet for T { }
impl<U:Sweet> Sweet for Box<U> { }

I was surprised that this crate passed the overlap check, but it does. In particular, the overlap checker considers Box<$0>: Sugar to be unimplemented. I think this was due to me tightening the rules a bit too much on how it treats unbound variables. The problem is that now one can come from another crate and implement both Sugar and Sweet to cause ambiguity:

// crate2.rs
extern crate crate1;
use crate1::{Sugar, Sweet};

struct Cube;
impl Sugar for Box<Cube> { }
impl Sweet for Cube { }

fn foo<T:Sweet>() {
}

fn main() {
    foo::<Box<Cube>>();
}

Possibly the fix is to tighten the overlap checker on crate1, but I'm not sure of the fallout from that. Another option is to widen the overlap search in crate2, potentially.

cc @aturon
cc @arielb1 (this will interest you I'm sure)

[nikomatsakis]

triage: P-backcompat-lang (1.0 beta)

[nikomatsakis]

Related to #19032. In that case, the coherence checker is (correctly, but annoyingly) defending against this scenario.

[nikomatsakis]

I tried the naive fix here. It breaks a lot of code. Example:

impl<'a, T> IntoIterator for &'a [T; $N]
impl<T:Iterator> IntoIterator for T

are considered to conflict. The reason is that we can't know that some sicko didn't do (or won't do)

struct MyStruct;
impl<'a> Iterator for &'a [MyStruct; 22]

[nikomatsakis]

A variation on a theme. This one causes a similar failure but with only one of the two traits being implemented in the downstream crate:

// crate1
#![crate_type="rlib"]

pub trait Sugar { fn dummy(&self) { } }
pub trait Sweet { fn dummy(&self) { } }
impl<T:Sugar> Sweet for T { }
impl<U:Sugar> Sweet for Box<U> { }

// crate2
extern crate crate1;
use crate1::{Sugar, Sweet};

struct Cube;
impl Sugar for Box<Cube> { }
impl Sugar for Cube { }

fn foo<T:Sweet>() {
}

fn main() {
    foo::<Box<Cube>>();
}