第15章: パッケージとモジュール - 機械レベルの深層理解

学習目標

この章を終えると、以下ができるようになります：

go.mod/go.sumファイルの内部構造と処理フローを理解できる
MVS（Minimal Version Selection）アルゴリズムの動作原理を説明できる
依存解決グラフの構築と探索アルゴリズムを理解できる
import cycleの検出メカニズムを理解できる
パッケージ初期化順序の決定アルゴリズムを理解できる

🔑 go.modファイルの内部構造

ファイルフォーマットとパーサー

go.modファイルは独自のDSL（Domain Specific Language）で記述されています。コンパイラは以下の手順でパースします。

go.modパース処理フロー:

1. Lexical Analysis (字句解析)
   ┌─────────────────────────────┐
   │ ソーステキスト              │
   │ "module example.com/foo"    │
   └──────────┬──────────────────┘
              ↓
   ┌─────────────────────────────┐
   │ トークン列生成              │
   │ [MODULE, STRING, NEWLINE]   │
   └──────────┬──────────────────┘

2. Syntax Analysis (構文解析)
   ┌─────────────────────────────┐
   │ AST (抽象構文木) 構築       │
   │   ModFile                   │
   │   ├─ Module                 │
   │   ├─ Go                     │
   │   ├─ Require                │
   │   └─ Replace                │
   └──────────┬──────────────────┘

3. Semantic Analysis (意味解析)
   ┌─────────────────────────────┐
   │ バージョン検証              │
   │ パス検証                    │
   │ 循環依存検出                │
   └──────────┬──────────────────┘

4. Build List Construction
   ┌─────────────────────────────┐
   │ MVSアルゴリズム実行         │
   │ 最終的な依存リスト生成      │
   └─────────────────────────────┘

go.modの内部データ構造

Goコンパイラ内部では、go.modは以下のような構造体で表現されます：

// cmd/go/internal/modfile/rule.go の簡略版
type File struct {
    Module  *Module      // module ディレクティブ
    Go      *Go          // go ディレクティブ
    Require []*Require   // require ディレクティブのリスト
    Replace []*Replace   // replace ディレクティブのリスト
    Exclude []*Exclude   // exclude ディレクティブのリスト
    Retract []*Retract   // retract ディレクティブのリスト
    Syntax  *FileSyntax  // 元の構文情報（コメント保持）
}

type Module struct {
    Mod     module.Version  // モジュールパスとバージョン
    Syntax  *Line           // 元の行情報
}

type Require struct {
    Mod      module.Version  // 依存モジュール
    Indirect bool            // 間接依存か？
    Syntax   *Line
}

type Replace struct {
    Old module.Version  // 置換元
    New module.Version  // 置換先
    Syntax *Line
}

メモリレイアウト例：

File構造体のメモリレイアウト (64bit システム):

0x00: Module    (8 bytes) → *Module構造体へのポインタ
0x08: Go        (8 bytes) → *Go構造体へのポインタ
0x10: Require   (24 bytes) → スライスヘッダ
      ├─ ptr   (8 bytes)
      ├─ len   (8 bytes)
      └─ cap   (8 bytes)
0x28: Replace   (24 bytes) → スライスヘッダ
0x40: Exclude   (24 bytes) → スライスヘッダ
0x58: Retract   (24 bytes) → スライスヘッダ
0x70: Syntax    (8 bytes) → *FileSyntax構造体へのポインタ

合計: 120 bytes (ポインタやスライスヘッダのみ)

🔑 ディレクティブの処理順序

go.modファイルのディレクティブは以下の順序で処理されます：

処理順序:

1. module ディレクティブ
   ┌────────────────────────────┐
   │ メインモジュールパス設定   │
   │ 全体の名前空間確立         │
   └────────────────────────────┘

2. go ディレクティブ
   ┌────────────────────────────┐
   │ 言語バージョン確認         │
   │ セマンティクス決定         │
   └────────────────────────────┘

3. exclude ディレクティブ
   ┌────────────────────────────┐
   │ 除外バージョンセット構築   │
   │ 後の依存解決で参照         │
   └────────────────────────────┘

4. replace ディレクティブ
   ┌────────────────────────────┐
   │ 置換マップ構築             │
   │ 依存解決時に適用           │
   └────────────────────────────┘

5. require ディレクティブ
   ┌────────────────────────────┐
   │ 依存グラフ構築開始         │
   │ MVSアルゴリズム準備        │
   └────────────────────────────┘

6. retract ディレクティブ
   ┌────────────────────────────┐
   │ 撤回バージョン記録         │
   │ 他のモジュールへの警告     │
   └────────────────────────────┘

🔑 go.sumファイルの内部構造

チェックサムの計算方法

go.sumファイルには、各モジュールの2種類のチェックサムが記録されます：

go.sumエントリの構造:

