pkgs/glob/lib/src/list_tree.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.

import 'dart:async';

import 'package:async/async.dart';
import 'package:file/file.dart';
import 'package:path/path.dart' as p;

import 'ast.dart';
import 'utils.dart';

/// The errno for a file or directory not existing on Mac and Linux.
const _enoent = 2;

/// Another errno we see on Windows when trying to list a non-existent
/// directory.
const _enoentWin = 3;

/// A structure built from a glob that efficiently lists filesystem entities
/// that match that glob.
///
/// This structure is designed to list the minimal number of physical
/// directories necessary to find everything that matches the glob. For example,
/// for the glob `foo/{bar,baz}/*`, there's no need to list the working
/// directory or even `foo/`; only `foo/bar` and `foo/baz` should be listed.
///
/// This works by creating a tree of [_ListTreeNode]s, each of which corresponds
/// to a single of directory nesting in the source glob. Each node has child
/// nodes associated with globs ([_ListTreeNode.children]), as well as its own
/// glob ([_ListTreeNode._validator]) that indicates which entities within that
/// node's directory should be returned.
///
/// For example, the glob `foo/{*.dart,b*/*.txt}` creates the following tree:
///
///     .
///     '-- "foo" (validator: "*.dart")
///         '-- "b*" (validator: "*.txt"
///
/// If a node doesn't have a validator, we know we don't have to list it
/// explicitly.
///
/// Nodes can also be marked as "recursive", which means they need to be listed
/// recursively (usually to support `**`). In this case, they will have no
/// children; instead, their validator will just encompass the globs that would
/// otherwise be in their children. For example, the glob
/// `foo/{**.dart,bar/*.txt}` creates a recursive node for `foo` with the
/// validator `**.dart,bar/*.txt`.
///
/// If the glob contains multiple filesystem roots (e.g. `{C:/,D:/}*.dart`),
/// each root will have its own tree of nodes. Relative globs use `.` as their
/// root instead.
class ListTree {
  /// A map from filesystem roots to the list tree for those roots.
  ///
  /// A relative glob will use `.` as its root.
  final Map<String, _ListTreeNode> _trees;

  /// Whether paths listed might overlap.
  ///
  /// If they do, we need to filter out overlapping paths.
  final bool _canOverlap;

  /// The file system to operate on.
  final FileSystem _fileSystem;

  ListTree._(this._trees, this._fileSystem)
      : _canOverlap = _computeCanOverlap(_trees);

  factory ListTree(AstNode glob, FileSystem fileSystem) {
    // The first step in constructing a tree from the glob is to simplify the
    // problem by eliminating options. [glob.flattenOptions] bubbles all options
    // (and certain ranges) up to the top level of the glob so we can deal with
    // them one at a time.
    var options = glob.flattenOptions();
    var trees = <String, _ListTreeNode>{};

    for (var option in options.options) {
      // Since each option doesn't include its own options, we can safely split
      // it into path components.
      var components = option.split(p.context);
      var firstNode = components.first.nodes.first;
      var root = '.';

      // Determine the root for this option, if it's absolute. If it's not, the
      // root's just ".".
      if (firstNode is LiteralNode) {
        var text = firstNode.text;
        // Platform agnostic way of checking for Windows without `dart:io`.
        if (p.context == p.windows) text.replaceAll('/', '\\');
        if (p.isAbsolute(text)) {
          // If the path is absolute, the root should be the only thing in the
          // first component.
          assert(components.first.nodes.length == 1);
          root = firstNode.text;
          components.removeAt(0);
        }
      }

      _addGlob(root, components, trees);
    }

    return ListTree._(trees, fileSystem);
  }

