Attempt to generate a list of packages that need updated in order to update a dependency. My ideal goal for something like this is to run a script via `npx` in a project, with something like `--target=multiformats@11.0.0` and get out a list of dependencies to update working in a depth-first order.

output.txt

╰─ ✔ ❯ npx -y ts-node parse-ls-output.ts
Package update order:
interface-ipfs-core - (depended on by 1 packages)
@ipld/car - (depended on by 1 packages)
@libp2p/interface-peer-id - (depended on by 1 packages)
@libp2p/peer-id-factory - (depended on by 1 packages)
@libp2p/peer-id - (depended on by 1 packages)
blockstore-core - (depended on by 1 packages)
dag-jose - (depended on by 1 packages)
did-jwt - (depended on by 1 packages)
uint8arrays - (depended on by 1 packages)
ipfs-unixfs-importer - (depended on by 1 packages)
ipns - (depended on by 1 packages)
is-ipfs - (depended on by 1 packages)
ipfs-cli - (depended on by 1 packages)
ipfs-repo - (depended on by 1 packages)
ipfs-repo-migrations - (depended on by 1 packages)
@chainsafe/libp2p-gossipsub - (depended on by 1 packages)
@libp2p/peer-record - (depended on by 1 packages)
@libp2p/pubsub - (depended on by 1 packages)
@libp2p/pubsub - (depended on by 1 packages)
@libp2p/mdns - (depended on by 1 packages)
@libp2p/webrtc-star - (depended on by 1 packages)
blockstore-datastore-adapter - (depended on by 1 packages)
ipfs-core-types - (depended on by 1 packages)
@libp2p/interface-keychain - (depended on by 1 packages)
ipfs-core-utils - (depended on by 1 packages)
ipfs-core - (depended on by 1 packages)
@libp2p/delegated-content-routing - (depended on by 1 packages)
@libp2p/interface-content-routing - (depended on by 1 packages)
@libp2p/delegated-peer-routing - (depended on by 1 packages)
@libp2p/interface-dht - (depended on by 1 packages)
@libp2p/kad-dht - (depended on by 1 packages)
@libp2p/record - (depended on by 1 packages)
interface-blockstore-tests - (depended on by 1 packages)
interface-blockstore - (depended on by 1 packages)
ipfs-bitswap - (depended on by 1 packages)
ipfs-unixfs-exporter - (depended on by 1 packages)
libp2p - (depended on by 1 packages)
@libp2p/peer-store - (depended on by 1 packages)
ipfs-grpc-client - (depended on by 1 packages)
ipfs-http-client - (depended on by 1 packages)
ipfs-http-gateway - (depended on by 1 packages)
ipfs-http-server - (depended on by 1 packages)
ipfs-message-port-client - (depended on by 1 packages)
ipfs-message-port-protocol - (depended on by 1 packages)
ipfs-message-port-server - (depended on by 1 packages)
ipfs-interop - (depended on by 1 packages)
kubo-rpc-client - (depended on by 1 packages)

parse-ls-output.ts

/* eslint-disable no-console */
import * as multiformatsLsOutput from './multiformats-ls.json'
// import { DirectedGraph, DirectedAcyclicGraph } from 'typescript-graph'
import { DirectedGraph } from 'typescript-graph'

interface NpmLsOutputJson {
  name: string
  version: string
  resolved?: string
  dependencies?: Record<string, Omit<NpmLsOutputJson, 'name'>>
}

interface NodeType {
  name: string
  nameAndVersion: string
  path: string
  deps: string[]
  id: string
}

type DepMap = Map<string, DepMap | Set<string>>
const depsToUpdate: DepMap = new Map()

const getNodeId = (n: Omit<NodeType, 'id'>) => `${n.nameAndVersion}+${n.path}+${n.deps.join(',')}`
const getNodeDeps = (lsOutput: Pick<NpmLsOutputJson, 'dependencies'>): string[] => {
  if (lsOutput.dependencies == null) {
    return []
  }
  const deps = lsOutput.dependencies
  return Object.keys(deps).map((name) => {
    const depObj = deps[name]
    return `${name}@${depObj.version}`
  })
}
// const getDepsAsSt
const getGraphNode = (name: string, lsOutput: Pick<NpmLsOutputJson, 'dependencies' | 'resolved' | 'version'>): NodeType => {
  // console.log('name: ', name)
  // console.log('lsOutput: ', lsOutput)
  const newNode: Omit<NodeType, 'id'> = {
    name: getDepNameWithoutVersion(name),
    nameAndVersion: `${getDepNameWithoutVersion(name)}@${lsOutput.version}`,
    path: lsOutput.resolved ?? 'no path',
    deps: getNodeDeps(lsOutput)
  }

  return {
    ...newNode,
    id: getNodeId(newNode)
  }
}