github.com/gorilla/mux v1.8.0 h1:i40aqfkR1h2SlN9hojwV5ZA91wcXFOvkdNIeFDP5koI=
github.com/gorilla/mux v1.8.0/go.mod h1:DVbg23sWSpFRCP0SfiEN6jmj59UnW/n46BH5rLB71So=

形式:
<module_path> <version> h1:<base64_hash>

h1: SHA-256ハッシュアルゴリズム

チェックサム計算アルゴリズム：

モジュールコンテンツのハッシュ計算:

1. モジュールファイルツリー構築
   ┌──────────────────────────┐
   │ .goファイルリスト作成    │
   │ 辞書順ソート             │
   │ go.modファイル含む       │
   └──────┬───────────────────┘

2. 正規化
   ┌──────────────────────────┐
   │ ファイルパス正規化       │
   │ /を区切り文字に統一      │
   │ .gitなどの除外           │
   └──────┬───────────────────┘

3. ハッシュ計算
   ┌──────────────────────────┐
   │ SHA-256初期化            │
   │ for each file:           │
   │   hash.Write(path)       │
   │   hash.Write(content)    │
   │ digest = hash.Sum()      │
   └──────┬───────────────────┘

4. エンコーディング
   ┌──────────────────────────┐
   │ base64エンコード         │
   │ "h1:" プレフィックス付与 │
   └──────────────────────────┘

疑似コード:
func computeModuleHash(files []File) string {
    h := sha256.New()

    // ファイルを辞書順でソート
    sort.Slice(files, func(i, j int) bool {
        return files[i].Path < files[j].Path
    })

    // 各ファイルをハッシュに追加
    for _, file := range files {
        h.Write([]byte(file.Path))
        h.Write([]byte{0})  // 区切り
        h.Write(file.Content)
        h.Write([]byte{0})
    }

    digest := h.Sum(nil)
    return "h1:" + base64.StdEncoding.EncodeToString(digest)
}

go.sumの検証フロー

チェックサム検証プロセス:

1. モジュールダウンロード
   ┌──────────────────────────────┐
   │ proxy.golang.orgから取得     │
   │ またはVCS (git等)から取得    │
   └──────────┬───────────────────┘
              ↓
2. ローカルハッシュ計算
   ┌──────────────────────────────┐
   │ ダウンロードしたファイル群   │
   │ をSHA-256でハッシュ化        │
   └──────────┬───────────────────┘
              ↓
3. go.sum照合
   ┌──────────────────────────────┐
   │ 既存のgo.sumに記録あり？     │
   │ YES → ハッシュ値比較         │
   │ NO  → 次のステップへ         │
   └──────────┬───────────────────┘
              ↓
4. チェックサムDB照会
   ┌──────────────────────────────┐
   │ sum.golang.orgへクエリ       │
   │ GET /lookup/<mod>@<version>  │
   └──────────┬───────────────────┘
              ↓
5. 検証と記録
   ┌──────────────────────────────┐
   │ 一致 → go.sumに追記          │
   │ 不一致 → エラー終了          │
   │ SECURITY WARNING             │
   └──────────────────────────────┘

💡 セキュリティポイント: go.sumは改ざん検出のための重要な仕組みです。攻撃者がモジュールコードを変更しても、チェックサムの不一致で検出されます。

🔑 MVS (Minimal Version Selection) アルゴリズム詳解

MVSの理論的基盤

MVSは、依存関係解決における決定論的アルゴリズムです。他の多くのパッケージマネージャー（npm, pip, cargo等）とは根本的に異なるアプローチを取ります。

設計原則：

1. 再現性 (Reproducibility)
   同じgo.modからは常に同じビルドリストを生成

2. 最小性 (Minimality)
   全ての制約を満たす最も古いバージョンを選択

3. 単調性 (Monotonicity)
   依存を追加しても既存の依存バージョンは下がらない

MVSアルゴリズムの詳細実装

MVSアルゴリズム擬似コード:

type Module struct {
    Path    string
    Version string
}

type BuildList struct {
    modules map[string]string  // path → version
}

// MVSのコア関数
func BuildList(main Module) (*BuildList, error) {
    // 1. 全ての要求されたバージョンを収集
    requirements := make(map[string][]string)
    visited := make(map[Module]bool)

    collectRequirements(main, requirements, visited)

    // 2. 各モジュールについて最大バージョンを選択
    result := &BuildList{
        modules: make(map[string]string),
    }

    for path, versions := range requirements {
        maxVer := findMax(versions)
        result.modules[path] = maxVer
    }

    return result, nil
}

