How Beads Prevents and Detects Circular Dependencies

Beads prevents circular dependencies through a pre-insertion recursive CTE guard in AddDependencyInTx and detects existing cycles via a post-insertion DFS scan in DetectCyclesInTx.

Circular dependencies in issue tracking graphs corrupt project timelines and invalidate automation workflows. The gastownhall/beads repository implements a two-layer defense system that prevents cycles during dependency creation while providing tools to audit and surface existing loops. This article examines the exact mechanisms used to maintain acyclic dependency graphs in Beads.

Pre-Insertion Cycle Prevention

When you add a blocking dependency using bd dep add, Beads validates the operation before committing it to the database.

The Recursive CTE Guard

The AddDependencyInTx function in internal/storage/issueops/dependencies.go (lines 25-53) runs a recursive Common Table Expression (CTE) to validate potential inserts. This guard specifically applies to DepBlocks and DepConditionalBlocks dependency types.

The CTE performs the following logic:

1. Starts from the proposed target issue (dep.DependsOnID)
2. Recursively follows all existing blocks and conditional-blocks edges in both the dependencies and wisp_dependencies tables
3. Checks if the source issue (dep.IssueID) appears in the reachable set

If the source is reachable from the target, inserting the edge would close a loop, so the function returns the error "adding dependency would create a cycle" and aborts the transaction.

// internal/storage/issueops/dependencies.go
if !opts.SkipCycleCheck && (dep.Type == types.DepBlocks || dep.Type == types.DepConditionalBlocks) {
    var unions []string
    for _, t := range depTables {
        unions = append(unions, fmt.Sprintf(
            "SELECT issue_id, depends_on_id FROM %s WHERE type IN ('blocks','conditional-blocks')", t))
    }
    unionQuery := strings.Join(unions, " UNION ALL ")

    var reachable int
    if err := tx.QueryRowContext(ctx, fmt.Sprintf(`
        WITH RECURSIVE reachable AS (
            SELECT ? AS node, 0 AS depth
            UNION ALL
            SELECT d.depends_on_id, r.depth + 1
            FROM reachable r
            JOIN (%s) d ON d.issue_id = r.node
            WHERE r.depth < 100
        )
        SELECT COUNT(*) FROM reachable WHERE node = ?
    `, unionQuery), dep.DependsOnID, dep.IssueID).Scan(&reachable); err != nil {
        return fmt.Errorf("failed to check for dependency cycle: %w", err)
    }
    if reachable > 0 {
        return fmt.Errorf("adding dependency would create a cycle")
    }
}

The recursion depth is capped at 100 levels to prevent runaway queries on deeply chained dependencies.

Bypassing the Guard

For bulk wiring operations, you can bypass the CTE check using the --no-cycle-check flag:

bd dep add --file bulk.jsonl --no-cycle-check

This is why Beads implements a secondary detection layer to catch cycles that bypass the initial guard.

Post-Insertion Cycle Detection

After dependencies are inserted—or when explicitly requested—Beads performs a comprehensive graph analysis to find cycles.

Building the Dependency Graph

The DetectCyclesInTx function in internal/storage/issueops/cycles.go (lines 11-34) reads all blocking edges from both storage tables into an in-memory adjacency map:

graph := make(map[string][]string)

for _, depTable := range []string{"dependencies", "wisp_dependencies"} {
    rows, err := tx.QueryContext(ctx,
        fmt.Sprintf(`SELECT issue_id, depends_on_id, type FROM %s`, depTable))
    // ... scan rows ...
    if types.DependencyType(depType) == types.DepBlocks ||
       types.DependencyType(depType) == types.DepConditionalBlocks {
        graph[issueID] = append(graph[issueID], dependsOnID)
    }
}

DFS-Based Cycle Enumeration

Lines 44-96 implement a depth-first search (DFS) algorithm with recursion stack tracking to detect back-edges:

var cycles [][]*types.Issue
visited := make(map[string]bool)
recStack := make(map[string]bool)
var path []string

var dfs func(node string) bool
dfs = func(node string) bool {
    visited[node] = true
    recStack[node] = true
    path = append(path, node)

    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            if dfs(neighbor) { return true }
        } else if recStack[neighbor] {
            // Cycle detected: extract and resolve IDs to Issues
            cycles = append(cycles, cycleIssues)
        }
    }
    path = path[:len(path)-1]
    recStack[node] = false
    return false
}

