グラフエンジン：Terraform が依存関係グラフをどのように構築し、走査するか

Terraform のアーキテクチャで最も際立った設計上の決断は、plan・apply・validate・import といったすべての操作を、有向非巡回グラフ (DAG) の走査としてモデル化していることです。互いに依存しないリソースは並列に実行され、依存関係があるリソースはトポロジカル順序で実行されます。このひとつの抽象化によって、Terraform は 1 回の実行で数千ものインフラリソースを安全に管理できるようになっています。

グラフエンジンは 2 つのパッケージに分かれています。internal/dag/ は Terraform に依存しない汎用グラフライブラリを提供し、internal/terraform/ がそれをラップしてドメイン固有の頂点型とグラフトランスフォーマーのパイプラインを実装します。この 2 層がどのように連携しているかを理解することは、plan の挙動のデバッグ、並列処理の理解、そしてコアエンジンのコードを読み解く上で欠かせません。

DAG パッケージ：汎用グラフライブラリ

基盤となるのは、internal/dag/dag.go#L15-L18 で定義されている AcyclicGraph です。

type AcyclicGraph struct {
    Graph
}

AcyclicGraph はベースとなる Graph 型を埋め込み、循環がないことを前提とした（そして検証する）メソッドを追加しています。頂点は interface{} 型であり、DAG パッケージは Terraform のリソースやプロバイダー、その他のドメイン概念を一切知りません。エッジは有向で、依存関係を表します。

classDiagram
    class Graph {
        +vertices Set
        +edges Set
        +Add(Vertex)
        +Remove(Vertex)
        +Connect(Edge)
        +DownEdges(Vertex) Set
        +UpEdges(Vertex) Set
    }
    class AcyclicGraph {
        +Ancestors(vs) Set
        +TransitiveReduction()
        +Validate() error
        +Walk(cb WalkFunc) Diagnostics
    }
    class Walker {
        +Callback WalkFunc
        +Reverse bool
        +Update(g)
        +Wait() Diagnostics
    }
    Graph <|-- AcyclicGraph
    AcyclicGraph ..> Walker : uses

Terraform が利用する主要な操作は以下のとおりです。

• Ancestors() — ある頂点の推移的な依存関係をすべて取得する。ターゲティングで使用される
• TransitiveReduction() — 実行順序を変えずに冗長なエッジを除去してグラフを簡略化する
• Validate() — 循環エッジや自己参照エッジがないかを検証する
• Walk() — Walker を生成して実行する高レベルのエントリーポイント

このような意図的な分離により、DAG パッケージは Terraform 固有の型を一切持ち込まず、単純な文字列頂点を使って独立してテストできます（実際にそうなっています）。

並列ウォーク：Goroutine、Channel、依存関係のシグナリング

internal/dag/walk.go#L39-L68 の Walker 構造体が、並列実行エンジンの本体です。

type Walker struct {
    Callback   WalkFunc
    Reverse    bool
    changeLock sync.Mutex
    vertices   Set
    edges      Set
    vertexMap  map[Vertex]*walkerVertex
    wait       sync.WaitGroup
    diagsMap       map[Vertex]tfdiags.Diagnostics
    upstreamFailed map[Vertex]struct{}
    diagsLock      sync.Mutex
}

Walker は各頂点に対して walkerVertex（88〜119 行目）を生成し、2 つの重要な channel を持たせます。

• DoneCh — この頂点の実行が完了した（成功・失敗を問わず）ときにクローズされる
• DepsCh — 上流の依存関係がすべて完了したときに boolean を受け取る。true はすべて成功、false は少なくとも 1 つが失敗したことを意味する

flowchart TD
    subgraph "Vertex A (no deps)"
        A_exec["Execute callback"] --> A_done["Close DoneCh"]
    end
    subgraph "Vertex B (depends on A)"
        B_wait["Wait on A.DoneCh"] --> B_deps["Receive on DepsCh"]
        B_deps -->|"true: deps OK"| B_exec["Execute callback"]
        B_deps -->|"false: upstream failed"| B_skip["Skip execution"]
        B_exec --> B_done["Close DoneCh"]
        B_skip --> B_done
    end
    A_done -.->|"signals"| B_wait

Walker は頂点ごとに 2 つの goroutine を起動します。ひとつは依存 channel を待機して集約結果を DepsCh に送信するもの、もうひとつは DepsCh から受け取ってコールバックを実行するものです。コメントにあるとおり、合計で V*2 個の goroutine が生成されます。

上流の頂点が失敗すると、下流のすべての頂点は DepsCh で false を受け取り、upstreamFailed に記録されます。これらのエラーは連鎖的な失敗とみなされ、最終的な diagnostic セットから除外されます。エラーメッセージの雪崩を防ぐための、細やかな配慮です。

ヒント： Terraform のデフォルトの並列度は 10 です（internal/terraform/context.go#L146-L148 の NewContext で設定されています）。これは goroutine の数を制限するわけではありません——すべての頂点には goroutine が割り当てられます——が、セマフォによってコールバックを同時に実行できる頂点の数を制限します。これはプロバイダーのレート制限から守るための仕組みです。

Terraform のグラフラッパーとウォークのディスパッチ

internal/terraform/ パッケージは、internal/terraform/graph.go#L19-L28 で独自の Graph 型を使って汎用 DAG をラップしています。

type Graph struct {
    dag.AcyclicGraph
    Path addrs.ModuleInstance
}

この埋め込みにより、Graph は DAG のすべてのメソッドを継承しつつ、モジュールパスと、GraphWalker インターフェースへの橋渡しをする重要な Walk() メソッド（37〜39 行目）を追加しています。

walk() 関数（41〜120 行目以降）がドメイン固有のディスパッチを担います。DAG ウォーカーが各頂点を訪問するたびに、以下の処理が行われます。

1. 頂点が GraphNodeOverridable を実装しているか確認する（テストフレームワークのオーバーライド用）
2. 評価コンテキストのスコープを決定する（グローバル、モジュールインスタンス、または部分展開済みモジュール）
3. 頂点が実装していれば GraphNodeExecutable.Execute() にディスパッチする

頂点インターフェースは豊富な型システムを形成しています。

classDiagram
    class GraphNodeExecutable {
        <<interface>>
        +Execute(EvalContext, walkOperation) Diagnostics
    }
    class GraphNodeReferenceable {
        <<interface>>
        +ReferenceableAddrs() []Referenceable
    }
    class GraphNodeReferencer {
        <<interface>>
        +References() []*Reference
    }
    class GraphNodeModuleInstance {
        <<interface>>
        +Path() ModuleInstance
    }
    class GraphNodeConfigResource {
        <<interface>>
        +ResourceAddr() ConfigResource
    }

NodePlannableResourceInstance のような単一のノード型が、これらのインターフェースを同時に複数実装します。グラフウォークのコードは Go の型アサーションを使って各頂点の能力を動的に検出し、モノリシックなノードインターフェースを必要としない柔軟なディスパッチ機構を実現しています。

BasicGraphBuilder：トランスフォームパイプライン

グラフはミューテーション（変更）のパイプラインを通じて構築されます。internal/terraform/graph_builder.go#L26-L34 の BasicGraphBuilder は、GraphTransformer のステップをスライスで保持しています。

type BasicGraphBuilder struct {
    Steps []GraphTransformer
    Name  string
    SkipGraphValidation bool
}

Build() メソッド（36〜90 行目）はこのスライスを順に走査し、各ステップに対して Transform(g) を呼び出します。

for _, step := range b.Steps {
    if step == nil { continue }
    err := step.Transform(g)
    // ...handle errors...
}

sequenceDiagram
    participant Builder as BasicGraphBuilder
    participant G as Graph
    participant T1 as ConfigTransformer
    participant T2 as ReferenceTransformer
    participant T3 as TransitiveReductionTransformer

    Builder->>T1: Transform(g)
    Note over T1,G: Adds resource vertices from config
    T1-->>G: mutated
    Builder->>T2: Transform(g)
    Note over T2,G: Wires dependency edges from HCL refs
    T2-->>G: mutated
    Builder->>T3: Transform(g)
    Note over T3,G: Removes redundant edges
    T3-->>G: mutated
    Builder->>G: Validate()

各トランスフォーマーはグラフをインプレースで変更します——頂点の追加・削除、エッジの追加、既存ノードの変更などを行います。このミューテーションのパイプラインというパターンは強力で、トランスフォーマーは互いに独立しているため、他のステップに影響を与えずに追加・削除ができます。一方で、グラフの構造はそれ以前のトランスフォーマーの実行順序に依存するため、各グラフビルダーの Steps() メソッドでは順序が慎重に設計されています。

すべてのトランスフォームが完了すると、Build() は g.Validate() を呼び出して循環がないか確認します。検証に失敗した場合、Terraform はグラフ構造をログに記録してエラーを返します。

PlanGraphBuilder：plan グラフの解剖

internal/terraform/graph_builder_plan.go#L30-L135 の PlanGraphBuilder は、planning に使うグラフを生成します。その Steps() メソッド（148〜328 行目）は 20 を超えるトランスフォーマーを返します。実行順序とともに、特に重要なものを示します。

