Hackの型推論エンジンが辿るパス：型チェッカーが変数を特定するまでの内部アルゴリズム
HHVM（HipHop Virtual Machine）のアーキテクチャ、そしてHack言語の核心にあるものは、妥協なき「静的型付けの極限追求」だ。動的言語であるPHPの血統を引き継ぎながらも、ミリ秒単位のレイテンシとペタバイト規模のコードベースを支配するため、Hackの型チェッカー（`hh_client` / `hh_server`）は常駐プロセスとしてメモリ上に巨大な型グラフを構築し続けている。
本稿では、日常的にコードを書くシニアエンジニアであっても踏み込むことのない、「Hackの型推論エンジンがソースコードから抽象構文木（AST）を走査し、変数の型を収束させるまでの内部アルゴリズム」の深淵を暴く。
—
1. 永続化型サーバー（`hh_server`）とグラフ構造のメモリモデル
Hackの型チェッカーは、単なるバッチ式の静的解析ツールではない。C++で実装された `hh_server` は、ファイルシステムの変更をインクリメンタルに監視し、依存関係グラフ（Dependency Graph）をメモリ上に常時維持している。
[ Disk: .hack files ]
│ (inotify / watchman)
▼
[ hh_server (C++ Daemon) ]
├── 1. AST Parser (Lexing & Parsing)
├── 2. Tast (Typed AST) Generation
├── 3. Constraint Generation & Type Inference Engine
└── 4. Shared Memory (APC-like internal structures)
型推論の基本単位：Tast（Typed AST）
ソースコードがパースされると、通常のAST（抽象構文木）から、すべての式や変数に型注釈または推論された型が付与された Tast（Typed AST） へと変換される。
型チェッカーの仕事は、このTastのノード間を駆け巡り、型変数（Type Variables）の制約充足問題（Constraint Satisfaction Problem）を解くことに他ならない。
—
2. 型推論アルゴリズムの核心：双方向型推論（Bidirectional Type Checking）と制約系
Hackの型チェッカーは、純粋なボトムアップ型の推論（Hindley-Milner系など）だけを採用しているわけではない。大規模なコードベースにおけるパフォーマンスと、クロージャやジェネリクス（Generics）の複雑性を両立させるため、双方向型推論（Bidirectional Type Checking）をベースにしている。
- 推論（Inference / Synthesis）: 下位の式から型を「導き出す」（例: リテラルや関数呼び出しの戻り値）。
- 検査（Checking / Analysis）: 上位の文脈から期待される型を「押し付ける」（例: 代入先の変数型や関数の引数型）。
内部での型変数のライフサイクル
変数が宣言された瞬間、型チェッカーはその変数に「未解決の型変数（Unresolved Type Variable：例 `$t_1`）」を割り当てる。コードのフローが進むにつ代わって、以下のようなアルゴリズムパスを辿る。
1. 制約の収集（Constraint Generation）:
制御フローグラフ（CFG）に沿って、代入や演算が行われるたびに型変数に対する制約（Upper Bound / Lower Bound）が生成される。
$$\$x \text{ は } T_{\text{int}} \text{ のサブタイプでなければならない } (\$x <: \text{int})$$
2. 単一化（Unification）と制約解決:
局所的なスコープ内での型変数を、具体的な型へと収束（Resolve）させる。
3. エスケープ解析とボックス化の回避:
HHVMのランタイム（JITコンパイラ）へ渡す際、型チェッカーが確定させた厳密な型情報は、バイトコード生成器（Emitter）を通じて、ネイティブなマシン語（x86-64）への最適化ヒント（Type Specialization）として利用される。
—
3. 実践：型チェッカーの限界点と「巧妙なすり抜け」の構造
厳格なStrict Modeであっても、型チェッカーのアルゴリズムが追跡しきれない領域、あるいは意図的に近似せざるを得ない領域が存在する。ここを理解することが、真に堅牢なHackコードを書く境界線となる。
以下のコードを見てほしい。
namespace Hack\Internal\Exploration;
<<__EnforceGlobalEventListeners>>
class TypeInferenceLimits {
// 共変性・反変性と複雑なジェネリクスの交差
public function processMixedData(mixed $input): void {
// 型チェッカーはここで一時的に「mixed」というトップ型に落とし込む
if ($input is shape(‘id’ => int, ‘payload’ => string)) {
// 内部アルゴリズム：Narrowing（型絞り込み）が発動
// $input はこのブロック内でのみ具体的な shape 型として推論される
Shapes::idx($input, ‘payload’);
}
}
// 【危険なアンチパターン】型チェッカーを欺く動的コール
public function executeDynamicInvocation(string $methodName, mixed $arg): mixed {
// call_user_func や動的メソッド呼び出しは、
// 型チェッカーの静的解析パスから外れる（あるいは Any 型に退行する）
// Strict Modeであっても、ここでランタイムのオーバーヘッドが発生する温床となる
return $this->$methodName($arg);
}
}
型絞り込み（Type Narrowing）の限界
`is` 演算子や `As` 演算子による型ガードは、CFGの分岐ごとに型環境（Type Environment）を複製・更新するコストを伴う。
もし、極端にネストした条件分岐や、参照渡し（Hackでは原則禁止だが、オブジェクトの内部ミューテーション経由）が絡むと、型チェッカーは「安全側に倒して（Conservative）」 broader な型（より広い型、最悪の場合は `mixed` や `dynamic`）にフォールバックする。
これが起きると、HHVMのJITコンパイラ側でポリモーフィックなインラインキャッシュ（PIC）への依存が増え、CPUパイプラインのストールやメガモーフィックなディスパッチを引き起こす原因となる。
—
4. HHVMランタイム最適化への直結：型情報がもたらすネイティブコードの極限
型チェッカーが完璧に型を特定できた場合、HHVMのバイトコード（HHBC）はどのように変化するのか。
動的言語（PHP 7/8）では、すべての変数アクセスやメソッド呼び出しのたびに「型ガード（Type Check）」や「ハッシュテーブルルックアップ」がランタイムで実行される。しかし、HackのStrict Modeかつ型チェッカーが完全に型を解決した領域では、以下の最適化がネイティブ層で実行される。
1. ボックス化の排除（Unboxing）:
整数や浮動小数点数が、PHPの汎用コンテナ（`TypedValue`構造体）ではなく、生のマシン語のレジスタ（64bit整数やdouble）として直接扱われる。
2. メソッドディスパッチの静的バインディング化:
仮想メソッドテーブル（vtable）のルックアップをバイパスし、直接アドレスへのジャンプ（Direct Call / Devirtualization）に置き換わる。
[ Hack Source Code ]
│ (Strict Mode & Type Checker)
▼
[ 完全解決された Tast ]
│ (HHVM Emitter)
▼
[ Optimised HHBC (Bytecode) ]
│ (JIT Compiler: 翻訳フェーズ)
▼
[ x86-64 Machine Code: 無駄な型チェックの完全な排除 ]
—
5. チーフアーキテクトからの提言：型チェッカーを味方につける極意
大規模なHackコードベースを破綻させず、かつHHVMのパフォーマンスを極限まで引き出すためには、型チェッカーのアルゴリズムに無駄な計算量を強いてはならない。
- `dynamic` 型の排除: 逃げの `dynamic` や `mixed` は、型チェッカーの単一化プロセスを放棄させ、ランタイムへの負荷を増大させる毒薬である。境界領域（外部APIやデータベースとのI/O）以外では絶対に使用するな。
- 複雑なジェネリクスの制約は浅く保て: 深すぎる再帰的ジェネリクスや、複雑な条件付き型（Conditional Types的アプローチ）は、`hh_server` のメモリ消費量を跳ね上げ、CI/CDパイプラインでの型チェック速度を殺す。
- 「推論に頼るな、明示せよ」の精神: ローカル変数であっても、複雑な式の右辺値を持つ場合は、あえて明示的な型注釈を書くことで、型チェッカーの推論パスの負担を軽減し、意図しない型の広がりを防ぐことができる。
Hackの型システムは、単なるバグ発見器ではない。それは、世界最高速のPHP派生仮想マシンであるHHVMへ与える「究極の最適化マニュフェスト」なのだ。その内部パスを脳内に焼き付け、コンパイラと対話するようにコードを紡ぎ出せ。