Multiple related traits as one trait. (where <T as _>::_)

The problem I have is that I can't seem to figure out how to create one trait that allows UpperHex trait created from Digest output.

A simpler version of what I want to do: I want to allow hash algorithms were the upper hex values trait is supported.

Here is an example of a function that takes a hash algorithm (digest crate) and prints the upper hex value.

use digest::{generic_array::ArrayLength, Digest, OutputSizeUser};
use std::{fmt::UpperHex, ops::Add};

fn main() {}

// Can write a funciton like this
pub fn print_upper_hex<D: Digest>()
where
    // needed for UpperHex trait.
    <D as OutputSizeUser>::OutputSize: Add,
    <<D as OutputSizeUser>::OutputSize as Add>::Output: ArrayLength<u8>,
{
    // create hash
    let mut hasher = D::new();
    hasher.update(b"Hello world!");
    let hash = hasher.finalize();

    // This works
    println!("{:X}", hash);
}

But now I have to write the where clause everywhere, where it is needed. So I want to make one trait that does the same:

pub trait CanUpperHex
where
    Self: Digest + UpperHex,
    <Self as OutputSizeUser>::OutputSize: Add,
    <<Self as OutputSizeUser>::OutputSize as Add>::Output: ArrayLength<u8>,
{
}
impl<T> CanUpperHex for T
where
    Self: Digest + UpperHex,
    <Self as OutputSizeUser>::OutputSize: Add,
    <<Self as OutputSizeUser>::OutputSize as Add>::Output: ArrayLength<u8>,
{
}

And so I want to recreate the print_upper_hex function with the CanUpperHex trait:

pub fn print_upper_hex_2<D: CanUpperHex>() {
    // create hash
    let mut hasher = D::new();
    hasher.update(b"Hello world!");
    let hash = hasher.finalize();

    // Doesn't work / compile
    println!("{:X}", hash);
}

But this doesn't work.
Terminal output:

error[E0277]: cannot add `<D as OutputSizeUser>::OutputSize` to `<D as OutputSizeUser>::OutputSize`
  --> src/main.rs:48:29
   |
