deps/npm/lib/dedupe.js

   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.
   5 //
   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.
   9
  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 archy = require("archy")
  15 var util = require("util")
  16 var RegClient = require("npm-registry-client")
  17 var npmconf = require("npmconf")
  18 var semver = require("semver")
  19 var rimraf = require("rimraf")
  20 var log = require("npmlog")
  21 var npm = require("./npm.js")
  22
  23 module.exports = dedupe
  24
  25 dedupe.usage = "npm dedupe [pkg pkg...]"
  26
  27 function dedupe (args, silent, cb) {
  28   if (typeof silent === "function") cb = silent, silent = false
  29   var dryrun = false
  30   if (npm.command.match(/^find/)) dryrun = true
  31   return dedupe_(npm.prefix, args, {}, dryrun, silent, cb)
  32 }
  33
  34 function dedupe_ (dir, filter, unavoidable, dryrun, silent, cb) {
  35   readInstalled(path.resolve(dir), {}, null, function (er, data, counter) {
  36     if (er) {
  37       return cb(er)
  38     }
  39
  40     if (!data) {
  41       return cb()
  42     }
  43
  44     // find out which things are dupes
  45     var dupes = Object.keys(counter || {}).filter(function (k) {
  46       if (filter.length && -1 === filter.indexOf(k)) return false
  47       return counter[k] > 1 && !unavoidable[k]
  48     }).reduce(function (s, k) {
  49       s[k] = []
  50       return s
  51     }, {})
  52
  53     // any that are unavoidable need to remain as they are.  don't even
  54     // try to touch them or figure it out.  Maybe some day, we can do
  55     // something a bit more clever here, but for now, just skip over it,
  56     // and all its children.
  57     ;(function U (obj) {
  58       if (unavoidable[obj.name]) {
  59         obj.unavoidable = true
  60       }
  61       if (obj.parent && obj.parent.unavoidable) {
  62         obj.unavoidable = true
  63       }
  64       Object.keys(obj.children).forEach(function (k) {
  65         U(obj.children[k])
  66       })
  67     })
  68
  69     // then collect them up and figure out who needs them
  70     ;(function C (obj) {
  71       if (dupes[obj.name] && !obj.unavoidable) {
  72         dupes[obj.name].push(obj)
  73         obj.duplicate = true
  74       }
  75       obj.dependents = whoDepends(obj)
  76       Object.keys(obj.children).forEach(function (k) {
  77         C(obj.children[k])
  78       })
  79     })(data)
  80
  81     if (dryrun) {
  82       var k = Object.keys(dupes)
  83       if (!k.length) return cb()
  84       return npm.commands.ls(k, silent, cb)
  85     }
  86
  87     var summary = Object.keys(dupes).map(function (n) {
  88       return [n, dupes[n].filter(function (d) {
  89         return d && d.parent && !d.parent.duplicate && !d.unavoidable
  90       }).map(function M (d) {
  91         return [d.path, d.version, d.dependents.map(function (k) {
  92           return [k.path, k.version, k.dependencies[d.name] || ""]
  93         })]
  94       })]
  95     }).map(function (item) {
  96       var name = item[0]
  97       var set = item[1]
  98
  99       var ranges = set.map(function (i) {
 100         return i[2].map(function (d) {
 101           return d[2]
 102         })
 103       }).reduce(function (l, r) {
 104         return l.concat(r)
 105       }, []).map(function (v, i, set) {
 106         if (set.indexOf(v) !== i) return false
 107         return v
 108       }).filter(function (v) {
 109         return v !== false
 110       })
 111
 112       var locs = set.map(function (i) {
 113         return i[0]
 114       })
 115
 116       var versions = set.map(function (i) {
 117         return i[1]
 118       }).filter(function (v, i, set) {
 119         return set.indexOf(v) === i
 120       })
 121
 122       var has = set.map(function (i) {
 123         return [i[0], i[1]]
 124       }).reduce(function (set, kv) {
 125         set[kv[0]] = kv[1]
 126         return set
 127       }, {})
 128
 129       var loc = locs.length ? locs.reduce(function (a, b) {
 130         // a=/path/to/node_modules/foo/node_modules/bar
 131         // b=/path/to/node_modules/elk/node_modules/bar
 132         // ==/path/to/node_modules/bar
 133         var nmReg = new RegExp("\\" + path.sep + "node_modules\\" + path.sep)
 134         a = a.split(nmReg)
 135         b = b.split(nmReg)
 136         var name = a.pop()
 137         b.pop()
 138         // find the longest chain that both A and B share.
 139         // then push the name back on it, and join by /node_modules/
 140         var res = []
 141         for (var i = 0, al = a.length, bl = b.length; i < al && i < bl && a[i] === b[i]; i++);
 142         return a.slice(0, i).concat(name).join(path.sep + "node_modules" + path.sep)
 143       }) : undefined
 144
 145       return [item[0], { item: item
 146                        , ranges: ranges
 147                        , locs: locs
 148                        , loc: loc
 149                        , has: has
 150                        , versions: versions
 151                        }]
 152     }).filter(function (i) {
 153       return i[1].loc
 154     })
 155
 156     findVersions(npm, summary, function (er, set) {
 157       if (er) return cb(er)
 158       if (!set.length) return cb()
 159       installAndRetest(set, filter, dir, unavoidable, silent, cb)
 160     })
 161   })
 162 }
 163
 164 function installAndRetest (set, filter, dir, unavoidable, silent, cb) {
 165   //return cb(null, set)
 166   var remove = []
 167
 168   asyncMap(set, function (item, cb) {
 169     // [name, has, loc, locMatch, regMatch, others]
 170     var name = item[0]
 171     var has = item[1]
 172     var where = item[2]
 173     var locMatch = item[3]
 174     var regMatch = item[4]
 175     var others = item[5]
 176
 177     // nothing to be done here.  oh well.  just a conflict.
 178     if (!locMatch && !regMatch) {
 179       log.warn("unavoidable conflict", item[0], item[1])
 180       log.warn("unavoidable conflict", "Not de-duplicating")
 181       unavoidable[item[0]] = true
 182       return cb()
 183     }
 184
 185     // nothing to do except to clean up the extraneous deps
 186     if (locMatch && has[where] === locMatch) {
 187       remove.push.apply(remove, others)
 188       return cb()
 189     }
 190
 191     if (regMatch) {
 192       var what = name + "@" + regMatch
 193       // where is /path/to/node_modules/foo/node_modules/bar
 194       // for package "bar", but we need it to be just
 195       // /path/to/node_modules/foo
 196       var nmReg = new RegExp("\\" + path.sep + "node_modules\\" + path.sep)
 197       where = where.split(nmReg)
 198       where.pop()
 199       where = where.join(path.sep + "node_modules" + path.sep)
 200       remove.push.apply(remove, others)
 201
 202       return npm.commands.install(where, what, cb)
 203     }
 204
 205     // hrm?
 206     return cb(new Error("danger zone\n" + name + " " +
 207                         + regMatch + " " + locMatch))
 208
 209   }, function (er, installed) {
 210     if (er) return cb(er)
 211     asyncMap(remove, rimraf, function (er) {
 212       if (er) return cb(er)
 213       remove.forEach(function (r) {
 214         log.info("rm", r)
 215       })
 216       dedupe_(dir, filter, unavoidable, false, silent, cb)
 217     })
 218   })
 219 }
 220
 221 function findVersions (npm, summary, cb) {
 222   // now, for each item in the summary, try to find the maximum version
 223   // that will satisfy all the ranges.  next step is to install it at
 224   // the specified location.
 225   asyncMap(summary, function (item, cb) {
 226     var name = item[0]
 227     var data = item[1]
 228     var loc = data.loc
 229     var locs = data.locs.filter(function (l) {
 230       return l !== loc
 231     })
 232
 233     // not actually a dupe, or perhaps all the other copies were
 234     // children of a dupe, so this'll maybe be picked up later.
 235     if (locs.length === 0) {
 236       return cb(null, [])
 237     }
 238
 239     // { <folder>: <version> }
 240     var has = data.has
 241
 242     // the versions that we already have.
 243     // if one of these is ok, then prefer to use that.
 244     // otherwise, try fetching from the registry.
 245     var versions = data.versions
 246
 247     var ranges = data.ranges
 248     npm.registry.get(name, function (er, data) {
 249       var regVersions = er ? [] : Object.keys(data.versions)
 250       var locMatch = bestMatch(versions, ranges)
 251       var regMatch;
 252       var tag = npm.config.get("tag");
 253       var distTags = data["dist-tags"];
 254       if (distTags && distTags[tag] && data.versions[distTags[tag]]) {
 255         regMatch = distTags[tag]
 256       } else {
 257         regMatch = bestMatch(regVersions, ranges)
 258       }
 259
 260       cb(null, [[name, has, loc, locMatch, regMatch, locs]])
 261     })
 262   }, cb)
 263 }
 264
 265 function bestMatch (versions, ranges) {
 266   return versions.filter(function (v) {
 267     return !ranges.some(function (r) {
 268       return !semver.satisfies(v, r, true)
 269     })
 270   }).sort(semver.compareLoose).pop()
 271 }
 272
 273
 274 function readInstalled (dir, counter, parent, cb) {
 275   var pkg, children, realpath
 276
 277   fs.realpath(dir, function (er, rp) {
 278     realpath = rp
 279     next()
 280   })
 281
 282   readJson(path.resolve(dir, "package.json"), function (er, data) {
 283     if (er && er.code !== "ENOENT" && er.code !== "ENOTDIR") return cb(er)
 284     if (er) return cb() // not a package, probably.
 285     counter[data.name] = counter[data.name] || 0
 286     counter[data.name]++
 287     pkg =
 288       { _id: data._id
 289       , name: data.name
 290       , version: data.version
 291       , dependencies: data.dependencies || {}
 292       , optionalDependencies: data.optionalDependencies || {}
 293       , devDependencies: data.devDependencies || {}
 294       , bundledDependencies: data.bundledDependencies || []
 295       , path: dir
 296       , realPath: dir
 297       , children: {}
 298       , parent: parent
 299       , family: Object.create(parent ? parent.family : null)
 300       , unavoidable: false
 301       , duplicate: false
 302       }
 303     if (parent) {
 304       parent.children[data.name] = pkg
 305       parent.family[data.name] = pkg
 306     }
 307     next()
 308   })
 309
 310   fs.readdir(path.resolve(dir, "node_modules"), function (er, c) {
 311     children = c || [] // error is ok, just means no children.
 312     children = children.filter(function (p) {
 313       return !p.match(/^[\._-]/)
 314     })
 315     next()
 316   })
 317
 318   function next () {
 319     if (!children || !pkg || !realpath) return
 320
 321     // ignore devDependencies.  Just leave them where they are.
 322     children = children.filter(function (c) {
 323       return !pkg.devDependencies.hasOwnProperty(c)
 324     })
 325
 326     pkg.realPath = realpath
 327     if (pkg.realPath !== pkg.path) children = []
 328     var d = path.resolve(dir, "node_modules")
 329     asyncMap(children, function (child, cb) {
 330       readInstalled(path.resolve(d, child), counter, pkg, cb)
 331     }, function (er) {
 332       cb(er, pkg, counter)
 333     })
 334   }
 335 }
 336
 337 function whoDepends (pkg) {
 338   var start = pkg.parent || pkg
 339   return whoDepends_(pkg, [], start)
 340 }
 341
 342 function whoDepends_ (pkg, who, test) {
 343   if (test !== pkg &&
 344       test.dependencies[pkg.name] &&
 345       test.family[pkg.name] === pkg) {
 346     who.push(test)
 347   }
 348   Object.keys(test.children).forEach(function (n) {
 349     whoDepends_(pkg, who, test.children[n])
 350   })
 351   return who
 352 }
 353