Can't provide non-overlapping impls with *any* type parameters, if a blanket impl exists

[sgrif]

use std::convert::Into;

struct Foo;

impl<T> Into<T> for Foo where T: From<String> {
    fn into(self) -> T {
        "foo".into()
    }
}

fn main() {}

This fails due to the blanket impl on Into for From in libcore, even though Foo does not implement From.

Possibly related to, but appears to be distinct from #20400 and #23341

[sgrif]

So I've spent a bit of time poking at this, and ultimately the type parameter is being treated as ambiguously fulfilling the obligation here: https://github.com/rust-lang/rust/blob/e9ac440/src/librustc/middle/traits/select.rs#L560-L590

While this example gets more interesting when you consider that the same code can be written as where String: Into<T>, which makes this even more obviously unambiguous, I think the example in the comment there is much easier to reason about. impl<T: Eq> Eq for Vec<T>. We are saying this is ambiguous, because when trying to evaluate whether _: Eq, we will eventually try to determine if Vec<_>: Eq, and recurse.

However, this seems like it's actually easy to disambiguate. An impl can never overlap with itself. We can safely ignore that obligation. (I'm likely conflating the concepts of an obligation being fulfilled with traits overlapping. I'm not sure how separate those are meant to be in the compiler).

Anyway, I'm fiddling with some changes to try and see if we can simply ignore the ambiguity when the candidate is where we started from, though I'd love to know if this sounds like it's on the right track.

[arielb1]

@sgrif

This is not, in fact, a bug. Any sibling dependency could define the following struct:

#![feature(optin_builtin_traits)]

trait Marker {}
impl Marker for .. {}
impl !Marker for Bar {}

struct Bar;
impl<T: Marker> From<T> for Bar { fn from(_: T) -> Self { Bar } }

In that case, both Bar: From<String> and Bar: From<Foo> would hold, so there will be a true impl conflict for Foo: Into<Bar>. As we want to always preserve crate linkability, your impl must not be allowed.

[sgrif]

@arielb1 Yes, it appears the specific example I gave is unsound, I was trying to get something that I could throw on playground. The problem still exists in cases that cannot be mucked up by sibling crates. Here's a simplified version of the actual case that I'm running into this, which I'm fairly certain could not be made ambiguous by sibling crates.

use std::error::Error
trait NativeSqlType;
struct Row;

pub trait FromSql<A: NativeSqlType>: Sized {
    fn from_sql(bytes: Option<&[u8]>) -> Result<Self, Box<Error>>;
}

pub trait FromSqlRow<A: NativeSqlType>: Sized {
    fn build_from_row(row: &mut Row) -> Result<Self, Box<Error>>;
}

impl<ST, T> FromSqlRow<ST> for T where
    ST: NativeSqlType,
    T: FromSql<ST>,
{
    fn build_from_row(row: &mut Row) -> Result<Self, Box<Error>> {
        // ...
    }
}

Now in a separate crate, I am unable to write this impl:

struct User {
    id: i32,
    name: String,
}

impl<ST> FromSqlRow<ST> for User where
    ST: NativeSqlType,
    (i32, String): FromSqlRow<ST>
{
    fn build_from_row(row: &mut Row) -> Result<Self, Box<Error>> {
        let (id, name) = try!(<(i32, String) as FromSqlRow<ST>>::build_from_row(row));
        Ok(User {
            id: id,
            name: name,
        })
    }
}

The only way this can ever become ambiguous is for another crate to create a blanket impl for a trait it does not control (disallowed).

[arielb1]

@sgrif

Our trait checker uses an older, less-conservative version of the orphan rules. That might be it.

[arielb1]

cc @nikomatsakis

[arielb1]

For reference, the problem is the check at https://github.com/rust-lang/rust/blob/master/src/librustc/middle/traits/select.rs#L587. It was introduced before the is_knowable rules and is redundant with them in a potentially harmful way. Should we remove it?

[arielb1]

tagging so this does not get lost.

[arielb1]

For the record, a full example that is broken:

struct Row;

pub trait FromSql<A> {}

pub trait FromSqlRow<A> {
    fn foo(&self);
}

impl<ST, T> FromSqlRow<ST> for T where
    T: FromSql<ST>,
{
    fn foo(&self) {}
}

struct User;

impl<ST> FromSqlRow<ST> for User where
    (i32, String): FromSqlRow<ST>
{
    fn foo(&self) {}
}

fn main() {}