cycles due to npm link causing Maximum call stack size exceeded

[stefanpenner]

I'm opening this issue because:

• npm is crashing.

What's going wrong?

When node_modules contains a cycle (due to npm link) npm install will stack overflow:

xxx-debug.log

0 info it worked if it ends with ok
1 verbose cli [ '/Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/bin/node',
1 verbose cli   '/Users/spenner/.config/node/default/bin/npm',
1 verbose cli   'install',
1 verbose cli   '--save-dev',
1 verbose cli   '--loglevel error',
1 verbose cli   'morgan@^1.3.2',
1 verbose cli   'glob@^4.0.5' ]
2 info using npm@5.0.1
3 info using node@v7.4.0
4 silly install loadCurrentTree
5 silly install readLocalPackageData
6 http fetch GET 200 http://registry.npmjs.org/morgan 25ms (from cache)
7 http fetch GET 200 http://registry.npmjs.org/glob 24ms (from cache)
8 silly pacote range manifest for morgan@^1.3.2 fetched in 57ms
9 silly pacote range manifest for glob@^4.0.5 fetched in 35ms
10 verbose stack RangeError: Maximum call stack size exceeded
10 verbose stack     at exports.create (/Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/lib/node_modules/npm/lib/install/node.js:31:40)
10 verbose stack     at /Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/lib/node_modules/npm/lib/install/node.js:36:14
10 verbose stack     at Array.forEach (native)
10 verbose stack     at exports.create (/Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/lib/node_modules/npm/lib/install/node.js:33:25)
10 verbose stack     at /Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/lib/node_modules/npm/lib/install/node.js:36:14
10 verbose stack     at Array.forEach (native)
10 verbose stack     at exports.create (/Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/lib/node_modules/npm/lib/install/node.js:33:25)
10 verbose stack     at normalizeTree (/Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/lib/node_modules/npm/lib/install.js:377:5)
10 verbose stack     at Array.forEach (native)
10 verbose stack     at normalizeTree (/Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/lib/node_modules/npm/lib/install.js:379:19)
10 verbose stack     at Array.forEach (native)
10 verbose stack     at normalizeTree (/Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/lib/node_modules/npm/lib/install.js:379:19)
10 verbose stack     at Array.forEach (native)
10 verbose stack     at normalizeTree (/Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/lib/node_modules/npm/lib/install.js:379:19)
10 verbose stack     at Array.forEach (native)
10 verbose stack     at normalizeTree (/Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/lib/node_modules/npm/lib/install.js:379:19)
11 verbose cwd /Users/spenner/src/ember-cli/ember-cli/tmp/some_cool_app_clone-nPqvJmWc.tmp
12 verbose Darwin 15.6.0
13 verbose argv "/Users/spenner/src/stefanpenner/dotfiles/.config/node/versions/node-v7.4.0-darwin-x64/bin/node" "/Users/spenner/.config/node/default/bin/npm" "install" "--save-dev" "--loglevel error" "morgan@^1.3.2" "glob@^4.0.5"
14 verbose node v7.4.0
15 verbose npm  v5.0.1
16 error Maximum call stack size exceeded
17 verbose exit [ 1, true ]

Specifically, read-package-tree can return a cyclic graph and Installer.prototype.normalizeCurrentTree expects currentTree to be acyclic

npm/lib/install.js

Lines 365 to 380 in d654a8e

	normalizeTree(this.currentTree)
	// If the user didn't have a package.json then fill in deps with what was on disk
	if (this.currentTree.error) {
	for (let child of this.currentTree.children) {
	if (!child.fakeChild && isExtraneous(child)) {
	this.currentTree.package.dependencies[child.package.name] = computeVersionSpec(this.currentTree, child)
	}
	}
	}
	return cb()
	function normalizeTree (tree) {
	createNode(tree)
	tree.location = flatNameFromTree(tree)
	tree.children.forEach(normalizeTree)
	}

the combination of these two things, results in a StackOverflow.

How can the CLI team reproduce the problem?

contrived example that appears to reproduce this issue:

ember-cli/node_modules/ember-cli <symlink to ../../>

But it appears to also be an issue in more realistic examples with larger cycles.

ember-cli/node_modules/some-ember-addon/node_modules/ember-cli <symlink to ../../../../>

supporting information:

• npm -v prints: 5.0.2
• node -v prints: v7.4.0
• npm config get registry prints: http://registry.npmjs.org/
• Windows, OS X/macOS, or Linux?: likely all, but reproduced on macOS

[haggholm]

Windows, OS X/macOS, or Linux?: likely all, but reproduced on macOS

FWIW, I’m not experiencing this bug on my Linux box, but a co-worker with a Mac is having the issue.

[Mike-Dax]

I've had this bug on a Windows 10 machine, but not on MacOS (10.10.4)

[JamesMessinger]

There are several issues that all seem to be related (or duplicates). The common thread seems to be that when npm link is used to link a package to itself, subsequent npm install commands lead to a "Maximum call stack size exceeded" error:

Related Issues:

• npm link/unlink causes Maximum call stack size exceeded  #17096
• npm link can link to same directory -> Maximum call stack size exceeded #17610
• npm 5 install fails with "Maximum call stack size exceeded" (if tree has local links?) #17056

[stefanpenner]

some spelunking has yielded more info (although still incomplete, as I have not had additional free cycles):

Given:

<project>/node_module/foo  --> ~/foo // symlink
~/foo/node_modules/bar // devDependency of foo
<project>node_modules/bar // dependency

And, ~/foo contains not only its dependencies, but also its devDependencies as it is linked for development..

bar will be in the NPM's dep tree twice:

• <project> dependency
• ~/foo devDependency

Unfortunately, the ~/foo devDependency, wont have its requiredBy setup correctly, failing to account for the requiredBy edge from bar to ~/foo. As the code that maintains requiredBy only considers tree.package.dependencies (not devDeps) for non root dependencies..

This results in one of the bar (the one a devDep of ~/foo) returning nothing from requiredBy which caused @forivall's (and others stack traces) -> https://gist.github.com/forivall/249c1966dd8ac335bca4a6177e41132d

Unfortunately I believe the bandaid introduced #16937 obscured the problem slightly...

---

I believe the internal tree state ends up being being incomplete, as read-package-tree's output is annotated and added to by npm itself, but those annotations (such as requiredBy) are not complete.

My instinct suggests pushing more of this responsibility to read-package-tree (or similar abstraction). That module should have sufficient visibility and authority to annotate fields such as requiredBy etc.