11 ms·

Flat Tree Dependency Resolution in Npm v3

113 points by funerr 11y ago

ruffrey 11y ago
If this works it might reduce the slug size of a built node app by a lot of a little. Though, if there are problems, I wonder - can the flat dep resolution be disabled using some CLI flag? Or when installing deps, or in .npmrc, or during a shrinkwrap?
justinsaccount 11y ago
Will this prevent node_modules/ from having 17 copies of the the same file in 17 different places?
- ksherlock 11y ago
  yes, as long as there aren't version conflicts.
  - baudehlo 11y ago
    Which there will be because everyone uses --save so each module has the version around when they added the module.
    - pauly 11y ago
      --save adds the fairly loose ^ version number, so any major version should match, so less conflicts than if you'd added an exact version match, or a ~ match
      - Touche 11y ago
        A good percentage of npm modules are <1.0.0 so you're very likely to get dupes.
shill 11y ago
This will help Windows users who have filesystem and zip compression issues with deeply nested dependency trees.
- frik 11y ago
  Windows to this day still has the 260 chars path limit. http://msdn.microsoft.com/en-us/library/aa365247(VS.85).aspx#maxpath http://msdn.microsoft.com/en-us/library/aa365247(VS.85).aspx... https://en.wikipedia.org/wiki/Long_filename https://en.wikipedia.org/wiki/Long_filename Microsoft should finally fix such old limitations (-> update WinAPI), instead adding work arounds to third party projects like Nodejs. https://github.com/Microsoft/nodejstools/issues/69 https://github.com/Microsoft/nodejstools/issues/69 They could also improve the command line shell (cmd.exe) that also PowerShell relies on.
  - bcoates 11y ago
    That's a serious breaking change to existing windows programs and can safely be put in the "never going to happen" pile.
amasad 11y ago
This is good news for client side bundlers like Webpack and Browserify -- where size really matters -- they don't have to end up with multiple copies of the same module. I would also assume for very large apps it may improve startup time because you don't have to initialize and retain multiple copies of the same module.
- deleted 11y ago
  [deleted]
  - Killswitch 11y ago
    While I can understand the want for that, there's too much issues. The only reason npm does it this way is because the module that depends on B v1.3 and a module that depends on B v2.1 could be introducing some really bad bugs or breakage if you force all modules to use B v2.1. That's one of the reason bower is losing out.
    - deleted 11y ago
      [deleted]
  - tedmiston 11y ago
    Not really -- unless you want to fork each top-level dependency and update the common dependencies to the latest common subversion in package.json (and maintain that). Far from ideal IMO.
  - ag_dubs 11y ago
    forcing a single copy of a dep is exactly the opposite of the dependency strategy both the node module loader and npm take. the fact that the node module loader can load more than one version of a module into memory is its strength and npm plays to this, and in doing so avoids "dependency hell". you might checkout this page in the docs that talks more about this: https://docs.npmjs.com/how-npm-works/npm2 https://docs.npmjs.com/how-npm-works/npm2
- frank-weindel 11y ago
  This has been around for a number of months. The sad thing is because of this unpredictable (or rather arbitrarily alphabetical) `npm install` order different dependency trees can result which can still lead to a very common module being bundled multiple times. I was a fan of bower's strictly flat model because it prevents such duplication and even notifies you when incompatibilities occur. However bower seems to be losing the battle with NPM as the defacto web/javascript module repo. The allowed/unpredictable duplication can even cause very hard to identify bugs when a peer dependency relies on "instanceof" checks and there are multiple versions of this dependency. I've seen it happen with React and Backbone to name a couple. If the `npm install` allowed control over install order (instead of just being alphabetical) and there was a way to be notified of incompatibilities that would cause potentially unnecessary duplication that would be at least something that could prevent problems like this from occurring.
