Generic function to compute a hash (digest::Digest trait) and get back a String

Question

I have a little bit of trouble wrapping my head around this problem. I am trying to write a generic function which can take any digest::Digest and spits out a string form of the computed digest ("hex string").

Here is the non-generic version as minimal example:

#![forbid(unsafe_code)]
#![forbid(warnings)]
extern crate sha2; // 0.9.1

use sha2::{Sha256, Digest}; // 0.9.1

fn main() {
    let hash = Sha256::new().chain("String data").finalize();
    let s = format!("{:x}", hash);
    println!("Result: {}", s);
}

... and here is my attempt at a generic version:

#![forbid(unsafe_code)]
#![forbid(warnings)]
extern crate sha2; // 0.9.1
extern crate digest; // 0.9.0

use digest::Digest;
use sha2::Sha256;

fn compute_hash<D: Digest>(input_data: &str) -> String {
    let mut hasher = D::new();
    hasher.update(input_data.as_bytes());
    let digest = hasher.finalize();
    format!("{:x}", digest)
}

fn main() {
    let s = compute_hash::<Sha256>("String data");
    println!("Result: {}", s);
}

... which gives the following error:

   Compiling playground v0.0.1 (/playground)
error[E0277]: cannot add `<D as sha2::Digest>::OutputSize` to `<D as sha2::Digest>::OutputSize`
  --> src/lib.rs:13:21
   |
13 |     format!("{:x}", digest)
   |                     ^^^^^^ no implementation for `<D as sha2::Digest>::OutputSize + <D as sha2::Digest>::OutputSize`
   |
   = help: the trait `std::ops::Add` is not implemented for `<D as sha2::Digest>::OutputSize`
   = note: required because of the requirements on the impl of `std::fmt::LowerHex` for `digest::generic_array::GenericArray<u8, <D as sha2::Digest>::OutputSize>`
   = note: required by `std::fmt::LowerHex::fmt`
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider further restricting the associated type
   |
9  | fn compute_hash<D: Digest>(input_data: &str) -> String where <D as sha2::Digest>::OutputSize: std::ops::Add {
   |                                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0277`.
error: could not compile `playground`.

Now suppose I understand the error correctly, the implementation of std::fmt::LowerHex used by format!() appears to require std::ops::Add for the OutputSize of the GenericArray<u8, N> (i.e. the N) which is returned by .finalize(). However, the non-generic example suggests that there is such an implementation for ArrayLength<u8>.

So, given I cannot implement the std::ops::Add trait for an external type, how can I satisfy the compiler in this case?

Or maybe to rephrase my question, although I - being new with Rust - am not a 100% sure it is what I want: how do I tell the compiler to treat <D as sha2::Digest>::OutputSize the same as ArrayLength<u8>?

NB: I am relatively new with Rust, so please keep that in mind and kindly refer to the exact piece of documentation applicable to my case, rather than "the documentation" in general. I have scoured the documentation for digest, for various of the implementers of digest::Digest, for this error and for (what I thought were) similar issues and the traits topics in the Rust Book (2018 edition) for nearly three hours before I asked. Thanks.

---

In the second example I am using use digest::Digest;. That's because in the future other hash algorithms are supposed to follow and it seemed to make more sense to use digest::Digest directly instead of the re-exported Digest from one of the implementers. If there is a reason against that, feel free to remark on it.

Myelitis

May be worth noting that the digest crate uses generic_array to work around the lack of language support for const generics. It seems likely that a future version of the language could allow digest to support this usage in a more direct way. – Prostitution

Answer 1

Rust requires that you specify all the functionality you use in generics. The note:

   |                     ^^^^^^ no implementation for `<D as sha2::Digest>::OutputSize + <D as sha2::Digest>::OutputSize`
   = help: the trait `std::ops::Add` is not implemented for `<D as sha2::Digest>::OutputSize`

is trying to say that we are using Add on the type D::OutputSize but not requiring it as a constraint, which we can do like so:

fn compute_hash<D: Digest>(input_data: &str) -> String
    where D::OutputSize: std::ops::Add

If you make this change, you'll come to the next error:

   |                     ^^^^^^ the trait `digest::generic_array::ArrayLength<u8>` is not implemented for `<<D as sha2::Digest>::OutputSize as std::ops::Add>::Output`

so there is another requirement, but we can add that too:

fn compute_hash<D: Digest>(input_data: &str) -> String
    where D::OutputSize: std::ops::Add,
          <D::OutputSize as std::ops::Add>::Output: digest::generic_array::ArrayLength<u8>

This will compile.

But let's dive into the reasons why these constraints are necessary. finalize returns Output<D> and we know that it is the type GenericArray<u8, <D as Digest>::OutputSize>. Evidently format!("{:x}", ...) requires the trait LowerHex so we can see when this type satisfies this trait. See:

impl<T: ArrayLength<u8>> LowerHex for GenericArray<u8, T>
where
    T: Add<T>,
    <T as Add<T>>::Output: ArrayLength<u8>, 

That looks familiar. So the return type of finalize is satisfies LowerHex if these constraints are true.

But we can get at the same thing more directly. We want to be able to format using LowerHex and we can say that:

fn compute_hash<D: Digest>(input_data: &str) -> String
    where digest::Output<D>: core::fmt::LowerHex

Since this can directly express what we use in the generic function, this seems preferable.

Crayfish

Thanks so much. Especially the path to your solution is what's interesting to me as a student of Rust. – Myelitis

Answer 2

So, given I cannot implement the std::ops::Add trait for an external type, how can I satisfy the compiler in this case?

You don't need to implement it, you need to require that it is implemented.

how do I tell the compiler to treat <D as sha2::Digest>::OutputSize the same as ArrayLength<u8>?

This is the right idea, but since ArrayLength is a trait, not a type, you want "is constrained to implement", not "the same as".

This will compile:

#![feature(associated_type_bounds)]

...

fn compute_hash<D>(input_data: &str) -> String
where
    D: Digest,
    D::OutputSize: ArrayLength<u8> + std::ops::Add<Output: ArrayLength<u8>>,
{

The catch is that it uses the unstable feature associated_type_bounds — that's the part where an associated type, D::OutputSize, appears on the left side of a trait bound, SomeType: SomeTrait.

To stick to stable Rust, we can introduce some ugly type parameters to avoid associated type bounds by making them equality instead:

fn compute_hash<D, L1, L2>(input_data: &str) -> String
where
    D: Digest<OutputSize = L1>,
    L1: ArrayLength<u8> + std::ops::Add<Output = L2>,
    L2: ArrayLength<u8>,
{
    ...
}

fn main() {
    let s = compute_hash::<Sha256, _, _>("String data");
    println!("Result: {}", s);
}

But this requires writing , _, _> at every call site.

There may be a better way to do this — I'm fairly new to Rust and not experienced with the ins and outs of the sort of type-level programming ArrayLength is doing, in Rust.

Janitress