Implement support for watching directories containing implicitly analyzed files

pkg/analysis_server/lib/src/watch_manager.dart

+// Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+library context.directory.manager;
+
+import 'dart:async';
+import 'dart:collection';
+import 'dart:core' hide Resource;
+
+import 'package:analyzer/file_system/file_system.dart';
+import 'package:watcher/watcher.dart';
+
+/**
+ * A function called when a watch [event] associated with a watched resource is
+ * received. The list of [tokens] will contain all of the tokens associated with
+ * folders containing (or the same as) the watched resource.
+ */
+typedef void HandleWatchEvent<T>(WatchEvent event, List<T> tokens);
+
+/**
+ * An object that manages a collections of folders that need to be watched in
+ * order to ensure that we are watching the minimum number of folders.
+ *
+ * Each folder can be watched multiple times. In order to differenciate between
+ * the watch requests, each watch request has a *token* associated with it. The
+ * tokens that are used must correctly implement both [==] and [hashCode].
+ */
+class WatchManager<T> {
+  /**
+   * The resource provider used to convert paths to resources.
+   */
+  final ResourceProvider provider;
+
+  /**
+   * The function that is invoked when a watch event is received.
+   */
+  final HandleWatchEvent<T> handleWatchEvent;
+
+  /**
+   * A node representing the (conceptual) root of all other folders.
+   */
+  final WatchNode<T> rootNode = new WatchNode<T>(null);
+
+  /**
+   * A table mapping the folders that are being watched to the nodes
+   * representing those folders.
+   */
+  final Map<Folder, WatchNode<T>> _watchedFolders =
+      new HashMap<Folder, WatchNode<T>>();
+
+  /**
+   * Initialize a newly created watch manager to use the resource [provider] to
+   * convert file paths to resources and to call the [handleWatchEvent] function
+   * to notify the owner of the manager when resources have been changed.
+   */
+  WatchManager(this.provider, this.handleWatchEvent);
+
+  /**
+   * Record the fact that we are now watching the given [folder], and associate
+   * that folder with the given [token].

[Paul Berry, 2015/07/19 18:38:34]

Documentation should say what happens if the same folder is watched multiple
times with the same token.  Are the later calls to addFolder() ignored, is the
folder effectively watched N times, or is the caller required to ensure that
this situation does not arise?  (I think that the later calls are effectively
ignored, since WatchNode.tokens is a set).

[Brian Wilkerson, 2015/07/19 21:24:19]

Done

+   */
+  void addFolder(Folder folder, T token) {
+    WatchNode<T> folderNode = _watchedFolders[folder];
+    //
+    // If the folder was already being watched, just record the new token.
+    //
+    if (folderNode != null) {
+      folderNode.tokens.add(token);
+      return;
+    }
+    //
+    // Otherwise, add the folder to the tree.
+    //
+    folderNode = new WatchNode<T>(folder);
+    _watchedFolders[folder] = folderNode;
+    folderNode.tokens.add(token);
+    WatchNode<T> parentNode = rootNode.insert(folderNode);
+    //
+    // If we are not watching a folder that contains the folder, then create a
+    // subscription for it.
+    //
+    if (parentNode == rootNode) {
+      folderNode.subscription = folder.changes.listen((WatchEvent event) {

[Paul Berry, 2015/07/19 18:38:34]

How about just:

folderNode.subscription = folder.changes.listen(_handleWatchEvent);

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+        _handleWatchEvent(event);
+      });
+      //
+      // Any nodes that became children of the newly added folder would have
+      // been top-level folders and would have been watched. We need to cancel
+      // their subscriptions.
+      //
+      for (WatchNode<T> childNode in folderNode.children) {
+        if (childNode.subscription != null) {

[Paul Berry, 2015/07/19 18:38:33]

Consider adding:

assert(childNode.subscription != null);

Since the only way a childNode would have a null subscription would be due to a
bug in the WatchManager.

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+          childNode.subscription.cancel();
+          childNode.subscription = null;
+        }
+      }
+    }
+  }
+
+  /**
+   * Record that we are no longer watching the given [folder] with the given
+   * [token].
+   */

[Paul Berry, 2015/07/19 18:38:33]

I like the fact that nothing happens if removeFolder() is called on a
folder/token pair that are not currently being watched.  That's good defensive
programming, however it carries the risk of masking bugs in clients.

Suggestion: document that the caller is required to call removeFolder() on a
folder/token pair that are currently being watched, and add assertions to verify
that folderNode != null and tokens.remove(token) returns true.

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+  void removeFolder(Folder folder, T token) {
+    WatchNode<T> folderNode = _watchedFolders[folder];
+    if (folderNode == null) {
+      return;
+    }
+    Set<T> tokens = folderNode.tokens;
+    tokens.remove(token);
+    //
+    // If this was the last token associated with this folder, then remove the
+    // folder from the tree.
+    //
+    if (tokens.isEmpty) {
+      //
+      // If the folder was a top-level folder, then we need to create
+      // subscriptions for all of it's children and cancel it's subscription.

[Paul Berry, 2015/07/19 18:38:33]

Nit: both "it's" should be "its".

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+      //
+      if (folderNode.subscription != null) {
+        for (WatchNode<T> childNode in folderNode.children) {
+          childNode.subscription = childNode.folder.changes

[Paul Berry, 2015/07/19 18:38:33]

Consider adding "assert(childNode.subscription == null);" prior to this line.

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+              .listen((WatchEvent event) {

[Paul Berry, 2015/07/19 18:38:33]

Again, ".listen(_handleWatchEvent);" should be sufficient.

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+            _handleWatchEvent(event);
+          });
+        }
+        folderNode.subscription.cancel();
+        folderNode.subscription = null;
+      }
+      folderNode.delete();
+      _watchedFolders.remove(folder);
+    }
+  }
+
+  /**
+   * Dispatch the given event by finding all of the tokens that contain the
+   * resource and invoke the [handleWatchEvent] function.
+   */
+  void _handleWatchEvent(WatchEvent event) {
+    String path = event.path;
+    List<T> tokens = <T>[];
+//    void visitNode(WatchNode node) {

[Paul Berry, 2015/07/19 18:38:34]

Was this commented-out code left here by accident?  It should either be removed
or its purpose should be documented with a TODO comment.

[Brian Wilkerson, 2015/07/19 21:24:20]

It was missed while cleaning-up.

+//      Folder folder = node.folder;
+//      if (folder.contains(path)) {
+//        tokens.addAll(_watchedFolders[folder].tokens);
+//      }
+//      node.forEachChild(visitNode);
+//    }
+//    visitNode(rootFolder.findParent(path));
+    WatchNode<T> parent = rootNode.findParent(path);

[Paul Berry, 2015/07/19 18:38:34]

What happens if path is identical to the path to one of the folder being
watched?  (E.g. we are watching "/foo/bar", and "/foo/bar" gets deleted from the
filesystem).  I believe your algorithm will only inform watchers for parent
folders.  But I think clients will expect to also receive notifications for the
folder itself, since AFAIK this is the behavior of the existing "watcher"
package.

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+    while (parent != rootNode) {
+      tokens.addAll(parent.tokens);
+      parent = parent.parent;
+    }
+    if (tokens.isNotEmpty) {
+      handleWatchEvent(event, tokens);
+    }
+  }
+}
+
+/**
+ * The information kept by a [WatchManager] about a single folder that is being
+ * watched.
+ *
+ * Watch nodes form a tree in which one node is a child of another node if the
+ * child's folder is contained in the parent's folder and none of the folders
+ * between the parent's folder and the child's folder are being watched.
+ */
+class WatchNode<T> {
+  /**
+   * An empty list of watch nodes.
+   */
+  static List<WatchNode> EMPTY_LIST = <WatchNode>[];

[Paul Berry, 2015/07/19 18:38:33]

I think this goes away if you take my suggestion below.  However, if you don't,
please make it const.  As it stands there's too much danger of someone
accidentally adding an entry to this list and breaking a bunch of invariants.

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+
+  /**
+   * The folder for which information is being maintained. This is `null` for
+   * the unique "root" node that maintains references to all of the top-level
+   * folders being watched.
+   */
+  Folder folder;

[Paul Berry, 2015/07/19 18:38:33]

Can this be final?

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+
+  /**
+   * The parent of this node.
+   */
+  WatchNode parent;
+
+  /**
+   * The information for the children of this node.
+   */
+  List<WatchNode> _children = null;

[Paul Berry, 2015/07/19 18:38:33]

It seems like premature optimization to use `null` for leaf nodes.  Consider
making this variable final and initializing it to <WatchNode>[].  That should
eliminate a bunch of explicit null checks (and might even allow the VM to drop
implicit null checks, since the VM will be able to prove that this field is
never null).

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+
+  /**
+   * The tokens that were used to register interest in watching this folder.
+   */
+  Set<T> tokens = new HashSet<T>();

[Paul Berry, 2015/07/19 18:38:34]

This can be final.

[Brian Wilkerson, 2015/07/19 21:24:19]

Done

+
+  /**
+   * The subscription being used to watch the folder, or `null` if the folder
+   * is being watched as part of a containing folder (in other words, if the
+   * parent is not the special "root").
+   */
+  StreamSubscription<WatchEvent> subscription;
+
+  /**
+   * Initialize a newly created node to represent the given [folder].
+   */
+  WatchNode(this.folder);
+
+  /**
+   * Return a list containing the children of this node.
+   */
+  List<WatchNode> get children => _children == null ? EMPTY_LIST : _children;

[Paul Berry, 2015/07/19 18:38:34]

Consider changing the return type to Iterable<WatchNode> so that clients are
discouraged from modifying the list directly and disrupting invariants.

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+
+  /**
+   * Remove this node from the tree of watched folders.
+   */
+  void delete() {
+    if (parent != null) {
+      parent._removeChild(this);
+    }

[Paul Berry, 2015/07/19 18:38:34]

Consider setting parent to null so the node returns to its initial state.

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+  }
+
+  /**
+   * Return the highest node reachable from this node that contains the given
+   * [filePath]. If no other node is found, return this node, even if this node
+   * does not contain the path.
+   */
+  WatchNode findParent(String filePath) {
+    if (_children == null) {
+      return this;
+    }
+    for (WatchNode childNode in _children) {
+      if (childNode.folder.contains(filePath)) {
+        return childNode.findParent(filePath);
+      }
+    }
+    return this;
+  }
+
+  @override
+  String toString() => 'WatchNode ('
+        'folder = ${folder == null ? '<root>' : folder.path}, '
+        'tokens = $tokens, '
+        'subscription = ${subscription == null ? 'null' : 'non-null'})';
+
+  /**
+   * Invoke the given [function] on each of the children of this node.
+   */
+  void forEachChild(void function(WatchNode<T> node)) {

[Paul Berry, 2015/07/19 18:38:33]

This method is only called from commented-out code.  Can it be removed?

[Brian Wilkerson, 2015/07/19 21:24:20]

Done

+    if (_children != null) {
+      _children.forEach(function);
+    }
+  }
+
+  /**
+   * Insert the given [node] into the tree of watched folders, either as a child
+   * of this node or as a descendent of one of this node's children. Return the
+   * immediate parent of the newly added node.
+   */
+  WatchNode insert(WatchNode node) {
+    WatchNode parentNode = findParent(node.folder.path);
+    parentNode._addChild(node, true);
+    return parentNode;
+  }
+
+  /**
+   * Add the given [newChild] as an immediate child of this node.
+   *
+   * If [checkChildren] is `true`, check to see whether any of the previously
+   * existing children of this node should now be children of the new child, and
+   * if so, move them.
+   */
+  void _addChild(WatchNode newChild, bool checkChildren) {
+    if (_children == null) {
+      _children = <WatchNode>[];
+    } else if (checkChildren) {
+      Folder folder = newChild.folder;
+      for (int i = _children.length - 1; i >= 0; i--) {
+        WatchNode existingChild = _children[i];
+        if (folder.contains(existingChild.folder.path)) {
+          newChild._addChild(existingChild, false);
+          _children.removeAt(i);
+        }
+      }
+    }
+    newChild.parent = this;
+    _children.add(newChild);
+  }
+
+  /**
+   * Remove the given [node] from the list of children of this node. Any
+   * children of the [node] will become children of this node.
+   */
+  void _removeChild(WatchNode child) {
+    _children.remove(child);
+    for (WatchNode grandchild in child.children) {
+      grandchild.parent = this;
+      _children.add(grandchild);
+    }
+    if (_children.isEmpty) {
+      _children = null;
+    }
+  }

[Paul Berry, 2015/07/19 18:38:33]

Consider setting child._children to null so that there is less danger of
corrupting data structures if the caller tries to re-use the child.

[Brian Wilkerson, 2015/07/19 21:24:21]

I can't because now there's an assumption that _children is never null. The only
caller is WatchManager, and it doesn't re-use WatchFolders, but the code now
removed the grandchild from the child's list of children just to avoid potential
problems.

+}