func collectRequirements(
    mod Module,
    reqs map[string][]string,
    visited map[Module]bool,
) {
    // 循環検出
    if visited[mod] {
        return
    }
    visited[mod] = true

    // このモジュールのgo.modを読み取る
    modFile := loadModFile(mod)

    // 各requireディレクティブを処理
    for _, req := range modFile.Require {
        // excludeディレクティブをチェック
        if isExcluded(req) {
            continue
        }

        // replaceディレクティブを適用
        if replacement := getReplacement(req); replacement != nil {
            req = replacement
        }

        // 要求を記録
        reqs[req.Path] = append(reqs[req.Path], req.Version)

        // 再帰的に依存を収集
        collectRequirements(req, reqs, visited)
    }
}

func findMax(versions []string) string {
    max := versions[0]
    for _, v := range versions[1:] {
        if compareVersions(v, max) > 0 {
            max = v
        }
    }
    return max
}

// セマンティックバージョニングの比較
func compareVersions(v1, v2 string) int {
    // v1.2.3 → [1, 2, 3]
    parts1 := parseVersion(v1)
    parts2 := parseVersion(v2)

    for i := 0; i < 3; i++ {
        if parts1[i] > parts2[i] {
            return 1  // v1 > v2
        } else if parts1[i] < parts2[i] {
            return -1  // v1 < v2
        }
    }
    return 0  // v1 == v2
}

🔑 MVS実行の具体例（ステップバイステップ）

依存グラフ例:

main module
├─ A@v1.2
│  ├─ D@v1.3
│  └─ E@v1.1
├─ B@v1.1
│  ├─ D@v1.4
│  └─ F@v1.0
└─ C@v1.0
   └─ E@v1.2


ステップ1: 初期化
┌─────────────────────────────┐
│ requirements = {}           │
│ visited = {}                │
│ result = {}                 │
└─────────────────────────────┘


ステップ2: main moduleを処理
┌─────────────────────────────┐
│ collectRequirements(main)   │
│ requirements = {            │
│   "A": ["v1.2"]            │
│   "B": ["v1.1"]            │
│   "C": ["v1.0"]            │
│ }                           │
└─────────────────────────────┘


ステップ3: A@v1.2を処理
┌─────────────────────────────┐
│ collectRequirements(A@v1.2) │
│ requirements = {            │
│   "A": ["v1.2"]            │
│   "B": ["v1.1"]            │
│   "C": ["v1.0"]            │
│   "D": ["v1.3"]            │
│   "E": ["v1.1"]            │
│ }                           │
└─────────────────────────────┘


ステップ4: B@v1.1を処理
┌─────────────────────────────┐
│ collectRequirements(B@v1.1) │
│ requirements = {            │
│   "A": ["v1.2"]            │
│   "B": ["v1.1"]            │
│   "C": ["v1.0"]            │
│   "D": ["v1.3", "v1.4"] ← │
│   "E": ["v1.1"]            │
│   "F": ["v1.0"]            │
│ }                           │
└─────────────────────────────┘


ステップ5: C@v1.0を処理
┌─────────────────────────────┐
│ collectRequirements(C@v1.0) │
│ requirements = {            │
│   "A": ["v1.2"]            │
│   "B": ["v1.1"]            │
│   "C": ["v1.0"]            │
│   "D": ["v1.3", "v1.4"]    │
│   "E": ["v1.1", "v1.2"] ← │
│   "F": ["v1.0"]            │
│ }                           │
└─────────────────────────────┘


ステップ6: 各モジュールの最大バージョン選択
┌─────────────────────────────┐
│ for each module:            │
│   A: max(["v1.2"]) = v1.2  │
│   B: max(["v1.1"]) = v1.1  │
│   C: max(["v1.0"]) = v1.0  │
│   D: max(["v1.3","v1.4"])  │
│      = v1.4 ✓              │
│   E: max(["v1.1","v1.2"])  │
│      = v1.2 ✓              │
│   F: max(["v1.0"]) = v1.0  │
└─────────────────────────────┘


最終ビルドリスト:
┌─────────────────────────────┐
│ main (current)              │
│ A    v1.2                   │
│ B    v1.1                   │
│ C    v1.0                   │
│ D    v1.4 (v1.3→v1.4昇格)  │
│ E    v1.2 (v1.1→v1.2昇格)  │
│ F    v1.0                   │
└─────────────────────────────┘

MVSの計算量解析

時間計算量:
  O(V + E)
  V: モジュール数 (頂点)
  E: 依存関係数 (辺)

  理由: 各モジュールを1回ずつ訪問し、
        各依存関係を1回ずつ辿る
        (深さ優先探索と同等)

空間計算量:
  O(V)

  理由: requirements マップと
        visited マップが必要
        各モジュールごとに1エントリ

例: 100個のモジュール、平均5個の依存
  V = 100
  E = 500
  O(100 + 500) = O(600) → 線形時間

🔑 依存解決グラフの構築と探索

グラフ表現

依存関係は有向非巡回グラフ (DAG: Directed Acyclic Graph) として表現されます。

内部データ構造:

type DependencyGraph struct {
    nodes map[string]*Node
    edges map[string][]*Edge
}

