dag

package
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Mar 11, 2026 License: AGPL-3.0 Imports: 19 Imported by: 0

Documentation

Overview

Package dag provides a DAG-based execution framework for Trace pipelines.

The DAG (Directed Acyclic Graph) framework enables:

  • Parallel execution of independent pipeline nodes
  • Explicit dependencies between operations
  • Unified tracing via OpenTelemetry
  • Checkpointing for resume after failure
  • Composable pipeline construction

Thread Safety

All exported types are safe for concurrent use.

Example

// Create nodes with dependencies declared internally
parseNode := dag.NewFuncNode("PARSE_FILES", nil, parseFn)
graphNode := dag.NewFuncNode("BUILD_GRAPH", []string{"PARSE_FILES"}, graphFn)
lintNode := dag.NewFuncNode("LINT_CODE", []string{"BUILD_GRAPH"}, lintFn)

// Build DAG
pipeline, err := dag.NewBuilder("my-pipeline").
    AddNode(parseNode).
    AddNode(graphNode).
    AddNode(lintNode).
    Build()

// Execute
executor, err := dag.NewExecutor(pipeline, logger)
result, err := executor.Run(ctx, input)

Index

Constants

View Source
const CheckpointVersion = "1.0.0"

CheckpointVersion is the current checkpoint format version (semver).

View Source
const DefaultNodeTimeout = 30 * time.Second

DefaultNodeTimeout is the default timeout for nodes that don't specify one.

Variables

View Source
var (
	// ErrNilContext is returned when a nil context is passed.
	ErrNilContext = errors.New("context must not be nil")

	// ErrNilNode is returned when a nil node is provided.
	ErrNilNode = errors.New("node must not be nil")

	// ErrDuplicateNode is returned when adding a node with an existing name.
	ErrDuplicateNode = errors.New("node with this name already exists")

	// ErrNodeNotFound is returned when a referenced node doesn't exist.
	ErrNodeNotFound = errors.New("node not found")

	// ErrCycleDetected is returned when the DAG contains a cycle.
	ErrCycleDetected = errors.New("cycle detected in DAG")

	// ErrNoProgress is returned when no nodes can make progress (deadlock).
	ErrNoProgress = errors.New("no progress possible: deadlock or missing dependency")

	// ErrNodeTimeout is returned when a node exceeds its timeout.
	ErrNodeTimeout = errors.New("node execution timed out")

	// ErrNodeFailed is returned when a node fails during execution.
	ErrNodeFailed = errors.New("node execution failed")

	// ErrDAGNotBuilt is returned when trying to execute an unbuilt DAG.
	ErrDAGNotBuilt = errors.New("DAG has not been built")

	// ErrAlreadyRunning is returned when trying to run an already running executor.
	ErrAlreadyRunning = errors.New("executor is already running")

	// ErrCheckpointCorrupt is returned when a checkpoint fails verification.
	ErrCheckpointCorrupt = errors.New("checkpoint data is corrupt")

	// ErrCheckpointVersionMismatch is returned when checkpoint version doesn't match.
	ErrCheckpointVersionMismatch = errors.New("checkpoint version mismatch")

	// ErrInvalidInput is returned when input validation fails.
	ErrInvalidInput = errors.New("invalid input")

	// ErrRehydrationFailed is returned when a node cannot restore its ephemeral state.
	// This signals that the node should be re-executed rather than assumed complete.
	ErrRehydrationFailed = errors.New("node rehydration failed: ephemeral state cannot be restored")
)

Sentinel errors for the dag package.

Functions

func SaveCheckpoint

func SaveCheckpoint(state *State, dagName string, path string) error

SaveCheckpoint serializes the current execution state to a file.

Description:

Creates a checkpoint file containing the execution state, enabling
resume after failure or restart. Writes atomically using temp file + rename.

Inputs:

