install: fix max callstack exceeded loops with links

iarna · iarna · commit 9fe905c399d0 · 2017-07-10T15:47:47.000-07:00
PR-URL: #17652 Credit: @iarna Reviewed-By: @zkat
diff --git a/lib/dedupe.js b/lib/dedupe.js
@@ -112,12 +112,12 @@ function moveRemainingChildren (node, diff) {
 }
 
 function remove (child, diff, done) {
-  remove_(child, diff, {}, done)
+  remove_(child, diff, new Set(), done)
 }
 
 function remove_ (child, diff, seen, done) {
-  if (seen[child.path]) return done()
-  seen[child.path] = true
+  if (seen.has(child)) return done()
+  seen.add(child)
   diff.push(['remove', child])
   child.parent.children = without(child.parent.children, child)
   asyncMap(child.children, function (child, next) {
@@ -126,13 +126,13 @@ function remove_ (child, diff, seen, done) {
 }
 
 function hoistChildren (tree, diff, next) {
-  hoistChildren_(tree, diff, {}, next)
+  hoistChildren_(tree, diff, new Set(), next)
 }
 
 function hoistChildren_ (tree, diff, seen, next) {
   validate('OAOF', arguments)
-  if (seen[tree.path]) return next()
-  seen[tree.path] = true
+  if (seen.has(tree)) return next()
+  seen.add(tree)
   asyncMap(tree.children, function (child, done) {
     if (!tree.parent) return hoistChildren_(child, diff, seen, done)
     var better = findRequirement(tree.parent, moduleName(child), getRequested(child) || npa(packageId(child)))
diff --git a/lib/install.js b/lib/install.js
@@ -372,10 +372,13 @@ Installer.prototype.normalizeCurrentTree = function (cb) {
   }
   return cb()
 
-  function normalizeTree (tree) {
+  function normalizeTree (tree, seen) {
+    if (!seen) seen = new Set()
+    if (seen.has(tree)) return
+    seen.add(tree)
     createNode(tree)
     tree.location = flatNameFromTree(tree)
-    tree.children.forEach(normalizeTree)
+    tree.children.forEach((child) => normalizeTree(child, seen))
   }
 }
 
@@ -886,15 +889,15 @@ Installer.prototype.debugTree = function (name, treeName, cb) {
 
 Installer.prototype.prettify = function (tree) {
   validate('O', arguments)
-  var seen = {}
+  var seen = new Set()
   function byName (aa, bb) {
     return packageId(aa).localeCompare(packageId(bb))
   }
   function expandTree (tree) {
-    seen[tree.path] = true
+    seen.add(tree)
     return {
       label: packageId(tree),
-      nodes: tree.children.filter((tree) => { return !seen[tree.path] && !tree.removed && !tree.failed }).sort(byName).map(expandTree)
+      nodes: tree.children.filter((tree) => { return !seen.has(tree) && !tree.removed && !tree.failed }).sort(byName).map(expandTree)
     }
   }
   return archy(expandTree(tree), '', { unicode: npm.config.get('unicode') })
diff --git a/lib/install/deps.js b/lib/install/deps.js
@@ -80,9 +80,9 @@ function childDependencySpecifier (tree, name, spec) {
 
 exports.computeMetadata = computeMetadata
 function computeMetadata (tree, seen) {
-  if (!seen) seen = {}
-  if (!tree || seen[tree.path]) return
-  seen[tree.path] = true
+  if (!seen) seen = new Set()
+  if (!tree || seen.has(tree)) return
+  seen.add(tree)
   if (tree.parent == null) {
     resetMetadata(tree)
     tree.isTop = true
@@ -413,7 +413,7 @@ exports.prefetchDeps = prefetchDeps
 function prefetchDeps (tree, deps, log, next) {
   validate('OOOF', arguments)
   var skipOptional = !npm.config.get('optional')
-  var seen = {}
+  var seen = new Set()
   const finished = andFinishTracker(log, next)
   const fpm = BB.promisify(fetchPackageMetadata)
   resolveBranchDeps(tree.package, deps).then(
@@ -426,15 +426,15 @@ function prefetchDeps (tree, deps, log, next) {
         return npa.resolve(dep, deps[dep])
       }).filter((dep) => {
         return dep.registry &&
-               !seen[dep.toString()] &&
+               !seen.has(dep.toString()) &&
                !findRequirement(tree, dep.name, dep)
       })
       if (skipOptional) {
         var optDeps = pkg.optionalDependencies || {}
         allDependencies = allDependencies.filter((dep) => !optDeps[dep.name])
       }
       return BB.map(allDependencies, (dep) => {
-        seen[dep.toString()] = true
+        seen.add(dep.toString())
         return fpm(dep, '', {tracker: log.newItem('fetchMetadata')}).then(
           (pkg) => {
             return pkg && pkg.dependencies && resolveBranchDeps(pkg, pkg.dependencies)
@@ -480,11 +480,11 @@ exports.loadDevDeps = function (tree, log, next) {
 }
 
 var loadExtraneous = exports.loadExtraneous = function (tree, log, next) {
-  var seen = {}
+  var seen = new Set()
 
   function loadExtraneous (tree) {
-    if (seen[tree.path]) return
-    seen[tree.path] = true
+    if (seen.has(tree)) return
+    seen.add(tree)
     for (var child of tree.children) {
       if (child.loaded) continue
       resolveWithExistingModule(child, tree)
@@ -634,13 +634,13 @@ var validatePeerDeps = exports.validatePeerDeps = function (tree, onInvalid) {
 }
 
 exports.validateAllPeerDeps = function (tree, onInvalid) {
-  validateAllPeerDeps(tree, onInvalid, {})
+  validateAllPeerDeps(tree, onInvalid, new Set())
 }
 
 function validateAllPeerDeps (tree, onInvalid, seen) {
   validate('OFO', arguments)
-  if (seen[tree.path]) return
-  seen[tree.path] = true
+  if (seen.has(tree)) return
+  seen.add(tree)
   validatePeerDeps(tree, onInvalid)
   tree.children.forEach(function (child) { validateAllPeerDeps(child, onInvalid, seen) })
 }
diff --git a/lib/install/flatten-tree.js b/lib/install/flatten-tree.js
@@ -8,19 +8,19 @@ module.exports.flatNameFromTree = flatNameFromTree
 
 function flattenTree (tree) {
   validate('O', arguments)
-  var seen = {}
+  var seen = new Set()
   var flat = {}
   var todo = [[tree, '/']]
   while (todo.length) {
     var next = todo.shift()
     var pkg = next[0]
-    seen[pkg.path] = true
+    seen.add(pkg)
     var path = next[1]
     flat[path] = pkg
     if (path !== '/') path += '/'
     for (var ii = 0; ii < pkg.children.length; ++ii) {
       var child = pkg.children[ii]
-      if (!seen[child.path]) {
+      if (!seen.has(child)) {
         todo.push([child, flatName(path, child)])
       }
     }
diff --git a/lib/install/is-only-dev.js b/lib/install/is-only-dev.js
@@ -10,7 +10,7 @@ const isProdDep = require('./is-prod-dep.js')
 // dependencies.
 // Dual mode modules (that are both dev AND prod) should return false.
 function isOnlyDev (node, seen) {
-  if (!seen) seen = {}
+  if (!seen) seen = new Set()
   return node.requiredBy.length && node.requiredBy.every(andIsOnlyDev(moduleName(node), seen))
 }
 
@@ -27,8 +27,8 @@ function andIsOnlyDev (name, seen) {
     if (req.isTop) {
       return isDev && !isProd
     } else {
-      if (seen[req.path]) return true
-      seen[req.path] = true
+      if (seen.has(req)) return true
+      seen.add(req)
       return isOnlyDev(req, seen)
     }
   }
diff --git a/lib/install/is-only-optional.js b/lib/install/is-only-optional.js
@@ -4,13 +4,13 @@ module.exports = isOptional
 const isOptDep = require('./is-opt-dep.js')
 
 function isOptional (node, seen) {
-  if (!seen) seen = {}
+  if (!seen) seen = new Set()
   // If a node is not required by anything, then we've reached
   // the top level package.
-  if (seen[node.path] || node.requiredBy.length === 0) {
+  if (seen.has(node) || node.requiredBy.length === 0) {
     return false
   }
-  seen[node.path] = true
+  seen.add(node)
 
   return node.requiredBy.every(function (req) {
     return isOptDep(req, node.package.name) || isOptional(req, seen)
diff --git a/lib/install/mutate-into-logical-tree.js b/lib/install/mutate-into-logical-tree.js
@@ -70,13 +70,13 @@ module.exports.asReadInstalled = function (tree) {
 }
 
 function translateTree (tree) {
-  return translateTree_(tree, {})
+  return translateTree_(tree, new Set())
 }
 
 function translateTree_ (tree, seen) {
   var pkg = tree.package
-  if (seen[tree.path]) return pkg
-  seen[tree.path] = pkg
+  if (seen.has(tree)) return pkg
+  seen.add(tree)
   if (pkg._dependencies) return pkg
   pkg._dependencies = pkg.dependencies
   pkg.dependencies = {}
diff --git a/lib/install/node.js b/lib/install/node.js
@@ -54,12 +54,12 @@ var create = exports.create = function (node, template, isNotTop) {
 }
 
 exports.reset = function (node) {
-  reset(node, {})
+  reset(node, new Set())
 }
 
 function reset (node, seen) {
-  if (seen[node.path]) return
-  seen[node.path] = true
+  if (seen.has(node)) return
+  seen.add(node)
   var child = create(node)
 
   // FIXME: cleaning up after read-package-json's mess =(
diff --git a/lib/ls.js b/lib/ls.js
@@ -87,13 +87,13 @@ var lsFromTree = ls.fromTree = function (dir, physicalTree, args, silent, cb) {
   var json = npm.config.get('json')
   var out
   if (json) {
-    var seen = []
+    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 (inList(seen, o)) return '[Circular]'
-        seen.push(o)
+        if (seen.has(o)) return '[Circular]'
+        seen.add(o)
       }
       return o
     }, 2)
@@ -255,22 +255,22 @@ function getLite (data, noname, depth) {
 
 function unloop (root) {
   var queue = [root]
-  var seen = {}
-  seen[root.path] = true
+  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[dep.path]) {
+      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[dep.path] = true
+      seen.add(dep)
       queue.push(dep)
     })
   }
diff --git a/lib/outdated.js b/lib/outdated.js
@@ -42,17 +42,14 @@ var moduleName = require('./utils/module-name.js')
 var output = require('./utils/output.js')
 var ansiTrim = require('./utils/ansi-trim')
 
-function uniqName (item) {
-  return item[0].path + '|' + item[1] + '|' + item[7]
-}
-
 function uniq (list) {
+  // we maintain the array because we need an array, not iterator, return
+  // value.
   var uniqed = []
-  var seen = {}
+  var seen = new Set()
   list.forEach(function (item) {
-    var name = uniqName(item)
-    if (seen[name]) return
-    seen[name] = true
+    if (seen.has(item)) return
+    seen.add(item)
     uniqed.push(item)
   })
   return uniqed
diff --git a/lib/rebuild.js b/lib/rebuild.js
@@ -43,10 +43,10 @@ function cleanBuild (folders, set, cb) {
 
 function filter (data, args, set, seen) {
   if (!set) set = {}
-  if (!seen) seen = {}
+  if (!seen) seen = new Set()
   if (set.hasOwnProperty(data.path)) return set
-  if (seen.hasOwnProperty(data.path)) return set
-  seen[data.path] = true
+  if (seen.has(data)) return set
+  seen.add(data)
   var pass
   if (!args.length) pass = true // rebuild everything
   else if (data.name && data._id) {
diff --git a/lib/shrinkwrap.js b/lib/shrinkwrap.js
@@ -97,9 +97,9 @@ function treeToShrinkwrap (tree) {
 
 function shrinkwrapDeps (deps, top, tree, seen) {
   validate('OOO', [deps, top, tree])
-  if (!seen) seen = {}
-  if (seen[tree.path]) return
-  seen[tree.path] = true
+  if (!seen) seen = new Set()
+  if (seen.has(tree)) return
+  seen.add(tree)
   tree.children.sort(function (aa, bb) { return moduleName(aa).localeCompare(moduleName(bb)) }).forEach(function (child) {
     if (child.fakeChild) {
       deps[moduleName(child)] = child.fakeChild
diff --git a/lib/utils/tar.js b/lib/utils/tar.js
@@ -185,11 +185,11 @@ function pack_ (tarball, folder, tree, pkg, cb) {
     var pkg = tree.children.filter(nameMatch(name))[0]
     if (!pkg) return false
     var requiredBy = [].concat(pkg.requiredBy)
-    var seen = {}
+    var seen = new Set()
     while (requiredBy.length) {
       var reqPkg = requiredBy.shift()
-      if (seen[reqPkg.path]) continue
-      seen[reqPkg.path] = true
+      if (seen.has(reqPkg)) continue
+      seen.add(reqPkg)
       if (!reqPkg) continue
       if (reqPkg.parent === tree && bd.indexOf(moduleName(reqPkg)) !== -1) {
         return true

Original file line number	Diff line number	Diff line change
`@@ -372,10 +372,13 @@ Installer.prototype.normalizeCurrentTree = function (cb) {`
`372`	`372`	`}`
`373`	`373`	`return cb()`
`374`	`374`
`375`		`- function normalizeTree (tree) {`
	`375`	`+ function normalizeTree (tree, seen) {`
	`376`	`+ if (!seen) seen = new Set()`
	`377`	`+ if (seen.has(tree)) return`
	`378`	`+ seen.add(tree)`
`376`	`379`	`createNode(tree)`
`377`	`380`	`tree.location = flatNameFromTree(tree)`
`378`		`- tree.children.forEach(normalizeTree)`
	`381`	`+ tree.children.forEach((child) => normalizeTree(child, seen))`
`379`	`382`	`}`
`380`	`383`	`}`
`381`	`384`
`@@ -886,15 +889,15 @@ Installer.prototype.debugTree = function (name, treeName, cb) {`
`886`	`889`
`887`	`890`	`Installer.prototype.prettify = function (tree) {`
`888`	`891`	`validate('O', arguments)`
`889`		`- var seen = {}`
	`892`	`+ var seen = new Set()`
`890`	`893`	`function byName (aa, bb) {`
`891`	`894`	`return packageId(aa).localeCompare(packageId(bb))`
`892`	`895`	`}`
`893`	`896`	`function expandTree (tree) {`
`894`		`- seen[tree.path] = true`
	`897`	`+ seen.add(tree)`
`895`	`898`	`return {`
`896`	`899`	`label: packageId(tree),`
`897`		`- nodes: tree.children.filter((tree) => { return !seen[tree.path] && !tree.removed && !tree.failed }).sort(byName).map(expandTree)`
	`900`	`+ nodes: tree.children.filter((tree) => { return !seen.has(tree) && !tree.removed && !tree.failed }).sort(byName).map(expandTree)`
`898`	`901`	`}`
`899`	`902`	`}`
`900`	`903`	`return archy(expandTree(tree), '', { unicode: npm.config.get('unicode') })`
Original file line number	Diff line number	Diff line change
`@@ -10,7 +10,7 @@ const isProdDep = require('./is-prod-dep.js')`
`10`	`10`	`// dependencies.`
`11`	`11`	`// Dual mode modules (that are both dev AND prod) should return false.`
`12`	`12`	`function isOnlyDev (node, seen) {`
`13`		`- if (!seen) seen = {}`
	`13`	`+ if (!seen) seen = new Set()`
`14`	`14`	`return node.requiredBy.length && node.requiredBy.every(andIsOnlyDev(moduleName(node), seen))`
`15`	`15`	`}`
`16`	`16`
`@@ -27,8 +27,8 @@ function andIsOnlyDev (name, seen) {`
`27`	`27`	`if (req.isTop) {`
`28`	`28`	`return isDev && !isProd`
`29`	`29`	`} else {`
`30`		`- if (seen[req.path]) return true`
`31`		`- seen[req.path] = true`
	`30`	`+ if (seen.has(req)) return true`
	`31`	`+ seen.add(req)`
`32`	`32`	`return isOnlyDev(req, seen)`
`33`	`33`	`}`
`34`	`34`	`}`
Original file line number	Diff line number	Diff line change
`@@ -54,12 +54,12 @@ var create = exports.create = function (node, template, isNotTop) {`
`54`	`54`	`}`
`55`	`55`
`56`	`56`	`exports.reset = function (node) {`
`57`		`- reset(node, {})`
	`57`	`+ reset(node, new Set())`
`58`	`58`	`}`
`59`	`59`
`60`	`60`	`function reset (node, seen) {`
`61`		`- if (seen[node.path]) return`
`62`		`- seen[node.path] = true`
	`61`	`+ if (seen.has(node)) return`
	`62`	`+ seen.add(node)`
`63`	`63`	`var child = create(node)`
`64`	`64`
`65`	`65`	`// FIXME: cleaning up after read-package-json's mess =(`