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:

  • Addition
  • 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

Let’s start with an non-generic factorial 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
00000000000062b0 t _ZN26factorial_generic_analysis9factorial17had561ff9f2a266a5E
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.


Comments on Reddit