"Fossies" - the Fresh Open Source Software Archive

Member "Atom/resources/app/apm/node_modules/npm/lib/install/deps.js" (7 Feb 2017, 23564 Bytes) of archive /windows/misc/atom-windows.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Javascript source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 'use strict'
    2 var assert = require('assert')
    3 var path = require('path')
    4 var semver = require('semver')
    5 var asyncMap = require('slide').asyncMap
    6 var chain = require('slide').chain
    7 var union = require('lodash.union')
    8 var iferr = require('iferr')
    9 var npa = require('npm-package-arg')
   10 var validate = require('aproba')
   11 var realizePackageSpecifier = require('realize-package-specifier')
   12 var realizeShrinkwrapSpecifier = require('./realize-shrinkwrap-specifier')
   13 var asap = require('asap')
   14 var dezalgo = require('dezalgo')
   15 var fetchPackageMetadata = require('../fetch-package-metadata.js')
   16 var andAddParentToErrors = require('./and-add-parent-to-errors.js')
   17 var addShrinkwrap = require('../fetch-package-metadata.js').addShrinkwrap
   18 var addBundled = require('../fetch-package-metadata.js').addBundled
   19 var readShrinkwrap = require('./read-shrinkwrap.js')
   20 var inflateShrinkwrap = require('./inflate-shrinkwrap.js')
   21 var inflateBundled = require('./inflate-bundled.js')
   22 var andFinishTracker = require('./and-finish-tracker.js')
   23 var npm = require('../npm.js')
   24 var flatName = require('./flatten-tree.js').flatName
   25 var createChild = require('./node.js').create
   26 var resetMetadata = require('./node.js').reset
   27 var andIgnoreErrors = require('./and-ignore-errors.js')
   28 var isInstallable = require('./validate-args.js').isInstallable
   29 var packageId = require('../utils/package-id.js')
   30 var moduleName = require('../utils/module-name.js')
   31 
   32 // The export functions in this module mutate a dependency tree, adding
   33 // items to them.
   34 
   35 function isDep (tree, child, cb) {
   36   var name = moduleName(child)
   37   var prodVer = isProdDep(tree, name)
   38   var devVer = isDevDep(tree, name)
   39 
   40   childDependencySpecifier(tree, name, prodVer, function (er, prodSpec) {
   41     if (er) return cb(child.fromShrinkwrap)
   42     var matches
   43     if (prodSpec) matches = doesChildVersionMatch(child, prodSpec, tree)
   44     if (matches) return cb(true, prodSpec)
   45     if (devVer === prodVer) return cb(child.fromShrinkwrap)
   46     childDependencySpecifier(tree, name, devVer, function (er, devSpec) {
   47       if (er) return cb(child.fromShrinkwrap)
   48       cb(doesChildVersionMatch(child, devSpec, tree) || child.fromShrinkwrap, null, devSpec)
   49     })
   50   })
   51 }
   52 
   53 function isDevDep (tree, name, cb) {
   54   var devDeps = tree.package.devDependencies || {}
   55   return devDeps[name]
   56 }
   57 
   58 function isProdDep (tree, name, cb) {
   59   var deps = tree.package.dependencies || {}
   60   return deps[name]
   61 }
   62 
   63 var registryTypes = { range: true, version: true }
   64 
   65 function doesChildVersionMatch (child, requested, requestor) {
   66   // we always consider deps provided by a shrinkwrap as "correct" or else
   67   // we'll subvert them if they're intentionally "invalid"
   68   if (child.parent === requestor && child.fromShrinkwrap) return true
   69   // ranges of * ALWAYS count as a match, because when downloading we allow
   70   // prereleases to match * if there are ONLY prereleases
   71   if (requested.spec === '*') return true
   72 
   73   var childReq = child.package._requested
   74   if (childReq) {
   75     if (childReq.rawSpec === requested.rawSpec) return true
   76     if (childReq.type === requested.type && childReq.spec === requested.spec) return true
   77   }
   78   if (!registryTypes[requested.type]) return requested.rawSpec === child.package._from
   79   return semver.satisfies(child.package.version, requested.spec)
   80 }
   81 
   82 // TODO: Rename to maybe computeMetadata or computeRelationships
   83 exports.recalculateMetadata = function (tree, log, next) {
   84   recalculateMetadata(tree, log, {}, next)
   85 }
   86 
   87 exports._childDependencySpecifier = childDependencySpecifier
   88 function childDependencySpecifier (tree, name, spec, cb) {
   89   if (!tree.resolved) tree.resolved = {}
   90   if (!tree.resolved[name]) tree.resolved[name] = {}
   91   if (tree.resolved[name][spec]) {
   92     return asap(function () {
   93       cb(null, tree.resolved[name][spec])
   94     })
   95   }
   96   realizePackageSpecifier(name + '@' + spec, packageRelativePath(tree), function (er, req) {
   97     if (er) return cb(er)
   98     tree.resolved[name][spec] = req
   99     cb(null, req)
  100   })
  101 }
  102 
  103 function recalculateMetadata (tree, log, seen, next) {
  104   validate('OOOF', arguments)
  105   if (seen[tree.path]) return next()
  106   seen[tree.path] = true
  107   if (tree.parent == null) {
  108     resetMetadata(tree)
  109     tree.isTop = true
  110   }
  111 
  112   function markDeps (toMark, done) {
  113     var name = toMark.name
  114     var spec = toMark.spec
  115     var kind = toMark.kind
  116     childDependencySpecifier(tree, name, spec, function (er, req) {
  117       if (er || !req.name) return done()
  118       var child = findRequirement(tree, req.name, req)
  119       if (child) {
  120         resolveWithExistingModule(child, tree, log, andIgnoreErrors(done))
  121       } else if (kind === 'dep') {
  122         tree.missingDeps[req.name] = req.rawSpec
  123         done()
  124       } else if (kind === 'dev') {
  125         tree.missingDevDeps[req.name] = req.rawSpec
  126         done()
  127       } else {
  128         done()
  129       }
  130     })
  131   }
  132 
  133   function makeMarkable (deps, kind) {
  134     if (!deps) return []
  135     return Object.keys(deps).map(function (depname) { return { name: depname, spec: deps[depname], kind: kind } })
  136   }
  137 
  138   // Ensure dependencies and dev dependencies are marked as required
  139   var tomark = makeMarkable(tree.package.dependencies, 'dep')
  140   if (tree.isTop) tomark = union(tomark, makeMarkable(tree.package.devDependencies, 'dev'))
  141 
  142   // Ensure any children ONLY from a shrinkwrap are also included
  143   var childrenOnlyInShrinkwrap = tree.children.filter(function (child) {
  144     return child.fromShrinkwrap &&
  145       !tree.package.dependencies[child.package.name] &&
  146       !tree.package.devDependencies[child.package.name]
  147   })
  148   var tomarkOnlyInShrinkwrap = childrenOnlyInShrinkwrap.map(function (child) {
  149     var name = child.package.name
  150     var matched = child.package._spec.match(/^@?[^@]+@(.*)$/)
  151     var spec = matched ? matched[1] : child.package._spec
  152     var kind = tree.package.dependencies[name] ? 'dep'
  153              : tree.package.devDependencies[name] ? 'dev'
  154              : 'dep'
  155     return { name: name, spec: spec, kind: kind }
  156   })
  157   tomark = union(tomark, tomarkOnlyInShrinkwrap)
  158 
  159   // Don't bother trying to recalc children of failed deps
  160   tree.children = tree.children.filter(function (child) { return !child.failed })
  161 
  162   chain([
  163     [asyncMap, tomark, markDeps],
  164     [asyncMap, tree.children, function (child, done) { recalculateMetadata(child, log, seen, done) }]
  165   ], function () {
  166     tree.location = flatNameFromTree(tree)
  167     next(null, tree)
  168   })
  169 }
  170 
  171 function addRequiredDep (tree, child, cb) {
  172   isDep(tree, child, function (childIsDep, childIsProdDep, childIsDevDep) {
  173     if (!childIsDep) return cb(false)
  174     replaceModuleByPath(child, 'requiredBy', tree)
  175     replaceModuleByName(tree, 'requires', child)
  176     if (childIsProdDep && tree.missingDeps) delete tree.missingDeps[moduleName(child)]
  177     if (childIsDevDep && tree.missingDevDeps) delete tree.missingDevDeps[moduleName(child)]
  178     cb(true)
  179   })
  180 }
  181 
  182 exports.removeObsoleteDep = removeObsoleteDep
  183 function removeObsoleteDep (child) {
  184   if (child.removed) return
  185   child.removed = true
  186   // remove from physical tree
  187   if (child.parent) {
  188     child.parent.children = child.parent.children.filter(function (pchild) { return pchild !== child })
  189   }
  190   // remove from logical tree
  191   var requires = child.requires || []
  192   requires.forEach(function (requirement) {
  193     requirement.requiredBy = requirement.requiredBy.filter(function (reqBy) { return reqBy !== child })
  194     if (requirement.requiredBy.length === 0) removeObsoleteDep(requirement)
  195   })
  196 }
  197 
  198 function matchingDep (tree, name) {
  199   if (tree.package.dependencies && tree.package.dependencies[name]) return tree.package.dependencies[name]
  200   if (tree.package.devDependencies && tree.package.devDependencies[name]) return tree.package.devDependencies[name]
  201   return
  202 }
  203 
  204 function packageRelativePath (tree) {
  205   if (!tree) return ''
  206   var requested = tree.package._requested || {}
  207   var isLocal = requested.type === 'directory' || requested.type === 'local'
  208   return isLocal ? requested.spec : tree.path
  209 }
  210 
  211 function getShrinkwrap (tree, name) {
  212   return tree.package._shrinkwrap && tree.package._shrinkwrap.dependencies && tree.package._shrinkwrap.dependencies[name]
  213 }
  214 
  215 exports.getAllMetadata = function (args, tree, where, next) {
  216   asyncMap(args, function (arg, done) {
  217     function fetchMetadataWithVersion () {
  218       var version = matchingDep(tree, arg)
  219       var spec = version == null ? arg : arg + '@' + version
  220       return fetchPackageMetadata(spec, where, done)
  221     }
  222     if (tree && arg.lastIndexOf('@') <= 0) {
  223       var sw = getShrinkwrap(tree, arg)
  224       if (sw) {
  225         return realizeShrinkwrapSpecifier(arg, sw, where, function (err, spec) {
  226           if (err) {
  227             return fetchMetadataWithVersion()
  228           } else {
  229             return fetchPackageMetadata(spec, where, done)
  230           }
  231         })
  232       } else {
  233         return fetchMetadataWithVersion()
  234       }
  235     } else {
  236       return fetchPackageMetadata(arg, where, done)
  237     }
  238   }, next)
  239 }
  240 
  241 // Add a list of args to tree's top level dependencies
  242 exports.loadRequestedDeps = function (args, tree, saveToDependencies, log, next) {
  243   validate('AOOF', [args, tree, log, next])
  244   asyncMap(args, function (pkg, done) {
  245     var depLoaded = andAddParentToErrors(tree, done)
  246     resolveWithNewModule(pkg, tree, log.newGroup('loadRequestedDeps'), iferr(depLoaded, function (child, tracker) {
  247       validate('OO', arguments)
  248       if (npm.config.get('global')) {
  249         child.isGlobal = true
  250       }
  251       var childName = moduleName(child)
  252       if (saveToDependencies) {
  253         tree.package[saveToDependencies][childName] =
  254           child.package._requested.rawSpec || child.package._requested.spec
  255       }
  256       if (saveToDependencies && saveToDependencies !== 'devDependencies') {
  257         tree.package.dependencies[childName] =
  258           child.package._requested.rawSpec || child.package._requested.spec
  259       }
  260       child.userRequired = true
  261       child.save = saveToDependencies
  262 
  263       // For things the user asked to install, that aren't a dependency (or
  264       // won't be when we're done), flag it as "depending" on the user
  265       // themselves, so we don't remove it as a dep that no longer exists
  266       addRequiredDep(tree, child, function (childIsDep) {
  267         if (!childIsDep) child.userRequired = true
  268         depLoaded(null, child, tracker)
  269       })
  270     }))
  271   }, andForEachChild(loadDeps, andFinishTracker(log, next)))
  272 }
  273 
  274 function moduleNameMatches (name) {
  275   return function (child) { return moduleName(child) === name }
  276 }
  277 
  278 function noModuleNameMatches (name) {
  279   return function (child) { return moduleName(child) !== name }
  280 }
  281 
  282 // while this implementation does not require async calling, doing so
  283 // gives this a consistent interface with loadDeps et al
  284 exports.removeDeps = function (args, tree, saveToDependencies, log, next) {
  285   validate('AOOF', [args, tree, log, next])
  286   args.forEach(function (pkg) {
  287     var pkgName = moduleName(pkg)
  288     var toRemove = tree.children.filter(moduleNameMatches(pkgName))
  289     var pkgToRemove = toRemove[0] || createChild({package: {name: pkgName}})
  290     if (saveToDependencies) {
  291       replaceModuleByPath(tree, 'removed', pkgToRemove)
  292       pkgToRemove.save = saveToDependencies
  293     }
  294     removeObsoleteDep(pkgToRemove)
  295   })
  296   log.finish()
  297   next()
  298 }
  299 
  300 function andForEachChild (load, next) {
  301   validate('F', [next])
  302   next = dezalgo(next)
  303   return function (er, children, logs) {
  304     // when children is empty, logs won't be passed in at all (asyncMap is weird)
  305     // so shortcircuit before arg validation
  306     if (!er && (!children || children.length === 0)) return next()
  307     validate('EAA', arguments)
  308     if (er) return next(er)
  309     assert(children.length === logs.length)
  310     var cmds = []
  311     for (var ii = 0; ii < children.length; ++ii) {
  312       cmds.push([load, children[ii], logs[ii]])
  313     }
  314     var sortedCmds = cmds.sort(function installOrder (aa, bb) {
  315       return moduleName(aa[1]).localeCompare(moduleName(bb[1]))
  316     })
  317     chain(sortedCmds, next)
  318   }
  319 }
  320 
  321 function isDepOptional (tree, name) {
  322   if (!tree.package.optionalDependencies) return false
  323   if (tree.package.optionalDependencies[name] != null) return true
  324   return false
  325 }
  326 
  327 var failedDependency = exports.failedDependency = function (tree, name_pkg) {
  328   var name, pkg
  329   if (typeof name_pkg === 'string') {
  330     name = name_pkg
  331   } else {
  332     pkg = name_pkg
  333     name = moduleName(pkg)
  334   }
  335   tree.children = tree.children.filter(noModuleNameMatches(name))
  336 
  337   if (isDepOptional(tree, name)) {
  338     return false
  339   }
  340 
  341   tree.failed = true
  342 
  343   if (tree.isTop) return true
  344 
  345   if (tree.userRequired) return true
  346 
  347   removeObsoleteDep(tree)
  348 
  349   if (!tree.requiredBy) return false
  350 
  351   for (var ii = 0; ii < tree.requiredBy.length; ++ii) {
  352     var requireParent = tree.requiredBy[ii]
  353     if (failedDependency(requireParent, tree.package)) {
  354       return true
  355     }
  356   }
  357   return false
  358 }
  359 
  360 function top (tree) {
  361   if (tree.parent) return top(tree.parent)
  362   return tree
  363 }
  364 
  365 function treeWarn (tree, what, error) {
  366   var topTree = top(tree)
  367   if (!topTree.warnings) topTree.warnings = []
  368   error.optional = flatNameFromTree(tree) + '/' + what
  369   topTree.warnings.push(error)
  370 }
  371 
  372 function andHandleOptionalErrors (log, tree, name, done) {
  373   validate('OOSF', arguments)
  374   return function (er, child, childLog) {
  375     if (!er) validate('OO', [child, childLog])
  376     if (!er) return done(er, child, childLog)
  377     var isFatal = failedDependency(tree, name)
  378     if (er && !isFatal) {
  379       tree.children = tree.children.filter(noModuleNameMatches(name))
  380       treeWarn(tree, name, er)
  381       return done()
  382     } else {
  383       return done(er, child, childLog)
  384     }
  385   }
  386 }
  387 
  388 // Load any missing dependencies in the given tree
  389 exports.loadDeps = loadDeps
  390 function loadDeps (tree, log, next) {
  391   validate('OOF', arguments)
  392   if (tree.loaded || (tree.parent && tree.parent.failed) || tree.removed) return andFinishTracker.now(log, next)
  393   if (tree.parent) tree.loaded = true
  394   if (!tree.package.dependencies) tree.package.dependencies = {}
  395   asyncMap(Object.keys(tree.package.dependencies), function (dep, done) {
  396     var version = tree.package.dependencies[dep]
  397     if (tree.package.optionalDependencies &&
  398         tree.package.optionalDependencies[dep] &&
  399         !npm.config.get('optional')) {
  400       return done()
  401     }
  402 
  403     addDependency(dep, version, tree, log.newGroup('loadDep:' + dep), andHandleOptionalErrors(log, tree, dep, done))
  404   }, andForEachChild(loadDeps, andFinishTracker(log, next)))
  405 }
  406 
  407 // Load development dependencies into the given tree
  408 exports.loadDevDeps = function (tree, log, next) {
  409   validate('OOF', arguments)
  410   if (!tree.package.devDependencies) return andFinishTracker.now(log, next)
  411   asyncMap(Object.keys(tree.package.devDependencies), function (dep, done) {
  412     // things defined as both dev dependencies and regular dependencies are treated
  413     // as the former
  414     if (tree.package.dependencies[dep]) return done()
  415 
  416     var logGroup = log.newGroup('loadDevDep:' + dep)
  417     addDependency(dep, tree.package.devDependencies[dep], tree, logGroup, done)
  418   }, andForEachChild(loadDeps, andFinishTracker(log, next)))
  419 }
  420 
  421 exports.loadExtraneous = function loadExtraneous (tree, log, next) {
  422   var seen = {}
  423   function loadExtraneous (tree, log, next) {
  424     validate('OOF', arguments)
  425     if (seen[tree.path]) return next()
  426     seen[tree.path] = true
  427     asyncMap(tree.children.filter(function (child) { return !child.loaded }), function (child, done) {
  428       resolveWithExistingModule(child, tree, log, done)
  429     }, andForEachChild(loadExtraneous, andFinishTracker(log, next)))
  430   }
  431   loadExtraneous(tree, log, next)
  432 }
  433 
  434 exports.loadExtraneous.andResolveDeps = function (tree, log, next) {
  435   validate('OOF', arguments)
  436   asyncMap(tree.children.filter(function (child) { return !child.loaded }), function (child, done) {
  437     resolveWithExistingModule(child, tree, log, done)
  438   }, andForEachChild(loadDeps, andFinishTracker(log, next)))
  439 }
  440 
  441 function addDependency (name, versionSpec, tree, log, done) {
  442   validate('SSOOF', arguments)
  443   var next = andAddParentToErrors(tree, done)
  444   childDependencySpecifier(tree, name, versionSpec, iferr(done, function (req) {
  445     var child = findRequirement(tree, name, req)
  446     if (child) {
  447       resolveWithExistingModule(child, tree, log, iferr(next, function (child, log) {
  448         if (child.package._shrinkwrap === undefined) {
  449           readShrinkwrap.andInflate(child, function (er) { next(er, child, log) })
  450         } else {
  451           next(null, child, log)
  452         }
  453       }))
  454     } else {
  455       resolveWithNewModule(req, tree, log, next)
  456     }
  457   }))
  458 }
  459 
  460 function resolveWithExistingModule (child, tree, log, next) {
  461   validate('OOOF', arguments)
  462   addRequiredDep(tree, child, function () {
  463     if (tree.parent && child.parent !== tree) updatePhantomChildren(tree.parent, child)
  464     next(null, child, log)
  465   })
  466 }
  467 
  468 var updatePhantomChildren = exports.updatePhantomChildren = function (current, child) {
  469   validate('OO', arguments)
  470   while (current && current !== child.parent) {
  471     if (!current.phantomChildren) current.phantomChildren = {}
  472     current.phantomChildren[moduleName(child)] = child
  473     current = current.parent
  474   }
  475 }
  476 
  477 function flatNameFromTree (tree) {
  478   validate('O', arguments)
  479   if (tree.isTop) return '/'
  480   var path = flatNameFromTree(tree.parent)
  481   if (path !== '/') path += '/'
  482   return flatName(path, tree)
  483 }
  484 
  485 exports._replaceModuleByPath = replaceModuleByPath
  486 function replaceModuleByPath (obj, key, child) {
  487   return replaceModule(obj, key, child, function (replacing, child) {
  488     return replacing.path === child.path
  489   })
  490 }
  491 
  492 exports._replaceModuleByName = replaceModuleByName
  493 function replaceModuleByName (obj, key, child) {
  494   var childName = moduleName(child)
  495   return replaceModule(obj, key, child, function (replacing, child) {
  496     return moduleName(replacing) === childName
  497   })
  498 }
  499 
  500 function replaceModule (obj, key, child, matchBy) {
  501   validate('OSOF', arguments)
  502   if (!obj[key]) obj[key] = []
  503   // we replace children with a new array object instead of mutating it
  504   // because mutating it results in weird failure states.
  505   // I would very much like to know _why_ this is. =/
  506   var children = [].concat(obj[key])
  507   for (var replaceAt = 0; replaceAt < children.length; ++replaceAt) {
  508     if (matchBy(children[replaceAt], child)) break
  509   }
  510   var replacing = children.splice(replaceAt, 1, child)
  511   obj[key] = children
  512   return replacing[0]
  513 }
  514 
  515 function resolveWithNewModule (pkg, tree, log, next) {
  516   validate('OOOF', arguments)
  517   if (pkg.type) {
  518     return fetchPackageMetadata(pkg, packageRelativePath(tree), log.newItem('fetchMetadata'), iferr(next, function (pkg) {
  519       resolveWithNewModule(pkg, tree, log, next)
  520     }))
  521   }
  522 
  523   if (!pkg._installable) {
  524     log.silly('resolveWithNewModule', packageId(pkg), 'checking installable status')
  525     return isInstallable(pkg, iferr(next, function () {
  526       pkg._installable = true
  527       resolveWithNewModule(pkg, tree, log, next)
  528     }))
  529   }
  530 
  531   if (!pkg._from) {
  532     pkg._from = pkg._requested.name + '@' + pkg._requested.spec
  533   }
  534   addShrinkwrap(pkg, iferr(next, function () {
  535     addBundled(pkg, iferr(next, function () {
  536       var parent = earliestInstallable(tree, tree, pkg) || tree
  537       var child = createChild({
  538         package: pkg,
  539         parent: parent,
  540         path: path.join(parent.path, 'node_modules', pkg.name),
  541         realpath: path.resolve(parent.realpath, 'node_modules', pkg.name),
  542         children: pkg._bundled || [],
  543         isLink: tree.isLink
  544       })
  545       delete pkg._bundled
  546       var hasBundled = child.children.length
  547 
  548       var replaced = replaceModuleByName(parent, 'children', child)
  549       if (replaced) removeObsoleteDep(replaced)
  550       addRequiredDep(tree, child, function () {
  551         child.location = flatNameFromTree(child)
  552 
  553         if (tree.parent && parent !== tree) updatePhantomChildren(tree.parent, child)
  554 
  555         if (hasBundled) {
  556           inflateBundled(child, child.children)
  557         }
  558 
  559         if (pkg._shrinkwrap && pkg._shrinkwrap.dependencies) {
  560           return inflateShrinkwrap(child, pkg._shrinkwrap.dependencies, function (er) {
  561             next(er, child, log)
  562           })
  563         }
  564 
  565         next(null, child, log)
  566       })
  567     }))
  568   }))
  569 }
  570 
  571 var validatePeerDeps = exports.validatePeerDeps = function (tree, onInvalid) {
  572   if (!tree.package.peerDependencies) return
  573   Object.keys(tree.package.peerDependencies).forEach(function (pkgname) {
  574     var version = tree.package.peerDependencies[pkgname]
  575     var match = findRequirement(tree.parent || tree, pkgname, npa(pkgname + '@' + version))
  576     if (!match) onInvalid(tree, pkgname, version)
  577   })
  578 }
  579 
  580 exports.validateAllPeerDeps = function (tree, onInvalid) {
  581   validateAllPeerDeps(tree, onInvalid, {})
  582 }
  583 
  584 function validateAllPeerDeps (tree, onInvalid, seen) {
  585   validate('OFO', arguments)
  586   if (seen[tree.path]) return
  587   seen[tree.path] = true
  588   validatePeerDeps(tree, onInvalid)
  589   tree.children.forEach(function (child) { validateAllPeerDeps(child, onInvalid, seen) })
  590 }
  591 
  592 // Determine if a module requirement is already met by the tree at or above
  593 // our current location in the tree.
  594 var findRequirement = exports.findRequirement = function (tree, name, requested, requestor) {
  595   validate('OSO', [tree, name, requested])
  596   if (!requestor) requestor = tree
  597   var nameMatch = function (child) {
  598     return moduleName(child) === name && child.parent && !child.removed
  599   }
  600   var versionMatch = function (child) {
  601     return doesChildVersionMatch(child, requested, requestor)
  602   }
  603   if (nameMatch(tree)) {
  604     // this *is* the module, but it doesn't match the version, so a
  605     // new copy will have to be installed
  606     return versionMatch(tree) ? tree : null
  607   }
  608 
  609   var matches = tree.children.filter(nameMatch)
  610   if (matches.length) {
  611     matches = matches.filter(versionMatch)
  612     // the module exists as a dependent, but the version doesn't match, so
  613     // a new copy will have to be installed above here
  614     if (matches.length) return matches[0]
  615     return null
  616   }
  617   if (tree.isTop) return null
  618   return findRequirement(tree.parent, name, requested, requestor)
  619 }
  620 
  621 // Find the highest level in the tree that we can install this module in.
  622 // If the module isn't installed above us yet, that'd be the very top.
  623 // If it is, then it's the level below where its installed.
  624 var earliestInstallable = exports.earliestInstallable = function (requiredBy, tree, pkg) {
  625   validate('OOO', arguments)
  626 
  627   function undeletedModuleMatches (child) {
  628     return !child.removed && moduleName(child) === pkg.name
  629   }
  630   if (tree.children.some(undeletedModuleMatches)) return null
  631 
  632   // If any of the children of this tree have conflicting
  633   // binaries then we need to decline to install this package here.
  634   var binaryMatches = typeof pkg.bin === 'object' && tree.children.some(function (child) {
  635     if (child.removed) return false
  636     if (typeof child.package.bin !== 'object') return false
  637     return Object.keys(child.package.bin).some(function (bin) {
  638       return pkg.bin[bin]
  639     })
  640   })
  641   if (binaryMatches) return null
  642 
  643   // if this tree location requested the same module then we KNOW it
  644   // isn't compatible because if it were findRequirement would have
  645   // found that version.
  646   var deps = tree.package.dependencies || {}
  647   if (!tree.removed && requiredBy !== tree && deps[pkg.name]) {
  648     return null
  649   }
  650 
  651   if (tree.phantomChildren && tree.phantomChildren[pkg.name]) return null
  652 
  653   if (tree.isTop) return tree
  654   if (tree.isGlobal) return tree
  655 
  656   if (npm.config.get('global-style') && tree.parent.isTop) return tree
  657   if (npm.config.get('legacy-bundling')) return tree
  658 
  659   return (earliestInstallable(requiredBy, tree.parent, pkg) || tree)
  660 }