BREAKING: rewrite npm ls

- Rewrites lib/ls.js command to use @npmcli/arborist
- Updates unit tests
- Breaking changes:
  - added error codes: ELSPROBLEMS, EJSONPARSE to callback errors
  - extraneous deps depth will match current location in nm folder
  - mark top-level deps as extraneous when missing root package.json
  - don't mark deps as extraneous if they're valid deps of invalid deps
  - peer deps are now listed as regular deps, removed oddities such as
  peerinvalid label and stops labeling peer deps extraneous
  - might print diff git resolved values,
  see: https://github.com/npm/hosted-git-info
  - Parseable (--parseable) output:
    - possible order of printed elements changed
    - fixed consistency problems in which it would print root folder
    name if using a filter argument that could not match against
    any of the deps in the current installed tree
    - fixed printing non-existing paths for missing dependencies
    - fixed undefined symlink output when using --long output
  - JSON (--json) output:
    - removed: `from` property from --json output
    - removed: "[Circular]" references
    - added "missing" to list of peer-dep problems listed
    - added peerDependencies ref when using --long output
    - removed readme properties using --long output
    - Renamed error msg:
    `Failed to parse json` -> `Failed to parse root package.json`

refs:
  - https://github.com/npm/statusboard/issues/99
  - https://github.com/npm/statusboard/issues/103

1 files changed, 386 insertions, 473 deletions

