A Flaw of Promoting Complex Trait Bounds in Rust

Days ago, for some reason, I was trying to implement a function that can polymorphize over its return type. The solution is simple, but my brain was jammed at that time, trapped in some complicated typing tricks for hours.

During the struggling, I coincidently ran into something that is temporarily a flaw in the current Rust compiler implementation. In some cases, the compiler is not smart enough to promote known trait bounds, and we have to replicate them again and again. Although the problem is afterwards proved to be a useless “X-Y Problem”, I would still like to share the story.

The Problem

Let’s say we are going to write a function that digests a given &[u8] slice and computes a hash value. The function would adopt either of two different algorithms, and a u64 or u128 integer is returned as the hash result.

Trivially, this can be achieved by splitting into two functions get_hash_u64() and get_hash_u128(). But I prefer to have a single and unified interface, so concretely, I am expecting a function to polymorphize over its return type, with the following signature

fn get_hash<T>(b: &[u8]) -> T
    where /* some bounds on T */
{ todo!() }

Two things I should fill in for the above snippet

1. The where-clause. Some trait bounds might be satisfied for typevar T, and I expect them to be as concise as possible in order for less verbosity in callers.
2. The body. The function should behave differently regarding different typevar T.

In order to emulate the effect of choosing different hashing algorithm, we expect a different numeric value be returnedwhen different typevar T supplied. Also, since the argument b: &[u8] is irrelavant to our problem, I will omit it in the following text for brevity. So overall, I would like the two assertions to be held

assert_eq!(get_hash::<u64>(), 42u64);
assert_eq!(get_hash::<u128>(), 4242u128);

The Simple Answer

Before stepping far, I will place a simple and straight-forward solution at the front, in case of anybody taking the same wrong path.

Specifically, we can define a trait, say HashVal, as the upper bound of all possbile return types for get_hash.

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

For each possible type such as u64 or u128, we place corresponding hashing algorithm in HashVal::digest

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

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

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

get_hash<T>() is now polymorphized over return type T. User might select a 64-bit hashing algorithm via a calling like get_hash::<u64>().

This solution is neat and, most importantly, the prerequisite T: HashVal is concise and self-explained, which saves a lot of verbosity in callers’ where-clause. However, this didn’t come to my mind at that time. I alternatively choose a more complicated solution.

The Complicated Answer

In this version, I start by a dummy struct Hasher and a trait HashDispatcher<T>.

type Hasher;

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

The struct Hasher implements HashDispatcher<T> for different type T with corresponding algorithm filled in digest() method

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

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

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

Function get_hash<T>() delegates the calling to Hasher::digest(), which requires a verbose trait bound Hasher: HashDispatcher<T>. In order to reduce the boilerplate, I was seeking to write another trait, named also HashVal, such that for all T being a HashVal, the trait bound Hasher: HashDispatcher<T> holds, or formally $$\text{T: HashVal} \Rightarrow \text{Hasher: HashDispatcher<T>}$$. If achieved, the signature of get_hash can be largely deduced into

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

The Incorrect Attempt for HashVal

The first attempt I made was to place the bound in the where-clause of a generic impl

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

I mistakenly thought this would fulfill my purpose. The statement instead should read as “for every T that satisfies Hasher: HashDispatcher, T is a HashVal”, which delivers a different implication that converses to what I expect. Thank u/schungx for pointing out in the reddit thread. As a counter-example, one is able to impl other types as HashVal, while without ensuring them to satisfy my bound

impl HashVal for String {}

The Correct yet Flawed 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 no memory of seeing a where clause in the trait definition before. The syntax is not introduced by “The Book”, but rather mentioned in the RFC of where clause.

where-clause for trait is not a new concept. In fact, the “supertrait” bound can be regarded as a specialized version of where-style bound

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

More generally, the where-clause is used to elaborate the constraints that the typevars (or the special Self) should satisify. If SomeT: Trait holds, type SomeT should meet all the requirements in Trait‘s where-clause.

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

With this declaration, however, we still cannot deduce the trait bound of get_hash to T: HashVal, due to the flaw 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, except from some simple constraints like supertraits, the constraints in where-clause will only be respected within the trait definition (to ensure some type-checks in the trait can pass), but not be promoted in other places.

trait HashVal: Sized where Hasher: HashDispatcher<Self> {
    fn foo() -> Self {
        // OK. 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()
}

The flaw is quite annoying. We still have to replicate the verbose trait bounds here and there. Hopefully it can be fixed in the future.

Author: hsfzxjy.
Link: .
License: CC BY-NC-ND 4.0.
All rights reserved by the author.
Commercial use of this post in any form is NOT permitted.
Non-commercial use of this post should be attributed with this block of text.