1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

// depgraph.reef — Dependency graph and topological sort
//
// Builds a directed acyclic graph from ServiceDef dependencies,
// performs topological sort to determine boot order, and identifies
// services that can start in parallel.
//
// This module has no illumos dependencies — can be tested on any platform.

import config.{ServiceDef}

// A node in the dependency graph
struct DepNode {
    name: String,
    service: ServiceDef,
    edges: Vec<String>,     // services this depends on (requires + after)
    in_degree: i32,         // number of unsatisfied dependencies
}

// The full dependency graph
struct DepGraph {
    nodes: Map<String, DepNode>,
}

// Build a dependency graph from a list of service definitions
fn build_graph(services: Vec<ServiceDef>) -> Result<DepGraph, String> {
    // TODO: implement
    // 1. Create a DepNode for each service
    // 2. Add edges for requires + after dependencies
    // 3. Detect missing dependencies (warn, don't fail)
    // 4. Detect cycles (fail with clear error message)
    Err("not yet implemented")
}

// Topological sort — returns services grouped by startup tier
// Services within the same tier can start in parallel.
//
// Returns: Vec<Vec<String>> — each inner Vec is a parallel tier
// Example: [["root-fs"], ["filesystem", "loopback"], ["network", "syslog"], ["sshd", "cron"]]
fn topo_sort(graph: DepGraph) -> Result<Vec<Vec<String>>, String> {
    // TODO: implement using Kahn's algorithm
    // 1. Find all nodes with in_degree == 0 → first tier
    // 2. Remove those nodes, decrement in_degree of dependents
    // 3. Repeat until all nodes placed
    // 4. If nodes remain with in_degree > 0 → cycle detected
    Err("not yet implemented")
}

// Check for dependency cycles — returns the cycle path if found
fn detect_cycle(graph: DepGraph) -> Option<Vec<String>> {
    // TODO: implement using DFS with coloring
    None
}