Days ago I was trying to implement a function that is able to polymorphize over its return type. The solution is simple but at that time I failed to catch up with the answer and got a long way around. I struggled to fight with some complex typing tricks for hours, and coincidently, I encountered a bug of trait bound promotion in current Rust compiler implementation (not sure the statement is appropriate). The story, although acts as a wrong introduction for doing polymorphism, is quite interesting and I would like to share it here.

Say we are going to write a function that computes a hash value from a given &[u8] slice. The function would return a u64 or u128 as the hash value, and for either case, a completely different algorithm is adopted. This trivially can be done by writing two functions get_hash_u64() and get_hash_u128(), but I would like it to have a single and unified interface. Concretely, I am expecting a function with the following signature and behavior

fn get_hash<T>() -> T { todo!() }
// get_hash<u64>() returns 42u64
// get_hash<u128>() returns 4242u128

For brevity I will omit the input argument of type &[u8] in the following text, as it’s irrelavant to our problem. Instead, the function returns different values with respect to different T as an emulation of adopting different hashing algorithms.

The Simple Answer

I will put a simple and straight-forward solution at the front, in case of anybody taking the same wrong way as me.

Specifically, we can define a trait, say HashVal, to be the set of types that can act as the return type of our hashing function. After then, we implement HashVal for type u64 and u128, where the concrete algorithm is invoked. The code would look like this

trait HashVal: Sized {
fn digest() -> Self;
}

impl HashVal for u64 {
fn digest() -> Self { 42u64 }
}

impl HashVal for u128 {
fn digest() -> Self { 4242u128 }
}

fn get_hash<T>() -> T {
T::digest()
}

Now the user is able to select a different algorithm by writing code like get_hash<u64>().

This solution, however, did not jump into my mind at that time. I alternatively spent way more time on a complicated one, during which I touched some weakness of the current Rust compiler.

The Complicated Answer

In this version, I first declare a dummy struct Hasher. The struct implements a trait HashDispatcher<T>, where I wish different algorithm is invoked for different T

type Hasher;

trait HashDispatcher<T> {
fn digest() -> T;
}

impl HashDispatcher<u64> for Hasher {
fn digest() -> u64 { 42u64 };
}

impl HashDispatcher<u128> for Hasher {
fn digest() -> u128 { 4242u128 };
}

The function get_hash<T>() is supposed to delegate the calling to <Hasher as HashDispatcher<T>>::digest(). The casting, however, can not be made, unless a trait bound is added for the type variable T:

fn get_hash<T>() -> T where Hasher: HashDispatcher<T> {
Hasher::digest()
}

get_hash() works now. But we’ve got a lot of verbosity, because the bound where Hasher: HashDispatcher<T> must also be satisfied in every caller of the function.

In order to eliminate the boilerplates, I was seeking to write another trait, say also HashVal, such that $$\text{T: HashVal} \Rightarrow \text{Hasher: HashDispatcher<T>}$$. If achieved, the signature of get_hash can be largely simplified to

fn get_hash<T: HashVal>() -> T;

which is neat and easy to write.

The Incorrect Attempt for HashVal

At first glance, I tried by impl HashVal for any type T that satisfied the bound

trait HashVal {};
impl<T> HashVal for T where Hasher: HashDispatcher<T> {}

This, however, does not compile, since it delivers a different implication that converses with what we expect $$\text{T: HashVal} \Leftarrow \text{Hasher: HashDispatcher<T>}$$. Thank u/schungx for pointing out in the reddit thread. As a counter-example, one is able to write another impl without any bound

impl HashVal for String {}

The bound String: HashVal is satisfied, but it apparently does not imply Hasher: HashDispatcher<String>.

The Correct yet Bugged Attempt

u/SkiFire13 mentioned that the trait bound should be placed at the definition of HashVal to meet my requirement like this

trait HashVal where Hasher: HashDispatcher<Self> {}

I have never seen a where clause appears in a trait definition before. The syntax is not introduced by “The Book”, but rather mentioned in the RFC of where clause. In fact, the “supertrait” bound can be regarded as specialized version of “where” bound

trait Foo: Bar {}  // is equivalent to
trait Foo where Self: Bar {}

In our case, the where clause grants an upper bound for HashVal – any type T implements HashVal should advancedly satisfies Hasher: HashDispatcher<T>, which is precisely our requirement.

However, this still doesn’t work, due to the deficiency of current compiler. A long discussion “where clauses are only elaborated for supertraits, and not other things” can be found on Github back in 2015. In short words, the bounds in where clause will be respected within the trait definition (so that some type-checks in the trait can pass), but not promoted in other places.

trait HashVal: Sized where Hasher: HashDispatcher<Self> {
fn foo() -> Self {
// this works, the "where" bound permits the casting
<Hasher as HashDispatcher<Self>>::digest()
}
}
impl<T: Sized> HashVal for T where Hasher: HashDispatcher<T> {}

// this fails, the bound is not promoted
fn get_hash<T: HashVal>() -> T {
Hasher::digest()
}

If the trait is used for type-check somewhere else, its bounds should also be repeated there. This is currently inevitable, but might be improved in the future.