Add support for listing to the glob package.

pkg/glob/lib/src/list_tree.dart

Index: pkg/glob/lib/src/list_tree.dart
diff --git a/pkg/glob/lib/src/list_tree.dart b/pkg/glob/lib/src/list_tree.dart
new file mode 100644
index 0000000000000000000000000000000000000000..16bdfe005939535e05a7dc5d3d04889a1bb919ee
--- /dev/null
+++ b/pkg/glob/lib/src/list_tree.dart
@@ -0,0 +1,353 @@
+// Copyright (c) 2014, 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 glob.list_tree;
+
+import 'dart:io';
+import 'dart:async';
+
+import 'package:path/path.dart' as p;
+
+import 'ast.dart';
+import 'stream_pool.dart';
+
+/// A structure built from a glob that efficiently lists filesystem entities
+/// that match that glob.

[Bob Nystrom, 2014/09/18 22:17:40]

The logic for turning a raw AstNode into a ListTree is split across the expand()
methods in AstNode subclasses, AstNode.split() and the ctor here. I think it
might be clearer to put that into a single compiler class so it's all in one
place. Doing the review here, I find I have to bounce back and forth a lot and
all of these methods are pretty deeply intertwined.

[nweiz, 2014/09/22 23:48:39]

I factored them that way because it strikes me as *minimally* intertwined.
[flattenOptions] and [split] are very well-defined Glob-to-Glob operations that
can be understood in their own right completely separate from the compilation
process.

I guess I could move them here or into a new ListTreeCompiler class, but the
recursion in [flattenOptions] would be more awkward and I at least would read
them as more intertwined, by virtue of being in the same class.

