beads/cmd/bd/dep_cycles.go
Stephanie Jarmak 12b19a6df7
feat(dep): detect cycles through tracks edges (#6148)
* feat(dep): teach bd dep cycles to traverse tracks edges (gc-818bx)

Adds DetectCyclesRequest.IncludeTracks and a CanonicalMixedCyclePaths
walk so a molecule-root deadlock closing through a tracks edge (root
--blocks--> its own entry step, step --tracks--> root) is detectable,
while a cycle made entirely of tracks edges stays silent by
construction (guards against the PR #4933 false-positive regression).

Wired end to end: public issueops.DetectCyclesRequest -> pure
CanonicalMixedCyclePaths/AppendMixedCycleGraphInTx ->
DetectCycleReportInTx -> dolt/embeddeddolt/uow-domain transactional
wrappers -> `bd dep cycles --include-tracks`. Default request behavior
is unchanged (byte-identical code path when IncludeTracks is false).

Tests: pure-function unit tests for the new DFS variant (rotation,
parallel-edge dedup, self-loops, map-order determinism); conformance
cases against both dolt and embeddeddolt real backends plus the uow
provider (RunCycleDetectorIncludeTracksIgnoresAPureTracksLoop,
RunCycleDetectorIncludeTracksFindsTheMoleculeRootShape, and an added
DepTracks case in RunCycleDetectorFollowsOnlyBlockingEdges pinning the
default's exclusion); CLI-level flag registration and threading tests.

Scope: fix candidate 3 only, per gascity-pl's 2026-08-10 scope-narrowing
comment on gc-818bx (candidates 1/2 addressed upstream by gastownhall/
gascity PR #5202).

* fix(dep): find mixed cycles by SCC instead of single-pass DFS (gc-818bx)

CanonicalMixedCyclePaths could report no cycle for a graph that has a
qualifying one. A single global visited/onPath set only detects a back
edge to a node still on the active recursion stack, so a tracks-only
loop that fully closes and unwinds first (a->b->a) leaves b marked
visited-but-off-path by the time a scheduling edge into the same
component (a->c->b) is examined, and the c->b return edge is invisible
to the DFS.

Every internal edge of a strongly connected component lies on some
cycle within it, so replace the DFS with Tarjan's algorithm: find each
SCC, and for any SCC containing a scheduling edge, walk a deterministic
BFS return path back to that edge's source. Nodes, adjacency, SCC
membership, the chosen edge, and the return path are all sorted so the
result stays a pure function of the graph, matching the existing
determinism guarantee.

Adds the counterexample from exact-head review: a--tracks-->b,
b--tracks-->a, a--blocks-->c, c--tracks-->b, which the prior
implementation reported as acyclic despite the qualifying a->c->b->a
cycle.

* fix(dep): fail loudly if SCC path invariant breaks (gc-zo8a7)

Agent-Signature: codex-gpt-5-unknown-reasoning on behalf of sjarmak

* fix(dep): keep every default cycle in the --include-tracks report

CanonicalMixedCyclePaths emitted one cycle per strongly connected
component, so a tracks edge joining two separate blocks-only deadlocks
collapsed them into one reported cycle and --include-tracks could report
fewer cycles than the default walk.

The widened report is now the union of the default depth-first walk on the
scheduling-only subgraph and, for each blocks/conditional-blocks edge
inside a component of the widened graph, that edge closed by its shortest
return path over either edge type. The first set is the default report by
construction; the second adds cycles that close through tracks edges. Every
reported cycle still contains a scheduling edge, so tracks-only loops stay
out. The report holds at most one cycle per internal scheduling edge plus
the default cycles.

A missing return path inside a component is an invariant breach; it now
returns an error through DetectCycles instead of panicking.

* test(dep): pin tracks edge direction in the cycle detector contract

A two-node cycle reads the same under edge reversal, so the existing
IncludeTracks cases could not tell a walk that follows issue_id ->
depends_on_id from one that follows the reverse. The new three-node case
seeds a -> c (tracks), c -> b (blocks), b -> a (tracks), whose reported
path is a, c, b and becomes a, b, c if the edges are reversed.

Also refresh the cycledetector.go line citations this branch shifted.

* perf(dep): share one return-path search per target in the --include-tracks report

CanonicalMixedCyclePaths ran one breadth-first search per scheduling edge
inside a component, O(E(V+E)). On a dense tangle E grows with the square of
V, so the report grew with the fourth power of the component size.

Group the component's scheduling edges by target and close every edge into a
target from one shortestPathTree rooted there, confined to the component.
closeMixedCycle now reads the return path out of that tree and still returns
an error, never loops, when the tree does not reach the edge's source.

TestShortestPathTreeClosesEachEdgeAsAPerEdgeSearchDid checks over generated
graphs that each edge closes to the cycle reachPath produced for it alone,
ties included. BenchmarkCanonicalMixedCyclePathsDenseTangle (80 issues, a
blocks edge for every ordered pair, one tracks edge back): 26.3 ms and
27.8 MB per call before, 5.4 ms and 2.8 MB after.

* fix(dep): scope the --include-tracks guarantee and bound its output

Review iteration 1 (maintainer fixup) for the one gating major. The
IncludeTracks doc claimed that requiring "at least one blocks/
conditional-blocks edge" on every reported cycle is what keeps out the
`bd doctor` regression that "produced thousands of cycles". That rule is
NECESSARY, NOT SUFFICIENT. One tracks-only loop fuses everything it
touches into a single strongly connected component, after which every
scheduling edge inside that component lies on a cycle and is reported --
even where those scheduling edges alone are strictly acyclic and the
default walk reports nothing. A 10-step molecule whose entry step tracks
back to its root yields 9 reports against the default walk's 0.

The doc's own BOUND paragraph conceded the volume ("never more than twice
the distinct scheduling edges") while the paragraph above it claimed the
guard prevented it. The algorithm is correct and is unchanged; what was
wrong is the contract written over it, plus the absence of any cap on a
diagnostic that can now be edge-count sized.

A census found the claim in 5 sites, not the 2 the review cited:
  issueops/cycledetector.go                       IncludeTracks field doc
  internal/storage/issueops/cycle_report.go       the BOUND paragraph
  internal/storage/issueops/cycles.go             AppendMixedCycleGraphInTx
  cmd/bd/dep.go                                   flag registration comment
  internal/storage/issueops/cycle_report_test.go  section header
backend/conformance/cycle_detector_contract.go:246 already scoped it
correctly ("a loop made entirely of tracks edges stays silent") and is
left alone. The PR body and the contributor's commit messages assert only
the true narrow rule, so neither needed correcting.

--limit caps the RENDERED list (default 50, 0 = no limit), matching the
idiom in list/search/stale/find_duplicates. It is a rendering cap and not
a narrower request because CycleReport.Cycles promises to omit no cycle:
the printed total stays the whole report's, the truncation says how much
it held back, and --json is never capped.

TestCanonicalMixedCyclePathsBoundsAFusedMoleculeByItsSchedulingEdges pins
the manufacture direction ...KeepsDeadlocksATracksEdgeFuses left open --
that one fuses two real deadlocks and checks neither is lost; this one
fuses none at all and still gets 9 reports.

Also taken, both non-gating: dropped the dormant
`json:"include_tracks,omitempty"` tag, since no serializer of
DetectCyclesRequest exists in the tree and handleDependencyCycles calls
requireNoQuery, so the tag advertised a wire contract the server refuses;
and added a comment naming the backend conformance cases as the only pin
on the row->edge admission switch.

Declined this iteration: factoring appendDependencyGraphInTx and
AppendMixedCycleGraphInTx onto one shared row loop (nit, gate impact
none). It restructures the SQL read path that, per the finding directly
above it, is pinned only at the conformance layer, and
appendDependencyGraphInTx also backs AppendSchedulingGraphInTx -- the
write-time gate behind every `bd dep add`. That is a wider blast radius
than a zero-gate-impact nit earns inside a fixup whose subject is a doc
overclaim; it belongs in its own change.

Validation: go build ./... clean; go vet clean on the 4 touched packages;
golangci-lint v2.10.1 reports 0 issues on issueops/...,
internal/storage/issueops/... and cmd/bd/...; internal/storage/issueops
full package 749 PASS / 0 FAIL / 0 SKIP (748 before, +1 new); cmd/bd
dep-cycles selector 9 PASS / 0 FAIL / 0 SKIP; internal/httpapi
Cycle|SpecParity 6 PASS / 0 FAIL. Mutation: making tracks edges unable to
fuse a component reds the new pin plus 5 incumbents (the feature dies);
reporting only one cycle per component reds the new pin ALONE (1 of 14),
so it covers a degradation no existing test catches.

Review iteration 2: the remedy above re-entered its own finding class. Both
iteration-2 items indict text THIS fixup wrote, not the contributor's.

The --limit cap is UNCONDITIONAL -- `if limit > 0 && len(shown) > limit` never
consults includeTracks -- yet every rationale iteration 1 wrote for it was
scoped to the widened walk, and the IncludeTracks field doc still closed with
"the base walk this type's doc above describes is unchanged". True of the walk;
false of its rendering, since plain `bd dep cycles` printed every cycle at base
and now prints at most 50. That is the same defect class as the major this
commit exists to fix: a doc claiming a scope the mechanism does not honor.

Of the two arms the review offered, only documenting the true scope is
available. Gating the cap on includeTracks reds this PR's own incumbent test:
printCycleReportForTest calls runDepCycles(false, limit), so
TestDepCyclesTruncatesTheRenderedListButNotTheCount/capped asserts the DEFAULT
walk truncates. Measured, not assumed -- that arm fails capped and
registered_default while no_limit passes. The implementation, the flag's help
string and the tests already agreed the cap is unconditional; only the prose
disagreed, so the prose moved:
  cmd/bd/dep_cycles.go      runDepCycles doc: the cap is unconditional, bounds
                            both walks, and names the behavior change vs base
  cmd/bd/dep.go             flag comment: caps both walks; the widened walk is
                            what makes the cap necessary, not what scopes it
  issueops/cycledetector.go the "Default false" closer: the walk is unchanged,
                            its RENDERING is not
Also the nit: the opening paragraph argued no flag can narrow either question
while --limit had no carve-out, where IncludeTracks had one. It now says no flag
narrows the ANSWER, and that --limit caps only what is PRINTED.

New renderer arm "registered default" closes the gap the minor named: every
existing arm drove an explicit limit, so the shipped 50 was pinned only by
TestDepCyclesLimitFlagRegistration's DefValue != "0". It reads the default off
the command and renders past it, so it tracks whatever ships; ids are
fixed-width so "past the cap" cannot match as a prefix of one inside it.

Mutation (3 arms, control restored byte-identical by cp -- the fixset was
uncommitted): gate the cap on includeTracks => capped + registered_default RED;
default 50 -> 0 => LimitFlagRegistration + registered_default RED (the new arm
independently catches an unbounded default); shown[:limit+1] => capped +
registered_default RED, so the arm pins the boundary and not merely "some
truncation". no_limit stays green under all three by design.

Validation: gofmt clean, git diff --check clean, go build ./... rc=0, go vet
clean on cmd/bd and issueops, cmd/bd dep-cycles selector 9 PASS / 0 FAIL / 0
SKIP (same top-level roster, +1 subtest). No production behavior changed this
iteration -- doc text plus one test arm.

Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>

---------

Co-authored-by: sjarmak <t@t.co>
Co-authored-by: Gas City Adopt-PR <adopt-pr@gascity.local>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
2026-09-30 20:20:17 -07:00

182 lines
6.3 KiB
Go

package main
import (
"errors"
"fmt"
"os"
"github.com/steveyegge/beads/internal/storage"
"github.com/steveyegge/beads/internal/storage/uow"
"github.com/steveyegge/beads/internal/ui"
"github.com/steveyegge/beads/issueops"
)
// `bd dep cycles`, and the post-add warning every route that wires an edge
// prints, on ONE role and ONE renderer.
// openCycleDetector hands back the cycle role for whichever route this
// invocation is on.
func openCycleDetector() (issueops.CycleDetector, error) {
if usesProxiedServer() {
return proxiedCycleDetector()
}
return store.CycleDetector()
}
// proxiedCycleDetector hands back the guarded cycle-report surface for the
// proxied-server provider, through the provider's own capability accessor.
func proxiedCycleDetector() (issueops.CycleDetector, error) {
if uowProvider == nil {
return nil, errors.New("proxied-server UOW provider not initialized")
}
src, ok := uowProvider.(uow.CycleDetectorSource)
if !ok {
return nil, fmt.Errorf("proxied-server provider %T does not offer the cycle-report surface", uowProvider)
}
return src.CycleDetector()
}
// runDepCycles is the whole of `bd dep cycles` on both routes. includeTracks
// widens the walk per issueops.DetectCyclesRequest.IncludeTracks; the default
// invocation leaves it false and the walk unchanged.
//
// limit caps how many cycles are PRINTED, and nothing else: 0 prints them all.
// THE CAP IS UNCONDITIONAL — it does not consult includeTracks, so it bounds
// the default walk's rendering too, and plain `bd dep cycles` now prints at most
// 50 cycles where before this change it printed every one. The widened walk is
// what makes the cap necessary rather than what scopes it: that walk is bounded
// by the scheduling-edge count and not by the number of deadlocks (see that
// field's BOUND), so a tracks-dense workspace can hold a correct report longer
// than anyone can read. Capping both walks by one rule is the deliberate
// choice — an operator can predict one rendering rule, and a --limit that
// silently did nothing without a second flag would be the worse surprise. It
// also matches --limit in list/search/stale/find_duplicates, which cap
// unconditionally.
//
// It stays a rendering cap rather than a narrower request on EITHER walk:
// CycleReport.Cycles promises to omit no cycle, and a --json consumer diffing
// two snapshots needs the whole of it. So the count this prints is always the
// whole report's, the truncation says how much it held back, and the --json
// branch below is never capped.
func runDepCycles(includeTracks bool, limit int) error {
detector, err := openCycleDetector()
if err != nil {
return HandleErrorRespectJSON("%v", err)
}
report, err := detector.DetectCycles(rootCtx, issueops.DetectCyclesRequest{IncludeTracks: includeTracks})
if err != nil {
return HandleErrorRespectJSON("%v", err)
}
if jsonOutput {
// The role's slice is empty rather than nil for an acyclic workspace, so
// this is `[]` and never `null` without a guard here.
return outputJSON(report.Cycles)
}
if len(report.Cycles) == 0 {
fmt.Printf("\n%s No dependency cycles detected\n\n", ui.RenderPass("✓"))
return nil
}
fmt.Printf("\n%s Found %d dependency cycles:\n\n", ui.RenderFail("⚠"), len(report.Cycles))
shown := report.Cycles
if limit > 0 && len(shown) > limit {
shown = shown[:limit]
}
for i, cycle := range shown {
if missing := unknownCycleMembers(cycle); missing > 0 {
fmt.Printf("%d. Cycle involving (%d of %d members have no record in this database):\n",
i+1, missing, len(cycle.Members))
} else {
fmt.Printf("%d. Cycle involving:\n", i+1)
}
for _, member := range cycle.Members {
fmt.Printf(" - %s: %s\n", member.ID, cycleMemberTitle(member))
}
fmt.Println()
}
if len(shown) < len(report.Cycles) {
fmt.Printf("... and %d more not shown. The count above is the whole report; use --limit 0 to print all of it.\n\n",
len(report.Cycles)-len(shown))
}
return nil
}
// cycleMemberTitle renders a member's description, naming the absence rather
// than printing a blank line after the id.
func cycleMemberTitle(member issueops.CycleMember) string {
if member.Issue == nil {
return ui.RenderMuted("(no record in this database)")
}
return member.Issue.Title
}
func unknownCycleMembers(cycle issueops.Cycle) int {
missing := 0
for _, member := range cycle.Members {
if member.Issue == nil {
missing++
}
}
return missing
}
// warnIfCyclesExist sweeps for cycles after an edge lands and prints a warning
// on stderr if it finds any.
//
// It takes a STORE rather than using the global one because the direct dep and
// link routes resolve their endpoints with routing: the edge may have landed in
// another project's database, and sweeping this one would answer about a graph
// the write did not touch.
func warnIfCyclesExist(s storage.DoltStorage) {
if s == nil {
return // Skip the sweep if the store is not available.
}
detector, err := s.CycleDetector()
if err != nil {
printCycleDetectionError(err)
return
}
report, err := detector.DetectCycles(rootCtx, issueops.DetectCyclesRequest{})
if err != nil {
printCycleDetectionError(err)
return
}
printCycleWarnings(report.Cycles)
}
func printCycleDetectionError(err error) {
if err != nil {
fmt.Fprintf(os.Stderr, "Warning: Failed to check for cycles: %v\n", err)
}
}
// printCycleWarnings renders the post-add warning: one arrow path per cycle,
// closed by repeating the first member.
//
// The path is spelled from the role's MEMBER IDS, which are complete whether or
// not each member has a row behind it: a cycle whose middle node has no record
// used to print as a shorter path, or not at all.
func printCycleWarnings(cycles []issueops.Cycle) {
if len(cycles) == 0 {
return
}
fmt.Fprintf(os.Stderr, "\n%s Warning: Dependency cycle detected!\n", ui.RenderWarn("⚠"))
fmt.Fprintf(os.Stderr, "This can hide issues from the ready work list and cause confusion.\n\n")
fmt.Fprintf(os.Stderr, "Cycle path:\n")
for _, cycle := range cycles {
for j, member := range cycle.Members {
if j == 0 {
fmt.Fprintf(os.Stderr, " %s", member.ID)
} else {
fmt.Fprintf(os.Stderr, " → %s", member.ID)
}
}
if len(cycle.Members) > 0 {
fmt.Fprintf(os.Stderr, " → %s", cycle.Members[0].ID)
}
fmt.Fprintf(os.Stderr, "\n")
}
fmt.Fprintf(os.Stderr, "\nRun 'bd dep cycles' for detailed analysis.\n\n")
}