130 lines
4.2 KiB
Text
130 lines
4.2 KiB
Text
#!/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 ', ')" }
|
|
}
|
|
}
|