Create a 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
new file mode 100644
index 0000000000000000000000000000000000000000..f0eba2108b140215fc50aab5d5dc0b83dcbdff28
--- /dev/null
+++ b/pkg/glob/lib/src/ast.dart
@@ -0,0 +1,204 @@
+// 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 {

[Bob Nystrom, 2014/08/27 00:42:04]

Instead of actually parsing to an AST and then compiling that down to a RegExp
in a separate step, how about having the parser just accumulate the result as it
goes along? There's no real reason to keep the AST around after generating the
RegExp is done, is there?

[nweiz, 2014/08/27 01:36:33]

Checking for absolute vs relative globs uses the AST. Listing will also use it.

[Bob Nystrom, 2014/08/27 22:16:44]

Sure, but you could bubble that up at parse time and just store that in the
Glob.

I don't see much use in keeping the entire tree around when its immutable and
only contains a few fields. For example, each tree node calculates and caches
its _regExp, but you only need the top-level one, right?

I think it would be simpler (and certainly more memory efficient) to treat it
more like a builder pattern and either flatten as you go while parsing or
flatten once you're done and then discard the tree.
I guess I'd have to see the details here.

[nweiz, 2014/09/02 19:48:15]

No; only the top-level AST node caches its RegExp. The rest are generated using
[AstNode._toRegExp], which doesn't cache.
Once listing exists, it will compile the AST to a completely different data
structure. I don't want to do both the RegExp compilation and the listing
compilation when the glob is first created, since probably only one of them will
be used. I could add some logic to ditch the AST if both of the compilations
*are* done, but that doesn't seem worth the complexity.

[Bob Nystrom, 2014/09/02 20:23:50]

SGTM.

+  /// The cached regular expression that this AST was compiled into.
+  RegExp _regExp;
+
+  /// Whether this glob could match an absolute path.
+  ///
+  /// Either this or [couldBeRelative] or both will be true.
+  final bool couldBeAbsolute = false;
+
+  /// Whether this glob could match a relative path.
+  ///
+  /// Either this or [couldBeRelative] or both will be true.
+  final bool couldBeRelative = true;
+
+  /// 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 couldBeAbsolute => nodes.first.couldBeAbsolute;
+  bool get couldBeRelative => nodes.first.couldBeRelative;
+
+  SequenceNode(Iterable<AstNode> nodes)
+      : nodes = nodes.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() => '[^/]*';
+
+  String toString() => '*';
+}
+
+/// A node matching zero or more characters that may be separators.
+class DoubleStarNode extends AstNode {
+  /// The path context for the glob.
+  ///
+  /// This is used to determine what absolute paths look like.
+  final p.Context _context;
+
+  DoubleStarNode(this._context);
+
+  String _toRegExp() {
+    // Double star shouldn't match paths with a leading "../", since these paths
+    // wouldn't be listed with this glob. We only check for "../" at the
+    // beginning since the paths are normalized before being checked against the
+    // glob.
+    var buffer = new StringBuffer()..write(r'(?!^(?:\.\./|');
+
+    // A double star at the beginning of the glob also shouldn't match absolute
+    // paths, since those also wouldn't be listed. Which root patterns we look
+    // for depends on the style of path we're matching.
+    if (_context.style == p.Style.posix) {
+      buffer.write(r'/');
+    } else if (_context.style == p.Style.windows) {
+      buffer.write(r'//|[A-Za-z]:/');
+    } else {
+      assert(_context.style == p.Style.url);
+      buffer.write(r'[a-zA-Z][-+.a-zA-Z\d]*://|/');
+    }
+
+    // Use `[^]` rather than `.` so that it matches newlines as well.
+    buffer.write(r'))[^]*');
+
+    return buffer.toString();
+  }
+
+  String toString() => '**';
+}
+
+/// A node matching a single non-separator character.
+class AnyCharNode extends AstNode {
+  AnyCharNode();
+
+  String _toRegExp() => '[^/]';
+
+  String toString() => '?';
+}
+
+/// A node matching a single character in a range of options.
+class RangeNode extends AstNode {
+  /// The ranges matched by this node.
+  ///
+  /// 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();
+
+  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('[');
+    if (negated) {
+      buffer.write('^');
+      // If the range doesn't itself exclude separators, exclude them ourselves,
+      // since ranges are never allowed to match them.
+      if (!containsSeparator) buffer.write('/');
+    }
+
+    for (var range in ranges) {
+      var start = new String.fromCharCodes([range.min]);
+      buffer.write(regExpQuote(start));
+      if (range.isSingleton) continue;
+      buffer.write('-');
+      buffer.write(regExpQuote(new String.fromCharCodes([range.max])));
+    }
+
+    buffer.write(']');
+    return buffer.toString();
+  }
+
+  String toString() {
+    var buffer = new StringBuffer()..write('[');
+    for (var range in ranges) {
+      buffer.writeCharCode(range.min);
+      if (range.isSingleton) continue;
+      buffer.write('-');
+      buffer.writeCharCode(range.max);
+    }
+    buffer.write(']');
+    return buffer.toString();
+  }
+}
+
+/// A node that matches one of several options.
+class OptionsNode extends AstNode {
+  /// The options to match.
+  final List<SequenceNode> options;

[Bob Nystrom, 2014/08/27 00:42:04]

Why not AstNode?

[nweiz, 2014/08/27 01:36:33]

Because in practice they're always SequenceNodes and making that explicit can
simplify manipulation logic.

+
+  bool get couldBeAbsolute => options.any((node) => node.couldBeAbsolute);
+  bool get couldBeRelative => options.any((node) => node.couldBeRelative);
+
+  OptionsNode(Iterable<SequenceNode> options)
+      : options = options.toList();
+
+  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 couldBeAbsolute {
+    var nativeText = _context.style == p.Style.windows ?
+        text.replaceAll('/', '\\') : text;
+    return _context.isAbsolute(nativeText);
+  }
+
+  bool get couldBeRelative => !couldBeAbsolute;
+
+  LiteralNode(this.text, this._context);
+
+  String _toRegExp() => regExpQuote(text);
+
+  String toString() => text;
+}