Recursive Typesの極限：Hack静的型チェッカーとHHVMランタイムの深淵
HHVMのコアコミッターとして、これまで数々の言語機能の限界、とりわけ静的型システムの境界線と向き合ってきた。PHPの動的な泥沼から脱却し、厳格な静的型付け（`<<____EntryPoint>>`と`strict`モード）を手に入れたHackは、世界でも稀に見る高速なメガモンスタ言語へと進化を遂げた。
しかし、シニアエンジニアやセキュリティ研究者であるならば、誰もが一度はこの壁にぶぶるはずだ。
「自己参照するデータ構造（Recursive Types）」を厳格な型システムでどう表現し、HHVMのJITコンパイラと型チェッカー（hh_client / hh_server）の検閲をいかにして潜り抜けるか、と。
今回は、ツリー構造やグラフ構造をHackの厳格な世界で安全に、かつメモリ効率良く構築するための極限の知見を公開する。
—
1. Hack型チェッカーにおける「再帰型」のパラドックス
まず、コンパイラ内部の現実を知る必要がある。
TypeScriptやRust、あるいはHaskellであれば、代数的データ型（ADT）やポインタを介して再帰的な型定義は容易だ。しかし、Hack（厳格モード）の型チェッカーは、無限に展開される可能性のある循環型定義に対して極めて保守的である。
例えば、単純に自身の型を持つプロパティを定義しようとすると、型チェッカーの推論エンジンは無限ループの恐怖に直面し、エラーを吐くか、あるいは表現力の限界を迎える。
// 【アンチパターン】これでは型チェッカーが破綻する
<<__Strict>>
namespace HackInternals;
class Node {
// 循環参照を直接型ヒントにすると、型チェッカーが無限再帰の解析に陥るか、
// あるいはコンパイル時にサイズが確定しないというエラーを引き起こす。
public ?Node $left;
public ?Node $right;
}
HHVMのオブジェクトモデル（`ObjectData`）において、プロパティの型が自己参照を持つ場合、型チェッカーは「型の有限性（Type Finiteness）」を証明できなければならない。これを回避するためには、「抽象化のレイヤー（Interface / Shape）」と「コンテナの型消去（Type Erasure / Generics）」を巧みに組み合わせる必要がある。
—
2. 実践：ジェネリクスとインターフェースによる「安全な再帰型」の構築
ツリーやグラフ構造をメモリ上で効率よく、かつ型安全に扱うためのベストプラクティスは、具象クラスではなくインターフェースによる抽象化とジェネリクス（Generics）による境界づけだ。
以下のコードは、HHVMのJIT最適化（PropType hintsのインライン化）を阻害せず、かつ型チェッカーの再帰制限を回避するプロダクションレディな実装である。
<<__Strict>>
namespace HackInternals\DataStructures;
/
- グラフノードの共通インターフェース
- 具象クラスではなくインターフェースに依存することで、型チェッカーの無限再帰を断ち切る。
/
interface IGraphNode
public function getValue(): T;
public function getChildren(): vec
}
/
- 不変（Immutable）なツリーノードの実装
- HHVMのメモリレイアウトを最適化するため、readonlyプロパティを活用する。
/
final class TreeNode
// プリミティブまたは確定した型のみを保持
private T $value;
private vec
public function __construct(T $value, vec
$this->value = $value;
$this->children = $children;
}
public function getValue(): T {
return $this->value;
}
/
- @return vec
- HHVMの vec は連続したメモリ領域に配置されるため、
- リンクリストよりもCPUキャッシュヒット率が劇的に向上する。
/
public function getChildren(): vec
$this->children;
}
}
この設計がHHVMランタイムにとって優れている理由
1. メモリの連続性 (`vec`):
従来のPHP的なポインタチェイン（リンクリスト）は、ヒープ領域あちこちにオブジェクトが散らばり、CPUキャッシュミス（Cache Miss）の嵐を引き起こす。Hackの `vec
2. 型チェッカーの停止性保証:
インターフェース `IGraphNode
—
3. 循環参照とメモリ管理：GCのプレッシャーを極限まで下げる
ツリーやグラフ構造を扱う際、最大の悪夢は「循環参照（Circular References）」によるメモリリークと、それに伴うPHP/HHVMのGarbage Collector（GC）のオーバーヘッドだ。
特に有向グラフ（DAG）や一般のグラフ構造では、ノード同士が互いを指し示すため、単純な参照カウント（Reference Counting）だけではメモリが解放されない。HHVMは強力な世代別GCを持っているが、高スループットなAPIサーバなどではGCの停止時間（Stop-the-world）が致命傷になり得る。
対策：WeakRef または IDベースのグラフ表現
もしグラフ構造に閉路（Cycles）が含まれる可能性がある場合、厳格モードであっても生のオブジェクト参照を巡らせるべきではない。代わりに、「インデクス（ID）による仮想ポインタ方式」を採用する。
<<__Strict>>
namespace HackInternals\Graph;
type NodeId = int;
/
- 閉路を持つ複雑なグラフ構造のためのメモリ最適化モデル
- オブジェクト間のハードリファレンスを排除し、ストレージ（Map）のキーで管理する。
/
final class ArenaGraph
// すべてのノードを単一のベクター（Arena）に集約する
private dict
// 隣接リスト（Adjacency List）をIDの配列で表現
private dict
public function addNode(NodeId $id, T $value): void {
$this->nodes[$id] = $value;
if (!C\contains_key($this->edges, $id)) {
$this->edges[$id] = vec[];
}
}
public function addEdge(NodeId $from, NodeId $to): void {
invariant(C\contains_key($this->nodes, $from), “From node does not exist.”);
invariant(C\contains_key($this->nodes, $to), “To node does not exist.”);
$this->edges[$from][] = $to;
}
public function getNeighbors(NodeId $id): vec
return $this->edges[$id] ?? vec[];
}
}
アーキテクチャ的メリット
- GCからの解放: オブジェクト間の循環参照が完全に消滅するため、HHVMのRC（参照カウント）メカニズムだけでメモリが即座に回収される。GCサイクルの走査コストがゼロになる。
- シリアライゼーションの容易さ: この構造はそのままJSONやバイナリフォーマットにダンプできるため、RPCやIPC（Inter-Process Communication）のペイロードとしても極めて優秀。
—
4. まとめ：Hackの型システムを飼い慣らす
Hackの厳格モードと型チェッカーは、開発者の自由を奪う足枷ではない。むしろ、CPUの物理的限界とメモリの効率性を極限まで引き出すための「羅針盤」である。
再帰的なデータ構造を設計する際は、以下の鉄則を思い出してほしい：
1. 直接的な自己参照型プロパティを避ける（型チェッカーの無限ループを防ぐ）。
2. インターフェースとジェネリクスで境界を抽象化する。
3. 複雑なグラフにはArenaパターン（IDベースの管理）を導入し、HHVMのGC負荷を消し去る。
この領域の挙動を完全に掌握したとき、あなたの書くHackコードは、単なるスクリプト言語の延長ではなく、システムプログラミング言語に匹敵する堅牢性と爆速のパフォーマンスを手に入れることになる。
限界の先へ進め。型チェッカーを味方につけた者だけが、真のHHVMの支配者となれるのだ。