turbopack_core/resolve/
pattern.rs

1use std::{
2    collections::{VecDeque, hash_map::Entry},
3    mem::take,
4    sync::LazyLock,
5};
6
7use anyhow::{Result, bail};
8use bincode::{Decode, Encode};
9use regex::Regex;
10use rustc_hash::{FxHashMap, FxHashSet};
11use tracing::Instrument;
12use turbo_rcstr::{RcStr, rcstr};
13use turbo_tasks::{
14    NonLocalValue, TaskInput, ValueToString, Vc, debug::ValueDebugFormat, trace::TraceRawVcs,
15};
16use turbo_tasks_fs::{
17    FileSystemPath, LinkContent, LinkType, RawDirectoryContent, RawDirectoryEntry,
18};
19use turbo_unix_path::normalize_path;
20
21#[turbo_tasks::value]
22#[derive(Hash, Clone, Debug, Default, ValueToString)]
23#[value_to_string(self.describe_as_string())]
24pub enum Pattern {
25    Constant(RcStr),
26    #[default]
27    Dynamic,
28    DynamicNoSlash,
29    Alternatives(Vec<Pattern>),
30    Concatenation(Vec<Pattern>),
31}
32
33/// manually implement TaskInput to avoid recursion in the implementation of `resolve_input` in the
34/// derived implementation.  We can instead use the default implementation since `Pattern` contains
35/// no VCs.
36impl TaskInput for Pattern {
37    fn is_transient(&self) -> bool {
38        // We contain no vcs so they cannot be transient.
39        false
40    }
41}
42
43fn concatenation_push_or_merge_item(list: &mut Vec<Pattern>, pat: Pattern) {
44    if let Pattern::Constant(ref s) = pat
45        && let Some(Pattern::Constant(last)) = list.last_mut()
46    {
47        let mut buf = last.to_string();
48        buf.push_str(s);
49        *last = buf.into();
50        return;
51    }
52    list.push(pat);
53}
54
55fn concatenation_push_front_or_merge_item(list: &mut Vec<Pattern>, pat: Pattern) {
56    if let Pattern::Constant(s) = pat {
57        if let Some(Pattern::Constant(first)) = list.iter_mut().next() {
58            let mut buf = s.into_owned();
59            buf.push_str(first);
60
61            *first = buf.into();
62            return;
63        }
64        list.insert(0, Pattern::Constant(s));
65    } else {
66        list.insert(0, pat);
67    }
68}
69
70fn concatenation_extend_or_merge_items(
71    list: &mut Vec<Pattern>,
72    mut iter: impl Iterator<Item = Pattern>,
73) {
74    if let Some(first) = iter.next() {
75        concatenation_push_or_merge_item(list, first);
76        list.extend(iter);
77    }
78}
79
80fn longest_common_prefix<'a>(strings: &[&'a str]) -> &'a str {
81    if strings.is_empty() {
82        return "";
83    }
84    if let [single] = strings {
85        return single;
86    }
87    let first = strings[0];
88    let mut len = first.len();
89    for str in &strings[1..] {
90        len = std::cmp::min(
91            len,
92            // TODO these are Unicode Scalar Values, not graphemes
93            str.chars()
94                .zip(first.chars())
95                .take_while(|&(a, b)| a == b)
96                .count(),
97        );
98    }
99    &first[..len]
100}
101
102fn longest_common_suffix<'a>(strings: &[&'a str]) -> &'a str {
103    if strings.is_empty() {
104        return "";
105    }
106    let first = strings[0];
107    let mut len = first.len();
108    for str in &strings[1..] {
109        len = std::cmp::min(
110            len,
111            // TODO these are Unicode Scalar Values, not graphemes
112            str.chars()
113                .rev()
114                .zip(first.chars().rev())
115                .take_while(|&(a, b)| a == b)
116                .count(),
117        );
118    }
119    &first[(first.len() - len)..]
120}
121
122impl Pattern {
123    // TODO this should be removed in favor of pattern resolving
124    pub fn as_constant_string(&self) -> Option<&RcStr> {
125        match self {
126            Pattern::Constant(str) => Some(str),
127            _ => None,
128        }
129    }
130
131    /// Whether the pattern has any significant constant parts (everything except `/`).
132    /// E.g. `<dynamic>/<dynamic>` doesn't really have constant parts
133    pub fn has_constant_parts(&self) -> bool {
134        match self {
135            Pattern::Constant(str) => str != "/",
136            Pattern::Dynamic | Pattern::DynamicNoSlash => false,
137            Pattern::Alternatives(list) | Pattern::Concatenation(list) => {
138                list.iter().any(|p| p.has_constant_parts())
139            }
140        }
141    }
142
143    pub fn has_dynamic_parts(&self) -> bool {
144        match self {
145            Pattern::Constant(_) => false,
146            Pattern::Dynamic | Pattern::DynamicNoSlash => true,
147            Pattern::Alternatives(list) | Pattern::Concatenation(list) => {
148                list.iter().any(|p| p.has_dynamic_parts())
149            }
150        }
151    }
152
153    pub fn constant_prefix(&self) -> &str {
154        // The normalized pattern is an Alternative of maximally merged
155        // Concatenations, so extracting the first/only Concatenation child
156        // elements is enough.
157
158        if let Pattern::Constant(c) = self {
159            return c;
160        }
161
162        fn collect_constant_prefix<'a: 'b, 'b>(pattern: &'a Pattern, result: &mut Vec<&'b str>) {
163            match pattern {
164                Pattern::Constant(c) => {
165                    result.push(c.as_str());
166                }
167                Pattern::Concatenation(list) => {
168                    if let Some(Pattern::Constant(first)) = list.first() {
169                        result.push(first.as_str());
170                    }
171                }
172                Pattern::Alternatives(_) => {
173                    panic!("for constant_prefix a Pattern must be normalized");
174                }
175                Pattern::Dynamic | Pattern::DynamicNoSlash => {}
176            }
177        }
178
179        let mut strings: Vec<&str> = vec![];
180        match self {
181            c @ Pattern::Constant(_) | c @ Pattern::Concatenation(_) => {
182                collect_constant_prefix(c, &mut strings);
183            }
184            Pattern::Alternatives(list) => {
185                for c in list {
186                    collect_constant_prefix(c, &mut strings);
187                }
188            }
189            Pattern::Dynamic | Pattern::DynamicNoSlash => {}
190        }
191        longest_common_prefix(&strings)
192    }
193
194    pub fn constant_suffix(&self) -> &str {
195        // The normalized pattern is an Alternative of maximally merged
196        // Concatenations, so extracting the first/only Concatenation child
197        // elements is enough.
198
199        fn collect_constant_suffix<'a: 'b, 'b>(pattern: &'a Pattern, result: &mut Vec<&'b str>) {
200            match pattern {
201                Pattern::Constant(c) => {
202                    result.push(c.as_str());
203                }
204                Pattern::Concatenation(list) => {
205                    if let Some(Pattern::Constant(first)) = list.last() {
206                        result.push(first.as_str());
207                    }
208                }
209                Pattern::Alternatives(_) => {
210                    panic!("for constant_suffix a Pattern must be normalized");
211                }
212                Pattern::Dynamic | Pattern::DynamicNoSlash => {}
213            }
214        }
215
216        let mut strings: Vec<&str> = vec![];
217        match self {
218            c @ Pattern::Constant(_) | c @ Pattern::Concatenation(_) => {
219                collect_constant_suffix(c, &mut strings);
220            }
221            Pattern::Alternatives(list) => {
222                for c in list {
223                    collect_constant_suffix(c, &mut strings);
224                }
225            }
226            Pattern::Dynamic | Pattern::DynamicNoSlash => {}
227        }
228        longest_common_suffix(&strings)
229    }
230
231    pub fn strip_prefix(&self, prefix: &str) -> Result<Option<Self>> {
232        if self.must_match(prefix) {
233            let mut pat = self.clone();
234            pat.strip_prefix_len(prefix.len())?;
235            Ok(Some(pat))
236        } else {
237            Ok(None)
238        }
239    }
240
241    pub fn strip_prefix_len(&mut self, len: usize) -> Result<()> {
242        fn strip_prefix_internal(pattern: &mut Pattern, chars_to_strip: &mut usize) -> Result<()> {
243            match pattern {
244                Pattern::Constant(c) => {
245                    let c_len = c.len();
246                    if *chars_to_strip >= c_len {
247                        *c = rcstr!("");
248                    } else {
249                        *c = (&c[*chars_to_strip..]).into();
250                    }
251                    *chars_to_strip = (*chars_to_strip).saturating_sub(c_len);
252                }
253                Pattern::Concatenation(list) => {
254                    for c in list {
255                        if *chars_to_strip > 0 {
256                            strip_prefix_internal(c, chars_to_strip)?;
257                        }
258                    }
259                }
260                Pattern::Alternatives(_) => {
261                    bail!("strip_prefix pattern must be normalized");
262                }
263                Pattern::Dynamic | Pattern::DynamicNoSlash => {
264                    bail!("strip_prefix prefix is too long");
265                }
266            }
267            Ok(())
268        }
269
270        match &mut *self {
271            c @ Pattern::Constant(_) | c @ Pattern::Concatenation(_) => {
272                let mut len_local = len;
273                strip_prefix_internal(c, &mut len_local)?;
274            }
275            Pattern::Alternatives(list) => {
276                for c in list {
277                    let mut len_local = len;
278                    strip_prefix_internal(c, &mut len_local)?;
279                }
280            }
281            Pattern::Dynamic | Pattern::DynamicNoSlash => {
282                if len > 0 {
283                    bail!(
284                        "strip_prefix prefix ({}) is too long: {}",
285                        len,
286                        self.describe_as_string()
287                    );
288                }
289            }
290        };
291
292        self.normalize();
293
294        Ok(())
295    }
296
297    pub fn strip_suffix_len(&mut self, len: usize) {
298        fn strip_suffix_internal(pattern: &mut Pattern, chars_to_strip: &mut usize) {
299            match pattern {
300                Pattern::Constant(c) => {
301                    let c_len = c.len();
302                    if *chars_to_strip >= c_len {
303                        *c = rcstr!("");
304                    } else {
305                        *c = (&c[..(c_len - *chars_to_strip)]).into();
306                    }
307                    *chars_to_strip = (*chars_to_strip).saturating_sub(c_len);
308                }
309                Pattern::Concatenation(list) => {
310                    for c in list.iter_mut().rev() {
311                        if *chars_to_strip > 0 {
312                            strip_suffix_internal(c, chars_to_strip);
313                        }
314                    }
315                }
316                Pattern::Alternatives(_) => {
317                    panic!("for strip_suffix a Pattern must be normalized");
318                }
319                Pattern::Dynamic | Pattern::DynamicNoSlash => {
320                    panic!("strip_suffix suffix is too long");
321                }
322            }
323        }
324
325        match &mut *self {
326            c @ Pattern::Constant(_) | c @ Pattern::Concatenation(_) => {
327                let mut len_local = len;
328                strip_suffix_internal(c, &mut len_local);
329            }
330            Pattern::Alternatives(list) => {
331                for c in list {
332                    let mut len_local = len;
333                    strip_suffix_internal(c, &mut len_local);
334                }
335            }
336            Pattern::Dynamic | Pattern::DynamicNoSlash => {
337                if len > 0 {
338                    panic!("strip_suffix suffix is too long");
339                }
340            }
341        };
342
343        self.normalize()
344    }
345
346    /// Replace all `*`s in `template` with self.
347    ///
348    /// Handle top-level alternatives separately so that multiple star placeholders
349    /// match the same pattern instead of the whole alternative.
350    pub fn spread_into_star(&self, template: &str) -> Pattern {
351        if template.contains("*") {
352            let alternatives: Box<dyn Iterator<Item = &Pattern>> = match self {
353                Pattern::Alternatives(list) => Box::new(list.iter()),
354                c => Box::new(std::iter::once(c)),
355            };
356
357            let mut result = Pattern::alternatives(alternatives.map(|pat| {
358                let mut split = template.split("*");
359                let mut concatenation: Vec<Pattern> = Vec::with_capacity(3);
360
361                // There are at least two elements in the iterator
362                concatenation.push(Pattern::Constant(split.next().unwrap().into()));
363
364                for part in split {
365                    concatenation.push(pat.clone());
366                    if !part.is_empty() {
367                        concatenation.push(Pattern::Constant(part.into()));
368                    }
369                }
370                Pattern::Concatenation(concatenation)
371            }));
372
373            result.normalize();
374            result
375        } else {
376            Pattern::Constant(template.into())
377        }
378    }
379
380    /// Appends something to end the pattern.
381    pub fn extend(&mut self, concatenated: impl Iterator<Item = Self>) {
382        if let Pattern::Concatenation(list) = self {
383            concatenation_extend_or_merge_items(list, concatenated);
384        } else {
385            let mut vec = vec![take(self)];
386            for item in concatenated {
387                if let Pattern::Concatenation(more) = item {
388                    concatenation_extend_or_merge_items(&mut vec, more.into_iter());
389                } else {
390                    concatenation_push_or_merge_item(&mut vec, item);
391                }
392            }
393            *self = Pattern::Concatenation(vec);
394        }
395    }
396
397    /// Appends something to end the pattern.
398    pub fn push(&mut self, pat: Pattern) {
399        if let Pattern::Constant(this) = &*self
400            && this.is_empty()
401        {
402            // Short-circuit to replace empty constants with the appended pattern
403            *self = pat;
404            return;
405        }
406        if let Pattern::Constant(pat) = &pat
407            && pat.is_empty()
408        {
409            // Short-circuit to ignore when trying to append an empty string.
410            return;
411        }
412
413        match (self, pat) {
414            (Pattern::Concatenation(list), Pattern::Concatenation(more)) => {
415                concatenation_extend_or_merge_items(list, more.into_iter());
416            }
417            (Pattern::Concatenation(list), pat) => {
418                concatenation_push_or_merge_item(list, pat);
419            }
420            (this, Pattern::Concatenation(mut list)) => {
421                concatenation_push_front_or_merge_item(&mut list, take(this));
422                *this = Pattern::Concatenation(list);
423            }
424            (Pattern::Constant(str), Pattern::Constant(other)) => {
425                let mut buf = str.to_string();
426                buf.push_str(&other);
427                *str = buf.into();
428            }
429            (this, pat) => {
430                *this = Pattern::Concatenation(vec![take(this), pat]);
431            }
432        }
433    }
434
435    /// Prepends something to front of the pattern.
436    pub fn push_front(&mut self, pat: Pattern) {
437        match (self, pat) {
438            (Pattern::Concatenation(list), Pattern::Concatenation(mut more)) => {
439                concatenation_extend_or_merge_items(&mut more, take(list).into_iter());
440                *list = more;
441            }
442            (Pattern::Concatenation(list), pat) => {
443                concatenation_push_front_or_merge_item(list, pat);
444            }
445            (this, Pattern::Concatenation(mut list)) => {
446                concatenation_push_or_merge_item(&mut list, take(this));
447                *this = Pattern::Concatenation(list);
448            }
449            (Pattern::Constant(str), Pattern::Constant(other)) => {
450                let mut buf = other.into_owned();
451
452                buf.push_str(str);
453                *str = buf.into();
454            }
455            (this, pat) => {
456                *this = Pattern::Concatenation(vec![pat, take(this)]);
457            }
458        }
459    }
460
461    pub fn alternatives(alts: impl IntoIterator<Item = Pattern>) -> Self {
462        let mut list = Vec::new();
463        for alt in alts {
464            if let Pattern::Alternatives(inner) = alt {
465                list.extend(inner);
466            } else {
467                list.push(alt)
468            }
469        }
470        Self::Alternatives(list)
471    }
472
473    pub fn concat(items: impl IntoIterator<Item = Pattern>) -> Self {
474        let mut items = items.into_iter();
475        let mut current = items.next().unwrap_or_default();
476        for item in items {
477            current.push(item);
478        }
479        current
480    }
481
482    /// Normalizes paths by
483    /// - processing path segments: `.` and `..`
484    /// - normalizing windows filepaths by replacing `\` with `/`
485    ///
486    /// The Pattern must have already been processed by [Self::normalize].
487    /// Returns [Option::None] if any of the patterns attempt to navigate out of the root.
488    pub fn with_normalized_path(&self) -> Option<Pattern> {
489        let mut new = self.clone();
490
491        #[derive(Debug)]
492        enum PathElement {
493            Segment(Pattern),
494            Separator,
495        }
496
497        fn normalize_path_internal(pattern: &mut Pattern) -> Option<()> {
498            match pattern {
499                Pattern::Constant(c) => {
500                    let normalized = c.replace('\\', "/");
501                    *c = RcStr::from(normalize_path(normalized.as_str())?);
502                    Some(())
503                }
504                Pattern::Dynamic | Pattern::DynamicNoSlash => Some(()),
505                Pattern::Concatenation(list) => {
506                    let mut segments = Vec::new();
507                    for segment in list.iter() {
508                        match segment {
509                            Pattern::Constant(str) => {
510                                let mut iter = str.split('/').peekable();
511                                while let Some(segment) = iter.next() {
512                                    match segment {
513                                        "." | "" => {
514                                            // Ignore empty segments
515                                            continue;
516                                        }
517                                        ".." => {
518                                            if segments.is_empty() {
519                                                // Leaving root
520                                                return None;
521                                            }
522
523                                            if let Some(PathElement::Separator) = segments.last()
524                                                && let Some(PathElement::Segment(
525                                                    Pattern::Constant(_),
526                                                )) = segments.get(segments.len() - 2)
527                                            {
528                                                // Resolve `foo/..`
529                                                segments.truncate(segments.len() - 2);
530                                                continue;
531                                            }
532
533                                            // Keep it, can't pop non-constant segment.
534                                            segments.push(PathElement::Segment(Pattern::Constant(
535                                                rcstr!(".."),
536                                            )));
537                                        }
538                                        segment => {
539                                            segments.push(PathElement::Segment(Pattern::Constant(
540                                                segment.into(),
541                                            )));
542                                        }
543                                    }
544
545                                    if iter.peek().is_some() {
546                                        // If not last, add separator
547                                        segments.push(PathElement::Separator);
548                                    }
549                                }
550                            }
551                            Pattern::Dynamic | Pattern::DynamicNoSlash => {
552                                segments.push(PathElement::Segment(segment.clone()));
553                            }
554                            Pattern::Alternatives(_) | Pattern::Concatenation(_) => {
555                                panic!("for with_normalized_path the Pattern must be normalized");
556                            }
557                        }
558                    }
559                    let separator = rcstr!("/");
560                    *list = segments
561                        .into_iter()
562                        .map(|c| match c {
563                            PathElement::Segment(p) => p,
564                            PathElement::Separator => Pattern::Constant(separator.clone()),
565                        })
566                        .collect();
567                    Some(())
568                }
569                Pattern::Alternatives(_) => {
570                    panic!("for with_normalized_path the Pattern must be normalized");
571                }
572            }
573        }
574
575        match &mut new {
576            c @ Pattern::Constant(_) | c @ Pattern::Concatenation(_) => {
577                normalize_path_internal(c)?;
578            }
579            Pattern::Alternatives(list) => {
580                for c in list {
581                    normalize_path_internal(c)?;
582                }
583            }
584            Pattern::Dynamic | Pattern::DynamicNoSlash => {}
585        }
586
587        new.normalize();
588        Some(new)
589    }
590
591    /// Order into Alternatives -> Concatenation -> Constant/Dynamic
592    /// Merge when possible
593    pub fn normalize(&mut self) {
594        match self {
595            Pattern::Dynamic | Pattern::DynamicNoSlash | Pattern::Constant(_) => {
596                // already normalized
597            }
598            Pattern::Alternatives(list) => {
599                for alt in list.iter_mut() {
600                    alt.normalize();
601                }
602                let mut new_alternatives = Vec::new();
603                let mut has_dynamic = false;
604                for alt in list.drain(..) {
605                    if let Pattern::Alternatives(inner) = alt {
606                        for alt in inner {
607                            if alt == Pattern::Dynamic {
608                                if !has_dynamic {
609                                    has_dynamic = true;
610                                    new_alternatives.push(alt);
611                                }
612                            } else {
613                                new_alternatives.push(alt);
614                            }
615                        }
616                    } else if alt == Pattern::Dynamic {
617                        if !has_dynamic {
618                            has_dynamic = true;
619                            new_alternatives.push(alt);
620                        }
621                    } else {
622                        new_alternatives.push(alt);
623                    }
624                }
625                if new_alternatives.len() == 1 {
626                    *self = new_alternatives.into_iter().next().unwrap();
627                } else {
628                    *list = new_alternatives;
629                }
630            }
631            Pattern::Concatenation(list) => {
632                let mut has_alternatives = false;
633                for part in list.iter_mut() {
634                    part.normalize();
635                    if let Pattern::Alternatives(_) = part {
636                        has_alternatives = true;
637                    }
638                }
639                if has_alternatives {
640                    // list has items that are one of these
641                    // * Alternatives -> [Concatenation] -> ...
642                    // * [Concatenation] -> ...
643                    let mut new_alternatives: Vec<Vec<Pattern>> = vec![Vec::new()];
644                    for part in list.drain(..) {
645                        if let Pattern::Alternatives(list) = part {
646                            // list is [Concatenation] -> ...
647                            let mut combined = Vec::new();
648                            for alt2 in list.iter() {
649                                for mut alt in new_alternatives.clone() {
650                                    if let Pattern::Concatenation(parts) = alt2 {
651                                        alt.extend(parts.clone());
652                                    } else {
653                                        alt.push(alt2.clone());
654                                    }
655                                    combined.push(alt)
656                                }
657                            }
658                            new_alternatives = combined;
659                        } else {
660                            // part is [Concatenation] -> ...
661                            for alt in new_alternatives.iter_mut() {
662                                if let Pattern::Concatenation(ref parts) = part {
663                                    alt.extend(parts.clone());
664                                } else {
665                                    alt.push(part.clone());
666                                }
667                            }
668                        }
669                    }
670                    // new_alternatives has items in that form:
671                    // * [Concatenation] -> ...
672                    *self = Pattern::Alternatives(
673                        new_alternatives
674                            .into_iter()
675                            .map(|parts| {
676                                if parts.len() == 1 {
677                                    parts.into_iter().next().unwrap()
678                                } else {
679                                    Pattern::Concatenation(parts)
680                                }
681                            })
682                            .collect(),
683                    );
684                    // The recursive call will deduplicate the alternatives after simplifying them
685                    self.normalize();
686                } else {
687                    let mut new_parts = Vec::new();
688                    for part in list.drain(..) {
689                        fn add_part(part: Pattern, new_parts: &mut Vec<Pattern>) {
690                            match part {
691                                Pattern::Constant(c) => {
692                                    if !c.is_empty() {
693                                        if let Some(Pattern::Constant(last)) = new_parts.last_mut()
694                                        {
695                                            let mut buf = last.to_string();
696                                            buf.push_str(&c);
697                                            *last = buf.into();
698                                        } else {
699                                            new_parts.push(Pattern::Constant(c));
700                                        }
701                                    }
702                                }
703                                Pattern::Dynamic => {
704                                    if let Some(Pattern::Dynamic | Pattern::DynamicNoSlash) =
705                                        new_parts.last()
706                                    {
707                                        // do nothing
708                                    } else {
709                                        new_parts.push(Pattern::Dynamic);
710                                    }
711                                }
712                                Pattern::DynamicNoSlash => {
713                                    if let Some(Pattern::DynamicNoSlash) = new_parts.last() {
714                                        // do nothing
715                                    } else {
716                                        new_parts.push(Pattern::DynamicNoSlash);
717                                    }
718                                }
719                                Pattern::Concatenation(parts) => {
720                                    for part in parts {
721                                        add_part(part, new_parts);
722                                    }
723                                }
724                                Pattern::Alternatives(_) => unreachable!(),
725                            }
726                        }
727
728                        add_part(part, &mut new_parts);
729                    }
730                    if new_parts.len() == 1 {
731                        *self = new_parts.into_iter().next().unwrap();
732                    } else {
733                        *list = new_parts;
734                    }
735                }
736            }
737        }
738    }
739
740    pub fn is_empty(&self) -> bool {
741        match self {
742            Pattern::Constant(s) => s.is_empty(),
743            Pattern::Dynamic | Pattern::DynamicNoSlash => false,
744            Pattern::Concatenation(parts) => parts.iter().all(|p| p.is_empty()),
745            Pattern::Alternatives(parts) => parts.iter().all(|p| p.is_empty()),
746        }
747    }
748
749    pub fn filter_could_match(&self, value: &str) -> Option<Pattern> {
750        if let Pattern::Alternatives(list) = self {
751            let new_list = list
752                .iter()
753                .filter(|alt| alt.could_match(value))
754                .cloned()
755                .collect::<Vec<_>>();
756            if new_list.is_empty() {
757                None
758            } else {
759                Some(Pattern::Alternatives(new_list))
760            }
761        } else if self.could_match(value) {
762            Some(self.clone())
763        } else {
764            None
765        }
766    }
767
768    pub fn filter_could_not_match(&self, value: &str) -> Option<Pattern> {
769        if let Pattern::Alternatives(list) = self {
770            let new_list = list
771                .iter()
772                .filter(|alt| !alt.could_match(value))
773                .cloned()
774                .collect::<Vec<_>>();
775            if new_list.is_empty() {
776                None
777            } else {
778                Some(Pattern::Alternatives(new_list))
779            }
780        } else if self.could_match(value) {
781            None
782        } else {
783            Some(self.clone())
784        }
785    }
786
787    pub fn split_could_match(&self, value: &str) -> (Option<Pattern>, Option<Pattern>) {
788        if let Pattern::Alternatives(list) = self {
789            let mut could_match_list = Vec::new();
790            let mut could_not_match_list = Vec::new();
791            for alt in list.iter() {
792                if alt.could_match(value) {
793                    could_match_list.push(alt.clone());
794                } else {
795                    could_not_match_list.push(alt.clone());
796                }
797            }
798            (
799                if could_match_list.is_empty() {
800                    None
801                } else if could_match_list.len() == 1 {
802                    Some(could_match_list.into_iter().next().unwrap())
803                } else {
804                    Some(Pattern::Alternatives(could_match_list))
805                },
806                if could_not_match_list.is_empty() {
807                    None
808                } else if could_not_match_list.len() == 1 {
809                    Some(could_not_match_list.into_iter().next().unwrap())
810                } else {
811                    Some(Pattern::Alternatives(could_not_match_list))
812                },
813            )
814        } else if self.could_match(value) {
815            (Some(self.clone()), None)
816        } else {
817            (None, Some(self.clone()))
818        }
819    }
820
821    pub fn is_match(&self, value: &str) -> bool {
822        if let Pattern::Alternatives(list) = self {
823            list.iter().any(|alt| {
824                alt.match_internal(value, None, InNodeModules::False, false)
825                    .is_match()
826            })
827        } else {
828            self.match_internal(value, None, InNodeModules::False, false)
829                .is_match()
830        }
831    }
832
833    /// Like [`Pattern::is_match`], but does not consider any dynamic
834    /// pattern matching
835    pub fn is_match_ignore_dynamic(&self, value: &str) -> bool {
836        if let Pattern::Alternatives(list) = self {
837            list.iter().any(|alt| {
838                alt.match_internal(value, None, InNodeModules::False, true)
839                    .is_match()
840            })
841        } else {
842            self.match_internal(value, None, InNodeModules::False, true)
843                .is_match()
844        }
845    }
846
847    pub fn match_position(&self, value: &str) -> Option<usize> {
848        if let Pattern::Alternatives(list) = self {
849            list.iter().position(|alt| {
850                alt.match_internal(value, None, InNodeModules::False, false)
851                    .is_match()
852            })
853        } else {
854            self.match_internal(value, None, InNodeModules::False, false)
855                .is_match()
856                .then_some(0)
857        }
858    }
859
860    pub fn could_match_others(&self, value: &str) -> bool {
861        if let Pattern::Alternatives(list) = self {
862            list.iter().any(|alt| {
863                alt.match_internal(value, None, InNodeModules::False, false)
864                    .could_match_others()
865            })
866        } else {
867            self.match_internal(value, None, InNodeModules::False, false)
868                .could_match_others()
869        }
870    }
871
872    /// Returns true if all matches of the pattern start with `value`.
873    pub fn must_match(&self, value: &str) -> bool {
874        if let Pattern::Alternatives(list) = self {
875            list.iter().all(|alt| {
876                alt.match_internal(value, None, InNodeModules::False, false)
877                    .could_match()
878            })
879        } else {
880            self.match_internal(value, None, InNodeModules::False, false)
881                .could_match()
882        }
883    }
884
885    /// Returns true the pattern could match something that starts with `value`.
886    pub fn could_match(&self, value: &str) -> bool {
887        if let Pattern::Alternatives(list) = self {
888            list.iter().any(|alt| {
889                alt.match_internal(value, None, InNodeModules::False, false)
890                    .could_match()
891            })
892        } else {
893            self.match_internal(value, None, InNodeModules::False, false)
894                .could_match()
895        }
896    }
897
898    pub fn could_match_position(&self, value: &str) -> Option<usize> {
899        if let Pattern::Alternatives(list) = self {
900            list.iter().position(|alt| {
901                alt.match_internal(value, None, InNodeModules::False, false)
902                    .could_match()
903            })
904        } else {
905            self.match_internal(value, None, InNodeModules::False, false)
906                .could_match()
907                .then_some(0)
908        }
909    }
910    fn match_internal<'a>(
911        &self,
912        mut value: &'a str,
913        mut any_offset: Option<usize>,
914        mut in_node_modules: InNodeModules,
915        ignore_dynamic: bool,
916    ) -> MatchResult<'a> {
917        match self {
918            Pattern::Constant(c) => {
919                if let Some(offset) = any_offset {
920                    if let Some(index) = value.find(&**c) {
921                        if index <= offset {
922                            MatchResult::Consumed {
923                                remaining: &value[index + c.len()..],
924                                any_offset: None,
925                                in_node_modules: InNodeModules::check(c),
926                            }
927                        } else {
928                            MatchResult::None
929                        }
930                    } else if offset >= value.len() {
931                        MatchResult::Partial
932                    } else {
933                        MatchResult::None
934                    }
935                } else if value.starts_with(&**c) {
936                    MatchResult::Consumed {
937                        remaining: &value[c.len()..],
938                        any_offset: None,
939                        in_node_modules: InNodeModules::check(c),
940                    }
941                } else if c.starts_with(value) {
942                    MatchResult::Partial
943                } else {
944                    MatchResult::None
945                }
946            }
947            Pattern::Dynamic | Pattern::DynamicNoSlash => {
948                static FORBIDDEN: LazyLock<Regex> = LazyLock::new(|| {
949                    Regex::new(r"(/|^)(ROOT|\.|/|(node_modules|__tests?__)(/|$))").unwrap()
950                });
951                static FORBIDDEN_MATCH: LazyLock<Regex> =
952                    LazyLock::new(|| Regex::new(r"\.d\.ts$|\.map$").unwrap());
953                if in_node_modules == InNodeModules::FolderSlashMatched
954                    || (in_node_modules == InNodeModules::FolderMatched && value.starts_with('/'))
955                {
956                    MatchResult::None
957                } else if let Some(m) = FORBIDDEN.find(value) {
958                    MatchResult::Consumed {
959                        remaining: value,
960                        any_offset: Some(m.start()),
961                        in_node_modules: InNodeModules::False,
962                    }
963                } else if FORBIDDEN_MATCH.find(value).is_some() {
964                    MatchResult::Partial
965                } else if ignore_dynamic {
966                    MatchResult::None
967                } else {
968                    let match_length = matches!(self, Pattern::DynamicNoSlash)
969                        .then(|| value.find("/"))
970                        .flatten()
971                        .unwrap_or(value.len());
972                    MatchResult::Consumed {
973                        remaining: value,
974                        any_offset: Some(match_length),
975                        in_node_modules: InNodeModules::False,
976                    }
977                }
978            }
979            Pattern::Alternatives(_) => {
980                panic!("for matching a Pattern must be normalized {self:?}")
981            }
982            Pattern::Concatenation(list) => {
983                for part in list {
984                    match part.match_internal(value, any_offset, in_node_modules, ignore_dynamic) {
985                        MatchResult::None => return MatchResult::None,
986                        MatchResult::Partial => return MatchResult::Partial,
987                        MatchResult::Consumed {
988                            remaining: new_value,
989                            any_offset: new_any_offset,
990                            in_node_modules: new_in_node_modules,
991                        } => {
992                            value = new_value;
993                            any_offset = new_any_offset;
994                            in_node_modules = new_in_node_modules
995                        }
996                    }
997                }
998                MatchResult::Consumed {
999                    remaining: value,
1000                    any_offset,
1001                    in_node_modules,
1002                }
1003            }
1004        }
1005    }
1006
1007    /// Same as `match_internal`, but additionally pushing matched dynamic elements into the given
1008    /// result list.
1009    fn match_collect_internal<'a>(
1010        &self,
1011        mut value: &'a str,
1012        mut any_offset: Option<usize>,
1013        mut in_node_modules: InNodeModules,
1014        dynamics: &mut VecDeque<&'a str>,
1015    ) -> MatchResult<'a> {
1016        match self {
1017            Pattern::Constant(c) => {
1018                if let Some(offset) = any_offset {
1019                    if let Some(index) = value.find(&**c) {
1020                        if index <= offset {
1021                            if index > 0 {
1022                                dynamics.push_back(&value[..index]);
1023                            }
1024                            MatchResult::Consumed {
1025                                remaining: &value[index + c.len()..],
1026                                any_offset: None,
1027                                in_node_modules: InNodeModules::check(c),
1028                            }
1029                        } else {
1030                            MatchResult::None
1031                        }
1032                    } else if offset >= value.len() {
1033                        MatchResult::Partial
1034                    } else {
1035                        MatchResult::None
1036                    }
1037                } else if value.starts_with(&**c) {
1038                    MatchResult::Consumed {
1039                        remaining: &value[c.len()..],
1040                        any_offset: None,
1041                        in_node_modules: InNodeModules::check(c),
1042                    }
1043                } else if c.starts_with(value) {
1044                    MatchResult::Partial
1045                } else {
1046                    MatchResult::None
1047                }
1048            }
1049            Pattern::Dynamic | Pattern::DynamicNoSlash => {
1050                static FORBIDDEN: LazyLock<Regex> = LazyLock::new(|| {
1051                    Regex::new(r"(/|^)(ROOT|\.|/|(node_modules|__tests?__)(/|$))").unwrap()
1052                });
1053                static FORBIDDEN_MATCH: LazyLock<Regex> =
1054                    LazyLock::new(|| Regex::new(r"\.d\.ts$|\.map$").unwrap());
1055                if in_node_modules == InNodeModules::FolderSlashMatched
1056                    || (in_node_modules == InNodeModules::FolderMatched && value.starts_with('/'))
1057                {
1058                    MatchResult::None
1059                } else if let Some(m) = FORBIDDEN.find(value) {
1060                    MatchResult::Consumed {
1061                        remaining: value,
1062                        any_offset: Some(m.start()),
1063                        in_node_modules: InNodeModules::False,
1064                    }
1065                } else if FORBIDDEN_MATCH.find(value).is_some() {
1066                    MatchResult::Partial
1067                } else {
1068                    let match_length = matches!(self, Pattern::DynamicNoSlash)
1069                        .then(|| value.find("/"))
1070                        .flatten()
1071                        .unwrap_or(value.len());
1072                    MatchResult::Consumed {
1073                        remaining: value,
1074                        any_offset: Some(match_length),
1075                        in_node_modules: InNodeModules::False,
1076                    }
1077                }
1078            }
1079            Pattern::Alternatives(_) => {
1080                panic!("for matching a Pattern must be normalized {self:?}")
1081            }
1082            Pattern::Concatenation(list) => {
1083                for part in list {
1084                    match part.match_collect_internal(value, any_offset, in_node_modules, dynamics)
1085                    {
1086                        MatchResult::None => return MatchResult::None,
1087                        MatchResult::Partial => return MatchResult::Partial,
1088                        MatchResult::Consumed {
1089                            remaining: new_value,
1090                            any_offset: new_any_offset,
1091                            in_node_modules: new_in_node_modules,
1092                        } => {
1093                            value = new_value;
1094                            any_offset = new_any_offset;
1095                            in_node_modules = new_in_node_modules
1096                        }
1097                    }
1098                }
1099                if let Some(offset) = any_offset
1100                    && offset == value.len()
1101                {
1102                    dynamics.push_back(value);
1103                }
1104                MatchResult::Consumed {
1105                    remaining: value,
1106                    any_offset,
1107                    in_node_modules,
1108                }
1109            }
1110        }
1111    }
1112
1113    pub fn next_constants<'a>(&'a self, value: &str) -> Option<Vec<(&'a str, bool)>> {
1114        if let Pattern::Alternatives(list) = self {
1115            let mut results = Vec::new();
1116            for alt in list.iter() {
1117                match alt.next_constants_internal(value, None) {
1118                    NextConstantUntilResult::NoMatch => {}
1119                    NextConstantUntilResult::PartialDynamic => {
1120                        return None;
1121                    }
1122                    NextConstantUntilResult::Partial(s, end) => {
1123                        results.push((s, end));
1124                    }
1125                    NextConstantUntilResult::Consumed(rem, None) => {
1126                        if rem.is_empty() {
1127                            results.push(("", true));
1128                        }
1129                    }
1130                    NextConstantUntilResult::Consumed(rem, Some(any)) => {
1131                        if any == rem.len() {
1132                            // can match anything
1133                            // we don't have constant only matches
1134                            return None;
1135                        }
1136                    }
1137                }
1138            }
1139            Some(results)
1140        } else {
1141            match self.next_constants_internal(value, None) {
1142                NextConstantUntilResult::NoMatch => None,
1143                NextConstantUntilResult::PartialDynamic => None,
1144                NextConstantUntilResult::Partial(s, e) => Some(vec![(s, e)]),
1145                NextConstantUntilResult::Consumed(_, _) => None,
1146            }
1147        }
1148    }
1149
1150    fn next_constants_internal<'a, 'b>(
1151        &'a self,
1152        mut value: &'b str,
1153        mut any_offset: Option<usize>,
1154    ) -> NextConstantUntilResult<'a, 'b> {
1155        match self {
1156            Pattern::Constant(c) => {
1157                if let Some(offset) = any_offset {
1158                    if let Some(index) = value.find(&**c) {
1159                        if index <= offset {
1160                            NextConstantUntilResult::Consumed(&value[index + c.len()..], None)
1161                        } else {
1162                            NextConstantUntilResult::NoMatch
1163                        }
1164                    } else if offset >= value.len() {
1165                        NextConstantUntilResult::PartialDynamic
1166                    } else {
1167                        NextConstantUntilResult::NoMatch
1168                    }
1169                } else if let Some(stripped) = value.strip_prefix(&**c) {
1170                    NextConstantUntilResult::Consumed(stripped, None)
1171                } else if let Some(stripped) = c.strip_prefix(value) {
1172                    NextConstantUntilResult::Partial(stripped, true)
1173                } else {
1174                    NextConstantUntilResult::NoMatch
1175                }
1176            }
1177            Pattern::Dynamic | Pattern::DynamicNoSlash => {
1178                static FORBIDDEN: LazyLock<Regex> = LazyLock::new(|| {
1179                    Regex::new(r"(/|^)(\.|(node_modules|__tests?__)(/|$))").unwrap()
1180                });
1181                static FORBIDDEN_MATCH: LazyLock<Regex> =
1182                    LazyLock::new(|| Regex::new(r"\.d\.ts$|\.map$").unwrap());
1183                if let Some(m) = FORBIDDEN.find(value) {
1184                    NextConstantUntilResult::Consumed(value, Some(m.start()))
1185                } else if FORBIDDEN_MATCH.find(value).is_some() {
1186                    NextConstantUntilResult::PartialDynamic
1187                } else {
1188                    NextConstantUntilResult::Consumed(value, Some(value.len()))
1189                }
1190            }
1191            Pattern::Alternatives(_) => {
1192                panic!("for next_constants() the Pattern must be normalized");
1193            }
1194            Pattern::Concatenation(list) => {
1195                let mut iter = list.iter();
1196                while let Some(part) = iter.next() {
1197                    match part.next_constants_internal(value, any_offset) {
1198                        NextConstantUntilResult::NoMatch => {
1199                            return NextConstantUntilResult::NoMatch;
1200                        }
1201                        NextConstantUntilResult::PartialDynamic => {
1202                            return NextConstantUntilResult::PartialDynamic;
1203                        }
1204                        NextConstantUntilResult::Partial(r, end) => {
1205                            return NextConstantUntilResult::Partial(
1206                                r,
1207                                end && iter.next().is_none(),
1208                            );
1209                        }
1210                        NextConstantUntilResult::Consumed(new_value, new_any_offset) => {
1211                            value = new_value;
1212                            any_offset = new_any_offset;
1213                        }
1214                    }
1215                }
1216                NextConstantUntilResult::Consumed(value, any_offset)
1217            }
1218        }
1219    }
1220
1221    pub fn or_any_nested_file(&self) -> Self {
1222        let mut new = self.clone();
1223        new.push(Pattern::Constant(rcstr!("/")));
1224        new.push(Pattern::Dynamic);
1225        new.normalize();
1226        Pattern::alternatives([self.clone(), new])
1227    }
1228
1229    /// Calls `cb` on all constants that are at the end of the pattern and
1230    /// replaces the given final constant with the returned pattern. Returns
1231    /// true if replacements were performed.
1232    pub fn replace_final_constants(
1233        &mut self,
1234        cb: &mut impl FnMut(&RcStr) -> Option<Pattern>,
1235    ) -> bool {
1236        let mut replaced = false;
1237        match self {
1238            Pattern::Constant(c) => {
1239                if let Some(replacement) = cb(c) {
1240                    *self = replacement;
1241                    replaced = true;
1242                }
1243            }
1244            Pattern::Dynamic | Pattern::DynamicNoSlash => {}
1245            Pattern::Alternatives(list) => {
1246                for i in list {
1247                    replaced = i.replace_final_constants(cb) || replaced;
1248                }
1249            }
1250            Pattern::Concatenation(list) => {
1251                if let Some(i) = list.last_mut() {
1252                    replaced = i.replace_final_constants(cb) || replaced;
1253                }
1254            }
1255        }
1256        replaced
1257    }
1258
1259    /// Calls `cb` on all constants and replaces the them with the returned pattern. Returns true if
1260    /// replacements were performed.
1261    pub fn replace_constants(&mut self, cb: &impl Fn(&RcStr) -> Option<Pattern>) -> bool {
1262        let mut replaced = false;
1263        match self {
1264            Pattern::Constant(c) => {
1265                if let Some(replacement) = cb(c) {
1266                    *self = replacement;
1267                    replaced = true;
1268                }
1269            }
1270            Pattern::Dynamic | Pattern::DynamicNoSlash => {}
1271            Pattern::Concatenation(list) | Pattern::Alternatives(list) => {
1272                for i in list {
1273                    replaced = i.replace_constants(cb) || replaced;
1274                }
1275            }
1276        }
1277        replaced
1278    }
1279
1280    /// Matches the given string against self, and applies the match onto the target pattern.
1281    ///
1282    /// The two patterns should have a similar structure (same number of alternatives and dynamics)
1283    /// and only differ in the constant contents.
1284    pub fn match_apply_template(&self, value: &str, target: &Pattern) -> Option<String> {
1285        let match_idx = self.match_position(value)?;
1286        let source = match self {
1287            Pattern::Alternatives(list) => list.get(match_idx),
1288            Pattern::Constant(_) | Pattern::Dynamic | Pattern::Concatenation(_)
1289                if match_idx == 0 =>
1290            {
1291                Some(self)
1292            }
1293            _ => None,
1294        }?;
1295        let target = match target {
1296            Pattern::Alternatives(list) => list.get(match_idx),
1297            Pattern::Constant(_) | Pattern::Dynamic | Pattern::Concatenation(_)
1298                if match_idx == 0 =>
1299            {
1300                Some(target)
1301            }
1302            _ => None,
1303        }?;
1304
1305        let mut dynamics = VecDeque::new();
1306        // This is definitely a match, because it matched above in `self.match_position(value)`
1307        source.match_collect_internal(value, None, InNodeModules::False, &mut dynamics);
1308
1309        let mut result = "".to_string();
1310        match target {
1311            Pattern::Constant(c) => result.push_str(c),
1312            Pattern::Dynamic | Pattern::DynamicNoSlash => result.push_str(dynamics.pop_front()?),
1313            Pattern::Concatenation(list) => {
1314                for c in list {
1315                    match c {
1316                        Pattern::Constant(c) => result.push_str(c),
1317                        Pattern::Dynamic | Pattern::DynamicNoSlash => {
1318                            result.push_str(dynamics.pop_front()?)
1319                        }
1320                        Pattern::Alternatives(_) | Pattern::Concatenation(_) => {
1321                            panic!("Pattern must be normalized")
1322                        }
1323                    }
1324                }
1325            }
1326            Pattern::Alternatives(_) => panic!("Pattern must be normalized"),
1327        }
1328        if !dynamics.is_empty() {
1329            return None;
1330        }
1331
1332        Some(result)
1333    }
1334}
1335
1336impl Pattern {
1337    pub fn new(mut pattern: Pattern) -> Vc<Self> {
1338        pattern.normalize();
1339        Pattern::new_internal(pattern)
1340    }
1341}
1342
1343#[turbo_tasks::value_impl]
1344impl Pattern {
1345    #[turbo_tasks::function]
1346    fn new_internal(pattern: Pattern) -> Vc<Self> {
1347        Self::cell(pattern)
1348    }
1349}
1350
1351#[derive(PartialEq, Debug)]
1352enum InNodeModules {
1353    False,
1354    // Inside of a match ending in `node_modules`
1355    FolderMatched,
1356    // Inside of a match ending in `node_modules/`
1357    FolderSlashMatched,
1358}
1359impl InNodeModules {
1360    fn check(value: &str) -> Self {
1361        if value.ends_with("node_modules/") {
1362            InNodeModules::FolderSlashMatched
1363        } else if value.ends_with("node_modules") {
1364            InNodeModules::FolderMatched
1365        } else {
1366            InNodeModules::False
1367        }
1368    }
1369}
1370
1371#[derive(PartialEq, Debug)]
1372enum MatchResult<'a> {
1373    /// No match
1374    None,
1375    /// Matches only a part of the pattern before reaching the end of the string
1376    Partial,
1377    /// Matches the whole pattern (but maybe not the whole string)
1378    Consumed {
1379        /// Part of the string remaining after matching the whole pattern
1380        remaining: &'a str,
1381        /// Set when the pattern ends with a dynamic part. The dynamic part
1382        /// could match n bytes more of the string.
1383        any_offset: Option<usize>,
1384        /// Set when the pattern ends with `node_modules` or `node_modules/` (and a following
1385        /// Pattern::Dynamic would thus match all existing packages)
1386        in_node_modules: InNodeModules,
1387    },
1388}
1389
1390impl MatchResult<'_> {
1391    /// Returns true if the whole pattern matches the whole string
1392    fn is_match(&self) -> bool {
1393        match self {
1394            MatchResult::None => false,
1395            MatchResult::Partial => false,
1396            MatchResult::Consumed {
1397                remaining: rem,
1398                any_offset,
1399                in_node_modules: _,
1400            } => {
1401                if let Some(offset) = any_offset {
1402                    *offset == rem.len()
1403                } else {
1404                    rem.is_empty()
1405                }
1406            }
1407        }
1408    }
1409
1410    /// Returns true if (at least a part of) the pattern matches the whole
1411    /// string and can also match more bytes in the string
1412    fn could_match_others(&self) -> bool {
1413        match self {
1414            MatchResult::None => false,
1415            MatchResult::Partial => true,
1416            MatchResult::Consumed {
1417                remaining: rem,
1418                any_offset,
1419                in_node_modules: _,
1420            } => {
1421                if let Some(offset) = any_offset {
1422                    *offset == rem.len()
1423                } else {
1424                    false
1425                }
1426            }
1427        }
1428    }
1429
1430    /// Returns true if (at least a part of) the pattern matches the whole
1431    /// string
1432    fn could_match(&self) -> bool {
1433        match self {
1434            MatchResult::None => false,
1435            MatchResult::Partial => true,
1436            MatchResult::Consumed {
1437                remaining: rem,
1438                any_offset,
1439                in_node_modules: _,
1440            } => {
1441                if let Some(offset) = any_offset {
1442                    *offset == rem.len()
1443                } else {
1444                    rem.is_empty()
1445                }
1446            }
1447        }
1448    }
1449}
1450
1451#[derive(PartialEq, Debug)]
1452enum NextConstantUntilResult<'a, 'b> {
1453    NoMatch,
1454    PartialDynamic,
1455    Partial(&'a str, bool),
1456    Consumed(&'b str, Option<usize>),
1457}
1458
1459impl From<RcStr> for Pattern {
1460    fn from(s: RcStr) -> Self {
1461        Pattern::Constant(s)
1462    }
1463}
1464
1465impl Pattern {
1466    pub fn describe_as_string(&self) -> String {
1467        match self {
1468            Pattern::Constant(c) => format!("'{c}'"),
1469            Pattern::Dynamic => "<dynamic>".to_string(),
1470            Pattern::DynamicNoSlash => "<dynamic no slash>".to_string(),
1471            Pattern::Alternatives(list) => format!(
1472                "({})",
1473                list.iter()
1474                    .map(|i| i.describe_as_string())
1475                    .collect::<Vec<_>>()
1476                    .join(" | ")
1477            ),
1478            Pattern::Concatenation(list) => list
1479                .iter()
1480                .map(|i| i.describe_as_string())
1481                .collect::<Vec<_>>()
1482                .join(" "),
1483        }
1484    }
1485}
1486
1487#[derive(
1488    Debug, PartialEq, Eq, Clone, TraceRawVcs, ValueDebugFormat, NonLocalValue, Encode, Decode,
1489)]
1490pub enum PatternMatch {
1491    File(RcStr, FileSystemPath),
1492    Directory(RcStr, FileSystemPath),
1493}
1494
1495impl PatternMatch {
1496    pub fn path(&self) -> Vc<FileSystemPath> {
1497        match self {
1498            PatternMatch::File(_, path) | PatternMatch::Directory(_, path) => path.clone().cell(),
1499        }
1500    }
1501
1502    pub fn name(&self) -> &str {
1503        match self {
1504            PatternMatch::File(name, _) | PatternMatch::Directory(name, _) => name.as_str(),
1505        }
1506    }
1507}
1508
1509// TODO this isn't super efficient
1510// avoid storing a large list of matches
1511#[turbo_tasks::value(transparent)]
1512#[derive(Debug)]
1513pub struct PatternMatches(Vec<PatternMatch>);
1514
1515/// Find all files or directories that match the provided `pattern` with the
1516/// specified `lookup_dir` directory. `prefix` is the already matched part of
1517/// the pattern that leads to the `lookup_dir` directory. When
1518/// `force_in_lookup_dir` is set, leaving the `lookup_dir` directory by
1519/// matching `..` is not allowed.
1520///
1521/// Symlinks will not be resolved. It's expected that the caller resolves
1522/// symlinks when they are interested in that.
1523#[turbo_tasks::function]
1524pub async fn read_matches(
1525    lookup_dir: FileSystemPath,
1526    prefix: RcStr,
1527    force_in_lookup_dir: bool,
1528    pattern: Vc<Pattern>,
1529) -> Result<Vc<PatternMatches>> {
1530    let mut prefix = prefix.to_string();
1531    let pat = pattern.await?;
1532    let mut results = Vec::new();
1533    let mut nested = Vec::new();
1534    let slow_path = if let Some(constants) = pat.next_constants(&prefix) {
1535        if constants
1536            .iter()
1537            .all(|(str, until_end)| *until_end || str.contains('/'))
1538        {
1539            // Fast path: There is a finite list of possible strings that include at least
1540            // one path segment We will enumerate the list instead of the
1541            // directory
1542            let mut handled = FxHashSet::default();
1543            let mut read_dir_results = FxHashMap::default();
1544            for (index, (str, until_end)) in constants.into_iter().enumerate() {
1545                if until_end {
1546                    if !handled.insert(str) {
1547                        continue;
1548                    }
1549                    let (parent_path, last_segment) = split_last_segment(str);
1550                    if last_segment.is_empty() {
1551                        // This means we don't have a last segment, so we just have a directory
1552                        let joined = if force_in_lookup_dir {
1553                            lookup_dir.try_join_inside(parent_path)
1554                        } else {
1555                            lookup_dir.try_join(parent_path)
1556                        };
1557                        let Some(fs_path) = joined else {
1558                            continue;
1559                        };
1560                        results.push((
1561                            index,
1562                            PatternMatch::Directory(concat(&prefix, str).into(), fs_path),
1563                        ));
1564                        continue;
1565                    }
1566                    let entry = read_dir_results.entry(parent_path);
1567                    let read_dir = match entry {
1568                        Entry::Occupied(e) => Some(e.into_mut()),
1569                        Entry::Vacant(e) => {
1570                            let path_option = if force_in_lookup_dir {
1571                                lookup_dir.try_join_inside(parent_path)
1572                            } else {
1573                                lookup_dir.try_join(parent_path)
1574                            };
1575                            if let Some(path) = path_option {
1576                                Some(e.insert((path.raw_read_dir().await?, path)))
1577                            } else {
1578                                None
1579                            }
1580                        }
1581                    };
1582                    let Some((read_dir, parent_fs_path)) = read_dir else {
1583                        continue;
1584                    };
1585                    let RawDirectoryContent::Entries(entries) = &**read_dir else {
1586                        continue;
1587                    };
1588                    let Some(entry) = entries.get(last_segment) else {
1589                        continue;
1590                    };
1591                    match *entry {
1592                        RawDirectoryEntry::File => {
1593                            results.push((
1594                                index,
1595                                PatternMatch::File(
1596                                    concat(&prefix, str).into(),
1597                                    parent_fs_path.join(last_segment)?,
1598                                ),
1599                            ));
1600                        }
1601                        RawDirectoryEntry::Directory => results.push((
1602                            index,
1603                            PatternMatch::Directory(
1604                                concat(&prefix, str).into(),
1605                                parent_fs_path.join(last_segment)?,
1606                            ),
1607                        )),
1608                        RawDirectoryEntry::Symlink => {
1609                            let fs_path = parent_fs_path.join(last_segment)?;
1610                            let LinkContent::Link { link_type, .. } = &*fs_path.read_link().await?
1611                            else {
1612                                continue;
1613                            };
1614                            let path = concat(&prefix, str).into();
1615                            if link_type.contains(LinkType::DIRECTORY) {
1616                                results.push((index, PatternMatch::Directory(path, fs_path)));
1617                            } else {
1618                                results.push((index, PatternMatch::File(path, fs_path)))
1619                            }
1620                        }
1621                        _ => {}
1622                    }
1623                } else {
1624                    let subpath = &str[..=str.rfind('/').unwrap()];
1625                    if handled.insert(subpath) {
1626                        let joined = if force_in_lookup_dir {
1627                            lookup_dir.try_join_inside(subpath)
1628                        } else {
1629                            lookup_dir.try_join(subpath)
1630                        };
1631                        let Some(fs_path) = joined else {
1632                            continue;
1633                        };
1634                        nested.push((
1635                            0,
1636                            read_matches(
1637                                fs_path.clone(),
1638                                concat(&prefix, subpath).into(),
1639                                force_in_lookup_dir,
1640                                pattern,
1641                            ),
1642                        ));
1643                    }
1644                }
1645            }
1646            false
1647        } else {
1648            true
1649        }
1650    } else {
1651        true
1652    };
1653
1654    if slow_path {
1655        async {
1656            // Slow path: There are infinite matches for the pattern
1657            // We will enumerate the filesystem to find matches
1658            if !force_in_lookup_dir {
1659                // {prefix}..
1660                prefix.push_str("..");
1661                if let Some(pos) = pat.match_position(&prefix) {
1662                    results.push((
1663                        pos,
1664                        PatternMatch::Directory(prefix.clone().into(), lookup_dir.parent()),
1665                    ));
1666                }
1667
1668                // {prefix}../
1669                prefix.push('/');
1670                if let Some(pos) = pat.match_position(&prefix) {
1671                    results.push((
1672                        pos,
1673                        PatternMatch::Directory(prefix.clone().into(), lookup_dir.parent()),
1674                    ));
1675                }
1676                if let Some(pos) = pat.could_match_position(&prefix) {
1677                    nested.push((
1678                        pos,
1679                        read_matches(lookup_dir.parent(), prefix.clone().into(), false, pattern),
1680                    ));
1681                }
1682                prefix.pop();
1683                prefix.pop();
1684                prefix.pop();
1685            }
1686            {
1687                prefix.push('.');
1688                // {prefix}.
1689                if let Some(pos) = pat.match_position(&prefix) {
1690                    results.push((
1691                        pos,
1692                        PatternMatch::Directory(prefix.clone().into(), lookup_dir.clone()),
1693                    ));
1694                }
1695                prefix.pop();
1696            }
1697            if prefix.is_empty() {
1698                if let Some(pos) = pat.match_position("./") {
1699                    results.push((
1700                        pos,
1701                        PatternMatch::Directory(rcstr!("./"), lookup_dir.clone()),
1702                    ));
1703                }
1704                if let Some(pos) = pat.could_match_position("./") {
1705                    nested.push((
1706                        pos,
1707                        read_matches(lookup_dir.clone(), rcstr!("./"), false, pattern),
1708                    ));
1709                }
1710            } else {
1711                prefix.push('/');
1712                // {prefix}/
1713                if let Some(pos) = pat.could_match_position(&prefix) {
1714                    nested.push((
1715                        pos,
1716                        read_matches(
1717                            lookup_dir.clone(),
1718                            prefix.to_string().into(),
1719                            false,
1720                            pattern,
1721                        ),
1722                    ));
1723                }
1724                prefix.pop();
1725                prefix.push_str("./");
1726                // {prefix}./
1727                if let Some(pos) = pat.could_match_position(&prefix) {
1728                    nested.push((
1729                        pos,
1730                        read_matches(
1731                            lookup_dir.clone(),
1732                            prefix.to_string().into(),
1733                            false,
1734                            pattern,
1735                        ),
1736                    ));
1737                }
1738                prefix.pop();
1739                prefix.pop();
1740            }
1741            match &*lookup_dir.raw_read_dir().await? {
1742                RawDirectoryContent::Entries(map) => {
1743                    for (key, entry) in map.iter() {
1744                        match entry {
1745                            RawDirectoryEntry::File => {
1746                                let len = prefix.len();
1747                                prefix.push_str(key);
1748                                // {prefix}{key}
1749                                if let Some(pos) = pat.match_position(&prefix) {
1750                                    let path = lookup_dir.join(key)?;
1751                                    results.push((
1752                                        pos,
1753                                        PatternMatch::File(prefix.clone().into(), path),
1754                                    ));
1755                                }
1756                                prefix.truncate(len)
1757                            }
1758                            RawDirectoryEntry::Directory => {
1759                                let len = prefix.len();
1760                                prefix.push_str(key);
1761                                // {prefix}{key}
1762                                if prefix.ends_with('/') {
1763                                    prefix.pop();
1764                                }
1765                                if let Some(pos) = pat.match_position(&prefix) {
1766                                    let path = lookup_dir.join(key)?;
1767                                    results.push((
1768                                        pos,
1769                                        PatternMatch::Directory(prefix.clone().into(), path),
1770                                    ));
1771                                }
1772                                prefix.push('/');
1773                                // {prefix}{key}/
1774                                if let Some(pos) = pat.match_position(&prefix) {
1775                                    let path = lookup_dir.join(key)?;
1776                                    results.push((
1777                                        pos,
1778                                        PatternMatch::Directory(prefix.clone().into(), path),
1779                                    ));
1780                                }
1781                                if let Some(pos) = pat.could_match_position(&prefix) {
1782                                    let path = lookup_dir.join(key)?;
1783                                    nested.push((
1784                                        pos,
1785                                        read_matches(path, prefix.clone().into(), true, pattern),
1786                                    ));
1787                                }
1788                                prefix.truncate(len)
1789                            }
1790                            RawDirectoryEntry::Symlink => {
1791                                let len = prefix.len();
1792                                prefix.push_str(key);
1793                                // {prefix}{key}
1794                                if prefix.ends_with('/') {
1795                                    prefix.pop();
1796                                }
1797                                if let Some(pos) = pat.match_position(&prefix) {
1798                                    let fs_path = lookup_dir.join(key)?;
1799                                    if let LinkContent::Link { link_type, .. } =
1800                                        &*fs_path.read_link().await?
1801                                    {
1802                                        if link_type.contains(LinkType::DIRECTORY) {
1803                                            results.push((
1804                                                pos,
1805                                                PatternMatch::Directory(
1806                                                    prefix.clone().into(),
1807                                                    fs_path,
1808                                                ),
1809                                            ));
1810                                        } else {
1811                                            results.push((
1812                                                pos,
1813                                                PatternMatch::File(prefix.clone().into(), fs_path),
1814                                            ));
1815                                        }
1816                                    }
1817                                }
1818                                prefix.push('/');
1819                                if let Some(pos) = pat.match_position(&prefix) {
1820                                    let fs_path = lookup_dir.join(key)?;
1821                                    if let LinkContent::Link { link_type, .. } =
1822                                        &*fs_path.read_link().await?
1823                                        && link_type.contains(LinkType::DIRECTORY)
1824                                    {
1825                                        results.push((
1826                                            pos,
1827                                            PatternMatch::Directory(prefix.clone().into(), fs_path),
1828                                        ));
1829                                    }
1830                                }
1831                                if let Some(pos) = pat.could_match_position(&prefix) {
1832                                    let fs_path = lookup_dir.join(key)?;
1833                                    if let LinkContent::Link { link_type, .. } =
1834                                        &*fs_path.read_link().await?
1835                                        && link_type.contains(LinkType::DIRECTORY)
1836                                    {
1837                                        results.push((
1838                                            pos,
1839                                            PatternMatch::Directory(prefix.clone().into(), fs_path),
1840                                        ));
1841                                    }
1842                                }
1843                                prefix.truncate(len)
1844                            }
1845                            RawDirectoryEntry::Other => {}
1846                        }
1847                    }
1848                }
1849                RawDirectoryContent::NotFound => {}
1850            };
1851            anyhow::Ok(())
1852        }
1853        .instrument(tracing::trace_span!("read_matches slow_path"))
1854        .await?;
1855    }
1856    if results.is_empty() && nested.len() == 1 {
1857        Ok(nested.into_iter().next().unwrap().1)
1858    } else {
1859        for (pos, nested) in nested.into_iter() {
1860            results.extend(nested.await?.iter().cloned().map(|p| (pos, p)));
1861        }
1862        results.sort_by(|(a, am), (b, bm)| (*a).cmp(b).then_with(|| am.name().cmp(bm.name())));
1863        Ok(Vc::cell(
1864            results.into_iter().map(|(_, p)| p).collect::<Vec<_>>(),
1865        ))
1866    }
1867}
1868
1869fn concat(a: &str, b: &str) -> String {
1870    let mut result = String::with_capacity(a.len() + b.len());
1871    result.push_str(a);
1872    result.push_str(b);
1873    result
1874}
1875
1876/// Returns the parent folder and the last segment of the path. When the last segment is unknown (e.
1877/// g. when using `../`) it returns the full path and an empty string.
1878fn split_last_segment(path: &str) -> (&str, &str) {
1879    if let Some((remaining_path, last_segment)) = path.rsplit_once('/') {
1880        match last_segment {
1881            "" => split_last_segment(remaining_path),
1882            "." => split_last_segment(remaining_path),
1883            ".." => match split_last_segment(remaining_path) {
1884                (_, "") => (path, ""),
1885                (parent_path, _) => split_last_segment(parent_path),
1886            },
1887            _ => (remaining_path, last_segment),
1888        }
1889    } else {
1890        match path {
1891            "" => ("", ""),
1892            "." => ("", ""),
1893            ".." => ("..", ""),
1894            _ => ("", path),
1895        }
1896    }
1897}
1898
1899#[cfg(test)]
1900mod tests {
1901    use std::path::Path;
1902
1903    use rstest::*;
1904    use turbo_rcstr::{RcStr, rcstr};
1905    use turbo_tasks::Vc;
1906    use turbo_tasks_backend::{BackendOptions, TurboTasksBackend, noop_backing_storage};
1907    use turbo_tasks_fs::{DiskFileSystem, FileSystem};
1908
1909    use super::{
1910        Pattern, longest_common_prefix, longest_common_suffix, read_matches, split_last_segment,
1911    };
1912
1913    #[test]
1914    fn longest_common_prefix_test() {
1915        assert_eq!(longest_common_prefix(&["ab"]), "ab");
1916        assert_eq!(longest_common_prefix(&["ab", "cd", "ef"]), "");
1917        assert_eq!(longest_common_prefix(&["ab1", "ab23", "ab456"]), "ab");
1918        assert_eq!(longest_common_prefix(&["abc", "abc", "abc"]), "abc");
1919        assert_eq!(longest_common_prefix(&["abc", "a", "abc"]), "a");
1920    }
1921
1922    #[test]
1923    fn longest_common_suffix_test() {
1924        assert_eq!(longest_common_suffix(&["ab"]), "ab");
1925        assert_eq!(longest_common_suffix(&["ab", "cd", "ef"]), "");
1926        assert_eq!(longest_common_suffix(&["1ab", "23ab", "456ab"]), "ab");
1927        assert_eq!(longest_common_suffix(&["abc", "abc", "abc"]), "abc");
1928        assert_eq!(longest_common_suffix(&["abc", "c", "abc"]), "c");
1929    }
1930
1931    #[test]
1932    fn normalize() {
1933        let a = Pattern::Constant(rcstr!("a"));
1934        let b = Pattern::Constant(rcstr!("b"));
1935        let c = Pattern::Constant(rcstr!("c"));
1936        let s = Pattern::Constant(rcstr!("/"));
1937        let d = Pattern::Dynamic;
1938        {
1939            let mut p = Pattern::Concatenation(vec![
1940                Pattern::Alternatives(vec![a.clone(), b.clone()]),
1941                s.clone(),
1942                c.clone(),
1943            ]);
1944            p.normalize();
1945            assert_eq!(
1946                p,
1947                Pattern::Alternatives(vec![
1948                    Pattern::Constant(rcstr!("a/c")),
1949                    Pattern::Constant(rcstr!("b/c")),
1950                ])
1951            );
1952        }
1953
1954        #[allow(clippy::redundant_clone)] // alignment
1955        {
1956            let mut p = Pattern::Concatenation(vec![
1957                Pattern::Alternatives(vec![a.clone(), b.clone(), d.clone()]),
1958                s.clone(),
1959                Pattern::Alternatives(vec![b.clone(), c.clone(), d.clone()]),
1960            ]);
1961            p.normalize();
1962
1963            assert_eq!(
1964                p,
1965                Pattern::Alternatives(vec![
1966                    Pattern::Constant(rcstr!("a/b")),
1967                    Pattern::Constant(rcstr!("b/b")),
1968                    Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!("/b"))]),
1969                    Pattern::Constant(rcstr!("a/c")),
1970                    Pattern::Constant(rcstr!("b/c")),
1971                    Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!("/c"))]),
1972                    Pattern::Concatenation(vec![Pattern::Constant(rcstr!("a/")), Pattern::Dynamic]),
1973                    Pattern::Concatenation(vec![Pattern::Constant(rcstr!("b/")), Pattern::Dynamic]),
1974                    Pattern::Concatenation(vec![
1975                        Pattern::Dynamic,
1976                        Pattern::Constant(rcstr!("/")),
1977                        Pattern::Dynamic
1978                    ]),
1979                ])
1980            );
1981        }
1982
1983        #[allow(clippy::redundant_clone)] // alignment
1984        {
1985            let mut p = Pattern::Alternatives(vec![a.clone()]);
1986            p.normalize();
1987
1988            assert_eq!(p, a);
1989        }
1990
1991        #[allow(clippy::redundant_clone)] // alignment
1992        {
1993            let mut p = Pattern::Alternatives(vec![Pattern::Dynamic, Pattern::Dynamic]);
1994            p.normalize();
1995
1996            assert_eq!(p, Pattern::Dynamic);
1997        }
1998    }
1999
2000    #[test]
2001    fn with_normalized_path() {
2002        assert!(
2003            Pattern::Constant(rcstr!("a/../.."))
2004                .with_normalized_path()
2005                .is_none()
2006        );
2007        assert_eq!(
2008            Pattern::Constant(rcstr!("a/b/../c"))
2009                .with_normalized_path()
2010                .unwrap(),
2011            Pattern::Constant(rcstr!("a/c"))
2012        );
2013        assert_eq!(
2014            Pattern::Alternatives(vec![
2015                Pattern::Constant(rcstr!("a/b/../c")),
2016                Pattern::Constant(rcstr!("a/b/../c/d"))
2017            ])
2018            .with_normalized_path()
2019            .unwrap(),
2020            Pattern::Alternatives(vec![
2021                Pattern::Constant(rcstr!("a/c")),
2022                Pattern::Constant(rcstr!("a/c/d"))
2023            ])
2024        );
2025        assert_eq!(
2026            Pattern::Constant(rcstr!("a/b/"))
2027                .with_normalized_path()
2028                .unwrap(),
2029            Pattern::Constant(rcstr!("a/b"))
2030        );
2031
2032        // Dynamic is a segment itself
2033        assert_eq!(
2034            Pattern::Concatenation(vec![
2035                Pattern::Constant(rcstr!("a/b/")),
2036                Pattern::Dynamic,
2037                Pattern::Constant(rcstr!("../c"))
2038            ])
2039            .with_normalized_path()
2040            .unwrap(),
2041            Pattern::Concatenation(vec![
2042                Pattern::Constant(rcstr!("a/b/")),
2043                Pattern::Dynamic,
2044                Pattern::Constant(rcstr!("../c"))
2045            ])
2046        );
2047
2048        // Dynamic is part of a segment
2049        assert_eq!(
2050            Pattern::Concatenation(vec![
2051                Pattern::Constant(rcstr!("a/b")),
2052                Pattern::Dynamic,
2053                Pattern::Constant(rcstr!("../c"))
2054            ])
2055            .with_normalized_path()
2056            .unwrap(),
2057            Pattern::Concatenation(vec![
2058                Pattern::Constant(rcstr!("a/b")),
2059                Pattern::Dynamic,
2060                Pattern::Constant(rcstr!("../c"))
2061            ])
2062        );
2063        assert_eq!(
2064            Pattern::Concatenation(vec![
2065                Pattern::Constant(rcstr!("src/")),
2066                Pattern::Dynamic,
2067                Pattern::Constant(rcstr!(".js"))
2068            ])
2069            .with_normalized_path()
2070            .unwrap(),
2071            Pattern::Concatenation(vec![
2072                Pattern::Constant(rcstr!("src/")),
2073                Pattern::Dynamic,
2074                Pattern::Constant(rcstr!(".js"))
2075            ])
2076        );
2077    }
2078
2079    #[test]
2080    fn is_match() {
2081        let pat = Pattern::Concatenation(vec![
2082            Pattern::Constant(rcstr!(".")),
2083            Pattern::Constant(rcstr!("/")),
2084            Pattern::Dynamic,
2085            Pattern::Constant(rcstr!(".js")),
2086        ]);
2087        assert!(pat.could_match(""));
2088        assert!(pat.could_match("./"));
2089        assert!(!pat.is_match("./"));
2090        assert!(pat.is_match("./index.js"));
2091        assert!(!pat.is_match("./index"));
2092        assert!(pat.is_match("./foo/index.js"));
2093        assert!(pat.is_match("./foo/bar/index.js"));
2094
2095        // forbidden:
2096        assert!(!pat.is_match("./../index.js"));
2097        assert!(!pat.is_match("././index.js"));
2098        assert!(!pat.is_match("./.git/index.js"));
2099        assert!(!pat.is_match("./inner/../index.js"));
2100        assert!(!pat.is_match("./inner/./index.js"));
2101        assert!(!pat.is_match("./inner/.git/index.js"));
2102        assert!(!pat.could_match("./../"));
2103        assert!(!pat.could_match("././"));
2104        assert!(!pat.could_match("./.git/"));
2105        assert!(!pat.could_match("./inner/../"));
2106        assert!(!pat.could_match("./inner/./"));
2107        assert!(!pat.could_match("./inner/.git/"));
2108    }
2109
2110    #[test]
2111    fn is_match_dynamic_no_slash() {
2112        let pat = Pattern::Concatenation(vec![
2113            Pattern::Constant(rcstr!(".")),
2114            Pattern::Constant(rcstr!("/")),
2115            Pattern::DynamicNoSlash,
2116            Pattern::Constant(rcstr!(".js")),
2117        ]);
2118        assert!(pat.could_match(""));
2119        assert!(pat.could_match("./"));
2120        assert!(!pat.is_match("./"));
2121        assert!(pat.is_match("./index.js"));
2122        assert!(!pat.is_match("./index"));
2123        assert!(!pat.is_match("./foo/index.js"));
2124        assert!(!pat.is_match("./foo/bar/index.js"));
2125    }
2126
2127    #[test]
2128    fn constant_prefix() {
2129        assert_eq!(
2130            Pattern::Constant(rcstr!("a/b/c.js")).constant_prefix(),
2131            "a/b/c.js",
2132        );
2133
2134        let pat = Pattern::Alternatives(vec![
2135            Pattern::Constant(rcstr!("a/b/x")),
2136            Pattern::Constant(rcstr!("a/b/y")),
2137            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("a/b/c/")), Pattern::Dynamic]),
2138        ]);
2139        assert_eq!(pat.constant_prefix(), "a/b/");
2140    }
2141
2142    #[test]
2143    fn constant_suffix() {
2144        assert_eq!(
2145            Pattern::Constant(rcstr!("a/b/c.js")).constant_suffix(),
2146            "a/b/c.js",
2147        );
2148
2149        let pat = Pattern::Alternatives(vec![
2150            Pattern::Constant(rcstr!("a/b/x.js")),
2151            Pattern::Constant(rcstr!("a/b/y.js")),
2152            Pattern::Concatenation(vec![
2153                Pattern::Constant(rcstr!("a/b/c/")),
2154                Pattern::Dynamic,
2155                Pattern::Constant(rcstr!(".js")),
2156            ]),
2157        ]);
2158        assert_eq!(pat.constant_suffix(), ".js");
2159    }
2160
2161    #[test]
2162    fn strip_prefix() {
2163        fn strip(mut pat: Pattern, n: usize) -> Pattern {
2164            pat.strip_prefix_len(n).unwrap();
2165            pat
2166        }
2167
2168        assert_eq!(
2169            strip(Pattern::Constant(rcstr!("a/b")), 0),
2170            Pattern::Constant(rcstr!("a/b"))
2171        );
2172
2173        assert_eq!(
2174            strip(
2175                Pattern::Alternatives(vec![
2176                    Pattern::Constant(rcstr!("a/b/x")),
2177                    Pattern::Constant(rcstr!("a/b/y")),
2178                ]),
2179                2
2180            ),
2181            Pattern::Alternatives(vec![
2182                Pattern::Constant(rcstr!("b/x")),
2183                Pattern::Constant(rcstr!("b/y")),
2184            ])
2185        );
2186
2187        assert_eq!(
2188            strip(
2189                Pattern::Concatenation(vec![
2190                    Pattern::Constant(rcstr!("a/")),
2191                    Pattern::Constant(rcstr!("b")),
2192                    Pattern::Constant(rcstr!("/")),
2193                    Pattern::Constant(rcstr!("y/")),
2194                    Pattern::Dynamic
2195                ]),
2196                4
2197            ),
2198            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("y/")), Pattern::Dynamic]),
2199        );
2200    }
2201
2202    #[test]
2203    fn strip_suffix() {
2204        fn strip(mut pat: Pattern, n: usize) -> Pattern {
2205            pat.strip_suffix_len(n);
2206            pat
2207        }
2208
2209        assert_eq!(
2210            strip(Pattern::Constant(rcstr!("a/b")), 0),
2211            Pattern::Constant(rcstr!("a/b"))
2212        );
2213
2214        assert_eq!(
2215            strip(
2216                Pattern::Alternatives(vec![
2217                    Pattern::Constant(rcstr!("x/b/a")),
2218                    Pattern::Constant(rcstr!("y/b/a")),
2219                ]),
2220                2
2221            ),
2222            Pattern::Alternatives(vec![
2223                Pattern::Constant(rcstr!("x/b")),
2224                Pattern::Constant(rcstr!("y/b")),
2225            ])
2226        );
2227
2228        assert_eq!(
2229            strip(
2230                Pattern::Concatenation(vec![
2231                    Pattern::Dynamic,
2232                    Pattern::Constant(rcstr!("/a/")),
2233                    Pattern::Constant(rcstr!("b")),
2234                    Pattern::Constant(rcstr!("/")),
2235                    Pattern::Constant(rcstr!("y/")),
2236                ]),
2237                4
2238            ),
2239            Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!("/a/")),]),
2240        );
2241    }
2242
2243    #[test]
2244    fn spread_into_star() {
2245        let pat = Pattern::Constant(rcstr!("xyz"));
2246        assert_eq!(
2247            pat.spread_into_star("before/after"),
2248            Pattern::Constant(rcstr!("before/after")),
2249        );
2250
2251        let pat =
2252            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("a/b/c/")), Pattern::Dynamic]);
2253        assert_eq!(
2254            pat.spread_into_star("before/*/after"),
2255            Pattern::Concatenation(vec![
2256                Pattern::Constant(rcstr!("before/a/b/c/")),
2257                Pattern::Dynamic,
2258                Pattern::Constant(rcstr!("/after"))
2259            ])
2260        );
2261
2262        let pat = Pattern::Alternatives(vec![
2263            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("a/")), Pattern::Dynamic]),
2264            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("b/")), Pattern::Dynamic]),
2265        ]);
2266        assert_eq!(
2267            pat.spread_into_star("before/*/after"),
2268            Pattern::Alternatives(vec![
2269                Pattern::Concatenation(vec![
2270                    Pattern::Constant(rcstr!("before/a/")),
2271                    Pattern::Dynamic,
2272                    Pattern::Constant(rcstr!("/after"))
2273                ]),
2274                Pattern::Concatenation(vec![
2275                    Pattern::Constant(rcstr!("before/b/")),
2276                    Pattern::Dynamic,
2277                    Pattern::Constant(rcstr!("/after"))
2278                ]),
2279            ])
2280        );
2281
2282        let pat = Pattern::Alternatives(vec![
2283            Pattern::Constant(rcstr!("a")),
2284            Pattern::Constant(rcstr!("b")),
2285        ]);
2286        assert_eq!(
2287            pat.spread_into_star("before/*/*"),
2288            Pattern::Alternatives(vec![
2289                Pattern::Constant(rcstr!("before/a/a")),
2290                Pattern::Constant(rcstr!("before/b/b")),
2291            ])
2292        );
2293
2294        let pat = Pattern::Dynamic;
2295        assert_eq!(
2296            pat.spread_into_star("before/*/*"),
2297            Pattern::Concatenation(vec![
2298                // TODO currently nothing ensures that both Dynamic parts are equal
2299                Pattern::Constant(rcstr!("before/")),
2300                Pattern::Dynamic,
2301                Pattern::Constant(rcstr!("/")),
2302                Pattern::Dynamic
2303            ])
2304        );
2305    }
2306
2307    #[rstest]
2308    #[case::dynamic(Pattern::Dynamic)]
2309    #[case::dynamic_concat(Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!(".js"))]))]
2310    fn dynamic_match(#[case] pat: Pattern) {
2311        assert!(pat.could_match(""));
2312        assert!(pat.is_match("index.js"));
2313
2314        // forbidden:
2315        assert!(!pat.could_match("./"));
2316        assert!(!pat.is_match("./"));
2317        assert!(!pat.could_match("."));
2318        assert!(!pat.is_match("."));
2319        assert!(!pat.could_match("../"));
2320        assert!(!pat.is_match("../"));
2321        assert!(!pat.could_match(".."));
2322        assert!(!pat.is_match(".."));
2323        assert!(!pat.is_match("./../index.js"));
2324        assert!(!pat.is_match("././index.js"));
2325        assert!(!pat.is_match("./.git/index.js"));
2326        assert!(!pat.is_match("./inner/../index.js"));
2327        assert!(!pat.is_match("./inner/./index.js"));
2328        assert!(!pat.is_match("./inner/.git/index.js"));
2329        assert!(!pat.could_match("./../"));
2330        assert!(!pat.could_match("././"));
2331        assert!(!pat.could_match("./.git/"));
2332        assert!(!pat.could_match("./inner/../"));
2333        assert!(!pat.could_match("./inner/./"));
2334        assert!(!pat.could_match("./inner/.git/"));
2335        assert!(!pat.could_match("dir//"));
2336        assert!(!pat.could_match("dir//dir"));
2337        assert!(!pat.could_match("dir///dir"));
2338        assert!(!pat.could_match("/"));
2339        assert!(!pat.could_match("//"));
2340        assert!(!pat.could_match("/ROOT/"));
2341
2342        assert!(!pat.could_match("node_modules"));
2343        assert!(!pat.could_match("node_modules/package"));
2344        assert!(!pat.could_match("nested/node_modules"));
2345        assert!(!pat.could_match("nested/node_modules/package"));
2346
2347        // forbidden match
2348        assert!(pat.could_match("file.map"));
2349        assert!(!pat.is_match("file.map"));
2350        assert!(pat.is_match("file.map/file.js"));
2351        assert!(!pat.is_match("file.d.ts"));
2352        assert!(!pat.is_match("file.d.ts.map"));
2353        assert!(!pat.is_match("file.d.ts.map"));
2354        assert!(!pat.is_match("dir/file.d.ts.map"));
2355        assert!(!pat.is_match("dir/inner/file.d.ts.map"));
2356        assert!(pat.could_match("dir/inner/file.d.ts.map"));
2357    }
2358
2359    #[rstest]
2360    #[case::slash(Pattern::Concatenation(vec![Pattern::Constant(rcstr!("node_modules/")),Pattern::Dynamic]))]
2361    #[case::nested(Pattern::Constant(rcstr!("node_modules")).or_any_nested_file())]
2362    fn dynamic_match_node_modules(#[case] pat: Pattern) {
2363        assert!(!pat.is_match("node_modules/package"));
2364        assert!(!pat.could_match("node_modules/package"));
2365        assert!(!pat.is_match("node_modules/package/index.js"));
2366        assert!(!pat.could_match("node_modules/package/index.js"));
2367    }
2368
2369    #[rstest]
2370    fn dynamic_match2() {
2371        let pat = Pattern::Concatenation(vec![
2372            Pattern::Dynamic,
2373            Pattern::Constant(rcstr!("/")),
2374            Pattern::Dynamic,
2375        ]);
2376        assert!(pat.could_match("dir"));
2377        assert!(pat.could_match("dir/"));
2378        assert!(pat.is_match("dir/index.js"));
2379
2380        // forbidden:
2381        assert!(!pat.could_match("./"));
2382        assert!(!pat.is_match("./"));
2383        assert!(!pat.could_match("."));
2384        assert!(!pat.is_match("."));
2385        assert!(!pat.could_match("../"));
2386        assert!(!pat.is_match("../"));
2387        assert!(!pat.could_match(".."));
2388        assert!(!pat.is_match(".."));
2389        assert!(!pat.is_match("./../index.js"));
2390        assert!(!pat.is_match("././index.js"));
2391        assert!(!pat.is_match("./.git/index.js"));
2392        assert!(!pat.is_match("./inner/../index.js"));
2393        assert!(!pat.is_match("./inner/./index.js"));
2394        assert!(!pat.is_match("./inner/.git/index.js"));
2395        assert!(!pat.could_match("./../"));
2396        assert!(!pat.could_match("././"));
2397        assert!(!pat.could_match("./.git/"));
2398        assert!(!pat.could_match("./inner/../"));
2399        assert!(!pat.could_match("./inner/./"));
2400        assert!(!pat.could_match("./inner/.git/"));
2401        assert!(!pat.could_match("dir//"));
2402        assert!(!pat.could_match("dir//dir"));
2403        assert!(!pat.could_match("dir///dir"));
2404        assert!(!pat.could_match("/ROOT/"));
2405
2406        assert!(!pat.could_match("node_modules"));
2407        assert!(!pat.could_match("node_modules/package"));
2408        assert!(!pat.could_match("nested/node_modules"));
2409        assert!(!pat.could_match("nested/node_modules/package"));
2410
2411        // forbidden match
2412        assert!(pat.could_match("dir/file.map"));
2413        assert!(!pat.is_match("dir/file.map"));
2414        assert!(pat.is_match("file.map/file.js"));
2415        assert!(!pat.is_match("dir/file.d.ts"));
2416        assert!(!pat.is_match("dir/file.d.ts.map"));
2417        assert!(!pat.is_match("dir/file.d.ts.map"));
2418        assert!(!pat.is_match("dir/file.d.ts.map"));
2419        assert!(!pat.is_match("dir/inner/file.d.ts.map"));
2420        assert!(pat.could_match("dir/inner/file.d.ts.map"));
2421    }
2422
2423    #[rstest]
2424    #[case::dynamic(Pattern::Dynamic)]
2425    #[case::dynamic_concat(Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!(".js"))]))]
2426    #[case::dynamic_concat2(Pattern::Concatenation(vec![
2427        Pattern::Dynamic,
2428        Pattern::Constant(rcstr!("/")),
2429        Pattern::Dynamic,
2430    ]))]
2431    #[case::dynamic_alt_concat(Pattern::alternatives(vec![
2432        Pattern::Concatenation(vec![
2433            Pattern::Dynamic,
2434            Pattern::Constant(rcstr!("/")),
2435            Pattern::Dynamic,
2436        ]),
2437        Pattern::Dynamic,
2438    ]))]
2439    fn split_could_match(#[case] pat: Pattern) {
2440        let (abs, rel) = pat.split_could_match("/ROOT/");
2441        assert!(abs.is_none());
2442        assert!(rel.is_some());
2443    }
2444
2445    #[rstest]
2446    #[case::dynamic(Pattern::Dynamic, "feijf", None)]
2447    #[case::dynamic_concat(
2448        Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!(".js"))]),
2449        "hello.", None
2450    )]
2451    #[case::constant(Pattern::Constant(rcstr!("Hello World")), "Hello ", Some(vec![("World", true)]))]
2452    #[case::alternatives(
2453        Pattern::Alternatives(vec![
2454            Pattern::Constant(rcstr!("Hello World")),
2455            Pattern::Constant(rcstr!("Hello All"))
2456        ]), "Hello ", Some(vec![("World", true), ("All", true)])
2457    )]
2458    #[case::alternatives_non_end(
2459        Pattern::Alternatives(vec![
2460            Pattern::Constant(rcstr!("Hello World")),
2461            Pattern::Constant(rcstr!("Hello All")),
2462            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("Hello more")), Pattern::Dynamic])
2463        ]), "Hello ", Some(vec![("World", true), ("All", true), ("more", false)])
2464    )]
2465    #[case::request_with_extensions(
2466        Pattern::Alternatives(vec![
2467            Pattern::Constant(rcstr!("./file.js")),
2468            Pattern::Constant(rcstr!("./file.ts")),
2469            Pattern::Constant(rcstr!("./file.cjs")),
2470        ]), "./", Some(vec![("file.js", true), ("file.ts", true), ("file.cjs", true)])
2471    )]
2472    fn next_constants(
2473        #[case] pat: Pattern,
2474        #[case] value: &str,
2475        #[case] expected: Option<Vec<(&str, bool)>>,
2476    ) {
2477        assert_eq!(pat.next_constants(value), expected);
2478    }
2479
2480    #[test]
2481    fn replace_final_constants() {
2482        fn f(mut p: Pattern, cb: &mut impl FnMut(&RcStr) -> Option<Pattern>) -> Pattern {
2483            p.replace_final_constants(cb);
2484            p
2485        }
2486
2487        let mut js_to_ts_tsx = |c: &RcStr| -> Option<Pattern> {
2488            c.strip_suffix(".js").map(|rest| {
2489                let new_ending = Pattern::Alternatives(vec![
2490                    Pattern::Constant(rcstr!(".ts")),
2491                    Pattern::Constant(rcstr!(".tsx")),
2492                    Pattern::Constant(rcstr!(".js")),
2493                ]);
2494                if !rest.is_empty() {
2495                    Pattern::Concatenation(vec![Pattern::Constant(rest.into()), new_ending])
2496                } else {
2497                    new_ending
2498                }
2499            })
2500        };
2501
2502        assert_eq!(
2503            f(
2504                Pattern::Concatenation(vec![
2505                    Pattern::Constant(rcstr!(".")),
2506                    Pattern::Constant(rcstr!("/")),
2507                    Pattern::Dynamic,
2508                    Pattern::Alternatives(vec![
2509                        Pattern::Constant(rcstr!(".js")),
2510                        Pattern::Constant(rcstr!(".node")),
2511                    ])
2512                ]),
2513                &mut js_to_ts_tsx
2514            ),
2515            Pattern::Concatenation(vec![
2516                Pattern::Constant(rcstr!(".")),
2517                Pattern::Constant(rcstr!("/")),
2518                Pattern::Dynamic,
2519                Pattern::Alternatives(vec![
2520                    Pattern::Alternatives(vec![
2521                        Pattern::Constant(rcstr!(".ts")),
2522                        Pattern::Constant(rcstr!(".tsx")),
2523                        Pattern::Constant(rcstr!(".js")),
2524                    ]),
2525                    Pattern::Constant(rcstr!(".node")),
2526                ])
2527            ]),
2528        );
2529        assert_eq!(
2530            f(
2531                Pattern::Concatenation(vec![
2532                    Pattern::Constant(rcstr!(".")),
2533                    Pattern::Constant(rcstr!("/")),
2534                    Pattern::Constant(rcstr!("abc.js")),
2535                ]),
2536                &mut js_to_ts_tsx
2537            ),
2538            Pattern::Concatenation(vec![
2539                Pattern::Constant(rcstr!(".")),
2540                Pattern::Constant(rcstr!("/")),
2541                Pattern::Concatenation(vec![
2542                    Pattern::Constant(rcstr!("abc")),
2543                    Pattern::Alternatives(vec![
2544                        Pattern::Constant(rcstr!(".ts")),
2545                        Pattern::Constant(rcstr!(".tsx")),
2546                        Pattern::Constant(rcstr!(".js")),
2547                    ])
2548                ]),
2549            ])
2550        );
2551    }
2552
2553    #[test]
2554    fn match_apply_template() {
2555        assert_eq!(
2556            Pattern::Concatenation(vec![
2557                Pattern::Constant(rcstr!("a/b/")),
2558                Pattern::Dynamic,
2559                Pattern::Constant(rcstr!(".ts")),
2560            ])
2561            .match_apply_template(
2562                "a/b/foo.ts",
2563                &Pattern::Concatenation(vec![
2564                    Pattern::Constant(rcstr!("@/a/b/")),
2565                    Pattern::Dynamic,
2566                    Pattern::Constant(rcstr!(".js")),
2567                ])
2568            )
2569            .as_deref(),
2570            Some("@/a/b/foo.js")
2571        );
2572        assert_eq!(
2573            Pattern::Concatenation(vec![
2574                Pattern::Constant(rcstr!("b/")),
2575                Pattern::Dynamic,
2576                Pattern::Constant(rcstr!(".ts")),
2577            ])
2578            .match_apply_template(
2579                "a/b/foo.ts",
2580                &Pattern::Concatenation(vec![
2581                    Pattern::Constant(rcstr!("@/a/b/")),
2582                    Pattern::Dynamic,
2583                    Pattern::Constant(rcstr!(".js")),
2584                ])
2585            )
2586            .as_deref(),
2587            None,
2588        );
2589        assert_eq!(
2590            Pattern::Concatenation(vec![
2591                Pattern::Constant(rcstr!("a/b/")),
2592                Pattern::Dynamic,
2593                Pattern::Constant(rcstr!(".ts")),
2594            ])
2595            .match_apply_template(
2596                "a/b/foo.ts",
2597                &Pattern::Concatenation(vec![
2598                    Pattern::Constant(rcstr!("@/a/b/x")),
2599                    Pattern::Constant(rcstr!(".js")),
2600                ])
2601            )
2602            .as_deref(),
2603            None,
2604        );
2605        assert_eq!(
2606            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("./sub/")), Pattern::Dynamic])
2607                .match_apply_template(
2608                    "./sub/file1",
2609                    &Pattern::Concatenation(vec![
2610                        Pattern::Constant(rcstr!("@/sub/")),
2611                        Pattern::Dynamic
2612                    ])
2613                )
2614                .as_deref(),
2615            Some("@/sub/file1"),
2616        );
2617    }
2618
2619    #[test]
2620    fn test_split_last_segment() {
2621        assert_eq!(split_last_segment(""), ("", ""));
2622        assert_eq!(split_last_segment("a"), ("", "a"));
2623        assert_eq!(split_last_segment("a/"), ("", "a"));
2624        assert_eq!(split_last_segment("a/b"), ("a", "b"));
2625        assert_eq!(split_last_segment("a/b/"), ("a", "b"));
2626        assert_eq!(split_last_segment("a/b/c"), ("a/b", "c"));
2627        assert_eq!(split_last_segment("a/b/."), ("a", "b"));
2628        assert_eq!(split_last_segment("a/b/.."), ("", "a"));
2629        assert_eq!(split_last_segment("a/b/c/.."), ("a", "b"));
2630        assert_eq!(split_last_segment("a/b/c/../.."), ("", "a"));
2631        assert_eq!(split_last_segment("a/b/c/d/../.."), ("a", "b"));
2632        assert_eq!(split_last_segment("a/b/c/../d/.."), ("a", "b"));
2633        assert_eq!(split_last_segment("a/b/../c/d/.."), ("a/b/..", "c"));
2634        assert_eq!(split_last_segment("."), ("", ""));
2635        assert_eq!(split_last_segment("./"), ("", ""));
2636        assert_eq!(split_last_segment(".."), ("..", ""));
2637        assert_eq!(split_last_segment("../"), ("..", ""));
2638        assert_eq!(split_last_segment("./../"), ("./..", ""));
2639        assert_eq!(split_last_segment("../../"), ("../..", ""));
2640        assert_eq!(split_last_segment("../../."), ("../..", ""));
2641        assert_eq!(split_last_segment("../.././"), ("../..", ""));
2642        assert_eq!(split_last_segment("a/.."), ("", ""));
2643        assert_eq!(split_last_segment("a/../"), ("", ""));
2644        assert_eq!(split_last_segment("a/../.."), ("a/../..", ""));
2645        assert_eq!(split_last_segment("a/../../"), ("a/../..", ""));
2646        assert_eq!(split_last_segment("a/././../"), ("", ""));
2647        assert_eq!(split_last_segment("../a"), ("..", "a"));
2648        assert_eq!(split_last_segment("../a/"), ("..", "a"));
2649        assert_eq!(split_last_segment("../../a"), ("../..", "a"));
2650        assert_eq!(split_last_segment("../../a/"), ("../..", "a"));
2651    }
2652
2653    #[tokio::test(flavor = "multi_thread", worker_threads = 2)]
2654    async fn test_read_matches() {
2655        let tt = turbo_tasks::TurboTasks::new(TurboTasksBackend::new(
2656            BackendOptions::default(),
2657            noop_backing_storage(),
2658        ));
2659        tt.run_once(async {
2660            #[turbo_tasks::value]
2661            struct ReadMatchesOutput {
2662                dynamic: Vec<String>,
2663                dynamic_file_suffix: Vec<String>,
2664                node_modules_dynamic: Vec<String>,
2665            }
2666
2667            #[turbo_tasks::function(operation)]
2668            async fn read_matches_operation() -> anyhow::Result<Vc<ReadMatchesOutput>> {
2669                let root = DiskFileSystem::new(
2670                    rcstr!("test"),
2671                    Path::new(env!("CARGO_MANIFEST_DIR"))
2672                        .join("tests/pattern/read_matches")
2673                        .to_str()
2674                        .unwrap()
2675                        .into(),
2676                )
2677                .root()
2678                .owned()
2679                .await?;
2680
2681                let dynamic = read_matches(
2682                    root.clone(),
2683                    rcstr!(""),
2684                    false,
2685                    Pattern::new(Pattern::Dynamic),
2686                )
2687                .await?
2688                .into_iter()
2689                .map(|m| m.name().to_string())
2690                .collect::<Vec<_>>();
2691
2692                let dynamic_file_suffix = read_matches(
2693                    root.clone(),
2694                    rcstr!(""),
2695                    false,
2696                    Pattern::new(Pattern::concat([
2697                        Pattern::Constant(rcstr!("sub/foo")),
2698                        Pattern::Dynamic,
2699                    ])),
2700                )
2701                .await?
2702                .into_iter()
2703                .map(|m| m.name().to_string())
2704                .collect::<Vec<_>>();
2705
2706                let node_modules_dynamic = read_matches(
2707                    root,
2708                    rcstr!(""),
2709                    false,
2710                    Pattern::new(Pattern::Constant(rcstr!("node_modules")).or_any_nested_file()),
2711                )
2712                .await?
2713                .into_iter()
2714                .map(|m| m.name().to_string())
2715                .collect::<Vec<_>>();
2716
2717                Ok(ReadMatchesOutput {
2718                    dynamic,
2719                    dynamic_file_suffix,
2720                    node_modules_dynamic,
2721                }
2722                .cell())
2723            }
2724
2725            let matches = read_matches_operation().read_strongly_consistent().await?;
2726
2727            // node_modules shouldn't be matched by Dynamic here
2728            assert_eq!(
2729                matches.dynamic,
2730                &["index.js", "sub", "sub/", "sub/foo-a.js", "sub/foo-b.js"]
2731            );
2732
2733            // basic dynamic file suffix
2734            assert_eq!(
2735                matches.dynamic_file_suffix,
2736                &["sub/foo-a.js", "sub/foo-b.js"]
2737            );
2738
2739            // read_matches "node_modules/<dynamic>" should not return anything inside. We never
2740            // want to enumerate the list of packages here.
2741            assert_eq!(matches.node_modules_dynamic, &["node_modules"]);
2742
2743            Ok(())
2744        })
2745        .await
2746        .unwrap();
2747    }
2748}
turbopack_core/resolve/pattern.rs

turbopack_core/resolve/
pattern.rs