type Node struct {
    Module  Module
    Version string
}

type Edge struct {
    From     *Node
    To       *Node
    Indirect bool  // 間接依存フラグ
}

メモリレイアウト (概念図):

       main
      /  |  \
     /   |   \
    A    B    C
   / \   |    |
  D   E  D    E
      |  |
      F  F

隣接リスト表現:
nodes["main"] → [A, B, C]
nodes["A"]    → [D, E]
nodes["B"]    → [D, F]
nodes["C"]    → [E]
nodes["D"]    → [F]
nodes["E"]    → [F]
nodes["F"]    → []

グラフ探索アルゴリズム

深さ優先探索 (DFS) による依存収集:

func DFS(graph *DependencyGraph, start *Node) {
    visited := make(map[*Node]bool)
    stack := []*Node{start}

    for len(stack) > 0 {
        // スタックから取り出す
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if visited[node] {
            continue
        }
        visited[node] = true

        // 処理
        processNode(node)

        // 隣接ノードをスタックに追加
        for _, edge := range graph.edges[node.Module.Path] {
            if !visited[edge.To] {
                stack = append(stack, edge.To)
            }
        }
    }
}

実行トレース例:

初期: stack=[main], visited={}

Step 1:
  pop: main
  visited: {main}
  push: [C, B, A]
  stack: [C, B, A]

Step 2:
  pop: A
  visited: {main, A}
  push: [E, D]
  stack: [C, B, E, D]

Step 3:
  pop: D
  visited: {main, A, D}
  push: [F]
  stack: [C, B, E, F]

Step 4:
  pop: F
  visited: {main, A, D, F}
  stack: [C, B, E]

... 続く

🔑 間接依存 (Indirect Dependencies) の検出

間接依存の定義:
  直接requireしていないが、依存チェーンに含まれるモジュール

検出アルゴリズム:

func markIndirectDeps(graph *DependencyGraph, mainMod *Node) {
    // 直接依存をマーク
    directDeps := make(map[string]bool)
    for _, edge := range graph.edges[mainMod.Module.Path] {
        directDeps[edge.To.Module.Path] = true
    }

    // 全依存を収集
    allDeps := make(map[string]bool)
    collectAllDeps(graph, mainMod, allDeps)

    // 間接依存 = 全依存 - 直接依存
    for dep := range allDeps {
        if !directDeps[dep] {
            markAsIndirect(graph, dep)
        }
    }
}

go.modでの表現:

require (
    github.com/A v1.2.0          // 直接依存
    github.com/B v1.1.0          // 直接依存
    github.com/D v1.4.0 // indirect  ← 間接依存マーク
)

🔑 Import Cycle 検出メカニズム

Import Cycleとは

Import Cycleの例:

package a
import "b"

package b
import "c"

package c
import "a"  ← サイクル！

グラフ表現:
a → b → c
↑       ↓
└───────┘

検出アルゴリズム (DFSベース)

func detectCycle(graph *ImportGraph) ([]string, bool) {
    visited := make(map[string]bool)
    recStack := make(map[string]bool)  // 再帰スタック
    parent := make(map[string]string)

    for pkg := range graph.packages {
        if !visited[pkg] {
            if cycle := dfsDetect(pkg, graph, visited, recStack, parent); cycle != nil {
                return cycle, true
            }
        }
    }
    return nil, false
}

func dfsDetect(
    pkg string,
    graph *ImportGraph,
    visited map[string]bool,
    recStack map[string]bool,
    parent map[string]string,
) []string {
    visited[pkg] = true
    recStack[pkg] = true  // 現在の探索パスに追加

    for _, imported := range graph.imports[pkg] {
        if !visited[imported] {
            parent[imported] = pkg
            if cycle := dfsDetect(imported, graph, visited, recStack, parent); cycle != nil {
                return cycle
            }
        } else if recStack[imported] {
            // サイクル発見！
            return buildCyclePath(imported, pkg, parent)
        }
    }

    recStack[pkg] = false  // 探索完了、スタックから削除
    return nil
}

func buildCyclePath(start, end string, parent map[string]string) []string {
    path := []string{end}
    current := end

    for current != start {
        current = parent[current]
        path = append(path, current)
    }

    // 逆順にして返す
    reverse(path)
    return path
}

実行例:

packages: {a, b, c}
imports:
  a → [b]
  b → [c]
  c → [a]

Step 1: pkg=a
  visited: {a}
  recStack: {a}
  imports: [b]

Step 2: pkg=b
  visited: {a, b}
  recStack: {a, b}
  imports: [c]

Step 3: pkg=c
  visited: {a, b, c}
  recStack: {a, b, c}
  imports: [a]

  ここで a は visited かつ recStack に存在
  → サイクル検出！

サイクルパス: [a, b, c, a]

