lib/src/ignore.dart - pub - Git at Google

 // Copyright (c) 2020, 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.

 /// Implements an [Ignore] filter compatible with `.gitignore`.
 ///
 /// An [Ignore] instance holds a set of [`.gitignore` rules][1], and allows
 /// testing if a given path is ignored.
 ///
 /// **Example**:
 /// ```dart
 /// import 'package:ignore/ignore.dart';
 ///
 /// void main() {
 ///   final ignore = Ignore([
 ///     '*.o',
 ///   ]);
 ///
 ///   print(ignore.ignores('main.o')); // true
 ///   print(ignore.ignores('main.c')); // false
 /// }
 /// ```
 ///
 /// For a generic walk of a file-hierarchy with ignore files at all levels see
 /// [Ignore.listFiles].
 ///
 /// [1]: https://git-scm.com/docs/gitignore

 import 'package:meta/meta.dart';

 /// A set of ignore rules representing a single ignore file.
 ///
 /// An [Ignore] instance holds [`.gitignore` rules][1] relative to a given path.
 ///
 /// **Example**:
 /// ```dart
 /// import 'package:ignore/ignore.dart';
 ///
 /// void main() {
 ///   final ignore = Ignore([
 ///     '*.o',
 ///   ]);
 ///
 ///   print(ignore.ignores('main.o')); // true
 ///   print(ignore.ignores('main.c')); // false
 /// }
 /// ```
 ///
 /// [1]: https://git-scm.com/docs/gitignore
 @sealed
 class Ignore {
   final List<_IgnoreRule> _rules;

   /// Create an [Ignore] instance with a set of [`.gitignore` compatible][1]
   /// patterns.
   ///
   /// Each value in [patterns] will be interpreted as one or more lines from
   /// a `.gitignore` file, in compliance with the [`.gitignore` manual page][1].
   ///
   /// The keys of 'pattern' are the directories to intpret the rules relative
   /// to. The root should be the empty string, and sub-directories are separated
   /// by '/' (but no final '/').
   ///
   /// If [ignoreCase] is `true`, patterns will be case-insensitive. By default
   /// `git` is case-sensitive. But case insensitivity can be enabled when a
   /// repository is created, or by configuration option, see
   /// [`core.ignoreCase` documentation][2] for details.
   ///
   /// If [onInvalidPattern] is passed, it will be called with a
   /// [FormatException] describing the problem. The exception will have [source]
   /// as source.
   ///
   /// **Example**:
   /// ```dart
   /// import 'package:ignore/ignore.dart';
   /// void main() {
   ///   final ignore = Ignore({'': [
   ///     // You can pass an entire .gitignore file as a single string.
   ///     // You can also pass it as a list of lines, or both.
   ///     '''
   /// # Comment in a .gitignore file
   /// obj/
   /// *.o
   /// !main.o
   ///   '''
   ///   }]);
   ///
   ///   print(ignore.ignores('obj/README.md')); // true
   ///   print(ignore.ignores('lib.o')); // false
   ///   print(ignore.ignores('main.o')); // false
   /// }
   /// ```
   ///
   /// [1]: https://git-scm.com/docs/gitignore
   /// [2]: https://git-scm.com/docs/git-config#Documentation/git-config.txt-coreignoreCase
   Ignore(
     List<String> patterns, {
     bool ignoreCase = false,
     void Function(String pattern, FormatException exception)? onInvalidPattern,
   }) : _rules = _parseIgnorePatterns(
           patterns,
           ignoreCase,
           onInvalidPattern: onInvalidPattern,
         ).toList(growable: false);

   /// Returns `true` if [path] is ignored by the patterns used to create this
   /// [Ignore] instance, assuming those patterns are placed at `.`.
   ///
   /// The [path] must be a relative path, not starting with `./`, `../`, and
   /// must end in slash (`/`) if it is directory.
   ///
   /// **Example**:
   /// ```dart
   /// import 'package:ignore/ignore.dart';
   ///
   /// void main() {
   ///   final ignore = Ignore([
   ///     '*.o',
   ///   ]);
   ///
   ///   print(ignore.ignores('main.o')); // true
   ///   print(ignore.ignores('main.c')); // false
   ///   print(ignore.ignores('lib/')); // false
   ///   print(ignore.ignores('lib/helper.o')); // true
   ///   print(ignore.ignores('lib/helper.c')); // false
   /// }
   /// ```
   bool ignores(String path) {
     ArgumentError.checkNotNull(path, 'path');
     if (path.isEmpty) {
       throw ArgumentError.value(path, 'path', 'must be not empty');
     }
     if (path.startsWith('/') ||
         path.startsWith('./') ||
         path.startsWith('../') ||
         path == '.' ||
         path == '..') {
       throw ArgumentError.value(
         path,
         'path',
         'must be relative, and not start with "./", "../"',
       );
     }
     if (_rules.isEmpty) {
       return false;
     }
     final pathWithoutSlash =
         path.endsWith('/') ? path.substring(0, path.length - 1) : path;
     return listFiles(
       beneath: pathWithoutSlash,
       includeDirs: true, // because we are listing below pathWithoutSlash
       listDir: (dir) {
         // List the next part of path:
         if (dir == pathWithoutSlash) return [];
         final startOfNext = dir.isEmpty ? 0 : dir.length + 1;
         final nextSlash = path.indexOf('/', startOfNext);
         return [path.substring(startOfNext, nextSlash)];
       },
       ignoreForDir: (dir) => dir == '.' || dir.isEmpty ? this : null,
       isDir: (candidate) =>
           candidate == '.' ||
           candidate.isEmpty ||
           path.length > candidate.length && path[candidate.length] == '/',
     ).isEmpty;
   }

   /// Returns all the files in the tree under (and including) [beneath] not
   /// ignored by ignore-files from [root] and down.
   ///
   /// Represents paths normalized  using '/' as directory separator. The empty
   /// relative path is '.', no '..' are allowed.
   ///
   /// [beneath] must start with [root] and even if it is a directory it should not
   /// end with '/', if [beneath] is not provided, everything under root is
   /// included.
   ///
   /// [listDir] should enumerate the immediate contents of a given directory,
   /// returning paths including [root].
   ///
   /// [isDir] should return true if the argument is a directory. It will only be
   /// queried with file-names under (and including) [beneath]
   ///
   /// [ignoreForDir] should retrieve the ignore rules for a single directory
   /// or return `null` if there is no ignore rules.
   ///
   /// If [includeDirs] is true non-ignored directories will be included in the
   /// result (including beneath).
   ///
   /// This example program lists all files under second argument that are
   /// not ignored by .gitignore files from first argument and below:
   ///
   /// ```dart
   /// import 'dart:io';
   /// import 'package:path/path.dart' as p;
   /// import 'package:pub/src/ignore.dart';
   ///
   /// void main(List<String> args) {
   ///   var root = p.normalize(args[0]);
   ///   if (root == '.') root = '';
   ///   var beneath = args.length > 1 ? p.normalize(args[1]) : root;
   ///   if (beneath == '.') beneath = '';
   ///   String resolve(String path) {
   ///     return p.joinAll([root, ...p.posix.split(path)]);
   ///   }
   ///
   ///   Ignore.listFiles(
   ///     beneath: beneath,
   ///     listDir: (dir) => Directory(resolve(dir)).listSync().map((x) {
   ///        final relative = p.relative(x.path, from: root);
   ///       return p.posix.joinAll(p.split(relative));
   ///     }),
   ///     ignoreForDir: (dir) {
   ///       final f = File(resolve('dir/.gitignore'));
   ///       return f.existsSync() ? Ignore([f.readAsStringSync()]) : null;
   ///     },
   ///     isDir: (dir) => Directory(resolve(dir)).existsSync(),
   ///   ).forEach(print);
   /// }
   /// ```
   static List<String> listFiles({
     String beneath = '',
     required Iterable<String> Function(String) listDir,
     required Ignore? Function(String) ignoreForDir,
     required bool Function(String) isDir,
     bool includeDirs = false,
   }) {
     if (beneath.startsWith('/') ||
         beneath.startsWith('./') ||
         beneath.startsWith('../')) {
       throw ArgumentError.value(
           'must be relative and normalized', 'beneath', beneath);
     }
     if (beneath.endsWith('/')) {
       throw ArgumentError.value('must not end with /', beneath);
     }
     // To streamline the algorithm we represent all paths as starting with '/'
     // and the empty path as just '/'.
     if (beneath == '.') beneath = '';
     beneath = '/$beneath';

     // Will contain all the files that are not ignored.
     final result = <String>[];
     // At any given point in the search, this will contain the Ignores from
     // directories leading up to the current entity.
     // The single `null` aligns popping and pushing in this stack with [toVisit]
     // below.
     final ignoreStack = <_IgnorePrefixPair?>[null];
     // Find all ignores between './' and [beneath] (not inclusive).

     // [index] points at the next '/' in the path.
     var index = -1;
     while ((index = beneath.indexOf('/', index + 1)) != -1) {
       final partial = beneath.substring(0, index + 1);
       if (_matchesStack(ignoreStack, partial)) {
         // A directory on the way towards [beneath] was ignored. Empty result.
         return <String>[];
       }
       final ignore = ignoreForDir(
           partial == '/' ? '.' : partial.substring(1, partial.length - 1));
       ignoreStack
           .add(ignore == null ? null : _IgnorePrefixPair(ignore, partial));
     }
     // Do a depth first tree-search starting at [beneath].
     // toVisit is a stack containing all items that are waiting to be processed.
     final toVisit = [
       [beneath]
     ];
     while (toVisit.isNotEmpty) {
       final topOfStack = toVisit.last;
       if (topOfStack.isEmpty) {
         toVisit.removeLast();
         ignoreStack.removeLast();
         continue;
       }
       final current = topOfStack.removeLast();
       // This is the version of current we present to the callbacks and in
       // [result].
       //
       // The empty path is represented as '.' and there is no leading '/'.
       final normalizedCurrent = current == '/' ? '.' : current.substring(1);
       final currentIsDir = isDir(normalizedCurrent);
       if (_matchesStack(ignoreStack, currentIsDir ? '$current/' : current)) {
         // current was ignored. Continue with the next item.
         continue;
       }
       if (currentIsDir) {
         final ignore = ignoreForDir(normalizedCurrent);
         ignoreStack
             .add(ignore == null ? null : _IgnorePrefixPair(ignore, current));
         // Put all entities in current on the stack to be processed.
         toVisit.add(listDir(normalizedCurrent).map((x) => '/$x').toList());
         if (includeDirs) {
           result.add(normalizedCurrent);
         }
       } else {
         result.add(normalizedCurrent);
       }
     }
     return result;
   }
 }

 class _IgnoreParseResult {
   // The parsed pattern.
   final String pattern;

   // The resulting matching rule. `null` if the pattern was empty or invalid.
   final _IgnoreRule? rule;

   // An invalid pattern is also considered empty.
   bool get empty => rule == null;
   bool get valid => exception == null;

   // For invalid patterns this contains a description of the problem.
   final FormatException? exception;

   _IgnoreParseResult(this.pattern, this.rule) : exception = null;
   _IgnoreParseResult.invalid(this.pattern, this.exception) : rule = null;
   _IgnoreParseResult.empty(this.pattern)
       : rule = null,
         exception = null;
 }

 class _IgnoreRule {
   /// A regular expression that represents this rule.
   final RegExp pattern;
   final bool negative;

   /// The String this pattern was generated from.
   final String original;

   _IgnoreRule(this.pattern, this.negative, this.original);

   @override
   String toString() {
     // TODO: implement toString
     return '$original -> $pattern';
   }
 }

 /// Pattern for a line-break which accepts CR LF and LF.
 final _lineBreakPattern = RegExp('\r?\n');

 /// [onInvalidPattern] can be used to handle parse failures. If
 /// [onInvalidPattern] is `null` invalid patterns are ignored.
 Iterable<_IgnoreRule> _parseIgnorePatterns(
   Iterable<String> patterns,
   bool ignoreCase, {
   void Function(String pattern, FormatException exception)? onInvalidPattern,
 }) sync* {
   ArgumentError.checkNotNull(patterns, 'patterns');
   ArgumentError.checkNotNull(ignoreCase, 'ignoreCase');
   onInvalidPattern ??= (_, __) {};

   final parsedPatterns = patterns
       .expand((s) => s.split(_lineBreakPattern))
       .map((pattern) => _parseIgnorePattern(pattern, ignoreCase));

   for (final r in parsedPatterns) {
     if (!r.valid) {
       onInvalidPattern(r.pattern, r.exception!);
     }
     if (!r.empty) {
       yield r.rule!;
     }
   }
 }

 _IgnoreParseResult _parseIgnorePattern(String pattern, bool ignoreCase) {
   // Check if patterns is a comment
   if (pattern.startsWith('#')) {
     return _IgnoreParseResult.empty(pattern);
   }
   var first = 0;
   var end = pattern.length;

   // Detect negative patterns
   final negative = pattern.startsWith('!');
   if (negative) {
     first++;
   }

   // Remove trailing whitespace unless escaped
   while (end != 0 &&
       pattern[end - 1] == ' ' &&
       (end == 1 || pattern[end - 2] != '\\')) {
     end--;
   }
   // Empty patterns match nothing.
   if (first == end) return _IgnoreParseResult.empty(pattern);

   var current = first;
   String? peekChar() => current >= end ? null : pattern[current];

   var expr = '';

   // Parses the inside of a [] range. Returns the value as a RegExp character
   // range, or null if the pattern was broken.
   String? parseCharacterRange() {
     var characterRange = '';
     var first = true;
     for (;;) {
       final nextChar = peekChar();
       if (nextChar == null) {
         return null;
       }
       current++;
       if (nextChar == '\\') {
         final escaped = peekChar();
         if (escaped == null) {
           return null;
         }
         current++;

         characterRange += escaped == '-' ? r'\-' : RegExp.escape(escaped);
       } else if (nextChar == '!' && first) {
         characterRange += '^';
       } else if (nextChar == ']' && first) {
         characterRange += RegExp.escape(nextChar);
       } else if (nextChar == ']') {
         assert(!first);
         return characterRange;
       } else {
         characterRange += nextChar;
       }
       first = false;
     }
   }

   var relativeToPath = false;
   var matchesDirectoriesOnly = false;

   // slashes have different significance depending on where they are in
   // the String. Handle that here.
   void handleSlash() {
     if (current == end) {
       // A slash at the end makes us only match directories.
       matchesDirectoriesOnly = true;
     } else {
       // A slash anywhere else makes the pattern relative anchored at the
       // current path.
       relativeToPath = true;
     }
   }

   for (;;) {
     final nextChar = peekChar();
     if (nextChar == null) break;
     current++;
     if (nextChar == '*') {
       if (peekChar() == '*') {
         // Handle '**'
         current++;
         if (peekChar() == '/') {
           current++;
           if (current == end) {
             expr += '.*';
           } else {
             // Match nothing or a path followed by '/'
             expr += '(?:(?:)|(?:.*/))';
           }
           // Handle the side effects of seeing a slash.
           handleSlash();
         } else {
           expr += '.*';
         }
       } else if (peekChar() == '/' || peekChar() == null) {
         // /a/* should not match '/a/'
         expr += '[^/]+';
       } else {
         // Handle a single '*'
         expr += '[^/]*';
       }
     } else if (nextChar == '?') {
       // Handle '?'
       expr += '[^/]';
     } else if (nextChar == '[') {
       // Character ranges
       final characterRange = parseCharacterRange();
       if (characterRange == null) {
         return _IgnoreParseResult.invalid(
           pattern,
           FormatException(
               'Pattern "$pattern" had an invalid `[a-b]` style character range',
               pattern,
               current),
         );
       }
       expr += '[$characterRange]';
     } else if (nextChar == '\\') {
       // Escapes
       final escaped = peekChar();
       if (escaped == null) {
         return _IgnoreParseResult.invalid(
           pattern,
           FormatException(
               'Pattern "$pattern" end of pattern inside character escape.',
               pattern,
               current),
         );
       }
       expr += RegExp.escape(escaped);
       current++;
     } else {
       if (nextChar == '/') {
         if (current - 1 != first && current != end) {
           // If slash appears in the beginning we don't want it manifest in the
           // regexp.
           expr += '/';
         }
         handleSlash();
       } else {
         expr += RegExp.escape(nextChar);
       }
     }
   }
   if (relativeToPath) {
     expr = '^$expr';
   } else {
     expr = '(?:^|/)$expr';
   }
   if (matchesDirectoriesOnly) {
     expr = '$expr/\$';
   } else {
     expr = '$expr/?\$';
   }
   try {
     return _IgnoreParseResult(
         pattern,
         _IgnoreRule(
             RegExp(expr, caseSensitive: !ignoreCase), negative, pattern));
   } on FormatException catch (e) {
     throw AssertionError(
         'Created broken expression "$expr" from ignore pattern "$pattern" -> $e');
   }
 }

 /// A [Ignore] object, paired with the prefix where it is found in the directory
 /// hierarchy.
 class _IgnorePrefixPair {
   final Ignore ignore;
   final String prefix;
   _IgnorePrefixPair(this.ignore, this.prefix);
   @override
   String toString() {
     return '{${ignore._rules.map((r) => r.original)} $prefix}';
   }
 }

 /// Returns true if any of [ignores] has a match of [path] that is not negated
 /// by a later one.
 ///
 /// expects [path] to start with '/'
 ///
 /// If [path] should be matched as a directory, it should end with '/'.
 bool _matchesStack(List<_IgnorePrefixPair?> ignores, String path) {
   // This is optimized by trying the rules in reverse order.
   // If a rule matches, the result is true if the rule is not negative.
   for (final ignorePair in ignores.reversed) {
     if (ignorePair == null) continue;
     final prefixLength = ignorePair.prefix.length;
     final s =
         prefixLength == 0 ? path : path.substring(ignorePair.prefix.length);
     for (final rule in ignorePair.ignore._rules.reversed) {
       if (rule.pattern.hasMatch(s)) {
         return !rule.negative;
       }
     }
   }
   return false;
 }
	// Copyright (c) 2020, 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.

	/// Implements an [Ignore] filter compatible with `.gitignore`.
	///
	/// An [Ignore] instance holds a set of [`.gitignore` rules][1], and allows
	/// testing if a given path is ignored.
	///
	/// Example:
	/// ```dart
	/// import 'package:ignore/ignore.dart';
	///
	/// void main() {
	/// final ignore = Ignore([
	/// '*.o',
	/// ]);
	///
	/// print(ignore.ignores('main.o')); // true
	/// print(ignore.ignores('main.c')); // false
	/// }
	/// ```
	///
	/// For a generic walk of a file-hierarchy with ignore files at all levels see
	/// [Ignore.listFiles].
	///
	/// [1]: https://git-scm.com/docs/gitignore

	import 'package:meta/meta.dart';

	/// A set of ignore rules representing a single ignore file.
	///
	/// An [Ignore] instance holds [`.gitignore` rules][1] relative to a given path.
	///
	/// Example:
	/// ```dart
	/// import 'package:ignore/ignore.dart';
	///
	/// void main() {
	/// final ignore = Ignore([
	/// '*.o',
	/// ]);
	///
	/// print(ignore.ignores('main.o')); // true
	/// print(ignore.ignores('main.c')); // false
	/// }
	/// ```
	///
	/// [1]: https://git-scm.com/docs/gitignore
	@sealed
	class Ignore {
	final List<_IgnoreRule> _rules;

	/// Create an [Ignore] instance with a set of [`.gitignore` compatible][1]
	/// patterns.
	///
	/// Each value in [patterns] will be interpreted as one or more lines from
	/// a `.gitignore` file, in compliance with the [`.gitignore` manual page][1].
	///
	/// The keys of 'pattern' are the directories to intpret the rules relative
	/// to. The root should be the empty string, and sub-directories are separated
	/// by '/' (but no final '/').
	///
	/// If [ignoreCase] is `true`, patterns will be case-insensitive. By default
	/// `git` is case-sensitive. But case insensitivity can be enabled when a
	/// repository is created, or by configuration option, see
	/// [`core.ignoreCase` documentation][2] for details.
	///
	/// If [onInvalidPattern] is passed, it will be called with a
	/// [FormatException] describing the problem. The exception will have [source]
	/// as source.
	///
	/// Example:
	/// ```dart
	/// import 'package:ignore/ignore.dart';
	/// void main() {
	/// final ignore = Ignore({'': [
	/// // You can pass an entire .gitignore file as a single string.
	/// // You can also pass it as a list of lines, or both.
	/// '''
	/// # Comment in a .gitignore file
	/// obj/
	/// *.o
	/// !main.o
	/// '''
	/// }]);
	///
	/// print(ignore.ignores('obj/README.md')); // true
	/// print(ignore.ignores('lib.o')); // false
	/// print(ignore.ignores('main.o')); // false
	/// }
	/// ```
	///
	/// [1]: https://git-scm.com/docs/gitignore
	/// [2]: https://git-scm.com/docs/git-config#Documentation/git-config.txt-coreignoreCase
	Ignore(
	List<String> patterns, {
	bool ignoreCase = false,
	void Function(String pattern, FormatException exception)? onInvalidPattern,
	}) : _rules = _parseIgnorePatterns(
	patterns,
	ignoreCase,
	onInvalidPattern: onInvalidPattern,
	).toList(growable: false);

	/// Returns `true` if [path] is ignored by the patterns used to create this
	/// [Ignore] instance, assuming those patterns are placed at `.`.
	///
	/// The [path] must be a relative path, not starting with `./`, `../`, and
	/// must end in slash (`/`) if it is directory.
	///
	/// Example:
	/// ```dart
	/// import 'package:ignore/ignore.dart';
	///
	/// void main() {
	/// final ignore = Ignore([
	/// '*.o',
	/// ]);
	///
	/// print(ignore.ignores('main.o')); // true
	/// print(ignore.ignores('main.c')); // false
	/// print(ignore.ignores('lib/')); // false
	/// print(ignore.ignores('lib/helper.o')); // true
	/// print(ignore.ignores('lib/helper.c')); // false
	/// }
	/// ```
	bool ignores(String path) {
	ArgumentError.checkNotNull(path, 'path');
	if (path.isEmpty) {
	throw ArgumentError.value(path, 'path', 'must be not empty');
	}
	if (path.startsWith('/') \|\|
	path.startsWith('./') \|\|
	path.startsWith('../') \|\|
	path == '.' \|\|
	path == '..') {
	throw ArgumentError.value(
	path,
	'path',
	'must be relative, and not start with "./", "../"',
	);
	}
	if (_rules.isEmpty) {
	return false;
	}
	final pathWithoutSlash =
	path.endsWith('/') ? path.substring(0, path.length - 1) : path;
	return listFiles(
	beneath: pathWithoutSlash,
	includeDirs: true, // because we are listing below pathWithoutSlash
	listDir: (dir) {
	// List the next part of path:
	if (dir == pathWithoutSlash) return [];
	final startOfNext = dir.isEmpty ? 0 : dir.length + 1;
	final nextSlash = path.indexOf('/', startOfNext);
	return [path.substring(startOfNext, nextSlash)];
	},
	ignoreForDir: (dir) => dir == '.' \|\| dir.isEmpty ? this : null,
	isDir: (candidate) =>
	candidate == '.' \|\|
	candidate.isEmpty \|\|
	path.length > candidate.length && path[candidate.length] == '/',
	).isEmpty;
	}

	/// Returns all the files in the tree under (and including) [beneath] not
	/// ignored by ignore-files from [root] and down.
	///
	/// Represents paths normalized using '/' as directory separator. The empty
	/// relative path is '.', no '..' are allowed.
	///
	/// [beneath] must start with [root] and even if it is a directory it should not
	/// end with '/', if [beneath] is not provided, everything under root is
	/// included.
	///
	/// [listDir] should enumerate the immediate contents of a given directory,
	/// returning paths including [root].
	///
	/// [isDir] should return true if the argument is a directory. It will only be
	/// queried with file-names under (and including) [beneath]
	///
	/// [ignoreForDir] should retrieve the ignore rules for a single directory
	/// or return `null` if there is no ignore rules.
	///
	/// If [includeDirs] is true non-ignored directories will be included in the
	/// result (including beneath).
	///
	/// This example program lists all files under second argument that are
	/// not ignored by .gitignore files from first argument and below:
	///
	/// ```dart
	/// import 'dart:io';
	/// import 'package:path/path.dart' as p;
	/// import 'package:pub/src/ignore.dart';
	///
	/// void main(List<String> args) {
	/// var root = p.normalize(args[0]);
	/// if (root == '.') root = '';
	/// var beneath = args.length > 1 ? p.normalize(args[1]) : root;
	/// if (beneath == '.') beneath = '';
	/// String resolve(String path) {
	/// return p.joinAll([root, ...p.posix.split(path)]);
	/// }
	///
	/// Ignore.listFiles(
	/// beneath: beneath,
	/// listDir: (dir) => Directory(resolve(dir)).listSync().map((x) {
	/// final relative = p.relative(x.path, from: root);
	/// return p.posix.joinAll(p.split(relative));
	/// }),
	/// ignoreForDir: (dir) {
	/// final f = File(resolve('dir/.gitignore'));
	/// return f.existsSync() ? Ignore([f.readAsStringSync()]) : null;
	/// },
	/// isDir: (dir) => Directory(resolve(dir)).existsSync(),
	/// ).forEach(print);
	/// }
	/// ```
	static List<String> listFiles({
	String beneath = '',
	required Iterable<String> Function(String) listDir,
	required Ignore? Function(String) ignoreForDir,
	required bool Function(String) isDir,
	bool includeDirs = false,
	}) {
	if (beneath.startsWith('/') \|\|
	beneath.startsWith('./') \|\|
	beneath.startsWith('../')) {
	throw ArgumentError.value(
	'must be relative and normalized', 'beneath', beneath);
	}
	if (beneath.endsWith('/')) {
	throw ArgumentError.value('must not end with /', beneath);
	}
	// To streamline the algorithm we represent all paths as starting with '/'
	// and the empty path as just '/'.
	if (beneath == '.') beneath = '';
	beneath = '/$beneath';

	// Will contain all the files that are not ignored.
	final result = <String>[];
	// At any given point in the search, this will contain the Ignores from
	// directories leading up to the current entity.
	// The single `null` aligns popping and pushing in this stack with [toVisit]
	// below.
	final ignoreStack = <_IgnorePrefixPair?>[null];
	// Find all ignores between './' and [beneath] (not inclusive).

	// [index] points at the next '/' in the path.
	var index = -1;
	while ((index = beneath.indexOf('/', index + 1)) != -1) {
	final partial = beneath.substring(0, index + 1);
	if (_matchesStack(ignoreStack, partial)) {
	// A directory on the way towards [beneath] was ignored. Empty result.
	return <String>[];
	}
	final ignore = ignoreForDir(
	partial == '/' ? '.' : partial.substring(1, partial.length - 1));
	ignoreStack
	.add(ignore == null ? null : _IgnorePrefixPair(ignore, partial));
	}
	// Do a depth first tree-search starting at [beneath].
	// toVisit is a stack containing all items that are waiting to be processed.
	final toVisit = [
	[beneath]
	];
	while (toVisit.isNotEmpty) {
	final topOfStack = toVisit.last;
	if (topOfStack.isEmpty) {
	toVisit.removeLast();
	ignoreStack.removeLast();
	continue;
	}
	final current = topOfStack.removeLast();
	// This is the version of current we present to the callbacks and in
	// [result].
	//
	// The empty path is represented as '.' and there is no leading '/'.
	final normalizedCurrent = current == '/' ? '.' : current.substring(1);
	final currentIsDir = isDir(normalizedCurrent);
	if (_matchesStack(ignoreStack, currentIsDir ? '$current/' : current)) {
	// current was ignored. Continue with the next item.
	continue;
	}
	if (currentIsDir) {
	final ignore = ignoreForDir(normalizedCurrent);
	ignoreStack
	.add(ignore == null ? null : _IgnorePrefixPair(ignore, current));
	// Put all entities in current on the stack to be processed.
	toVisit.add(listDir(normalizedCurrent).map((x) => '/$x').toList());
	if (includeDirs) {
	result.add(normalizedCurrent);
	}
	} else {
	result.add(normalizedCurrent);
	}
	}
	return result;
	}
	}

	class _IgnoreParseResult {
	// The parsed pattern.
	final String pattern;

	// The resulting matching rule. `null` if the pattern was empty or invalid.
	final _IgnoreRule? rule;

	// An invalid pattern is also considered empty.
	bool get empty => rule == null;
	bool get valid => exception == null;

	// For invalid patterns this contains a description of the problem.
	final FormatException? exception;

	_IgnoreParseResult(this.pattern, this.rule) : exception = null;
	_IgnoreParseResult.invalid(this.pattern, this.exception) : rule = null;
	_IgnoreParseResult.empty(this.pattern)
	: rule = null,
	exception = null;
	}

	class _IgnoreRule {
	/// A regular expression that represents this rule.
	final RegExp pattern;
	final bool negative;

	/// The String this pattern was generated from.
	final String original;

	_IgnoreRule(this.pattern, this.negative, this.original);

	@override
	String toString() {
	// TODO: implement toString
	return '$original -> $pattern';
	}
	}

	/// Pattern for a line-break which accepts CR LF and LF.
	final _lineBreakPattern = RegExp('\r?\n');

	/// [onInvalidPattern] can be used to handle parse failures. If
	/// [onInvalidPattern] is `null` invalid patterns are ignored.
	Iterable<_IgnoreRule> _parseIgnorePatterns(
	Iterable<String> patterns,
	bool ignoreCase, {
	void Function(String pattern, FormatException exception)? onInvalidPattern,
	}) sync* {
	ArgumentError.checkNotNull(patterns, 'patterns');
	ArgumentError.checkNotNull(ignoreCase, 'ignoreCase');
	onInvalidPattern ??= (_, __) {};

	final parsedPatterns = patterns
	.expand((s) => s.split(_lineBreakPattern))
	.map((pattern) => _parseIgnorePattern(pattern, ignoreCase));

	for (final r in parsedPatterns) {
	if (!r.valid) {
	onInvalidPattern(r.pattern, r.exception!);
	}
	if (!r.empty) {
	yield r.rule!;
	}
	}
	}

	_IgnoreParseResult _parseIgnorePattern(String pattern, bool ignoreCase) {
	// Check if patterns is a comment
	if (pattern.startsWith('#')) {
	return _IgnoreParseResult.empty(pattern);
	}
	var first = 0;
	var end = pattern.length;

	// Detect negative patterns
	final negative = pattern.startsWith('!');
	if (negative) {
	first++;
	}

	// Remove trailing whitespace unless escaped
	while (end != 0 &&
	pattern[end - 1] == ' ' &&
	(end == 1 \|\| pattern[end - 2] != '\\')) {
	end--;
	}
	// Empty patterns match nothing.
	if (first == end) return _IgnoreParseResult.empty(pattern);

	var current = first;
	String? peekChar() => current >= end ? null : pattern[current];

	var expr = '';

	// Parses the inside of a [] range. Returns the value as a RegExp character
	// range, or null if the pattern was broken.
	String? parseCharacterRange() {
	var characterRange = '';
	var first = true;
	for (;;) {
	final nextChar = peekChar();
	if (nextChar == null) {
	return null;
	}
	current++;
	if (nextChar == '\\') {
	final escaped = peekChar();
	if (escaped == null) {
	return null;
	}
	current++;

	characterRange += escaped == '-' ? r'\-' : RegExp.escape(escaped);
	} else if (nextChar == '!' && first) {
	characterRange += '^';
	} else if (nextChar == ']' && first) {
	characterRange += RegExp.escape(nextChar);
	} else if (nextChar == ']') {
	assert(!first);
	return characterRange;
	} else {
	characterRange += nextChar;
	}
	first = false;
	}
	}

	var relativeToPath = false;
	var matchesDirectoriesOnly = false;

	// slashes have different significance depending on where they are in
	// the String. Handle that here.
	void handleSlash() {
	if (current == end) {
	// A slash at the end makes us only match directories.
	matchesDirectoriesOnly = true;
	} else {
	// A slash anywhere else makes the pattern relative anchored at the
	// current path.
	relativeToPath = true;
	}
	}

	for (;;) {
	final nextChar = peekChar();
	if (nextChar == null) break;
	current++;
	if (nextChar == '*') {
	if (peekChar() == '*') {
	// Handle '**'
	current++;
	if (peekChar() == '/') {
	current++;
	if (current == end) {
	expr += '.*';
	} else {
	// Match nothing or a path followed by '/'
	expr += '(?:(?:)\|(?:.*/))';
	}
	// Handle the side effects of seeing a slash.
	handleSlash();
	} else {
	expr += '.*';
	}
	} else if (peekChar() == '/' \|\| peekChar() == null) {
	// /a/* should not match '/a/'
	expr += '[^/]+';
	} else {
	// Handle a single '*'
	expr += '[^/]*';
	}
	} else if (nextChar == '?') {
	// Handle '?'
	expr += '[^/]';
	} else if (nextChar == '[') {
	// Character ranges
	final characterRange = parseCharacterRange();
	if (characterRange == null) {
	return _IgnoreParseResult.invalid(
	pattern,
	FormatException(
	'Pattern "$pattern" had an invalid `[a-b]` style character range',
	pattern,
	current),
	);
	}
	expr += '[$characterRange]';
	} else if (nextChar == '\\') {
	// Escapes
	final escaped = peekChar();
	if (escaped == null) {
	return _IgnoreParseResult.invalid(
	pattern,
	FormatException(
	'Pattern "$pattern" end of pattern inside character escape.',
	pattern,
	current),
	);
	}
	expr += RegExp.escape(escaped);
	current++;
	} else {
	if (nextChar == '/') {
	if (current - 1 != first && current != end) {
	// If slash appears in the beginning we don't want it manifest in the
	// regexp.
	expr += '/';
	}
	handleSlash();
	} else {
	expr += RegExp.escape(nextChar);
	}
	}
	}
	if (relativeToPath) {
	expr = '^$expr';
	} else {
	expr = '(?:^\|/)$expr';
	}
	if (matchesDirectoriesOnly) {
	expr = '$expr/\$';
	} else {
	expr = '$expr/?\$';
	}
	try {
	return _IgnoreParseResult(
	pattern,
	_IgnoreRule(
	RegExp(expr, caseSensitive: !ignoreCase), negative, pattern));
	} on FormatException catch (e) {
	throw AssertionError(
	'Created broken expression "$expr" from ignore pattern "$pattern" -> $e');
	}
	}

	/// A [Ignore] object, paired with the prefix where it is found in the directory
	/// hierarchy.
	class _IgnorePrefixPair {
	final Ignore ignore;
	final String prefix;
	_IgnorePrefixPair(this.ignore, this.prefix);
	@override
	String toString() {
	return '{${ignore._rules.map((r) => r.original)} $prefix}';
	}
	}

	/// Returns true if any of [ignores] has a match of [path] that is not negated
	/// by a later one.
	///
	/// expects [path] to start with '/'
	///
	/// If [path] should be matched as a directory, it should end with '/'.
	bool _matchesStack(List<_IgnorePrefixPair?> ignores, String path) {
	// This is optimized by trying the rules in reverse order.
	// If a rule matches, the result is true if the rule is not negative.
	for (final ignorePair in ignores.reversed) {
	if (ignorePair == null) continue;
	final prefixLength = ignorePair.prefix.length;
	final s =
	prefixLength == 0 ? path : path.substring(ignorePair.prefix.length);
	for (final rule in ignorePair.ignore._rules.reversed) {
	if (rule.pattern.hasMatch(s)) {
	return !rule.negative;
	}
	}
	}
	return false;
	}