こんにちは、リーです。エモーションテックのバックエンドエンジニアとして働いています。 Rust のasync fn は素直には再帰できないらしいという話を聞いたのでその理由と克服方法について調べてみました。
再帰の例 (fibonacci)
まずは、再帰のプログラムで検証してみます。今回、再帰をつかったプログラムの例としてfibonacciを実装してみました。
非 async 版
まずは async を使わずに書いてみます。これはとくに問題ありません。
fn fibonacci(n: u64) -> u64 { if n <= 1 { n } else { fibonacci(n - 1) + fibonacci(n - 2) } } fn main() { for i in 0..10 { println!("fibonacci({}) = {}", i, fibonacci(i)); } }
async 版
次に 先ほどのコードを元にasyncを使って、どうなるかを試しました。
async fn fibonacci(n: u64) -> u64 { if n <= 1 { n } else { fibonacci(n - 1).await + fibonacci(n - 2).await } } #[tokio::main] async fn main() { for i in 0..10 { println!("fibonacci({}) = {}", i, fibonacci(i).await); } }
しかし、これはコンパイルエラーが出ます。
error[E0733]: recursion in an `async fn` requires boxing
--> api/src/main.rs:151:1
|
151 | async fn fibonacci(n: u64) -> u64 {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ recursive `async fn`
|
= note: a recursive `async fn` must be rewritten to return a boxed `dyn Future`
= note: consider using the `async_recursion` crate: https://crates.io/crates/async_recursion
このコンパイルエラーのエラーコード E0733 (An async function used recursion without boxing) を調べてみると下記のような説明があります。
The Box<...> ensures that the result is of known size, and the pin is required to keep it in the same place in memory.
https://doc.rust-lang.org/error_codes/E0733.html
Boxを使えば解決できそうだと書いてあります
エラーの理由
コンパイラの指示通り直す前に、なぜBoxが必要なのか、下記の２点を調べてみました。
- Box なしだとサイズが決まらない原因は何か
- Box::pinは何故必要なのか
おさらい
理由を考える前に少しだけRustのasyncとawaitについておさらいしてみます。この2つは簡単に説明すると次のようなものです。
- async は「Futureトレイトを実装した型を返す関数」を通常の同期関数のように記述できる構文です
- asyncで実装された関数の処理の完了を待つにはawaitを呼び出します
そしてFutureトレイトは簡単に説明すると「将来に値が確定する計算のステートマシンを抽象化したインタフェース」です。
Futureについて：https://rust-lang.github.io/async-book/02_execution/02_future.html
Trait std::future::Futureの定義は下記のようになります。
pub trait Future { type Output; // Required method fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>; }
なぜBoxなしだとサイズが決まらないか
これはasync fn がコンパイラ内部でどのように変換されるかを考えると分かります。
再帰がない場合
まず簡単な例として再帰がない場合を見てみます。 https://rust-lang.github.io/async-book/04_pinning/01_chapter.html の例が分かりやすいです。
(変換前)
let fut_one = /* ... */; let fut_two = /* ... */; async move { fut_one.await; fut_two.await; }
(変換後)
// The `Future` type generated by our `async { ... }` block struct AsyncFuture { fut_one: FutOne, fut_two: FutTwo, state: State, } // List of states our `async` block can be in enum State { AwaitingFutOne, AwaitingFutTwo, Done, } impl Future for AsyncFuture { type Output = (); fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> { loop { match self.state { State::AwaitingFutOne => match self.fut_one.poll(..) { Poll::Ready(()) => self.state = State::AwaitingFutTwo, Poll::Pending => return Poll::Pending, } State::AwaitingFutTwo => match self.fut_two.poll(..) { Poll::Ready(()) => self.state = State::Done, Poll::Pending => return Poll::Pending, } State::Done => return Poll::Ready(()), } } } }
注目ポイントは AsyncFuture の構造です。fut_one と fut_two という二つの Future をフィールドとして含んでいます。再帰の場合にこの特徴が問題になります。
再帰がある場合
再帰のある場合のコードも見てみましょ。例は https://rust-lang.github.io/async-book/07_workarounds/04_recursion.html のもので、 Future トレイトの実装は省略して構造だけに着目します。
// So this function: async fn recursive() { recursive().await; recursive().await; } // generates a type like this: enum Recursive { First(Recursive), Second(Recursive), }
First や Second の中に Recursive が表われるという再帰的な構造になっているのでコンパイル時にサイズが決まりません。Enabling Recursive Types with Boxes で説明されている通り、この問題を回避するためにBoxが必要です。つまり下記のような構造にする必要があります。
enum Recursive { First(Box<Recursive>), Second(Box<Recursive>), }
上の recursive 関数の場合であれば、下記のように直すことができます。
use futures::future::{BoxFuture, FutureExt}; fn recursive() -> BoxFuture<'static, ()> { async move { recursive().await; recursive().await; }.boxed() }
なぜpinが必要か
こちらもasync fn がコンパイラ内部でどのように変換されるかを考えると分かります。
https://rust-lang.github.io/async-book/04_pinning/01_chapter.html のもう一つの例を見てみます。
(変換前)
async { let mut x = [0; 128]; let read_into_buf_fut = read_into_buf(&mut x); read_into_buf_fut.await; println!("{:?}", x); }
(変換後)
struct ReadIntoBuf<'a> { buf: &'a mut [u8], // points to `x` below } struct AsyncFuture { x: [u8; 128], read_into_buf_fut: ReadIntoBuf<'what_lifetime?>, }
pinが必要な理由も上記ページに記載されています。
Here, the
ReadIntoBuffuture holds a reference into the other field of our structure,x. However, ifAsyncFutureis moved, the location ofxwill move as well, invalidating the pointer stored inread_into_buf_fut.buf.
x のメモリ上の位置が移動すると read_into_buf_fut.buf が指す先が無効になってしまいます。この移動を防ぐために pin が必要なのです。pin については https://rust-lang.github.io/async-book/04_pinning/01_chapter.html#pinning-in-detail が詳しいです。
async 版の fibonacci を書き直す
Box や pin の必要性が分かったところで実際にこれらを使って async 版の fibonacci 関数を二通りの方法で書き直してみます。
Box::pin を使う書き方
1つめは Box::pin をそのまま使う書き方です。
use std::boxed::Box; use std::future::Future; use std::pin::Pin; use tokio; fn boxed_fibonacci(n: u64) -> Pin<Box<dyn Future<Output = u64>>> { Box::pin(async move { if n <= 1 { n } else { let fib1 = boxed_fibonacci(n - 1).await; let fib2 = boxed_fibonacci(n - 2).await; fib1 + fib2 } }) } #[tokio::main] async fn main() { for i in 0..40 { println!("fibonacci({}) = {}", i, boxed_fibonacci(i).await); } }
async_recursion クレートを使う書き方
2つめは async_recursion クレートを使う書き方です。
async_recursion クレートは、非同期関数をBox化された Future を返す関数に自動的に変換するマクロを提供します。このマクロのおかげで簡潔に書くことができます。
use async_recursion::async_recursion; use tokio; #[async_recursion] async fn fibonacci(n: u64) -> u64 { if n <= 1 { n } else { fibonacci(n - 1).await + fibonacci(n - 2).await } } #[tokio::main] async fn main() { for i in 0..10 { println!("fibonacci({}) = {}", i, fibonacci(i).await); } }
まとめ
いかがでしたか。今回の話は、Rustで再帰的な非同期関数を実装する際の特有の課題ですが、適切な方法を使うことで克服することができます。ここで紹介したBox::pinの使用やasync_recursionクレートの利用は、その代表的な解決方法です。再帰的な非同期関数を実装することは、場合によってプログラムの実行速度の向上が期待できます。また、Rust のコンパイラは非常に賢く、適切な方法についての提案や通知を行ってくれるため、最適な実装が可能です。