エラーメッセージ:
import cycle not allowed
package a
    imports b
    imports c
    imports a

コンパイラでの検出タイミング

コンパイルフロー:

1. ソースコード解析
   ┌──────────────────────┐
   │ import文パース       │
   │ パッケージ依存収集   │
   └──────┬───────────────┘

2. 依存グラフ構築
   ┌──────────────────────┐
   │ 各パッケージをノード │
   │ importを有向辺       │
   └──────┬───────────────┘

3. サイクル検出
   ┌──────────────────────┐
   │ DFSでグラフ探索      │
   │ 後退辺を検出         │
   └──────┬───────────────┘

4. エラー処理
   ┌──────────────────────┐
   │ サイクルあり？       │
   │ YES → コンパイル中止 │
   │ NO  → 次のフェーズ   │
   └──────────────────────┘

⚠️ 重要: Import cycleはコンパイル時エラーです。実行時ではなく、ビルド時に検出されます。

🔑 パッケージ初期化順序の決定

初期化の段階

パッケージ初期化の4段階:

1. インポートされた全パッケージの初期化（再帰的、深さ優先）
2. パッケージレベル変数の初期化（依存順序）
3. init()関数の実行（ファイル名順）
4. main()関数の実行（mainパッケージのみ）


具体例:

// package config
var DatabaseURL = os.Getenv("DB_URL")  // ステップ2
func init() {                          // ステップ3
    log.Println("config initialized")
}

// package database
import "myapp/config"                  // ステップ1

var DB = connectDB(config.DatabaseURL) // ステップ2

func init() {                          // ステップ3
    DB.Ping()
}

// package main
import "myapp/database"                // ステップ1

func main() {                          // ステップ4
    database.DB.Query(...)
}

初期化順序決定アルゴリズム

type Package struct {
    Name         string
    Imports      []*Package
    Vars         []*VarDecl
    InitFuncs    []*Func
    initialized  bool
}

type VarDecl struct {
    Name     string
    InitExpr Expr
    Deps     []*VarDecl  // この変数が依存する他の変数
}

// トポロジカルソートを使った初期化順序決定
func determineInitOrder(packages []*Package) []*Package {
    order := []*Package{}
    visited := make(map[*Package]bool)

    var visit func(*Package)
    visit = func(pkg *Package) {
        if visited[pkg] || pkg.initialized {
            return
        }
        visited[pkg] = true

        // 依存パッケージを先に初期化
        for _, imp := range pkg.Imports {
            visit(imp)
        }

        // パッケージレベル変数の初期化順序を決定
        varOrder := determineVarInitOrder(pkg.Vars)

        // このパッケージを順序リストに追加
        order = append(order, pkg)
        pkg.initialized = true
    }

    for _, pkg := range packages {
        visit(pkg)
    }

    return order
}

// 変数初期化順序の決定（依存グラフのトポロジカルソート）
func determineVarInitOrder(vars []*VarDecl) []*VarDecl {
    order := []*VarDecl{}
    visited := make(map[*VarDecl]bool)
    recStack := make(map[*VarDecl]bool)

    var visit func(*VarDecl) error
    visit = func(v *VarDecl) error {
        if visited[v] {
            return nil
        }
        if recStack[v] {
            return errors.New("initialization cycle detected")
        }

        recStack[v] = true

        // 依存変数を先に訪問
        for _, dep := range v.Deps {
            if err := visit(dep); err != nil {
                return err
            }
        }

        recStack[v] = false
        visited[v] = true
        order = append(order, v)
        return nil
    }

    for _, v := range vars {
        visit(v)
    }

    return order
}

実行トレース例

パッケージ構成:

main
├─ import "database"
└─ import "logger"

database
├─ import "config"
└─ import "logger"

logger
└─ import "config"

config
└─ (標準ライブラリのみ)


依存グラフ (逆方向、初期化順):

config
  ↑
  ├─ logger
  │    ↑
  │    └─ main
  └─ database
       ↑
       └─ main


初期化順序決定 (DFS):

Step 1: visit(main)
  main.Imports = [database, logger]
  visit(database)

Step 2: visit(database)
  database.Imports = [config, logger]
  visit(config)

Step 3: visit(config)
  config.Imports = []
  order += [config]
  config.initialized = true

Step 4: (戻る) visit(database)
  visit(logger)

Step 5: visit(logger)
  logger.Imports = [config]
  visit(config) → すでに初期化済み、スキップ
  order += [logger]
  logger.initialized = true

Step 6: (戻る) visit(database)
  全ての依存が初期化済み
  order += [database]
  database.initialized = true

Step 7: (戻る) visit(main)
  visit(logger) → すでに初期化済み、スキップ
  order += [main]
  main.initialized = true

最終初期化順序:
[config, logger, database, main]


実行時の動作:

1. config パッケージ
   ├─ パッケージ変数初期化
   └─ init()実行

