【上級者向け】Hack言語におけるRecursive Typesの極意：木構造と再帰的データ構造の厳格な型安全設計
コードレビューをしていて、お前らが持ち込む「JSONパーサーの出力結果」や「ネストした抽象構文木（AST）」の型定義を見るたびに、私は深い絶望と微かな期待を覚える。
「とりあえず `mixed` にしておきました」「`dynamic` でキャストしています」——そんな甘ったれたコードをプロダクションのメインラインにマージさせるわけにはいかない。
Hack言語の真髄は、その厳格な静的型システム（Strict Mode）にある。HHVMのJITコンパイラが爆速でコードをネイティブ実行できるのは、型チェッカーがコンパイル時にすべての型の境界を完全に把握しているからだ。
今回は、実務で最も頭を悩ませる「Recursive Types（再帰的型定義）」に真っ向から焦点を当てる。木構造や非同期で送受信される多層的なJSONペイロードを、型チェッカーの制限をかいくぐり、1ミリの妥協もなく安全にハンドリングする極限のテクニックを伝授しよう。
—
1. Hackの型チェッカーが「再帰」を恐れる理由
まず、背後にあるHHVMのアーキテクチャの話をしておこう。
Hackの型チェッカー（hh_client / hh_server）は、型推論とサブタイピングのグラフを構築する際、無限ループに陥るリスクを極度に嫌う。何も考えずに自己参照的な型を作ると、型チェッカーが停止不能問題（Halting Problem）の泥沼にはまり、IDEがフリーズするか、次のような残酷なエラーを吐く。
> Type cycle detected.
特に、HHVMのジェネリクス（Generics）と組み合わせた場合、型変数の単一化（Unification）の過程でメモリ消費量が爆発的に跳ね上がる。
だからこそ、我々は「型チェッカーに優しく、かつ実行時オーバーヘッドを生まない再帰構造」のパターンを熟知していなければならない。
—
2. 【アンチパターン】なぜその再帰型はスケールしないのか
実務でよく見かける、最悪な実装例から見ていこう。
// 悪い例：緩い型付けと不完全な構造
<<__Strict>>
namespace HackBestPractices\AntiPattern;
type BadNode = shape(
‘value’ => string,
‘children’ => ?vec
);
なぜこれがダメなのか？
1. `mixed` への依存: 子ノードの型が保証されないため、アクセスするたびに手動での型アサーションや `is` チェックが必要になり、Strict Modeの意味が完全に失われる。
2. 実行時コスト: 毎回ボクシング（Boxing）が発生し、HHVMの最適化パス（JIT）が効かなくなる。
—
3. 【プロダクション・パターン】完全型安全なツリー構造の実装
では、HHVMの型チェッカーを完璧に手なずけ、かつ美しいIDE補完を実現するプロダクションコードを見てほしい。ここでは、エンタープライズ環境のDSL（ドメイン特化言語）パーサーやUIコンポーネントツリーを想定した「Discriminated Union（代数的データ型）を用いた再帰的AST構造」を実装する。
<<__Strict>>
namespace HackBestPractices\Production;
/
- 表現力の高い再帰的ノードの定義
- 葉（Leaf）と節（Branch）を完全に型レベルで分離する
/
enum NodeType: string {
LEAF = ‘leaf’;
BRANCH = ‘branch’;
}
/
- リーフノードのシェイプ
/
type LeafNode = shape(
‘type’ => NodeType,
‘value’ => string,
);
/
- ブランチノードのシェイプ
- 再帰型を定義する際は、配列の要素型を明確なAliasまたはUnionにする
/
type BranchNode = shape(
‘type’ => NodeType,
‘label’ => string,
‘children’ => vec
);
/
- 再帰的代数的データ型（Recursive Sum Type）
- Hackではtypeエイリアスを通じた相互再帰が強力にサポートされている
/
type ASTNode =
| LeafNode
| BranchNode;
final class ASTValidator {
/
- 再帰構造を安全に走査し、すべての値を集約するリファレンス実装
- パターンマッチング（switch）により、型チェッカーが網羅性を保証する
/
public static function flattenTree(ASTNode $node): vec
// ‘type’ キーによる安全なディスパッチ
switch ($node[‘type’]) {
case NodeType::LEAF:
// このスコープでは $node は LeafNode として静的保証される
return vec[$node[‘value’]];
case NodeType::BRANCH:
// このスコープでは $node は BranchNode として静的保証される
$acc = vec[$node[‘label’]];
foreach ($node[‘children’] as $child) {
// 再帰呼び出し
$acc = Vec\concat($acc, self::flattenTree($child));
}
return $acc;
}
}
}
この設計が優れている理由
1. 完全な網羅性（Exhaustiveness）:
`switch` 文で `NodeType` を判定しているため、将来的に新しいノードタイプを追加した際、対応するケースを書き忘れると型チェッカーがビルドを即座に落とす。これにより「実行時までバグに気づかない」という最悪のシナリオを防げる。
2. メモリ効率とJIT最適化:
`vec
—
4. 非同期API連携と再帰的ペイロードのハンドリング
Webエンジニアであれば、GraphQLのネストしたレスポンスや、階層化された組織ツリーのJSONを非同期で受け取るシチュエーションが多いだろう。
Async APIから返ってきた `json_decode()` の結果を、安全に再帰型へマッピングするイディオムを共有する。
<<__Strict>>
namespace HackBestPractices\AsyncAPI;
type OrganizationUnit = shape(
‘id’ => int,
‘name’ => string,
‘sub_units’ => vec
);
class OrgService {
/
- 外部APIから再帰的なJSONデータを受け取り、型安全にパースする
/
public async function fetchOrganizationTreeAsync(int $rootId): Awaitable
// 実際の非同期HTTPクライアント呼び出しの模倣
$rawJson = await $this->httpClient->getJsonAsync(“/orgs/{$rootId}”);
// 境界値での型アサーション（Runtime Validation）
returnShapes\org_unit($rawJson);
}
}
> Architect’s Note:
> ネットワーク境界（外部入力）から内部に入る瞬間だけは、`Shapes::idx` や外部バリデーションライブラリを用いてランダムな型を `OrganizationUnit` へキャストする必要がある。しかし、一度バリデーションを通過した瞬間から、その下流のすべてのロジックは100%型安全な世界（Strict Zone）に守られる。この境界線のデザインこそが、シニアエンジニアの腕の見せ所だ。
—
5. パフォーマンス上の注意点と限界
最後に、HackのRecursive Typesを使う上でのハードルについても触れておこう。
- 深さの制限（Recursion Depth）:
無限にネストするJSONを受け取る可能性がある場合、再帰関数の呼び出し回数がHHVMのコールスタック上限（Call Stack Limit）を直撃し、`Stack overflow` を引き起こす恐れがある。
対策: 深い階層を持つツリーを処理する場合は、再帰ではなく、キュー（Queue）やスタック（Stack）を用いたイテレーティブ（非再帰）な幅優先・深さ優先探索に書き換えること。型定義自体は再帰的であっても、アルゴリズム側を平坦化するのがプロダクションコードの鉄則だ。
まとめ
Hack言語の静的型システムは、お前たちが適当に書いたコードを許容するほど甘くはない。しかし、その厳格さに準拠した設計を行った瞬間、コードベースはドキュメントすら不要なほど堅牢で、変更に強く、驚異的に高速なシステムへと生まれ変わる。
「動けばいい」というアマチュアの思考を捨て、型チェッカーを味方につけた美しい再帰構造を、今日のコードレビューから実践せよ。