state - The current execution state. Must not be nil.
dagName - Name of the DAG being executed.
path - File path to write checkpoint. Parent directory must exist.

Outputs:

error - Non-nil if serialization or file write fails.

Thread Safety:

Safe to call concurrently with DAG execution.

Types

type BaseNode

type BaseNode struct {
	NodeName         string
	NodeDependencies []string
	NodeTimeout      time.Duration
	NodeRetryable    bool
}

BaseNode provides a partial implementation of the Node interface.

Description:

BaseNode implements the common parts of Node (name, dependencies, timeout,
retryable). Embed this in concrete node implementations and override Execute.

Example:

type MyNode struct {
    dag.BaseNode
    // custom fields
}

func NewMyNode() *MyNode {
    return &MyNode{
        BaseNode: dag.BaseNode{
            NodeName:         "MY_NODE",
            NodeDependencies: []string{"OTHER_NODE"},
            NodeTimeout:      10 * time.Second,
        },
    }
}

func (n *MyNode) Execute(ctx context.Context, inputs map[string]any) (any, error) {
    // implementation
}

func (*BaseNode) Dependencies

func (n *BaseNode) Dependencies() []string

Dependencies returns the names of nodes that must complete first.

func (*BaseNode) Execute

func (n *BaseNode) Execute(_ context.Context, _ map[string]any) (any, error)

Execute returns an error if called directly. Concrete implementations must override this method.

func (*BaseNode) Name

func (n *BaseNode) Name() string

Name returns the node's unique identifier.

func (*BaseNode) Retryable

func (n *BaseNode) Retryable() bool

Retryable returns whether this node can be retried on failure.

func (*BaseNode) Timeout

func (n *BaseNode) Timeout() time.Duration

Timeout returns the maximum execution time for this node.

type Builder

type Builder struct {
	// contains filtered or unexported fields
}

Builder constructs a DAG with validation.

Description:

Builder provides a fluent API for constructing DAGs. It validates that
all dependencies exist and that no cycles are present.

Thread Safety:

Builder is NOT safe for concurrent use. Build the DAG in a single goroutine.

Example:

dag, err := dag.NewBuilder("my-pipeline").
    AddNode(parseNode).
    AddNode(graphNode).
    Build()

func NewBuilder

func NewBuilder(name string) *Builder

NewBuilder creates a new DAG builder.

Inputs:

name - The name for the DAG (used in logging/metrics).

Outputs:

*Builder - The builder instance.

func (*Builder) AddNode

func (b *Builder) AddNode(node Node) *Builder

AddNode adds a node to the DAG.

Description:

Adds a node and automatically creates edges from its declared dependencies.
If a node with the same name already exists, an error is recorded.

Inputs:

node - The node to add. Must not be nil.

Outputs:

*Builder - The builder for chaining.

func (*Builder) Build

func (b *Builder) Build() (*DAG, error)

Build validates and constructs the DAG.

Description:

Validates that all dependencies exist and no cycles are present.
Returns an error if validation fails.

Outputs:

*DAG - The constructed DAG.
error - Non-nil if validation fails.

type Checkpoint

type Checkpoint struct {
	// State is the execution state at checkpoint time.
	State *State `json:"state"`

	// Timestamp is when the checkpoint was created (Unix milliseconds UTC).
	Timestamp int64 `json:"timestamp"`

	// Version is the checkpoint format version.
	Version string `json:"version"`

	// Checksum is the SHA256 of the state for integrity verification.
	Checksum string `json:"checksum"`

	// DAGName is the name of the DAG being executed.
	DAGName string `json:"dag_name"`
}

Checkpoint is a serializable snapshot for resume.

Description:

Checkpoint captures the execution state at a point in time, enabling
resume after failure or restart.

func LoadCheckpoint

func LoadCheckpoint(path string) (*Checkpoint, error)

LoadCheckpoint reads and verifies a checkpoint from a file.

Description:

