From 6ef53ee73a2a0ed26f8c1507018d201a7bd36d1e Mon Sep 17 00:00:00 2001
From: Ruy Adorno <ruyadorno@hotmail.com>
Date: Tue, 28 Jul 2020 20:18:20 -0400
Subject: fix: npm ls duplicated items

When having nodes that are children of extraneous nodes, items were
getting printed twice using `npm ls`.

This fixes it by keeping track of seen nodes while iterating in a same
children level and effectively avoiding printing a same item twice.

fix: #1573

PR-URL: https://github.com/npm/cli/pull/1576
Credit: @ruyadorno
Close: #1576
Reviewed-by: @isaacs
---
 lib/ls.js                                | 21 +++++++++----
 tap-snapshots/test-lib-ls.js-TAP.test.js | 10 ++++++
 test/lib/ls.js                           | 52 ++++++++++++++++++++++++++++++++
 3 files changed, 77 insertions(+), 6 deletions(-)

diff --git a/lib/ls.js b/lib/ls.js
index b54ab02ba..09e70c9be 100644
--- a/lib/ls.js
+++ b/lib/ls.js
@@ -69,7 +69,7 @@ const getProblems = (node, { global }) => {
     problems.add(`invalid: ${node.pkgid} ${node.path}`)
   }
 
-  if (node.extraneous && !global) {
+  if (isExtraneous(node, { global })) {
     problems.add(`extraneous: ${node.pkgid} ${node.path}`)
   }
 
@@ -217,13 +217,13 @@ const filterByEdgesTypes = ({
     (filterLink ? (edge.to && edge.to.isLink) : true)
 }
 
-const appendExtraneousChildren = ({ node }) =>
+const appendExtraneousChildren = ({ node, seenPaths }) =>
   // extraneous children are not represented
   // in edges out, so here we add them to the list:
   [...node.children.values()]
-    .filter(i => i.extraneous)
+    .filter(i => !seenPaths.has(i.path) && i.extraneous)
 
-const mapEdgesToNodes = (edge) => {
+const mapEdgesToNodes = ({ seenPaths }) => (edge) => {
   let node = edge.to
 
   // if the edge is linking to a missing node, we go ahead
@@ -234,6 +234,14 @@ const mapEdgesToNodes = (edge) => {
     node = { name, pkgid, [_missing]: edge.from.pkgid }
   }
 
+  // keeps track of a set of seen paths to avoid the edge case in which a tree
+  // item would appear twice given that it's a children of an extraneous item,
+  // so it's marked extraneous but it will ALSO show up in edgesOuts of
+  // its parent so it ends up as two diff nodes if we don't track it
+  if (node.path) {
+    seenPaths.add(node.path)
+  }
+
   node[_required] = edge.spec
   node[_type] = edge.type
   node[_invalid] = edge.invalid
@@ -410,6 +418,7 @@ 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) {
+      const seenPaths = new Set()
       const shouldSkipChildren =
         !(node instanceof Arborist.Node) || (node[_depth] > depthToPrint)
       return (shouldSkipChildren)
@@ -425,8 +434,8 @@ const ls = async (args) => {
             only,
             tree
           }))
-          .map(mapEdgesToNodes)
-          .concat(appendExtraneousChildren({ node }))
+          .map(mapEdgesToNodes({ seenPaths }))
+          .concat(appendExtraneousChildren({ node, seenPaths }))
           .sort(sortAlphabetically)
           .map(augmentNodesWithMetadata({
             args,
diff --git a/tap-snapshots/test-lib-ls.js-TAP.test.js b/tap-snapshots/test-lib-ls.js-TAP.test.js
index 1363eec70..6f0c0beff 100644
--- a/tap-snapshots/test-lib-ls.js-TAP.test.js
+++ b/tap-snapshots/test-lib-ls.js-TAP.test.js
@@ -373,6 +373,16 @@ test-npm-ls@1.0.0 {CWD}/ls-ls-extraneous-deps
 
 `
 
+exports[`test/lib/ls.js TAP ls filtering by child of missing dep > should print tree and not duplicate child of missing items 1`] = `
+filter-by-child-of-missing-dep@1.0.0 {CWD}/ls-ls-filtering-by-child-of-missing-dep
++-- b@1.0.0 extraneous
+| \`-- c@1.0.0 deduped
++-- c@1.0.0 extraneous
+\`-- d@1.0.0 extraneous
+  \`-- c@2.0.0 extraneous
+
+`
+
 exports[`test/lib/ls.js TAP ls from and resolved properties > should not be printed in tree output 1`] = `
 test-npm-ls@1.0.0 {CWD}/ls-ls-from-and-resolved-properties
 \`-- simple-output@2.1.1
diff --git a/test/lib/ls.js b/test/lib/ls.js
index 21a864860..cf619eb93 100644
--- a/test/lib/ls.js
+++ b/test/lib/ls.js
@@ -1332,6 +1332,58 @@ t.test('ls', (t) => {
     })
   })
 
+  t.test('filtering by child of missing dep', (t) => {
+    prefix = t.testdir({
+      'package.json': JSON.stringify({
+        name: 'filter-by-child-of-missing-dep',
+        version: '1.0.0',
+        dependencies: {
+          'a': '^1.0.0'
+        }
+      }),
+      node_modules: {
+        b: {
+          'package.json': JSON.stringify({
+            name: 'b',
+            version: '1.0.0',
+            dependencies: {
+              c: '^1.0.0'
+            }
+          })
+        },
+        c: {
+          'package.json': JSON.stringify({
+            name: 'c',
+            version: '1.0.0'
+          })
+        },
+        d: {
+          'package.json': JSON.stringify({
+            name: 'd',
+            version: '1.0.0',
+            dependencies: {
+              c: '^2.0.0'
+            }
+          }),
+          node_modules: {
+            c: {
+              'package.json': JSON.stringify({
+                name: 'c',
+                version: '2.0.0'
+              })
+            }
+          }
+        }
+      }
+    })
+
+    ls(['c'], (err) => {
+      t.match(err.code, 'ELSPROBLEMS', 'should have ELSPROBLEMS error code')
+      t.matchSnapshot(redactCwd(result), 'should print tree and not duplicate child of missing items')
+      t.end()
+    })
+  })
+
   t.end()
 })
 
-- 
cgit v1.2.3