dag.ts

/**
 * Type-Level Directed Acyclic Graph (DAG) Enforcer
 * * This file demonstrates how to use TypeScript's recursive conditional types
 * to detect cycles in a statically defined graph at compile time.
 * * Note: Requires TypeScript 5.0+ for the `<const T>` type parameter feature.
 */

// ==========================================
// 1. Core Types & Recursion
// ==========================================

/**
 * The basic shape of our graph: a dictionary where keys are node IDs 
 * and values are arrays of child node IDs.
 */
type Graph = Record<string, readonly string[]>;

/**
 * Recursively walks a path in the graph to check for cycles.
 * * @template G - The entire graph literal.
 * @template CurrentNode - The node currently being evaluated.
 * @template Visited - A union of all nodes visited on the current path.
 */
type CheckPath<
  G extends Graph,
  CurrentNode extends string,
  Visited extends string = never
> = CurrentNode extends Visited
  // BASE CASE A: The current node is in our Visited union. Cycle detected!
  ? `Error: Cycle detected at node '${CurrentNode}'`
  : CurrentNode extends keyof G
    // RECURSIVE CASE: Node is safe so far. Add it to Visited and check its children.
    ? CheckChildren<G, G[CurrentNode], Visited | CurrentNode>
    // BASE CASE B: Leaf node (no children defined in the graph). Safe.
    : unknown;

/**
 * Helper type to iterate through an array of child nodes.
 */
type CheckChildren<
  G extends Graph,
  Children extends readonly string[],
  Visited extends string
> = Children extends readonly [infer FirstChild extends string, ...infer Rest extends readonly string[]]
  // Check the first child
  ? CheckPath<G, FirstChild, Visited> extends infer Result
    ? Result extends string
      // If a cycle was found, bubble the error string up
      ? Result
      // Otherwise, recursively check the remaining children in the array
      : CheckChildren<G, Rest, Visited>
    : never
  // Array is empty (no more children to check). Path is clear.
  : unknown;

/**
 * Iterates over every node in the graph and validates its paths.
 * If a cycle is detected, it overwrites that node's value with an error string,
 * which intentionally breaks the compiler's type matching.
 */
type EnforceDAG<G extends Graph> = {
  [Node in keyof G]: CheckPath<G, Node & string> extends infer Result
    ? Result extends string
      ? Result // Inject the error string
      : G[Node] // Keep the original array if safe
    : G[Node]
};


// ==========================================
// 2. The Validation Function
// ==========================================

/**
 * Identity function that enforces the DAG constraint.
 * * The `<const G extends Graph>` forces TypeScript to infer the graph as a 
 * strict literal (e.g., `["B"]` instead of `string[]`), which is required 
 * for the type-level traversal to work.
 * * It intersects the input graph with `EnforceDAG<G>`. If `EnforceDAG` found 
 * a cycle, it changes a node's type to a string, causing a type mismatch error here.
 */
const defineDAG = <const G extends Graph>(graph: G & EnforceDAG<G>): G => graph;


// ==========================================
// 3. Examples & Usage
// ==========================================

// ✅ VALID DAG
// Compiles perfectly. Hovering over `validGraph` shows the exact literal types.
const validGraph = defineDAG({
  A: ["B", "C"],
  B: ["D"],
  C: ["D"],
  D: ["E"],
  E: []
});

// ❌ INVALID GRAPH (Simple Cycle)
// TypeScript Error: Type 'readonly ["A"]' is not assignable to type '"Error: Cycle detected at node 'A'"'.
const invalidGraph = defineDAG({
  A: ["B"],
  B: ["C"],
  C: ["A"] // <-- Cycle here! C points back to A
});

// ❌ INVALID GRAPH (Self-Referential)
// TypeScript Error: Type 'readonly ["F"]' is not assignable to type '"Error: Cycle detected at node 'F'"'.
const selfReferentialGraph = defineDAG({
  F: ["F"] // <-- Cycle here! F points to itself
});

// ❌ INVALID GRAPH (Deep Cycle)
// TypeScript Error surfaces at the node that completes the loop.
const deepCycleGraph = defineDAG({
  Start: ["Node1"],
  Node1: ["Node2"],
  Node2: ["Node3"],
  Node3: ["Node4"],
  Node4: ["Node2"], // <-- Cycle here! Node4 points back up the chain to Node2
  Standalone: []
});