Trait impls from where clauses (ParamEnv) take precedence over freestanding trait impls

[hanna-kruppe]

I stumbled upon this trying to write a function that generically takes a range (or something else with which str can be indexed), and slices a str with that range. I got that to work, this bug comes into play when the str is produced by slicing another string with a RangeFrom or another concrete type (in the same function).

Here's a simpler (no lifetimes, no associated types) and self-contained example (playpen):

trait Frobnicate<I> {
    fn frob(&self, i: I) -> Self;
}

struct Thing;

struct IA;
struct IB;

impl Frobnicate<IA> for Thing {
    fn frob(&self, _i: IA) -> Thing { Thing }
}

impl Frobnicate<IB> for Thing {
    fn frob(&self, _i: IB) -> Thing { Thing }
}

fn delegate_frob<I>(t: Thing, i: I) -> Thing
        where Thing : Frobnicate<I> {
    let t2: Thing = t.frob(IA);
    t2.frob(i)
}

fn main() {}

This seems innocent enough. There's a impl Frobnicate<IA> for Thing, so the .frob(IA) call should work, and it's known to return Thing again, so via the where clause the .frob(i) call is good as well. However, I get this error message:

<anon>:20:28: 20:30 error: mismatched types:
 expected `I`,
    found `IA`
(expected type parameter,
    found struct `IA`) [E0308]
<anon>:20     let t2: Thing = t.frob(IA);
                                     ^~

It appears that the where clause makes the compiler forget that there are other impls.
Adding a Thing : Frobnicate<IA> bound only makes the compiler (rightly) complain that that's not a bound at all, since it doesn't involve any type parameters.
UFCS makes it compile, though:

    let t2: Thing = <Thing as Frobnicate<IA>>::frob(&t, IA);

Edit: Besides playpen, I can also reproduce this locally:

rustc 1.0.0-beta (9854143cb 2015-04-02) (built 2015-04-02)
binary: rustc
commit-hash: 9854143cba679834bc4ef932858cd5303f015a0e
commit-date: 2015-04-02
build-date: 2015-04-02
host: x86_64-pc-windows-gnu
release: 1.0.0-beta

But I already noticed it a couple of weeks ago, so it can't be a recent regression.

[bluss]

@nikomatsakis Is this not a bug? It seems to be the feature that was discussed in #33108 of lifting trait methods to inherent methods.

[nikomatsakis]

I would say this is... a grey area. Perhaps a known shortcoming would be the best description. The trait selection algorithm definitely prefers where clauses to impls when there is inference involved -- this often is crucial to making progress, but here creates a problem. You could probably workaround it by adding some (redundant) where-clauses like where Thing : Frobnicate<IA>, but that shouldn't be necessary. I'm not sure though of the best way to improve the trait selection algorithm to circumvent this problem.

[rocallahan]

Here's a simple example of what I think is the same bug:

fn f<V>(_: V) -> String where String: From<V> { String::from("hello") }

This is definitely a problem.

[Mark-Simulacrum]

The example in the issue description now compiles. Closing.

[Mark-Simulacrum]

Not again, I tested in the wrong directory. Re-opening....

[dhardy]

"Me too" — play example — forum.

[Pzixel]

Small example to illustrate the problem (I do velieve it caused by the same bug):

fn f<V>(_: V) -> String
where
    String: From<V>,
{
    From::from("Hello")   // works
    String::from("Hello") // doesn't work
}

playground

[Globidev]

One thing I noted while investigating a related issue also applies to @Pzixel's example above, where adding another trait bound can fix the problem in strange ways. The type parameter of the generic trait in the extra bound can be another generic type parameter or an HRTB with a concrete type, but not another concrete type.
Also in this specific case with String and From it cannot even be the expected concrete type for some reason. And I can't reproduce the behavior with either a local trait or a local type

Here is more (confusing) food for thought as of 1.55.0-nightly (2021-07-12 955b9c0d4cd9176b53f5) :
playground link

fn ok_with_another_bound_generic<V, W>() -> String
where
    String: From<V> + From<W>,
{
    String::from("✅")
}

fn nok_with_another_bound_concrete<V>() -> String
where
    String: From<V> + From<char>,
{
    String::from("❌")
}

fn ok_with_another_bound_concrete_hrtb<V>() -> String
where
    String: From<V> + for<'a> From<&'a String>,
{
    String::from("✅")
}

fn nok_with_another_bound_concrete_expected_type<V>() -> String
where
    String: From<V> + From<&'static str>,
{
    String::from("❌")
}

fn ok_with_another_bound_concrete_expected_type_local_trait<V>() -> String
where
    String: MyFrom<V> + MyFrom<&'static str>,
{
    String::my_from("✅")
}

fn ok_with_another_bound_concrete_expected_type_local_type<V>() -> MyString
where
    MyString: From<V> + From<&'static str>,
{
    MyString::from("✅")
}

trait MyFrom<T> { fn my_from(_: T) -> Self; }
impl<T> MyFrom<T> for T { fn my_from(x: T) -> Self { x } }
impl MyFrom<&str> for String { fn my_from(c: &str) -> Self { c.into() } }

struct MyString;
impl From<&str> for MyString { fn from(_: &str) -> Self { MyString } }