kylecordes 11y ago
I understand that this is a hairy, messy problem they are solving, and that they traded off one aspect of the problem for another (Install order dependency! as a new "feature" in 2015!). But I wish they had aimed higher. The better goal would be that the entire state of the node modules directory is a pure function of the contents of the package.json file plus the platform details (compiler used for native modules). While they're at it, the ecosystem could be improved considerably if there was some sort of obvious "penalty" applied to any package that compiles native code, because such things cause considerable extra trouble for Windows users. A visible penalty, transitively carried up the dependency tree, would discourage use of such modules with native code; projects would use them (depend on them) only if absolutely necessary instead of accidentally, all over, all the time.
- city41 11y ago
  Why do dev communities have to continually pay the Windows tax? If Microsoft keeps insisting on being an outlier in the world of OSes, shouldn't they be the ones burdened? I gotta say, as someone who never ever uses Windows but maintains a couple of open source packages, I'm really sick of the Windows only problems that crop up.
  - tvanantwerp 11y ago
    As someone who has no choice but to use Windows at work, I'm really sick of all the problems that crop up because so many tools use were written by people who won't use Windows and haven't tested anything on it.
    - city41 11y ago
      I feel your pain, but am not convinced open source maintainers should have to be the ones to resolve the issue. Especially since so many projects are done using spare time and with no compensation.
    - saosebastiao 11y ago
      If I had no choice but to use Windows at work, and using Windows meant I couldn't use a large amount of development tools that I rely on, then the last ones I would blame would be the open source developers that won't use or develop for Windows. Your employer is the problem here.
vec 11y ago
So, assuming I have two libraries, A and B, that both require the same version of library C, do those libraries still get their own separate in-memory copies of C, or do they share a singleton? It's terrible practice, but it's not unheard of for an NPM module to monkey patch its dependencies, since before this the library could assume it had sole ownership of its whole subtree.
- mavdi 11y ago
  Interesting. This would indeed be a problem. I hope they don't share them between modules because if one mutates a dependancy, it would be nearly impossible to debug/fix.
- Killswitch 11y ago
  If depend on A and B and both A and B depend on the same version range as C, C is now a top-level dependency. Your node_modules will look like this: - Package_A - Package_B - Package_C It's only when A and B depend on different versions of C that cannot be resolved via semver as safe. - Package_A -- node_modules --- Package_C - Package_B -- node_modules --- Package_C I am pretty certain that monkey patching your dependencies is frowned upon in the Node world. It's best to fork the repo make your changes, and then depend on that.
  - randallsquared 11y ago
    Sadly, this is the result of the second situation: - Package_A - Package_C_vX - Package_B -- node_modules --- Package_C_vY
theGimp 11y ago
That's a great improvement over the old behavior, but I'm wondering why the team didn't go a different route. Why not always store packages at the top level, and create a directory for each version that's required? For example: directory "A" contains two subdirectories: "v0.1.0" and "v0.1.1"
- dc2 11y ago
  When your actual Node .js file runs `require('a')`, it has no context to determine which version it is requiring. To expect Node to look for a package.json file at runtime is absurd. This presents a problem.
  - deleted 11y ago
    [deleted]
  - theGimp 11y ago
    I'm guessing the current behavior for require is to bubble up the directory structure and look for "node_packages". So resolving things at runtime is already happening. I agree using package.json at runtime is not the best solution though. A way to keep things clean and avoid using package.json is to use symlinks instead of downloading a fresh copy, which would make putting everything at the top level a possibility. I'm sure that option was considered, but I'm curious about why it was not taken. I suppose I should look at the discussion notes. Hope I'll remember to do that when I'm home!
    - nawitus 11y ago
      Symlinks would make copying and archiving the node_modules structure more problematic.
    - JaRail 11y ago
      Symlinks break peer dependencies.
  - curun1r 11y ago
    That version information could be encoded into symlinks if it weren't for the need to support Windows.
ag_dubs 11y ago
as the person who wrote these docs-- if you have questions or things you'd like to see addressed, i'd really love if you filed issues on the repo. https://github.com/npm/docs/issues https://github.com/npm/docs/issues
hoodoof 11y ago
Sorry to be negative but one of the things that I hate more than anything in my software development work is typing "npm install blah" and almost always being hit with wave after wave of errors typically related to dependencies. I don't know why it happens and I don't care I just wish they'd fix it. So many, many errors. Go on, try installing X packages at random using npm - did they install cleanly? The baseline outcome for using a package installer should not be reams of errors, it should be a cleanly installed package. Installing packages works fine with other language ecosystems, why not with npm?
- Touche 11y ago
  NPM has some dumb legacy features like optionalDependencies. optionalDependencies are often native code dependencies that might fail but the package is still usable, maybe just some specific feature isn't. That's the most common reason I come across for errors.
  - hoodoof 11y ago
    Whatever the reason, they should fix it - I spend all day fighting through vast numbers of problems and errors in all sorts of software systems but nothing ranks as high as "npm install" for bad user experience. It's the one thing that browns me off more than anything - I dread having to type "npm install" and its my number one gripe in a world of broken software which is really saying something when so much software is broken.