Loads a previously saved checkpoint, verifying its integrity via checksum.
Returns an error if the checkpoint is corrupt or version mismatched.

Inputs:

path - File path to read checkpoint from.

Outputs:

*Checkpoint - The loaded checkpoint. Never nil on success.
error - Non-nil if file read, parse, or verification fails.

func (*Checkpoint) Verify

func (c *Checkpoint) Verify() bool

Verify checks the checkpoint's integrity.

Description:

Recalculates the checksum and compares it to the stored value.
Returns true if the checkpoint is valid.

Outputs:

bool - True if checksum matches, false if corrupt.

type CycleError

type CycleError struct {
	Path []string
}

CycleError provides details about a detected cycle.

func NewCycleError

func NewCycleError(path []string) *CycleError

NewCycleError creates a CycleError.

func (*CycleError) Error

func (e *CycleError) Error() string

Error returns the cycle description.

type DAG

type DAG struct {
	// contains filtered or unexported fields
}

DAG represents the complete pipeline graph.

Description:

DAG holds the nodes and their dependency relationships. It must be built
using a Builder before execution.

Thread Safety:

DAG is safe for concurrent read access after building. Do not modify
after calling Build().

func (*DAG) GetDependencies

func (d *DAG) GetDependencies(nodeName string) []string

GetDependencies returns the dependency names for a node.

func (*DAG) GetNode

func (d *DAG) GetNode(name string) (Node, bool)

GetNode returns a node by name.

Inputs:

name - The node name.

Outputs:

Node - The node if found.
bool - True if found.

func (*DAG) Name

func (d *DAG) Name() string

Name returns the DAG's name.

func (*DAG) NodeCount

func (d *DAG) NodeCount() int

NodeCount returns the number of nodes.

func (*DAG) NodeNames

func (d *DAG) NodeNames() []string

NodeNames returns all node names.

func (*DAG) Terminal

func (d *DAG) Terminal() string

Terminal returns the terminal (final) node name.

type Edge

type Edge struct {
	// From is the dependency node name (must complete first).
	From string `json:"from"`

	// To is the dependent node name (waits for From).
	To string `json:"to"`
}

Edge represents a dependency relationship between nodes.

type Executor

type Executor struct {
	// contains filtered or unexported fields
}

Executor runs a DAG with parallelism and observability.

Description:

Executor manages DAG execution, running independent nodes in parallel,
tracking state, and providing observability via OpenTelemetry.

Thread Safety:

Executor is safe for concurrent use. Multiple DAG executions can run
concurrently on the same Executor.

func NewExecutor

func NewExecutor(dag *DAG, logger *slog.Logger) (*Executor, error)

NewExecutor creates a new DAG executor.

Inputs:

dag - The DAG to execute. Must not be nil.
logger - Logger for execution logs. If nil, uses slog.Default().

Outputs:

*Executor - The configured executor.
error - Non-nil if initialization fails.

func (*Executor) Resume

func (e *Executor) Resume(ctx context.Context, checkpoint *Checkpoint) (*Result, error)

Resume continues DAG execution from a checkpoint.

Description:

Verifies the checkpoint integrity and DAG compatibility, then resumes
execution from the saved state. Any previously failed node is cleared
to allow retry.

Inputs:

ctx - Context for cancellation. Must not be nil.
checkpoint - The checkpoint to resume from. Must not be nil.

Outputs:

*Result - Execution result including output and timing.
error - Non-nil if verification fails or execution fails.

func (*Executor) Run

func (e *Executor) Run(ctx context.Context, input any) (*Result, error)

Run executes the DAG from start to completion.

Description:

Executes all nodes in the DAG, respecting dependencies and running
independent nodes in parallel. Creates a root span for tracing.

Inputs:

ctx - Context for cancellation. Must not be nil.
input - Initial input passed to root nodes (nodes with no dependencies).

Outputs:

*Result - Execution result including output and timing.
error - Non-nil on failure.

