turbo_tasks_fs/
glob.rs

1use std::{borrow::Cow, fmt::Display};
2
3use anyhow::{Result, bail};
4use bincode::{
5    Decode, Encode,
6    de::Decoder,
7    enc::Encoder,
8    error::{DecodeError, EncodeError},
9    impl_borrow_decode,
10};
11use regex::bytes::{Regex, RegexBuilder};
12use turbo_rcstr::{RcStr, rcstr};
13use turbo_tasks::Vc;
14
15use crate::{FileSystemPath, globset::parse};
16
17// Examples:
18// - file.js = File(file.js)
19// - *.js = AnyFile, File(.js)
20// - file*.js = File(file), AnyFile, File(.js)
21// - dir/file.js = File(dir), PathSeparator, File(file.js)
22// - **/*.js = AnyDirectories, PathSeparator, AnyFile, File(.js)
23// - {a/**,*}/file = Alternatives([File(a), PathSeparator, AnyDirectories], [AnyFile]),
24//   PathSeparator, File(file)
25
26// Note: a/**/b does match a/b, so we need some special logic about path
27// separators
28
29#[turbo_tasks::value(eq = "manual", serialization = "custom")]
30#[derive(Debug, Clone)]
31pub struct Glob {
32    glob: RcStr,
33    opts: GlobOptions,
34    #[turbo_tasks(unsafe_ignore)]
35    regex: Regex,
36    #[turbo_tasks(unsafe_ignore)]
37    directory_match_regex: Regex,
38}
39
40impl PartialEq for Glob {
41    fn eq(&self, other: &Self) -> bool {
42        self.glob == other.glob && self.opts == other.opts
43    }
44}
45
46impl Eq for Glob {}
47
48impl Display for Glob {
49    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
50        write!(f, "Glob({})", self.glob)
51    }
52}
53
54impl Encode for Glob {
55    fn encode<E: Encoder>(&self, encoder: &mut E) -> Result<(), EncodeError> {
56        self.glob.encode(encoder)?;
57        self.opts.encode(encoder)?;
58        Ok(())
59    }
60}
61
62impl<Context> Decode<Context> for Glob {
63    fn decode<D: Decoder<Context = Context>>(decoder: &mut D) -> Result<Self, DecodeError> {
64        let glob = RcStr::decode(decoder)?;
65        let opts = GlobOptions::decode(decoder)?;
66        Glob::parse(glob, opts).map_err(|err| DecodeError::OtherString(err.to_string()))
67    }
68}
69
70impl_borrow_decode!(Glob);
71
72#[turbo_tasks::task_input]
73#[derive(Copy, Clone, PartialEq, Eq, Hash, Default, Debug, Encode, Decode)]
74pub struct GlobOptions {
75    /// Whether the glob is a partial match.
76    /// Allows glob to match any part of the given string(s).
77    /// NOTE: this means that a pattern like `node_modules/package_name` with `contains:true` will
78    /// match `foo_node_modules/package_name_bar` If you want to match a _directory_ named
79    /// `node_modules/package_name` you should use `**/node_modules/package_name/**`.
80    ///
81    /// A partial match cannot safely determine whether a directory might contain a match, so this
82    /// option cannot be used with [`Glob::can_match_in_directory`].
83    pub contains: bool,
84    /// Whether matching should ignore ASCII case differences.
85    pub case_insensitive: bool,
86}
87
88impl Glob {
89    // Returns true if the glob matches the given path.
90    pub fn matches(&self, path: &str) -> bool {
91        self.regex.is_match(path.as_bytes())
92    }
93
94    // Returns true if the glob might match a filename underneath this `path` where the
95    // path represents a directory.
96    pub fn can_match_in_directory(&self, path: &str) -> bool {
97        assert!(
98            !self.opts.contains,
99            "Glob::can_match_in_directory cannot be used when GlobOptions::contains is true"
100        );
101        debug_assert!(
102            !path.ends_with('/'),
103            "Path should be a directory name and not end with /"
104        );
105        self.directory_match_regex.is_match(path.as_bytes())
106    }
107
108    pub fn parse(input: RcStr, opts: GlobOptions) -> Result<Glob> {
109        let (glob_re, directory_match_re) = parse(&input, opts)?;
110        let regex = new_regex(glob_re.as_str(), opts);
111        let directory_match_regex = new_regex(directory_match_re.as_str(), opts);
112
113        Ok(Glob {
114            glob: input,
115            opts,
116            regex,
117            directory_match_regex,
118        })
119    }
120}
121
122#[turbo_tasks::value_impl]
123impl Glob {
124    #[turbo_tasks::function]
125    pub fn new(glob: RcStr, opts: GlobOptions) -> Result<Vc<Self>> {
126        Ok(Self::cell(Glob::parse(glob, opts)?))
127    }
128
129    #[turbo_tasks::function]
130    pub async fn alternatives(globs: Vec<Vc<Glob>>) -> Result<Vc<Self>> {
131        match globs.len() {
132            0 => Ok(Glob::new(rcstr!(""), GlobOptions::default())),
133            1 => Ok(globs.into_iter().next().unwrap()),
134            _ => {
135                let mut new_glob = String::new();
136                new_glob.push('{');
137                let mut opts = None;
138                for (index, glob) in globs.iter().enumerate() {
139                    if index > 0 {
140                        new_glob.push(',');
141                    }
142                    let glob = &*glob.await?;
143                    if let Some(old_opts) = opts {
144                        if old_opts != glob.opts {
145                            bail!(
146                                "Cannot compose globs with different options via the \
147                                 `alternatives` function."
148                            )
149                        }
150                    } else {
151                        opts = Some(glob.opts);
152                    }
153                    new_glob.push_str(&glob.glob);
154                }
155                new_glob.push('}');
156                // The loop must have iterated at least once, so the options must be initialized.
157                Ok(Glob::new(new_glob.into(), opts.unwrap()))
158            }
159        }
160    }
161}
162
163/// Resolve the leading `./` and `../` segments of a glob pattern into a
164/// directory, so that what remains only ever traverses *down* the tree.
165///
166/// [`Glob`] matches paths relative to the directory that is scanned and has no
167/// notion of `.` or `..`, and the directory walker only descends. A pattern like
168/// `../dir/*.js` therefore has to be turned into the pattern `dir/*.js` matched
169/// against the parent of `relative_to`, which is what this does.
170///
171/// Returns the remaining pattern together with the directory it is relative to,
172/// or [`None`] if the pattern walks above the root of the filesystem. Callers
173/// decide how to report that: it is a hard error for some and a diagnostic for
174/// others.
175///
176/// ```ignore
177/// // with `relative_to` = `src/app`
178/// relativize_glob("*.js")           // => ("*.js",    "src/app")
179/// relativize_glob("./dir/*.js")     // => ("dir/*.js", "src/app")
180/// relativize_glob("../dir/*.js")    // => ("dir/*.js", "src")
181/// relativize_glob("././../x/*.js")  // => ("x/*.js",   "src")
182/// ```
183pub fn relativize_glob<'a>(
184    glob: &'a str,
185    relative_to: &FileSystemPath,
186) -> Option<(&'a str, FileSystemPath)> {
187    let mut relative_to = Cow::Borrowed(relative_to);
188    let mut remaining = glob;
189    loop {
190        if let Some(stripped) = remaining.strip_prefix("../") {
191            if relative_to.is_root() {
192                return None;
193            }
194            relative_to = Cow::Owned(relative_to.parent());
195            remaining = stripped;
196        } else if let Some(stripped) = remaining.strip_prefix("./") {
197            remaining = stripped;
198        } else {
199            return Some((remaining, relative_to.into_owned()));
200        }
201    }
202}
203
204fn new_regex(pattern: &str, opts: GlobOptions) -> Regex {
205    RegexBuilder::new(pattern)
206        // Because we aren't setting the `unicode` flag, this is only ASCII case-insensitive.
207        .case_insensitive(opts.case_insensitive)
208        .dot_matches_new_line(true)
209        .build()
210        .expect("A successfully parsed glob should produce a valid regex")
211}
212
213#[cfg(test)]
214mod relativize_glob_tests {
215    use turbo_tasks::ResolvedVc;
216    use turbo_tasks_backend::{BackendOptions, TurboTasksBackend, noop_backing_storage};
217
218    use super::*;
219    use crate::NullFileSystem;
220
221    fn path(path: &str) -> FileSystemPath {
222        FileSystemPath {
223            fs: ResolvedVc::upcast(NullFileSystem {}.resolved_cell()),
224            path: path.into(),
225        }
226    }
227
228    #[tokio::test(flavor = "multi_thread", worker_threads = 2)]
229    async fn relativizes_leading_segments() {
230        let tt = turbo_tasks::TurboTasks::new(TurboTasksBackend::new(
231            BackendOptions::default(),
232            noop_backing_storage(),
233        ));
234        tt.run_once(async {
235            let dir = path("project/src/components");
236
237            // No leading relative segments: returned as-is.
238            let (glob, root) = relativize_glob("*.js", &dir).unwrap();
239            assert_eq!(
240                (glob, root.path.as_str()),
241                ("*.js", "project/src/components")
242            );
243            let (glob, root) = relativize_glob("nested/**/*.js", &dir).unwrap();
244            assert_eq!(
245                (glob, root.path.as_str()),
246                ("nested/**/*.js", "project/src/components")
247            );
248
249            // `./` doesn't move the directory, repeated or not.
250            let (glob, root) = relativize_glob("./*.js", &dir).unwrap();
251            assert_eq!(
252                (glob, root.path.as_str()),
253                ("*.js", "project/src/components")
254            );
255            let (glob, root) = relativize_glob("././*.js", &dir).unwrap();
256            assert_eq!(
257                (glob, root.path.as_str()),
258                ("*.js", "project/src/components")
259            );
260
261            // Each `../` walks one directory up.
262            let (glob, root) = relativize_glob("../*.js", &dir).unwrap();
263            assert_eq!((glob, root.path.as_str()), ("*.js", "project/src"));
264            let (glob, root) = relativize_glob("../../lib/*.js", &dir).unwrap();
265            assert_eq!((glob, root.path.as_str()), ("lib/*.js", "project"));
266
267            // `./` and `../` may be mixed, in either order, and are all consumed.
268            let (glob, root) = relativize_glob(".././utils/*.js", &dir).unwrap();
269            assert_eq!((glob, root.path.as_str()), ("utils/*.js", "project/src"));
270            let (glob, root) = relativize_glob("./../lib/*.js", &dir).unwrap();
271            assert_eq!((glob, root.path.as_str()), ("lib/*.js", "project/src"));
272            let (glob, root) = relativize_glob("././../.././x/*.js", &dir).unwrap();
273            assert_eq!((glob, root.path.as_str()), ("x/*.js", "project"));
274
275            // Walking exactly to the filesystem root is fine.
276            let (glob, root) = relativize_glob("../../../*.js", &dir).unwrap();
277            assert_eq!((glob, root.path.as_str()), ("*.js", ""));
278
279            Ok(())
280        })
281        .await
282        .unwrap();
283    }
284
285    #[tokio::test(flavor = "multi_thread", worker_threads = 2)]
286    async fn reports_walking_above_the_root() {
287        let tt = turbo_tasks::TurboTasks::new(TurboTasksBackend::new(
288            BackendOptions::default(),
289            noop_backing_storage(),
290        ));
291        tt.run_once(async {
292            // One `../` too many, from a nested directory and from the root itself.
293            assert!(relativize_glob("../../../../*.js", &path("project/src/components")).is_none());
294            assert!(relativize_glob("../*.js", &path("")).is_none());
295            // The `../` doesn't have to be the first segment to be detected.
296            assert!(relativize_glob("./../../*.js", &path("project")).is_none());
297            Ok(())
298        })
299        .await
300        .unwrap();
301    }
302}
303
304#[cfg(test)]
305mod tests {
306    use rstest::*;
307
308    use super::*;
309
310    #[rstest]
311    #[case::file("file.js", "file.js")]
312    #[case::dir_and_file("../public/äöüščří.png", "../public/äöüščří.png")]
313    #[case::dir_and_file("dir/file.js", "dir/file.js")]
314    #[case::file_braces("file.{ts,js}", "file.js")]
315    #[case::dir_and_file_braces("dir/file.{ts,js}", "dir/file.js")]
316    #[case::dir_and_file_dir_braces("{dir,other}/file.{ts,js}", "dir/file.js")]
317    #[case::star("*.js", "file.js")]
318    #[case::dir_star("dir/*.js", "dir/file.js")]
319    #[case::globstar("**/*.js", "file.js")]
320    #[case::globstar("**/*.js", "dir/file.js")]
321    #[case::globstar("**/*.js", "dir/sub/file.js")]
322    #[case::globstar("**/**/*.js", "file.js")]
323    #[case::globstar("**/**/*.js", "dir/sub/file.js")]
324    #[case::globstar("**", "/foo")]
325    #[case::globstar("**", "foo")]
326    #[case::star("*", "foo")]
327    #[case::globstar_in_dir("dir/**/sub/file.js", "dir/sub/file.js")]
328    #[case::globstar_in_dir("dir/**/sub/file.js", "dir/a/sub/file.js")]
329    #[case::globstar_in_dir("dir/**/sub/file.js", "dir/a/b/sub/file.js")]
330    #[case::globstar_in_dir(
331        "**/next/dist/**/*.shared-runtime.js",
332        "next/dist/shared/lib/app-router-context.shared-runtime.js"
333    )]
334    #[case::star_dir(
335        "**/*/next/dist/server/next.js",
336        "node_modules/next/dist/server/next.js"
337    )]
338    #[case::node_modules_root("**/node_modules/**", "node_modules/next/dist/server/next.js")]
339    #[case::node_modules_root_package(
340        "**/node_modules/next/**",
341        "node_modules/next/dist/server/next.js"
342    )]
343    #[case::node_modules_nested(
344        "**/node_modules/**",
345        "apps/some-app/node_modules/regenerate-unicode-properties/Script_Extensions/Osage.js"
346    )]
347    #[case::node_modules_nested_package(
348        "**/node_modules/regenerate-unicode-properties/**",
349        "apps/some-app/node_modules/regenerate-unicode-properties/Script_Extensions/Osage.js"
350    )]
351    #[case::node_modules_pnpm(
352        "**/node_modules/**",
353        "node_modules/.pnpm/regenerate-unicode-properties@9.0.0/node_modules/\
354         regenerate-unicode-properties/Script_Extensions/Osage.js"
355    )]
356    #[case::node_modules_pnpm_package(
357        "**/node_modules/{regenerate,regenerate-unicode-properties}/**",
358        "node_modules/.pnpm/regenerate-unicode-properties@9.0.0/node_modules/\
359         regenerate-unicode-properties/Script_Extensions/Osage.js"
360    )]
361    #[case::node_modules_pnpm_prefixed_package(
362        "**/node_modules/{@blockfrost/blockfrost-js,@highlight-run/node,@libsql/client,@jpg-store/\
363         lucid-cardano,@mikro-orm/core,@mikro-orm/knex,@prisma/client,@sentry/nextjs,@sentry/node,\
364         @swc/core,argon2,autoprefixer,bcrypt,better-sqlite3,canvas,cpu-features,cypress,eslint,\
365         express,next-seo,node-pty,payload,pg,playwright,postcss,prettier,prisma,puppeteer,rimraf,\
366         sharp,shiki,sqlite3,tailwindcss,ts-node,typescript,vscode-oniguruma,webpack,websocket,@\
367         aws-sdk/client-dynamodb,@aws-sdk/lib-dynamodb}/**",
368        "node_modules/.pnpm/@aws-sdk+lib-dynamodb@3.445.0_@aws-sdk+client-dynamodb@3.445.0/\
369         node_modules/@aws-sdk/lib-dynamodb/dist-es/index.js"
370    )]
371    #[case::alternatives_nested1("{a,b/c,d/e/{f,g/h}}", "a")]
372    #[case::alternatives_nested2("{a,b/c,d/e/{f,g/h}}", "b/c")]
373    #[case::alternatives_nested3("{a,b/c,d/e/{f,g/h}}", "d/e/f")]
374    #[case::alternatives_nested4("{a,b/c,d/e/{f,g/h}}", "d/e/g/h")]
375    #[case::alternatives_empty1("react{,-dom}", "react")]
376    #[case::alternatives_empty2("react{,-dom}", "react-dom")]
377    #[case::alternatives_chars("[abc]", "b")]
378    #[case::character_range("[a-z].js", "b.js")]
379    fn glob_match(#[case] glob: &str, #[case] path: &str) {
380        let glob = Glob::parse(RcStr::from(glob), GlobOptions::default()).unwrap();
381
382        println!("{glob:?} {path}");
383
384        assert!(glob.matches(path));
385    }
386
387    #[test]
388    fn glob_rejects_invalid_character_range() {
389        let error = Glob::parse(rcstr!("[z-a]"), GlobOptions::default()).unwrap_err();
390
391        assert!(format!("{error:#}").contains("invalid character range"));
392    }
393
394    #[rstest]
395    #[case::early_end("*.raw", "hello.raw.js")]
396    #[case::early_end(
397        "**/next/dist/esm/*.shared-runtime.js",
398        "next/dist/shared/lib/app-router-context.shared-runtime.js"
399    )]
400    #[case::star("*", "/foo")]
401    fn glob_not_matching(#[case] glob: &str, #[case] path: &str) {
402        let glob = Glob::parse(RcStr::from(glob), GlobOptions::default()).unwrap();
403
404        println!("{glob:?} {path}");
405
406        assert!(!glob.matches(path));
407    }
408
409    #[test]
410    fn glob_case_insensitive_matching() {
411        let case_sensitive =
412            Glob::parse(rcstr!("case-dir/module*.js"), GlobOptions::default()).unwrap();
413        let case_insensitive = Glob::parse(
414            rcstr!("case-dir/module*.js"),
415            GlobOptions {
416                case_insensitive: true,
417                ..Default::default()
418            },
419        )
420        .unwrap();
421
422        assert!(!case_sensitive.matches("Case-Dir/Module.js"));
423        assert!(case_insensitive.matches("Case-Dir/Module.js"));
424    }
425
426    #[test]
427    fn glob_case_insensitive_directory_matching() {
428        let case_sensitive =
429            Glob::parse(rcstr!("case-dir/module*.js"), GlobOptions::default()).unwrap();
430        let case_insensitive = Glob::parse(
431            rcstr!("case-dir/module*.js"),
432            GlobOptions {
433                case_insensitive: true,
434                ..Default::default()
435            },
436        )
437        .unwrap();
438
439        assert!(!case_sensitive.can_match_in_directory("Case-Dir"));
440        assert!(case_insensitive.can_match_in_directory("Case-Dir"));
441    }
442
443    #[rstest]
444    #[case::dir_and_file_partial("dir/file.js", "dir")]
445    #[case::dir_star_partial("dir/*.js", "dir")]
446    #[case::globstar_partial("**/**/*.js", "dir")]
447    #[case::globstar_partial("**/**/*.js", "dir/sub")]
448    #[case::globstar_partial("**/**/*.js", "dir/sub/file.js")] // This demonstrates some ambiguity in naming. `file.js` might be a directory name.
449    #[case::globstar_in_dir_partial("dir/**/sub/file.js", "dir")]
450    #[case::globstar_in_dir_partial("dir/**/sub/file.js", "dir/a")]
451    #[case::globstar_in_dir_partial("dir/**/sub/file.js", "dir/a/b")]
452    #[case::globstar_in_dir_partial("dir/**/sub/file.js", "dir/a/b/sub")]
453    #[case::globstar_in_dir_partial("dir/**/sub/file.js", "dir/a/b/sub/file.js")]
454    fn glob_can_match_directory(#[case] glob: &str, #[case] path: &str) {
455        let glob = Glob::parse(RcStr::from(glob), GlobOptions::default()).unwrap();
456
457        println!("{glob:?} {path}");
458
459        assert!(glob.can_match_in_directory(path));
460    }
461    #[rstest]
462    #[case::dir_and_file_partial("dir/file.js", "dir/file.js")] // even if there was a dir, named `file.js` we know the glob wasn't intended to match it.
463    #[case::alternatives_chars("[abc]", "b")]
464    fn glob_not_can_match_directory(#[case] glob: &str, #[case] path: &str) {
465        let glob = Glob::parse(RcStr::from(glob), GlobOptions::default()).unwrap();
466
467        println!("{glob:?} {path}");
468
469        assert!(!glob.can_match_in_directory(path));
470    }
471
472    #[rstest]
473    #[case::star("*", "/foo")]
474    #[case::star("*", "foo")]
475    #[case::star("*", "foo/bar")]
476    #[case::prefix("foo/*", "bar/foo/baz")]
477    // This is a possibly surprising case.
478    #[case::dir_match("node_modules/foo", "my_node_modules/foobar")]
479    fn partial_glob_match(#[case] glob: &str, #[case] path: &str) {
480        let glob = Glob::parse(
481            RcStr::from(glob),
482            GlobOptions {
483                contains: true,
484                ..Default::default()
485            },
486        )
487        .unwrap();
488
489        println!("{glob:?} {path}");
490
491        assert!(glob.matches(path));
492    }
493
494    #[rstest]
495    #[case::literal("foo", "bar")]
496    #[case::suffix("*.js", "foo.ts")]
497    #[case::prefix("foo/*", "bar")]
498    // This is a possibly surprising case
499    #[case::dir_match("/node_modules/", "node_modules/")]
500    fn partial_glob_not_matching(#[case] glob: &str, #[case] path: &str) {
501        let glob = Glob::parse(
502            RcStr::from(glob),
503            GlobOptions {
504                contains: true,
505                ..Default::default()
506            },
507        )
508        .unwrap();
509
510        println!("{glob:?} {path}");
511
512        assert!(!glob.matches(path));
513    }
514
515    #[test]
516    fn literal_glob_directory_pruning() {
517        let pattern = rcstr!(
518            "node_modules/.pnpm/lightningcss-wasm@1.28.2/node_modules/lightningcss-wasm/\
519             lightningcss_node.wasm"
520        );
521        let anchored = Glob::parse(pattern, GlobOptions::default()).unwrap();
522
523        assert!(anchored.can_match_in_directory("node_modules"));
524        assert!(anchored.can_match_in_directory("node_modules/.pnpm"));
525        assert!(!anchored.can_match_in_directory("node_modules/next"));
526    }
527
528    #[test]
529    #[should_panic(
530        expected = "Glob::can_match_in_directory cannot be used when GlobOptions::contains is true"
531    )]
532    fn contains_glob_cannot_match_in_directory() {
533        let glob = Glob::parse(
534            rcstr!("node_modules/package_name"),
535            GlobOptions {
536                contains: true,
537                ..Default::default()
538            },
539        )
540        .unwrap();
541
542        glob.can_match_in_directory("node_modules");
543    }
544}
turbo_tasks_fs/glob.rs

turbo_tasks_fs/
glob.rs