+///
+/// This structure is designed to list the minimal number of physical
+/// directories necessary to find everything that matches the glob. For example,
+/// for the glob `foo/{bar,baz}/*`, there's no need to list the working
+/// directory or even `foo/`; only `foo/bar` and `foo/baz` should be listed.
+///
+/// This works by creating a tree of [_ListTreeNode]s, each of which corresponds
+/// to a single of directory nesting in the source glob. Each node has child
+/// nodes associated with globs ([_ListTreeNode.children]), as well as its own
+/// glob ([_ListTreeNode._validator]) that indicates which entities within that
+/// node's directory should be returned.
+///
+/// For example, the glob `foo/{*.dart,b*/*.txt}` creates the following tree:
+///
+///     .
+///     '-- "foo" (validator: "*.dart")
+///         '-- "b*" (validator: "*.txt"
+///
+/// If a node doesn't have a validator, we know we don't have to list it
+/// explicitly.
+///
+/// Nodes can also be marked as "recursive", which means they need to be listed
+/// recursively (usually to support `**`). In this case, they will have no
+/// children; instead, their validator will just encompass the globs that would
+/// otherwise be in their children. For example, the glob
+/// `foo/{**.dart,bar/*.txt}` creates a recursive node for `foo` with the
+/// validator `**.dart,bar/*.txt`.
+///
+/// If the glob contains multiple filesystem roots (e.g. `{C:/,D:/}*.dart`),
+/// each root will have its own tree of nodes. Relative globs use `.` as their
+/// root instead.
+class ListTree {
+  /// A map from filesystem roots to the list tree for those roots.
+  ///
+  /// A relative glob will use `.` as its root.
+  final _trees = new Map<String, _ListTreeNode>();
+
+  ListTree(AstNode glob) {
+    // The first step in constructing a tree from the glob is to simplify the
+    // problem by eliminating options. [glob.expand] bubbles all options (and
+    // certain ranges) up to the top level of the glob so we can deal with them
+    // one at a time.
+    var options = glob.expand();
+
+    for (var option in options.options) {
+      // Since each option doesn't include its own options, we can safely split
+      // it into path components.
+      var components = option.split(p.context);
+      var firstNode = components.first.nodes.first;
+      var root;
+
+      // Determine the root for this option, if it's absolute. If it's not, the
+      // root's just ".".
+      if (firstNode is LiteralNode) {
+        var text = firstNode.text;
+        if (Platform.isWindows) text.replaceAll("/", "\\");
+        if (p.isAbsolute(text)) {
+          assert(components.first.nodes.length == 1);

[Bob Nystrom, 2014/09/18 22:17:40]

Document this.

[nweiz, 2014/09/22 23:48:40]

Done.

+          root = firstNode.text;
+          components.removeAt(0);
+        } else {
+          root = '.';

[Bob Nystrom, 2014/09/18 22:17:40]

How about just initializing root to "." and ditch the else clauses?

[nweiz, 2014/09/22 23:48:39]

Done.

+        }
+      } else {
+        root = '.';
+      }
+
+      // The first [parent] represents the root directory itself. It may be null

[Bob Nystrom, 2014/09/18 22:17:40]

This looks like a good chunk to break out into a separate method.

[nweiz, 2014/09/22 23:48:40]

Done.

+      // here if this is the first option with this particular [root]. If so,
+      // we'll create it below.
+      //
+      // As we iterate through [components], [parent] will be set to
+      // progressively more nested nodes.
+      var parent = _trees[root];
+      for (var i = 0; i < components.length; i++) {
+        var component = components[i];
+        var recursive = component.nodes.any((node) => node is DoubleStarNode);
+        var complete = i == components.length - 1;
+
+        // If the parent node for this level of nesting already exists, the new
+        // option will be added to it as additional validator options and/or
+        // additional children.
+        //
+        // If the parent doesn't exist, we'll create it in one of the else
+        // clauses below.
+        if (parent != null) {

[Bob Nystrom, 2014/09/18 22:17:40]

Breaking this out into a method would get rid of some of the nesting too.

[nweiz, 2014/09/22 23:48:40]

How so?

[Bob Nystrom, 2014/09/23 00:22:04]

I was thinking you could early return instead of all of the "else if"s but I
guess that doesn't buy much.

+          if (parent.isRecursive || recursive) {
+            // If [component] is recursive, mark [parent] as recursive. This
+            // will cause all of its children to be folded into its validator.
+            // If [parent] was already recursive, this is a no-op.
+            parent.makeRecursive();
+
+            // Add [component] and everything nested beneath it as an option to
+            // [parent]. Since [parent] is recursive, it will recursively list
+            // everything beneath it and filter them with one big glob.
+            parent.addOption(_join(components.sublist(i)));
+            break;
+          } else if (complete) {
+            // If [component] is the last component, add it to [parent]'s
+            // validator but not to its children.
+            parent.addOption(component);
+          } else {
+            // On the other hand if there are more components, add [component]
+            // to [parent]'s children and not its validator. Since we process
+            // each option's components separately, the same component is never
+            // both a validator and a child.
+            if (!parent.children.containsKey(component)) {
+              parent.children[component] = new _ListTreeNode();
+            }
+            parent = parent.children[component];
+          }
+        } else if (recursive) {
+          _trees[root] = new _ListTreeNode.recursive(
+              _join(components.sublist(i)));
+          break;
+        } else if (complete) {
+          _trees[root] = new _ListTreeNode()..addOption(component);
+        } else {
+          _trees[root] = new _ListTreeNode();
+          _trees[root].children[component] = new _ListTreeNode();
+          parent = _trees[root].children[component];
+        }
+      }
+    }
+  }
+
+  /// List all entities that match this glob beneath [root].
+  Stream<FileSystemEntity> list({String root, bool followLinks: true}) {
+    if (root == null) root = '.';
+    var pool = new StreamPool();
+    for (var rootDir in _trees.keys) {
+      var dir = rootDir == '.' ? root : rootDir;
+      pool.add(_trees[rootDir].list(dir, followLinks: followLinks));
+    }
+    pool.closeWhenEmpty();
+
+    // TODO(nweiz): Rather than filtering here, avoid double-listing directories
+    // in the first place.
+    var seen = new Set();
+    return pool.stream.where((entity) {
+      if (seen.contains(entity.path)) return false;
+      seen.add(entity.path);

[Bob Nystrom, 2014/09/18 22:17:40]

This will use buckets of memory on large directory listings. Ideas in order of
decreasing goodness:

1. Certainly don't do any this in the common case where there's only a single
call to Directory.list();
2. Don't do this if none of the listed directories overlap.
3. Only store paths that are within the overlapping range of the listed
directories.
4. Store the visited set as a tree of components instead of a set of paths.
5. Risky, but you could just store a fixed-size hash of the path instead of the
full path.
6. Don't guarantee non-repeated results.
 

[nweiz, 2014/09/22 23:48:40]

Done.
These seem like more work than is warranted. At that point, we might as well
figure out the logic to avoid re-listing directories in the first place.
Yuck.

+      return true;
+    });
+  }
+
+  /// Synchronosuly list all entities that match this glob beneath [root].
+  List<FileSystemEntity> listSync({String root, bool followLinks: true}) {
+    if (root == null) root = '.';
+
+    // TODO(nweiz): Rather than filtering here, avoid double-listing directories
+    // in the first place.
+    var seen = new Set();
+    return _trees.keys.expand((rootDir) {
+      var dir = rootDir == '.' ? root : rootDir;
+      return _trees[rootDir].listSync(dir, followLinks: followLinks);
+    }).where((entity) {
+      if (seen.contains(entity.path)) return false;
+      seen.add(entity.path);
+      return true;
+    }).toList();
+  }
+}
+
+/// A single node in a [ListTree].
+class _ListTreeNode {
+  /// This node's child nodes, by their corresponding globs.
+  ///
+  /// Each child node will only be listed on directories that match its glob.
+  ///
+  /// This may be `null`, indicating that this should be listed recursively.

[Bob Nystrom, 2014/09/18 22:17:40]

Clarify what the second "this" means.

[nweiz, 2014/09/22 23:48:40]

Done.

+  Map<SequenceNode, _ListTreeNode> children;
+
+  /// This node's validator.
+  ///
+  /// This determines which entities will ultimately be emitted when [list] is
+  /// called.
+  OptionsNode _validator;
+
+  /// Whether this node is recursive.
+  ///
+  /// A recursive node has no children and is listed recursively.
+  bool get isRecursive => children == null;
+
+  /// Whether this node doesn't itself need to be listed.
+  ///
+  /// If a node has no validator and all of its children are literal filenames,
+  /// there's no need to list its contents. We can just directly traverse into
+  /// its children.
+  bool get _isIntermediate {
+    if (_validator != null) return false;
+    return children.keys.every((sequence) =>
+        sequence.nodes.length == 1 && sequence.nodes.first is LiteralNode);
+  }
+
+  /// Creates a node with no children and no validator.
+  _ListTreeNode()
+      : children = new Map<SequenceNode, _ListTreeNode>(),
+        _validator = null;
+
+  /// Creates a recursive node the given [validator].
+  _ListTreeNode.recursive(SequenceNode validator)
+      : children = null,
+        _validator = new OptionsNode([validator]);
+
+  /// Transforms this into recursive node, folding all its children into its
+  /// validator.
+  void makeRecursive() {
+    if (isRecursive) return;
+    _validator = new OptionsNode(children.keys.map((sequence) {
+      var child = children[sequence];
+      child.makeRecursive();
+      return _join([sequence, child._validator]);
+    }));
+    children = null;
+  }
+
+  /// Adds [validator] to this node's existing validator.
+  void addOption(SequenceNode validator) {
+    if (_validator == null) {
+      _validator = new OptionsNode([validator]);
+    } else {
+      _validator.options.add(validator);
+    }
+  }
+
+  /// Lists all entities within [dir] matching this node or its children.

[Bob Nystrom, 2014/09/18 22:17:40]

Document that this (and listSync()) may return duplicates.

[nweiz, 2014/09/22 23:48:39]

Done.

+  Stream<FileSystemEntity> list(String dir, {bool followLinks: true}) {
+    if (isRecursive) {
+      return new Directory(dir).list(recursive: true, followLinks: followLinks)
+          .where((entity) => _matches(entity.path.substring(dir.length + 1)))
+          .handleError((error) {
+        // Swallow FileSystemExceptions because nonexistent or unreadable
+        // directories should just not produce any entities rather than crashing
+        // the list.

[Bob Nystrom, 2014/09/18 22:17:40]

Why?

[nweiz, 2014/09/22 23:48:40]

This was here to handle things like an unreadable directory nested within the
stuff a glob is listing. I thought Directory.list just didn't traverse into
unreadable directories, but it looks like I was wrong. Changed to match the
Directory.list behavior.

+        if (error is! FileSystemException) throw error;
+      });
+    }
+
+    var resultPool = new StreamPool();
+
+    // Don't spawn extra [Directory.list] calls when we already know exactly
+    // which subdirectories we're interested in.
+    if (_isIntermediate) {
+      children.forEach((sequence, child) {

[Bob Nystrom, 2014/09/18 22:17:40]

How does this handle a glob that points to a file, like "foo/bar/baz" where baz
is an actual file?

[nweiz, 2014/09/22 23:48:39]

That's handled as a validator. The root "." node's children has a sequence "foo"
with a child node. That child node has a sequence "bar" with another child node.
That child node has no children, just a validator "baz".

+        resultPool.add(child.list(p.join(dir, sequence.nodes.single.text),
+            followLinks: followLinks));
+      });
+      resultPool.closeWhenEmpty();
+      return resultPool.stream;
+    }
+
+    var resultController = new StreamController(sync: true);
+    resultPool.add(resultController.stream);
+    new Directory(dir).list(followLinks: followLinks).listen((entity) {
+      var basename = entity.path.substring(dir.length + 1);
+      if (_matches(basename)) resultController.add(entity);
+
+      children.forEach((sequence, child) {
+        if (!sequence.matches(basename)) return;
+        resultPool.add(child.list(p.join(dir, basename),

[Bob Nystrom, 2014/09/18 22:17:40]

Calling this recursively will create a tree of StreamControllers and
StreamPools, won't it?

[nweiz, 2014/09/22 23:48:40]

That's right, although it won't create more than are necessary.

[Bob Nystrom, 2014/09/23 00:22:04]

Isn't only one necessary? Couldn't you create a single one of each and pass them
into the recursive calls?

[nweiz, 2014/09/23 00:26:46]

I suppose so. It seems cleaner to me to keep the [list] API self-contained, so
I'd rather not do that without evidence that it'll make a substantial
performance difference.

+            followLinks: followLinks));
+      });
+    }, onError: (error, stackTrace) {
+      // Swallow FileSystemExceptions because nonexistent or unreadable
+      // directories should just not produce any entities rather than crashing
+      // the list.
+      if (error is FileSystemException) return;

[Bob Nystrom, 2014/09/18 22:17:40]

I don't understand the motivation here. If a raw Directory.list() call would
fail here, why shouldn't the glob list? If I glob a directory I don't have
access to, I want it to yell at me, not let me think the directory is empty.

[nweiz, 2014/09/22 23:48:40]

See above.

+      resultController.addError(error, stackTrace);
+    }, onDone: resultController.close);
+
+    resultPool.closeWhenEmpty();
+    return resultPool.stream;
+  }
+
+  /// Synchronously lists all entities within [dir] matching this node or its
+  /// children.
+  Iterable<FileSystemEntity> listSync(String dir, {bool followLinks: true}) {
+    try {
+      if (isRecursive) {
+        return new Directory(dir)
+            .listSync(recursive: true, followLinks: followLinks)
+            .where((entity) => _matches(entity.path.substring(dir.length + 1)));
+      }
+
+      // Don't spawn extra [Directory.listSync] calls when we already know exactly

[Bob Nystrom, 2014/09/18 22:17:40]

Long line.

[nweiz, 2014/09/22 23:48:40]

Done.

+      // which subdirectories we're interested in.
+      if (_isIntermediate) {
+        return children.keys.expand((sequence) {
+          return children[sequence].listSync(
+              p.join(dir, sequence.nodes.single.text), followLinks: followLinks);
+        });
+      }
+
+      return new Directory(dir).listSync(followLinks: followLinks)
+          .expand((entity) {
+        var entities = [];
+        var basename = entity.path.substring(dir.length + 1);
+        if (_matches(basename)) entities.add(entity);
+
+        entities.addAll(children.keys
+            .where((sequence) => sequence.matches(basename))
+            .expand((sequence) {
+          return children[sequence].listSync(
+              p.join(dir, basename), followLinks: followLinks);
+        }));
+
+        return entities;
+      });
+    } on FileSystemException catch (error) {
+      // Swallow FileSystemExceptions because nonexistent or unreadable
+      // directories should just not produce any entities rather than crashing
+      // the list.
+      return [];
+    }
+  }
+
+  /// Returns whether the native [path] matches [_validator].
+  bool _matches(String path) {
+    if (_validator == null) return false;
+    return _validator.matches(path);
+  }
+
+  String toString() => "($_validator) $children";
+}
+
+/// Joins each [components] into a new glob where each component is separated by
+/// a path separator.
+SequenceNode _join(Iterable<AstNode> components) {
+  var componentsList = components.toList();
+  var nodes = [componentsList.removeAt(0)];
+  for (var component in componentsList) {
+    nodes.add(new LiteralNode('/'));
+    nodes.add(component);
+  }
+  return new SequenceNode(nodes);
+}