tlrobinson 11y ago
"dependency resolution depends on install order" Does this sound insane to anyone else? EDIT: I understand not wanting to modify node's `require` semantics, but this is an unacceptable sacrifice of consistency for efficiency. Surely it would have been possible for an `npm install --save x` to put the `node_modules` directory in a state identical to `npm install --save x && rm -rf node_modules && npm install`. It might take a little longer to shuffle some directories around, but certainly not longer than a full `npm install`.
- hakcermani 11y ago
  Totally. That was the first thing that stuck out to me.
- paulddraper 11y ago
  Surely they will have to change that. Right? It can't last long.
- frank-weindel 11y ago
  What's more is that standard `npm install` install order is ALWAYS alphabetic. Which causes some packages, purely arbitrarily, to influence directory structure.
z3t4 11y ago
I think they are trying to be too smart about it ... I rather waste several GB's of HDD space then having my production crash once because of dependencies.
vfc1 11y ago
Jspm solves this by installing the module in a directory appending the package version. There is no maximally flat tree, the tree is 100% flat. At most there are several versions of the same package side by side, but no nesting. It even supports circular dependencies.
- theGimp 11y ago
  Wow. Thanks for opening my eyes to do that. I was wondering why I would use another package manager.
- nmjohn 11y ago
  Are there any trade-offs to this approach? This seems so obvious to me I'm confused why it is more widely used.
  - zebracanevra 11y ago
    In node, require()'ing a dependency is stateless - it searches ./node_modules/ for the module, then ../n_m/ then ../../n_m/, etc, until it finds an appropriately named module. In JSPM/SystemJS, require()'ing/importing a module is still by name (as it supports NPM modules), but the package.json file has to be parsed in order to map module names to an installed module version. Note, this mapping is only done in the developer environment - once you build a bundle all the mapping is statically compiled into one file.
tolmasky 11y ago
I just filed a bug: https://github.com/npm/npm/issues/10999 https://github.com/npm/npm/issues/10999 I guess I'm not sure what level of non-determinism they expect, but on this page: https://docs.npmjs.com/how-npm-works/npm3-nondet https://docs.npmjs.com/how-npm-works/npm3-nondet it appears to make the claim that the only effect is on tree structure, not the actual versions of packages that are picked up. And in fact in their example this IS the case. I think this is fine btw. However, I have found edge cases where install order actually changes the versions of packages that are picked up, and in ways that make it very very difficult to work around (basically you will be forced to manually edit a shrink-wrap file -- so it is necessarily on the end user not the package writer). Basically, if any package lists and absolute dependency (vs a semver range), it will affect ALL the packages alphabetically later than it and FORCE them to take the same dependency.
bhouston 11y ago
I do not understand why they just didn't have a two level directory structure: node_modules/[module_name]/[version] Then it would be flat and support multiple versions of the same module in a way that is completely deterministic and also fully deduplicated. This new system is unnecessarily complex.
- JaRail 11y ago
  The file system layout is constrained by how dependency resolution works. For example, a require() call has a very (computationally) simple algorithm. I certainly agree that your suggestion simplifies file-system layouts. The tradeoff is that the complexity shifts to other parts of the system. That said, I'm not a fan of the v3 approach. I'd have preferred a central package cache with a structure similar to your suggestion. I'd add that each package in the cache should have all of its dependencies resolved in its own /node_modules/ dir with symlinks. Unfortunately, I still can't see a nice way to handle peer dependencies. Peer dependencies require the ability to walk up the file system to resolve, which you can't do with symlinks.
- DCoder 11y ago
  With that approach, the module loader needs to know which version of a module to load for you when you require() something - in the general case that can't be done without parsing your package.json . This would require changes to node itself, not just npm, as well as all the external tools that implemented node's current require algorithm.
brianbarker 11y ago
V2's deep nesting recently caused trouble for us at work. We had errors where our node_modules folder was too long for Windows, due to the deep folder structure. Updating to v3 resolved the problem. Hopefully other flaws being discussed here can be worked out as npm evolves.

