native-watcher-registry.js
1 const path = require('path'); 2 3 // Private: re-join the segments split from an absolute path to form another absolute path. 4 function absolute(...parts) { 5 const candidate = path.join(...parts); 6 return path.isAbsolute(candidate) 7 ? candidate 8 : path.join(path.sep, candidate); 9 } 10 11 // Private: Map userland filesystem watcher subscriptions efficiently to deliver filesystem change notifications to 12 // each watcher with the most efficient coverage of native watchers. 13 // 14 // * If two watchers subscribe to the same directory, use a single native watcher for each. 15 // * Re-use a native watcher watching a parent directory for a watcher on a child directory. If the parent directory 16 // watcher is removed, it will be split into child watchers. 17 // * If any child directories already being watched, stop and replace them with a watcher on the parent directory. 18 // 19 // Uses a trie whose structure mirrors the directory structure. 20 class RegistryTree { 21 // Private: Construct a tree with no native watchers. 22 // 23 // * `basePathSegments` the position of this tree's root relative to the filesystem's root as an {Array} of directory 24 // names. 25 // * `createNative` {Function} used to construct new native watchers. It should accept an absolute path as an argument 26 // and return a new {NativeWatcher}. 27 constructor(basePathSegments, createNative) { 28 this.basePathSegments = basePathSegments; 29 this.root = new RegistryNode(); 30 this.createNative = createNative; 31 } 32 33 // Private: Identify the native watcher that should be used to produce events at a watched path, creating a new one 34 // if necessary. 35 // 36 // * `pathSegments` the path to watch represented as an {Array} of directory names relative to this {RegistryTree}'s 37 // root. 38 // * `attachToNative` {Function} invoked with the appropriate native watcher and the absolute path to its watch root. 39 add(pathSegments, attachToNative) { 40 const absolutePathSegments = this.basePathSegments.concat(pathSegments); 41 const absolutePath = absolute(...absolutePathSegments); 42 43 const attachToNew = childPaths => { 44 const native = this.createNative(absolutePath); 45 const leaf = new RegistryWatcherNode( 46 native, 47 absolutePathSegments, 48 childPaths 49 ); 50 this.root = this.root.insert(pathSegments, leaf); 51 52 const sub = native.onWillStop(() => { 53 sub.dispose(); 54 this.root = 55 this.root.remove(pathSegments, this.createNative) || 56 new RegistryNode(); 57 }); 58 59 attachToNative(native, absolutePath); 60 return native; 61 }; 62 63 this.root.lookup(pathSegments).when({ 64 parent: (parent, remaining) => { 65 // An existing NativeWatcher is watching the same directory or a parent directory of the requested path. 66 // Attach this Watcher to it as a filtering watcher and record it as a dependent child path. 67 const native = parent.getNativeWatcher(); 68 parent.addChildPath(remaining); 69 attachToNative(native, absolute(...parent.getAbsolutePathSegments())); 70 }, 71 children: children => { 72 // One or more NativeWatchers exist on child directories of the requested path. Create a new native watcher 73 // on the parent directory, note the subscribed child paths, and cleanly stop the child native watchers. 74 const newNative = attachToNew(children.map(child => child.path)); 75 76 for (let i = 0; i < children.length; i++) { 77 const childNode = children[i].node; 78 const childNative = childNode.getNativeWatcher(); 79 childNative.reattachTo(newNative, absolutePath); 80 childNative.dispose(); 81 childNative.stop(); 82 } 83 }, 84 missing: () => attachToNew([]) 85 }); 86 } 87 88 // Private: Access the root node of the tree. 89 getRoot() { 90 return this.root; 91 } 92 93 // Private: Return a {String} representation of this tree's structure for diagnostics and testing. 94 print() { 95 return this.root.print(); 96 } 97 } 98 99 // Private: Non-leaf node in a {RegistryTree} used by the {NativeWatcherRegistry} to cover the allocated {Watcher} 100 // instances with the most efficient set of {NativeWatcher} instances possible. Each {RegistryNode} maps to a directory 101 // in the filesystem tree. 102 class RegistryNode { 103 // Private: Construct a new, empty node representing a node with no watchers. 104 constructor() { 105 this.children = {}; 106 } 107 108 // Private: Recursively discover any existing watchers corresponding to a path. 109 // 110 // * `pathSegments` filesystem path of a new {Watcher} already split into an Array of directory names. 111 // 112 // Returns: A {ParentResult} if the exact requested directory or a parent directory is being watched, a 113 // {ChildrenResult} if one or more child paths are being watched, or a {MissingResult} if no relevant watchers 114 // exist. 115 lookup(pathSegments) { 116 if (pathSegments.length === 0) { 117 return new ChildrenResult(this.leaves([])); 118 } 119 120 const child = this.children[pathSegments[0]]; 121 if (child === undefined) { 122 return new MissingResult(this); 123 } 124 125 return child.lookup(pathSegments.slice(1)); 126 } 127 128 // Private: Insert a new {RegistryWatcherNode} into the tree, creating new intermediate {RegistryNode} instances as 129 // needed. Any existing children of the watched directory are removed. 130 // 131 // * `pathSegments` filesystem path of the new {Watcher}, already split into an Array of directory names. 132 // * `leaf` initialized {RegistryWatcherNode} to insert 133 // 134 // Returns: The root of a new tree with the {RegistryWatcherNode} inserted at the correct location. Callers should 135 // replace their node references with the returned value. 136 insert(pathSegments, leaf) { 137 if (pathSegments.length === 0) { 138 return leaf; 139 } 140 141 const pathKey = pathSegments[0]; 142 let child = this.children[pathKey]; 143 if (child === undefined) { 144 child = new RegistryNode(); 145 } 146 this.children[pathKey] = child.insert(pathSegments.slice(1), leaf); 147 return this; 148 } 149 150 // Private: Remove a {RegistryWatcherNode} by its exact watched directory. 151 // 152 // * `pathSegments` absolute pre-split filesystem path of the node to remove. 153 // * `createSplitNative` callback to be invoked with each child path segment {Array} if the {RegistryWatcherNode} 154 // is split into child watchers rather than removed outright. See {RegistryWatcherNode.remove}. 155 // 156 // Returns: The root of a new tree with the {RegistryWatcherNode} removed. Callers should replace their node 157 // references with the returned value. 158 remove(pathSegments, createSplitNative) { 159 if (pathSegments.length === 0) { 160 // Attempt to remove a path with child watchers. Do nothing. 161 return this; 162 } 163 164 const pathKey = pathSegments[0]; 165 const child = this.children[pathKey]; 166 if (child === undefined) { 167 // Attempt to remove a path that isn't watched. Do nothing. 168 return this; 169 } 170 171 // Recurse 172 const newChild = child.remove(pathSegments.slice(1), createSplitNative); 173 if (newChild === null) { 174 delete this.children[pathKey]; 175 } else { 176 this.children[pathKey] = newChild; 177 } 178 179 // Remove this node if all of its children have been removed 180 return Object.keys(this.children).length === 0 ? null : this; 181 } 182 183 // Private: Discover all {RegistryWatcherNode} instances beneath this tree node and the child paths 184 // that they are watching. 185 // 186 // * `prefix` {Array} of intermediate path segments to prepend to the resulting child paths. 187 // 188 // Returns: A possibly empty {Array} of `{node, path}` objects describing {RegistryWatcherNode} 189 // instances beneath this node. 190 leaves(prefix) { 191 const results = []; 192 for (const p of Object.keys(this.children)) { 193 results.push(...this.children[p].leaves(prefix.concat([p]))); 194 } 195 return results; 196 } 197 198 // Private: Return a {String} representation of this subtree for diagnostics and testing. 199 print(indent = 0) { 200 let spaces = ''; 201 for (let i = 0; i < indent; i++) { 202 spaces += ' '; 203 } 204 205 let result = ''; 206 for (const p of Object.keys(this.children)) { 207 result += `${spaces}${p}\n${this.children[p].print(indent + 2)}`; 208 } 209 return result; 210 } 211 } 212 213 // Private: Leaf node within a {NativeWatcherRegistry} tree. Represents a directory that is covered by a 214 // {NativeWatcher}. 215 class RegistryWatcherNode { 216 // Private: Allocate a new node to track a {NativeWatcher}. 217 // 218 // * `nativeWatcher` An existing {NativeWatcher} instance. 219 // * `absolutePathSegments` The absolute path to this {NativeWatcher}'s directory as an {Array} of 220 // path segments. 221 // * `childPaths` {Array} of child directories that are currently the responsibility of this 222 // {NativeWatcher}, if any. Directories are represented as arrays of the path segments between this 223 // node's directory and the watched child path. 224 constructor(nativeWatcher, absolutePathSegments, childPaths) { 225 this.nativeWatcher = nativeWatcher; 226 this.absolutePathSegments = absolutePathSegments; 227 228 // Store child paths as joined strings so they work as Set members. 229 this.childPaths = new Set(); 230 for (let i = 0; i < childPaths.length; i++) { 231 this.childPaths.add(path.join(...childPaths[i])); 232 } 233 } 234 235 // Private: Assume responsibility for a new child path. If this node is removed, it will instead 236 // split into a subtree with a new {RegistryWatcherNode} for each child path. 237 // 238 // * `childPathSegments` the {Array} of path segments between this node's directory and the watched 239 // child directory. 240 addChildPath(childPathSegments) { 241 this.childPaths.add(path.join(...childPathSegments)); 242 } 243 244 // Private: Stop assuming responsibility for a previously assigned child path. If this node is 245 // removed, the named child path will no longer be allocated a {RegistryWatcherNode}. 246 // 247 // * `childPathSegments` the {Array} of path segments between this node's directory and the no longer 248 // watched child directory. 249 removeChildPath(childPathSegments) { 250 this.childPaths.delete(path.join(...childPathSegments)); 251 } 252 253 // Private: Accessor for the {NativeWatcher}. 254 getNativeWatcher() { 255 return this.nativeWatcher; 256 } 257 258 // Private: Return the absolute path watched by this {NativeWatcher} as an {Array} of directory names. 259 getAbsolutePathSegments() { 260 return this.absolutePathSegments; 261 } 262 263 // Private: Identify how this watcher relates to a request to watch a directory tree. 264 // 265 // * `pathSegments` filesystem path of a new {Watcher} already split into an Array of directory names. 266 // 267 // Returns: A {ParentResult} referencing this node. 268 lookup(pathSegments) { 269 return new ParentResult(this, pathSegments); 270 } 271 272 // Private: Remove this leaf node if the watcher's exact path matches. If this node is covering additional 273 // {Watcher} instances on child paths, it will be split into a subtree. 274 // 275 // * `pathSegments` filesystem path of the node to remove. 276 // * `createSplitNative` callback invoked with each {Array} of absolute child path segments to create a native 277 // watcher on a subtree of this node. 278 // 279 // Returns: If `pathSegments` match this watcher's path exactly, returns `null` if this node has no `childPaths` 280 // or a new {RegistryNode} on a newly allocated subtree if it did. If `pathSegments` does not match the watcher's 281 // path, it's an attempt to remove a subnode that doesn't exist, so the remove call has no effect and returns 282 // `this` unaltered. 283 remove(pathSegments, createSplitNative) { 284 if (pathSegments.length !== 0) { 285 return this; 286 } else if (this.childPaths.size > 0) { 287 let newSubTree = new RegistryTree( 288 this.absolutePathSegments, 289 createSplitNative 290 ); 291 292 for (const childPath of this.childPaths) { 293 const childPathSegments = childPath.split(path.sep); 294 newSubTree.add(childPathSegments, (native, attachmentPath) => { 295 this.nativeWatcher.reattachTo(native, attachmentPath); 296 }); 297 } 298 299 return newSubTree.getRoot(); 300 } else { 301 return null; 302 } 303 } 304 305 // Private: Discover this {RegistryWatcherNode} instance. 306 // 307 // * `prefix` {Array} of intermediate path segments to prepend to the resulting child paths. 308 // 309 // Returns: An {Array} containing a `{node, path}` object describing this node. 310 leaves(prefix) { 311 return [{ node: this, path: prefix }]; 312 } 313 314 // Private: Return a {String} representation of this watcher for diagnostics and testing. Indicates the number of 315 // child paths that this node's {NativeWatcher} is responsible for. 316 print(indent = 0) { 317 let result = ''; 318 for (let i = 0; i < indent; i++) { 319 result += ' '; 320 } 321 result += '[watcher'; 322 if (this.childPaths.size > 0) { 323 result += ` +${this.childPaths.size}`; 324 } 325 result += ']\n'; 326 327 return result; 328 } 329 } 330 331 // Private: A {RegistryNode} traversal result that's returned when neither a directory, its children, nor its parents 332 // are present in the tree. 333 class MissingResult { 334 // Private: Instantiate a new {MissingResult}. 335 // 336 // * `lastParent` the final successfully traversed {RegistryNode}. 337 constructor(lastParent) { 338 this.lastParent = lastParent; 339 } 340 341 // Private: Dispatch within a map of callback actions. 342 // 343 // * `actions` {Object} containing a `missing` key that maps to a callback to be invoked when no results were returned 344 // by {RegistryNode.lookup}. The callback will be called with the last parent node that was encountered during the 345 // traversal. 346 // 347 // Returns: the result of the `actions` callback. 348 when(actions) { 349 return actions.missing(this.lastParent); 350 } 351 } 352 353 // Private: A {RegistryNode.lookup} traversal result that's returned when a parent or an exact match of the requested 354 // directory is being watched by an existing {RegistryWatcherNode}. 355 class ParentResult { 356 // Private: Instantiate a new {ParentResult}. 357 // 358 // * `parent` the {RegistryWatcherNode} that was discovered. 359 // * `remainingPathSegments` an {Array} of the directories that lie between the leaf node's watched directory and 360 // the requested directory. This will be empty for exact matches. 361 constructor(parent, remainingPathSegments) { 362 this.parent = parent; 363 this.remainingPathSegments = remainingPathSegments; 364 } 365 366 // Private: Dispatch within a map of callback actions. 367 // 368 // * `actions` {Object} containing a `parent` key that maps to a callback to be invoked when a parent of a requested 369 // requested directory is returned by a {RegistryNode.lookup} call. The callback will be called with the 370 // {RegistryWatcherNode} instance and an {Array} of the {String} path segments that separate the parent node 371 // and the requested directory. 372 // 373 // Returns: the result of the `actions` callback. 374 when(actions) { 375 return actions.parent(this.parent, this.remainingPathSegments); 376 } 377 } 378 379 // Private: A {RegistryNode.lookup} traversal result that's returned when one or more children of the requested 380 // directory are already being watched. 381 class ChildrenResult { 382 // Private: Instantiate a new {ChildrenResult}. 383 // 384 // * `children` {Array} of the {RegistryWatcherNode} instances that were discovered. 385 constructor(children) { 386 this.children = children; 387 } 388 389 // Private: Dispatch within a map of callback actions. 390 // 391 // * `actions` {Object} containing a `children` key that maps to a callback to be invoked when a parent of a requested 392 // requested directory is returned by a {RegistryNode.lookup} call. The callback will be called with the 393 // {RegistryWatcherNode} instance. 394 // 395 // Returns: the result of the `actions` callback. 396 when(actions) { 397 return actions.children(this.children); 398 } 399 } 400 401 // Private: Track the directories being monitored by native filesystem watchers. Minimize the number of native watchers 402 // allocated to receive events for a desired set of directories by: 403 // 404 // 1. Subscribing to the same underlying {NativeWatcher} when watching the same directory multiple times. 405 // 2. Subscribing to an existing {NativeWatcher} on a parent of a desired directory. 406 // 3. Replacing multiple {NativeWatcher} instances on child directories with a single new {NativeWatcher} on the 407 // parent. 408 class NativeWatcherRegistry { 409 // Private: Instantiate an empty registry. 410 // 411 // * `createNative` {Function} that will be called with a normalized filesystem path to create a new native 412 // filesystem watcher. 413 constructor(createNative) { 414 this.tree = new RegistryTree([], createNative); 415 } 416 417 // Private: Attach a watcher to a directory, assigning it a {NativeWatcher}. If a suitable {NativeWatcher} already 418 // exists, it will be attached to the new {Watcher} with an appropriate subpath configuration. Otherwise, the 419 // `createWatcher` callback will be invoked to create a new {NativeWatcher}, which will be registered in the tree 420 // and attached to the watcher. 421 // 422 // If any pre-existing child watchers are removed as a result of this operation, {NativeWatcher.onWillReattach} will 423 // be broadcast on each with the new parent watcher as an event payload to give child watchers a chance to attach to 424 // the new watcher. 425 // 426 // * `watcher` an unattached {Watcher}. 427 async attach(watcher) { 428 const normalizedDirectory = await watcher.getNormalizedPathPromise(); 429 const pathSegments = normalizedDirectory 430 .split(path.sep) 431 .filter(segment => segment.length > 0); 432 433 this.tree.add(pathSegments, (native, nativePath) => { 434 watcher.attachToNative(native, nativePath); 435 }); 436 } 437 438 // Private: Generate a visual representation of the currently active watchers managed by this 439 // registry. 440 // 441 // Returns a {String} showing the tree structure. 442 print() { 443 return this.tree.print(); 444 } 445 } 446 447 module.exports = { NativeWatcherRegistry };