topological sort in cue

topologicalsort.cue

import "list"
// it's possible to do a topological sort of a DAG in cue without functions
// by using lazy evaluation to calculate the depth of all nodes
// (calculated as max of all children + 1)
// and then build a list using this for ordering
// (there may be multiple at a given level so we have to flatten).

// this works because we ensure that each node's level is always
// greater than all its children, therefore will always order
// after anything that it is dependent on.
// A benefit of the depth sorting approach is that nodes come as early as possible,
// which isn't the case when just concatenating each separate DFS's in the order
// they appear in the input.
// i don't actually know off-the-top-of-my-head if iterating over object keys in cue
// is guaranteed to be a deterministic order? It seems to be from my runs of this code.

// the output of this cue script (in yaml) is:
//output:
//  - id: nodeA
//  - id: nodeH
//  - id: nodeB
//  - id: nodeC
//  - id: nodeD
//  - id: nodeI
//  - id: nodeJ
//  - id: nodeE
//  - id: nodeF
//  - id: nodeG

// Any cycles will cause it to fail to evaluate

_input: {
    nodeA: _needs: []
    nodeB: _needs: ["nodeA"]
    nodeC: _needs: ["nodeA"]
    nodeD: _needs: ["nodeB", "nodeC"]
    nodeE: _needs: ["nodeB", "nodeD"]
    nodeF: _needs: ["nodeA", "nodeD"]
    nodeG: _needs: ["nodeC", "nodeE", "nodeF"]
    nodeH: _needs: []
    nodeI: _needs: ["nodeH", "nodeC"]
    nodeJ: _needs: ["nodeB", "nodeC"]
}
// calculate the level of each item with self referencing
_withLevel: {
  for k, v in _input {
    "\(k)": {
      _level: list.Max([for i in v._needs { _withLevel["\(i)"]._level + 1 }, 0]),
    }
  }
}
// index by calculated level for easy indexing in list comprehension
_ixByLevel: {
  for k, v in _withLevel {
    "\(v._level)": "\(k)": v
  }
}
// get max level for range query
let max = list.Max([for k, v in _withLevel {v._level}])
output: list.FlattenN([for i in list.Range(0, max + 1, 1) {
  [for k, v in _ixByLevel["\(i)"] {v, id: k}]
}], 1)