When the algorithm encounters a node already present in the current recursion stack, it extracts the cycle path and resolves each ID to a full *types.Issue struct for display purposes.

CLI Integration and User Feedback

Beads surfaces cycle information through the CLI in two ways.

Post-Add Warnings

The warnIfCyclesExist function in cmd/bd/dep.go (lines 57-71) runs automatically after bd dep add completes successfully (unless --no-cycle-check was used):

func warnIfCyclesExist(s storage.DoltStorage) {
    if s == nil { return }
    cycles, err := s.DetectCycles(rootCtx)
    if err != nil { /* handle error */ }
    if len(cycles) == 0 { return }

    fmt.Fprintf(os.Stderr, "\n%s Warning: Dependency cycle detected!\n", ui.RenderWarn("⚠"))
    // ... pretty-print each cycle ...
}

Explicit Detection Command

The bd dep cycles command invokes store.DetectCycles, which delegates to DetectCyclesInTx for a full analysis:

bd dep cycles

This outputs a detailed report listing each cycle with issue titles and statuses.

Code Examples

Blocking a Cycle at Insert Time

# Create two issues

bd issue add "First"   # → bd-001

bd issue add "Second"  # → bd-002

# Add forward dependency (succeeds)

bd dep add bd-001 bd-002

# Attempt reverse (fails with cycle error)

bd dep add bd-002 bd-001

# Error: adding dependency would create a cycle

Detecting Cycles After Bulk Import

# Import with cycle check disabled

bd dep add --file bulk.jsonl --no-cycle-check

# Audit for cycles

bd dep cycles

# Output:

#   1. Cycle involving:

#      - bd-001: First

#      - bd-002: Second

#      - bd-001 (repeated)

Programmatic Usage

ctx := context.Background()
dep := &types.Dependency{
    IssueID:     "bd-002",
    DependsOnID: "bd-001",
    Type:        types.DepBlocks,
}

// This returns error if cycle would be created
if err := store.AddDependency(ctx, dep, "tester"); err != nil {
    // err.Error() == "adding dependency would create a cycle"
}

Key Implementation Files

File	Function	Purpose
internal/storage/issueops/dependencies.go	AddDependencyInTx	Pre-insertion CTE validation
internal/storage/issueops/cycles.go	DetectCyclesInTx	Post-insertion DFS enumeration
cmd/bd/dep.go	warnIfCyclesExist	CLI warning after add operations
cmd/bd/dep.go	depCyclesCmd	Implementation of bd dep cycles
internal/storage/dolt/dependencies.go	DetectCycles	Storage-layer delegation to detection logic

Summary

• Pre-insertion guard: The recursive CTE in AddDependencyInTx rejects any dependency that would create a cycle before it reaches the database.
• Post-insertion detection: The DFS algorithm in DetectCyclesInTx scans the entire graph on demand to find existing cycles.
• CLI feedback: Automatic warnings after bd dep add and the explicit bd dep cycles command provide visibility into graph integrity.
• Bypass safety: The --no-cycle-check flag allows bulk imports while relying on the secondary detection layer for remediation.

Frequently Asked Questions

What happens when I try to create a circular dependency in Beads?

Beads rejects the operation with the error "adding dependency would create a cycle". The AddDependencyInTx function runs a recursive CTE query starting from the target issue; if it can reach the source issue through existing blocks or conditional-blocks edges, the transaction aborts before persisting the new edge.

Can I skip the cycle check when adding dependencies?

Yes. Use the --no-cycle-check flag with bd dep add to bypass the pre-insertion CTE validation. This is useful for bulk imports but should be followed by running bd dep cycles to audit the graph for any cycles introduced during the import.

How does Beads detect cycles across temporary issues (wisps)?

The CTE guard and DFS detection both query both the dependencies and wisp_dependencies tables using a UNION ALL clause. This ensures that blocking relationships involving temporary issues (wisps) are included in the cycle detection logic, maintaining graph integrity across both permanent and temporary branches.

What is the maximum depth searched by the cycle prevention CTE?

The recursive CTE limits traversal depth to 100 levels (WHERE r.depth < 100). This prevents performance degradation on deeply nested dependency chains while still catching cycles in practical project management scenarios where dependencies rarely exceed dozens of levels.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}