# 機能設計書 89-型システムランタイム

## 概要

本ドキュメントは、Julia の型システムランタイム機能の設計を記述する。DataType の構築・キャッシュ管理、メソッドテーブルの操作、ジェネリック関数の多重ディスパッチ、サブタイプ判定のランタイム実装を提供する。

### 本機能の処理概要

型システムランタイムは、Julia の型システムとメソッドディスパッチの基盤をC言語で実装したものであり、実行時の型操作とメソッド解決を担当する。

**業務上の目的・背景**：Julia の型システムはパラメトリック型、Union型、抽象型、具象型から構成される豊かな型階層を持ち、多重ディスパッチにより関数の引数型に基づいてメソッドが選択される。このメカニズムは Julia のプログラミングモデルの根幹であり、パフォーマンスクリティカルなランタイムパスであるため、C言語で実装されている。サブタイプ判定アルゴリズムは Jeff Bezanson の博士論文（section 4.2.2）に基づく。

**機能の利用シーン**：
- 関数呼び出し時のメソッドディスパッチ
- `isa` / `<:` 演算子によるサブタイプ判定
- パラメトリック型の型インスタンス化
- `struct` / `mutable struct` の定義時の DataType 構築

**主要な処理内容**：
1. DataType の構築とキャッシュ: `jl_new_datatype` による型オブジェクトの生成
2. サブタイプ判定: `jl_subtype` による型間の包含関係判定
3. メソッドテーブル管理: メソッドの追加・検索・無効化
4. ジェネリック関数ディスパッチ: 引数型に基づくメソッド選択
5. 型キャッシュ: パラメトリック型の型インスタンスキャッシュ
6. 静的パラメータ推論: メソッドシグネチャからの型パラメータ推定

**関連システム・外部連携**：型推論（No.79）がサブタイプ判定を頻繁に呼び出す。プリミティブ型定義（No.1）で定義された型がランタイムで管理される。コード生成（No.84）がDispatch情報を使用する。

**権限による制御**：特になし。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 本機能はランタイム内部機能であり、直接的なUI画面は存在しない |

## 機能種別

計算処理（ランタイム型システム処理）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| 引数型タプル | jl_value_t* | Yes | ディスパッチ対象の引数型 | 有効な型であること |
| メソッドテーブル | jl_methtable_t* | Yes | 検索対象のメソッドテーブル | - |
| world_counter | size_t | Yes | ワールドカウンタ（メソッド定義のバージョン） | 有効な world age |

### 入力データソース

- 関数呼び出し時の引数オブジェクト
- メソッド定義時の型シグネチャ

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| DataType | jl_datatype_t* | 新しく構築された型オブジェクト |
| Method | jl_method_t* | ディスパッチで選択されたメソッド |
| MethodInstance | jl_method_instance_t* | 型特殊化されたメソッドインスタンス |
| subtype 結果 | int | サブタイプ関係の判定結果（0/1） |

### 出力先

- メソッドキャッシュに登録
- JIT コンパイルへの入力

## 処理フロー

### 処理シーケンス

```
1. メソッドディスパッチ
   └─ 引数型タプルの取得
   └─ メソッドテーブルの検索
   └─ サブタイプマッチングによるメソッド選択
   └─ MethodInstance の取得またはキャッシュ生成
2. サブタイプ判定
   └─ forall_exists_subtype アルゴリズム
   └─ Union 分解とバックトラック
   └─ TypeVar の境界チェック
3. 型インスタンス化
   └─ パラメトリック型のインスタンスキャッシュ検索
   └─ キャッシュミス時の新規 DataType 構築
```

### フローチャート

