Rust の const fn で最速の FizzBuzz

## 動機
最速のプログラムは何かと考えたときにその答えは「何もしない」が正解になるのではないでしょうか。ということで実行時 (runtime) ではなくコンパイル時 (compile time) に FizzBuzz をやってしまうということを考えてみました。Rust で。

## どうやって
タイトルに書いてあるのでネタバレしていますが、Rust には const fn (C++ で言うところの constexpr) という機能があるのでこれを利用します。つまり const fn を使って`"1\n2\nFizz\n4\nBuzz\n6..."`のような文字列をバイナリに埋め込んでしまうということです。実行時にはその文字列を標準出力に流し込むだけです。

## しかし
const fn の機能は現状 (stable channel) ではかなり制限されており、まともに使えません。制限されている機能は主に下記の通り。

- if / match 等の条件分岐
- ~~for / loop 等の繰り返し処理~~ (`#![feature(const_loop)]`で使えるとの情報をコメントで頂きました)
- heap の使用 (Vec 等は使えない)
- const fn 以外の関数の呼び出し (1.to_string() とかも使えない)

などなど…。つらい:pensive:。

## どうしたか
### if / match 等の条件分岐は？
nightly channel なら使えます。その上で`feature flag`を設定します。

```rust
#![feature(const_if_match)]

const fn foo() {
    match (i % 3, i % 5) {
        // do something
    }
}
```

### for / loop 等の繰り返し処理は？
~~nightly channel でも使えないようなので、再帰で処理することに。~~
nightly channel では`#![feature(const_loop)]`で loop / while が使えます。

``` rust
// const LIMIT: usize = 20;

// const fn bar() {
//     baz(0);
// }

// const fn baz(mut count: usize) {
//     if count <= LIMIT {
//         // do something
//         count += 1;
//         baz(count);
//     }
// }

#![feature(const_loop)]

const fn bar() {
    loop {
        // do somthing
    }
}
```

### heap の使用は？
コンパイル時にサイズの分かっている型しか使えません。ミュータブルな参照を使うにも`feature flag`が必要です。

```rust
#![feature(const_mut_refs)]

const fn hoge() -> [u8; 1024] {
    let mut buf = [0; 1024];
    piyo(&mut buf);
    buf
}

const fn piyo(buf: &mut [u8]) {
    // do something
}
```

### const fn 以外の関数の呼び出しは？
`1.to_string()`で整数を文字に変換したいですが、これはコンパイルエラーです（たぶん heap も使うし）。なのでルックアップテーブルを使って、整数の`1`を文字の`'1'`(utf-8 の 0x31) に変換することにしました。

```rust
const LUT: [u8; 10] = *b"0123456789";
let fuga = LUT[1]; // 文字の '1' になる。
```

## 最速の FizzBuzz がこちら
何をやっているかはコードを読んで察してください。`fizzbuzz(n)`を大きくすると、どこかでコンパイルエラーになると思います。（編集リクエストありがとうございます！）（みなさまのコメントを反映して書き換えました。）（以下の例は buf サイズを 1024 にしていますが、[コンパイル時に計算できます。](https://qiita.com/benki/items/5c857a0e8695fabd4df8#comment-9696d7f0a0d842f6a034)）

```rust
#![feature(const_fn)]
#![feature(const_if_match)]
#![feature(const_mut_refs)]
#![feature(const_loop)]
#![allow(non_upper_case_globals)]

const F: u8 = b'F';
const i: u8 = b'i';
const z: u8 = b'z';
const B: u8 = b'B';
const u: u8 = b'u';
const NEW_LINE: u8 = b'\n';
const LUT: [u8; 10] = *b"0123456789";

#[inline]
const fn insert(buf: &mut [u8], pos: &mut usize, utf8: u8) {
    buf[*pos] = utf8;
    *pos += 1;
}

macro_rules! bulk_insert {
    ($buf:expr, $pos:expr, [$($inner:tt),*]) => (
        $(insert($buf, $pos, $inner);)*
    );
}

const fn fizzbuzz(limit: usize) -> [u8; 1024] {
    let mut buf = [0; 1024];
    let mut num = 1;
    let mut pos = 0;
    loop {
        if num > limit {
            break;
        }
        match (num % 3, num % 5) {
            (0, 0) => {
                bulk_insert!(&mut buf, &mut pos, [F, i, z, z, B, u, z, z]);
            }
            (0, _) => {
                bulk_insert!(&mut buf, &mut pos, [F, i, z, z]);
            }
            (_, 0) => {
                bulk_insert!(&mut buf, &mut pos, [B, u, z, z]);
            }
            (_, _) => {
                let third = if num / 100 > 0 {
                    insert(&mut buf, &mut pos, LUT[(num / 100)]);
                    (num / 100) * 100
                } else {
                    0
                };
                let second = if (num - third) / 10 > 0 {
                    insert(&mut buf, &mut pos, LUT[(num - third) / 10]);
                    ((num - third) / 10) * 10
                } else {
                    0
                };
                insert(&mut buf, &mut pos, LUT[(num - third - second)]);
            }
        }
        insert(&mut buf, &mut pos, NEW_LINE);
        num += 1;
    }
    buf
}

// 1..=20
const FIZZBUZZ_20: [u8; 1024] = fizzbuzz(20);

fn main() {
    println!("{}", unsafe { std::str::from_utf8_unchecked(&FIZZBUZZ_20) });
}

```

できあがったバイナリを覗いてみると、確かに`"1\n2\nFizz\n4\nBuzz\n6..."`な文字列が埋め込まれていますね。
![fizzbuzz.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/353186/38e19e8f-8f09-f595-fc64-5de7ac829002.png)

## まとめ
const fn ~~つらい~~ いいぞ:blush:。