dependency-resolver.js

const _ = require('lodash')
const actionTree = generateActionTree()
const steps = resolveDependencies(actionTree)
console.log(steps)

function resolveDependencies(cmds) {
  const dependencies = fetchDependencies(actionTree)
  const steps = chunkIntoSteps(dependencies)
  return steps
}

function fetchDependencies(cmds) {
  const graph = {}
  cmds.forEach(cmd => {
    const node = cmd.set
    const inputs = cmd.input
    graph[node] = {}
    if (inputs) {
      Object.values(inputs).forEach(val => {
        graph[node][val.path[0]] = true
      })
    }
  })

  const dependencies = {}
  Object.keys(graph).forEach(node => {
    dependencies[node] = Object.keys(graph[node])
  })
  return dependencies
}

function chunkIntoSteps(dependencies) {
  const sources = fetchStartNodes(dependencies)
  let level = _.clone(sources)
  const done = _.clone(level)
  const todos = _.difference(Object.keys(dependencies), done)
  const levels = []
  while (level.length) {
    levels.push(level)
    // # Next level is jobs that have all dependencies done
    const newLevel = {}
    // # A clever data structure could find the next level in O(k log n)
    // # for a level size of k and n jobs. This needs O(n).
    todos.forEach(todo => {
      if (isSubset(dependencies[todo], done)) {
        newLevel[todo] = true
      }
    })

    const newLevelArray = Object.keys(newLevel)

    // remove items that differ in both sets
    updateDifference(todos, newLevelArray)
    done.push(...newLevelArray)
    level = newLevelArray
  }
  return levels
}

function fetchStartNodes(dependencies) {
  const sources = {}
  Object.keys(dependencies).forEach(node => {
    if (!dependencies[node].length) {
      sources[node] = true
    }
  })
  return Object.keys(sources)
}

function isSubset(a, ofB) {
  return a.every(val => ofB.includes(val));
}

function updateDifference(a, b) {
  for (let i = 0, n = a.length; i < n; i++) {
    let x = a[i]
    k:
    for (let j = 0, m = b.length; j < m; j++) {
      let y = b[j]
      if (x === y) {
        a.splice(i, 1)
        i--
        break k;
      }
    }
  }
}

function generateActionTree() {
  // this would be constructed through a bunch of real-world
  // functions, queuing up all the actions
  // and pointing outputs to inputs.
  return [
    { action: 'create', table: 'tb1', set: 'key1' },
    { action: 'create', table: 'tb2', set: 'key2' },
    { action: 'create', table: 'tb2', set: 'key3' },
    { action: 'create', table: 'tb3', set: 'key5' },
    { action: 'create', table: 'tb4', set: 'key6' },
    { action: 'create', table: 'tb3', set: 'key7' },
    { action: 'create', table: 'tb4', set: 'key8' },
    { action: 'create', table: 'tb3', set: 'key9' },
    { action: 'create', table: 'tb3', set: 'key10', input: {
      y: { type: 'binding', path: ['key6', 'foo'] },
      z: { type: 'binding', path: ['key1', 'bar'] }
    } },
    { action: 'create', table: 'tb1', set: 'key4', input: {
      x: { type: 'binding', path: ['key2', 'baz'] }
    } },
    { action: 'create', table: 'tb4', set: 'key11', input: {
      a: { type: 'binding', path: ['key10', 'z'] },
      b: { type: 'binding', path: ['key1', 'bar'] }
    } },
    { action: 'create', table: 'tb1', set: 'key12', input: {
      p: { type: 'binding', path: ['key10', 'z'] },
      q: { type: 'binding', path: ['key11', 'a'] }
    } },
    { action: 'create', table: 'tb4', set: 'key13' },
    { action: 'create', table: 'tb3', set: 'key14' },
    { action: 'create', table: 'tb4', set: 'key15', input: {
      a: { type: 'binding', path: ['key8', 'z'] },
    } },
    { action: 'create', table: 'tb5', set: 'key16' },
    { action: 'create', table: 'tb6', set: 'key17' },
    { action: 'create', table: 'tb6', set: 'key18', input: {
      m: { type: 'binding', path: ['key4', 'x'] },
    } },
    { action: 'create', table: 'tb6', set: 'key19', input: {
      m: { type: 'binding', path: ['key4', 'x'] },
      n: { type: 'binding', path: ['key13', 'a'] },
    } },
    { action: 'create', table: 'tb6', set: 'key20', input: {
      m: { type: 'binding', path: ['key18', 'm'] },
      n: { type: 'binding', path: ['key17', 'm'] },
    } },
    { action: 'create', table: 'tb1', set: 'key21' },
    { action: 'create', table: 'tb2', set: 'key22', input: {
      w: { type: 'binding', path: ['key18', 'm'] },
      x: { type: 'binding', path: ['key17', 'm'] },
    } },
    { action: 'create', table: 'tb2', set: 'key23' },
    { action: 'create', table: 'tb3', set: 'key24' },
  ]
}