Rustのクロージャtraitについて調べた(FnOnce, FnMut, Fn)

# 概要
Rust勉強中です。
クロージャを扱うときに出てくる三つのtrait (`FnOnce`, `FnMut`, `Fn`) について、主に以下の観点で調べたので、備忘録的にまとめます。

* クロージャを定義したとき、どのtraitが実装されるのか
* クロージャを扱うときにどのtraitを使えばいいのか

誤りなどありましたらご指摘いただければと思います。
なお、参考文献は末尾にまとめました。

~~以下の内容は、v1.23.0 (2018/1/12時点の最新のstable)に基づきます。~~

__追記(2021/02/14): 最新版(v1.50.0)に基づいた内容に変更、文章の修正、参考文献の更新__

# 前提: クロージャと`FnOnce`, `FnMut`, `Fn`について
Rustでクロージャを定義すると、キャプチャした変数をメンバとして持つ匿名構造体が、コンパイル時に内部的に作られます。[^reference][^example_anonymity]

この内部的に作られる型はコンパイル時にしか分からないため、「クロージャを受け取る関数」を作ろうと思っても、クロージャの型をコード上で直接指定することはできません。

代わりに、`FnOnce`, `FnMut`, `Fn` という三つのtraitを使うことで、クロージャ（に限らず任意の関数など）を受け取る関数を作ることができます。
クロージャ定義時に自動生成される型は、この三つのtraitのうち一つ以上を実装しています。

具体的には、これらのtraitのうちいずれかをジェネリック境界としたジェネリック関数を作ることで、クロージャを受け取る関数を作れます:

```rust:クロージャを受け取る関数の例
// 「i32を受け取りi32を返すクロージャ」を受け取る関数
fn call_with_42<F>(f: F) where F: FnOnce(i32) -> i32 {
    println!("f(42) = {}", f(42));
}

call_with_42(|x| 2 * x);
```

何故`FnOnce`, `FnMut`, `Fn`の三つのtraitがあり、それぞれどう使い分けられるのかがこの記事の主題になります。
それを見ていく前に、それぞれのtraitの定義を確認しておきたいと思います。[^fn_once][^fn_mut][^fn]

```rust
pub trait FnOnce<Args> {
    type Output;
    extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
}

pub trait FnMut<Args>: FnOnce<Args> {
    extern "rust-call" fn call_mut(&mut self, args: Args) -> Self::Output;
}

pub trait Fn<Args>: FnMut<Args> {
    extern "rust-call" fn call(&self, args: Args) -> Self::Output;
}
```

それぞれの違いは、`self`と`&mut self`と`&self`のいずれを受け取るかです。

また、もう一つ重要なのは、`Fn`が`FnMut`を、`FnMut`が`FnOnce`を継承していることです。次の項で詳しく見ますが、これらはクロージャ間の包含関係を表しています。

* `FnMut` を実装しているクロージャは、`FnOnce` も実装している
* `Fn` を実装しているクロージャは、`FnMut`, `FnOnce` も実装している

なお、`FnOnce` trait を介した呼び出しは`self`の所有権をとるので、**`FnOnce`は（その名の通り）一回しか呼び出せない**ことにも注意が必要です。

# どのtraitがいつ実装されるか
本題です。
上述の通り、クロージャが実装しうるtraitは三つあるので、「じゃあ、どう使い分けられているのか？」という疑問が湧きます。

結論から言えば、各traitは、それぞれクロージャが特定の条件を満たしているかどうかに応じて、自動的に実装されるかどうかが変わります:

* `FnOnce`は、**全てのクロージャ**が実装している
* `FnMut`は、**キャプチャした変数をmoveしない全てのクロージャ**が実装している
* `Fn`は、**キャプチャした変数をmoveせず、書き換えもしない全てのクロージャ**が実装している

逆から言えば、以下のようになります。