113 points by funerr 11y ago

If this works it might reduce the slug size of a built node app by a lot of a little. Though, if there are problems, I wonder - can the flat dep resolution be disabled using some CLI flag? Or when installing deps, or in .npmrc, or during a shrinkwrap?

justinsaccount 11y ago

Will this prevent node_modules/ from having 17 copies of the the same file in 17 different places?

ksherlock 11y ago
yes, as long as there aren't version conflicts.
- baudehlo 11y ago
  Which there will be because everyone uses --save so each module has the version around when they added the module.
  - pauly 11y ago
    --save adds the fairly loose ^ version number, so any major version should match, so less conflicts than if you'd added an exact version match, or a ~ match
    - Touche 11y ago
      A good percentage of npm modules are <1.0.0 so you're very likely to get dupes.

shill 11y ago

This will help Windows users who have filesystem and zip compression issues with deeply nested dependency trees.

frik 11y ago
Windows to this day still has the 260 chars path limit. http://msdn.microsoft.com/en-us/library/aa365247(VS.85).aspx#maxpath http://msdn.microsoft.com/en-us/library/aa365247(VS.85).aspx... https://en.wikipedia.org/wiki/Long_filename https://en.wikipedia.org/wiki/Long_filename Microsoft should finally fix such old limitations (-> update WinAPI), instead adding work arounds to third party projects like Nodejs. https://github.com/Microsoft/nodejstools/issues/69 https://github.com/Microsoft/nodejstools/issues/69 They could also improve the command line shell (cmd.exe) that also PowerShell relies on.
- bcoates 11y ago
  That's a serious breaking change to existing windows programs and can safely be put in the "never going to happen" pile.

amasad 11y ago

This is good news for client side bundlers like Webpack and Browserify -- where size really matters -- they don't have to end up with multiple copies of the same module. I would also assume for very large apps it may improve startup time because you don't have to initialize and retain multiple copies of the same module.

deleted 11y ago
[deleted]
- Killswitch 11y ago
  While I can understand the want for that, there's too much issues. The only reason npm does it this way is because the module that depends on B v1.3 and a module that depends on B v2.1 could be introducing some really bad bugs or breakage if you force all modules to use B v2.1. That's one of the reason bower is losing out.
  - deleted 11y ago
    [deleted]
- tedmiston 11y ago
  Not really -- unless you want to fork each top-level dependency and update the common dependencies to the latest common subversion in package.json (and maintain that). Far from ideal IMO.
- ag_dubs 11y ago
  forcing a single copy of a dep is exactly the opposite of the dependency strategy both the node module loader and npm take. the fact that the node module loader can load more than one version of a module into memory is its strength and npm plays to this, and in doing so avoids "dependency hell". you might checkout this page in the docs that talks more about this: https://docs.npmjs.com/how-npm-works/npm2 https://docs.npmjs.com/how-npm-works/npm2
frank-weindel 11y ago
This has been around for a number of months. The sad thing is because of this unpredictable (or rather arbitrarily alphabetical) `npm install` order different dependency trees can result which can still lead to a very common module being bundled multiple times. I was a fan of bower's strictly flat model because it prevents such duplication and even notifies you when incompatibilities occur. However bower seems to be losing the battle with NPM as the defacto web/javascript module repo. The allowed/unpredictable duplication can even cause very hard to identify bugs when a peer dependency relies on "instanceof" checks and there are multiple versions of this dependency. I've seen it happen with React and Backbone to name a couple. If the `npm install` allowed control over install order (instead of just being alphabetical) and there was a way to be notified of incompatibilities that would cause potentially unnecessary duplication that would be at least something that could prevent problems like this from occurring.

kylecordes 11y ago

I understand that this is a hairy, messy problem they are solving, and that they traded off one aspect of the problem for another (Install order dependency! as a new "feature" in 2015!). But I wish they had aimed higher. The better goal would be that the entire state of the node modules directory is a pure function of the contents of the package.json file plus the platform details (compiler used for native modules). While they're at it, the ecosystem could be improved considerably if there was some sort of obvious "penalty" applied to any package that compiles native code, because such things cause considerable extra trouble for Windows users. A visible penalty, transitively carried up the dependency tree, would discourage use of such modules with native code; projects would use them (depend on them) only if absolutely necessary instead of accidentally, all over, all the time.

