perf: skip expanding exclude globs (#21817)

We were calling `expand_glob` on our excludes, which is very expensive
and unnecessary because we can pattern match while traversing instead.

1. Doesn't expand "exclude" globs. Instead pattern matches while walking
the directory.
2. Splits up the "include" into base paths and applicable file patterns.
This causes less pattern matching to occur because we're only pattern
matching on patterns that might match and not ones in completely
unrelated directories.

6 files changed, 191 insertions, 91 deletions

diff --git a/cli/tools/bench/mod.rs b/cli/tools/bench/mod.rs
index 4cfd90278..1eb703813 100644
--- a/cli/tools/bench/mod.rs
+++ b/cli/tools/bench/mod.rs
@@ -15,6 +15,8 @@ use crate::tools::test::format_test_error;
 use crate::tools::test::TestFilter;
 use crate::util::file_watcher;
 use crate::util::fs::collect_specifiers;
+use crate::util::glob::FilePatterns;
+use crate::util::glob::PathOrPattern;
 use crate::util::path::is_script_ext;
 use crate::version::get_user_agent;
 use crate::worker::CliMainWorkerFactory;
@@ -393,13 +395,33 @@ async fn bench_specifiers(
 }
 
 /// Checks if the path has a basename and extension Deno supports for benches.
-fn is_supported_bench_path(path: &Path) -> bool {
+fn is_supported_bench_path(path: &Path, patterns: &FilePatterns) -> bool {
+  if !is_script_ext(path) {
+    false
+  } else if has_supported_bench_path_name(path) {
+    true
+  } else {
+    // allow someone to explicitly specify a path
+    let matches_exact_path_or_pattern = patterns
+      .include
+      .as_ref()
+      .map(|p| {
+        p.inner().iter().any(|p| match p {
+          PathOrPattern::Path(p) => p == path,
+          PathOrPattern::Pattern(p) => p.matches_path(path),
+        })
+      })
+      .unwrap_or(false);
+    matches_exact_path_or_pattern
+  }
+}
+
+fn has_supported_bench_path_name(path: &Path) -> bool {
   if let Some(name) = path.file_stem() {
     let basename = name.to_string_lossy();
-    (basename.ends_with("_bench")
+    basename.ends_with("_bench")
       || basename.ends_with(".bench")
-      || basename == "bench")
-      && is_script_ext(path)
+      || basename == "bench"
   } else {
     false
   }
@@ -420,7 +442,7 @@ pub async fn run_benchmarks(
     Permissions::from_options(&cli_options.permissions_options())?;
 
   let specifiers =
-    collect_specifiers(&bench_options.files, is_supported_bench_path)?;
+    collect_specifiers(bench_options.files, is_supported_bench_path)?;
 
   if specifiers.is_empty() {
     return Err(generic_error("No bench modules found"));
@@ -480,16 +502,21 @@ pub async fn run_benchmarks_with_watch(
         let bench_options = cli_options.resolve_bench_options(bench_flags)?;
 
         let _ = watcher_communicator.watch_paths(cli_options.watch_paths());
-        if let Some(include) = &bench_options.files.include {
-          let _ = watcher_communicator.watch_paths(include.clone());
+        if let Some(set) = &bench_options.files.include {
+          let watch_paths = set.base_paths();
+          if !watch_paths.is_empty() {
+            let _ = watcher_communicator.watch_paths(watch_paths);
+          }
         }
 
         let graph_kind = cli_options.type_check_mode().as_graph_kind();
         let module_graph_builder = factory.module_graph_builder().await?;
         let module_load_preparer = factory.module_load_preparer().await?;
 
-        let bench_modules =
-          collect_specifiers(&bench_options.files, is_supported_bench_path)?;
+        let bench_modules = collect_specifiers(
+          bench_options.files.clone(),
+          is_supported_bench_path,
+        )?;
 
         // Various bench files should not share the same permissions in terms of
         // `PermissionsContainer` - otherwise granting/revoking permissions in one
@@ -509,16 +536,13 @@ pub async fn run_benchmarks_with_watch(
 
         let bench_modules_to_reload = if let Some(changed_paths) = changed_paths
         {
-          let changed_specifiers = changed_paths
-            .into_iter()
-            .filter_map(|p| ModuleSpecifier::from_file_path(p).ok())
-            .collect::<HashSet<_>>();
+          let changed_paths = changed_paths.into_iter().collect::<HashSet<_>>();
           let mut result = Vec::new();
           for bench_module_specifier in bench_modules {
             if has_graph_root_local_dependent_changed(
               &graph,
               &bench_module_specifier,
-              &changed_specifiers,
+              &changed_paths,
             ) {
               result.push(bench_module_specifier.clone());
             }
@@ -531,8 +555,10 @@ pub async fn run_benchmarks_with_watch(
         let worker_factory =
           Arc::new(factory.create_cli_main_worker_factory().await?);
 
+        // todo(THIS PR): why are we collecting specifiers twice in a row?
+        // Seems like a perf bug.
         let specifiers =
-          collect_specifiers(&bench_options.files, is_supported_bench_path)?
+          collect_specifiers(bench_options.files, is_supported_bench_path)?
             .into_iter()
             .filter(|specifier| bench_modules_to_reload.contains(specifier))
             .collect::<Vec<ModuleSpecifier>>();
diff --git a/cli/tools/coverage/mod.rs b/cli/tools/coverage/mod.rs
index 9f5c142e7..49bb5d5de 100644
--- a/cli/tools/coverage/mod.rs
+++ b/cli/tools/coverage/mod.rs
@@ -9,6 +9,8 @@ use crate::npm::CliNpmResolver;
 use crate::tools::fmt::format_json;
 use crate::tools::test::is_supported_test_path;
 use crate::util::fs::FileCollector;
+use crate::util::glob::FilePatterns;
+use crate::util::glob::PathOrPatternSet;
 use crate::util::text_encoding::source_map_from_code;
 
 use deno_ast::MediaType;
@@ -371,9 +373,23 @@ fn range_to_src_line_index(
 
 fn collect_coverages(
   files: FileFlags,
+  initial_cwd: &Path,
 ) -> Result<Vec<cdp::ScriptCoverage>, AnyError> {
+  let files = files.with_absolute_paths(initial_cwd);
   let mut coverages: Vec<cdp::ScriptCoverage> = Vec::new();
-  let file_paths = FileCollector::new(|file_path| {
+  let file_patterns = FilePatterns {
+    include: Some({
+      let files = if files.include.is_empty() {
+        vec![initial_cwd.to_path_buf()]
+      } else {
+        files.include
+      };
+      PathOrPatternSet::from_absolute_paths(files)?
+    }),
+    exclude: PathOrPatternSet::from_absolute_paths(files.ignore)
+      .context("Invalid ignore pattern.")?,
+  };
+  let file_paths = FileCollector::new(|file_path, _| {
     file_path
       .extension()
       .map(|ext| ext == "json")
@@ -382,16 +398,13 @@ fn collect_coverages(
   .ignore_git_folder()
   .ignore_node_modules()
   .ignore_vendor_folder()
-  .add_ignore_paths(&files.ignore)
-  .collect_files(if files.include.is_empty() {
-    None
-  } else {
-    Some(&files.include)
-  })?;
+  .collect_file_patterns(file_patterns)?;
 
   for file_path in file_paths {
-    let json = fs::read_to_string(file_path.as_path())?;
-    let new_coverage: cdp::ScriptCoverage = serde_json::from_str(&json)?;
+    let new_coverage = fs::read_to_string(file_path.as_path())
+      .map_err(AnyError::from)
+      .and_then(|json| serde_json::from_str(&json).map_err(AnyError::from))
+      .with_context(|| format!("Failed reading '{}'", file_path.display()))?;
     coverages.push(new_coverage);
   }
 
@@ -451,7 +464,8 @@ pub async fn cover_files(
 
   // Use the first include path as the default output path.
   let coverage_root = coverage_flags.files.include[0].clone();
-  let script_coverages = collect_coverages(coverage_flags.files)?;
+  let script_coverages =
+    collect_coverages(coverage_flags.files, cli_options.initial_cwd())?;
   if script_coverages.is_empty() {
     return Err(generic_error("No coverage files found"));
   }
diff --git a/cli/tools/doc.rs b/cli/tools/doc.rs
index b0eecd044..b8d6b8a87 100644
--- a/cli/tools/doc.rs
+++ b/cli/tools/doc.rs
@@ -12,12 +12,13 @@ use crate::factory::CliFactory;
 use crate::graph_util::graph_lock_or_exit;
 use crate::graph_util::CreateGraphOptions;
 use crate::tsc::get_types_declaration_file_text;
-use crate::util::glob::expand_globs;
+use crate::util::fs::collect_specifiers;
+use crate::util::glob::FilePatterns;
+use crate::util::glob::PathOrPatternSet;
 use deno_core::anyhow::bail;
 use deno_core::anyhow::Context;
 use deno_core::error::AnyError;
 use deno_core::futures::FutureExt;
-use deno_core::resolve_url_or_path;
 use deno_doc as doc;
 use deno_graph::CapturingModuleParser;
 use deno_graph::DefaultParsedSourceStore;
@@ -100,19 +101,28 @@ pub async fn doc(flags: Flags, doc_flags: DocFlags) -> Result<(), AnyError> {
       let module_graph_builder = factory.module_graph_builder().await?;
       let maybe_lockfile = factory.maybe_lockfile();
 
-      let expanded_globs =
-        expand_globs(source_files.iter().map(PathBuf::from).collect())?;
-      let module_specifiers: Result<Vec<ModuleSpecifier>, AnyError> =
-        expanded_globs
-          .iter()
-          .map(|source_file| {
-            Ok(resolve_url_or_path(
-              &source_file.to_string_lossy(),
-              cli_options.initial_cwd(),
-            )?)
-          })
-          .collect();
-      let module_specifiers = module_specifiers?;
+      let module_specifiers = collect_specifiers(
+        FilePatterns {
+          include: Some(PathOrPatternSet::from_absolute_paths(
+            source_files
+              .iter()
+              .map(|p| {
+                if p.starts_with("https:")
+                  || p.starts_with("http:")
+                  || p.starts_with("file:")
+                {
+                  // todo(dsherret): don't store URLs in PathBufs
+                  PathBuf::from(p)
+                } else {
+                  cli_options.initial_cwd().join(p)
+                }
+              })
+              .collect(),
+          )?),
+          exclude: Default::default(),
+        },
+        |_, _| true,
+      )?;
       let mut loader = module_graph_builder.create_graph_loader();
       let graph = module_graph_builder
         .create_graph_with_options(CreateGraphOptions {
diff --git a/cli/tools/fmt.rs b/cli/tools/fmt.rs
index 111632d4a..c35c72844 100644
--- a/cli/tools/fmt.rs
+++ b/cli/tools/fmt.rs
@@ -8,7 +8,6 @@
 //! the same functions as ops available in JS runtime.
 
 use crate::args::CliOptions;
-use crate::args::FilesConfig;
 use crate::args::Flags;
 use crate::args::FmtFlags;
 use crate::args::FmtOptions;
@@ -18,7 +17,9 @@ use crate::colors;
 use crate::factory::CliFactory;
 use crate::util::diff::diff;
 use crate::util::file_watcher;
+use crate::util::fs::canonicalize_path;
 use crate::util::fs::FileCollector;
+use crate::util::glob::FilePatterns;
 use crate::util::path::get_extension;
 use crate::util::text_encoding;
 use deno_ast::ParsedSource;
@@ -72,7 +73,7 @@ pub async fn format(flags: Flags, fmt_flags: FmtFlags) -> Result<(), AnyError> {
           let cli_options = factory.cli_options();
           let fmt_options = cli_options.resolve_fmt_options(fmt_flags)?;
           let files =
-            collect_fmt_files(&fmt_options.files).and_then(|files| {
+            collect_fmt_files(fmt_options.files.clone()).and_then(|files| {
               if files.is_empty() {
                 Err(generic_error("No target files found."))
               } else {
@@ -85,13 +86,21 @@ pub async fn format(flags: Flags, fmt_flags: FmtFlags) -> Result<(), AnyError> {
               // check all files on any changed (https://github.com/denoland/deno/issues/12446)
               files
                 .iter()
-                .any(|path| paths.contains(path))
+                .any(|path| {
+                  canonicalize_path(path)
+                    .map(|path| paths.contains(&path))
+                    .unwrap_or(false)
+                })
                 .then_some(files)
                 .unwrap_or_else(|| [].to_vec())
             } else {
               files
                 .into_iter()
-                .filter(|path| paths.contains(path))
+                .filter(|path| {
+                  canonicalize_path(path)
+                    .map(|path| paths.contains(&path))
+                    .unwrap_or(false)
+                })
                 .collect::<Vec<_>>()
             }
           } else {
@@ -108,13 +117,14 @@ pub async fn format(flags: Flags, fmt_flags: FmtFlags) -> Result<(), AnyError> {
     let factory = CliFactory::from_flags(flags).await?;
     let cli_options = factory.cli_options();
     let fmt_options = cli_options.resolve_fmt_options(fmt_flags)?;
-    let files = collect_fmt_files(&fmt_options.files).and_then(|files| {
-      if files.is_empty() {
-        Err(generic_error("No target files found."))
-      } else {
-        Ok(files)
-      }
-    })?;
+    let files =
+      collect_fmt_files(fmt_options.files.clone()).and_then(|files| {
+        if files.is_empty() {
+          Err(generic_error("No target files found."))
+        } else {
+          Ok(files)
+        }
+      })?;
     format_files(factory, fmt_options, files).await?;
   }
 
@@ -144,13 +154,12 @@ async fn format_files(
   Ok(())
 }
 
-fn collect_fmt_files(files: &FilesConfig) -> Result<Vec<PathBuf>, AnyError> {
-  FileCollector::new(is_supported_ext_fmt)
+fn collect_fmt_files(files: FilePatterns) -> Result<Vec<PathBuf>, AnyError> {
+  FileCollector::new(|path, _| is_supported_ext_fmt(path))
     .ignore_git_folder()
     .ignore_node_modules()
     .ignore_vendor_folder()
-    .add_ignore_paths(&files.exclude)
-    .collect_files(files.include.as_deref())
+    .collect_file_patterns(files)
 }
 
 /// Formats markdown (using <https://github.com/dprint/dprint-plugin-markdown>) and its code blocks
diff --git a/cli/tools/lint.rs b/cli/tools/lint.rs
index 7981fec09..a91f14ad8 100644
--- a/cli/tools/lint.rs
+++ b/cli/tools/lint.rs
@@ -2,7 +2,6 @@
 
 //! This module provides file linting utilities using
 //! [`deno_lint`](https://github.com/denoland/deno_lint).
-use crate::args::FilesConfig;
 use crate::args::Flags;
 use crate::args::LintFlags;
 use crate::args::LintOptions;
@@ -12,7 +11,9 @@ use crate::colors;
 use crate::factory::CliFactory;
 use crate::tools::fmt::run_parallelized;
 use crate::util::file_watcher;
+use crate::util::fs::canonicalize_path;
 use crate::util::fs::FileCollector;
+use crate::util::glob::FilePatterns;
 use crate::util::path::is_script_ext;
 use crate::util::sync::AtomicFlag;
 use deno_ast::MediaType;
@@ -66,21 +67,26 @@ pub async fn lint(flags: Flags, lint_flags: LintFlags) -> Result<(), AnyError> {
           let factory = CliFactory::from_flags(flags).await?;
           let cli_options = factory.cli_options();
           let lint_options = cli_options.resolve_lint_options(lint_flags)?;
-          let files =
-            collect_lint_files(&lint_options.files).and_then(|files| {
+          let files = collect_lint_files(lint_options.files.clone()).and_then(
+            |files| {
               if files.is_empty() {
                 Err(generic_error("No target files found."))
               } else {
                 Ok(files)
               }
-            })?;
+            },
+          )?;
           _ = watcher_communicator.watch_paths(files.clone());
 
           let lint_paths = if let Some(paths) = changed_paths {
             // lint all files on any changed (https://github.com/denoland/deno/issues/12446)
             files
               .iter()
-              .any(|path| paths.contains(path))
+              .any(|path| {
+                canonicalize_path(path)
+                  .map(|p| paths.contains(&p))
+                  .unwrap_or(false)
+              })
               .then_some(files)
               .unwrap_or_else(|| [].to_vec())
           } else {
@@ -109,13 +115,14 @@ pub async fn lint(flags: Flags, lint_flags: LintFlags) -> Result<(), AnyError> {
       reporter_lock.lock().unwrap().close(1);
       success
     } else {
-      let target_files = collect_lint_files(files).and_then(|files| {
-        if files.is_empty() {
-          Err(generic_error("No target files found."))
-        } else {
-          Ok(files)
-        }
-      })?;
+      let target_files =
+        collect_lint_files(files.clone()).and_then(|files| {
+          if files.is_empty() {
+            Err(generic_error("No target files found."))
+          } else {
+            Ok(files)
+          }
+        })?;
       debug!("Found {} files", target_files.len());
       lint_files(factory, lint_options, target_files).await?
     };
@@ -191,13 +198,12 @@ async fn lint_files(
   Ok(!has_error.is_raised())
 }
 
-fn collect_lint_files(files: &FilesConfig) -> Result<Vec<PathBuf>, AnyError> {
-  FileCollector::new(is_script_ext)
+fn collect_lint_files(files: FilePatterns) -> Result<Vec<PathBuf>, AnyError> {
+  FileCollector::new(|path, _| is_script_ext(path))
     .ignore_git_folder()
     .ignore_node_modules()
     .ignore_vendor_folder()
-    .add_ignore_paths(&files.exclude)
-    .collect_files(files.include.as_deref())
+    .collect_file_patterns(files)
 }
 
 pub fn print_rules_list(json: bool, maybe_rules_tags: Option<Vec<String>>) {
diff --git a/cli/tools/test/mod.rs b/cli/tools/test/mod.rs
index 2a5e87b2a..2c226db4d 100644
--- a/cli/tools/test/mod.rs
+++ b/cli/tools/test/mod.rs
@@ -1,7 +1,6 @@
 // Copyright 2018-2024 the Deno authors. All rights reserved. MIT license.
 
 use crate::args::CliOptions;
-use crate::args::FilesConfig;
 use crate::args::Flags;
 use crate::args::TestFlags;
 use crate::args::TestReporterConfig;
@@ -17,6 +16,8 @@ use crate::module_loader::ModuleLoadPreparer;
 use crate::ops;
 use crate::util::file_watcher;
 use crate::util::fs::collect_specifiers;
+use crate::util::glob::FilePatterns;
+use crate::util::glob::PathOrPattern;
 use crate::util::path::get_extension;
 use crate::util::path::is_script_ext;
 use crate::util::path::mapped_specifier_for_tsc;
@@ -1048,14 +1049,41 @@ pub async fn report_tests(
   (Ok(()), receiver)
 }
 
+fn is_supported_test_path_predicate(
+  path: &Path,
+  patterns: &FilePatterns,
+) -> bool {
+  if !is_script_ext(path) {
+    false
+  } else if has_supported_test_path_name(path) {
+    true
+  } else {
+    // allow someone to explicitly specify a path
+    let matches_exact_path_or_pattern = patterns
+      .include
+      .as_ref()
+      .map(|p| {
+        p.inner().iter().any(|p| match p {
+          PathOrPattern::Path(p) => p == path,
+          PathOrPattern::Pattern(p) => p.matches_path(path),
+        })
+      })
+      .unwrap_or(false);
+    matches_exact_path_or_pattern
+  }
+}
+
 /// Checks if the path has a basename and extension Deno supports for tests.
 pub(crate) fn is_supported_test_path(path: &Path) -> bool {
+  has_supported_test_path_name(path) && is_script_ext(path)
+}
+
+fn has_supported_test_path_name(path: &Path) -> bool {
   if let Some(name) = path.file_stem() {
     let basename = name.to_string_lossy();
-    (basename.ends_with("_test")
+    basename.ends_with("_test")
       || basename.ends_with(".test")
-      || basename == "test")
-      && is_script_ext(path)
+      || basename == "test"
   } else {
     false
   }
@@ -1094,13 +1122,15 @@ fn is_supported_test_ext(path: &Path) -> bool {
 /// - Specifiers matching the `is_supported_test_path` are marked as `TestMode::Executable`.
 /// - Specifiers matching both predicates are marked as `TestMode::Both`
 fn collect_specifiers_with_test_mode(
-  files: &FilesConfig,
+  files: FilePatterns,
   include_inline: &bool,
 ) -> Result<Vec<(ModuleSpecifier, TestMode)>, AnyError> {
-  let module_specifiers = collect_specifiers(files, is_supported_test_path)?;
+  // todo(dsherret): there's no need to collect twice as it's slow
+  let module_specifiers =
+    collect_specifiers(files.clone(), is_supported_test_path_predicate)?;
 
   if *include_inline {
-    return collect_specifiers(files, is_supported_test_ext).map(
+    return collect_specifiers(files, |p, _| is_supported_test_ext(p)).map(
       |specifiers| {
         specifiers
           .into_iter()
@@ -1136,7 +1166,7 @@ fn collect_specifiers_with_test_mode(
 /// as well.
 async fn fetch_specifiers_with_test_mode(
   file_fetcher: &FileFetcher,
-  files: &FilesConfig,
+  files: FilePatterns,
   doc: &bool,
 ) -> Result<Vec<(ModuleSpecifier, TestMode)>, AnyError> {
   let mut specifiers_with_mode = collect_specifiers_with_test_mode(files, doc)?;
@@ -1174,7 +1204,7 @@ pub async fn run_tests(
 
   let specifiers_with_mode = fetch_specifiers_with_test_mode(
     file_fetcher,
-    &test_options.files,
+    test_options.files.clone(),
     &test_options.doc,
   )
   .await?;
@@ -1264,8 +1294,11 @@ pub async fn run_tests_with_watch(
         let test_options = cli_options.resolve_test_options(test_flags)?;
 
         let _ = watcher_communicator.watch_paths(cli_options.watch_paths());
-        if let Some(include) = &test_options.files.include {
-          let _ = watcher_communicator.watch_paths(include.clone());
+        if let Some(set) = &test_options.files.include {
+          let watch_paths = set.base_paths();
+          if !watch_paths.is_empty() {
+            let _ = watcher_communicator.watch_paths(watch_paths);
+          }
         }
 
         let graph_kind = cli_options.type_check_mode().as_graph_kind();
@@ -1274,13 +1307,18 @@ pub async fn run_tests_with_watch(
         let module_graph_builder = factory.module_graph_builder().await?;
         let file_fetcher = factory.file_fetcher()?;
         let test_modules = if test_options.doc {
-          collect_specifiers(&test_options.files, is_supported_test_ext)
+          collect_specifiers(test_options.files.clone(), |p, _| {
+            is_supported_test_ext(p)
+          })
         } else {
-          collect_specifiers(&test_options.files, is_supported_test_path)
+          collect_specifiers(
+            test_options.files.clone(),
+            is_supported_test_path_predicate,
+          )
         }?;
+
         let permissions =
           Permissions::from_options(&cli_options.permissions_options())?;
-
         let graph = module_graph_builder
           .create_graph(graph_kind, test_modules.clone())
           .await?;
@@ -1293,16 +1331,13 @@ pub async fn run_tests_with_watch(
 
         let test_modules_to_reload = if let Some(changed_paths) = changed_paths
         {
-          let changed_specifiers = changed_paths
-            .into_iter()
-            .filter_map(|p| ModuleSpecifier::from_file_path(p).ok())
-            .collect::<HashSet<_>>();
           let mut result = Vec::new();
+          let changed_paths = changed_paths.into_iter().collect::<HashSet<_>>();
           for test_module_specifier in test_modules {
             if has_graph_root_local_dependent_changed(
               &graph,
               &test_module_specifier,
-              &changed_specifiers,
+              &changed_paths,
             ) {
               result.push(test_module_specifier.clone());
             }
@@ -1317,7 +1352,7 @@ pub async fn run_tests_with_watch(
         let module_load_preparer = factory.module_load_preparer().await?;
         let specifiers_with_mode = fetch_specifiers_with_test_mode(
           file_fetcher,
-          &test_options.files,
+          test_options.files.clone(),
           &test_options.doc,
         )
         .await?