org.simantics.maps.server/node/node-v4.8.0-win-x64/node_modules/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 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")
  19
  20 module.exports = dedupe
  21
  22 dedupe.usage = "npm dedupe [pkg pkg...]"
  23
  24 function dedupe (args, silent, cb) {
  25   if (typeof silent === "function") cb = silent, silent = false
  26   var dryrun = false
  27   if (npm.command.match(/^find/)) dryrun = true
  28   return dedupe_(npm.prefix, args, {}, dryrun, silent, cb)
  29 }
  30
  31 function dedupe_ (dir, filter, unavoidable, dryrun, silent, cb) {
  32   readInstalled(path.resolve(dir), {}, null, function (er, data, counter) {
  33     if (er) {
  34       return cb(er)
  35     }
  36
  37     if (!data) {
  38       return cb()
  39     }
  40
  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) {
  46       s[k] = []
  47       return s
  48     }, {})
  49
  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.
  54     ;(function U (obj) {
  55       if (unavoidable[obj.name]) {
  56         obj.unavoidable = true
  57       }
  58       if (obj.parent && obj.parent.unavoidable) {
  59         obj.unavoidable = true
  60       }
  61       Object.keys(obj.children).forEach(function (k) {
  62         U(obj.children[k])
  63       })
  64     })(data)
  65
  66     // then collect them up and figure out who needs them
  67     ;(function C (obj) {
  68       if (dupes[obj.name] && !obj.unavoidable) {
  69         dupes[obj.name].push(obj)
  70         obj.duplicate = true
  71       }
  72       obj.dependents = whoDepends(obj)
  73       Object.keys(obj.children).forEach(function (k) {
  74         C(obj.children[k])
  75       })
  76     })(data)
  77
  78     if (dryrun) {
  79       var k = Object.keys(dupes)
  80       if (!k.length) return cb()
  81       return npm.commands.ls(k, silent, cb)
  82     }
  83
  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] || ""]
  90         })]
  91       })]
  92     }).map(function (item) {
  93       var set = item[1]
  94
  95       var ranges = set.map(function (i) {
  96         return i[2].map(function (d) {
  97           return d[2]
  98         })
  99       }).reduce(function (l, r) {
 100         return l.concat(r)
 101       }, []).map(function (v, i, set) {
 102         if (set.indexOf(v) !== i) return false
 103         return v
 104       }).filter(function (v) {
 105         return v !== false
 106       })
 107
 108       var locs = set.map(function (i) {
 109         return i[0]
 110       })
 111
 112       var versions = set.map(function (i) {
 113         return i[1]
 114       }).filter(function (v, i, set) {
 115         return set.indexOf(v) === i
 116       })
 117
 118       var has = set.map(function (i) {
 119         return [i[0], i[1]]
 120       }).reduce(function (set, kv) {
 121         set[kv[0]] = kv[1]
 122         return set
 123       }, {})
 124
 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)
 130         a = a.split(nmReg)
 131         b = b.split(nmReg)
 132         var name = a.pop()
 133         b.pop()
 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)
 138       }) : undefined
 139
 140       return [item[0], { item: item
 141                        , ranges: ranges
 142                        , locs: locs
 143                        , loc: loc
 144                        , has: has
 145                        , versions: versions
 146                        }]
 147     }).filter(function (i) {
 148       return i[1].loc
 149     })
 150
 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)
 155     })
 156   })
 157 }
 158
 159 function installAndRetest (set, filter, dir, unavoidable, silent, cb) {
 160   //return cb(null, set)
 161   var remove = []
 162
 163   asyncMap(set, function (item, cb) {
 164     // [name, has, loc, locMatch, regMatch, others]
 165     var name = item[0]
 166     var has = item[1]
 167     var where = item[2]
 168     var locMatch = item[3]
 169     var regMatch = item[4]
 170     var others = item[5]
 171
 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
 177       return cb()
 178     }
 179
 180     // nothing to do except to clean up the extraneous deps
 181     if (locMatch && has[where] === locMatch) {
 182       remove.push.apply(remove, others)
 183       return cb()
 184     }
 185
 186     if (regMatch) {
 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)
 193       where.pop()
 194       where = where.join(path.sep + "node_modules" + path.sep)
 195       remove.push.apply(remove, others)
 196
 197       return npm.commands.install(where, what, cb)
 198     }
 199
 200     // hrm?
 201     return cb(new Error("danger zone\n" + name + " " +
 202                         regMatch + " " + locMatch))
 203
 204   }, function (er) {
 205     if (er) return cb(er)
 206     asyncMap(remove, rm, function (er) {
 207       if (er) return cb(er)
 208       remove.forEach(function (r) {
 209         log.info("rm", r)
 210       })
 211       dedupe_(dir, filter, unavoidable, false, silent, cb)
 212     })
 213   })
 214 }
 215
 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) {
 221     var name = item[0]
 222     var data = item[1]
 223     var loc = data.loc
 224     var locs = data.locs.filter(function (l) {
 225       return l !== loc
 226     })
 227
 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) {
 231       return cb(null, [])
 232     }
 233
 234     // { <folder>: <version> }
 235     var has = data.has
 236
 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
 241
 242     var ranges = data.ranges
 243     mapToRegistry(name, npm.config, function (er, uri, auth) {
 244       if (er) return cb(er)
 245
 246       npm.registry.get(uri, { auth : auth }, next)
 247     })
 248
 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]
 254
 255       var regMatch
 256       if (distTag && data.versions[distTag] && matches(distTag, ranges)) {
 257         regMatch = distTag
 258       } else {
 259         regMatch = bestMatch(regVersions, ranges)
 260       }
 261
 262       cb(null, [[name, has, loc, locMatch, regMatch, locs]])
 263     }
 264   }, cb)
 265 }
 266
 267 function matches (version, ranges) {
 268   return !ranges.some(function (r) {
 269     return !semver.satisfies(version, r, true)
 270   })
 271 }
 272
 273 function bestMatch (versions, ranges) {
 274   return versions.filter(function (v) {
 275     return matches(v, ranges)
 276   }).sort(semver.compareLoose).pop()
 277 }
 278
 279
 280 function readInstalled (dir, counter, parent, cb) {
 281   var pkg, children, realpath
 282
 283   fs.realpath(dir, function (er, rp) {
 284     realpath = rp
 285     next()
 286   })
 287
 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
 292     counter[data.name]++
 293     pkg =
 294       { _id: data._id
 295       , name: data.name
 296       , version: data.version
 297       , dependencies: data.dependencies || {}
 298       , optionalDependencies: data.optionalDependencies || {}
 299       , devDependencies: data.devDependencies || {}
 300       , bundledDependencies: data.bundledDependencies || []
 301       , path: dir
 302       , realPath: dir
 303       , children: {}
 304       , parent: parent
 305       , family: Object.create(parent ? parent.family : null)
 306       , unavoidable: false
 307       , duplicate: false
 308       }
 309     if (parent) {
 310       parent.children[data.name] = pkg
 311       parent.family[data.name] = pkg
 312     }
 313     next()
 314   })
 315
 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))
 325           })
 326           cb()
 327         })
 328       } else {
 329         children.push(child)
 330         cb()
 331       }
 332     }, function (er) {
 333       if (er) return cb(er)
 334       children = children.filter(function (p) {
 335         return !p.match(/^[\._-]/)
 336       })
 337       next();
 338     });
 339   })
 340
 341   function next () {
 342     if (!children || !pkg || !realpath) return
 343
 344     // ignore devDependencies.  Just leave them where they are.
 345     children = children.filter(function (c) {
 346       return !pkg.devDependencies.hasOwnProperty(c)
 347     })
 348
 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)
 354     }, function (er) {
 355       cb(er, pkg, counter)
 356     })
 357   }
 358 }
 359
 360 function whoDepends (pkg) {
 361   var start = pkg.parent || pkg
 362   return whoDepends_(pkg, [], start)
 363 }
 364
 365 function whoDepends_ (pkg, who, test) {
 366   if (test !== pkg &&
 367       test.dependencies[pkg.name] &&
 368       test.family[pkg.name] === pkg) {
 369     who.push(test)
 370   }
 371   Object.keys(test.children).forEach(function (n) {
 372     whoDepends_(pkg, who, test.children[n])
 373   })
 374   return who
 375 }