4

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?

typesanitizer
  • 2,505
  • 1
  • 20
  • 44
  • Can a single implementation be even chosen in your example? You ask for two implementations of the same trait for the same class, they overlap, and neither looks more specific than the other. Am I missing anything? – 9000 Sep 11 '18 at 17:29
  • @9000 Suppose `V` and `K` have some concrete types such that (a) there is no `Into` for `K` and (b) there is a unique `V_` such that `V: Into`, then the second one should be picked. – typesanitizer Sep 11 '18 at 17:33
  • Can you provide an example of how this would be used? I know there are workarounds for some problems like this one, but I don't know whether they would work for your case or not. – trent Sep 11 '18 at 20:20
  • @trentcl I was playing around with coercions, where you may want to "coerce through" either parameter. The code is quite similar to this (well not now, because this doesn't work), except with a bunch of more trait constraints. If it doesn't work here, then it won't work there. – typesanitizer Sep 11 '18 at 22:32
  • Maybe I should rephrase. In your ideal situation, where the code here is replaced with (some workaround), what does the call site look like? Can you write a test that would pass if this code did compile? – trent Sep 12 '18 at 02:37

2 Answers2

3

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:

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
  • Are there any particular soundness/modularity related issues with this? Some educated guesses would be very helpful in understanding the status quo. I had a look at the linked questions but I fail to see how the points made there apply here. My question doesn't involve overlapping impls, and no one downstream can define `impl<..> Foo<..> for HashMap<..>`. – typesanitizer Sep 11 '18 at 17:44
3

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
Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
trent
  • 25,033
  • 7
  • 51
  • 90