1// A path exclusive reservation system
2// reserve([list, of, paths], fn)
3// When the fn is first in line for all its paths, it
4// is called with a cb that clears the reservation.
5//
6// Used by async unpack to avoid clobbering paths in use,
7// while still allowing maximal safe parallelization.
8
9const assert = require('assert')
10const normalize = require('./normalize-unicode.js')
11const stripSlashes = require('./strip-trailing-slashes.js')
12const { join } = require('path')
13
14const platform = process.env.TESTING_TAR_FAKE_PLATFORM || process.platform
15const isWindows = platform === 'win32'
16
17module.exports = () => {
18  // path => [function or Set]
19  // A Set object means a directory reservation
20  // A fn is a direct reservation on that path
21  const queues = new Map()
22
23  // fn => {paths:[path,...], dirs:[path, ...]}
24  const reservations = new Map()
25
26  // return a set of parent dirs for a given path
27  // '/a/b/c/d' -> ['/', '/a', '/a/b', '/a/b/c', '/a/b/c/d']
28  const getDirs = path => {
29    const dirs = path.split('/').slice(0, -1).reduce((set, path) => {
30      if (set.length) {
31        path = join(set[set.length - 1], path)
32      }
33      set.push(path || '/')
34      return set
35    }, [])
36    return dirs
37  }
38
39  // functions currently running
40  const running = new Set()
41
42  // return the queues for each path the function cares about
43  // fn => {paths, dirs}
44  const getQueues = fn => {
45    const res = reservations.get(fn)
46    /* istanbul ignore if - unpossible */
47    if (!res) {
48      throw new Error('function does not have any path reservations')
49    }
50    return {
51      paths: res.paths.map(path => queues.get(path)),
52      dirs: [...res.dirs].map(path => queues.get(path)),
53    }
54  }
55
56  // check if fn is first in line for all its paths, and is
57  // included in the first set for all its dir queues
58  const check = fn => {
59    const { paths, dirs } = getQueues(fn)
60    return paths.every(q => q[0] === fn) &&
61      dirs.every(q => q[0] instanceof Set && q[0].has(fn))
62  }
63
64  // run the function if it's first in line and not already running
65  const run = fn => {
66    if (running.has(fn) || !check(fn)) {
67      return false
68    }
69    running.add(fn)
70    fn(() => clear(fn))
71    return true
72  }
73
74  const clear = fn => {
75    if (!running.has(fn)) {
76      return false
77    }
78
79    const { paths, dirs } = reservations.get(fn)
80    const next = new Set()
81
82    paths.forEach(path => {
83      const q = queues.get(path)
84      assert.equal(q[0], fn)
85      if (q.length === 1) {
86        queues.delete(path)
87      } else {
88        q.shift()
89        if (typeof q[0] === 'function') {
90          next.add(q[0])
91        } else {
92          q[0].forEach(fn => next.add(fn))
93        }
94      }
95    })
96
97    dirs.forEach(dir => {
98      const q = queues.get(dir)
99      assert(q[0] instanceof Set)
100      if (q[0].size === 1 && q.length === 1) {
101        queues.delete(dir)
102      } else if (q[0].size === 1) {
103        q.shift()
104
105        // must be a function or else the Set would've been reused
106        next.add(q[0])
107      } else {
108        q[0].delete(fn)
109      }
110    })
111    running.delete(fn)
112
113    next.forEach(fn => run(fn))
114    return true
115  }
116
117  const reserve = (paths, fn) => {
118    // collide on matches across case and unicode normalization
119    // On windows, thanks to the magic of 8.3 shortnames, it is fundamentally
120    // impossible to determine whether two paths refer to the same thing on
121    // disk, without asking the kernel for a shortname.
122    // So, we just pretend that every path matches every other path here,
123    // effectively removing all parallelization on windows.
124    paths = isWindows ? ['win32 parallelization disabled'] : paths.map(p => {
125      // don't need normPath, because we skip this entirely for windows
126      return stripSlashes(join(normalize(p))).toLowerCase()
127    })
128
129    const dirs = new Set(
130      paths.map(path => getDirs(path)).reduce((a, b) => a.concat(b))
131    )
132    reservations.set(fn, { dirs, paths })
133    paths.forEach(path => {
134      const q = queues.get(path)
135      if (!q) {
136        queues.set(path, [fn])
137      } else {
138        q.push(fn)
139      }
140    })
141    dirs.forEach(dir => {
142      const q = queues.get(dir)
143      if (!q) {
144        queues.set(dir, [new Set([fn])])
145      } else if (q[q.length - 1] instanceof Set) {
146        q[q.length - 1].add(fn)
147      } else {
148        q.push(new Set([fn]))
149      }
150    })
151
152    return run(fn)
153  }
154
155  return { check, reserve }
156}
157