```mermaid
flowchart TD
    A[関数呼び出し] --> B[引数型タプル取得]
    B --> C[メソッドテーブル検索]
    C --> D{キャッシュヒット?}
    D -->|Yes| E[キャッシュされた MethodInstance を返却]
    D -->|No| F[サブタイプマッチング]
    F --> G{一致するメソッドあり?}
    G -->|Yes| H[MethodInstance 生成]
    G -->|No| I[MethodError を throw]
    H --> J[キャッシュに登録]
    J --> E
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-89-01 | ワールドカウンタ | メソッド定義はワールドカウンタでバージョン管理され、あるworld ageで定義されたメソッドはそれ以降のworldでのみ有効 | メソッドディスパッチ時 |
| BR-89-02 | MAX_UNSPECIALIZED_CONFLICTS | 32を超える重複メソッドがある場合、コンパイルシグネチャはキャッシュに使用されない | メソッド特殊化時 |
| BR-89-03 | 対角線ルール | 型変数が共変位置に2回以上出現し、不変位置に出現しない場合、その型変数は具象型に制限される | サブタイプ判定時 |
| BR-89-04 | max_varargs | Varargs の展開上限は m->max_varargs（指定時）またはヒューリスティクスで決定 | Vararg メソッドのディスパッチ時 |
| BR-89-05 | 型キャッシュ | パラメトリック型のインスタンスはハッシュテーブルでキャッシュされ、max_probe で検索を制限 | 型インスタンス化時 |

### 計算ロジック

型キャッシュのプローブ制限:
```c
#define max_probe(size) ((size) <= 1024 ? 16 : (size) >> 6)
#define h2index(hv, sz) (size_t)((hv) & ((sz)-1))
```

Varargs 展開上限:
```c
max_varargs = max_args + 2 - nargs  // ヒューリスティクス
```

## データベース操作仕様

本機能はデータベースを使用しない。

### 操作別データベース影響一覧

該当なし。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | MethodError | 一致するメソッドが見つからない | Julia レベルの例外として throw |
| - | AmbiguityError | 複数のメソッドが曖昧に一致 | Julia レベルの例外として throw |
| - | StackOverflowError | サブタイプ判定の再帰が深すぎる | 再帰制限による検出 |

### リトライ仕様

該当なし。

## トランザクション仕様

- メソッド定義はワールドカウンタのインクリメントにより原子的に可視化される
- `world_counter_lock` ミューテックスにより排他制御

## パフォーマンス要件

- メソッドディスパッチはホットパスであり、キャッシュヒット時はO(1)であるべき
- サブタイプ判定は最悪ケースで指数的になりうるが、実用的な型に対しては高速
- 型キャッシュの衝突を max_probe で制限して検索時間を制御

## セキュリティ考慮事項

- 型システムのバグはメモリ安全性に影響しうる
- `allow_new_worlds` フラグで新しいワールドの生成を制御可能

## 備考

- サブタイプアルゴリズムの詳細は Jeff Bezanson の博士論文 section 4.2.2 を参照
- `jl_bits_stack_t` は Union のコンポーネント選択を追跡するビットスタック
- `ijl_small_typeof` は16ビットアラインの小型 typeof テーブル（GCと同期）

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | jltypes.c | `src/jltypes.c` | グローバル変数（22-30行目）: sysimg_global, const_globals, internal_global |
| 1-2 | jltypes.c | `src/jltypes.c` | 型キャッシュ定数（33-34行目）: max_probe, h2index マクロ |
| 1-3 | subtype.c | `src/subtype.c` | jl_unionstate_t / jl_bits_stack_t（43-53行目）: Union コンポーネント追跡 |

**読解のコツ**: jltypes.c はジュリアの型システムの中核であり、`typeenv_has` / `layout_uses_free_typevars` などの型環境操作から読み始めるとよい。subtype.c は冒頭コメント（1-21行目）にアルゴリズムの概要が記載されている。

#### Step 2: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | gf.c | `src/gf.c` | jl_get_world_counter（31-37行目）: ワールドカウンタの取得 |
| 2-2 | gf.c | `src/gf.c` | get_max_varargs（50-80行目）: Varargs 展開上限の計算 |
| 2-3 | gf.c | `src/gf.c` | jl_world_counter（28行目）: アトミックなワールドカウンタ |

**主要処理フロー**:
1. **27-28行目**: allow_new_worlds と jl_world_counter のグローバル定義
2. **31-37行目**: jl_get_world_counter: pure_callback 中は ~(size_t)0 を返す
3. **50-80行目**: get_max_varargs: max_varargs の計算ヒューリスティクス

#### Step 3: サブタイプ判定を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | subtype.c | `src/subtype.c` | 冒頭コメント（1-21行目）: アルゴリズムの概要と拡張点 |
| 3-2 | subtype.c | `src/subtype.c` | jl_bits_stack_t（43-46行目）: Union 選択のビットスタック |
| 3-3 | subtype.c | `src/subtype.c` | jl_unionstate_t（48-53行目）: Union 状態の追跡 |

#### Step 4: 型構築を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | jltypes.c | `src/jltypes.c` | typeenv_has / typeenv_has_ne（38-56行目）: 型環境での変数検索 |
| 4-2 | jltypes.c | `src/jltypes.c` | layout_uses_free_typevars（59-80行目）: レイアウトの自由型変数チェック |

### プログラム呼び出し階層図

```
関数呼び出し (runtime)
    |
    +-- jl_apply_generic (gf.c)
    |      +-- メソッドキャッシュ検索
    |      +-- jl_mt_assoc_by_type (型によるメソッド検索)
    |      |      +-- jl_subtype (subtype.c)
    |      |      +-- forall_exists_subtype
    |      +-- jl_specializations_get_linfo (MethodInstance 取得)
    |
    +-- 型インスタンス化 (jltypes.c)
           +-- jl_apply_type
           +-- inst_datatype_inner
           +-- 型キャッシュ検索/挿入
```

### データフロー図

```
[入力]                         [処理]                      [出力]

引数型タプル           --> メソッドキャッシュ検索     --> MethodInstance (ヒット時)
引数型タプル           --> サブタイプマッチング       --> Method (選択結果)
Method + 引数型        --> 静的パラメータ推論         --> MethodInstance (新規)
パラメトリック型 + 引数 --> 型インスタンス化          --> DataType (キャッシュ済み)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| jltypes.c | `src/jltypes.c` | ソース | 型の構築・キャッシュ・Union/UnionAll操作 |
| gf.c | `src/gf.c` | ソース | ジェネリック関数・メソッドテーブル・ディスパッチ |
| subtype.c | `src/subtype.c` | ソース | サブタイプ判定アルゴリズム |
| julia.h | `src/julia.h` | ヘッダ | Julia の型定義（jl_datatype_t 等） |
| julia_internal.h | `src/julia_internal.h` | ヘッダ | 内部API定義 |
| builtin_proto.h | `src/builtin_proto.h` | ヘッダ | 組み込み関数プロトタイプ |