diff --git a/lib/ls.js b/lib/ls.js
index 78a2b1d79..3fc07c7f1 100644
--- a/lib/ls.js
+++ b/lib/ls.js
@@ -1,554 +1,467 @@
-// show the installed versions of packages
-//
-// --parseable creates output like this:
-// <fullpath>:<name@ver>:<realpath>:<flags>
-// Flags are a :-separated list of zero or more indicators
-
-module.exports = exports = ls
-
-var path = require('path')
-var url = require('url')
-var readPackageTree = require('read-package-tree')
-var archy = require('archy')
-var semver = require('semver')
-var color = require('ansicolors')
-var moduleName = require('./utils/module-name.js')
-var npa = require('npm-package-arg')
-var sortedObject = require('sorted-object')
-var npm = require('./npm.js')
-var mutateIntoLogicalTree = require('./install/mutate-into-logical-tree.js')
-var computeMetadata = require('./install/deps.js').computeMetadata
-var readShrinkwrap = require('./install/read-shrinkwrap.js')
-var packageId = require('./utils/package-id.js')
-var usage = require('./utils/usage')
-var output = require('./utils/output.js')
-
-ls.usage = usage(
+'use strict'
+
+const { resolve } = require('path')
+const { EOL } = require('os')
+
+const archy = require('archy')
+const chalk = require('chalk')
+const Arborist = require('@npmcli/arborist')
+const { breadth } = require('treeverse')
+const npa = require('npm-package-arg')
+
+const npm = require('./npm.js')
+const usageUtil = require('./utils/usage.js')
+const completion = require('./utils/completion/installed-deep.js')
+const output = require('./utils/output.js')
+
+const _depth = Symbol('depth')
+const _dedupe = Symbol('dedupe')
+const _include = Symbol('include')
+const _invalid = Symbol('invalid')
+const _name = Symbol('name')
+const _missing = Symbol('missing')
+const _parent = Symbol('parent')
+const _required = Symbol('required')
+const _type = Symbol('type')
+
+const usage = usageUtil(
   'ls',
   'npm ls [[<@scope>/]<pkg> ...]'
 )
 
-ls.completion = require('./utils/completion/installed-deep.js')
+const cmd = (args, cb) => ls(args).then(() => cb()).catch(cb)
 
-function ls (args, silent, cb) {
-  if (typeof cb !== 'function') {
-    cb = silent
-    silent = false
-  }
-  var dir = path.resolve(npm.dir, '..')
-  readPackageTree(dir, function (_, physicalTree) {
-    if (!physicalTree) physicalTree = {package: {}, path: dir}
-    physicalTree.isTop = true
-    readShrinkwrap.andInflate(physicalTree, function () {
-      lsFromTree(dir, computeMetadata(physicalTree), args, silent, cb)
-    })
-  })
-}
+const initTree = async ({ arb, args, json }) => {
+  let tree = await arb.loadActual()
+  tree[_include] = args.length === 0
+  tree[_depth] = 0
 
-function inList (list, value) {
-  return list.indexOf(value) !== -1
+  return tree
 }
 
-var lsFromTree = ls.fromTree = function (dir, physicalTree, args, silent, cb) {
-  if (typeof cb !== 'function') {
-    cb = silent
-    silent = false
-  }
+const isGitNode = (node) => {
+  if (!node.resolved) return
 
-  // npm ls 'foo@~1.3' bar 'baz@<2'
-  if (!args) {
-    args = []
-  } else {
-    args = args.map(function (a) {
-      if (typeof a === 'object' && a.package._requested.type === 'alias') {
-        return [moduleName(a), `npm:${a.package.name}@${a.package.version}`, a]
-      } else if (typeof a === 'object') {
-        return [a.package.name, a.package.version, a]
-      } else {
-        var p = npa(a)
-        var name = p.name
-        // When version spec is missing, we'll skip using it when filtering.
-        // Otherwise, `semver.validRange` would return '*', which won't
-        // match prerelease versions.
-        var ver = (p.rawSpec &&
-                   (semver.validRange(p.rawSpec) || ''))
-        return [ name, ver, a ]
-      }
-    })
+  try {
+    const { type } = npa(node.resolved)
+    return type === 'git' || type === 'hosted'
+  } catch (err) {
+    return false
   }
+}
 
-  var data = mutateIntoLogicalTree.asReadInstalled(physicalTree)
-
-  pruneNestedExtraneous(data)
-  filterByEnv(data)
-  filterByLink(data)
-
-  var unlooped = filterFound(unloop(data), args)
-  var lite = getLite(unlooped)
+const isOptional = (node) =>
+  node[_type] === 'optional' || node[_type] === 'peerOptional'
 
-  if (silent) return cb(null, data, lite)
+const getProblems = (node) => {
+  const problems = new Set()
 
-  var long = npm.config.get('long')
-  var json = npm.config.get('json')
-  var out
-  if (json) {
-    var seen = new Set()
-    var d = long ? unlooped : lite
-    // the raw data can be circular
-    out = JSON.stringify(d, function (k, o) {
-      if (typeof o === 'object') {
-        if (seen.has(o)) return '[Circular]'
-        seen.add(o)
-      }
-      return o
-    }, 2)
-  } else if (npm.config.get('parseable')) {
-    out = makeParseable(unlooped, long, dir)
-  } else if (data) {
-    out = makeArchy(unlooped, long, dir)
+  if (node[_missing] && !isOptional(node)) {
+    problems.add(`missing: ${node.pkgid}, required by ${node[_missing]}`)
   }
-  output(out)
 
-  if (args.length && !data._found) process.exitCode = 1
+  if (node[_invalid]) {
+    problems.add(`invalid: ${node.pkgid} ${node.path}`)
+  }
 
-  var er
-  // if any errors were found, then complain and exit status 1
-  if (lite.problems && lite.problems.length) {
-    er = lite.problems.join('\n')
+  if (node.extraneous) {
+    problems.add(`extraneous: ${node.pkgid} ${node.path}`)
   }
-  cb(er, data, lite)
+
+  return problems
 }
 
-function pruneNestedExtraneous (data, visited) {
-  visited = visited || []
-  visited.push(data)
-  for (var i in data.dependencies) {
-    if (data.dependencies[i].extraneous) {
-      data.dependencies[i].dependencies = {}
-    } else if (visited.indexOf(data.dependencies[i]) === -1) {
-      pruneNestedExtraneous(data.dependencies[i], visited)
+// annotates _parent and _include metadata into the resulting
+// item obj allowing for filtering out results during output
+const augmentItemWithIncludeMetadata = (node, item) => {
+  item[_parent] = node[_parent]
+
+  // append current item to its parent.nodes which is the
+  // structure expected by archy in order to print tree
+  if (node[_include] && node[_parent]) {
+    item[_include] = true
+
+    // includes all ancestors of included node
+    let p = node[_parent]
+    while (p) {
+      p[_include] = true
+      p = p[_parent]
     }
   }
+  return item
 }
 
-function filterByEnv (data) {
-  var dev = npm.config.get('dev') || /^dev(elopment)?$/.test(npm.config.get('only'))
-  var production = npm.config.get('production') || /^prod(uction)?$/.test(npm.config.get('only'))
-  var dependencies = {}
-  var devKeys = Object.keys(data.devDependencies || [])
-  var prodKeys = Object.keys(data._dependencies || [])
-  Object.keys(data.dependencies).forEach(function (name) {
-    if (!dev && inList(devKeys, name) && !inList(prodKeys, name) && data.dependencies[name].missing) {
-      return
-    }
+const getHumanOutputItem = (node, { color, long }) => {
+  const { extraneous, pkgid, path } = node
+  let printable = pkgid
 
-    if ((dev && inList(devKeys, name)) || // only --dev
-        (production && inList(prodKeys, name)) || // only --production
-        (!dev && !production)) { // no --production|--dev|--only=xxx
-      dependencies[name] = data.dependencies[name]
+  // special formatting for top-level package name
+  if (node.isRoot) {
+    const hasNoPackageJson = !Object.keys(node.package).length
+    if (hasNoPackageJson) {
+      printable = path
+    } else {
+      printable += `${long ? EOL : ' '}${path}`
     }
-  })
-  data.dependencies = dependencies
-}
-
-function filterByLink (data) {
-  if (npm.config.get('link')) {
-    var dependencies = {}
-    Object.keys(data.dependencies).forEach(function (name) {
-      var dependency = data.dependencies[name]
-      if (dependency.link) {
-        dependencies[name] = dependency
-      }
-    })
-    data.dependencies = dependencies
   }
-}
 
-function alphasort (a, b) {
-  a = a.toLowerCase()
-  b = b.toLowerCase()
-  return a > b ? 1
-    : a < b ? -1 : 0
-}
+  const missingColor = isOptional(node)
+    ? chalk.yellow.bgBlack
+    : chalk.red.bgBlack
+  const missingMsg = `UNMET ${isOptional(node) ? 'OPTIONAL ' : ''}DEPENDENCY `
+  const label =
+    (
+      node[_missing]
+        ? (color ? missingColor(missingMsg) : missingMsg)
+        : ''
+    ) +
+    `${printable}` +
+    (node[_dedupe] ? ' deduped' : '') +
+    (
+      node[_invalid]
+        ? (color ? chalk.red.bgBlack(' invalid') : ' invalid')
+        : ''
+    ) +
+    (
+      extraneous
+        ? (color ? chalk.green.bgBlack(' extraneous') : ' extraneous')
+        : ''
+    ) +
+    (isGitNode(node) ? ` (${node.resolved})` : '') +
+    (node.isLink ? ` -> ${node.realpath}` : '') +
+    (long ? `${EOL}${node.package.description || ''}` : '')
 
-function isCruft (data) {
-  return data.extraneous && data.error && data.error.code === 'ENOTDIR'
+  return augmentItemWithIncludeMetadata(node, { label, nodes: [] })
 }
 
-function getLite (data, noname, depth) {
-  var lite = {}
-
-  if (isCruft(data)) return lite
+const getJsonOutputItem = (node, { long, nodeProblems }) => {
+  const item = {}
 
-  var maxDepth = npm.config.get('depth')
-
-  if (typeof depth === 'undefined') depth = 0
-  if (!noname && data.name) lite.name = data.name
-  if (data.version) lite.version = data.version
-  if (data.extraneous) {
-    lite.extraneous = true
-    lite.problems = lite.problems || []
-    lite.problems.push('extraneous: ' + packageId(data) + ' ' + (data.path || ''))
+  if (node.version) {
+    item.version = node.version
   }
-
-  if (data.error && data.path !== path.resolve(npm.globalDir, '..') &&
-      (data.error.code !== 'ENOENT' || noname)) {
-    lite.invalid = true
-    lite.problems = lite.problems || []
-    var message = data.error.message
-    lite.problems.push('error in ' + data.path + ': ' + message)
+  if (node.resolved) {
+    item.resolved = node.resolved
   }
 
-  if (data._from) {
-    lite.from = data._from
-  }
+  item[_name] = node.name
 
-  if (data._resolved) {
-    lite.resolved = data._resolved
+  // special formatting for top-level package name
+  const hasPackageJson =
+    node && node.package && Object.keys(node.package).length
+  if (node.isRoot && hasPackageJson) {
+    item.name = node.package.name || node.name
   }
 
-  if (data.invalid) {
-    lite.invalid = true
-    lite.problems = lite.problems || []
-    lite.problems.push('invalid: ' +
-                       packageId(data) +
-                       ' ' + (data.path || ''))
+  if (long) {
+    item.name = item[_name]
+    const { dependencies, ...packageInfo } = node.package
+    Object.assign(item, packageInfo)
+    item.extraneous = false
+    item.path = node.path
+    item._dependencies = node.package.dependencies || {}
+    item.devDependencies = node.package.devDependencies || {}
+    item.peerDependencies = node.package.peerDependencies || {}
   }
 
-  if (data.peerInvalid) {
-    lite.peerInvalid = true
-    lite.problems = lite.problems || []
-    lite.problems.push('peer dep not met: ' +
-                       packageId(data) +
-                       ' ' + (data.path || ''))
+  // augment json output items with extra metadata
+  if (node.extraneous) {
+    item.extraneous = true
   }
-
-  var deps = (data.dependencies && Object.keys(data.dependencies)) || []
-  if (deps.length) {
-    lite.dependencies = deps.map(function (d) {
-      var dep = data.dependencies[d]
-      if (dep.missing && !dep.optional) {
-        lite.problems = lite.problems || []
-        var p
-        if (data.depth > maxDepth) {
-          p = 'max depth reached: '
-        } else {
-          p = 'missing: '
-        }
-        p += d + '@' + dep.requiredBy +
-            ', required by ' +
-            packageId(data)
-        lite.problems.push(p)
-        if (dep.dependencies) {
-          return [d, getLite(dep, true)]
-        } else {
-          return [d, { required: dep.requiredBy, missing: true }]
-        }
-      } else if (dep.peerMissing) {
-        lite.problems = lite.problems || []
-        dep.peerMissing.forEach(function (missing) {
-          var pdm = 'peer dep missing: ' +
-              missing.requires +
-              ', required by ' +
-              missing.requiredBy
-          lite.problems.push(pdm)
-        })
-        return [d, { required: dep, peerMissing: true }]
-      } else if (npm.config.get('json')) {
-        if (depth === maxDepth) delete dep.dependencies
-        return [d, getLite(dep, true, depth + 1)]
-      }
-      return [d, getLite(dep, true)]
-    }).reduce(function (deps, d) {
-      if (d[1].problems) {
-        lite.problems = lite.problems || []
-        lite.problems.push.apply(lite.problems, d[1].problems)
-      }
-      deps[d[0]] = d[1]
-      return deps
-    }, {})
+  if (node[_invalid]) {
+    item.invalid = true
   }
-  return lite
-}
-
-function unloop (root) {
-  var queue = [root]
-  var seen = new Set()
-  seen.add(root)
-
-  while (queue.length) {
-    var current = queue.shift()
-    var deps = current.dependencies = current.dependencies || {}
-    Object.keys(deps).forEach(function (d) {
-      var dep = deps[d]
-      if (dep.missing && !dep.dependencies) return
-      if (dep.path && seen.has(dep)) {
-        dep = deps[d] = Object.assign({}, dep)
-        dep.dependencies = {}
-        dep._deduped = path.relative(root.path, dep.path).replace(/node_modules\//g, '')
-        return
-      }
-      seen.add(dep)
-      queue.push(dep)
-    })
+  if (node[_missing] && !isOptional(node)) {
+    item.required = node[_required]
+    item.missing = true
+  }
+  if (nodeProblems && nodeProblems.size) {
+    item.problems = [...nodeProblems]
   }
 
-  return root
+  return augmentItemWithIncludeMetadata(node, item)
 }
 
-function filterFound (root, args) {
-  if (!args.length) return root
-  if (!root.dependencies) return root
-
-  // Mark all deps
-  var toMark = [root]
-  while (toMark.length) {
-    var markPkg = toMark.shift()
-    var markDeps = markPkg.dependencies
-    if (!markDeps) continue
-    Object.keys(markDeps).forEach(function (depName) {
-      var dep = markDeps[depName]
-      if (dep.peerMissing && !dep._from) return
-      dep._parent = markPkg
-      for (var ii = 0; ii < args.length; ii++) {
-        var argName = args[ii][0]
-        var argVersion = args[ii][1]
-        var argRaw = args[ii][2]
-        var found
-        if (typeof argRaw === 'object') {
-          if (dep.path === argRaw.path) {
-            found = true
-          }
-        } else if (depName === argName && argVersion) {
-          found = semver.satisfies(dep.version, argVersion, true)
-        } else if (depName === argName) {
-          // If version is missing from arg, just do a name match.
-          found = true
-        }
-        if (found) {
-          dep._found = 'explicit'
-          var parent = dep._parent
-          while (parent && !parent._found && !parent._deduped) {
-            parent._found = 'implicit'
-            parent = parent._parent
-          }
-          break
-        }
-      }
-      toMark.push(dep)
-    })
-  }
-  var toTrim = [root]
-  while (toTrim.length) {
-    var trimPkg = toTrim.shift()
-    var trimDeps = trimPkg.dependencies
-    if (!trimDeps) continue
-    trimPkg.dependencies = {}
-    Object.keys(trimDeps).forEach(function (name) {
-      var dep = trimDeps[name]
-      if (!dep._found) return
-      if (dep._found === 'implicit' && dep._deduped) return
-      trimPkg.dependencies[name] = dep
-      toTrim.push(dep)
-    })
-  }
-  return root
+const filterByEdgesTypes = ({
+  dev,
+  development,
+  link,
+  node,
+  prod,
+  production,
+  only,
+  tree
+}) => {
+  // filter deps by type, allows for: `npm ls --dev`, `npm ls --prod`,
+  // `npm ls --link`, `npm ls --only=dev`, etc
+  const filterDev = node === tree &&
+    (dev || development || /^dev(elopment)?$/.test(only))
+  const filterProd = node === tree &&
+    (prod || production || /^prod(uction)?$/.test(only))
+  const filterLink = node === tree && link
+
+  return (edge) =>
+    (filterDev ? edge.dev : true) &&
+    (filterProd ? (!edge.dev && !edge.peer && !edge.peerOptional) : true) &&
+    (filterLink ? (edge.to && edge.to.isLink) : true)
 }
 
-function makeArchy (data, long, dir) {
-  var out = makeArchy_(data, long, dir, 0)
-  return archy(out, '', { unicode: npm.config.get('unicode') })
-}
+const appendExtraneousChildren = ({ node }) =>
+  // extraneous children are not represented
+  // in edges out, so here we add them to the list:
+  [...node.children.values()]
+    .filter(i => i.extraneous)
 
-function makeArchy_ (data, long, dir, depth, parent, d) {
-  if (data.missing) {
-    if (depth - 1 <= npm.config.get('depth')) {
-      // just missing
-      var unmet = 'UNMET ' + (data.optional ? 'OPTIONAL ' : '') + 'DEPENDENCY'
-      if (npm.color) {
-        if (data.optional) {
-          unmet = color.bgBlack(color.yellow(unmet))
-        } else {
-          unmet = color.bgBlack(color.red(unmet))
-        }
-      }
-      var label = data._id || (d + '@' + data.requiredBy)
-      if (data._found === 'explicit' && data._id) {
-        if (npm.color) {
-          label = color.bgBlack(color.yellow(label.trim())) + ' '
-        } else {
-          label = label.trim() + ' '
-        }
-      }
-      return {
-        label: unmet + ' ' + label,
-        nodes: Object.keys(data.dependencies || {})
-          .sort(alphasort).filter(function (d) {
-            return !isCruft(data.dependencies[d])
-          }).map(function (d) {
-            return makeArchy_(sortedObject(data.dependencies[d]), long, dir, depth + 1, data, d)
-          })
-      }
-    } else {
-      return {label: d + '@' + data.requiredBy}
-    }
-  }
+const mapEdgesToNodes = (edge) => {
+  let node = edge.to
 
-  var out = {}
-  if (data._requested && data._requested.type === 'alias') {
-    out.label = `${d}@npm:${data._id}`
-  } else {
-    out.label = data._id || ''
-  }
-  if (data._found === 'explicit' && data._id) {
-    if (npm.color) {
-      out.label = color.bgBlack(color.yellow(out.label.trim())) + ' '
-    } else {
-      out.label = out.label.trim() + ' '
-    }
+  // if the edge is linking to a missing node, we go ahead
+  // and create a new obj that will represent the missing node
+  if (edge.missing || (edge.optional && !edge.to)) {
+    const { name, spec } = edge
+    const pkgid = `${name}@${spec}`
+    node = { name, pkgid, [_missing]: edge.from.pkgid }
   }
-  if (data.link) out.label += ' -> ' + data.link
 
-  if (data._deduped) {
-    if (npm.color) {
-      out.label += ' ' + color.brightBlack('deduped')
-    } else {
-      out.label += ' deduped'
-    }
-  }
+  node[_required] = edge.spec
+  node[_type] = edge.type
+  node[_invalid] = edge.invalid
 
-  if (data.invalid) {
-    if (data.realName !== data.name) out.label += ' (' + data.realName + ')'
-    var invalid = 'invalid'
-    if (npm.color) invalid = color.bgBlack(color.red(invalid))
-    out.label += ' ' + invalid
-  }
+  return node
+}
 
-  if (data.peerInvalid) {
-    var peerInvalid = 'peer invalid'
-    if (npm.color) peerInvalid = color.bgBlack(color.red(peerInvalid))
-    out.label += ' ' + peerInvalid
+const filterByPositionalArgs = (args, node) =>
+  args.length > 0 ? args.some(
+    (spec) => node.satisfies && node.satisfies(spec)
+  ) : true
+
+const augmentNodesWithMetadata = ({
+  args,
+  currentDepth,
+  nodeResult,
+  parseable,
+  seenNodes
+}) => (node) => {
+  // if the original edge was a deduped dep, treeverse will fail to
+  // revisit that node in tree traversal logic, so we make it so that
+  // we have a diff obj for deduped nodes:
+  if (seenNodes.has(node)) {
+    node = {
+      name: node.name,
+      version: node.version,
+      pkgid: node.pkgid,
+      package: node.package,
+      [_dedupe]: true
+    }
   }
 
-  if (data.peerMissing) {
-    var peerMissing = 'UNMET PEER DEPENDENCY'
+  // _parent is going to be a ref to a treeverse-visited node (returned from
+  // getHumanOutputItem, getJsonOutputItem, etc) so that we have an easy
+  // shortcut to place new nodes in their right place during tree traversal
+  node[_parent] = nodeResult
+  // _include is the property that allow us to filter based on position args
+  // e.g: `npm ls foo`, `npm ls simple-output@2`
+  node[_include] =
+    filterByPositionalArgs(args, node, { parseable })
+  // _depth keeps track of how many levels deep tree traversal currently is
+  // so that we can `npm ls --depth=1`
+  node[_depth] = currentDepth + 1
 
-    if (npm.color) peerMissing = color.bgBlack(color.red(peerMissing))
-    out.label = peerMissing + ' ' + out.label
-  }
+  return node
+}
 
-  if (data.extraneous && data.path !== dir) {
-    var extraneous = 'extraneous'
-    if (npm.color) extraneous = color.bgBlack(color.green(extraneous))
-    out.label += ' ' + extraneous
-  }
+const sortAlphabetically = (a, b) =>
+  a.pkgid.localeCompare(b.pkgid)
 
-  if (data.error && depth) {
-    var message = data.error.message
-    if (message.indexOf('\n')) message = message.slice(0, message.indexOf('\n'))
-    var error = 'error: ' + message
-    if (npm.color) error = color.bgRed(color.brightWhite(error))
-    out.label += ' ' + error
+const humanOutput = ({ color, result, seenItems, topLevelChildren, unicode }) => {
+  if (!topLevelChildren) {
+    result.nodes = ['(empty)']
   }
 
-  // add giturl to name@version
-  if (data._resolved) {
-    try {
-      var type = npa(data._resolved).type
-      var isGit = type === 'git' || type === 'hosted'
-      if (isGit) {
-        out.label += ' (' + data._resolved + ')'
-      }
-    } catch (ex) {
-      // npa threw an exception then it ain't git so whatev
+  // we need to traverse the entire tree in order to determine which items
+  // should be included (since a nested transitive included dep will make it
+  // so that all its ancestors should be displayed)
+  // here is where we put items in their expected place for archy output
+  for (const item of seenItems) {
+    if (item[_include] && item[_parent]) {
+      item[_parent].nodes.push(item)
     }
   }
 
-  if (long) {
-    if (dir === data.path) out.label += '\n' + dir
-    out.label += '\n' + getExtras(data)
-  } else if (dir === data.path) {
-    if (out.label) out.label += ' '
-    out.label += dir
-  }
+  const archyOutput = archy(result, '', { unicode })
+  return color ? chalk.reset(archyOutput) : archyOutput
+}
 
-  // now all the children.
-  out.nodes = []
-  if (depth <= npm.config.get('depth')) {
-    out.nodes = Object.keys(data.dependencies || {})
-      .sort(alphasort).filter(function (d) {
-        return !isCruft(data.dependencies[d])
-      }).map(function (d) {
-        return makeArchy_(sortedObject(data.dependencies[d]), long, dir, depth + 1, data, d)
-      })
-  }
+const jsonOutput = ({ path, problems, result, rootError, seenItems }) => {
+  if (problems.size) {
+    result.problems = [...problems]
+  }
+
+  if (rootError) {
+    result.problems = [
+      ...(result.problems || []),
+      ...[`error in ${path}: Failed to parse root package.json`]
+    ]
+    result.invalid = true
+  }
+
+  // we need to traverse the entire tree in order to determine which items
+  // should be included (since a nested transitive included dep will make it
+  // so that all its ancestors should be displayed)
+  // here is where we put items in their expected place for json output
+  for (const item of seenItems) {
+    // append current item to its parent item.dependencies obj in order
+    // to provide a json object structure that represents the installed tree
+    if (item[_include] && item[_parent]) {
+      if (!item[_parent].dependencies) {
+        item[_parent].dependencies = {}
+      }
 
-  if (out.nodes.length === 0 && data.path === dir) {
-    out.nodes = ['(empty)']
+      item[_parent].dependencies[item[_name]] = item
+    }
   }
 
-  return out
+  return JSON.stringify(result, null, 2)
 }
 
-function getExtras (data) {
-  var extras = []
-
-  if (data.description) extras.push(data.description)
-  if (data.repository) extras.push(data.repository.url)
-  if (data.homepage) extras.push(data.homepage)
-  if (data._from) {
-    var from = data._from
-    if (from.indexOf(data.name + '@') === 0) {
-      from = from.substr(data.name.length + 1)
+const parseableOutput = ({ long, seenNodes }) => {
+  let out = ''
+  for (const node of seenNodes) {
+    if (node.path && node[_include]) {
+      out += node.path
+      if (long) {
+        out += `:${node.pkgid}`
+        out += node.path !== node.realpath ? `:${node.realpath}` : ''
+        out += node.extraneous ? ':EXTRANEOUS' : ''
+        out += node[_invalid] ? ':INVALID' : ''
+      }
+      out += EOL
     }
-    var u = url.parse(from)
-    if (u.protocol) extras.push(from)
   }
-  return extras.join('\n')
+  return out.trim()
 }
 
-function makeParseable (data, long, dir, depth, parent, d) {
-  if (data._deduped) return []
-  depth = depth || 0
-  if (depth > npm.config.get('depth')) return [ makeParseable_(data, long, dir, depth, parent, d) ]
-  return [ makeParseable_(data, long, dir, depth, parent, d) ]
-    .concat(Object.keys(data.dependencies || {})
-      .sort(alphasort).map(function (d) {
-        return makeParseable(data.dependencies[d], long, dir, depth + 1, data, d)
-      }))
-    .filter(function (x) { return x && x.length })
-    .join('\n')
-}
+const ls = async (args) => {
+  const path = npm.prefix
+  const {
+    color,
+    depth,
+    json,
+    long,
+    parseable,
+    unicode
+  } = npm.flatOptions
+  const dev = npm.config.get('dev')
+  const development = npm.config.get('development')
+  const link = npm.config.get('link')
+  const only = npm.config.get('only')
+  const prod = npm.config.get('prod')
+  const production = npm.config.get('production')
+
+  const arb = new Arborist({
+    ...npm.flatOptions,
+    legacyPeerDeps: false,
+    path
+  })
+  let tree = await initTree({
+    arb,
+    args,
+    json
+  })
 
-function makeParseable_ (data, long, dir, depth, parent, d) {
-  if (data.hasOwnProperty('_found') && data._found !== 'explicit') return ''
+  const seenItems = new Set()
+  const seenNodes = new Set()
+  const problems = new Set()
+  let topLevelChildren = 0
+
+  // tree traversal happens here, using treeverse.breadth
+  const result = breadth({
+    tree,
+    // recursive method, `node` is going to be the current elem (starting from
+    // the `tree` obj) that was just visited in the `visit` method below
+    // `nodeResult` is going to be the returned `item` from `visit`
+    getChildren (node, nodeResult) {
+      return (!(node instanceof Arborist.Node) || node[_depth] > depth)
+        ? []
+        : [...node.edgesOut.values()]
+          .filter(filterByEdgesTypes({
+            dev,
+            development,
+            link,
+            node,
+            prod,
+            production,
+            only,
+            tree
+          }))
+          .map(mapEdgesToNodes)
+          .concat(appendExtraneousChildren({ node }))
+          .map(augmentNodesWithMetadata({
+            args,
+            currentDepth: node[_depth],
+            nodeResult,
+            parseable,
+            seenNodes
+          }))
+          .sort(sortAlphabetically)
+    },
+    // visit each `node` of the `tree`, returning an `item` - these are
+    // the elements that will be used to build the final output
+    visit (node) {
+      seenNodes.add(node)
+
+      const nodeProblems = getProblems(node)
+      for (const problem of nodeProblems) {
+        problems.add(problem)
+      }
 
-  if (data.missing) {
-    if (depth < npm.config.get('depth')) {
-      data = npm.config.get('long')
-        ? path.resolve(parent.path, 'node_modules', d) +
-             ':' + d + '@' + JSON.stringify(data.requiredBy) + ':INVALID:MISSING'
-        : ''
-    } else {
-      data = path.resolve(dir || '', 'node_modules', d || '') +
-             (npm.config.get('long')
-               ? ':' + d + '@' + JSON.stringify(data.requiredBy) +
-               ':' + // no realpath resolved
-               ':MAXDEPTH'
-               : '')
+      // keeps track of the number of top-level children found since
+      // we have a bunch of edge cases related to empty top-level
+      if (node[_include] && node[_parent] && !node[_parent][_parent]) {
+        topLevelChildren++
+      }
+
+      const item = json
+        ? getJsonOutputItem(node, { long, nodeProblems })
+        : parseable
+          ? null
+          : getHumanOutputItem(node, { color, long })
+
+      seenItems.add(item)
+      return item
     }
+  })
 
-    return data
+  // if filtering items, should exit with error code on no results
+  if (!topLevelChildren && args.length) {
+    process.exitCode = 1
   }
 
-  if (!npm.config.get('long')) return data.path
+  // handle the special case of a broken package.json in the root folder
+  const [rootError] = tree.errors.filter(e =>
+    e.code === 'EJSONPARSE' && e.path === resolve(path, 'package.json'))
 
-  return data.path +
-         ':' + (data._id || '') +
-         ':' + (data.realPath !== data.path ? data.realPath : '') +
-         (data.extraneous ? ':EXTRANEOUS' : '') +
-         (data.error && data.path !== path.resolve(npm.globalDir, '..') ? ':ERROR' : '') +
-         (data.invalid ? ':INVALID' : '') +
-         (data.peerInvalid ? ':PEERINVALID' : '') +
-         (data.peerMissing ? ':PEERINVALID:MISSING' : '')
+  output(
+    json
+      ? jsonOutput({ path, problems, result, rootError, seenItems })
+      : parseable
+        ? parseableOutput({ seenNodes, long })
+        : humanOutput({ color, result, seenItems, topLevelChildren, unicode })
+  )
+
+  if (rootError) {
+    throw Object.assign(
+      new Error('Failed to parse root package.json'),
+      { code: 'EJSONPARSE' }
+    )
+  }
+
+  if (problems.size) {
+    throw Object.assign(
+      new Error([...problems].join(EOL)),
+      { code: 'ELSPROBLEMS' }
+    )
+  }
 }
+
+module.exports = Object.assign(cmd, { usage, completion })