func (*Executor) RunFromState

func (e *Executor) RunFromState(ctx context.Context, state *State) (*Result, error)

RunFromState continues execution from a saved state.

Description:

Resumes DAG execution from a previously saved state, useful for
implementing checkpoint/resume functionality. Before resuming,
it calls OnResume on all completed RehydratableNodes to restore
any ephemeral state (e.g., respawn LSP processes).

Inputs:

ctx - Context for cancellation.
state - Previously saved state to resume from.

Outputs:

*Result - Execution result.
error - Non-nil on failure.

type ExecutorConfig

type ExecutorConfig struct {
	// VerificationMode enables lightweight execution for MCTS scoring.
	//
	// When true, the executor:
	//   - Skips setup/initialization nodes (nodes with "setup" or "init" in name)
	//   - Disables detailed per-node tracing spans
	//   - Only runs verification nodes (lint, test, security)
	//   - Returns minimal scoring result instead of full trace
	//
	// This addresses the DAG vs MCTS performance tension where MCTS rollouts
	// need fast leaf verification (<100ms) without full pipeline overhead.
	//
	// Default: false
	VerificationMode bool

	// SkipNodes lists node names to skip in verification mode.
	// These are typically heavy setup nodes that aren't needed for scoring.
	// Default: []string{"PARSE_FILES", "LOAD_CACHE", "BUILD_GRAPH"}
	SkipNodes []string

	// VerificationNodes lists the only nodes to run in verification mode.
	// If empty, runs all nodes except those in SkipNodes.
	// Default: []string{"LINT_CHECK", "TYPE_CHECK", "SECURITY_SCAN"}
	VerificationNodes []string
}

ExecutorConfig configures the DAG executor behavior.

func DefaultExecutorConfig

func DefaultExecutorConfig() ExecutorConfig

DefaultExecutorConfig returns sensible defaults for normal execution.

func VerificationExecutorConfig

func VerificationExecutorConfig() ExecutorConfig

VerificationExecutorConfig returns config optimized for MCTS verification.

Description

Use this configuration when calling DAG from MCTS rollout scoring. It skips heavy setup nodes and only runs lightweight verification, targeting <100ms per leaf verification.

Usage

config := dag.VerificationExecutorConfig()
executor, _ := dag.NewExecutorWithConfig(dag, logger, config)
result, _ := executor.Run(ctx, nil)
score := extractScore(result)

type FuncNode

type FuncNode struct {
	BaseNode
	// contains filtered or unexported fields
}

FuncNode wraps a function as a Node for simple cases.

Description:

FuncNode allows creating nodes from simple functions without
defining a full struct.

Example:

node := dag.NewFuncNode("MY_NODE", []string{"DEP"}, func(ctx, inputs) (any, error) {
    return "result", nil
})

func NewFuncNode

func NewFuncNode(
	name string,
	deps []string,
	fn func(context.Context, map[string]any) (any, error),
) *FuncNode

NewFuncNode creates a node from a function.

Inputs:

name - The node name.
deps - Dependency node names.
fn - The function to execute.

Outputs:

*FuncNode - The function node.

func (*FuncNode) Execute

func (n *FuncNode) Execute(ctx context.Context, inputs map[string]any) (any, error)

Execute runs the wrapped function.

func (*FuncNode) WithRetryable

func (n *FuncNode) WithRetryable(retryable bool) *FuncNode

WithRetryable sets whether the FuncNode is retryable.

func (*FuncNode) WithTimeout

func (n *FuncNode) WithTimeout(d time.Duration) *FuncNode

WithTimeout sets the timeout for a FuncNode.

type Node