* クロージャが**キャプチャした変数をmoveしている**なら、`FnOnce`だけを実装している（`FnMut`, `Fn`は実装されない）
* クロージャが**キャプチャした変数をmoveしていないが、書き換えている**ならば、`FnMut`, `FnOnce`だけを実装している（`Fn`は実装されない）
* クロージャが**キャプチャした変数をmoveしておらず、書き換えてもいない**ならば、`Fn`, `FnMut`, `FnOnce`を全て実装している

## 考え方
上記は暗記する必要はなく、以下のことを考慮すれば自然に導けます。

* クロージャを定義すると、内部で匿名の構造体が作られること
* キャプチャした変数は、構造体のメンバとなること

たとえば、以下のようにクロージャを定義したとします:

```rust
struct Data(i32)

let x = Data(1);
let c = || {
    // ここでxを使ってなにかやる
    ...
};
```

このとき、内部的に以下のような型が作られます。（イメージです）

```rust
struct Closure {
    // ここでは例として `&Data` 型で持っているが、ケースによっては `&mut Data` や `Data` になる
    x: &Data,
}
```

そして、以下のそれぞれのimplが**可能なら**作られます。（イメージです）

```rust
impl FnOnce() for Closure {
    fn call_once(self) {
        ...
    }
}

impl FnMut() for Closure {
    fn call_mut(&mut self) {
        ...
    }
}

impl Fn() for Closure {
    fn call(&self) {
        ...
    }
}
```

各「...」のところには、クロージャの定義時に書いた処理の中身が入ります（この際、`x`は`self.x`に置き換えて考えます）。

ここで、「可能なら」と言ったのは、処理の中身によってはimplできないことがあるからです。

* 処理の中で `x` を書き換えていたら、 `self`を受け取る`FnOnce`や`&mut self`を受け取る`FnMut`のimplは成立するが、`&self`を受け取る`Fn`のimplは成立しない
* 処理の中で `x` の所有権を手放していたら、`self`の所有権をとらない`FnMut`や`Fn`の定義は成立しない

このことから、処理の中身に応じて自然に「三つのtraitのどれが実装されるか」が決まると考えられます。

以下、具体的な例を見ていきます。

## 例1: キャプチャした変数をmoveしていれば`FnOnce`のみ実装
キャプチャした変数の所有権をどこかにmoveしている場合、`FnOnce`のみが実装されます。

```rust:例1
// FnOnceのみ渡せる関数
fn call_fn_once<F>(f: F) where F: FnOnce() {
    f();
}

// FnMutのみ渡せる関数
fn call_fn_mut<F>(mut f: F) where F: FnMut() {
    f();
}

// Fnのみ渡せる関数
fn call_fn<F>(f: F) where F: Fn() {
    f();
}

struct Data(i32);

// This function takes ownership of x.
fn consume(x: Data) {
    println!("{}", x.0);
}

// ok
let x = Data(0);
call_fn_once(|| {
    consume(x);
});

// error: cannot move out of `x`, a captured variable in an `FnMut` closure
// let x = Data(0);
// call_fn_mut(|| {
//     consume(x);
// });

// error: cannot move out of `x`, a captured variable in an `Fn` closure
// let x = Data(0);
// call_fn(|| {
//    consume(x);
// });
```

上の考え方に照らせば、このときに`FnMut`が実装されないのは、以下のような定義が成立しえないためだと考えられます:

```rust
fn call_mut(&mut self) {
    // NG: mut参照からconsumeすることはできない
    consume(self.x);
}
```

`Fn`も同様です。

なお、上述のように、`FnOnce`しか実装していないクロージャは、**一回しか呼び出せません**。
キャプチャした変数の所有権を初回呼出時に手放してしまうことを考えれば、納得できます。

## 例2: キャプチャした変数をmoveせず書き換えていれば`FnOnce`と`FnMut`を実装
キャプチャした変数を書き換えているが所有権のmoveはしていない場合、`FnOnce`と`FnMut`が実装されます。

