fix: deduped+filter issues

- When using args to filter out items deduped pkgs were broken
- Fixed highlight color when using filter args
- Changed default behavior to show all packages when using args filter

Paired-with: @isaacs

3 files changed, 279 insertions, 42 deletions

diff --git a/lib/ls.js b/lib/ls.js
index 6f936a7b3..f73856c0a 100644
--- a/lib/ls.js
+++ b/lib/ls.js
@@ -16,6 +16,7 @@ const output = require('./utils/output.js')
 
 const _depth = Symbol('depth')
 const _dedupe = Symbol('dedupe')
+const _filteredBy = Symbol('filteredBy')
 const _include = Symbol('include')
 const _invalid = Symbol('invalid')
 const _name = Symbol('name')
@@ -78,12 +79,11 @@ const getProblems = (node, { global }) => {
 // item obj allowing for filtering out results during output
 const augmentItemWithIncludeMetadata = (node, item) => {
   item[_parent] = node[_parent]
+  item[_include] = node[_include]
 
   // 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
-
+  if (node[_include]) {
     // includes all ancestors of included node
     let p = node[_parent]
     while (p) {
@@ -94,7 +94,7 @@ const augmentItemWithIncludeMetadata = (node, item) => {
   return item
 }
 
-const getHumanOutputItem = (node, { color, global, long }) => {
+const getHumanOutputItem = (node, { args, color, global, long }) => {
   const { pkgid, path } = node
   let printable = pkgid
 
@@ -108,6 +108,8 @@ const getHumanOutputItem = (node, { color, global, long }) => {
     }
   }
 
+  const highlightDepName =
+    color && args.length && node[_filteredBy]
   const missingColor = isOptional(node)
     ? chalk.yellow.bgBlack
     : chalk.red.bgBlack
@@ -118,7 +120,7 @@ const getHumanOutputItem = (node, { color, global, long }) => {
         ? (color ? missingColor(missingMsg) : missingMsg)
         : ''
     ) +
-    `${printable}` +
+    `${highlightDepName ? chalk.yellow.bgBlack(printable) : printable}` +
     (node[_dedupe] ? ' deduped' : '') +
     (
       node[_invalid]
@@ -220,7 +222,7 @@ const mapEdgesToNodes = (edge) => {
 
   // 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)) {
+  if (edge.missing || (edge.optional && !node)) {
     const { name, spec } = edge
     const pkgid = `${name}@${spec}`
     node = { name, pkgid, [_missing]: edge.from.pkgid }
@@ -233,9 +235,9 @@ const mapEdgesToNodes = (edge) => {
   return node
 }
 
-const filterByPositionalArgs = (args, node) =>
+const filterByPositionalArgs = (args, { node }) =>
   args.length > 0 ? args.some(
-    (spec) => node.satisfies && node.satisfies(spec)
+    (spec) => (node.satisfies(spec))
   ) : true
 
 const augmentNodesWithMetadata = ({
@@ -248,14 +250,18 @@ const augmentNodesWithMetadata = ({
   // 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)) {
+  if (seenNodes.has(node.path)) {
     node = {
       name: node.name,
       version: node.version,
       pkgid: node.pkgid,
       package: node.package,
+      path: node.path,
       [_dedupe]: true
     }
+  } else {
+    // keeps track of already seen nodes in order to check for dedupes
+    seenNodes.set(node.path, node)
   }
 
   // _parent is going to be a ref to a treeverse-visited node (returned from
@@ -264,8 +270,10 @@ const augmentNodesWithMetadata = ({
   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 })
+  // _filteredBy is used to apply extra color info to the item that
+  // was used in args in order to filter
+  node[_filteredBy] = node[_include] =
+    filterByPositionalArgs(args, { node: seenNodes.get(node.path), seenNodes })
   // _depth keeps track of how many levels deep tree traversal currently is
   // so that we can `npm ls --depth=1`
   node[_depth] = currentDepth + 1
@@ -276,11 +284,7 @@ const augmentNodesWithMetadata = ({
 const sortAlphabetically = (a, b) =>
   a.pkgid.localeCompare(b.pkgid)
 
-const humanOutput = ({ color, result, seenItems, topLevelChildren, unicode }) => {
-  if (!topLevelChildren) {
-    result.nodes = ['(empty)']
-  }
-
+const humanOutput = ({ color, result, seenItems, unicode }) => {
   // 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)
@@ -291,6 +295,10 @@ const humanOutput = ({ color, result, seenItems, topLevelChildren, unicode }) =>
     }
   }
 
+  if (!result.nodes.length) {
+    result.nodes = ['(empty)']
+  }
+
   const archyOutput = archy(result, '', { unicode })
   return color ? chalk.reset(archyOutput) : archyOutput
 }
@@ -329,7 +337,7 @@ const jsonOutput = ({ path, problems, result, rootError, seenItems }) => {
 
 const parseableOutput = ({ global, long, seenNodes }) => {
   let out = ''
-  for (const node of seenNodes) {
+  for (const node of seenNodes.values()) {
     if (node.path && node[_include]) {
       out += node.path
       if (long) {
@@ -378,10 +386,12 @@ const ls = async (args) => {
   })
 
   const seenItems = new Set()
-  const seenNodes = new Set()
+  const seenNodes = new Map()
   const problems = new Set()
-  let topLevelChildren = 0
-  const depthToPrint = all ? Infinity : (depth || 0)
+  const depthToPrint = (all || args.length) ? Infinity : (depth || 0)
+
+  // add root node of tree to list of seenNodes
+  seenNodes.set(tree.path, tree)
 
   // tree traversal happens here, using treeverse.breadth
   const result = await breadth({
@@ -390,7 +400,9 @@ const ls = async (args) => {
     // 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] > depthToPrint))
+      const shouldSkipChildren =
+        !(node instanceof Arborist.Node) || (node[_depth] > depthToPrint)
+      return (shouldSkipChildren)
         ? []
         : [...node.edgesOut.values()]
           .filter(filterByEdgesTypes({
@@ -405,6 +417,7 @@ const ls = async (args) => {
           }))
           .map(mapEdgesToNodes)
           .concat(appendExtraneousChildren({ node }))
+          .sort(sortAlphabetically)
           .map(augmentNodesWithMetadata({
             args,
             currentDepth: node[_depth],
@@ -412,40 +425,28 @@ const ls = async (args) => {
             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, { global })
       for (const problem of nodeProblems) {
         problems.add(problem)
       }
 
-      // 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, { global, long, nodeProblems })
         : parseable
           ? null
-          : getHumanOutputItem(node, { color, global, long })
+          : getHumanOutputItem(node, { args, color, global, long })
 
       seenItems.add(item)
+
+      // return a promise so we don't blow the stack
       return Promise.resolve(item)
     }
   })
 
-  // if filtering items, should exit with error code on no results
-  if (!topLevelChildren && args.length) {
-    process.exitCode = 1
-  }
-
   // 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'))
@@ -455,9 +456,14 @@ const ls = async (args) => {
       ? jsonOutput({ path, problems, result, rootError, seenItems })
       : parseable
         ? parseableOutput({ seenNodes, global, long })
-        : humanOutput({ color, result, seenItems, topLevelChildren, unicode })
+        : humanOutput({ color, result, seenItems, unicode })
   )
 
+  // if filtering items, should exit with error code on no results
+  if (!tree[_include] && args.length) {
+    process.exitCode = 1
+  }
+
   if (rootError) {
     throw Object.assign(
       new Error('Failed to parse root package.json'),
diff --git a/tap-snapshots/test-lib-ls.js-TAP.test.js b/tap-snapshots/test-lib-ls.js-TAP.test.js
index 6095d8adc..5c7dc2f0f 100644
--- a/tap-snapshots/test-lib-ls.js-TAP.test.js
+++ b/tap-snapshots/test-lib-ls.js-TAP.test.js
@@ -454,15 +454,34 @@ test-npm-ls@1.0.0 {CWD}/ls-ls-using-aliases
 
 `
 
-exports[`test/lib/ls.js TAP ls with filter arg > should output tree contaning only occurences of filtered by package 1`] = `
-test-npm-ls@1.0.0 {CWD}/ls-ls-with-filter-arg
-\`-- lorem@1.0.0
+exports[`test/lib/ls.js TAP ls with args and dedupe entries > should print tree output containing deduped ref 1`] = `
+dedupe-entries@1.0.0 {CWD}/ls-ls-with-args-and-dedupe-entries
++-- @npmcli/a@1.0.0
+| \`-- @npmcli/b@1.1.2 deduped
++-- @npmcli/b@1.1.2
+\`-- @npmcli/c@1.0.0
+  \`-- @npmcli/b@1.1.2 deduped
+
+`
+
+exports[`test/lib/ls.js TAP ls with args and different order of items > should print tree output containing deduped ref 1`] = `
+dedupe-entries@1.0.0 {CWD}/ls-ls-with-args-and-different-order-of-items
++-- @npmcli/a@1.0.0
+| \`-- @npmcli/c@1.0.0 deduped
++-- @npmcli/b@1.1.2
+| \`-- @npmcli/c@1.0.0 deduped
+\`-- @npmcli/c@1.0.0
 
 `
 
+exports[`test/lib/ls.js TAP ls with filter arg > should output tree contaning only occurences of filtered by package and coloured output 1`] = `
+test-npm-ls@1.0.0 {CWD}/ls-ls-with-filter-arg
+\`-- lorem@1.0.0
+
+`
+
 exports[`test/lib/ls.js TAP ls with filter arg nested dep > should output tree contaning only occurences of filtered package and its ancestors 1`] = `
 test-npm-ls@1.0.0 {CWD}/ls-ls-with-filter-arg-nested-dep
-+-- (empty)
 \`-- foo@1.0.0
   \`-- bar@1.0.0
 
@@ -481,3 +500,21 @@ test-npm-ls@1.0.0 {CWD}/ls-ls-with-multiple-filter-args
 \`-- lorem@1.0.0
 
 `
+
+exports[`test/lib/ls.js TAP ls with no args dedupe entries > should print tree output containing deduped ref 1`] = `
+dedupe-entries@1.0.0 {CWD}/ls-ls-with-no-args-dedupe-entries
++-- @npmcli/a@1.0.0
+| \`-- @npmcli/b@1.1.2 deduped
++-- @npmcli/b@1.1.2
+\`-- @npmcli/c@1.0.0
+  \`-- @npmcli/b@1.1.2 deduped
+
+`
+
+exports[`test/lib/ls.js TAP ls with no args dedupe entries and not displaying all > should print tree output containing deduped ref 1`] = `
+dedupe-entries@1.0.0 {CWD}/ls-ls-with-no-args-dedupe-entries-and-not-displaying-all
++-- @npmcli/a@1.0.0
++-- @npmcli/b@1.1.2
+\`-- @npmcli/c@1.0.0
+
+`
diff --git a/test/lib/ls.js b/test/lib/ls.js
index 311582d42..5b8295727 100644
--- a/test/lib/ls.js
+++ b/test/lib/ls.js
@@ -186,6 +186,7 @@ test('ls', (t) => {
   })
 
   t.test('with filter arg', (t) => {
+    _flatOptions.color = true
     prefix = t.testdir({
       'package.json': JSON.stringify({
         name: 'test-npm-ls',
@@ -199,7 +200,8 @@ test('ls', (t) => {
     })
     ls(['lorem'], (err) => {
       t.ifError(err, 'npm ls')
-      t.matchSnapshot(redactCwd(result), 'should output tree contaning only occurences of filtered by package')
+      t.matchSnapshot(redactCwd(result), 'should output tree contaning only occurences of filtered by package and coloured output')
+      _flatOptions.color = false
       t.end()
     })
   })
@@ -781,6 +783,198 @@ test('ls', (t) => {
     })
   })
 
+  t.test('with no args dedupe entries', (t) => {
+    prefix = t.testdir({
+      'package.json': JSON.stringify({
+        name: 'dedupe-entries',
+        version: '1.0.0',
+        dependencies: {
+          '@npmcli/a': '^1.0.0',
+          '@npmcli/b': '^1.0.0',
+          '@npmcli/c': '^1.0.0'
+        }
+      }),
+      node_modules: {
+        '@npmcli': {
+          'a': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/a',
+              version: '1.0.0',
+              dependencies: {
+                '@npmcli/b': '^1.0.0'
+              }
+            })
+          },
+          'b': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/b',
+              version: '1.1.2'
+            })
+          },
+          'c': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/c',
+              version: '1.0.0',
+              dependencies: {
+                '@npmcli/b': '^1.0.0'
+              }
+            })
+          }
+        }
+      }
+    })
+    ls([], (err) => {
+      t.ifError(err, 'npm ls')
+      t.matchSnapshot(redactCwd(result), 'should print tree output containing deduped ref')
+      t.end()
+    })
+  })
+
+  t.test('with no args dedupe entries and not displaying all', (t) => {
+    _flatOptions.all = false
+    _flatOptions.depth = 0
+    prefix = t.testdir({
+      'package.json': JSON.stringify({
+        name: 'dedupe-entries',
+        version: '1.0.0',
+        dependencies: {
+          '@npmcli/a': '^1.0.0',
+          '@npmcli/b': '^1.0.0',
+          '@npmcli/c': '^1.0.0'
+        }
+      }),
+      node_modules: {
+        '@npmcli': {
+          'a': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/a',
+              version: '1.0.0',
+              dependencies: {
+                '@npmcli/b': '^1.0.0'
+              }
+            })
+          },
+          'b': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/b',
+              version: '1.1.2'
+            })
+          },
+          'c': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/c',
+              version: '1.0.0',
+              dependencies: {
+                '@npmcli/b': '^1.0.0'
+              }
+            })
+          }
+        }
+      }
+    })
+    ls([], (err) => {
+      t.ifError(err, 'npm ls')
+      t.matchSnapshot(redactCwd(result), 'should print tree output containing deduped ref')
+      _flatOptions.all = true
+      _flatOptions.depth = Infinity
+      t.end()
+    })
+  })
+
+  t.test('with args and dedupe entries', (t) => {
+    prefix = t.testdir({
+      'package.json': JSON.stringify({
+        name: 'dedupe-entries',
+        version: '1.0.0',
+        dependencies: {
+          '@npmcli/a': '^1.0.0',
+          '@npmcli/b': '^1.0.0',
+          '@npmcli/c': '^1.0.0'
+        }
+      }),
+      node_modules: {
+        '@npmcli': {
+          'a': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/a',
+              version: '1.0.0',
+              dependencies: {
+                '@npmcli/b': '^1.0.0'
+              }
+            })
+          },
+          'b': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/b',
+              version: '1.1.2'
+            })
+          },
+          'c': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/c',
+              version: '1.0.0',
+              dependencies: {
+                '@npmcli/b': '^1.0.0'
+              }
+            })
+          }
+        }
+      }
+    })
+    ls(['@npmcli/b'], (err) => {
+      t.ifError(err, 'npm ls')
+      t.matchSnapshot(redactCwd(result), 'should print tree output containing deduped ref')
+      t.end()
+    })
+  })
+
+  t.test('with args and different order of items', (t) => {
+    prefix = t.testdir({
+      'package.json': JSON.stringify({
+        name: 'dedupe-entries',
+        version: '1.0.0',
+        dependencies: {
+          '@npmcli/a': '^1.0.0',
+          '@npmcli/b': '^1.0.0',
+          '@npmcli/c': '^1.0.0'
+        }
+      }),
+      node_modules: {
+        '@npmcli': {
+          'a': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/a',
+              version: '1.0.0',
+              dependencies: {
+                '@npmcli/c': '^1.0.0'
+              }
+            })
+          },
+          'b': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/b',
+              version: '1.1.2',
+              dependencies: {
+                '@npmcli/c': '^1.0.0'
+              }
+            })
+          },
+          'c': {
+            'package.json': JSON.stringify({
+              name: '@npmcli/c',
+              version: '1.0.0'
+            })
+          }
+        }
+      }
+    })
+    ls(['@npmcli/c'], (err) => {
+      t.ifError(err, 'npm ls')
+      t.matchSnapshot(redactCwd(result), 'should print tree output containing deduped ref')
+      t.end()
+    })
+  })
+
   t.test('using aliases', (t) => {
     prefix = t.testdir({
       'package.json': JSON.stringify({