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() {}

[nikomatsakis]

This is perhaps a dup of #19032 --- have to read more deeply

[spaolacci]

I can't say for sure if this the same situation (and I don't want to polute useless issues), but the following code reports a "conflicting implementations of trait Convert for type f64" while the two constraints do not overlap (i64 doesn't implement From<f64>).

trait Convert {
    fn convert(&self) -> i64;
}

impl<T> Convert for T
    where T: Copy,
          i64: From<T>
{
    fn convert(&self) -> i64 {
        i64::from(*self)
    }
}

impl Convert for f64 {
    fn convert(&self) -> i64 {
        unsafe { std::mem::transmute(*self) }
    }
}

[arielb1]

now it is https://github.com/rust-lang/rust/blob/1.10.0/src/librustc/traits/select.rs#L652

[arielb1]

With the orphan rules, anyone can implement FromStr<MyType> for User and cause overlap.

[nikomatsakis]

So, I believe the orphan check is doing the right thing here. The danger is that a downstream crate might do something like:

struct Foo;
impl FromSql<Foo> for User { }

which they are legally able to do, for better or worse.

One solution here would be to adopt one of the negative impl proposals (such as what I describe in this gist]) that would permit impl<T> !FromSql<T> for User, which presumably coherence could then make use of.

[nikomatsakis]

Another solution that @aturon and I considered at some point but rejected is to implicitly derive the fact that the impls in the parent crate are only consistent if !FromSql<T> for User, but it seemed like this ultimately led to a real complexity problem, since every downstream crate would have to re-check all impls from upstream crates for independence, leading to an O(n^2) computation where n is the set of impls in your crate and all parent crates. Not good.

[nikomatsakis]

Also, I think this is definitely a dup of #19032.

[nikomatsakis]

Closing as dup of #19032.

[sgrif]

@nikomatsakis I'm fine with closing as a dup, but based on your example shouldn't the blanket impl for From be illegal as well?

[nikomatsakis]

@sgrif

...based on your example shouldn't the blanket impl for From be illegal as well?

I guess you mean an impl like the following?

impl<T,U> Into<T> for U where T: From<U>

This impl is allowed, but only in the crate that defines the trait Into. It is true that downstream creates could, according to the orphan rules alone, define an overlapping impl like:

struct Foo;
impl<T> Into<T> for Foo { .. }

but they would also be required to prove this impl is disjoint from the impls in the crate where Into is defined (this is the overlap check).

In other words, the crate that defines the trait has the ability to define blanket impls of that kind, since any other crate that might overlap would be able to detect the overlap easily enough.

[sgrif]

I think I misunderstood #30191 (comment). It assumes that there's a crate further downstream. Shouldn't we be able to omit that assumption for binary projects, or for types which are not public?

[nikomatsakis]

Shouldn't we be able to omit that assumption for binary projects, or for types which are not public?

We have not (currently) drawn any distinction between binary / library projects. I am reluctant to do so -- it seems to create refactoring hazards where you expose a binary as a library and so forth. But at the same time it seems clear that a number of coherence issues go away for binary projects -- so maybe there is a good way to handle these "at most once" decisions.

Regarding privacy, that's another thing that coherence doesn't currently consider, but yes I could imagine taking it into account.

[sgrif]

👍 Thanks for clarifying