Add support for listing to the glob package.

pkg/glob/lib/src/ast.dart

Index: pkg/glob/lib/src/ast.dart
diff --git a/pkg/glob/lib/src/ast.dart b/pkg/glob/lib/src/ast.dart
index 5e1da1a72c2fddff8fac2c64c6f3d132d8c0c0f9..d49b7af6a0d4e7f474fb5cc763be89aefa21985d 100644
--- a/pkg/glob/lib/src/ast.dart
+++ b/pkg/glob/lib/src/ast.dart
@@ -25,6 +25,14 @@ abstract class AstNode {
   /// Either this or [canMatchRelative] or both will be true.
   final bool canMatchRelative = true;
 
+  /// Returns a new glob with all the options bubbled to the top level.
+  ///
+  /// In particular, this returns a glob AST with two guarantees:
+  ///
+  /// 1. There are no [OptionsNode]s other than the one at the top level.
+  /// 2. It matches the same set of paths as [this].
+  OptionsNode expand() => new OptionsNode([new SequenceNode([this])]);

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

How about "flattenOptions"? Using the same name as Iterable.expand() makes the
method below super hard to read.

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

Done.

+
   /// Returns whether this glob matches [string].
   bool matches(String string) {
     if (_regExp == null) _regExp = new RegExp('^${_toRegExp()}\$');
@@ -46,6 +54,87 @@ class SequenceNode extends AstNode {
   SequenceNode(Iterable<AstNode> nodes)
       : nodes = nodes.toList();
 
+  OptionsNode expand() {
+    if (nodes.isEmpty) return new OptionsNode([this]);
+
+    var sequences = nodes.first.expand().options;
+    for (var node in nodes.skip(1)) {
+      var nextSequences = node.expand().options;
+      sequences = sequences.expand((sequence) {
+        return nextSequences.map((nextSequence) {

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

A loop containing an expand call that's mapping each item from the outer loop
that imperatively modifies a collection from the outer loop... this is pretty
much impenetrable.

Is this just concatenating the result of .expand() on all of the child nodes and
then combining adjacent literals? Can you do that in two passes?

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

Done.

+          var next = nextSequence.nodes.toList();
+          var combined = sequence.nodes.toList();
+
+          // Combine adjacent LiteralNodes.
+          if (!combined.isEmpty && !next.isEmpty &&
+              combined.last is LiteralNode && next.first is LiteralNode) {
+            combined[combined.length - 1] =
+                new LiteralNode(combined.last.text + next.removeAt(0).text);
+          }
+
+          return new SequenceNode(combined..addAll(next));
+        });
+      });
+    }
+    return new OptionsNode(sequences.toList());
+  }
+
+  /// Splits this glob into components along its path separators.

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

A before/after example would help a lot here.

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

Done.

+  ///
+  /// This should only be called once the glob has been [expand]ed. [context] is

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

If this is only valid on certain states, maybe it would be cleaner to have a
separate type to represent an expanded AstNode? Basically compile it to an IR?

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

Rather than doing that (which I think would add a lot of boilerplate for
relatively little benefit), I'll just allow options here and document that it
won't split on separators contained in them.

+  /// used to determine what absolute roots look like for this glob.
+  List<SequenceNode> split(p.Context context) {
+    // The inner list represents a [SequenceNode] for a single path component;
+    // the outer list is the list of components.
+    var sequences = [[]];

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

I think this code will be easier to read if you add the component list to the
outer list after its finished instead of right when you start. Something like:

var components = [];
var sequence;

addNode(node) {
  if (sequence == null) sequence = [];
  sequence.add(node);
}

finishComponent() {
  components.add(new SequenceNode(sequence));
  sequence = null;
}

And then use these.

I found just doing a bunch of iterable method calls on a untyped nested list to
be hard to reason about.

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

Done.

+
+    for (var node in nodes) {
+      // This should only be called after [expand].
+      assert(node is! OptionsNode);
+
+      if (node is! LiteralNode || !node.text.contains('/')) {
+        sequences.last.add(node);
+        continue;
+      }
+
+      var text = node.text;
+      if (context.style == p.Style.windows) text.replaceAll("/", "\\");
+      var components = context.split(text);

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

"nodeComponents"?

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

This is referenced a lot more often than the previous variable, so I'd rather
give it the shorter name.

+
+      // If the first component is absolute, that means it's a separator (on
+      // Windows some non-separator things are also absolute, but it's invalid
+      // to have "C:" show up in the middle of a path anyway).
+      if (context.isAbsolute(components.first)) {
+        // If this is the first component, it's the root.
+        if (sequences.length == 1 && sequences.first.isEmpty) {
+          var root = components.first;
+          if (context.style == p.Style.windows) {
+            root = root.replaceAll("\\", "/");

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

Why switch to forward slashes on Windows?

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

Above, we switched to backslashes to make [context.split] handle roots properly.
That means that if there is a root, it'll still have backslashes, where forward
slashes are required for globs. So we switch it back here.

Added a comment explaining that.

+          }
+          sequences.last.add(new LiteralNode(root));
+        }
+        sequences.add([]);
+        components = components.skip(1);
+        if (components.isEmpty) continue;
+      }
+
+      // For each component except the last one, add a separate sequence to
+      // [sequences] containing only that component.
+      for (var component in components.take(components.length - 1)) {
+        sequences.last.add(new LiteralNode(component));
+        sequences.add([]);
+      }
+
+      // For the final component, only end its sequence (by adding a new empty
+      // sequence) if it ends with a separator.
+      sequences.last.add(new LiteralNode(components.last));
+      if (node.text.endsWith('/')) sequences.add([]);
+    }
+
+    if (sequences.last.isEmpty) sequences.removeLast();
+    return sequences.map((sequence) => new SequenceNode(sequence)).toList();
+  }
+
   String _toRegExp() => nodes.map((node) => node._toRegExp()).join();
 
   String toString() => nodes.join();
@@ -119,6 +208,20 @@ class RangeNode extends AstNode {
   RangeNode(Iterable<Range> ranges, {this.negated})
       : ranges = ranges.toSet();
 
+  OptionsNode expand() {
+    if (negated || ranges.any((range) => !range.isSingleton)) {
+      return super.expand();
+    }
+
+    // If a range explicitly lists a set of characters, return each character as
+    // a separate expansion.
+    return new OptionsNode(ranges.map((range) {
+      return new SequenceNode([
+        new LiteralNode(new String.fromCharCodes([range.min]))
+      ]);
+    }));
+  }
+
   String _toRegExp() {
     var buffer = new StringBuffer();
 
@@ -172,6 +275,9 @@ class OptionsNode extends AstNode {
   OptionsNode(Iterable<SequenceNode> options)
       : options = options.toList();
 
+  OptionsNode expand() =>
+      new OptionsNode(options.expand((option) => option.expand().options));
+
   String _toRegExp() =>
       '(?:${options.map((option) => option._toRegExp()).join("|")})';
 
@@ -196,7 +302,7 @@ class LiteralNode extends AstNode {
 
   bool get canMatchRelative => !canMatchAbsolute;
 
-  LiteralNode(this.text, this._context);
+  LiteralNode(this.text, [this._context]);
 
   String _toRegExp() => regExpQuote(text);