ls: stop flattening output, show the actual tree

PR-URL: https://github.com/npm/npm/pull/15888
Credit: @iarna
Reviewed-By: @zkat

4 files changed, 154 insertions, 106 deletions

diff --git a/lib/ls.js b/lib/ls.js
index ba5ab16e5..3c0e4384d 100644
--- a/lib/ls.js
+++ b/lib/ls.js
@@ -15,6 +15,8 @@ var semver = require('semver')
 var color = require('ansicolors')
 var npa = require('npm-package-arg')
 var iferr = require('iferr')
+var sortedObject = require('sorted-object')
+var extend = Object.assign || require('util')._extend
 var npm = require('./npm.js')
 var mutateIntoLogicalTree = require('./install/mutate-into-logical-tree.js')
 var recalculateMetadata = require('./install/deps.js').recalculateMetadata
@@ -76,8 +78,8 @@ var lsFromTree = ls.fromTree = function (dir, physicalTree, args, silent, cb) {
 
   pruneNestedExtraneous(data)
   filterByEnv(data)
-  var bfs = filterFound(bfsify(data), args)
-  var lite = getLite(bfs)
+  var unlooped = filterFound(unloop(data), args)
+  var lite = getLite(unlooped)
 
   if (silent) return cb(null, data, lite)
 
@@ -86,7 +88,7 @@ var lsFromTree = ls.fromTree = function (dir, physicalTree, args, silent, cb) {
   var out
   if (json) {
     var seen = []
-    var d = long ? bfs : lite
+    var d = long ? unlooped : lite
     // the raw data can be circular
     out = JSON.stringify(d, function (k, o) {
       if (typeof o === 'object') {
@@ -96,9 +98,9 @@ var lsFromTree = ls.fromTree = function (dir, physicalTree, args, silent, cb) {
       return o
     }, 2)
   } else if (npm.config.get('parseable')) {
-    out = makeParseable(bfs, long, dir)
+    out = makeParseable(unlooped, long, dir)
   } else if (data) {
-    out = makeArchy(bfs, long, dir)
+    out = makeArchy(unlooped, long, dir)
   }
   output(out)
 
@@ -247,18 +249,10 @@ function getLite (data, noname, depth) {
   return lite
 }
 
-function bfsify (root) {
-  // walk over the data, and turn it from this:
-  // +-- a
-  // |   `-- b
-  // |       `-- a (truncated)
-  // `--b (truncated)
-  // into this:
-  // +-- a
-  // `-- b
-  // which looks nicer
+function unloop (root) {
   var queue = [root]
-  var seen = [root]
+  var seen = {}
+  seen[root.path] = true
 
   while (queue.length) {
     var current = queue.shift()
@@ -266,17 +260,14 @@ function bfsify (root) {
     Object.keys(deps).forEach(function (d) {
       var dep = deps[d]
       if (dep.missing) return
-      if (inList(seen, dep)) {
-        if (npm.config.get('parseable') || !npm.config.get('long')) {
-          delete deps[d]
-          return
-        } else {
-          dep = deps[d] = Object.create(dep)
-          dep.dependencies = {}
-        }
+      if (dep.path && seen[dep.path]) {
+        dep = deps[d] = extend({}, dep)
+        dep.dependencies = {}
+        dep._deduped = path.relative(root.path, dep.path).replace(/node_modules\//g, '')
+        return
       }
+      seen[dep.path] = true
       queue.push(dep)
-      seen.push(dep)
     })
   }
 
@@ -285,18 +276,23 @@ function bfsify (root) {
 
 function filterFound (root, args) {
   if (!args.length) return root
-  var deps = root.dependencies
-  if (deps) {
-    Object.keys(deps).forEach(function (depName) {
-      var dep = filterFound(deps[depName], args)
+  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) return
-
-      // see if this one itself matches
-      var found = false
-      for (var ii = 0; !found && ii < args.length; ii++) {
+      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 (depName === argName && argVersion) {
           found = semver.satisfies(dep.version, argVersion, true)
         } else if (depName === argName) {
@@ -305,16 +301,33 @@ function filterFound (root, args) {
         } else if (dep.path === argRaw) {
           found = true
         }
+        if (found) {
+          dep._found = 'explicit'
+          var parent = dep._parent
+          while (parent && !parent._found && !parent._deduped) {
+            parent._found = 'implicit'
+            parent = parent._parent
+          }
+          break
+        }
       }
-      // included explicitly
-      if (found) dep._found = true
-      // included because a child was included
-      if (dep._found && !root._found) root._found = 1
-      // not included
-      if (!dep._found) delete deps[depName]
+      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)
     })
   }
-  if (!root._found) root._found = false
   return root
 }
 
@@ -345,7 +358,7 @@ function makeArchy_ (data, long, dir, depth, parent, d) {
   var out = {}
   // the top level is a bit special.
   out.label = data._id || ''
-  if (data._found === true && data._id) {
+  if (data._found === 'explicit' && data._id) {
     if (npm.color) {
       out.label = color.bgBlack(color.yellow(out.label.trim())) + ' '
     } else {
@@ -354,6 +367,14 @@ function makeArchy_ (data, long, dir, depth, parent, d) {
   }
   if (data.link) out.label += ' -> ' + data.link
 
+  if (data._deduped) {
+    if (npm.color) {
+      out.label += ' ' + color.brightBlack('deduped')
+    } else {
+      out.label += ' deduped'
+    }
+  }
+
   if (data.invalid) {
     if (data.realName !== data.name) out.label += ' (' + data.realName + ')'
     var invalid = 'invalid'
@@ -369,6 +390,7 @@ function makeArchy_ (data, long, dir, depth, parent, d) {
 
   if (data.peerMissing) {
     var peerMissing = 'UNMET PEER DEPENDENCY'
+
     if (npm.color) peerMissing = color.bgBlack(color.red(peerMissing))
     out.label = peerMissing + ' ' + out.label
   }
@@ -415,7 +437,7 @@ function makeArchy_ (data, long, dir, depth, parent, d) {
       .sort(alphasort).filter(function (d) {
         return !isCruft(data.dependencies[d])
       }).map(function (d) {
-        return makeArchy_(data.dependencies[d], long, dir, depth + 1, data, d)
+        return makeArchy_(sortedObject(data.dependencies[d]), long, dir, depth + 1, data, d)
       })
   }
 
@@ -444,19 +466,20 @@ function getExtras (data) {
 }
 
 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 })
-  .join('\n')
+    .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 })
+    .join('\n')
 }
 
 function makeParseable_ (data, long, dir, depth, parent, d) {
-  if (data.hasOwnProperty('_found') && data._found !== true) return ''
+  if (data.hasOwnProperty('_found') && data._found !== 'explicit') return ''
 
   if (data.missing) {
     if (depth < npm.config.get('depth')) {
diff --git a/test/tap/extraneous-dep-cycle-ls-ok.js b/test/tap/extraneous-dep-cycle-ls-ok.js
index 767cb6d7f..d483b3e22 100644
--- a/test/tap/extraneous-dep-cycle-ls-ok.js
+++ b/test/tap/extraneous-dep-cycle-ls-ok.js
@@ -54,7 +54,8 @@ test('setup', function (t) {
 
 var expected = pkg + '\n' +
                '└─┬ moduleA@1.0.0\n' +
-               '  └── moduleB@1.0.0\n\n'
+               '  └─┬ moduleB@1.0.0\n' +
+               '    └── moduleA@1.0.0 deduped\n\n'
 
 test('extraneous-dep-cycle', function (t) {
   common.npm(['ls', '--unicode=true'], {cwd: pkg}, function (er, code, stdout, stderr) {
diff --git a/test/tap/git-races.js b/test/tap/git-races.js
index f275455cd..c6c27d504 100644
--- a/test/tap/git-races.js
+++ b/test/tap/git-races.js
@@ -162,7 +162,8 @@ function setup (cb) {
 var oneTree = [
   'npm-git-test@1.0.0', [
     ['dummy-npm-bar@4.0.0', [
-      ['dummy-npm-foo@3.0.0', []]
+      ['dummy-npm-foo@3.0.0', []],
+      ['dummy-npm-buzz@3.0.0', []]
     ]],
     ['dummy-npm-buzz@3.0.0', []],
     ['dummy-npm-foo@4.0.0', [
@@ -199,17 +200,19 @@ test('setup', function (t) {
 })
 
 test('correct versions are installed for git dependency', function (t) {
-  t.plan(3)
   t.comment('test for https://github.com/npm/npm/issues/7202')
   npm.commands.install([], function (er) {
     t.ifError(er, 'installed OK')
     npm.commands.ls([], true, function (er, result) {
       t.ifError(er, 'ls OK')
       var simplified = toSimple(result)
-      t.ok(
-        deepEqual(simplified, oneTree) || deepEqual(simplified, otherTree),
-        'install tree is correct'
-      )
+      if (deepEqual(simplified, oneTree) || deepEqual(simplified, otherTree)) {
+        t.pass('install tree is correct')
+      } else {
+        t.isDeeply(simplified, oneTree, 'oneTree matches')
+        t.isDeeply(simplified, otherTree, 'otherTree matches')
+      }
+      t.done()
     })
   })
 })
diff --git a/test/tap/peer-deps-toplevel.js b/test/tap/peer-deps-toplevel.js
index 1c9586730..a4384a7a5 100644
--- a/test/tap/peer-deps-toplevel.js
+++ b/test/tap/peer-deps-toplevel.js
@@ -1,16 +1,29 @@
-var fs = require('graceful-fs')
+'use strict'
 var path = require('path')
-
-var mkdirp = require('mkdirp')
-var mr = require('npm-registry-mock')
-var osenv = require('osenv')
-var rimraf = require('rimraf')
 var test = require('tap').test
-
+var mr = require('npm-registry-mock')
+var Tacks = require('tacks')
+var File = Tacks.File
+var Dir = Tacks.Dir
+var extend = Object.assign || require('util')._extend
 var common = require('../common-tap.js')
-var npm = npm = require('../../')
 
-var pkg = path.resolve(__dirname, 'peer-deps-toplevel')
+var basedir = path.join(__dirname, path.basename(__filename, '.js'))
+var testdir = path.join(basedir, 'testdir')
+var cachedir = path.join(basedir, 'cache')
+var globaldir = path.join(basedir, 'global')
+var tmpdir = path.join(basedir, 'tmp')
+
+var conf = {
+  cwd: testdir,
+  env: extend(extend({}, process.env), {
+    npm_config_cache: cachedir,
+    npm_config_tmp: tmpdir,
+    npm_config_prefix: globaldir,
+    npm_config_registry: common.registry,
+    npm_config_loglevel: 'warn'
+  })
+}
 
 var expected = {
   name: 'npm-test-peer-deps-toplevel',
@@ -59,57 +72,65 @@ var expected = {
   }
 }
 
-var json = {
-  author: 'Domenic Denicola',
-  name: 'npm-test-peer-deps-toplevel',
-  version: '0.0.0',
-  dependencies: {
-    'npm-test-peer-deps': '*'
-  },
-  peerDependencies: {
-    mkdirp: '*'
-  }
+var server
+var fixture = new Tacks(Dir({
+  cache: Dir(),
+  global: Dir(),
+  tmp: Dir(),
+  testdir: Dir({
+    'package.json': File({
+      name: 'npm-test-peer-deps-toplevel',
+      version: '0.0.0',
+      dependencies: {
+        'npm-test-peer-deps': '*'
+      },
+      peerDependencies: {
+        mkdirp: '*'
+      }
+    })
+  })
+}))
+
+function setup () {
+  cleanup()
+  fixture.create(basedir)
 }
 
-test('installs the peer dependency directory structure', function (t) {
-  mr({ port: common.port }, function (er, s) {
-    setup(function (err) {
-      t.ifError(err, 'setup ran successfully')
+function cleanup () {
+  fixture.remove(basedir)
+}
 
-      npm.install('.', function (err) {
-        t.ifError(err, 'packages were installed')
+test('setup', function (t) {
+  setup()
+  mr({port: common.port, throwOnUnmatched: true}, function (err, s) {
+    if (err) throw err
+    server = s
+    t.done()
+  })
+})
 
-        npm.commands.ls([], true, function (err, _, results) {
-          t.ifError(err, 'listed tree without problems')
+test('installs the peer dependency directory structure', function (t) {
+  common.npm(['install'], conf, function (err, code, stdout, stderr) {
+    if (err) throw err
+    t.is(code, 0, 'install ran ok even w/ missing peeer deps')
+    t.comment(stdout.trim())
+    t.comment(stderr.trim())
 
-          t.deepEqual(results, expected, 'got expected output from ls')
-          s.close()
-          t.end()
-        })
-      })
+    common.npm(['ls', '--json'], conf, function (err, code, stdout, stderr) {
+      if (err) throw err
+      t.is(code, 1, 'missing peer deps _are_ an ls error though')
+      t.comment(stderr.trim())
+      var results = JSON.parse(stdout)
+
+      t.deepEqual(results, expected, 'got expected output from ls')
+      t.done()
     })
   })
 })
 
 test('cleanup', function (t) {
+  server.close()
   cleanup()
-  t.end()
+  t.done()
 })
 
-function setup (cb) {
-  cleanup()
-  mkdirp.sync(pkg)
-  fs.writeFileSync(
-    path.join(pkg, 'package.json'),
-    JSON.stringify(json, null, 2)
-  )
-  process.chdir(pkg)
-
-  var opts = { cache: path.resolve(pkg, 'cache'), registry: common.registry }
-  npm.load(opts, cb)
-}
-
-function cleanup () {
-  process.chdir(osenv.tmpdir())
-  rimraf.sync(pkg)
-}