DAG primitive

Active contributors: Mitchell Hashimoto, James Bardin, Martin Atkins.

Purpose

internal/dag/ provides the directed-acyclic-graph type used by every graph builder in the codebase. It is the oldest unchanged piece of the engine and intentionally tiny: it does one thing — represent a DAG and walk it in topological order with bounded parallelism — and exposes nothing else.

Directory layout

internal/dag/
├── dag.go            # AcyclicGraph type and walk algorithm
├── edge.go           # Edge interface and BasicEdge
├── graph.go          # the underlying directed graph
├── marshal.go        # debug serialization
├── set.go            # a small set utility
├── tarjan.go         # cycle detection (Tarjan's strongly connected components)
└── walk.go           # synchronization primitives used by the walker

Key types

Type	File	Description
dag.Graph	graph.go	Directed graph with vertices and edges.
dag.AcyclicGraph	dag.go	Embeds Graph, adds Validate (cycle check) and Walk.
dag.Vertex	graph.go	An empty interface — vertices are arbitrary user types.
dag.Edge	edge.go	Interface with Source() and Target().
dag.BasicEdge	edge.go	Trivial implementation; constructor dag.BasicEdge(source, target).
dag.Walker	walk.go	Internal scheduler used by Walk.

How it works

The walk algorithm is a classic worker pool:

graph TD
    Validate[Validate: Tarjan SCC, reject cycles] --> Roots[find vertices with no incoming edges]
    Roots --> Schedule[push to ready queue]
    Schedule --> Workers[N goroutines pull from ready queue]
    Workers --> Visit[user-supplied visit fn]
    Visit --> Done[record completion, decrement successor counts]
    Done --> Schedule2[any successor with zero remaining → ready queue]
    Schedule2 --> Workers
    Workers --> Wait[when all done, return aggregated diagnostics]

The user-facing API is one method:

func (g *AcyclicGraph) Walk(visit WalkFunc) tfdiags.Diagnostics

type WalkFunc func(Vertex) tfdiags.Diagnostics

Cycle detection runs before the walk, via Tarjan's algorithm. If the graph has cycles, Walk returns immediately with a diagnostic listing the cycle.

Bounded parallelism

The walker uses a semaphore from internal/dag/walk.go to bound concurrent visits. The bound is set indirectly — the engine's terraform.Context configures the walk with the Parallelism value from ContextOpts (default 10), and dag.Walker respects it.

Failure handling

If a WalkFunc returns error-severity diagnostics, the walker:

1. Records the failure for that vertex.
2. Marks every vertex transitively downstream as "skipped due to upstream error".
3. Continues walking other independent branches.
4. At the end, returns the union of all diagnostics.

This is why a partial apply can still make forward progress on independent resources after one of them fails.

Marshaling and debugging

marshal.go produces a JSON dump of the graph, used by the terraform graph CLI command (rendered as Graphviz DOT) and by [TRACE] log output for debugging.

The terraform graph command uses internal/terraform.GraphBuilder to construct the graph, then dumps it through dag.Marshal.

Integration points

• Engine: every GraphBuilder in internal/terraform returns a *terraform.Graph, which embeds an AcyclicGraph. The engine adds path-aware indexing on top but the walk algorithm is pure dag.
• Stacks: the stacks runtime in internal/stacks/stackruntime/ does not use this package. It uses the internal/promising/ library for its scheduling, because stack components have dynamic dependencies that don't fit a static DAG.
• Tests: small graph tests use dag directly to exercise edge cases without going through the engine.

Why two scheduling primitives

internal/dag/ is for static graphs known at construction time. internal/promising/ is for dynamic dependencies expressed as promises. Both coexist:

• A typical terraform plan runs entirely under dag — the configuration determines the graph statically.
• A terraform stacks plan runs under promising — components are evaluated and create new dependencies as they run.

This split is recent (added with the stacks subsystem). Pre-stacks, dag was the only scheduler.

Entry points for modification

• The package is intentionally stable. Most changes in graph behavior happen in internal/terraform transforms or vertex implementations, not here.
• If you need a new walking mode (e.g. priority-based scheduling), it belongs in a wrapper around dag.Walker, not in dag.Walker itself.
• Cycle detection lives in tarjan.go and is not normally edited; the cycle-error message is constructed in the engine, not here.