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