• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1'use strict'
2
3let path
4
5class LogicalTree {
6  constructor (name, address, opts) {
7    this.name = name
8    this.version = opts.version
9    this.address = address || ''
10    this.optional = !!opts.optional
11    this.dev = !!opts.dev
12    this.bundled = !!opts.bundled
13    this.resolved = opts.resolved
14    this.integrity = opts.integrity
15    this.dependencies = new Map()
16    this.requiredBy = new Set()
17  }
18
19  get isRoot () { return !this.requiredBy.size }
20
21  addDep (dep) {
22    this.dependencies.set(dep.name, dep)
23    dep.requiredBy.add(this)
24    return this
25  }
26
27  delDep (dep) {
28    this.dependencies.delete(dep.name)
29    dep.requiredBy.delete(this)
30    return this
31  }
32
33  getDep (name) {
34    return this.dependencies.get(name)
35  }
36
37  path (prefix) {
38    if (this.isRoot) {
39      // The address of the root is the prefix itself.
40      return prefix || ''
41    } else {
42      if (!path) { path = require('path') }
43      return path.join(
44        prefix || '',
45        'node_modules',
46        this.address.replace(/:/g, '/node_modules/')
47      )
48    }
49  }
50
51  // This finds cycles _from_ a given node: if some deeper dep has
52  // its own cycle, but that cycle does not refer to this node,
53  // it will return false.
54  hasCycle (_seen, _from) {
55    if (!_seen) { _seen = new Set() }
56    if (!_from) { _from = this }
57    for (let dep of this.dependencies.values()) {
58      if (_seen.has(dep)) { continue }
59      _seen.add(dep)
60      if (dep === _from || dep.hasCycle(_seen, _from)) {
61        return true
62      }
63    }
64    return false
65  }
66
67  forEachAsync (fn, opts, _pending) {
68    if (!opts) { opts = _pending || {} }
69    if (!_pending) { _pending = new Map() }
70    const P = opts.Promise || Promise
71    if (_pending.has(this)) {
72      return P.resolve(this.hasCycle() || _pending.get(this))
73    }
74    const pending = P.resolve().then(() => {
75      return fn(this, () => {
76        return promiseMap(
77          this.dependencies.values(),
78          dep => dep.forEachAsync(fn, opts, _pending),
79          opts
80        )
81      })
82    })
83    _pending.set(this, pending)
84    return pending
85  }
86
87  forEach (fn, _seen) {
88    if (!_seen) { _seen = new Set() }
89    if (_seen.has(this)) { return }
90    _seen.add(this)
91    fn(this, () => {
92      for (let dep of this.dependencies.values()) {
93        dep.forEach(fn, _seen)
94      }
95    })
96  }
97}
98
99module.exports = lockTree
100function lockTree (pkg, pkgLock, opts) {
101  const tree = makeNode(pkg.name, null, pkg)
102  const allDeps = new Map()
103  Array.from(
104    new Set(Object.keys(pkg.devDependencies || {})
105    .concat(Object.keys(pkg.optionalDependencies || {}))
106    .concat(Object.keys(pkg.dependencies || {})))
107  ).forEach(name => {
108    let dep = allDeps.get(name)
109    if (!dep) {
110      const depNode = (pkgLock.dependencies || {})[name]
111      dep = makeNode(name, name, depNode)
112    }
113    addChild(dep, tree, allDeps, pkgLock)
114  })
115  return tree
116}
117
118module.exports.node = makeNode
119function makeNode (name, address, opts) {
120  return new LogicalTree(name, address, opts || {})
121}
122
123function addChild (dep, tree, allDeps, pkgLock) {
124  tree.addDep(dep)
125  allDeps.set(dep.address, dep)
126  const addr = dep.address
127  const lockNode = atAddr(pkgLock, addr)
128  Object.keys(lockNode.requires || {}).forEach(name => {
129    const tdepAddr = reqAddr(pkgLock, name, addr)
130    let tdep = allDeps.get(tdepAddr)
131    if (!tdep) {
132      tdep = makeNode(name, tdepAddr, atAddr(pkgLock, tdepAddr))
133      addChild(tdep, dep, allDeps, pkgLock)
134    } else {
135      dep.addDep(tdep)
136    }
137  })
138}
139
140module.exports._reqAddr = reqAddr
141function reqAddr (pkgLock, name, fromAddr) {
142  const lockNode = atAddr(pkgLock, fromAddr)
143  const child = (lockNode.dependencies || {})[name]
144  if (child) {
145    return `${fromAddr}:${name}`
146  } else {
147    const parts = fromAddr.split(':')
148    while (parts.length) {
149      parts.pop()
150      const joined = parts.join(':')
151      const parent = atAddr(pkgLock, joined)
152      if (parent) {
153        const child = (parent.dependencies || {})[name]
154        if (child) {
155          return `${joined}${parts.length ? ':' : ''}${name}`
156        }
157      }
158    }
159    const err = new Error(`${name} not accessible from ${fromAddr}`)
160    err.pkgLock = pkgLock
161    err.target = name
162    err.from = fromAddr
163    throw err
164  }
165}
166
167module.exports._atAddr = atAddr
168function atAddr (pkgLock, addr) {
169  if (!addr.length) { return pkgLock }
170  const parts = addr.split(':')
171  return parts.reduce((acc, next) => {
172    return acc && (acc.dependencies || {})[next]
173  }, pkgLock)
174}
175
176function promiseMap (arr, fn, opts, _index) {
177  _index = _index || 0
178  const P = (opts && opts.Promise) || Promise
179  if (P.map) {
180    return P.map(arr, fn, opts)
181  } else {
182    if (!(arr instanceof Array)) {
183      arr = Array.from(arr)
184    }
185    if (_index >= arr.length) {
186      return P.resolve()
187    } else {
188      return P.resolve(fn(arr[_index], _index, arr))
189      .then(() => promiseMap(arr, fn, opts, _index + 1))
190    }
191  }
192}
193