city41 11y ago
Why do dev communities have to continually pay the Windows tax? If Microsoft keeps insisting on being an outlier in the world of OSes, shouldn't they be the ones burdened? I gotta say, as someone who never ever uses Windows but maintains a couple of open source packages, I'm really sick of the Windows only problems that crop up.
- tvanantwerp 11y ago
  As someone who has no choice but to use Windows at work, I'm really sick of all the problems that crop up because so many tools use were written by people who won't use Windows and haven't tested anything on it.
  - city41 11y ago
    I feel your pain, but am not convinced open source maintainers should have to be the ones to resolve the issue. Especially since so many projects are done using spare time and with no compensation.
  - saosebastiao 11y ago
    If I had no choice but to use Windows at work, and using Windows meant I couldn't use a large amount of development tools that I rely on, then the last ones I would blame would be the open source developers that won't use or develop for Windows. Your employer is the problem here.

vec 11y ago

So, assuming I have two libraries, A and B, that both require the same version of library C, do those libraries still get their own separate in-memory copies of C, or do they share a singleton? It's terrible practice, but it's not unheard of for an NPM module to monkey patch its dependencies, since before this the library could assume it had sole ownership of its whole subtree.

mavdi 11y ago
Interesting. This would indeed be a problem. I hope they don't share them between modules because if one mutates a dependancy, it would be nearly impossible to debug/fix.
Killswitch 11y ago
If depend on A and B and both A and B depend on the same version range as C, C is now a top-level dependency. Your node_modules will look like this: - Package_A - Package_B - Package_C It's only when A and B depend on different versions of C that cannot be resolved via semver as safe. - Package_A -- node_modules --- Package_C - Package_B -- node_modules --- Package_C I am pretty certain that monkey patching your dependencies is frowned upon in the Node world. It's best to fork the repo make your changes, and then depend on that.
- randallsquared 11y ago
  Sadly, this is the result of the second situation: - Package_A - Package_C_vX - Package_B -- node_modules --- Package_C_vY

theGimp 11y ago

That's a great improvement over the old behavior, but I'm wondering why the team didn't go a different route. Why not always store packages at the top level, and create a directory for each version that's required? For example: directory "A" contains two subdirectories: "v0.1.0" and "v0.1.1"

dc2 11y ago
When your actual Node .js file runs `require('a')`, it has no context to determine which version it is requiring. To expect Node to look for a package.json file at runtime is absurd. This presents a problem.
- deleted 11y ago
  [deleted]
- theGimp 11y ago
  I'm guessing the current behavior for require is to bubble up the directory structure and look for "node_packages". So resolving things at runtime is already happening. I agree using package.json at runtime is not the best solution though. A way to keep things clean and avoid using package.json is to use symlinks instead of downloading a fresh copy, which would make putting everything at the top level a possibility. I'm sure that option was considered, but I'm curious about why it was not taken. I suppose I should look at the discussion notes. Hope I'll remember to do that when I'm home!
  - nawitus 11y ago
    Symlinks would make copying and archiving the node_modules structure more problematic.
  - JaRail 11y ago
    Symlinks break peer dependencies.
- curun1r 11y ago
  That version information could be encoded into symlinks if it weren't for the need to support Windows.

ag_dubs 11y ago

as the person who wrote these docs-- if you have questions or things you'd like to see addressed, i'd really love if you filed issues on the repo. https://github.com/npm/docs/issues https://github.com/npm/docs/issues

hoodoof 11y ago

Sorry to be negative but one of the things that I hate more than anything in my software development work is typing "npm install blah" and almost always being hit with wave after wave of errors typically related to dependencies. I don't know why it happens and I don't care I just wish they'd fix it. So many, many errors. Go on, try installing X packages at random using npm - did they install cleanly? The baseline outcome for using a package installer should not be reams of errors, it should be a cleanly installed package. Installing packages works fine with other language ecosystems, why not with npm?

