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 produces a legal class schedule that lets you take each course only after its prereqs.

Technical Deep Dive

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. This is the Kahn-style adjacency: edge from dependant to dependency. Operations that need the reverse (which services break if I touch X?) compute the transpose on demand.

Cycle Detection

TopologicalOrder uses Kahn’s algorithm: pick nodes with zero in-degree, peel, decrement neighbours. If after peeling the result slice is shorter than len(Nodes), a cycle exists; the function returns an error naming the unprocessed nodes (the cycle members are the survivors).

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

• In-degree → number of incoming edges into a node; Kahn starts at zero in-degree.
• 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: 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] introduces a cycle api ↔ shield ↔ web; TopologicalOrder returns an error naming all three.