Add support for listing to the glob package.

pkg/glob/lib/src/ast.dart

 // 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.ast;
 
 import 'package:path/path.dart' as p;
 
 import 'utils.dart';
 
 const _SEPARATOR = 0x2F; // "/"
 
 /// A node in the abstract syntax tree for a glob.
 abstract class AstNode {
   /// The cached regular expression that this AST was compiled into.
   RegExp _regExp;
 
   /// Whether this glob could match an absolute path.
   ///
   /// Either this or [canMatchRelative] or both will be true.
   final bool canMatchAbsolute = false;
 
   /// Whether this glob could match a relative path.
   ///
   /// 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()}\$');
     return _regExp.hasMatch(string);
   }
 
   /// Subclasses should override this to return a regular expression component.
   String _toRegExp();
 }
 
 /// A sequence of adjacent AST nodes.
 class SequenceNode extends AstNode {
   /// The nodes in the sequence.
   final List<AstNode> nodes;
 
   bool get canMatchAbsolute => nodes.first.canMatchAbsolute;
   bool get canMatchRelative => nodes.first.canMatchRelative;
 
   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();
 }
 
 /// A node matching zero or more non-separator characters.
 class StarNode extends AstNode {
   StarNode();
 
   String _toRegExp() => '[^/]*';
@@ skipping 53 matching lines @@
   ///
   /// The ends of the ranges are unicode code points.
   final Set<Range> ranges;
 
   /// Whether this range was negated.
   final bool negated;
 
   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();
 
     var containsSeparator = ranges.any((range) => range.contains(_SEPARATOR));
     if (!negated && containsSeparator) {
       // Add `(?!/)` because ranges are never allowed to match separators.
       buffer.write('(?!/)');
     }
 
     buffer.write('[');
@@ skipping 33 matching lines @@
 class OptionsNode extends AstNode {
   /// The options to match.
   final List<SequenceNode> options;
 
   bool get canMatchAbsolute => options.any((node) => node.canMatchAbsolute);
   bool get canMatchRelative => options.any((node) => node.canMatchRelative);
 
   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("|")})';
 
   String toString() => '{${options.join(',')}}';
 }
 
 /// A node that matches a literal string.
 class LiteralNode extends AstNode {
   /// The string to match.
   final String text;
 
   /// The path context for the glob.
   ///
   /// This is used to determine whether this could match an absolute path.
   final p.Context _context;
 
   bool get canMatchAbsolute {
     var nativeText = _context.style == p.Style.windows ?
         text.replaceAll('/', '\\') : text;
     return _context.isAbsolute(nativeText);
   }
 
   bool get canMatchRelative => !canMatchAbsolute;
 
-  LiteralNode(this.text, this._context);
+  LiteralNode(this.text, [this._context]);
 
   String _toRegExp() => regExpQuote(text);
 
   String toString() => text;
 }