```rust:例2
// FnOnceのみ渡せる関数
fn call_fn_once<F>(f: F) where F: FnOnce() {
    f();
}

// FnMutのみ渡せる関数
fn call_fn_mut<F>(mut f: F) where F: FnMut() {
    f();
}

// Fnのみ渡せる関数
fn call_fn<F>(f: F) where F: Fn() {
    f();
}

struct Data(i32);

// ok
let mut x = Data(0);
call_fn_once(|| {
    x.0 = 1;
});

// ok
let mut x = Data(0);
call_fn_mut(|| {
    x.0 = 1;
});

// error: cannot assign to `x.0`, as `Fn` closures cannot mutate their captured variables
// let mut x = Data(0);
// call_fn(|| {
//    x.0 = 1;
// });
```

例1と同様に、`Fn`が実装されないのは、以下のような定義が成立しえないためと考えられます:

```rust
fn call(&self) {
    // NG: mutでない参照を通じて書き換えることはできない
    self.x = 1;
}
```

## 例3: キャプチャした変数をmoveも書き換えもしていなければ`FnOnce`と`FnMut`と`Fn`を全て実装
上記のいずれにも当てはまらない場合、`FnOnce`と`FnMut`と`Fn`が全て実装されます。

```rust:例3
// FnOnceのみ渡せる関数
fn call_fn_once<F>(f: F) where F: FnOnce() {
    f();
}

// FnMutのみ渡せる関数
fn call_fn_mut<F>(mut f: F) where F: FnMut() {
    f();
}

// Fnのみ渡せる関数
fn call_fn<F>(f: F) where F: Fn() {
    f();
}

struct Data(i32);

// ok
let x = Data(0);
call_fn_once(|| {
    println!("{}", x.0);
});

// ok
let x = Data(0);
call_fn_mut(|| {
    println!("{}", x.0);
});

// ok
let x = Data(0);
call_fn(|| {
    println!("{}", x.0);
});
```

