depgraph.reef - zygaena/zyginit

root / src / depgraph.reef
depgraph.reef Reef 391 lines 11.0 KB
/******************************************************************************
                __               ____                __
               / /   ___  ____ _/ __/_____________ _/ /__
              / /   / _ \/ __ `/ /_/ ___/ ___/ __ `/ / _ \
             / /___/  __/ /_/ / __(__  ) /__/ /_/ / /  __/
            /_____/\___/\__,_/_/ /____/\___/\__,_/_/\___/

    (C)opyright 2025-2026, Leafscale, LLC -  https://www.leafscale.com

    Project: zyginit
   Filename: depgraph.reef
    Authors: Chris Tusa <chris.tusa@leafscale.com>
    License: <see LICENSE file included with this source code>
Description: Dependency graph and topological sort for service boot order

******************************************************************************/

module depgraph

import config
import collections.hashmap as hashmap
import core.str

export
    type DepGraph

    fn MAX_SERVICES(): int
    fn MAX_DEPS(): int

    fn new_depgraph(): DepGraph
    fn add_service(graph: DepGraph, name: string): int
    fn add_dependency(graph: DepGraph, name: string, dep_name: string): bool
    fn build_graph(graph: DepGraph, services: [config.ServiceDef], count: int): bool
    fn topo_sort(graph: DepGraph, tiers: [string], tier_counts: [int], max_tiers: int): int
    fn has_cycle(graph: DepGraph): bool
    fn service_count(graph: DepGraph): int
    fn service_name_at(graph: DepGraph, idx: int): string
end export

// ============================================================================
// Constants
// ============================================================================

fn MAX_SERVICES(): int
    return 128
end MAX_SERVICES

fn MAX_DEPS(): int
    return 16
end MAX_DEPS

// ============================================================================
// DepGraph type
// ============================================================================

type DepGraph = struct
    // Service names indexed 0..count-1
    names: [string]
    count: int

    // Name to index lookup
    name_map: hashmap.HashMap[int]

    // Adjacency: flattened array, deps[i * MAX_DEPS + j] = index of dep j for service i
    deps: [int]
    dep_count: [int]

    // In-degree for topological sort
    in_degree: [int]
end DepGraph

fn new_depgraph(): DepGraph
    let max = MAX_SERVICES()
    let max_d = MAX_DEPS()

    let g = DepGraph{
        names: new [string](max),
        count: 0,
        name_map: hashmap.create[:int](0 - 1),
        deps: new [int](max * max_d),
        dep_count: new [int](max),
        in_degree: new [int](max)
    }

    // Initialize dep_count and in_degree to 0
    mut i = 0
    while i < max
        g.dep_count[i] = 0
        g.in_degree[i] = 0
        i = i + 1
    end while

    return g
end new_depgraph

// ============================================================================
// Graph construction
// ============================================================================

// Add a service node to the graph. Returns its index, or -1 if full.
fn add_service(graph: DepGraph, name: string): int
    // Check if already exists
    if graph.name_map.has(name)
        return graph.name_map.get(name)
    end if

    if graph.count >= MAX_SERVICES()
        return 0 - 1
    end if

    let idx = graph.count
    graph.names[idx] = name
    graph.name_map.set(name, idx)
    graph.dep_count[idx] = 0
    graph.in_degree[idx] = 0
    graph.count = graph.count + 1

    return idx
end add_service

// Add a dependency edge: "name" depends on "dep_name".
// Both must already be in the graph. Returns true on success.
fn add_dependency(graph: DepGraph, name: string, dep_name: string): bool
    if not graph.name_map.has(name)
        return false
    end if
    if not graph.name_map.has(dep_name)
        return false
    end if

    let from_idx = graph.name_map.get(name)
    let to_idx = graph.name_map.get(dep_name)
    let dc = graph.dep_count[from_idx]

    if dc >= MAX_DEPS()
        return false
    end if

    // Check for duplicate edge
    let base = from_idx * MAX_DEPS()
    mut i = 0
    while i < dc
        if graph.deps[base + i] == to_idx
            return true
        end if
        i = i + 1
    end while

    // Add edge: from_idx depends on to_idx
    graph.deps[base + dc] = to_idx
    graph.dep_count[from_idx] = dc + 1

    // Increment in-degree of from_idx (it has one more dependency)
    graph.in_degree[from_idx] = graph.in_degree[from_idx] + 1

    return true
end add_dependency

// Build the dependency graph from an array of ServiceDefs.
// Returns true on success, false if a cycle is detected.
fn build_graph(graph: DepGraph, services: [config.ServiceDef], count: int): bool
    // First pass: add all service nodes
    mut i = 0
    while i < count
        let name = config.svc_name(services[i])
        if str.length(name) > 0
            add_service(graph, name)
        end if
        i = i + 1
    end while

    // Second pass: add dependency edges
    i = 0
    while i < count
        let name = config.svc_name(services[i])

        // Add "requires" edges
        let req = config.svc_requires(services[i])
        let req_count = config.svc_requires_count(services[i])
        mut j = 0
        while j < req_count
            let dep_name = req[j]
            if graph.name_map.has(dep_name)
                add_dependency(graph, name, dep_name)
            else
                println("depgraph: warning: " + name + " requires unknown service: " + dep_name)
            end if
            j = j + 1
        end while

        // Add "after" edges (ordering only, same graph treatment)
        let aft = config.svc_after(services[i])
        let aft_count = config.svc_after_count(services[i])
        j = 0
        while j < aft_count
            let dep_name = aft[j]
            if graph.name_map.has(dep_name)
                add_dependency(graph, name, dep_name)
            end if
            // Silently skip unknown "after" deps — they are soft ordering hints
            j = j + 1
        end while

        i = i + 1
    end while

    // Check for cycles
    if has_cycle(graph)
        println("depgraph: error: dependency cycle detected")
        return false
    end if

    return true
end build_graph

// ============================================================================
// Topological sort (Kahn's algorithm)
// ============================================================================

// Perform topological sort and group services into parallel tiers.
// Returns the number of tiers. Tiers are written into tiers[] as a flat
// array, with tier_counts[t] indicating how many services are in tier t.
// Services within a tier can start in parallel.
fn topo_sort(graph: DepGraph, tiers: [string], tier_counts: [int], max_tiers: int): int
    let n = graph.count

    if n == 0
        return 0
    end if

    // Copy in_degree to working array (preserve original)
    let work_degree = new [int](MAX_SERVICES())
    mut i = 0
    while i < n
        work_degree[i] = graph.in_degree[i]
        i = i + 1
    end while

    // Track which nodes have been placed
    let placed = new [bool](MAX_SERVICES())
    i = 0
    while i < n
        placed[i] = false
        i = i + 1
    end while

    mut total_placed = 0
    mut tier_idx = 0
    mut tier_offset = 0

    while total_placed < n and tier_idx < max_tiers
        // Find all nodes with in_degree == 0 that haven't been placed
        mut tier_size = 0

        i = 0
        while i < n
            if not placed[i] and work_degree[i] == 0
                tiers[tier_offset + tier_size] = graph.names[i]
                tier_size = tier_size + 1
                placed[i] = true
            end if
            i = i + 1
        end while

        if tier_size == 0
            // No progress — remaining nodes form a cycle
            break
        end if

        tier_counts[tier_idx] = tier_size

        // Decrement in_degree for all nodes that depend on placed nodes
        // For each placed node in this tier, find who depends on it
        mut t = 0
        while t < tier_size
            let placed_name = tiers[tier_offset + t]
            let placed_idx = graph.name_map.get(placed_name)

            // Scan all nodes to find those that depend on placed_idx
            i = 0
            while i < n
                if not placed[i]
                    let base = i * MAX_DEPS()
                    let dc = graph.dep_count[i]
                    mut d = 0
                    while d < dc
                        if graph.deps[base + d] == placed_idx
                            work_degree[i] = work_degree[i] - 1
                        end if
                        d = d + 1
                    end while
                end if
                i = i + 1
            end while

            t = t + 1
        end while

        total_placed = total_placed + tier_size
        tier_offset = tier_offset + tier_size
        tier_idx = tier_idx + 1
    end while

    if total_placed < n
        println("depgraph: error: cycle detected, could not place all services")
    end if

    return tier_idx
end topo_sort

// ============================================================================
// Cycle detection
// ============================================================================

// Check for cycles using iterative Kahn's — if we can't place all nodes,
// there's a cycle.
fn has_cycle(graph: DepGraph): bool
    let n = graph.count
    if n == 0
        return false
    end if

    let work_degree = new [int](MAX_SERVICES())
    mut i = 0
    while i < n
        work_degree[i] = graph.in_degree[i]
        i = i + 1
    end while

    // Queue-based Kahn's — just count how many we can place
    let queue = new [int](MAX_SERVICES())
    mut head = 0
    mut tail = 0

    // Enqueue all nodes with in_degree 0
    i = 0
    while i < n
        if work_degree[i] == 0
            queue[tail] = i
            tail = tail + 1
        end if
        i = i + 1
    end while

    mut placed = 0

    while head < tail
        let node = queue[head]
        head = head + 1
        placed = placed + 1

        // For each other node, if it depends on this node, decrement
        i = 0
        while i < n
            let base = i * MAX_DEPS()
            let dc = graph.dep_count[i]
            mut d = 0
            while d < dc
                if graph.deps[base + d] == node
                    work_degree[i] = work_degree[i] - 1
                    if work_degree[i] == 0
                        queue[tail] = i
                        tail = tail + 1
                    end if
                end if
                d = d + 1
            end while
            i = i + 1
        end while
    end while

    return placed < n
end has_cycle

// ============================================================================
// Accessors
// ============================================================================

fn service_count(graph: DepGraph): int
    return graph.count
end service_count

fn service_name_at(graph: DepGraph, idx: int): string
    if idx >= 0 and idx < graph.count
        return graph.names[idx]
    end if
    return ""
end service_name_at

end module