1 // traverse the node_modules/package.json tree
2 // looking for duplicates. If any duplicates are found,
3 // then move them up to the highest level necessary
4 // in order to make them no longer duplicated.
6 // This is kind of ugly, and really highlights the need for
7 // much better "put pkg X at folder Y" abstraction. Oh well,
8 // whatever. Perfect enemy of the good, and all that.
10 var fs = require("fs")
11 var asyncMap = require("slide").asyncMap
12 var path = require("path")
13 var readJson = require("read-package-json")
14 var semver = require("semver")
15 var rm = require("./utils/gently-rm.js")
16 var log = require("npmlog")
17 var npm = require("./npm.js")
18 var mapToRegistry = require("./utils/map-to-registry.js")
20 module.exports = dedupe
22 dedupe.usage = "npm dedupe [pkg pkg...]"
24 function dedupe (args, silent, cb) {
25 if (typeof silent === "function") cb = silent, silent = false
27 if (npm.command.match(/^find/)) dryrun = true
28 return dedupe_(npm.prefix, args, {}, dryrun, silent, cb)
31 function dedupe_ (dir, filter, unavoidable, dryrun, silent, cb) {
32 readInstalled(path.resolve(dir), {}, null, function (er, data, counter) {
41 // find out which things are dupes
42 var dupes = Object.keys(counter || {}).filter(function (k) {
43 if (filter.length && -1 === filter.indexOf(k)) return false
44 return counter[k] > 1 && !unavoidable[k]
45 }).reduce(function (s, k) {
50 // any that are unavoidable need to remain as they are. don't even
51 // try to touch them or figure it out. Maybe some day, we can do
52 // something a bit more clever here, but for now, just skip over it,
53 // and all its children.
55 if (unavoidable[obj.name]) {
56 obj.unavoidable = true
58 if (obj.parent && obj.parent.unavoidable) {
59 obj.unavoidable = true
61 Object.keys(obj.children).forEach(function (k) {
66 // then collect them up and figure out who needs them
68 if (dupes[obj.name] && !obj.unavoidable) {
69 dupes[obj.name].push(obj)
72 obj.dependents = whoDepends(obj)
73 Object.keys(obj.children).forEach(function (k) {
79 var k = Object.keys(dupes)
80 if (!k.length) return cb()
81 return npm.commands.ls(k, silent, cb)
84 var summary = Object.keys(dupes).map(function (n) {
85 return [n, dupes[n].filter(function (d) {
86 return d && d.parent && !d.parent.duplicate && !d.unavoidable
87 }).map(function M (d) {
88 return [d.path, d.version, d.dependents.map(function (k) {
89 return [k.path, k.version, k.dependencies[d.name] || ""]
92 }).map(function (item) {
95 var ranges = set.map(function (i) {
96 return i[2].map(function (d) {
99 }).reduce(function (l, r) {
101 }, []).map(function (v, i, set) {
102 if (set.indexOf(v) !== i) return false
104 }).filter(function (v) {
108 var locs = set.map(function (i) {
112 var versions = set.map(function (i) {
114 }).filter(function (v, i, set) {
115 return set.indexOf(v) === i
118 var has = set.map(function (i) {
120 }).reduce(function (set, kv) {
125 var loc = locs.length ? locs.reduce(function (a, b) {
126 // a=/path/to/node_modules/foo/node_modules/bar
127 // b=/path/to/node_modules/elk/node_modules/bar
128 // ==/path/to/node_modules/bar
129 var nmReg = new RegExp("\\" + path.sep + "node_modules\\" + path.sep)
134 // find the longest chain that both A and B share.
135 // then push the name back on it, and join by /node_modules/
136 for (var i = 0, al = a.length, bl = b.length; i < al && i < bl && a[i] === b[i]; i++);
137 return a.slice(0, i).concat(name).join(path.sep + "node_modules" + path.sep)
140 return [item[0], { item: item
147 }).filter(function (i) {
151 findVersions(npm, summary, function (er, set) {
152 if (er) return cb(er)
153 if (!set.length) return cb()
154 installAndRetest(set, filter, dir, unavoidable, silent, cb)
159 function installAndRetest (set, filter, dir, unavoidable, silent, cb) {
160 //return cb(null, set)
163 asyncMap(set, function (item, cb) {
164 // [name, has, loc, locMatch, regMatch, others]
168 var locMatch = item[3]
169 var regMatch = item[4]
172 // nothing to be done here. oh well. just a conflict.
173 if (!locMatch && !regMatch) {
174 log.warn("unavoidable conflict", item[0], item[1])
175 log.warn("unavoidable conflict", "Not de-duplicating")
176 unavoidable[item[0]] = true
180 // nothing to do except to clean up the extraneous deps
181 if (locMatch && has[where] === locMatch) {
182 remove.push.apply(remove, others)
187 var what = name + "@" + regMatch
188 // where is /path/to/node_modules/foo/node_modules/bar
189 // for package "bar", but we need it to be just
190 // /path/to/node_modules/foo
191 var nmReg = new RegExp("\\" + path.sep + "node_modules\\" + path.sep)
192 where = where.split(nmReg)
194 where = where.join(path.sep + "node_modules" + path.sep)
195 remove.push.apply(remove, others)
197 return npm.commands.install(where, what, cb)
201 return cb(new Error("danger zone\n" + name + " " +
202 regMatch + " " + locMatch))
205 if (er) return cb(er)
206 asyncMap(remove, rm, function (er) {
207 if (er) return cb(er)
208 remove.forEach(function (r) {
211 dedupe_(dir, filter, unavoidable, false, silent, cb)
216 function findVersions (npm, summary, cb) {
217 // now, for each item in the summary, try to find the maximum version
218 // that will satisfy all the ranges. next step is to install it at
219 // the specified location.
220 asyncMap(summary, function (item, cb) {
224 var locs = data.locs.filter(function (l) {
228 // not actually a dupe, or perhaps all the other copies were
229 // children of a dupe, so this'll maybe be picked up later.
230 if (locs.length === 0) {
234 // { <folder>: <version> }
237 // the versions that we already have.
238 // if one of these is ok, then prefer to use that.
239 // otherwise, try fetching from the registry.
240 var versions = data.versions
242 var ranges = data.ranges
243 mapToRegistry(name, npm.config, function (er, uri, auth) {
244 if (er) return cb(er)
246 npm.registry.get(uri, { auth : auth }, next)
249 function next (er, data) {
250 var regVersions = er ? [] : Object.keys(data.versions)
251 var locMatch = bestMatch(versions, ranges)
252 var tag = npm.config.get("tag")
253 var distTag = data["dist-tags"] && data["dist-tags"][tag]
256 if (distTag && data.versions[distTag] && matches(distTag, ranges)) {
259 regMatch = bestMatch(regVersions, ranges)
262 cb(null, [[name, has, loc, locMatch, regMatch, locs]])
267 function matches (version, ranges) {
268 return !ranges.some(function (r) {
269 return !semver.satisfies(version, r, true)
273 function bestMatch (versions, ranges) {
274 return versions.filter(function (v) {
275 return matches(v, ranges)
276 }).sort(semver.compareLoose).pop()
280 function readInstalled (dir, counter, parent, cb) {
281 var pkg, children, realpath
283 fs.realpath(dir, function (er, rp) {
288 readJson(path.resolve(dir, "package.json"), function (er, data) {
289 if (er && er.code !== "ENOENT" && er.code !== "ENOTDIR") return cb(er)
290 if (er) return cb() // not a package, probably.
291 counter[data.name] = counter[data.name] || 0
296 , version: data.version
297 , dependencies: data.dependencies || {}
298 , optionalDependencies: data.optionalDependencies || {}
299 , devDependencies: data.devDependencies || {}
300 , bundledDependencies: data.bundledDependencies || []
305 , family: Object.create(parent ? parent.family : null)
310 parent.children[data.name] = pkg
311 parent.family[data.name] = pkg
316 fs.readdir(path.resolve(dir, "node_modules"), function (er, c) {
317 children = children || [] // error is ok, just means no children.
318 // check if there are scoped packages.
319 asyncMap(c || [], function (child, cb) {
320 if (child.indexOf('@') === 0) {
321 fs.readdir(path.resolve(dir, "node_modules", child), function (er, scopedChildren) {
322 // error is ok, just means no children.
323 (scopedChildren || []).forEach(function (sc) {
324 children.push(path.join(child, sc))
333 if (er) return cb(er)
334 children = children.filter(function (p) {
335 return !p.match(/^[\._-]/)
342 if (!children || !pkg || !realpath) return
344 // ignore devDependencies. Just leave them where they are.
345 children = children.filter(function (c) {
346 return !pkg.devDependencies.hasOwnProperty(c)
349 pkg.realPath = realpath
350 if (pkg.realPath !== pkg.path) children = []
351 var d = path.resolve(dir, "node_modules")
352 asyncMap(children, function (child, cb) {
353 readInstalled(path.resolve(d, child), counter, pkg, cb)
360 function whoDepends (pkg) {
361 var start = pkg.parent || pkg
362 return whoDepends_(pkg, [], start)
365 function whoDepends_ (pkg, who, test) {
367 test.dependencies[pkg.name] &&
368 test.family[pkg.name] === pkg) {
371 Object.keys(test.children).forEach(function (n) {
372 whoDepends_(pkg, who, test.children[n])