Can I avoid eager ambiguity resolution for trait i

Question

Consider the following Rust code [playground]:

use std::collections::HashMap;
use std::hash::Hash;

trait Foo<K> {
    const FOO: i32;
}

impl<K, K_, V> Foo<HashMap<K_, V>> for HashMap<K, V>
where
    K: Hash + Eq + Into<K_>,
{
    const FOO: i32 = 1;
}

impl<K, V, V_> Foo<HashMap<K, V_>> for HashMap<K, V>
where
    K: Hash + Eq,
    V: Into<V_>,
{
    const FOO: i32 = 2;
}

fn main() {}

(The const is not relevant, I'd like the code to compile with fns too).

It fails to compile with the error:

error[E0119]: conflicting implementations of trait `Foo<std::collections::HashMap<_, _>>` for type `std::collections::HashMap<_, _>`:
  --> src/main.rs:15:1
   |
8  | / impl<K, K_, V> Foo<HashMap<K_, V>> for HashMap<K, V>
9  | | where
10 | |     K: Hash + Eq + Into<K_>,
11 | | {
12 | |     const FOO: i32 = 1;
13 | | }
   | |_- first implementation here
14 | 
15 | / impl<K, V, V_> Foo<HashMap<K, V_>> for HashMap<K, V>
16 | | where
17 | |     K: Hash + Eq,
18 | |     V: Into<V_>,
19 | | {
20 | |     const FOO: i32 = 2;
21 | | }
   | |_^ conflicting implementation for `std::collections::HashMap<_, _>`

As I understand it, the problem is that there is an ambiguity here - which implementation should be picked if both are legal? Ideally I'd like to have the following:

1. The above code (or some work around) should compile fine.
2. At the call site, if there is only one impl possible for the given type, then that one is picked.
3. At the call site, if there are multiple impls possible, then it is an error (coherence issues).

More succinctly, I want ambiguity resolution to be done at the call site, rather than at the definition site. Is it possible to have this behavior?

Answer 1

Can I avoid eager ambiguity resolution for trait implementations with generics?

No.

Is it possible to have [ambiguity resolution to be done at the call site, rather than at the definition site]?

No.

---

There's a (long-delayed) RFC for specialization that will allow overlapping trait implementations, but only when one of them is more specific than the others. I don't believe this is true for your case, so it would not help.

See also:

• Conflicting implementations of trait in Rust
• Why do I get "conflicting implementations of trait" for f32 which does not implement Ord?
• Why do I get a conflicting implementations error when specializing a trait?
• How is there a conflicting implementation of `From` when using a generic type?

Answer 2

There is, in fact, a trick you may be able to apply here.

In order for the compiler to pick an impl for you, it has to be attached to a type parameter that can be inferred. You can add a type parameter to trait Foo and create marker structs so that the impls no longer overlap:

trait Foo<K, U> {
    const FOO: i32;
}

struct ByKeyInto;
impl<K, K_, V> Foo<HashMap<K_, V>, ByKeyInto> for HashMap<K, V>
where
    K: Hash + Eq + Into<K_>,
{
    const FOO: i32 = 1;
}

struct ByValInto;
impl<K, V, V_> Foo<HashMap<K, V_>, ByValInto> for HashMap<K, V>
where
    K: Hash + Eq,
    V: Into<V_>,
{
    const FOO: i32 = 2;
}

Since Foo<_, ByKeyInto> and Foo<_, ByValInto> are different traits, the impls no longer overlap. When you use a generic function that requires Foo<_, U> for some U, the compiler can go looking for a type that works, and it does resolve to a concrete type if there is provably only one possibility.

Here's an example of code that compiles and infers the correct impl at each call site by picking ByKeyInto or ByValInto for U:

fn call_me<T, U>(_: T)
where
    T: Foo<HashMap<String, i32>, U>,
{
    println!("{}", T::FOO);
}

fn main() {
    let x: HashMap<&str, i32> = HashMap::new();
    call_me(x);
    let y: HashMap<String, bool> = HashMap::new();
    call_me(y);
}

This prints (playground):

1
2

---

However, since Into is reflexive (that is, T implements Into<T> for all T), this is awkward if you want to use Foo<HashMap<K, V>> for HashMap<K, V>. Since there are overlapping impls in this case, you have to choose one by turbofish (::<>).

let z: HashMap<String, i32> = HashMap::new();
call_me::<_, ByKeyInto>(z);  // prints 1
call_me::<_, ByValInto>(z);  // prints 2