install: Switch from clone to a tree-copier that's aware of our datastructures

Lodash's deep-clone is being updated to not have the catostrophic scalaing issues
it had when this patch was written, but even still, using something tailor-made
will necessarily be faster.

PR-URL: https://github.com/npm/npm/pull/9803
Fixes: #8826

2 files changed, 27 insertions, 2 deletions

diff --git a/lib/install.js b/lib/install.js
index 65d287ef2..3ebb3b3bb 100644
--- a/lib/install.js
+++ b/lib/install.js
@@ -99,7 +99,6 @@ var asyncMap = require('slide').asyncMap
 var archy = require('archy')
 var mkdirp = require('mkdirp')
 var rimraf = require('rimraf')
-var clone = require('lodash.clonedeep')
 var iferr = require('iferr')
 var validate = require('aproba')
 
@@ -112,6 +111,7 @@ var ls = require('./ls.js')
 var parseJSON = require('./utils/parse-json.js')
 
 // install specific libraries
+var copyTree = require('./install/copy-tree.js')
 var readShrinkwrap = require('./install/read-shrinkwrap.js')
 var recalculateMetadata = require('./install/deps.js').recalculateMetadata
 var loadDeps = require('./install/deps.js').loadDeps
@@ -602,7 +602,7 @@ Installer.prototype.readLocalPackageData = function (cb) {
 Installer.prototype.cloneCurrentTreeToIdealTree = function (cb) {
   validate('F', arguments)
   log.silly('install', 'cloneCurrentTreeToIdealTree')
-  this.idealTree = clone(this.currentTree)
+  this.idealTree = copyTree(this.currentTree)
   this.idealTree.warnings = []
   cb()
 }
diff --git a/lib/install/copy-tree.js b/lib/install/copy-tree.js
new file mode 100644
index 000000000..67a9c687a
--- /dev/null
+++ b/lib/install/copy-tree.js
@@ -0,0 +1,25 @@
+'use strict'
+
+module.exports = function (tree) {
+  return copyTree(tree, {})
+}
+
+function copyTree (tree, cache) {
+  if (cache[tree.path]) return cache[tree.path]
+  var newTree = cache[tree.path] = Object.create(tree)
+  copyModuleList(newTree, 'children', cache)
+  newTree.children.forEach(function (child) {
+    child.parent = newTree
+  })
+  copyModuleList(newTree, 'requires', cache)
+  copyModuleList(newTree, 'requiredBy', cache)
+  return newTree
+}
+
+function copyModuleList (tree, key, cache) {
+  var newList = []
+  tree[key].forEach(function (child) {
+    newList.push(copyTree(child, cache))
+  })
+  tree[key] = newList
+}