Touche 11y ago
NPM has some dumb legacy features like optionalDependencies. optionalDependencies are often native code dependencies that might fail but the package is still usable, maybe just some specific feature isn't. That's the most common reason I come across for errors.
- hoodoof 11y ago
  Whatever the reason, they should fix it - I spend all day fighting through vast numbers of problems and errors in all sorts of software systems but nothing ranks as high as "npm install" for bad user experience. It's the one thing that browns me off more than anything - I dread having to type "npm install" and its my number one gripe in a world of broken software which is really saying something when so much software is broken.

tlrobinson 11y ago

"dependency resolution depends on install order" Does this sound insane to anyone else? EDIT: I understand not wanting to modify node's `require` semantics, but this is an unacceptable sacrifice of consistency for efficiency. Surely it would have been possible for an `npm install --save x` to put the `node_modules` directory in a state identical to `npm install --save x && rm -rf node_modules && npm install`. It might take a little longer to shuffle some directories around, but certainly not longer than a full `npm install`.

hakcermani 11y ago
Totally. That was the first thing that stuck out to me.
paulddraper 11y ago
Surely they will have to change that. Right? It can't last long.
frank-weindel 11y ago
What's more is that standard `npm install` install order is ALWAYS alphabetic. Which causes some packages, purely arbitrarily, to influence directory structure.

z3t4 11y ago

I think they are trying to be too smart about it ... I rather waste several GB's of HDD space then having my production crash once because of dependencies.

vfc1 11y ago

Jspm solves this by installing the module in a directory appending the package version. There is no maximally flat tree, the tree is 100% flat. At most there are several versions of the same package side by side, but no nesting. It even supports circular dependencies.

theGimp 11y ago
Wow. Thanks for opening my eyes to do that. I was wondering why I would use another package manager.
nmjohn 11y ago
Are there any trade-offs to this approach? This seems so obvious to me I'm confused why it is more widely used.
- zebracanevra 11y ago
  In node, require()'ing a dependency is stateless - it searches ./node_modules/ for the module, then ../n_m/ then ../../n_m/, etc, until it finds an appropriately named module. In JSPM/SystemJS, require()'ing/importing a module is still by name (as it supports NPM modules), but the package.json file has to be parsed in order to map module names to an installed module version. Note, this mapping is only done in the developer environment - once you build a bundle all the mapping is statically compiled into one file.

tolmasky 11y ago

I just filed a bug: https://github.com/npm/npm/issues/10999 https://github.com/npm/npm/issues/10999 I guess I'm not sure what level of non-determinism they expect, but on this page: https://docs.npmjs.com/how-npm-works/npm3-nondet https://docs.npmjs.com/how-npm-works/npm3-nondet it appears to make the claim that the only effect is on tree structure, not the actual versions of packages that are picked up. And in fact in their example this IS the case. I think this is fine btw. However, I have found edge cases where install order actually changes the versions of packages that are picked up, and in ways that make it very very difficult to work around (basically you will be forced to manually edit a shrink-wrap file -- so it is necessarily on the end user not the package writer). Basically, if any package lists and absolute dependency (vs a semver range), it will affect ALL the packages alphabetically later than it and FORCE them to take the same dependency.

bhouston 11y ago

I do not understand why they just didn't have a two level directory structure: node_modules/[module_name]/[version] Then it would be flat and support multiple versions of the same module in a way that is completely deterministic and also fully deduplicated. This new system is unnecessarily complex.

JaRail 11y ago
The file system layout is constrained by how dependency resolution works. For example, a require() call has a very (computationally) simple algorithm. I certainly agree that your suggestion simplifies file-system layouts. The tradeoff is that the complexity shifts to other parts of the system. That said, I'm not a fan of the v3 approach. I'd have preferred a central package cache with a structure similar to your suggestion. I'd add that each package in the cache should have all of its dependencies resolved in its own /node_modules/ dir with symlinks. Unfortunately, I still can't see a nice way to handle peer dependencies. Peer dependencies require the ability to walk up the file system to resolve, which you can't do with symlinks.
DCoder 11y ago
With that approach, the module loader needs to know which version of a module to load for you when you require() something - in the general case that can't be done without parsing your package.json . This would require changes to node itself, not just npm, as well as all the external tools that implemented node's current require algorithm.

brianbarker 11y ago

V2's deep nesting recently caused trouble for us at work. We had errors where our node_modules folder was too long for Windows, due to the deep folder structure. Updating to v3 resolved the problem. Hopefully other flaws being discussed here can be worked out as npm evolves.