build.nix

{ pkgs, h }:

let
  # Fetch devenv (pinned) to visualize its dependency graph
  flakeUrl = "github:cachix/devenv/713af7fe484e3d8a8898ef0fd163fd651639330a";
  flake = builtins.getFlake flakeUrl;

  # Root flake metadata (parsed from URL)
  rootMeta = {
    name = "devenv";
    type = "github";
    owner = "cachix";
    repo = "devenv";
    rev = "713af7fe484e3d8a8898ef0fd163fd651639330a";
  };

  # Read flake.lock for metadata (owner, repo, type)
  lockFile = builtins.readFile "${flake}/flake.lock";
  lock = builtins.fromJSON lockFile;
  lockNodes = lock.nodes;

  # Resolve a lock input reference (can be string or follows list)
  resolveLockRef = fallback: ref:
    if builtins.isList ref then
      if builtins.length ref == 0 then fallback
      else if builtins.length ref == 1 then builtins.head ref
      else
        # Follows reference like ["agenix", "nixpkgs"] -> resolve recursively
        let
          path = ref;
          resolveStep = acc: part:
            let
              node = lockNodes.${acc} or {};
              nextRef = node.inputs.${part} or part;
            in if builtins.isList nextRef then resolveLockRef part nextRef else nextRef;
          resolved = builtins.foldl' resolveStep (builtins.head path) (builtins.tail path);
        in resolved
    else ref;

  # Get metadata from lock file for a node name
  getLockMeta = lockName:
    let
      node = lockNodes.${lockName} or {};
      locked = node.locked or {};
      original = node.original or {};
    in {
      type = locked.type or original.type or null;
      owner = locked.owner or original.owner or null;
      repo = locked.repo or original.repo or null;
    };

  # Maximum depth to traverse (prevent explosion from shared deps)
  maxTraversalDepth = 2;

  # Recursively collect all flake inputs into a flat graph
  collectInputs = visited: queue:
    if queue == [] then visited
    else
      let
        current = builtins.head queue;
        name = current.name;
        input = current.input;
        depth = current.depth;
        lockName = current.lockName;
        rest = builtins.tail queue;
      in
        if visited ? ${name} || depth > maxTraversalDepth then collectInputs visited rest
        else
          let
            childInputs = input.inputs or {};
            children = builtins.attrNames childInputs;
            lockNode = lockNodes.${lockName} or {};
            lockInputs = lockNode.inputs or {};
            newQueue = rest ++ map (childName: {
              name = "${name}/${childName}";
              input = childInputs.${childName};
              depth = depth + 1;
              parent = name;
              lockName = resolveLockRef childName (lockInputs.${childName} or childName);
            }) children;
            meta = getLockMeta lockName;
            rev = input.rev or null;
          in collectInputs (visited // {
            ${name} = {
              inherit depth rev children;
              inherit (current) parent;
              inherit (meta) type owner repo;
            };
          }) newQueue;

  # Start from root (self) and traverse all inputs
  rootInputs = flake.inputs or {};
  rootChildren = builtins.attrNames rootInputs;
  rootLockNode = lockNodes.${lock.root} or {};
  rootLockInputs = rootLockNode.inputs or {};
  initialQueue = map (name: {
    inherit name;
    input = rootInputs.${name};
    depth = 1;
    parent = rootMeta.name;
    lockName = resolveLockRef name (rootLockInputs.${name} or name);
  }) rootChildren;

  # Add root node and collect everything
  rootName = rootMeta.name;
  allNodes = collectInputs {
    ${rootName} = {
      depth = 0;
      parent = null;
      type = rootMeta.type;
      owner = rootMeta.owner;
      repo = rootMeta.repo;
      rev = rootMeta.rev;
      children = rootChildren;
    };
  } initialQueue;

  nodeNames = builtins.attrNames allNodes;

  # Group nodes by depth for layout
  maxDepth = builtins.foldl' (a: b: if b > a then b else a) 0
    (map (name: allNodes.${name}.depth) nodeNames);

  nodesAtDepth = d:
    builtins.filter (name: allNodes.${name}.depth == d) nodeNames;

  # Layout constants
  nodeWidth = 140;
  nodeHeight = 36;
  levelGap = 80;
  nodeGap = 20;

  # Tree layout - children grouped under their parents
  # Get valid children of a node
  getChildren = name:
    let
      node = allNodes.${name};
      childNames =
        if name == rootName then node.children
        else map (c: "${name}/${c}") node.children;
    in builtins.filter (c: allNodes ? ${c}) childNames;

  # Compute subtree width for each node (bottom-up by depth)
  subtreeWidth =
    let
      computeAtDepth = d: acc:
        builtins.foldl' (acc': name:
          let
            children = getChildren name;
            childWidths = map (c: acc'.${c} or nodeWidth) children;
            sumWidth =
              if children == [] then nodeWidth
              else builtins.foldl' builtins.add 0 childWidths +
                   (builtins.length children - 1) * nodeGap;
          in acc' // { ${name} = if sumWidth > nodeWidth then sumWidth else nodeWidth; }
        ) acc (nodesAtDepth d);
    in builtins.foldl' (acc: i: computeAtDepth (maxDepth - i) acc) {}
       (builtins.genList (i: i) (maxDepth + 1));

  # Position nodes top-down, grouping children under parents
  computePositions =
    let
      # Find index of element in list
      findIndex = elem: lst:
        let
          go = i: xs:
            if xs == [] then 0
            else if builtins.head xs == elem then i
            else go (i + 1) (builtins.tail xs);
        in go 0 lst;

      # Process each depth level
      processDepth = d: acc:
        builtins.foldl' (acc': name:
          let
            node = allNodes.${name};
            myWidth = subtreeWidth.${name};
            parentName = node.parent;

            # Find subtree start position
            subtreeStart =
              if parentName == null then 0
              else
                let
                  parentInfo = acc'.${parentName};
                  parentWidth = subtreeWidth.${parentName};
                  siblings = getChildren parentName;
                  siblingsWidth = builtins.foldl' (a: s: a + subtreeWidth.${s}) 0 siblings +
                                  (builtins.length siblings - 1) * nodeGap;
                  siblingsStart = parentInfo.subtreeStart + (parentWidth - siblingsWidth) / 2;
                  myIndex = findIndex name siblings;
                  prevWidth = builtins.foldl' (a: i:
                    a + subtreeWidth.${builtins.elemAt siblings i} + nodeGap
                  ) 0 (builtins.genList (i: i) myIndex);
                in siblingsStart + prevWidth;

            x = subtreeStart + (myWidth - nodeWidth) / 2;
            y = d * levelGap + nodeGap;
          in acc' // { ${name} = { inherit x y subtreeStart; }; }
        ) acc (nodesAtDepth d);

      positions = builtins.foldl' (acc: d: processDepth d acc) {}
                  (builtins.genList (d: d) (maxDepth + 1));
      posList = map (name: { inherit name; } // positions.${name}) nodeNames;
      minX = builtins.foldl' (a: p: if p.x < a then p.x else a) 0 posList;
      maxX = builtins.foldl' (a: p: let px = p.x + nodeWidth; in if px > a then px else a) 0 posList;
    in {
      width = maxX - minX + 2 * nodeGap;
      height = (maxDepth + 1) * levelGap + nodeGap + nodeHeight;
      nodes = map (p: { name = p.name; x = p.x - minX + nodeGap; y = p.y; }) posList;
    };

  layout = computePositions;
  posLookup = builtins.listToAttrs (map (n: { name = n.name; value = n; }) layout.nodes);

  # Get display info for a node
  nodeInfo = name:
    let
      node = allNodes.${name};
      isRoot = name == rootName;
      inputCount = builtins.length node.children;
      displayName =
        if builtins.match ".*/.*" name != null
        then builtins.elemAt (builtins.match ".*/(.*)" name) 0
        else name;
    in {
      label = displayName;
      subtitle =
        if node.type == "github" then "${node.owner}/${node.repo}"
        else if node.type == "path" then "path"
        else if node.type != null then node.type
        else "input";
      url =
        if node.type == "github" && node.rev != null
        then "https://github.com/${node.owner}/${node.repo}/tree/${node.rev}"
        else null;
    };

  # Render a node box
  renderNode = pos:
    let
      info = nodeInfo pos.name;
      isRoot = pos.name == rootName;
      cx = pos.x + nodeWidth / 2;
      subtitleElem =
        if info.url != null
        then [ "a" { href = info.url; target = "_blank"; }
               [ "text" { x = toString cx; y = toString (pos.y + 26); class = "subtitle link"; } info.subtitle ] ]
        else [ "text" { x = toString cx; y = toString (pos.y + 26); class = "subtitle"; } info.subtitle ];
    in [
      [ "rect" {
        x = toString pos.x;
        y = toString pos.y;
        width = toString nodeWidth;
        height = toString nodeHeight;
        rx = "6";
        class = if isRoot then "node root" else "node";
      } ]
      [ "text" { x = toString cx; y = toString (pos.y + 14); class = "label"; } info.label ]
      subtitleElem
    ];

  # Render edges from parent to children
  renderEdges = name:
    let
      node = allNodes.${name};
      fromPos = posLookup.${name};
      fromX = fromPos.x + nodeWidth / 2;
      fromY = fromPos.y + nodeHeight;
      childFullNames = map (c: "${name}/${c}") node.children;
      validChildren = builtins.filter (c: posLookup ? ${c}) childFullNames;
    in map (childName:
      let
        toPos = posLookup.${childName};
        toX = toPos.x + nodeWidth / 2;
        toY = toPos.y;
      in [ "path" {
        d = "M${toString fromX},${toString fromY} C${toString fromX},${toString (fromY + 25)} ${toString toX},${toString (toY - 25)} ${toString toX},${toString toY}";
        class = "edge";
      } ]
    ) validChildren;

  # Root's children don't have the "root/" prefix
  rootEdges =
    let
      fromPos = posLookup.${rootName};
      fromX = fromPos.x + nodeWidth / 2;
      fromY = fromPos.y + nodeHeight;
    in map (childName:
      let
        toPos = posLookup.${childName};
        toX = toPos.x + nodeWidth / 2;
        toY = toPos.y;
      in [ "path" {
        d = "M${toString fromX},${toString fromY} C${toString fromX},${toString (fromY + 25)} ${toString toX},${toString (toY - 25)} ${toString toX},${toString toY}";
        class = "edge";
      } ]
    ) (builtins.filter (c: posLookup ? ${c}) rootChildren);

  allEdges = rootEdges ++ builtins.concatLists (
    map renderEdges (builtins.filter (n: n != rootName) nodeNames));
  allNodeElems = builtins.concatLists (map renderNode layout.nodes);

  page = h.renderPretty [
    "html" { lang = "en"; }
    [ "head"
      [ "meta" { charset = "utf-8"; } ]
      [ "title" "Flake Dependency Graph" ]
      [ "style" (h.raw ''
        body {
          margin: 0;
          display: flex;
          justify-content: center;
          align-items: center;
          min-height: 100vh;
          background: #1a1a2e;
        }
        svg { max-width: 95vw; max-height: 95vh; }
        .node { fill: #2d2d4a; stroke: #4a4a6a; stroke-width: 1.5; }
        .node.root { fill: #3d2d5a; stroke: #7a5af5; stroke-width: 2; }
        .label { fill: #fff; font: bold 11px system-ui, sans-serif; text-anchor: middle; }
        .subtitle { fill: #888; font: 9px system-ui, sans-serif; text-anchor: middle; }
        .subtitle.link { fill: #6a9fff; cursor: pointer; }
        .subtitle.link:hover { fill: #9ac0ff; text-decoration: underline; }
        .edge { fill: none; stroke: #4a4a6a; stroke-width: 1.5; }
      '') ]
    ]
    [ "body"
      [ "svg" {
        viewBox = "0 0 ${toString layout.width} ${toString layout.height}";
        xmlns = "http://www.w3.org/2000/svg";
      }
        allEdges
        allNodeElems
      ]
    ]
  ];

in pkgs.runCommand "graph" {} ''
  mkdir -p $out
  cp ${pkgs.writeText "index.html" page} $out/index.html
''