Note: This post assumes some familiarity with Rust, in particular traits.

Contents:

## Introduction

It is useful to be able to write code that is generic over multiple types, such as integer types.

The Rust standard library originally had the unstable (deprecated since release 1.11.0) traits Zero and One that could partially help, but these required the nightly compiler. Since then, the `num` crate has moved out of the standard library.

In this post, I used stable Rust version 1.15.1. The code examples will probably work with earlier versions as well.

All example code is available on GitHub.

## What do we need?

In order to be able to write a generic function for various number types, we need a trait that guarantees several things, including:

• Multiplication
• Equality testing

The `num` crate has the useful PrimInt trait which inherits various traits.

## Factorial example

The factorial function is defined to be the product of integers from `1` to `n` (inclusive). The special case of `0! = 1`. For example, `4! = 4 * 3 * 2 * 1 = 24`. Factorial is defined only for non-negative integers.

## Concrete function

``````/// Find the factorial of n
fn factorial(n: u32) -> u32 {
(1..n + 1).product()
}
``````

This function only supports the concrete `u32` type.

## Generic attempt 1

We make the `n` parameter have the generic type `T` with the trait bound requiring the `PrimInt` trait and `Unsigned` trait:

``````extern crate num;

use num::{PrimInt, Unsigned};

/// Find the factorial of n
fn factorial<T>(n: T) -> T
where T: PrimInt + Unsigned
{
(1..n + 1).product()
}
``````

We get the following error:

``````error[E0308]: mismatched types
--> src/main.rs:9:13
|
9 |     (1..n + 1).product()
|             ^ expected type parameter, found integral variable
|
= note: expected type `T`
= note:    found type `{integer}`

error[E0308]: mismatched types
--> src/main.rs:9:9
|
9 |     (1..n + 1).product()
|         ^^^^^ expected integral variable, found type parameter
|
= note: expected type `{integer}`
= note:    found type `T`

...
``````

## Generic attempt 2

It seems like we cannot use the `1` literal. Luckily, the `PrimInt` trait inherits from the `One` trait (through `Num`), which requires the `one()` method.

``````extern crate num;

use num::{PrimInt, Unsigned};

/// Find the factorial of n
fn factorial<T>(n: T) -> T
where T: PrimInt + Unsigned
{
(T::one()..n + T::one()).product()
}
``````

However, we still get the error related to the required traits (like `Step`) being implemented. We could state in a `where` clause that the `Step` trait is required, but as of writing, `Step` is not stable.

``````error: no method named `product` found for type `std::ops::Range<T>` in the current scope
--> src/main.rs:9:30
|
9 |     (T::one()..n + T::one()).product()
|                              ^^^^^^^
|
= note: the method `product` exists but the following trait bounds were not satisfied: `T : std::iter::Step`, `&'a T : std::ops::Add`, `std::ops::Range<T> : std::iter::Iterator`
``````

## Generic attempt 3

We can avoid the `..`” range syntax by using and use `num`’s range function.

``````extern crate num;

use std::iter::Product;
use num::{PrimInt, Unsigned};

/// Find the factorial of n
fn factorial<T>(n: T) -> T
where T: PrimInt + Unsigned
{
num::range(T::one(), n + T::one()).product()
}
``````

The `PrimInt` trait still does not guarantee the existence of the `Product` trait.

``````error[E0277]: the trait bound `T: std::iter::Product` is not satisfied
--> src/main.rs:10:40
|
10 |     num::range(T::one(), n + T::one()).product()
|                                        ^^^^^^^ the trait `std::iter::Product` is not implemented for `T`
|
= help: consider adding a `where T: std::iter::Product` bound
``````

## Final result

We can import `Product` add add it to the `where` clause.

Now we have a factorial function that works over arbitrary unsigned integer type!

``````extern crate num;

use std::iter::Product;
use num::{PrimInt, Unsigned};

/// Find the factorial of n
fn factorial<T>(n: T) -> T
where T: PrimInt + Unsigned + Product
{
num::range(T::one(), n + T::one()).product()
}
``````

## Using the generic function

Now we can call our factorial function with different unsigned types.

``````fn main() {
println!("u8: 3! = {}", factorial(3_u8));
println!("u16: 3! = {}", factorial(3_u16));
println!("u32: 3! = {}", factorial(3_u32));
println!("u64: 3! = {}", factorial(3_u64));
}
``````

## Analyzing generated code

Rust monomorphizes generic functions, which means a new function is created for each type. This means `rustc` can optimize each instantiated function independently.

Below we can see the symbols for the four factorial functions (for each type) and the main function.

``````\$ nm target/release/factorial-generic-analysis | grep factorial --color=always | sort
0000000000005e90 t _ZN26factorial_generic_analysis9factorial17h771813924a71f57dE
0000000000005ed0 t _ZN26factorial_generic_analysis9factorial17h9049e4d7daf7ac87E
0000000000005f80 t _ZN26factorial_generic_analysis9factorial17h92280da431f06ddaE
00000000000062f0 t _ZN26factorial_generic_analysis4main17h5d9c70811fce980bE
``````

Below, we can see `factorial::<u16>()`:

``````\$ objdump -d target/release/factorial-generic-analysis
...
0000000000005e90 <_ZN26factorial_generic_analysis9factorial17h771813924a71f57dE>:
5e90:       ff c7                   inc    %edi
5e92:       66 b8 01 00             mov    \$0x1,%ax
5e96:       0f b7 cf                movzwl %di,%ecx
5e99:       83 f9 02                cmp    \$0x2,%ecx
5e9c:       72 28                   jb     5ec6 <_ZN26factorial_generic_analysis9factorial17h771813924a71f57dE+0x36>
5e9e:       66 b9 02 00             mov    \$0x2,%cx
5ea2:       66 ba 01 00             mov    \$0x1,%dx
5ea6:       66 b8 01 00             mov    \$0x1,%ax
5eaa:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
5eb0:       0f af c2                imul   %edx,%eax
5eb3:       66 39 f9                cmp    %di,%cx
5eb6:       89 ce                   mov    %ecx,%esi
5eb8:       83 d6 00                adc    \$0x0,%esi
5ebb:       66 39 f9                cmp    %di,%cx
5ebe:       66 89 ca                mov    %cx,%dx
5ec1:       66 89 f1                mov    %si,%cx
5ec4:       72 ea                   jb     5eb0 <_ZN26factorial_generic_analysis9factorial17h771813924a71f57dE+0x20>
5ec6:       c3                      retq
5ec7:       66 0f 1f 84 00 00 00    nopw   0x0(%rax,%rax,1)
5ece:       00 00
...
``````

## Conclusion

With the `num` crate, we can write stable, safe Rust code that is generic over various integer types.

Thanks to Gulshan Singh for reviewing this post.