flowchart TD
    CT["ConfigTransformer<br/>Add resource vertices from config"] --> RVT["RootVariableTransformer<br/>Add input variable nodes"]
    RVT --> MVT["ModuleVariableTransformer<br/>Add module variable nodes"]
    MVT --> LT["LocalTransformer<br/>Add local value nodes"]
    LT --> OT["OutputTransformer<br/>Add output value nodes"]
    OT --> ORIT["OrphanResourceInstanceTransformer<br/>Add nodes for state resources missing from config"]
    ORIT --> ST["StateTransformer<br/>Add deposed instance nodes"]
    ST --> AST["AttachStateTransformer<br/>Attach state to resource nodes"]
    AST --> ARC["AttachResourceConfigTransformer<br/>Attach config to resource nodes"]
    ARC --> PT["ProviderTransformer<br/>Wire provider dependencies"]
    PT --> SchemaT["AttachSchemaTransformer<br/>Attach schemas to nodes"]
    SchemaT --> MET["ModuleExpansionTransformer<br/>Handle count/for_each"]
    MET --> RT["ReferenceTransformer<br/>Wire dependency edges from HCL refs"]
    RT --> TT["TargetsTransformer<br/>Prune to targeted resources"]
    TT --> CPRT["CloseProviderTransformer<br/>Add provider close nodes"]
    CPRT --> TRT["TransitiveReductionTransformer<br/>Simplify graph"]

internal/terraform/transform_config.go#L33-L73 の ConfigTransformer は、通常最初に実質的な処理を行うトランスフォーマーです。設定ツリーを走査して、各リソース宣言に対応する頂点を追加します。ただし、この段階では count や for_each はまだ評価されていないため、各頂点は個々のインスタンスではなく設定レベルのリソースを表しています。インスタンスの展開は後続の ModuleExpansionTransformer とウォーク中の動的展開によって行われます。

internal/terraform/transform_reference.go#L19-L43 の ReferenceTransformer では、依存関係のエッジが実際に接続されます。各ノードが参照するアドレス（GraphNodeReferencer 経由）と、各ノードが提供するアドレス（GraphNodeReferenceable 経由）を照合し、エッジで結びます。これにより、リソースの設定内の var.name が変数ノードへの依存を生成し、aws_instance.web.id が aws_instance.web リソースノードへの依存を生成する仕組みです。

ApplyGraphBuilder：plan との違い

internal/terraform/graph_builder_apply.go#L26-L93 の ApplyGraphBuilder は、根本的に異なる入力を受け取ります——設定だけでなく、plan の変更セットです。その Steps() メソッド（105〜200 行目以降）では DiffTransformer が登場します。

&DiffTransformer{
    Concrete: concreteResourceInstance,
    State:    b.State,
    Changes:  b.Changes,
    Config:   b.Config,
},

ConfigTransformer が設定から頂点を追加するのに対し、DiffTransformer は計画済みの変更から頂点を追加します。これにより、apply グラフには実際に変更が必要なリソースだけが含まれるという、重要な安全特性が保証されます。

apply グラフでは、使用するコンクリートノード型も異なります。plan グラフが NodePlannableResourceInstance を使うのに対し、apply グラフは NodeApplyableResourceInstance（119〜124 行目）を使います。こちらは PlanResourceChange() の代わりに provider.ApplyResourceChange() を呼び出します。

両ビルダーは ReferenceTransformer、ProviderTransformer、TransitiveReductionTransformer といった多くのトランスフォーマーを共有しています。依存関係の順序付けとグラフの簡略化という根本的な要件は、どちらも同じだからです。

ウォーク操作：8 種類のグラフウォーク

同じグラフインフラが、8 種類の異なるウォークタイプをサポートしています。internal/terraform/graph_walk_operation.go#L9-L21 で列挙されています。

const (
    walkInvalid walkOperation = iota
    walkApply
    walkPlan
    walkPlanDestroy
    walkValidate
    walkDestroy
    walkImport
    walkEval
    walkInit
)

PlanGraphBuilder.Steps() メソッドはオペレーションタイプに応じて適切な初期化を選択します（149〜160 行目）。walkPlan の場合は initPlan() を呼び出して plannable なリソース向けのコンクリートノードファクトリをセットアップし、walkPlanDestroy の場合は initDestroy() を呼び出してグラフを破棄順序向けに設定します。

この設計により、同じトランスフォーマーパイプラインがオペレーションに応じて大きく異なるグラフを生成しつつ、構造的なロジックの大半を共有できるようになっています。

次回予告

グラフの構築と走査の仕組みを理解したところで、第 3 回では単一のリソースインスタンスが plan・apply の完全なライフサイクルをどのように辿るかを追いかけます。Context.Plan() がグラフを生成し、NodePlannableResourceInstance.Execute() がプロバイダーを呼び出し、Context.Apply() が実際のインフラ変更を加えるまでの流れを詳しく見ていきます。また、グラフノードと外部世界をつなぐ橋渡し役である EvalContext インターフェースについても掘り下げる予定です。