--- /dev/null
+
+// Walk through the file-system "database" of installed
+// packages, and create a data object related to the
+// installed versions of each package.
+
+/*
+This will traverse through all node_modules folders,
+resolving the dependencies object to the object corresponding to
+the package that meets that dep, or just the version/range if
+unmet.
+
+Assuming that you had this folder structure:
+
+/path/to
++-- package.json { name = "root" }
+`-- node_modules
+ +-- foo {bar, baz, asdf}
+ | +-- node_modules
+ | +-- bar { baz }
+ | `-- baz
+ `-- asdf
+
+where "foo" depends on bar, baz, and asdf, bar depends on baz,
+and bar and baz are bundled with foo, whereas "asdf" is at
+the higher level (sibling to foo), you'd get this object structure:
+
+{ <package.json data>
+, path: "/path/to"
+, parent: null
+, dependencies:
+ { foo :
+ { version: "1.2.3"
+ , path: "/path/to/node_modules/foo"
+ , parent: <Circular: root>
+ , dependencies:
+ { bar:
+ { parent: <Circular: foo>
+ , path: "/path/to/node_modules/foo/node_modules/bar"
+ , version: "2.3.4"
+ , dependencies: { baz: <Circular: foo.dependencies.baz> }
+ }
+ , baz: { ... }
+ , asdf: <Circular: asdf>
+ }
+ }
+ , asdf: { ... }
+ }
+}
+
+Unmet deps are left as strings.
+Extraneous deps are marked with extraneous:true
+deps that don't meet a requirement are marked with invalid:true
+deps that don't meet a peer requirement are marked with peerInvalid:true
+
+to READ(packagefolder, parentobj, name, reqver)
+obj = read package.json
+installed = ./node_modules/*
+if parentobj is null, and no package.json
+ obj = {dependencies:{<installed>:ANY}}
+deps = Object.keys(obj.dependencies)
+obj.path = packagefolder
+obj.parent = parentobj
+if name, && obj.name !== name, obj.invalid = true
+if reqver, && obj.version !satisfies reqver, obj.invalid = true
+if !reqver && parentobj, obj.extraneous = true
+for each folder in installed
+ obj.dependencies[folder] = READ(packagefolder+node_modules+folder,
+ obj, folder, obj.dependencies[folder])
+# walk tree to find unmet deps
+for each dep in obj.dependencies not in installed
+ r = obj.parent
+ while r
+ if r.dependencies[dep]
+ if r.dependencies[dep].verion !satisfies obj.dependencies[dep]
+ WARN
+ r.dependencies[dep].invalid = true
+ obj.dependencies[dep] = r.dependencies[dep]
+ r = null
+ else r = r.parent
+return obj
+
+
+TODO:
+1. Find unmet deps in parent directories, searching as node does up
+as far as the left-most node_modules folder.
+2. Ignore anything in node_modules that isn't a package folder.
+
+*/
+
+try {
+ var fs = require("graceful-fs")
+} catch (er) {
+ var fs = require("fs")
+}
+
+var path = require("path")
+var asyncMap = require("slide").asyncMap
+var semver = require("semver")
+var readJson = require("read-package-json")
+var url = require("url")
+var util = require("util")
+var extend = require("util-extend")
+
+var debug = require("debuglog")("read-installed")
+
+var readdir = require("readdir-scoped-modules")
+
+// Sentinel catch-all version constraint used when a dependency is not
+// listed in the package.json file.
+var ANY = {}
+
+module.exports = readInstalled
+
+function readInstalled (folder, opts, cb) {
+ if (typeof opts === 'function') {
+ cb = opts
+ opts = {}
+ } else {
+ opts = extend({}, opts)
+ }
+
+ if (typeof opts.depth !== 'number')
+ opts.depth = Infinity
+
+ opts.depth = Math.max(0, opts.depth)
+
+ if (typeof opts.log !== 'function')
+ opts.log = function () {}
+
+ opts.dev = !!opts.dev
+ opts.realpathSeen = {}
+ opts.findUnmetSeen = []
+
+
+ readInstalled_(folder, null, null, null, 0, opts, function (er, obj) {
+ if (er) return cb(er)
+ // now obj has all the installed things, where they're installed
+ // figure out the inheritance links, now that the object is built.
+ resolveInheritance(obj, opts)
+ obj.root = true
+ unmarkExtraneous(obj, opts)
+ cb(null, obj)
+ })
+}
+
+function readInstalled_ (folder, parent, name, reqver, depth, opts, cb) {
+ var installed
+ , obj
+ , real
+ , link
+ , realpathSeen = opts.realpathSeen
+
+ readdir(path.resolve(folder, "node_modules"), function (er, i) {
+ // error indicates that nothing is installed here
+ if (er) i = []
+ installed = i.filter(function (f) { return f.charAt(0) !== "." })
+ next()
+ })
+
+ readJson(path.resolve(folder, "package.json"), function (er, data) {
+ obj = copy(data)
+
+ if (!parent) {
+ obj = obj || true
+ er = null
+ }
+ return next(er)
+ })
+
+ fs.lstat(folder, function (er, st) {
+ if (er) {
+ if (!parent) real = true
+ return next(er)
+ }
+ fs.realpath(folder, function (er, rp) {
+ debug("realpath(%j) = %j", folder, rp)
+ real = rp
+ if (st.isSymbolicLink()) link = rp
+ next(er)
+ })
+ })
+
+ var errState = null
+ , called = false
+ function next (er) {
+ if (errState) return
+ if (er) {
+ errState = er
+ return cb(null, [])
+ }
+ debug('next', installed, obj && typeof obj, name, real)
+ if (!installed || !obj || !real || called) return
+ called = true
+ if (realpathSeen[real]) return cb(null, realpathSeen[real])
+ if (obj === true) {
+ obj = {dependencies:{}, path:folder}
+ installed.forEach(function (i) { obj.dependencies[i] = ANY })
+ }
+ if (name && obj.name !== name) obj.invalid = true
+ obj.realName = name || obj.name
+ obj.dependencies = obj.dependencies || {}
+
+ // At this point, figure out what dependencies we NEED to get met
+ obj._dependencies = copy(obj.dependencies)
+
+ if (reqver === ANY) {
+ // We were unable to determine the required version of this
+ // dependency from the package.json file, but we now know its actual
+ // version, so treat that version as the required version to avoid
+ // marking the dependency as invalid below. See #40.
+ reqver = obj.version;
+ }
+
+ // "foo":"http://blah" and "foo":"latest" are always presumed valid
+ if (reqver
+ && semver.validRange(reqver, true)
+ && !semver.satisfies(obj.version, reqver, true)) {
+ obj.invalid = true
+ }
+
+ // Mark as extraneous at this point.
+ // This will be un-marked in unmarkExtraneous, where we mark as
+ // not-extraneous everything that is required in some way from
+ // the root object.
+ obj.extraneous = true
+
+ obj.path = obj.path || folder
+ obj.realPath = real
+ obj.link = link
+ if (parent && !obj.link) obj.parent = parent
+ realpathSeen[real] = obj
+ obj.depth = depth
+ //if (depth >= opts.depth) return cb(null, obj)
+ asyncMap(installed, function (pkg, cb) {
+ var rv = obj.dependencies[pkg]
+ if (!rv && obj.devDependencies && opts.dev)
+ rv = obj.devDependencies[pkg]
+
+ if (depth > opts.depth) {
+ obj.dependencies = {}
+ return cb(null, obj)
+ }
+
+ readInstalled_( path.resolve(folder, "node_modules/"+pkg)
+ , obj, pkg, obj.dependencies[pkg], depth + 1, opts
+ , cb )
+
+ }, function (er, installedData) {
+ if (er) return cb(er)
+ installedData.forEach(function (dep) {
+ obj.dependencies[dep.realName] = dep
+ })
+
+ // any strings here are unmet things. however, if it's
+ // optional, then that's fine, so just delete it.
+ if (obj.optionalDependencies) {
+ Object.keys(obj.optionalDependencies).forEach(function (dep) {
+ if (typeof obj.dependencies[dep] === "string") {
+ delete obj.dependencies[dep]
+ }
+ })
+ }
+ return cb(null, obj)
+ })
+ }
+}
+
+// starting from a root object, call findUnmet on each layer of children
+var riSeen = []
+function resolveInheritance (obj, opts) {
+ if (typeof obj !== "object") return
+ if (riSeen.indexOf(obj) !== -1) return
+ riSeen.push(obj)
+ if (typeof obj.dependencies !== "object") {
+ obj.dependencies = {}
+ }
+ Object.keys(obj.dependencies).forEach(function (dep) {
+ findUnmet(obj.dependencies[dep], opts)
+ })
+ Object.keys(obj.dependencies).forEach(function (dep) {
+ if (typeof obj.dependencies[dep] === "object") {
+ resolveInheritance(obj.dependencies[dep], opts)
+ } else {
+ debug("unmet dep! %s %s@%s", obj.name, dep, obj.dependencies[dep])
+ }
+ })
+ findUnmet(obj, opts)
+}
+
+// find unmet deps by walking up the tree object.
+// No I/O
+function findUnmet (obj, opts) {
+ var findUnmetSeen = opts.findUnmetSeen
+ if (findUnmetSeen.indexOf(obj) !== -1) return
+ findUnmetSeen.push(obj)
+ debug("find unmet parent=%s obj=", obj.parent && obj.parent.name, obj.name || obj)
+ var deps = obj.dependencies = obj.dependencies || {}
+
+ debug(deps)
+ Object.keys(deps)
+ .filter(function (d) { return typeof deps[d] === "string" })
+ .forEach(function (d) {
+ var found = findDep(obj, d)
+ debug("finding dep %j", d, found && found.name || found)
+ // "foo":"http://blah" and "foo":"latest" are always presumed valid
+ if (typeof deps[d] === "string" &&
+ semver.validRange(deps[d], true) &&
+ found &&
+ !semver.satisfies(found.version, deps[d], true)) {
+ // the bad thing will happen
+ opts.log( "unmet dependency"
+ , obj.path + " requires "+d+"@'"+deps[d]
+ + "' but will load\n"
+ + found.path+",\nwhich is version "+found.version )
+ found.invalid = true
+ }
+ if (found) {
+ deps[d] = found
+ }
+ })
+
+ var peerDeps = obj.peerDependencies = obj.peerDependencies || {}
+ Object.keys(peerDeps).forEach(function (d) {
+ var dependency
+
+ if (!obj.parent) {
+ dependency = obj.dependencies[d]
+
+ // read it as a missing dep
+ if (!dependency) {
+ obj.dependencies[d] = peerDeps[d]
+ }
+ } else {
+ var r = obj.parent
+ while (r && !dependency) {
+ dependency = r.dependencies && r.dependencies[d]
+ r = r.link ? null : r.parent
+ }
+ }
+
+ if (!dependency) {
+ // mark as a missing dep!
+ obj.dependencies[d] = peerDeps[d]
+ } else if (!semver.satisfies(dependency.version, peerDeps[d], true)) {
+ dependency.peerInvalid = true
+ }
+ })
+
+ return obj
+}
+
+function unmarkExtraneous (obj, opts) {
+ // Mark all non-required deps as extraneous.
+ // start from the root object and mark as non-extraneous all modules
+ // that haven't been previously flagged as extraneous then propagate
+ // to all their dependencies
+
+ obj.extraneous = false
+
+ var deps = obj._dependencies || []
+ if (opts.dev && obj.devDependencies && (obj.root || obj.link)) {
+ Object.keys(obj.devDependencies).forEach(function (k) {
+ deps[k] = obj.devDependencies[k]
+ })
+ }
+
+ if (obj.peerDependencies) {
+ Object.keys(obj.peerDependencies).forEach(function (k) {
+ deps[k] = obj.peerDependencies[k]
+ })
+ }
+
+ debug("not extraneous", obj._id, deps)
+ Object.keys(deps).forEach(function (d) {
+ var dep = findDep(obj, d)
+ if (dep && dep.extraneous) {
+ unmarkExtraneous(dep, opts)
+ }
+ })
+}
+
+// Find the one that will actually be loaded by require()
+// so we can make sure it's valid etc.
+function findDep (obj, d) {
+ var r = obj
+ , found = null
+ while (r && !found) {
+ // if r is a valid choice, then use that.
+ // kinda weird if a pkg depends on itself, but after the first
+ // iteration of this loop, it indicates a dep cycle.
+ if (typeof r.dependencies[d] === "object") {
+ found = r.dependencies[d]
+ }
+ if (!found && r.realName === d) found = r
+ r = r.link ? null : r.parent
+ }
+ return found
+}
+
+function copy (obj) {
+ if (!obj || typeof obj !== 'object') return obj
+ if (Array.isArray(obj)) return obj.map(copy)
+
+ var o = {}
+ for (var i in obj) o[i] = copy(obj[i])
+ return o
+}