Duplicate defininitions with different trait bounds

Question

I'm implementing a heap and would like to implement two heapify functions, where one is used if the generic types are Copy:

// K - Key, V - Value
struct Heap<K, V> { ... }

impl<K, V> Heap<K, V>
where
    K: Ord,
{
    fn heapify(...) { ... }
}

impl<K, V> Heap<K, V>
where
    K: Ord + Copy, // NOTE: extra Copy bound
    V: Copy,
{
    fn heapify(...) { ... }
}

However, I get the following error:

E0592: duplicate definitions with name heapify.

Is there a way around this?

Answer 1

As the error message suggests, this can't be done directly due to conflicting impls. One way out of this can be using specialization, but this requires a nightly compiler. Another way is to (ab)use autoref during method resolution to get what you want, although this comes with some tradeoffs.

The idea behind using autoref is that the compiler will consider possible candidates for method resolution at the current level of indirection first, and - if no suitable candidates are found - add levels of indirection and try again. That is, if the method foo.bar() can't be called on some foo: Foo, the compiler will consider automatically referencing Foo to &Foo in order to call bar(). We can use that to our advantage.

The following example will use the :Copy-specialized impls on the first and third example, and use the generic impl on the String-version.

use std::marker::PhantomData;

#[derive(Default, Clone, Copy)]
struct Heap<K, V> {
    _k: PhantomData<K>,
    _v: PhantomData<V>,
}

trait Heapify {
    fn heapify(&self);
}

// Always applies, yet `heapify()` will be called
// with a `&&Heap`: This generic impl is purposefully
// hidden behind one layer of referencing.
impl<K, V> Heapify for &Heap<K, V>
where
    K: Ord,
{
    fn heapify(&self) {
        println!("Generic fallback")
    }
}

trait CopyHeapify {
    fn heapify(&self);
}

// Only applies to :Copy types, but applies before
// autoref kicks in during method resolution.
impl<K, V> CopyHeapify for Heap<K, V>
where
    K: Ord + Copy,
    V: Copy,
{
    fn heapify(&self) {
        println!("Specialized on :Copy")
    }
}

fn main() {
    // The first and third example will trigger clippy warnings
    // due to the useless borrowing of `&Heap`. Kept for consistency
    // as the second example _requires_ to be called on `&Heap`.

    // This `.heapify()` resolves to `CopyHeapify::heapify()`,
    // as the bounds are met, and we match the right "level"
    // of referencing. So `CopyHeapify` is used, and `Heapify`
    // is not even considered.
    (&Heap::<i32, i32>::default()).heapify();
    
    // This `.heapify()` resolves to `Heapify::heapify()`.
    // `CopyHeapify` can't be considered due to unsatisfied
    // bounds. As this level of referencing, method resolution
    // runs out of options, so autoref kicks in; `Heapify`
    // applies at one extra level of indirection, and the trait
    // bounds are met, so use that.
    (&Heap::<i32, String>::default()).heapify();
    
    // `CopyHeapify` again...
    (&Heap::<(), i32>::default()).heapify();
}

On the plus side, we got what we wanted. On the minus side, you probably want to use a macro the wrap the method call, in order to locally suppress the clippy warning, which is triggered by the - sometimes useless - extra reference introduced to make this work; while this sort-of-I-cant-believe-its-not-butter works, you may or may not be hard-pressed to gain much quality of life improvements from this approach, depending on why you need this. A fn heapify_copied<K: Copy, V: Copy>(&self) is usually simpler to understand...