2. logger パッケージ
   ├─ パッケージ変数初期化
   └─ init()実行

3. database パッケージ
   ├─ パッケージ変数初期化
   └─ init()実行

4. main パッケージ
   ├─ パッケージ変数初期化
   ├─ init()実行
   └─ main()実行 ← プログラム開始

変数初期化の依存解析

パッケージ内変数の初期化順序:

package example

// 依存関係:
// c → b (bがcを使う)
// b → a (aがbを使う)

var a = b + 1     // 依存: b
var b = c * 2     // 依存: c
var c = 42        // 依存: なし

依存グラフ:
c (level 0)
↓
b (level 1)
↓
a (level 2)

初期化順序: [c, b, a]

実行:
1. c = 42
2. b = 42 * 2 = 84
3. a = 84 + 1 = 85


複雑な例（関数呼び出し）:

var (
    config = loadConfig()        // 依存: なし
    db     = connectDB(config)   // 依存: config
    cache  = newCache(db)        // 依存: db
    server = newServer(db, cache) // 依存: db, cache
)

依存グラフ:
        config (level 0)
          ↓
         db (level 1)
          ↓
        cache (level 2)
          ↓
        server (level 3)

初期化順序: [config, db, cache, server]

🔑 初期化サイクルの検出

初期化サイクルの例（コンパイルエラー）:

var a = b + 1
var b = a + 1  ← サイクル！

依存グラフ:
a → b
↑   ↓
└───┘

エラーメッセージ:
initialization cycle:
    a refers to b
    b refers to a


検出アルゴリズム（DFS with recStack）:

func detectInitCycle(vars []*VarDecl) []string {
    visited := make(map[*VarDecl]bool)
    recStack := make(map[*VarDecl]bool)

    for _, v := range vars {
        if cycle := dfs(v, visited, recStack); cycle != nil {
            return cycle
        }
    }
    return nil
}

func dfs(v *VarDecl, visited, recStack map[*VarDecl]bool) []string {
    if recStack[v] {
        return []string{v.Name}  // サイクル発見
    }
    if visited[v] {
        return nil
    }

    visited[v] = true
    recStack[v] = true

    for _, dep := range v.Deps {
        if cycle := dfs(dep, visited, recStack); cycle != nil {
            return append(cycle, v.Name)
        }
    }

    recStack[v] = false
    return nil
}

🔑 go getの内部動作フロー

モジュール取得の完全なフロー

go get github.com/gorilla/mux@v1.8.0 の実行:

Phase 1: バージョン解決
┌────────────────────────────────────┐
│ 1. バージョン文字列パース          │
│    v1.8.0 → (major:1, minor:8, patch:0) │
│ 2. モジュールパス検証              │
│    github.com/gorilla/mux          │
│    ├─ DNS解決可能？                │
│    └─ VCSルート検出                │
└────────┬───────────────────────────┘

Phase 2: モジュールプロキシ照会
┌────────────────────────────────────┐
│ 3. GOPROXYに問い合わせ             │
│    GET https://proxy.golang.org/   │
│        github.com/gorilla/mux/     │
│        @v/v1.8.0.info              │
│                                    │
│    レスポンス (JSON):              │
│    {                               │
│      "Version": "v1.8.0",         │
│      "Time": "2020-09-23T..."     │
│    }                               │
└────────┬───────────────────────────┘

Phase 3: モジュールダウンロード
┌────────────────────────────────────┐
│ 4. モジュールコンテンツ取得        │
│    GET .../mux/@v/v1.8.0.zip      │
│                                    │
│ 5. ローカルキャッシュに保存        │
│    $GOPATH/pkg/mod/cache/download/ │
│    github.com/gorilla/mux/        │
│    @v/v1.8.0.zip                  │
└────────┬───────────────────────────┘

Phase 4: チェックサム検証
┌────────────────────────────────────┐
│ 6. ローカルでハッシュ計算          │
│    sha256(v1.8.0.zip)             │
│                                    │
│ 7. sum.golang.orgに問い合わせ      │
│    GET /lookup/                    │
│        github.com/gorilla/mux      │
│        @v1.8.0                     │
│                                    │
│ 8. ハッシュ値比較                  │
│    一致 → 続行                     │
│    不一致 → エラー (SECURITY)      │
└────────┬───────────────────────────┘

Phase 5: go.mod更新
┌────────────────────────────────────┐
│ 9. requireディレクティブ追加       │
│    require (                       │
│      github.com/gorilla/mux v1.8.0│
│    )                               │
│                                    │
│ 10. MVSアルゴリズム実行            │
│     既存依存との整合性確認         │
└────────┬───────────────────────────┘

Phase 6: go.sum更新
┌────────────────────────────────────┐
│ 11. チェックサムエントリ追加       │
│     github.com/gorilla/mux v1.8.0 │
│     h1:i40aqfkR1h2SlN...          │
│     github.com/gorilla/mux v1.8.0/│
│     go.mod h1:DVbg23sWSp...       │
└────────────────────────────────────┘