  /// Add the glob represented by [components] to the tree under [root].
  static void _addGlob(String root, List<SequenceNode> components,
      Map<String, _ListTreeNode> trees) {
    // The first [parent] represents the root directory itself. It may be null
    // here if this is the first option with this particular [root]. If so,
    // we'll create it below.
    //
    // As we iterate through [components], [parent] will be set to
    // progressively more nested nodes.
    var parent = trees[root];
    for (var i = 0; i < components.length; i++) {
      var component = components[i];
      var recursive = component.nodes.any((node) => node is DoubleStarNode);
      var complete = i == components.length - 1;

      // If the parent node for this level of nesting already exists, the new
      // option will be added to it as additional validator options and/or
      // additional children.
      //
      // If the parent doesn't exist, we'll create it in one of the else
      // clauses below.
      if (parent != null) {
        if (parent.isRecursive || recursive) {
          // If [component] is recursive, mark [parent] as recursive. This
          // will cause all of its children to be folded into its validator.
          // If [parent] was already recursive, this is a no-op.
          parent.makeRecursive();

          // Add [component] and everything nested beneath it as an option to
          // [parent]. Since [parent] is recursive, it will recursively list
          // everything beneath it and filter them with one big glob.
          parent.addOption(_join(components.sublist(i)));
          return;
        } else if (complete) {
          // If [component] is the last component, add it to [parent]'s
          // validator but not to its children.
          parent.addOption(component);
        } else {
          // On the other hand if there are more components, add [component]
          // to [parent]'s children and not its validator. Since we process
          // each option's components separately, the same component is never
          // both a validator and a child.
          var children = parent.children!;
          if (!children.containsKey(component)) {
            children[component] = _ListTreeNode();
          }
          parent = children[component];
        }
      } else if (recursive) {
        trees[root] = _ListTreeNode.recursive(_join(components.sublist(i)));
        return;
      } else if (complete) {
        trees[root] = _ListTreeNode()..addOption(component);
      } else {
        var rootNode = _ListTreeNode();
        trees[root] = rootNode;
        var rootChildren = rootNode.children!;
        rootChildren[component] = _ListTreeNode();
        parent = rootChildren[component];
      }
    }
  }

  /// Computes the value for [_canOverlap].
  static bool _computeCanOverlap(Map<String, _ListTreeNode> trees) {
    // If this can list a relative path and an absolute path, the former may be
    // contained within the latter.
    if (trees.length > 1 && trees.containsKey('.')) return true;

    // Otherwise, this can only overlap if the tree beneath any given root could
    // overlap internally.
    return trees.values.any((node) => node.canOverlap);
  }

  /// List all entities that match this glob beneath [root].
  Stream<FileSystemEntity> list({String? root, bool followLinks = true}) {
    root ??= '.';
    var group = StreamGroup<FileSystemEntity>();
    for (var rootDir in _trees.keys) {
      var dir = rootDir == '.' ? root : rootDir;
      group.add(
          _trees[rootDir]!.list(dir, _fileSystem, followLinks: followLinks));
    }
    group.close();

    if (!_canOverlap) return group.stream;

    // TODO: Rather than filtering here, avoid double-listing directories
    // in the first place.
    var seen = <String>{};
    return group.stream.where((entity) => seen.add(entity.path));
  }

  /// Synchronosuly list all entities that match this glob beneath [root].
  List<FileSystemEntity> listSync({String? root, bool followLinks = true}) {
    root ??= '.';
    var result = _trees.keys.expand((rootDir) {
      var dir = rootDir == '.' ? root! : rootDir;
      return _trees[rootDir]!
          .listSync(dir, _fileSystem, followLinks: followLinks);
    });

    if (!_canOverlap) return result.toList();

    // TODO: Rather than filtering here, avoid double-listing directories
    // in the first place.
    var seen = <String>{};
    return result.where((entity) => seen.add(entity.path)).toList();
  }
}

/// A single node in a [ListTree].
class _ListTreeNode {
  /// This node's child nodes, by their corresponding globs.
  ///
  /// Each child node will only be listed on directories that match its glob.
  ///
  /// This may be `null`, indicating that this node should be listed
  /// recursively.
  Map<SequenceNode, _ListTreeNode>? children;

  /// This node's validator.
  ///
  /// This determines which entities will ultimately be emitted when [list] is
  /// called.
  OptionsNode? _validator;

  /// Whether this node is recursive.
  ///
  /// A recursive node has no children and is listed recursively.
  bool get isRecursive => children == null;

  bool get _caseSensitive {
    if (_validator != null) return _validator!.caseSensitive;
    if (children?.isEmpty != false) return true;
    return children!.keys.first.caseSensitive;
  }

  /// Whether this node doesn't itself need to be listed.
  ///
  /// If a node has no validator and all of its children are literal filenames,
  /// there's no need to list its contents. We can just directly traverse into
  /// its children.
  bool get _isIntermediate {
    if (_validator != null) return false;
    return children!.keys.every((sequence) =>
        sequence.nodes.length == 1 && sequence.nodes.first is LiteralNode);
  }

