【実務・中級編】『Recursive Types』の定義と型チェッカーの制限：再帰的なデータ構造を安全に扱う方法 – Hack言語 コア・静的型システムとHHVMのアーキテクチャ解析バイブル

Hackを掌握する極限の知見：Recursive Typesの深淵とHHVM型チェッカーの調教法

コードレビューをしていて、最もエンジニアの「言語理解度の浅さ」が露呈する瞬間はどこか知っているか？ それは、ツリー構造やグラフ構造といった再帰的データ構造（Recursive Types）を実装する際、型チェッカーの警告に怯えて `mixed` 型や `dynamic` 型という名の「思考停止のゴミ箱」に逃げ込んだコードを見たときだ。

HHVM（HipHop Virtual Machine）の心臓部である静的型チェッカーは、厳格なモード（`<<____EnableUnstableFeatures('rust_enums')>>` や Strict Mode）において、無限に深化する型の解決を検知し、コンパイル時エラーを吐く。あるいは最悪の場合、型推論のループに陥り、CIのビルド時間をドブに捨てることになる。

今回は、Hack言語の厳格な静子型システムの裏側を暴き、再帰的データ構造を「安全に、美しく、そしてHHVMのJITコンパイラを唸らせるほど高速に」実装するための極限の知見を授けよう。

—

1. なぜ素朴な再帰型はHHVMの型チェッカーを破滅させるのか？

まずは、実務でよくあるアンチパターンから見ていこう。例えば、JSONのような任意の入れ子構造や、組織の階層ツリーを表現したいとする。

// 【悪夢のアンチパターン】これはいけない
<>
namespace HackExpert\AntiPattern;

class Node {
public function __construct(
public string $name,
// おっと、自分自身を型として使いたいが…
public ?Vector $children = null,
) {}
}

このコード、一見すると動くように見える。だが、もしこれがより複雑なジェネリックな再帰、例えば「ノードが任意のペイロードを持ち、かつ自己参照する」ような構造になった途端、HHVMの型チェッカー（`hh_client`）は無限再帰の恐怖に震えだす。

特に、Union Types（直和型）やGenericsと組み合わせた再帰型は、型チェッカーのグラフ解決アルゴリズムに負荷をかけ、次のようなエラーを引き起こす。
> Exceeded maximum recursion depth while inferring types.

HHVMはC++製であり、メモリ効率と実行速度の最適化の極限を追求している。型チェッカーに無限の解釈の余地を残す定義は、開発体験（DX）を殺すだけでなく、ランタイムの最適化をも阻害するのだ。

—

2. 解決策：コンテナの抽象化と「不変性（Immutability）」の徹底

この限界を突破し、プロダクション環境で耐えうる堅牢なツリー構造を構築するには、以下の3つの原則を守らなければならない。

1. `<<__Const>>` アノテーションによるメモリ効率と不変性の保証
2. Nullableな自己参照を隠蔽するファクトリーメソッドの活用
3. ジェネリクス（Generics）を用いた型安全なペイロードの分離

以下のコードを見てほしい。これが、我々テクニカルリードが現場で推奨する、美しく枯れたプロダクションコードの模範解答だ。

<>
namespace HackExpert\RecursiveTree;

/

• 任意のノードデータを安全に保持する再帰的ツリー構造のコンポーネント。
• HHVMのJIT最適化を最大限に引き出すため、完全な不変（Immutable）データとして設計する。

/
<<__Const>>
final class TreeNode {

/

• @param T $payload このノードが保持する実データ
• @param Vector> $children 子ノードのイミュータブルなコレクション

/
public function __construct(
public T $payload,
public Vector> $children = new Vector(),
) {}

/

• 深さ優先探索（DFS）を行い、条件に合致するノードを型安全に抽出する。
• クロージャの型も完全に推論されるため、呼び出し側でキャストの必要は一切ない。

/
public function find((function(T): bool) $predicate): ?TreeNode {
if ($predicate($this->payload)) {
return $this;
}

foreach ($this->children as $child) {
$found = $child->find($predicate);
if ($found !== null) {
return $found;
}
}

return null;
}

/

• 関数型アプローチでツリーを変形（Map）する。
• 再帰的な構造を維持したまま、新しいツリーを構築する。

/
public function map((function(T): U) $mapper): TreeNode {
$mappedChildren = new Vector();
foreach ($this->children as $child) {
$mappedChildren->add($child->map($mapper));
}