Service Dependency Graph & Topological Order

ELI5

Services are like courses in a university: some have prerequisites, the registrar (BuildDependencyGraph) sketches the arrows, and the topological-order routine walks each course’s prerequisites first, so you only take a course after everything it needs.

Technical Deep Dive

Source: nestr-tools/engine internal/project/model.go:44-168 @e9180e4 (file last changed 2026-04-02), read 2026-10-25. Corrected in this revision: the order is computed by depth-first search with visiting/visited marks, not Kahn’s algorithm, and a cycle error names one node.

Defined in engine/internal/project/model.go:

type DependencyGraph struct {
    Nodes []string
    Edges map[string][]string // service -> dependencies (depends-on)
}

Project.BuildDependencyGraph() walks Services, copies service.Config.Dependencies into Edges[name], and TopologicalOrder() returns a slice in execution order (deps first).

Construction

flowchart LR
    Cfg[.nest.yaml services map] --> P[Project.Services]
    P --> BG[BuildDependencyGraph]
    BG --> G[(DependencyGraph<br/>Nodes,Edges)]
    G --> TO[TopologicalOrder]
    TO --> ORD[ordered service slice]
    ORD --> ASM[assemble pipeline]

Edge Direction

Edges["api"] = ["shield"] means api depends on shield — i.e. shield must be cloned/built before api. The edge points from dependant to dependency. Operations that need the reverse (which services break if I touch X?) compute the transpose on demand.

Cycle Detection

TopologicalOrder runs a depth-first search from each node in Nodes order. It marks a node visiting, recurses into each dependency in Edges[node], then marks it visited and appends it, so dependencies land before dependants. Meeting a node that is still visiting means a back edge: the function returns dependency cycle detected at <node> naming the node where the cycle was entered (model.go:93-127). ValidateNoCycles runs the same walk without building the order.

Where the Order is Used

• assemble: clones / pulls services in topological order, optionally in parallel using a fan-out limited by assembly.parallel_clones.
• operations/run: when called with services: [], expands to the topological order so dependencies execute first.
• sync: order is irrelevant for sync direction but used to prioritise which working tree to read first when conflict_resolution=prompt.

Key Terms

• Visiting / visited → the two DFS marks; reaching a visiting node again is a cycle.
• Transpose → flipping all edges; converts “what does X need” into “what needs X”.
• Parallel clones → fan-out width during assemble; bounded by assembly.parallel_clones.

Q&A

Q: Where is BuildDependencyGraph defined? A: On Project in engine/internal/project/model.go:53; it copies each service’s configured Dependencies into Edges.

Q: What does Edges map represent — depends-on or required-by? A: Depends-on: Edges["api"] = ["shield"] means api needs shield first.

Q: How does the engine signal a cycle? A: TopologicalOrder (and ValidateNoCycles) return an error, dependency cycle detected at <node>, when the depth-first walk reaches a node still marked visiting.

Q: What is the order of two services with no dependency relation? A: Implementation-defined and stable per run, derived from map iteration over Services. Tests should not depend on a specific tie-break.

Q: Can a service depend on itself? A: That is a self-loop and produces a cycle of length 1 — TopologicalOrder reports it. The engine does not silently drop self-edges.

Q: Is the graph rebuilt every operation or cached? A: Rebuilt per call in this revision; cost is linear in len(services). Caching makes sense once the workspace exceeds tens of services.

Examples

A workspace with api → [shield], web → [api, shield], shield → [] produces the order [shield, api, web]. Adding shield → [api] creates the cycle api → shield → api; TopologicalOrder returns dependency cycle detected at <node> for whichever of the two it re-enters first, which depends on node order.