  /// Returns whether listing this node might return overlapping results.
  bool get canOverlap {
    // A recusive node can never overlap with itself, because it will only ever
    // involve a single call to [Directory.list] that's then filtered with
    // [_validator].
    if (isRecursive) return false;

    // If there's more than one child node and at least one of the children is
    // dynamic (that is, matches more than just a literal string), there may be
    // overlap.
    if (children!.length > 1) {
      // Case-insensitivity means that even literals may match multiple entries.
      if (!_caseSensitive) return true;

      if (children!.keys.any((sequence) =>
          sequence.nodes.length > 1 || sequence.nodes.single is! LiteralNode)) {
        return true;
      }
    }

    return children!.values.any((node) => node.canOverlap);
  }

  /// Creates a node with no children and no validator.
  _ListTreeNode()
      : children = <SequenceNode, _ListTreeNode>{},
        _validator = null;

  /// Creates a recursive node the given [validator].
  _ListTreeNode.recursive(SequenceNode validator)
      : children = null,
        _validator =
            OptionsNode([validator], caseSensitive: validator.caseSensitive);

  /// Transforms this into recursive node, folding all its children into its
  /// validator.
  void makeRecursive() {
    if (isRecursive) return;
    var children = this.children!;
    _validator = OptionsNode(children.entries.expand((entry) {
      entry.value.makeRecursive();
      return entry.value._validator!.options
          .map((option) => _join([entry.key, option]));
    }), caseSensitive: _caseSensitive);
    this.children = null;
  }

  /// Adds [validator] to this node's existing validator.
  void addOption(SequenceNode validator) {
    if (_validator == null) {
      _validator =
          OptionsNode([validator], caseSensitive: validator.caseSensitive);
    } else {
      _validator!.options.add(validator);
    }
  }

  /// Lists all entities within [dir] matching this node or its children.
  ///
  /// This may return duplicate entities. These will be filtered out in
  /// [ListTree.list].
  Stream<FileSystemEntity> list(String dir, FileSystem fileSystem,
      {bool followLinks = true}) {
    if (isRecursive) {
      return fileSystem
          .directory(dir)
          .list(recursive: true, followLinks: followLinks)
          .ignoreMissing()
          .where((entity) => _matches(p.relative(entity.path, from: dir)));
    }

    // Don't spawn extra [Directory.list] calls when we already know exactly
    // which subdirectories we're interested in.
    if (_isIntermediate && _caseSensitive) {
      var resultGroup = StreamGroup<FileSystemEntity>();
      children!.forEach((sequence, child) {
        resultGroup.add(child.list(
            p.join(dir, (sequence.nodes.single as LiteralNode).text),
            fileSystem,
            followLinks: followLinks));
      });
      resultGroup.close();
      return resultGroup.stream;
    }

    return StreamCompleter.fromFuture(() async {
      var entities = await fileSystem
          .directory(dir)
          .list(followLinks: followLinks)
          .ignoreMissing()
          .toList();
      await _validateIntermediateChildrenAsync(dir, entities, fileSystem);

      var resultGroup = StreamGroup<FileSystemEntity>();
      var resultController = StreamController<FileSystemEntity>(sync: true);
      unawaited(resultGroup.add(resultController.stream));
      for (var entity in entities) {
        var basename = p.relative(entity.path, from: dir);
        if (_matches(basename)) resultController.add(entity);

        children!.forEach((sequence, child) {
          if (entity is! Directory) return;
          if (!sequence.matches(basename)) return;
          var stream = child.list(p.join(dir, basename), fileSystem,
              followLinks: followLinks);
          resultGroup.add(stream);
        });
      }
      unawaited(resultController.close());
      unawaited(resultGroup.close());
      return resultGroup.stream;
    }());
  }

  /// If this is a case-insensitive list, validates that all intermediate
  /// children (according to [_isIntermediate]) match at least one entity in
  /// [entities].
  ///
  /// This ensures that listing "foo/bar/*" fails on case-sensitive systems if
  /// "foo/bar" doesn't exist.
  Future _validateIntermediateChildrenAsync(String dir,
      List<FileSystemEntity> entities, FileSystem fileSystem) async {
    if (_caseSensitive) return;

    for (var entry in children!.entries) {
      var child = entry.value;
      var sequence = entry.key;
      if (!child._isIntermediate) continue;
      if (entities.any(
          (entity) => sequence.matches(p.relative(entity.path, from: dir)))) {
        continue;
      }

      // We know this will fail, we're just doing it to force dart:io to emit
      // the exception it would if we were listing case-sensitively.
      await child
          .list(p.join(dir, (sequence.nodes.single as LiteralNode).text),
              fileSystem)
          .toList();
    }
  }