type Node interface {
	// Name returns the unique identifier for this node.
	//
	// Outputs:
	//   string - Unique node name (e.g., "PARSE_FILES", "BUILD_GRAPH").
	Name() string

	// Dependencies returns the names of nodes that must complete first.
	//
	// Outputs:
	//   []string - Names of dependency nodes. Empty if no dependencies.
	Dependencies() []string

	// Execute runs the node's logic.
	//
	// Inputs:
	//   ctx - Context for cancellation and timeout.
	//   inputs - Map of dependency node outputs keyed by node name.
	//
	// Outputs:
	//   any - The node's output, passed to dependent nodes.
	//   error - Non-nil on failure.
	Execute(ctx context.Context, inputs map[string]any) (any, error)

	// Retryable returns true if this node can be retried on failure.
	//
	// Outputs:
	//   bool - True if retryable.
	Retryable() bool

	// Timeout returns the maximum execution time for this node.
	//
	// Outputs:
	//   time.Duration - Maximum execution time. Zero means no timeout.
	Timeout() time.Duration
}

Node represents a single step in the pipeline.

Description:

Node is the fundamental unit of work in a DAG. Each node has a unique name,
declares its dependencies, and implements Execute to perform its work.

Thread Safety:

Implementations must be safe for concurrent use. Execute may be called
concurrently with other nodes.

type NodeError

type NodeError struct {
	NodeName string
	Err      error
}

NodeError wraps an error with the node that caused it.

func NewNodeError

func NewNodeError(nodeName string, err error) *NodeError

NewNodeError creates a NodeError.

func (*NodeError) Error

func (e *NodeError) Error() string

Error returns the error message.

func (*NodeError) Unwrap

func (e *NodeError) Unwrap() error

Unwrap returns the underlying error.

type NodeStatus

type NodeStatus string

NodeStatus represents the execution status of a node.

const (
	// NodeStatusPending indicates the node hasn't started.
	NodeStatusPending NodeStatus = "pending"

	// NodeStatusRunning indicates the node is executing.
	NodeStatusRunning NodeStatus = "running"

	// NodeStatusCompleted indicates successful completion.
	NodeStatusCompleted NodeStatus = "completed"

	// NodeStatusFailed indicates the node failed.
	NodeStatusFailed NodeStatus = "failed"

	// NodeStatusSkipped indicates the node was skipped.
	NodeStatusSkipped NodeStatus = "skipped"
)

type RehydratableNode

type RehydratableNode interface {
	Node

	// OnResume restores ephemeral state after checkpoint load.
	//
	// Description:
	//
	//   Called after loading a checkpoint, before resuming DAG execution.
	//   Implementations should check if their ephemeral resources still exist
	//   and recreate them if necessary.
	//
	// Inputs:
	//
	//   ctx - Context for cancellation. Must not be nil.
	//   output - The node's output from the checkpoint. May be nil.
	//
	// Outputs:
	//
	//   error - Non-nil if rehydration fails and the node should be re-executed.
	//
	// Example:
	//
	//   func (n *LSPNode) OnResume(ctx context.Context, output any) error {
	//       lspOutput, ok := output.(*LSPSpawnOutput)
	//       if !ok || lspOutput.Manager == nil {
	//           return ErrRehydrationFailed // Will cause re-execution
	//       }
	//       // Check if process is still alive
	//       if !lspOutput.Manager.IsHealthy() {
	//           return n.manager.RespawnAll(ctx)
	//       }
	//       return nil
	//   }
	OnResume(ctx context.Context, output any) error
}

RehydratableNode is implemented by nodes that manage ephemeral state which cannot survive checkpoint/restart (e.g., running processes, open connections).

Description:

When a DAG is resumed from a checkpoint, nodes marked "complete" may have
ephemeral resources that no longer exist (e.g., LSP processes that died,
network connections that closed). RehydratableNode allows these nodes to
restore their ephemeral state before downstream nodes attempt to use it.

The Zombie Problem:

Without rehydration, this sequence causes a panic:
  1. Agent runs Step 1 (Parse), Step 2 (Start LSP)
  2. DAG saves Checkpoint - LSP_SPAWN marked "Complete"
  3. System crashes
  4. System loads Checkpoint
  5. Step 3 (TYPE_CHECK) calls LSP
  6. PANIC: LSP.Manager is nil (process didn't survive restart)

Thread Safety:

OnResume must be safe for concurrent use. The executor calls OnResume
on all completed RehydratableNodes before resuming execution.

type Result

type Result struct {
	// Success indicates if the DAG completed successfully.
	Success bool `json:"success"`

	// SessionID is the execution session ID.
	SessionID string `json:"session_id"`

	// Duration is the total execution time.
	Duration time.Duration `json:"duration"`

	// NodesExecuted is the count of nodes that ran.
	NodesExecuted int `json:"nodes_executed"`

	// Output is the terminal node's output (if successful).
	Output any `json:"output,omitempty"`

	// Error is the error message (if failed).
	Error string `json:"error,omitempty"`

	// FailedNode is the node that caused failure.
	FailedNode string `json:"failed_node,omitempty"`

	// NodeDurations tracks execution time per node.
	NodeDurations map[string]time.Duration `json:"node_durations,omitempty"`
}

Result represents the outcome of a DAG execution.

type State

type State struct {

	// SessionID is the unique identifier for this execution.
	SessionID string `json:"session_id"`

	// StartedAt is when execution began (Unix milliseconds UTC).
	StartedAt int64 `json:"started_at"`

	// CompletedNodes tracks which nodes have finished.
	CompletedNodes map[string]bool `json:"completed_nodes"`

	// NodeOutputs stores outputs from completed nodes.
	NodeOutputs map[string]any `json:"node_outputs"`

	// NodeStatuses tracks status per node.
	NodeStatuses map[string]NodeStatus `json:"node_statuses"`

	// CurrentNodes is the set of currently executing nodes.
	CurrentNodes []string `json:"current_nodes"`

	// FailedNode is the name of the node that caused failure (if any).
	FailedNode string `json:"failed_node,omitempty"`

	// Error is the error message if failed.
	Error string `json:"error,omitempty"`
	// contains filtered or unexported fields
}

State represents the current execution state.

Description:

State tracks which nodes have completed, their outputs, and any failures.
It is updated by the Executor during pipeline execution.

Thread Safety:

State uses internal locking and is safe for concurrent access.

func NewState

func NewState(sessionID string) *State

NewState creates a new execution state.

func (*State) CompletedCount

func (s *State) CompletedCount() int

CompletedCount returns the number of completed nodes.

func (*State) GetOutput

func (s *State) GetOutput(nodeName string) (any, bool)

GetOutput returns the output of a completed node.

func (*State) GetStatus

func (s *State) GetStatus(nodeName string) NodeStatus

GetStatus returns the status of a node.

func (*State) IsCompleted

func (s *State) IsCompleted(nodeName string) bool

IsCompleted checks if a node has completed successfully.

func (*State) IsDAGComplete

func (s *State) IsDAGComplete(dag *DAG) bool

IsDAGComplete checks if all nodes in the DAG have completed.

func (*State) IsFailed

func (s *State) IsFailed() bool

IsFailed returns whether execution has failed.

func (*State) SetCompleted

func (s *State) SetCompleted(nodeName string, output any)

SetCompleted marks a node as completed with its output.

func (*State) SetCurrentNodes

func (s *State) SetCurrentNodes(nodes []string)

SetCurrentNodes sets the list of currently executing nodes.

func (*State) SetFailed

func (s *State) SetFailed(nodeName string, err error)

SetFailed marks a node and the execution as failed.

func (*State) SetStatus

func (s *State) SetStatus(nodeName string, status NodeStatus)

SetStatus sets the status of a node.

Directories

Path Synopsis
Package nodes provides concrete DAG node implementations for Trace pipelines.
Package nodes provides concrete DAG node implementations for Trace pipelines.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL