website-htmx-rustelo-code/scripts/content/validate-dag.nu

#!/usr/bin/env nu

# DAG Cycle Detector for Reflection Mode Graphs
#
# Validates that the depends_on relationships within each Mode form a true
# Directed Acyclic Graph using Kahn's topological sort algorithm.
#
# Nickel contracts (schema.ncl) already enforce:
#   - Step ID uniqueness within a mode
#   - Referential integrity (every depends_on.step references an existing step)
#
# This script adds the third guarantee: acyclicity.
#
# Usage:
#   nu scripts/content/validate-dag.nu site/reflection/content/blog/mod.ncl
#   nu scripts/content/validate-dag.nu --type blog
#   nu scripts/content/validate-dag.nu --all

def main [
    path: string = ""
    --type: string = ""    # resolve path from site/reflection/content/{type}/mod.ncl
    --all                  # validate all content types under site/reflection/content/
    --verbose
] {
    let paths = if $all {
        glob "site/reflection/content/*/mod.ncl" | where { |p| not ($p | str contains "_") }
    } else if $type != "" {
        [$"site/reflection/content/($type)/mod.ncl"]
    } else if $path != "" {
        [$path]
    } else {
        error make { msg: "Provide a path, --type {type}, or --all" }
    }

    mut any_error = false

    for p in $paths {
        if not ($p | path exists) {
            print $"(ansi red)NOT FOUND(ansi reset) ($p)"
            $any_error = true
            continue
        }

        let data = nickel export ($p | path expand) | from json

        if not ("modes" in $data) {
            print $"(ansi yellow)SKIP(ansi reset) ($p) — no modes field"
            continue
        }

        let results = $data.modes | items { |mode_name, mode|
            validate_mode $mode_name $mode $verbose
        }

        let errors = $results | where { |r| $r.ok == false }

        if ($errors | is-empty) {
            print $"(ansi green)✓(ansi reset) ($p) — ($results | length) modes acyclic"
        } else {
            for e in $errors {
                print $"(ansi red)CYCLE(ansi reset) ($p) / ($e.mode): ($e.msg)"
            }
            $any_error = true
        }
    }

    if $any_error {
        exit 1
    }
}

# Validate a single mode using Kahn's topological sort.
# Returns { ok: bool, mode: string, msg: string }
def validate_mode [mode_name: string, mode: record, verbose: bool] {
    if not ("steps" in $mode) {
        return { ok: true, mode: $mode_name, msg: "" }
    }

    let steps = $mode.steps

    # in-degree of a step = number of its own prerequisites (len of depends_on)
    mut in_degree = $steps | reduce -f {} { |step, acc|
        let deps = if "depends_on" in $step { $step.depends_on } else { [] }
        $acc | insert $step.id ($deps | length)
    }

    # adj[X] = steps that depend on X — when X completes, decrement their in-degree
    mut adj = $steps | reduce -f {} { |step, acc|
        $acc | insert $step.id []
    }
    for step in $steps {
        let deps = if "depends_on" in $step { $step.depends_on } else { [] }
        for dep in $deps {
            let cur = $adj | get $dep.step
            $adj = $adj | update $dep.step ($cur | append $step.id)
        }
    }

    # Kahn's algorithm: start with steps that have no dependencies
    mut queue  = $steps | where { |s| ($in_degree | get $s.id) == 0 } | get id
    mut sorted = []

    while ($queue | length) > 0 {
        let node = $queue | first
        $queue  = $queue | skip 1
        $sorted = $sorted | append $node

        for dependent in ($adj | get $node) {
            let new_deg = ($in_degree | get $dependent) - 1
            $in_degree  = $in_degree | update $dependent $new_deg
            if $new_deg == 0 {
                $queue = $queue | append $dependent
            }
        }
    }

    let total = $steps | length

    if ($sorted | length) == $total {
        if $verbose {
            print $"  ($mode_name): topological order → ($sorted | str join ' → ')"
        }
        { ok: true, mode: $mode_name, msg: "" }
    } else {
        # Nodes not in sorted have cyclic dependencies
        let all_ids  = $steps | get id
        let in_cycle = $all_ids | where { |id| not ($id in $sorted) }
        { ok: false, mode: $mode_name, msg: $"cycle among steps: ($in_cycle | str join ', ')" }
    }
}