Phase 7: モジュール展開
┌────────────────────────────────────┐
│ 12. zipファイル展開                │
│     $GOPATH/pkg/mod/               │
│     github.com/gorilla/mux@v1.8.0/ │
│     ├─ mux.go                      │
│     ├─ route.go                    │
│     └─ ...                         │
│                                    │
│ 13. 読み取り専用に設定             │
│     chmod -R a-w                   │
└────────────────────────────────────┘

プロキシプロトコル詳細

Module Proxy Protocol (GOPROXY):

ベースURL: https://proxy.golang.org

エンドポイント:

1. モジュールリスト
   GET /<module>/@v/list

   例: GET /github.com/gorilla/mux/@v/list
   レスポンス:
   v1.0.0
   v1.1.0
   v1.8.0

2. バージョン情報
   GET /<module>/@v/<version>.info

   例: GET /github.com/gorilla/mux/@v/v1.8.0.info
   レスポンス (JSON):
   {
     "Version": "v1.8.0",
     "Time": "2020-09-23T15:04:05Z"
   }

3. go.modファイル
   GET /<module>/@v/<version>.mod

   例: GET /github.com/gorilla/mux/@v/v1.8.0.mod
   レスポンス:
   module github.com/gorilla/mux

   go 1.12

4. モジュールZIP
   GET /<module>/@v/<version>.zip

   例: GET /github.com/gorilla/mux/@v/v1.8.0.zip
   レスポンス: バイナリZIPファイル

5. 最新バージョン
   GET /<module>/@latest

   リダイレクト → /@v/<latest>.info

🔑 モジュールキャッシュの構造

$GOPATH/pkg/mod/ の構造:

pkg/mod/
├─ cache/
│  ├─ download/              # ダウンロードキャッシュ
│  │  └─ github.com/
│  │     └─ gorilla/
│  │        └─ mux/
│  │           └─ @v/
│  │              ├─ v1.8.0.info
│  │              ├─ v1.8.0.mod
│  │              ├─ v1.8.0.zip
│  │              └─ v1.8.0.ziphash
│  └─ vcs/                   # VCSキャッシュ (git等)
│     └─ <hash>/
│        └─ .git/
│
└─ github.com/                # 展開されたモジュール
   └─ gorilla/
      └─ mux@v1.8.0/         # バージョン付きディレクトリ
         ├─ mux.go
         ├─ route.go
         ├─ go.mod
         └─ ...

パーミッション:
- cache/download/: read-write
- github.com/gorilla/mux@v1.8.0/: read-only (444)

理由: モジュールの不変性保証
     誤って変更されないように保護

💡 パフォーマンスヒント: モジュールキャッシュは複数のプロジェクト間で共有されます。同じバージョンは一度だけダウンロードされます。

🔑 replace ディレクティブの動作

replaceの内部処理

go.modでのreplace:

module myapp

require (
    github.com/old/module v1.2.3
)

replace github.com/old/module => github.com/new/module v1.0.0

処理フロー:

1. requireディレクティブ読み取り
   ┌─────────────────────────────┐
   │ 依存: github.com/old/module │
   │ バージョン: v1.2.3          │
   └──────────┬──────────────────┘

2. replaceディレクティブ適用
   ┌─────────────────────────────┐
   │ old: github.com/old/module  │
   │ new: github.com/new/module  │
   │ バージョン: v1.0.0          │
   └──────────┬──────────────────┘

3. ビルドリスト更新
   ┌─────────────────────────────┐
   │ 実際に使用するモジュール:   │
   │ github.com/new/module v1.0.0│
   │                             │
   │ (old/moduleは無視)          │
   └─────────────────────────────┘

内部マッピング構造:

type ReplaceMap map[module.Version]module.Version

replaceMap := ReplaceMap{
    {"github.com/old/module", "v1.2.3"}:
        {"github.com/new/module", "v1.0.0"},
}

// モジュール解決時
func resolve(req module.Version) module.Version {
    if replacement, ok := replaceMap[req]; ok {
        return replacement
    }
    return req
}

ローカルパスへのreplace

ローカル開発でのreplace:

module myapp

require (
    github.com/mylib v1.0.0
)

replace github.com/mylib => ../mylib


ファイルシステム構造:

workspace/
├─ myapp/
│  ├─ go.mod (replace使用)
│  └─ main.go
└─ mylib/
   ├─ go.mod
   └─ lib.go

処理:

1. インポート解決時
   import "github.com/mylib"

2. replaceディレクティブチェック
   github.com/mylib → ../mylib

3. 相対パス解決
   myapp/ + ../mylib = workspace/mylib/

4. ローカルファイルシステムから読み込み
   (プロキシやキャッシュを経由しない)