48 | pub fn print_upper_hex_2<D: CanUpperHex>() {
   |                             ^^^^^^^^^^^ no implementation for `<D as OutputSizeUser>::OutputSize + <D as OutputSizeUser>::OutputSize`
   |
   = help: the trait `Add` is not implemented for `<D as OutputSizeUser>::OutputSize`
note: required by a bound in `CanUpperHex`
  --> src/main.rs:34:43
   |
31 | pub trait CanUpperHex
   |           ----------- required by a bound in this
...
34 |     <Self as OutputSizeUser>::OutputSize: Add,
   |                                           ^^^ required by this bound in `CanUpperHex`
help: consider further restricting the associated type
   |
48 | pub fn print_upper_hex_2<D: CanUpperHex>() where <D as OutputSizeUser>::OutputSize: Add {
   |                                            ++++++++++++++++++++++++++++++++++++++++++++

For more information about this error, try `rustc --explain E0277`.
error: could not compile `ask_upper_hex_digest` due to previous error

If I do what the terminal says, I end up with the same version as at the beginning. (only now with CanUpperHex instead of Digest)

Am I overlooking something?
Is there an other way to solve this?
I have been trying to solve this multiple times but I can't seem to figure it out and I don't know where to go from here.
Any help would be appreciated.

Bounds that aren't on Self aren't automatically carried around. We may get it some day with implied bounds.

One alternative is to build the functionality you need into the functions of your extension trait and just put the bounds on the blanket implementation:

pub trait HexableDigest: Digest {
    // Or `print_hex` or whatever functionality you want
    fn hex(_: &digest::Output<Self>) -> &dyn UpperHex;
}

impl<D: Digest> HexableDigest for D
where
    <D as OutputSizeUser>::OutputSize: Add,
    <<D as OutputSizeUser>::OutputSize as Add>::Output: ArrayLength<u8>,
{
    fn hex(d: &digest::Output<Self>) -> &dyn UpperHex {
        d
    }
}

Playground.

2 Likes

@quinedot, thank you very much for your response.
I understand now why the previous version of my program failed.
But it took me a while to fully understand the core of why your version of the program works.

Here are my thoughts and findings after thinking about it for a while.

  1. First step is to create a trait that explains with a function from which input you want to go to which output.
    Here it is important that you do not link the input and output type but leave this to the implementation.
    (because the compiler will complain for the very same reasons why you started this journey.)
pub trait MyDigestOutput: Digest {
    type Output: UpperHex;
    fn convert_output(d: digest::Output<Self>) -> Self::Output;
}
  1. The second step is to implement this trait for all the types that are supported (implement the correct traits).
impl<D: Digest> MyDigestOutput for D
where
    <D as OutputSizeUser>::OutputSize: Add,
    <<D as OutputSizeUser>::OutputSize as Add>::Output: ArrayLength<u8>,
{
    type Output = digest::Output<D>;
    fn convert_output(d: digest::Output<Self>) -> Self::Output {
        d
    }
}
  1. Third step is to use the newly created trait. You can use this trait as input bounds because only the supported types implement this trait.
    But you still have to run the function from the trait to let the compiler know that the value indeed suffices and you can do with it what you want.
fn use_my_digest_output<D: MyDigestOutput>() {
    // create hash
    let mut hasher = D::new();
    hasher.update(b"Hello world!");
    let hash = hasher.finalize();

    // This works
    println!("{:X}", D::convert_output(hash));
}

Please let me know if I got anything wrong or if there are any ways to improve this.
And hopefully this can also help somebody else out with the same problem.

That seems pretty much correct to me. The pattern is called an extension trait. The goal in this case was to not repeat bounds everywhere by getting the functionality we needed expressed in places where the bounds are automatically "elaborated". Those are:

  • Supertrait bounds (bounds on the Self implementing the trait)
  • Bounds on associated types within the trait

However I must admit in this case, there was so much abstraction that I instead treated this as another type of extension trait pattern where you want additional functionality -- the ability to produce something "hexable" from Output<Self>.

As mentioned above, I took a shortcut by using fn hex(...) -> &dyn UpperHex. There is a way to get the actual bounds in question carried around, though it's a lot of boilerplate and sort of a pain due to how many layers of abstraction are in play.

But it can be an interesting exercise so let's check it out.


Just looking at the OP and signatures, my intuition for what you want says that we would need something like

pub trait HexableDigest
where
    Self: Digest<Output = <Self as HexableDigest>::HexOutput>
{
    type HexOutput: UpperHex;
}

The somewhat odd-looking associated type equality bound is there because

  • It teaches the compiler the associated type must be the same between both traits
  • It does this in a supertrait bound that is elaborated everywhere

And then the bound on our own associated type HexOutput gives us the other properties we want.

But things can't be so simple in this case because Digest doesn't actually have an associated type Output. Output is just a type alias to some other type, based on an associated type that Digest -- or more properly, its supertrait OutputSizeUser -- does have: OutputSize.

So perhaps...

 {
     type HexOutput: UpperHex;
+    type HexOutputSize: 'static + Add<Output: ArrayLength<u8>>,
 }

But this doesn't work either, because you can't put a bound on an associated type like that.

So now we're in the same position as my intuition said before, but at a different level -- we want an Add trait that guarantees additional properties on its associated type. This time though, we can make it work.


So here's what this pattern looks like when it can actually work. First you define the extension trait:

pub trait HexAdd
where
    Self: ArrayLength<u8>,
    Self: Add<Output = <Self as HexAdd>::AddOutput>,
{
    type AddOutput: ArrayLength<u8>;
}

I've used the associated type equality bound to thread the type through, added the bound on my own associated type, and given it a distinct name to avoid clashes (though this isn't always necessary).

Then you blanket implement it for everything that meets the bounds.

impl<T: ?Sized> HexAdd for T
where
    T: ArrayLength<u8> + Add,
    <T as Add>::Output: ArrayLength<u8>,
{
    type AddOutput = T::Output;
}

Now we have enough tools to go back to the trait we actually care about:

pub trait HexableDigest: Digest
where
    // Same associated-type threading pattern as before
    Self: OutputSizeUser<OutputSize = <Self as HexableDigest>::HexOutputSize>,
{
    // Here's where we use `HexAdd` from above
    type HexOutputSize: 'static + HexAdd;
    type HexOutput: UpperHex;
}

// Blanket implementation omitted

And after that, you can use the HexableDigest bound and you won't even need the helper hex method.

1 Like

@quinedot thank you for further clarifying. I first thought that it was maybe necessary to do it in the previous way.

I have been stuck on this point for a long time, now I can go further. I am very thankful for this.

Are there any learning resources that you can recommend to learn more about this? (more advanced uses of types, traits and patterns)

To help me understand what is going on, I have tried to make some easier to understand / basic examples. I will share them for anybody that is interested. I have tried to make it easy to read.

testing where:

use std::fmt::Display;

// starting very simple
trait TestTrait01: Display {}

fn test01(input: impl TestTrait01) {
    println!("{}", input);
}

trait TestTrait02 {
    type Type02: Display;
    fn get(&self) -> Self::Type02;
}

fn test_02(input: impl TestTrait02) {
    println!("{}", input.get());
}

// Now trying with supertrait...
trait SuperTrait {
    type TypeSuper;
    fn get(&self) -> Self::TypeSuper;
}

// (this does not work how we want it)
trait TestTrait03: SuperTrait
where
    <Self as SuperTrait>::TypeSuper: Display,
{
}

fn test_03<T: TestTrait03>(input: T)
where
    // Need to add Display again to make it work!!!
    // This is not what we want.
    <T as SuperTrait>::TypeSuper: Display,
{
    println!("{}", input.get());
}

trait TestTrait04: SuperTrait
where
    Self: SuperTrait<TypeSuper = <Self as TestTrait04>::Type04>,
{
    type Type04: Display;
}

// This works!
fn test_04(input: impl TestTrait04) {
    println!("{}", input.get());
}

Here I tried to create a more similar situation to the original question, but simpler.

use std::fmt::Display;

trait SuperTrait {
    type Associated;
    // get associated type
    fn result(self) -> Self::Associated;
}

// Simple example implementation
impl<T> SuperTrait for T {
    type Associated = T;
    fn result(self) -> Self::Associated {
        self
    }
}

trait ExtendTrait
where
    Self: SuperTrait,
    // Set external associated type to 'owned' associated type
    Self: SuperTrait<Associated = <Self as ExtendTrait>::ExtendAssociated>,
{
    type ExtendAssociated: Display;
}

impl<T> ExtendTrait for T
where
    T: ExtendTrait,
    // (because only implemented for T)
    T: ExtendTrait<ExtendAssociated = T>,
    <T as ExtendTrait>::ExtendAssociated: Display,
{
    type ExtendAssociated = T;
}

// use ExtendTrait
fn _print_super<T: ExtendTrait>(input: T) {
    println!("{}", input.result());
}

trait aliases are another unstable feature that is likely relevant, since that allows you to write

pub trait CanUpperHex = Digest + UpperHex + OutputSizeUser
where
    <Self as OutputSizeUser>::OutputSize: Add,
    <<Self as OutputSizeUser>::OutputSize as Add>::Output: ArrayLength<u8>,
;

and use that as a trait bound, which will include all of the where clause bounds as well.

I wouldn't recommend using this, but there's a curious way to abuse associated types to imitate this trait alias on stable today. I think this is the same as what quinedot presented, but more opaque because it's been all shoved into a single trait package rather than factored into multiple helpfully named pieces. Presented without comment, because unless you immediately understand what this is saying, you definitely shouldn't be using it.

pub trait CanUpperHex: Digest + UpperHex + OutputSizeUser<OutputSize = Self::__OutputSize> {
    type __OutputSize: Add<Output = Self::__OutputSize_Output>;
    type __OutputSize_Output: ArrayLength<u8>;
}
impl<T> CanUpperHex for T
where
    Self: Digest + UpperHex + OutputSizeUser,
    <Self as OutputSizeUser>::OutputSize: Add,
    <<Self as OutputSizeUser>::OutputSize as Add>::Output: ArrayLength<u8>,
{
    type __OutputSize = <Self as OutputSizeUser>::OutputSize;
    type __OutputSize_Output = <<Self as OutputSizeUser>::OutputSize as Add>::Output;
}

quinedot's version actually looks somewhat reasonable. This here is a mess of the kind you'd shove behind a procedural macro, pretend is a trait alias, and replace with a proper trait alias as soon as those become available.

I don't have a great answer for this I'm afraid; I learned mostly by doing. There are more learning resources available now, but I'm not sure which covers what. You can search for topics about intermediate or advanced resources and read some general recommendations though.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.