質問の履歴:
Rust 1.26では、言語が戻り位置 impl Trait (RPIT) を導入し、開発者が巣状イテレータアダプタやクロージャ生成構造などの複雑な具体型を隠し、静的ディスパッチによるパフォーマンスの利点を保持できるようにしました。この機能は、コンパイラがコンパイル時に単一の具体的な実装に解決する不透明な存在型を生成し、API境界間で実装の詳細が漏洩するのを防ぎます。ジェネリクスとは異なり、呼び出し側によって選択されるのではなく、RPITは関数の実装によって選択されますが、依然としてコンパイラが適切な機械コードを生成するために具体型の正確なサイズとレイアウトを知る必要があります。
問題:
関数がimpl Traitを返す場合に再帰的に呼び出そうとすると、具体的な戻り型は自身を含む必要があり、無限サイズの自己参照型定義を生み出すことになります。Rustは、スタック上に置かれるすべての戻り値が**Sized**トレイトを実装することを厳格に要求し、コンパイラがコンパイル時に固定なメモリレイアウトとアライメントを計算できることを義務付けています。再帰的なimpl Trait戻りは、各呼び出しフレームが前のものをネストする無制限の型拡張を暗示するため、コンパイラはストレージサイズやスタックフレームオフセットを決定できず、型チェック中にサイクル検出エラーが発生します。
解決策:
解決策は、ヒープ割り当てによる間接化を導入することによって再帰サイクルを明示的に壊すことを要求します。これにより、無限サイズの再帰構造が固定サイズのポインタに変換されます。Box<dyn Trait>を返すことで、関数は代わりに、再帰の深さに関わらずSizedであるvtableポインタとデータポインタを含む太いポインタを返します。あるいは、バリアントが明示的に自身を**Boxや他のポインタ型でラップする再帰的なenumを定義することで、再帰データがヒープ上に存在し、戻り型自体が具体的かつSized**な構造であることを明示的に示すことが可能です。
trait Expr { fn val(&self) -> i32; } struct Literal(i32); impl Expr for Literal { fn val(&self) -> i32 { self.0 } } struct Sum(Box<dyn Expr>, Box<dyn Expr>); impl Expr for Sum { fn val(&self) -> i32 { self.0.val() + self.1.val() } } // エラー: 再帰的な不透明型 // fn eval(n: u32) -> impl Expr { // if n == 0 { Literal(0) } // else { Sum(Box::new(eval(n-1)), Box::new(Literal(1))) } // } // 成功: Box<dyn Trait>を介した明示的な間接化 fn eval(n: u32) -> Box<dyn Expr> { if n == 0 { Box::new(Literal(0)) } else { Box::new(Sum(eval(n-1), Box::new(Literal(1)))) } }
高パフォーマンスのネットワークプロキシ用の構成パーサを設計している間、入れ子のポリシー表現のための再帰的降下パーサを実装する必要がありました。最初の設計では、解析されたルールを表す**Policyトレイトを指定し、内部のAND/OR/NOTロジックノードの表現を下流の消費者から隠すためにparse関数がimpl Policy**を返すことを意図していました。
最初のアプローチでは直接再帰を行いました。parse関数はトークンをマッチし、AND(policy1, policy2)のような複合表現に対しては、サブポリシーを再帰的に呼び出して直接**impl Policy**として返しました。この戦略は、モノモーフィゼーションによるゼロコスト抽象化の利点を提供し、ヒープ割り当てのオーバーヘッドを回避しました。しかし、Rustは、再帰的な呼び出しが無限の型サイズを暗示しているというサイクルを作成するというコンパイルエラーを出力しました。
第二の考慮された解決策は、戻り型を**Box<dyn Policy>**に切り替えることでした。これにより、各再帰的サブポリシーがヒープ上に割り当てられ、トレイトオブジェクトの太いポインタだけが返されました。このアプローチは成功裏にコンパイルされましたが、戻り型がネストの深さに関係なく固定サイズのポインタであったためです。しかし、パースツリー内の各ノードに対してヒープ割り当てのオーバーヘッドが導入され、ポリシー評価中にvtableルックアップを介した動的ディスパッチが必要となりました。
第三の代替案は、Literal、And、Or、Notのためのバリアントを持つ明示的な**PolicyNode列挙型を定義し、再帰的バリアントが自身をBox<PolicyNode>**でラップすることを探求し、dynディスパッチを回避しましたが、コンパイル時に知られているノードタイプの閉じた集合を必要としました。この静的ディスパッチアプローチは、トレイトオブジェクトに関連するvtableのオーバーヘッドと割り当てを排除しましたが、enum定義を変更することなく後続のクレートが新しいノードタイプでポリシー言語を拡張する能力を犠牲にしました。
私たちは、ポリシーエンジンがランタイムプラグイン登録を必要とし、サードパーティの拡張が新しいポリシータイプを定義できるため、閉じたenumは実用的ではないと考え、**Box<dyn Policy>**アプローチを選択しました。その結果、スタックスペースとヒープの安定性、および動的な柔軟性を交換する機能的な再帰パーサが得られましたが、後に高スループットシナリオにおける割り当て圧力を軽減するために、テール再帰的なパーシングパターンを反復処理に変換することによってホットパスを最適化しました。
async fn砂糖が再帰制約とどのように相互作用するのか、特にそれが不透明なimpl Futureも返すために？
async fnは、各.awaitポイントが生成される列挙型における異なるサスペンション状態を必要とする状態機械に変換されます。再帰的なasync fn呼び出しは、生成される未来が自身をバリアントとして含むため、同じ無限型エラーを引き起こします。候補者はしばしばコンパイラが非同期再帰を自動的に処理すると仮定しますが、解決策は未来を**Box::pinで手動的にボックス化するか、Pin<Box<dyn Future<Output = T>>>を返す必要があります。これにより、ヒープ割り当てが強制され、再帰的な未来が固定メモリ位置にピン留めされます。これは、戻り未来が'staticであるか、適切に制約されることを確保する追加の複雑さをもたらし、async fn再帰が標準のimpl Traitの戻りと同じSized**ルールに従うことを理解することが重要です。
引数位置(APIT)でimpl Traitを使用すると、なぜ同じ再帰制限が発生しないのか？
引数位置のimpl Traitは、指定されたトレイトによって制約された匿名のジェネリック型パラメータに対する構文的砂糖です。関数が再帰的にAPITで自分自身を呼び出すと、コンパイラは各呼び出しサイトで渡される具体型ごとに異なるモノモーフィゼーションされたインスタンスを生成します。つまり、再帰関数は自身の不透明バージョンを返すのではなく、各スタックレベルで異なる具体型を受け入れています。候補者はしばしばRPITとAPITを混同し、APITが戻り型（具体的なインスタンスである場合）が知られている呼び出しグラフに参加するのに対して、RPITは間接化なしには自己参照の無限構造に解決できない単一の不透明型を関数本体のために定義することを見落とします。
T: Traitを持つ構造体の中にimpl Traitをラップして使用できますか？
フィールドとしてimpl Traitを含む構造体は、impl Traitが関数の戻り位置または引数位置でのみ有効であり、型定義や構造体フィールドでは無効であるため、直接名前を付けることができません。候補者はしばしばBox<impl Trait>を書くことを試みますが、これは関数の戻り文脈の外では無効な構文であり、不透明型エイリアスを具体型コンストラクタと混同しています。この誤解は、impl Traitをジェネリック位置で使用できる第一級型として扱うことから生じており、特定の関数シグネチャ位置でのみ利用可能なコンパイラ生成の存在型として理解することが重要です。正しいアプローチは、型消去のためにBox<dyn Trait>を使用するか、具体型が明示的である再帰的な列挙型定義を使用する必要があり、型システムがランタイム前にSized制約を計算できるようにします。