5. バージョン情報
   go.modに記載されたバージョンは無視
   ディレクトリの内容を直接使用

🔑 excludeディレクティブの動作

excludeの使用例:

module myapp

require (
    github.com/somelib v1.0.0
)

exclude github.com/badlib v0.5.0

動作:

1. 依存解決中
   somelib v1.0.0 が badlib v0.5.0 を要求

2. excludeチェック
   ┌─────────────────────────────┐
   │ badlib v0.5.0 は除外対象？  │
   │ → はい                      │
   └──────────┬──────────────────┘

3. 代替バージョン選択
   ┌─────────────────────────────┐
   │ badlib の他のバージョン検索 │
   │ v0.4.0, v0.6.0 が存在       │
   │                             │
   │ v0.6.0 を選択 (より新しい)  │
   └─────────────────────────────┘

4. ビルドリスト
   github.com/somelib v1.0.0
   github.com/badlib v0.6.0  ← v0.5.0から変更

疑似コード:

func selectVersion(module string, requestedVer string) string {
    if isExcluded(module, requestedVer) {
        // 除外されているので代替を探す
        versions := listAvailableVersions(module)

        // 除外されていないバージョンでフィルタ
        validVersions := filter(versions, func(v string) bool {
            return !isExcluded(module, v)
        })

        // 最も近いバージョンを選択
        return findBestMatch(validVersions, requestedVer)
    }
    return requestedVer
}

⚠️ 重要: excludeは自分のモジュールにのみ効果があります。依存先のexcludeは無視されます。

自己確認問題

基礎レベル

go.modファイルは内部的にどのようなデータ構造で表現されますか？主要なフィールドを3つ挙げてください。

go.sumファイルに記録される2種類のチェックサムは何ですか？それぞれ何のハッシュですか？

MVSアルゴリズムで、モジュールAがDependency X v1.3を要求し、モジュールBがDependency X v1.5を要求する場合、どちらのバージョンが選ばれますか？その理由も説明してください。

パッケージ初期化の4つの段階を順番に述べてください。

import cycleはいつ検出されますか？（コンパイル時 or 実行時）

中級レベル

go.modファイルのパース処理は何段階に分かれていますか？各段階で何が行われますか？

チェックサムの計算時、ファイルはどのような順序でハッシュに追加されますか？なぜその順序が重要ですか？

MVSアルゴリズムの時間計算量はO(V+E)ですが、VとEは何を表しますか？

import cycle検出アルゴリズムで使用される「recStack」の役割は何ですか？

パッケージレベル変数の初期化順序はどのように決定されますか？使用されるアルゴリズムの名前を答えてください。

上級レベル

go getコマンドは内部的に何個のフェーズに分かれていますか？各フェーズの目的を簡潔に説明してください。

replaceディレクティブとexcludeディレクティブの動作の違いを、依存解決の観点から説明してください。

モジュールプロキシプロトコルで、バージョン一覧を取得するエンドポイントのパスは何ですか？

間接依存（indirect dependencies）はどのように検出されますか？アルゴリズムの概要を説明してください。

変数初期化時にサイクルが検出された場合、コンパイラはどのようなエラーメッセージを出力しますか？具体例を示してください。

実践的思考問題

なぜGoはMVSアルゴリズムを採用したのですか？npmやpipの依存解決アルゴリズムと比較して、どのような利点がありますか？

モジュールキャッシュ($GOPATH/pkg/mod/)のパーミッションが読み取り専用に設定される理由を、モジュールシステムの設計思想から説明してください。

大規模なモノレポ（monorepo）で多数の内部パッケージがある場合、import cycle検出のパフォーマンスはどのような要因に影響されますか？

まとめ

この章では、Goのパッケージとモジュールシステムの内部動作を機械レベルで学びました。

🔑 重要ポイント：

go.mod/go.sumの内部構造

- 独自DSLのパース処理（字句解析→構文解析→意味解析） - チェックサムによる改ざん検出 - SHA-256ハッシュとbase64エンコーディング

MVSアルゴリズム

- 決定論的な依存解決 - O(V+E)の線形時間計算量 - 最小バージョン選択原理

依存解決グラフ

- DAG（有向非巡環グラフ）表現 - DFSによる探索 - 間接依存の検出

Import Cycle検出

- DFS + 再帰スタック - 後退辺の検出 - コンパイル時エラー

パッケージ初期化順序

- トポロジカルソート - 依存関係の解析 - 初期化サイクルの検出

💡 実践的洞察：

モジュールシステムは再現性と決定性を最優先に設計されている
セキュリティはチェックサムDBによって分散的に保証される
コンパイル時の静的解析により、多くのエラーを早期に検出できる

次の章では、Goのtestingパッケージとテスト駆動開発について、特にテストバイナリのビルドプロセスとカバレッジ計測の内部メカニズムを学びます。