// const addNodes = (graph: DirectedGraph<NodeType>, root: NodeType, child: NodeType) => {
//   graph.insert(child)
//   graph.addEdge(getNodeId(root), getNodeId(child))
// }
const getDepNameWithoutVersion = (nameWithVersion: string) => {
  const versionSplitIndex = nameWithVersion.lastIndexOf('@')
  if (versionSplitIndex <= 0) {
    return nameWithVersion
  }
  return nameWithVersion.substring(0, versionSplitIndex)
}
const nodes = new Set<string>()
const addNode = (graph: DirectedGraph<NodeType>, node: NodeType) => {
  if (!nodes.has(node.id)) {
    try {
      graph.insert(node)
      nodes.add(node.id)
    } catch (e) {
      console.error(`${node.id} is already in the graph`, e)
    }
  }
}
const buildGraph = (name: string, lsOutput: Pick<NpmLsOutputJson, 'dependencies' | 'resolved' | 'version'>, graph = new DirectedGraph<NodeType>((n) => n.id)) => {
  const rootNode = getGraphNode(name, lsOutput)
  // console.log('graph.getNodes().length: ', graph.getNodes().length)
  addNode(graph, rootNode)

  if (lsOutput.dependencies == null) {
    return graph
  }
  const lsOutputDeps = lsOutput.dependencies
  rootNode.deps.forEach((dep: string) => {
    // console.log('dep: ', dep)
    const depNameWithoutVersion = getDepNameWithoutVersion(dep)
    // console.log('depNameWithoutVersion: ', depNameWithoutVersion)
    const depLsJson = lsOutputDeps[depNameWithoutVersion]
    // if (depLsJson == null) {
    //   return
    // }

    const childNode = getGraphNode(depNameWithoutVersion, depLsJson)
    // addNodes(graph, rootNode, childNode)
    addNode(graph, childNode)
    graph.addEdge(rootNode.id, childNode.id)
    buildGraph(dep, depLsJson, graph)
  })

  return graph

  // const tree: DirectedGraph = {}
}
// const getCurrentLevelDeps = (currentLevel: NpmLsOutputJson) => {
//   Object.keys(multiformatsLsOutput.dependencies)
// }
// const coreDeps = Object.keys(multiformatsLsOutput.dependencies).forEach((dep) => depsToUpdate.set(dep, new Map<string, DepMap>()))
const graph = buildGraph(multiformatsLsOutput.name, multiformatsLsOutput)
// console.log(coreDeps)

console.log('Package update order:')
// graph.getNodes()
graph.getNodes()
  .filter((n) => {
    // ignore direct dependency
    if (n.name === 'multiformats') {
      return false
    }
    // ignore dependencies that do not depend on multiformats (no update needed)
    let hasMultiformatsDependency = false
    n.deps.forEach((depWithVersion) => {
      if (depWithVersion.includes('multiformats') === true) {
        hasMultiformatsDependency = true
      }
    })
    return hasMultiformatsDependency
  })
  .filter((n) => {
    // ignore dependencies depending on the desired version (no update needed)
    let hasDesiredVersion = false
    n.deps.forEach((depWithVersion) => {
      if (depWithVersion.includes('multiformats@11.0.0') === true) {
        hasDesiredVersion = true
      }
    })
    return !hasDesiredVersion
  })
  .sort((a, b): number => {
    const aInDegree = graph.indegreeOfNode(a.id)
    const bInDegree = graph.indegreeOfNode(b.id)
    if (aInDegree < bInDegree) {
      return 1
    }
    if (aInDegree > bInDegree) {
      return -1
    }
    return 0
  })
  .forEach((n: NodeType) => {
  // console.log('dependency name and version: ', n.nameAndVersion)
    console.log(`${n.name} - (depended on by ${String(graph.indegreeOfNode(n.id))} packages)`)
  // console.log('How many packages depend on this: ', graph.indegreeOfNode(n.id))
  // console.log()
  })