## 補足1: キャプチャした変数がCopyを実装している場合
例1の補足です。
キャプチャした変数が[Copyトレイト](https://doc.rust-lang.org/std/marker/trait.Copy.html)を実装している場合は、所有権の移動は起こりません。
そのため、Copyトレイトを実装している型の変数（`i32`など）をキャプチャしてクロージャ内で他の関数に渡しても、`FnOnce`だけが実装されることはなく、常に`FnMut`もしくは`Fn`まで実装されます。

```rust:例4(例1でDataをCopy可能にした場合)
// FnOnceのみ渡せる関数
fn call_fn_once<F>(f: F) where F: FnOnce() {
    f();
}

// FnMutのみ渡せる関数
fn call_fn_mut<F>(mut f: F) where F: FnMut() {
    f();
}

// Fnのみ渡せる関数
fn call_fn<F>(f: F) where F: Fn() {
    f();
}

// Copyを実装
#[derive(Clone, Copy)]
struct CopyableData(i32);

// DataがCopyを実装しているので、moveではなくcopyされる
fn not_consume(x: CopyableData) {
    println!("{}", x.0);
}

// ok
let x = CopyableData(0);
call_fn_once(|| {
    not_consume(x);
});

// ok
let x = CopyableData(0);
call_fn_mut(|| {
    not_consume(x);
});

// ok
let x = CopyableData(0);
call_fn(|| {
    not_consume(x);
});
```


## 補足2: moveクロージャとの関係
クロージャの定義時に`move`キーワードを使うことで、キャプチャした変数の所有権のクロージャへの移動を強制します。

```rust:moveクロージャの例
struct Data(i32);

let x = Data(0);
let c = move || {
    println!("in closure: {}", x.0);
};

// xはクロージャにmoveされているので、ここでは使えない
// error: borrow of moved value: `x`
//println!("in main: {}", x.0);

c();
```

うえで、クロージャはキャプチャした変数をメンバに持つ構造体として考えられると書きましたが、`move`キーワードの有無によって、このメンバが参照になるか実体になるかが変わる、と解釈できます:[^move_captured_variable]

```rust
// moveなしで、xの所有権も必要としない場合
struct Closure {
    x: &Data,
}

// moveあり、もしくはxの所有権を必要とする場合
struct Closure {
    x: Data,
}
```

[^move_captured_variable]: `move`を付けなくても、例1のようにキャプチャした変数をよそへmoveする場合は、キャプチャした変数を実体で保持します


では、`move`を付けることで、「クロージャが`FnOnce`、`FnMut`、`Fn`のどれを実装するか」に影響するでしょうか。
結論としては、`move`を付けても**クロージャが`FnOnce`、`FnMut`、`Fn`のどれを実装するかには影響しません**。
すなわち、上の例1~例4は全て、クロージャに`move`を付けてもそのまま成り立ちます。

実際、うえのようなクロージャの構造体表現を考えてみると、クロージャがキャプチャした変数の所有権を保持していたとしても、`&mut self`を通してキャプチャした変数を書き換えられることなどには影響しないことから分かります。

`move`クロージャかどうかと、`FnOnce`、`FnMut`、 `Fn`のいずれを実装しているかという問題は、それぞれ別の段階での所有権の移動に紐づいています:

* `move`クロージャかどうか
    * 環境⇒クロージャへの所有権の移動に関係
* `FnOnce`、`FnMut`、`Fn`のいずれを実装しているか
    * クロージャ⇒外部の関数等への所有権の移動に関係

"The Book" には以下のように書かれています:[^book]

> Note: move closures may still implement Fn or FnMut, even though they capture variables by move. This is because the traits implemented by a closure type are determined by what the closure does with captured values, not how it captures them. The move keyword only specifies the latter.


# クロージャを受け取るときにどのtraitを使うべきか
実際に「クロージャを受け取る関数」を書くときに、どのtraitで受け取るべきかを考えてみます。

ここまで説明したように、クロージャの間には以下の包含関係があります。

```
(Fnを実装したクロージャの集合) ⊂ (FnMutを実装したクロージャの集合) ⊂ (FnOnceを実装したクロージャの集合) 
```
![fn.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/80237/9d35c74b-2b88-9738-ef7d-438ed437525b.png)

可能な限り**このベン図のより外側にあるtraitを使ったほうが、より多くのクロージャを受け取れる**ということになります。
逆に、**もしクロージャを受け取るときにFnで受け取るようにすると、一部のクロージャが受け取れない**ことを意味します。
なので、**可能な限り`Fn`より`FnMut`、また`FnMut`より`FnOnce`**でクロージャを受け取るべき、と考えられます。

具体的には、以下のように決めればよいと思います。

* 渡されたクロージャを一回しか呼び出さないならば、`FnOnce`で受け取る
  * 標準ライブラリでは、[Option](https://doc.rust-lang.org/std/option/enum.Option.html)の[map](https://doc.rust-lang.org/std/option/enum.Option.html#method.map)などのメソッドや、[std::thread::spawn](https://doc.rust-lang.org/std/thread/fn.spawn.html)などが該当
* 渡されたクロージャを複数回呼び出す可能性があるなら、`FnMut`で受け取る
  * 標準ライブラリでは、[Iterator](https://doc.rust-lang.org/std/iter/trait.Iterator.html)の[map](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.map)などのメソッドが該当
* クロージャのimmutable性を要求したい場合は`Fn`で受け取る
  * こちらは少し探してみても標準ライブラリでは例が見つかりませんでした
  * たとえば、複数のスレッドから一つのクロージャを呼び出したいときなどには該当するかと思われます

# クロージャを返すときにどのtraitを使うべきか
__追記(2021/02/14): implを使った内容に書き換え__


同様に、クロージャを返す時にどのtraitを使うべきか考えます。
まず前提として、クロージャを関数から返す方法について確認しておきます。

クロージャの具体的な型はコーディング時には分からないので、返り値型を直接書き下すことができません:

```rust
fn make_counter(init: i32, inc: i32) -> /* ここに何を書くか */ {
    let mut x = init;
    move || {
        x += inc;
        x - inc
    }
}
```

これは、Rustの1.26で導入された `impl Trait`という機能を使って書くことができます:[^announce_126]

```rust:例(impl-Trait)
fn make_counter(init: i32, inc: i32) -> impl FnMut() -> i32 {
    let mut x = init;
    move || {
        x += inc;
        x - inc
    }
}

let mut c = make_counter(5, 2);
println!("{}", c()); // 5
println!("{}", c()); // 7
println!("{}", c()); // 9
```

`impl FnMut() -> i32` は、「`FnMut() -> i32`を実装した何らかの型」を意味します。
クロージャの型を直接指定することができないので、「FnMutを実装している何か」であることだけ明示する、という感じです。

また、`Box`でラップしてトレイトオブジェクトとして返却する方法もあります（Rustの1.26より前のバージョンではこの方法しかありませんでした）:

```rust:例(dyn-Trait)
// 最新版では `Box<dyn FnMut() -> i32>` とdynを付けないと警告
fn make_counter(init: i32, inc: i32) -> Box<dyn FnMut() -> i32> {
    let mut x = init;
    Box::new(move || {
        x += inc;
        x - inc
    })
}

let mut c = make_counter(5, 2);
println!("{}", c()); // 5
println!("{}", c()); // 7
println!("{}", c()); // 9
```

`Box`を使った方法は、返却された関数の呼び出し時に動的ディスパッチが伴うので、可能なときは前者の`impl`を使ったほうが望ましいです（ただし`impl`を使った方法がとれない場合もあります）


さて、（implを使うにしろdynを使うにしろ）`FnOnce`、`FnMut`、`Fn`のいずれかのtraitを指定してやる必要があります。

例えばうえの例で返却しているクロージャは`FnOnce`と`FnMut`を実装していますが、これを`FnOnce`として返却してしまうと、呼び出し側は「FnOnceを実装した何か」ということしか分からないのでこのクロージャを一回しか呼び出すことができません。

より一般に、引数で受け取るときとは逆に、**可能な限り`FnOnce`よりも`FnMut`、また`FnMut`よりも`Fn`として返す**べきであると言えます。
「`Fn`は`FnMut`でもあり、`FnMut`は`FnOnce`でもある」わけですから、こうすることで、呼び出し側でより広い範囲で返却されたクロージャを使うことができます。

# 参考文献
以下のページを参考にしました。

* [Closure types - The Rust Reference](https://doc.rust-lang.org/stable/reference/types/closure.html)
* [Closures: Anonymous Functions that Can Capture Their Environment - The Rust Programming Language](https://doc.rust-lang.org/book/ch13-01-closures.html)
* 各traitのドキュメント
  * [std::ops::FnOnce](https://doc.rust-lang.org/beta/std/ops/trait.FnOnce.html)
  * [std::ops::FnMut](https://doc.rust-lang.org/beta/std/ops/trait.FnMut.html)
  * [std::ops::Fn](https://doc.rust-lang.org/beta/std/ops/trait.Fn.html)
* [Rustのクロージャ3種を作って理解する | κeenのHappy Hacκing Blog](http://keens.github.io/blog/2016/10/10/rustnokuro_ja3tanewotsukutterikaisuru/)
* [rust - When does a closure implement Fn, FnMut and FnOnce? - Stack Overflow](https://stackoverflow.com/questions/30177395/when-does-a-closure-implement-fn-fnmut-and-fnonce)

[^reference]: https://doc.rust-lang.org/stable/reference/types/closure.html
[^example_anonymity]: https://doc.rust-lang.org/rust-by-example/fn/closures/anonymity.html
[^book]: https://doc.rust-lang.org/book/ch13-01-closures.html
[^fn_once]: https://doc.rust-lang.org/beta/std/ops/trait.FnOnce.html
[^fn_mut]: \https://doc.rust-lang.org/beta/std/ops/trait.FnMut.html
[^fn]: https://doc.rust-lang.org/beta/std/ops/trait.Fn.html
[^announce_126]: https://blog.rust-lang.org/2018/05/10/Rust-1.26.html