  /// Synchronously lists all entities within [dir] matching this node or its
  /// children.
  ///
  /// This may return duplicate entities. These will be filtered out in
  /// [ListTree.listSync].
  Iterable<FileSystemEntity> listSync(String dir, FileSystem fileSystem,
      {bool followLinks = true}) {
    if (isRecursive) {
      try {
        return fileSystem
            .directory(dir)
            .listSync(recursive: true, followLinks: followLinks)
            .where((entity) => _matches(p.relative(entity.path, from: dir)));
      } on FileSystemException catch (error) {
        if (error.isMissing) return const [];
        rethrow;
      }
    }

    // Don't spawn extra [Directory.listSync] calls when we already know exactly
    // which subdirectories we're interested in.
    if (_isIntermediate && _caseSensitive) {
      return children!.entries.expand((entry) {
        var sequence = entry.key;
        var child = entry.value;
        return child.listSync(
            p.join(dir, (sequence.nodes.single as LiteralNode).text),
            fileSystem,
            followLinks: followLinks);
      });
    }

    List<FileSystemEntity> entities;
    try {
      entities = fileSystem.directory(dir).listSync(followLinks: followLinks);
    } on FileSystemException catch (error) {
      if (error.isMissing) return const [];
      rethrow;
    }
    _validateIntermediateChildrenSync(dir, entities, fileSystem);

    return entities.expand((entity) {
      var entities = <FileSystemEntity>[];
      var basename = p.relative(entity.path, from: dir);
      if (_matches(basename)) entities.add(entity);
      if (entity is! Directory) return entities;

      entities.addAll(children!.keys
          .where((sequence) => sequence.matches(basename))
          .expand((sequence) {
        return children![sequence]!
            .listSync(p.join(dir, basename), fileSystem,
                followLinks: followLinks)
            .toList();
      }));

      return entities;
    });
  }

  /// If this is a case-insensitive list, validates that all intermediate
  /// children (according to [_isIntermediate]) match at least one entity in
  /// [entities].
  ///
  /// This ensures that listing "foo/bar/*" fails on case-sensitive systems if
  /// "foo/bar" doesn't exist.
  void _validateIntermediateChildrenSync(
      String dir, List<FileSystemEntity> entities, FileSystem fileSystem) {
    if (_caseSensitive) return;

    children!.forEach((sequence, child) {
      if (!child._isIntermediate) return;
      if (entities.any(
          (entity) => sequence.matches(p.relative(entity.path, from: dir)))) {
        return;
      }

      // If there are no [entities] that match [sequence], manually list the
      // directory to force `dart:io` to throw an error. This allows us to
      // ensure that listing "foo/bar/*" fails on case-sensitive systems if
      // "foo/bar" doesn't exist.
      child.listSync(
          p.join(dir, (sequence.nodes.single as LiteralNode).text), fileSystem);
    });
  }

  /// Returns whether the native [path] matches [_validator].
  bool _matches(String path) =>
      _validator?.matches(toPosixPath(p.context, path)) ?? false;

  @override
  String toString() => '($_validator) $children';
}

/// Joins each [components] into a new glob where each component is separated by
/// a path separator.
SequenceNode _join(Iterable<SequenceNode> components) {
  var first = components.first;
  return SequenceNode([
    ...first.nodes,
    for (var component in components.skip(1)) ...[
      LiteralNode('/', caseSensitive: first.caseSensitive),
      ...component.nodes,
    ],
  ], caseSensitive: first.caseSensitive);
}

extension on Stream<FileSystemEntity> {
  Stream<FileSystemEntity> ignoreMissing() => handleError((_) {},
      test: (error) => error is FileSystemException && error.isMissing);
}

extension on FileSystemException {
  bool get isMissing {
    final errorCode = osError?.errorCode;
    return errorCode == _enoent || errorCode == _enoentWin;
  }
}