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, ReadRef, TaskInput, ValueToString, Vc, debug::ValueDebugFormat,
15    trace::TraceRawVcs,
16};
17use turbo_tasks_fs::{
18    FileSystemEntryType, FileSystemPath, LinkContent, RawDirectoryContent, RawDirectoryEntry,
19};
20use turbo_unix_path::normalize_path;
21
22#[turbo_tasks::value]
23#[derive(Hash, Clone, Debug, Default, ValueToString)]
24#[value_to_string(self.describe_as_string())]
25pub enum Pattern {
26    Constant(RcStr),
27    #[default]
28    Dynamic,
29    DynamicNoSlash,
30    Alternatives(Vec<Pattern>),
31    Concatenation(Vec<Pattern>),
32}
33
34// Use a manual impl since llvm cannot prove the default generated recursive impl always returns
35// false from `is_transient`
36impl TaskInput for Pattern {
37    fn is_transient(&self) -> bool {
38        // contains no vcs
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/// Reads the directory `path` points at, enumerating it through its realpath.
1516///
1517/// Callers keep the original logical `path` when constructing [`PatternMatch`] values, so symlinks
1518/// stay visible in the results while the directory itself is never read through a symlinked
1519/// parent. Resolving also registers a dependency on the symlink chain, so replacing a link
1520/// invalidates the enumeration.
1521///
1522/// A path that cannot be resolved (a dangling or cyclic link) is read as-is, which yields
1523/// [`RawDirectoryContent::NotFound`] just as it did before.
1524async fn raw_read_dir_resolved(path: &FileSystemPath) -> Result<ReadRef<RawDirectoryContent>> {
1525    let resolved = path.realpath().await?.unwrap_or_else(|_| path.clone());
1526    resolved.raw_read_dir().await
1527}
1528
1529/// Find all files or directories that match the provided `pattern` with the
1530/// specified `lookup_dir` directory. `prefix` is the already matched part of
1531/// the pattern that leads to the `lookup_dir` directory. When
1532/// `force_in_lookup_dir` is set, leaving the `lookup_dir` directory by
1533/// matching `..` is not allowed.
1534///
1535/// Symlinks in returned matches are not resolved. Lookup directories are resolved only for
1536/// physical enumeration; logical paths are retained in [`PatternMatch`] values so callers can
1537/// resolve and track the symlinks they are interested in.
1538#[turbo_tasks::function]
1539pub async fn read_matches(
1540    lookup_dir: FileSystemPath,
1541    prefix: RcStr,
1542    force_in_lookup_dir: bool,
1543    pattern: Vc<Pattern>,
1544) -> Result<Vc<PatternMatches>> {
1545    let mut prefix = prefix.to_string();
1546    let pat = pattern.await?;
1547    let mut results = Vec::new();
1548    let mut nested = Vec::new();
1549    let slow_path = if let Some(constants) = pat.next_constants(&prefix) {
1550        if constants
1551            .iter()
1552            .all(|(str, until_end)| *until_end || str.contains('/'))
1553        {
1554            // Fast path: There is a finite list of possible strings that include at least
1555            // one path segment We will enumerate the list instead of the
1556            // directory
1557            let mut handled = FxHashSet::default();
1558            let mut read_dir_results = FxHashMap::default();
1559            for (index, (str, until_end)) in constants.into_iter().enumerate() {
1560                if until_end {
1561                    if !handled.insert(str) {
1562                        continue;
1563                    }
1564                    let (parent_path, last_segment) = split_last_segment(str);
1565                    if last_segment.is_empty() {
1566                        // This means we don't have a last segment, so we just have a directory
1567                        let joined = if force_in_lookup_dir {
1568                            lookup_dir.try_join_inside(parent_path)
1569                        } else {
1570                            lookup_dir.try_join(parent_path)
1571                        };
1572                        let Some(fs_path) = joined else {
1573                            continue;
1574                        };
1575                        results.push((
1576                            index,
1577                            PatternMatch::Directory(concat(&prefix, str).into(), fs_path),
1578                        ));
1579                        continue;
1580                    }
1581                    let entry = read_dir_results.entry(parent_path);
1582                    let read_dir = match entry {
1583                        Entry::Occupied(e) => Some(e.into_mut()),
1584                        Entry::Vacant(e) => {
1585                            let path_option = if force_in_lookup_dir {
1586                                lookup_dir.try_join_inside(parent_path)
1587                            } else {
1588                                lookup_dir.try_join(parent_path)
1589                            };
1590                            if let Some(path) = path_option {
1591                                Some(e.insert((raw_read_dir_resolved(&path).await?, path)))
1592                            } else {
1593                                None
1594                            }
1595                        }
1596                    };
1597                    let Some((read_dir, parent_fs_path)) = read_dir else {
1598                        continue;
1599                    };
1600                    let RawDirectoryContent::Entries(entries) = &**read_dir else {
1601                        continue;
1602                    };
1603                    let Some(entry) = entries.get(last_segment) else {
1604                        continue;
1605                    };
1606                    match *entry {
1607                        RawDirectoryEntry::File => {
1608                            results.push((
1609                                index,
1610                                PatternMatch::File(
1611                                    concat(&prefix, str).into(),
1612                                    parent_fs_path.join(last_segment)?,
1613                                ),
1614                            ));
1615                        }
1616                        RawDirectoryEntry::Directory => results.push((
1617                            index,
1618                            PatternMatch::Directory(
1619                                concat(&prefix, str).into(),
1620                                parent_fs_path.join(last_segment)?,
1621                            ),
1622                        )),
1623                        RawDirectoryEntry::Symlink => {
1624                            let fs_path = parent_fs_path.join(last_segment)?;
1625                            let LinkContent::Link { target } = &*fs_path.read_link().await? else {
1626                                continue;
1627                            };
1628                            let path = concat(&prefix, str).into();
1629                            if matches!(
1630                                target.resolved_type().await?,
1631                                FileSystemEntryType::Directory
1632                            ) {
1633                                results.push((index, PatternMatch::Directory(path, fs_path)));
1634                            } else {
1635                                results.push((index, PatternMatch::File(path, fs_path)))
1636                            }
1637                        }
1638                        _ => {}
1639                    }
1640                } else {
1641                    let subpath = &str[..=str.rfind('/').unwrap()];
1642                    if handled.insert(subpath) {
1643                        let joined = if force_in_lookup_dir {
1644                            lookup_dir.try_join_inside(subpath)
1645                        } else {
1646                            lookup_dir.try_join(subpath)
1647                        };
1648                        let Some(fs_path) = joined else {
1649                            continue;
1650                        };
1651                        nested.push((
1652                            index,
1653                            read_matches(
1654                                fs_path.clone(),
1655                                concat(&prefix, subpath).into(),
1656                                force_in_lookup_dir,
1657                                pattern,
1658                            ),
1659                        ));
1660                    }
1661                }
1662            }
1663            false
1664        } else {
1665            true
1666        }
1667    } else {
1668        true
1669    };
1670
1671    if slow_path {
1672        async {
1673            // Slow path: There are infinite matches for the pattern
1674            // We will enumerate the filesystem to find matches
1675            if !force_in_lookup_dir {
1676                // {prefix}..
1677                prefix.push_str("..");
1678                if let Some(pos) = pat.match_position(&prefix) {
1679                    results.push((
1680                        pos,
1681                        PatternMatch::Directory(prefix.clone().into(), lookup_dir.parent()),
1682                    ));
1683                }
1684
1685                // {prefix}../
1686                prefix.push('/');
1687                if let Some(pos) = pat.match_position(&prefix) {
1688                    results.push((
1689                        pos,
1690                        PatternMatch::Directory(prefix.clone().into(), lookup_dir.parent()),
1691                    ));
1692                }
1693                if let Some(pos) = pat.could_match_position(&prefix) {
1694                    nested.push((
1695                        pos,
1696                        read_matches(lookup_dir.parent(), prefix.clone().into(), false, pattern),
1697                    ));
1698                }
1699                prefix.pop();
1700                prefix.pop();
1701                prefix.pop();
1702            }
1703            {
1704                prefix.push('.');
1705                // {prefix}.
1706                if let Some(pos) = pat.match_position(&prefix) {
1707                    results.push((
1708                        pos,
1709                        PatternMatch::Directory(prefix.clone().into(), lookup_dir.clone()),
1710                    ));
1711                }
1712                prefix.pop();
1713            }
1714            if prefix.is_empty() {
1715                if let Some(pos) = pat.match_position("./") {
1716                    results.push((
1717                        pos,
1718                        PatternMatch::Directory(rcstr!("./"), lookup_dir.clone()),
1719                    ));
1720                }
1721                if let Some(pos) = pat.could_match_position("./") {
1722                    nested.push((
1723                        pos,
1724                        read_matches(lookup_dir.clone(), rcstr!("./"), false, pattern),
1725                    ));
1726                }
1727            } else {
1728                prefix.push('/');
1729                // {prefix}/
1730                if let Some(pos) = pat.could_match_position(&prefix) {
1731                    nested.push((
1732                        pos,
1733                        read_matches(
1734                            lookup_dir.clone(),
1735                            prefix.to_string().into(),
1736                            false,
1737                            pattern,
1738                        ),
1739                    ));
1740                }
1741                prefix.pop();
1742                prefix.push_str("./");
1743                // {prefix}./
1744                if let Some(pos) = pat.could_match_position(&prefix) {
1745                    nested.push((
1746                        pos,
1747                        read_matches(
1748                            lookup_dir.clone(),
1749                            prefix.to_string().into(),
1750                            false,
1751                            pattern,
1752                        ),
1753                    ));
1754                }
1755                prefix.pop();
1756                prefix.pop();
1757            }
1758            match &*raw_read_dir_resolved(&lookup_dir).await? {
1759                RawDirectoryContent::Entries(map) => {
1760                    for (key, entry) in map.iter() {
1761                        match entry {
1762                            RawDirectoryEntry::File => {
1763                                let len = prefix.len();
1764                                prefix.push_str(key);
1765                                // {prefix}{key}
1766                                if let Some(pos) = pat.match_position(&prefix) {
1767                                    let path = lookup_dir.join(key)?;
1768                                    results.push((
1769                                        pos,
1770                                        PatternMatch::File(prefix.clone().into(), path),
1771                                    ));
1772                                }
1773                                prefix.truncate(len)
1774                            }
1775                            RawDirectoryEntry::Directory => {
1776                                let len = prefix.len();
1777                                prefix.push_str(key);
1778                                // {prefix}{key}
1779                                if prefix.ends_with('/') {
1780                                    prefix.pop();
1781                                }
1782                                if let Some(pos) = pat.match_position(&prefix) {
1783                                    let path = lookup_dir.join(key)?;
1784                                    results.push((
1785                                        pos,
1786                                        PatternMatch::Directory(prefix.clone().into(), path),
1787                                    ));
1788                                }
1789                                prefix.push('/');
1790                                // {prefix}{key}/
1791                                if let Some(pos) = pat.match_position(&prefix) {
1792                                    let path = lookup_dir.join(key)?;
1793                                    results.push((
1794                                        pos,
1795                                        PatternMatch::Directory(prefix.clone().into(), path),
1796                                    ));
1797                                }
1798                                if let Some(pos) = pat.could_match_position(&prefix) {
1799                                    let path = lookup_dir.join(key)?;
1800                                    nested.push((
1801                                        pos,
1802                                        read_matches(path, prefix.clone().into(), true, pattern),
1803                                    ));
1804                                }
1805                                prefix.truncate(len)
1806                            }
1807                            RawDirectoryEntry::Symlink => {
1808                                let len = prefix.len();
1809                                prefix.push_str(key);
1810                                // {prefix}{key}
1811                                if prefix.ends_with('/') {
1812                                    prefix.pop();
1813                                }
1814                                if let Some(pos) = pat.match_position(&prefix) {
1815                                    let fs_path = lookup_dir.join(key)?;
1816                                    if let LinkContent::Link { target } =
1817                                        &*fs_path.read_link().await?
1818                                    {
1819                                        if matches!(
1820                                            target.resolved_type().await?,
1821                                            FileSystemEntryType::Directory
1822                                        ) {
1823                                            results.push((
1824                                                pos,
1825                                                PatternMatch::Directory(
1826                                                    prefix.clone().into(),
1827                                                    fs_path,
1828                                                ),
1829                                            ));
1830                                        } else {
1831                                            results.push((
1832                                                pos,
1833                                                PatternMatch::File(prefix.clone().into(), fs_path),
1834                                            ));
1835                                        }
1836                                    }
1837                                }
1838                                prefix.push('/');
1839                                if let Some(pos) = pat.match_position(&prefix) {
1840                                    let fs_path = lookup_dir.join(key)?;
1841                                    if let LinkContent::Link { target } =
1842                                        &*fs_path.read_link().await?
1843                                        && matches!(
1844                                            target.resolved_type().await?,
1845                                            FileSystemEntryType::Directory
1846                                        )
1847                                    {
1848                                        results.push((
1849                                            pos,
1850                                            PatternMatch::Directory(prefix.clone().into(), fs_path),
1851                                        ));
1852                                    }
1853                                }
1854                                if let Some(pos) = pat.could_match_position(&prefix) {
1855                                    let fs_path = lookup_dir.join(key)?;
1856                                    if let LinkContent::Link { target } =
1857                                        &*fs_path.read_link().await?
1858                                        && matches!(
1859                                            target.resolved_type().await?,
1860                                            FileSystemEntryType::Directory
1861                                        )
1862                                    {
1863                                        results.push((
1864                                            pos,
1865                                            PatternMatch::Directory(prefix.clone().into(), fs_path),
1866                                        ));
1867                                    }
1868                                }
1869                                prefix.truncate(len)
1870                            }
1871                            RawDirectoryEntry::Other => {}
1872                        }
1873                    }
1874                }
1875                RawDirectoryContent::NotFound => {}
1876            };
1877            anyhow::Ok(())
1878        }
1879        .instrument(tracing::trace_span!("read_matches slow_path"))
1880        .await?;
1881    }
1882    if results.is_empty() && nested.len() == 1 {
1883        Ok(nested.into_iter().next().unwrap().1)
1884    } else {
1885        for (pos, nested) in nested.into_iter() {
1886            results.extend(nested.await?.iter().cloned().map(|p| (pos, p)));
1887        }
1888        results.sort_by(|(a, am), (b, bm)| (*a).cmp(b).then_with(|| am.name().cmp(bm.name())));
1889        Ok(Vc::cell(
1890            results.into_iter().map(|(_, p)| p).collect::<Vec<_>>(),
1891        ))
1892    }
1893}
1894
1895fn concat(a: &str, b: &str) -> String {
1896    let mut result = String::with_capacity(a.len() + b.len());
1897    result.push_str(a);
1898    result.push_str(b);
1899    result
1900}
1901
1902/// Returns the parent folder and the last segment of the path. When the last segment is unknown (e.
1903/// g. when using `../`) it returns the full path and an empty string.
1904fn split_last_segment(path: &str) -> (&str, &str) {
1905    if let Some((remaining_path, last_segment)) = path.rsplit_once('/') {
1906        match last_segment {
1907            "" => split_last_segment(remaining_path),
1908            "." => split_last_segment(remaining_path),
1909            ".." => match split_last_segment(remaining_path) {
1910                (_, "") => (path, ""),
1911                (parent_path, _) => split_last_segment(parent_path),
1912            },
1913            _ => (remaining_path, last_segment),
1914        }
1915    } else {
1916        match path {
1917            "" => ("", ""),
1918            "." => ("", ""),
1919            ".." => ("..", ""),
1920            _ => ("", path),
1921        }
1922    }
1923}
1924
1925#[cfg(test)]
1926mod tests {
1927    use std::path::Path;
1928
1929    use rstest::*;
1930    use turbo_rcstr::{RcStr, rcstr};
1931    use turbo_tasks::Vc;
1932    use turbo_tasks_backend::{BackendOptions, TurboTasksBackend, noop_backing_storage};
1933    use turbo_tasks_fs::{DiskFileSystem, FileSystem};
1934
1935    use super::{
1936        Pattern, PatternMatch, longest_common_prefix, longest_common_suffix, read_matches,
1937        split_last_segment,
1938    };
1939
1940    #[test]
1941    fn longest_common_prefix_test() {
1942        assert_eq!(longest_common_prefix(&["ab"]), "ab");
1943        assert_eq!(longest_common_prefix(&["ab", "cd", "ef"]), "");
1944        assert_eq!(longest_common_prefix(&["ab1", "ab23", "ab456"]), "ab");
1945        assert_eq!(longest_common_prefix(&["abc", "abc", "abc"]), "abc");
1946        assert_eq!(longest_common_prefix(&["abc", "a", "abc"]), "a");
1947    }
1948
1949    #[test]
1950    fn longest_common_suffix_test() {
1951        assert_eq!(longest_common_suffix(&["ab"]), "ab");
1952        assert_eq!(longest_common_suffix(&["ab", "cd", "ef"]), "");
1953        assert_eq!(longest_common_suffix(&["1ab", "23ab", "456ab"]), "ab");
1954        assert_eq!(longest_common_suffix(&["abc", "abc", "abc"]), "abc");
1955        assert_eq!(longest_common_suffix(&["abc", "c", "abc"]), "c");
1956    }
1957
1958    #[test]
1959    fn normalize() {
1960        let a = Pattern::Constant(rcstr!("a"));
1961        let b = Pattern::Constant(rcstr!("b"));
1962        let c = Pattern::Constant(rcstr!("c"));
1963        let s = Pattern::Constant(rcstr!("/"));
1964        let d = Pattern::Dynamic;
1965        {
1966            let mut p = Pattern::Concatenation(vec![
1967                Pattern::Alternatives(vec![a.clone(), b.clone()]),
1968                s.clone(),
1969                c.clone(),
1970            ]);
1971            p.normalize();
1972            assert_eq!(
1973                p,
1974                Pattern::Alternatives(vec![
1975                    Pattern::Constant(rcstr!("a/c")),
1976                    Pattern::Constant(rcstr!("b/c")),
1977                ])
1978            );
1979        }
1980
1981        #[allow(clippy::redundant_clone)] // alignment
1982        {
1983            let mut p = Pattern::Concatenation(vec![
1984                Pattern::Alternatives(vec![a.clone(), b.clone(), d.clone()]),
1985                s.clone(),
1986                Pattern::Alternatives(vec![b.clone(), c.clone(), d.clone()]),
1987            ]);
1988            p.normalize();
1989
1990            assert_eq!(
1991                p,
1992                Pattern::Alternatives(vec![
1993                    Pattern::Constant(rcstr!("a/b")),
1994                    Pattern::Constant(rcstr!("b/b")),
1995                    Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!("/b"))]),
1996                    Pattern::Constant(rcstr!("a/c")),
1997                    Pattern::Constant(rcstr!("b/c")),
1998                    Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!("/c"))]),
1999                    Pattern::Concatenation(vec![Pattern::Constant(rcstr!("a/")), Pattern::Dynamic]),
2000                    Pattern::Concatenation(vec![Pattern::Constant(rcstr!("b/")), Pattern::Dynamic]),
2001                    Pattern::Concatenation(vec![
2002                        Pattern::Dynamic,
2003                        Pattern::Constant(rcstr!("/")),
2004                        Pattern::Dynamic
2005                    ]),
2006                ])
2007            );
2008        }
2009
2010        #[allow(clippy::redundant_clone)] // alignment
2011        {
2012            let mut p = Pattern::Alternatives(vec![a.clone()]);
2013            p.normalize();
2014
2015            assert_eq!(p, a);
2016        }
2017
2018        #[allow(clippy::redundant_clone)] // alignment
2019        {
2020            let mut p = Pattern::Alternatives(vec![Pattern::Dynamic, Pattern::Dynamic]);
2021            p.normalize();
2022
2023            assert_eq!(p, Pattern::Dynamic);
2024        }
2025    }
2026
2027    #[test]
2028    fn with_normalized_path() {
2029        assert!(
2030            Pattern::Constant(rcstr!("a/../.."))
2031                .with_normalized_path()
2032                .is_none()
2033        );
2034        assert_eq!(
2035            Pattern::Constant(rcstr!("a/b/../c"))
2036                .with_normalized_path()
2037                .unwrap(),
2038            Pattern::Constant(rcstr!("a/c"))
2039        );
2040        assert_eq!(
2041            Pattern::Alternatives(vec![
2042                Pattern::Constant(rcstr!("a/b/../c")),
2043                Pattern::Constant(rcstr!("a/b/../c/d"))
2044            ])
2045            .with_normalized_path()
2046            .unwrap(),
2047            Pattern::Alternatives(vec![
2048                Pattern::Constant(rcstr!("a/c")),
2049                Pattern::Constant(rcstr!("a/c/d"))
2050            ])
2051        );
2052        assert_eq!(
2053            Pattern::Constant(rcstr!("a/b/"))
2054                .with_normalized_path()
2055                .unwrap(),
2056            Pattern::Constant(rcstr!("a/b"))
2057        );
2058
2059        // Dynamic is a segment itself
2060        assert_eq!(
2061            Pattern::Concatenation(vec![
2062                Pattern::Constant(rcstr!("a/b/")),
2063                Pattern::Dynamic,
2064                Pattern::Constant(rcstr!("../c"))
2065            ])
2066            .with_normalized_path()
2067            .unwrap(),
2068            Pattern::Concatenation(vec![
2069                Pattern::Constant(rcstr!("a/b/")),
2070                Pattern::Dynamic,
2071                Pattern::Constant(rcstr!("../c"))
2072            ])
2073        );
2074
2075        // Dynamic is part of a segment
2076        assert_eq!(
2077            Pattern::Concatenation(vec![
2078                Pattern::Constant(rcstr!("a/b")),
2079                Pattern::Dynamic,
2080                Pattern::Constant(rcstr!("../c"))
2081            ])
2082            .with_normalized_path()
2083            .unwrap(),
2084            Pattern::Concatenation(vec![
2085                Pattern::Constant(rcstr!("a/b")),
2086                Pattern::Dynamic,
2087                Pattern::Constant(rcstr!("../c"))
2088            ])
2089        );
2090        assert_eq!(
2091            Pattern::Concatenation(vec![
2092                Pattern::Constant(rcstr!("src/")),
2093                Pattern::Dynamic,
2094                Pattern::Constant(rcstr!(".js"))
2095            ])
2096            .with_normalized_path()
2097            .unwrap(),
2098            Pattern::Concatenation(vec![
2099                Pattern::Constant(rcstr!("src/")),
2100                Pattern::Dynamic,
2101                Pattern::Constant(rcstr!(".js"))
2102            ])
2103        );
2104    }
2105
2106    #[test]
2107    fn is_match() {
2108        let pat = Pattern::Concatenation(vec![
2109            Pattern::Constant(rcstr!(".")),
2110            Pattern::Constant(rcstr!("/")),
2111            Pattern::Dynamic,
2112            Pattern::Constant(rcstr!(".js")),
2113        ]);
2114        assert!(pat.could_match(""));
2115        assert!(pat.could_match("./"));
2116        assert!(!pat.is_match("./"));
2117        assert!(pat.is_match("./index.js"));
2118        assert!(!pat.is_match("./index"));
2119        assert!(pat.is_match("./foo/index.js"));
2120        assert!(pat.is_match("./foo/bar/index.js"));
2121
2122        // forbidden:
2123        assert!(!pat.is_match("./../index.js"));
2124        assert!(!pat.is_match("././index.js"));
2125        assert!(!pat.is_match("./.git/index.js"));
2126        assert!(!pat.is_match("./inner/../index.js"));
2127        assert!(!pat.is_match("./inner/./index.js"));
2128        assert!(!pat.is_match("./inner/.git/index.js"));
2129        assert!(!pat.could_match("./../"));
2130        assert!(!pat.could_match("././"));
2131        assert!(!pat.could_match("./.git/"));
2132        assert!(!pat.could_match("./inner/../"));
2133        assert!(!pat.could_match("./inner/./"));
2134        assert!(!pat.could_match("./inner/.git/"));
2135    }
2136
2137    #[test]
2138    fn is_match_dynamic_no_slash() {
2139        let pat = Pattern::Concatenation(vec![
2140            Pattern::Constant(rcstr!(".")),
2141            Pattern::Constant(rcstr!("/")),
2142            Pattern::DynamicNoSlash,
2143            Pattern::Constant(rcstr!(".js")),
2144        ]);
2145        assert!(pat.could_match(""));
2146        assert!(pat.could_match("./"));
2147        assert!(!pat.is_match("./"));
2148        assert!(pat.is_match("./index.js"));
2149        assert!(!pat.is_match("./index"));
2150        assert!(!pat.is_match("./foo/index.js"));
2151        assert!(!pat.is_match("./foo/bar/index.js"));
2152    }
2153
2154    #[test]
2155    fn constant_prefix() {
2156        assert_eq!(
2157            Pattern::Constant(rcstr!("a/b/c.js")).constant_prefix(),
2158            "a/b/c.js",
2159        );
2160
2161        let pat = Pattern::Alternatives(vec![
2162            Pattern::Constant(rcstr!("a/b/x")),
2163            Pattern::Constant(rcstr!("a/b/y")),
2164            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("a/b/c/")), Pattern::Dynamic]),
2165        ]);
2166        assert_eq!(pat.constant_prefix(), "a/b/");
2167    }
2168
2169    #[test]
2170    fn constant_suffix() {
2171        assert_eq!(
2172            Pattern::Constant(rcstr!("a/b/c.js")).constant_suffix(),
2173            "a/b/c.js",
2174        );
2175
2176        let pat = Pattern::Alternatives(vec![
2177            Pattern::Constant(rcstr!("a/b/x.js")),
2178            Pattern::Constant(rcstr!("a/b/y.js")),
2179            Pattern::Concatenation(vec![
2180                Pattern::Constant(rcstr!("a/b/c/")),
2181                Pattern::Dynamic,
2182                Pattern::Constant(rcstr!(".js")),
2183            ]),
2184        ]);
2185        assert_eq!(pat.constant_suffix(), ".js");
2186    }
2187
2188    #[test]
2189    fn strip_prefix() {
2190        fn strip(mut pat: Pattern, n: usize) -> Pattern {
2191            pat.strip_prefix_len(n).unwrap();
2192            pat
2193        }
2194
2195        assert_eq!(
2196            strip(Pattern::Constant(rcstr!("a/b")), 0),
2197            Pattern::Constant(rcstr!("a/b"))
2198        );
2199
2200        assert_eq!(
2201            strip(
2202                Pattern::Alternatives(vec![
2203                    Pattern::Constant(rcstr!("a/b/x")),
2204                    Pattern::Constant(rcstr!("a/b/y")),
2205                ]),
2206                2
2207            ),
2208            Pattern::Alternatives(vec![
2209                Pattern::Constant(rcstr!("b/x")),
2210                Pattern::Constant(rcstr!("b/y")),
2211            ])
2212        );
2213
2214        assert_eq!(
2215            strip(
2216                Pattern::Concatenation(vec![
2217                    Pattern::Constant(rcstr!("a/")),
2218                    Pattern::Constant(rcstr!("b")),
2219                    Pattern::Constant(rcstr!("/")),
2220                    Pattern::Constant(rcstr!("y/")),
2221                    Pattern::Dynamic
2222                ]),
2223                4
2224            ),
2225            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("y/")), Pattern::Dynamic]),
2226        );
2227    }
2228
2229    #[test]
2230    fn strip_suffix() {
2231        fn strip(mut pat: Pattern, n: usize) -> Pattern {
2232            pat.strip_suffix_len(n);
2233            pat
2234        }
2235
2236        assert_eq!(
2237            strip(Pattern::Constant(rcstr!("a/b")), 0),
2238            Pattern::Constant(rcstr!("a/b"))
2239        );
2240
2241        assert_eq!(
2242            strip(
2243                Pattern::Alternatives(vec![
2244                    Pattern::Constant(rcstr!("x/b/a")),
2245                    Pattern::Constant(rcstr!("y/b/a")),
2246                ]),
2247                2
2248            ),
2249            Pattern::Alternatives(vec![
2250                Pattern::Constant(rcstr!("x/b")),
2251                Pattern::Constant(rcstr!("y/b")),
2252            ])
2253        );
2254
2255        assert_eq!(
2256            strip(
2257                Pattern::Concatenation(vec![
2258                    Pattern::Dynamic,
2259                    Pattern::Constant(rcstr!("/a/")),
2260                    Pattern::Constant(rcstr!("b")),
2261                    Pattern::Constant(rcstr!("/")),
2262                    Pattern::Constant(rcstr!("y/")),
2263                ]),
2264                4
2265            ),
2266            Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!("/a/")),]),
2267        );
2268    }
2269
2270    #[test]
2271    fn spread_into_star() {
2272        let pat = Pattern::Constant(rcstr!("xyz"));
2273        assert_eq!(
2274            pat.spread_into_star("before/after"),
2275            Pattern::Constant(rcstr!("before/after")),
2276        );
2277
2278        let pat =
2279            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("a/b/c/")), Pattern::Dynamic]);
2280        assert_eq!(
2281            pat.spread_into_star("before/*/after"),
2282            Pattern::Concatenation(vec![
2283                Pattern::Constant(rcstr!("before/a/b/c/")),
2284                Pattern::Dynamic,
2285                Pattern::Constant(rcstr!("/after"))
2286            ])
2287        );
2288
2289        let pat = Pattern::Alternatives(vec![
2290            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("a/")), Pattern::Dynamic]),
2291            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("b/")), Pattern::Dynamic]),
2292        ]);
2293        assert_eq!(
2294            pat.spread_into_star("before/*/after"),
2295            Pattern::Alternatives(vec![
2296                Pattern::Concatenation(vec![
2297                    Pattern::Constant(rcstr!("before/a/")),
2298                    Pattern::Dynamic,
2299                    Pattern::Constant(rcstr!("/after"))
2300                ]),
2301                Pattern::Concatenation(vec![
2302                    Pattern::Constant(rcstr!("before/b/")),
2303                    Pattern::Dynamic,
2304                    Pattern::Constant(rcstr!("/after"))
2305                ]),
2306            ])
2307        );
2308
2309        let pat = Pattern::Alternatives(vec![
2310            Pattern::Constant(rcstr!("a")),
2311            Pattern::Constant(rcstr!("b")),
2312        ]);
2313        assert_eq!(
2314            pat.spread_into_star("before/*/*"),
2315            Pattern::Alternatives(vec![
2316                Pattern::Constant(rcstr!("before/a/a")),
2317                Pattern::Constant(rcstr!("before/b/b")),
2318            ])
2319        );
2320
2321        let pat = Pattern::Dynamic;
2322        assert_eq!(
2323            pat.spread_into_star("before/*/*"),
2324            Pattern::Concatenation(vec![
2325                // TODO currently nothing ensures that both Dynamic parts are equal
2326                Pattern::Constant(rcstr!("before/")),
2327                Pattern::Dynamic,
2328                Pattern::Constant(rcstr!("/")),
2329                Pattern::Dynamic
2330            ])
2331        );
2332    }
2333
2334    #[rstest]
2335    #[case::dynamic(Pattern::Dynamic)]
2336    #[case::dynamic_concat(Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!(".js"))]))]
2337    fn dynamic_match(#[case] pat: Pattern) {
2338        assert!(pat.could_match(""));
2339        assert!(pat.is_match("index.js"));
2340
2341        // forbidden:
2342        assert!(!pat.could_match("./"));
2343        assert!(!pat.is_match("./"));
2344        assert!(!pat.could_match("."));
2345        assert!(!pat.is_match("."));
2346        assert!(!pat.could_match("../"));
2347        assert!(!pat.is_match("../"));
2348        assert!(!pat.could_match(".."));
2349        assert!(!pat.is_match(".."));
2350        assert!(!pat.is_match("./../index.js"));
2351        assert!(!pat.is_match("././index.js"));
2352        assert!(!pat.is_match("./.git/index.js"));
2353        assert!(!pat.is_match("./inner/../index.js"));
2354        assert!(!pat.is_match("./inner/./index.js"));
2355        assert!(!pat.is_match("./inner/.git/index.js"));
2356        assert!(!pat.could_match("./../"));
2357        assert!(!pat.could_match("././"));
2358        assert!(!pat.could_match("./.git/"));
2359        assert!(!pat.could_match("./inner/../"));
2360        assert!(!pat.could_match("./inner/./"));
2361        assert!(!pat.could_match("./inner/.git/"));
2362        assert!(!pat.could_match("dir//"));
2363        assert!(!pat.could_match("dir//dir"));
2364        assert!(!pat.could_match("dir///dir"));
2365        assert!(!pat.could_match("/"));
2366        assert!(!pat.could_match("//"));
2367        assert!(!pat.could_match("/ROOT/"));
2368
2369        assert!(!pat.could_match("node_modules"));
2370        assert!(!pat.could_match("node_modules/package"));
2371        assert!(!pat.could_match("nested/node_modules"));
2372        assert!(!pat.could_match("nested/node_modules/package"));
2373
2374        // forbidden match
2375        assert!(pat.could_match("file.map"));
2376        assert!(!pat.is_match("file.map"));
2377        assert!(pat.is_match("file.map/file.js"));
2378        assert!(!pat.is_match("file.d.ts"));
2379        assert!(!pat.is_match("file.d.ts.map"));
2380        assert!(!pat.is_match("file.d.ts.map"));
2381        assert!(!pat.is_match("dir/file.d.ts.map"));
2382        assert!(!pat.is_match("dir/inner/file.d.ts.map"));
2383        assert!(pat.could_match("dir/inner/file.d.ts.map"));
2384    }
2385
2386    #[rstest]
2387    #[case::slash(Pattern::Concatenation(vec![Pattern::Constant(rcstr!("node_modules/")),Pattern::Dynamic]))]
2388    #[case::nested(Pattern::Constant(rcstr!("node_modules")).or_any_nested_file())]
2389    fn dynamic_match_node_modules(#[case] pat: Pattern) {
2390        assert!(!pat.is_match("node_modules/package"));
2391        assert!(!pat.could_match("node_modules/package"));
2392        assert!(!pat.is_match("node_modules/package/index.js"));
2393        assert!(!pat.could_match("node_modules/package/index.js"));
2394    }
2395
2396    #[rstest]
2397    fn dynamic_match2() {
2398        let pat = Pattern::Concatenation(vec![
2399            Pattern::Dynamic,
2400            Pattern::Constant(rcstr!("/")),
2401            Pattern::Dynamic,
2402        ]);
2403        assert!(pat.could_match("dir"));
2404        assert!(pat.could_match("dir/"));
2405        assert!(pat.is_match("dir/index.js"));
2406
2407        // forbidden:
2408        assert!(!pat.could_match("./"));
2409        assert!(!pat.is_match("./"));
2410        assert!(!pat.could_match("."));
2411        assert!(!pat.is_match("."));
2412        assert!(!pat.could_match("../"));
2413        assert!(!pat.is_match("../"));
2414        assert!(!pat.could_match(".."));
2415        assert!(!pat.is_match(".."));
2416        assert!(!pat.is_match("./../index.js"));
2417        assert!(!pat.is_match("././index.js"));
2418        assert!(!pat.is_match("./.git/index.js"));
2419        assert!(!pat.is_match("./inner/../index.js"));
2420        assert!(!pat.is_match("./inner/./index.js"));
2421        assert!(!pat.is_match("./inner/.git/index.js"));
2422        assert!(!pat.could_match("./../"));
2423        assert!(!pat.could_match("././"));
2424        assert!(!pat.could_match("./.git/"));
2425        assert!(!pat.could_match("./inner/../"));
2426        assert!(!pat.could_match("./inner/./"));
2427        assert!(!pat.could_match("./inner/.git/"));
2428        assert!(!pat.could_match("dir//"));
2429        assert!(!pat.could_match("dir//dir"));
2430        assert!(!pat.could_match("dir///dir"));
2431        assert!(!pat.could_match("/ROOT/"));
2432
2433        assert!(!pat.could_match("node_modules"));
2434        assert!(!pat.could_match("node_modules/package"));
2435        assert!(!pat.could_match("nested/node_modules"));
2436        assert!(!pat.could_match("nested/node_modules/package"));
2437
2438        // forbidden match
2439        assert!(pat.could_match("dir/file.map"));
2440        assert!(!pat.is_match("dir/file.map"));
2441        assert!(pat.is_match("file.map/file.js"));
2442        assert!(!pat.is_match("dir/file.d.ts"));
2443        assert!(!pat.is_match("dir/file.d.ts.map"));
2444        assert!(!pat.is_match("dir/file.d.ts.map"));
2445        assert!(!pat.is_match("dir/file.d.ts.map"));
2446        assert!(!pat.is_match("dir/inner/file.d.ts.map"));
2447        assert!(pat.could_match("dir/inner/file.d.ts.map"));
2448    }
2449
2450    #[rstest]
2451    #[case::dynamic(Pattern::Dynamic)]
2452    #[case::dynamic_concat(Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!(".js"))]))]
2453    #[case::dynamic_concat2(Pattern::Concatenation(vec![
2454        Pattern::Dynamic,
2455        Pattern::Constant(rcstr!("/")),
2456        Pattern::Dynamic,
2457    ]))]
2458    #[case::dynamic_alt_concat(Pattern::alternatives(vec![
2459        Pattern::Concatenation(vec![
2460            Pattern::Dynamic,
2461            Pattern::Constant(rcstr!("/")),
2462            Pattern::Dynamic,
2463        ]),
2464        Pattern::Dynamic,
2465    ]))]
2466    fn split_could_match(#[case] pat: Pattern) {
2467        let (abs, rel) = pat.split_could_match("/ROOT/");
2468        assert!(abs.is_none());
2469        assert!(rel.is_some());
2470    }
2471
2472    #[rstest]
2473    #[case::dynamic(Pattern::Dynamic, "feijf", None)]
2474    #[case::dynamic_concat(
2475        Pattern::Concatenation(vec![Pattern::Dynamic, Pattern::Constant(rcstr!(".js"))]),
2476        "hello.", None
2477    )]
2478    #[case::constant(Pattern::Constant(rcstr!("Hello World")), "Hello ", Some(vec![("World", true)]))]
2479    #[case::alternatives(
2480        Pattern::Alternatives(vec![
2481            Pattern::Constant(rcstr!("Hello World")),
2482            Pattern::Constant(rcstr!("Hello All"))
2483        ]), "Hello ", Some(vec![("World", true), ("All", true)])
2484    )]
2485    #[case::alternatives_non_end(
2486        Pattern::Alternatives(vec![
2487            Pattern::Constant(rcstr!("Hello World")),
2488            Pattern::Constant(rcstr!("Hello All")),
2489            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("Hello more")), Pattern::Dynamic])
2490        ]), "Hello ", Some(vec![("World", true), ("All", true), ("more", false)])
2491    )]
2492    #[case::request_with_extensions(
2493        Pattern::Alternatives(vec![
2494            Pattern::Constant(rcstr!("./file.js")),
2495            Pattern::Constant(rcstr!("./file.ts")),
2496            Pattern::Constant(rcstr!("./file.cjs")),
2497        ]), "./", Some(vec![("file.js", true), ("file.ts", true), ("file.cjs", true)])
2498    )]
2499    fn next_constants(
2500        #[case] pat: Pattern,
2501        #[case] value: &str,
2502        #[case] expected: Option<Vec<(&str, bool)>>,
2503    ) {
2504        assert_eq!(pat.next_constants(value), expected);
2505    }
2506
2507    #[test]
2508    fn replace_final_constants() {
2509        fn f(mut p: Pattern, cb: &mut impl FnMut(&RcStr) -> Option<Pattern>) -> Pattern {
2510            p.replace_final_constants(cb);
2511            p
2512        }
2513
2514        let mut js_to_ts_tsx = |c: &RcStr| -> Option<Pattern> {
2515            c.strip_suffix(".js").map(|rest| {
2516                let new_ending = Pattern::Alternatives(vec![
2517                    Pattern::Constant(rcstr!(".ts")),
2518                    Pattern::Constant(rcstr!(".tsx")),
2519                    Pattern::Constant(rcstr!(".js")),
2520                ]);
2521                if !rest.is_empty() {
2522                    Pattern::Concatenation(vec![Pattern::Constant(rest.into()), new_ending])
2523                } else {
2524                    new_ending
2525                }
2526            })
2527        };
2528
2529        assert_eq!(
2530            f(
2531                Pattern::Concatenation(vec![
2532                    Pattern::Constant(rcstr!(".")),
2533                    Pattern::Constant(rcstr!("/")),
2534                    Pattern::Dynamic,
2535                    Pattern::Alternatives(vec![
2536                        Pattern::Constant(rcstr!(".js")),
2537                        Pattern::Constant(rcstr!(".node")),
2538                    ])
2539                ]),
2540                &mut js_to_ts_tsx
2541            ),
2542            Pattern::Concatenation(vec![
2543                Pattern::Constant(rcstr!(".")),
2544                Pattern::Constant(rcstr!("/")),
2545                Pattern::Dynamic,
2546                Pattern::Alternatives(vec![
2547                    Pattern::Alternatives(vec![
2548                        Pattern::Constant(rcstr!(".ts")),
2549                        Pattern::Constant(rcstr!(".tsx")),
2550                        Pattern::Constant(rcstr!(".js")),
2551                    ]),
2552                    Pattern::Constant(rcstr!(".node")),
2553                ])
2554            ]),
2555        );
2556        assert_eq!(
2557            f(
2558                Pattern::Concatenation(vec![
2559                    Pattern::Constant(rcstr!(".")),
2560                    Pattern::Constant(rcstr!("/")),
2561                    Pattern::Constant(rcstr!("abc.js")),
2562                ]),
2563                &mut js_to_ts_tsx
2564            ),
2565            Pattern::Concatenation(vec![
2566                Pattern::Constant(rcstr!(".")),
2567                Pattern::Constant(rcstr!("/")),
2568                Pattern::Concatenation(vec![
2569                    Pattern::Constant(rcstr!("abc")),
2570                    Pattern::Alternatives(vec![
2571                        Pattern::Constant(rcstr!(".ts")),
2572                        Pattern::Constant(rcstr!(".tsx")),
2573                        Pattern::Constant(rcstr!(".js")),
2574                    ])
2575                ]),
2576            ])
2577        );
2578    }
2579
2580    #[test]
2581    fn match_apply_template() {
2582        assert_eq!(
2583            Pattern::Concatenation(vec![
2584                Pattern::Constant(rcstr!("a/b/")),
2585                Pattern::Dynamic,
2586                Pattern::Constant(rcstr!(".ts")),
2587            ])
2588            .match_apply_template(
2589                "a/b/foo.ts",
2590                &Pattern::Concatenation(vec![
2591                    Pattern::Constant(rcstr!("@/a/b/")),
2592                    Pattern::Dynamic,
2593                    Pattern::Constant(rcstr!(".js")),
2594                ])
2595            )
2596            .as_deref(),
2597            Some("@/a/b/foo.js")
2598        );
2599        assert_eq!(
2600            Pattern::Concatenation(vec![
2601                Pattern::Constant(rcstr!("b/")),
2602                Pattern::Dynamic,
2603                Pattern::Constant(rcstr!(".ts")),
2604            ])
2605            .match_apply_template(
2606                "a/b/foo.ts",
2607                &Pattern::Concatenation(vec![
2608                    Pattern::Constant(rcstr!("@/a/b/")),
2609                    Pattern::Dynamic,
2610                    Pattern::Constant(rcstr!(".js")),
2611                ])
2612            )
2613            .as_deref(),
2614            None,
2615        );
2616        assert_eq!(
2617            Pattern::Concatenation(vec![
2618                Pattern::Constant(rcstr!("a/b/")),
2619                Pattern::Dynamic,
2620                Pattern::Constant(rcstr!(".ts")),
2621            ])
2622            .match_apply_template(
2623                "a/b/foo.ts",
2624                &Pattern::Concatenation(vec![
2625                    Pattern::Constant(rcstr!("@/a/b/x")),
2626                    Pattern::Constant(rcstr!(".js")),
2627                ])
2628            )
2629            .as_deref(),
2630            None,
2631        );
2632        assert_eq!(
2633            Pattern::Concatenation(vec![Pattern::Constant(rcstr!("./sub/")), Pattern::Dynamic])
2634                .match_apply_template(
2635                    "./sub/file1",
2636                    &Pattern::Concatenation(vec![
2637                        Pattern::Constant(rcstr!("@/sub/")),
2638                        Pattern::Dynamic
2639                    ])
2640                )
2641                .as_deref(),
2642            Some("@/sub/file1"),
2643        );
2644    }
2645
2646    #[test]
2647    fn test_split_last_segment() {
2648        assert_eq!(split_last_segment(""), ("", ""));
2649        assert_eq!(split_last_segment("a"), ("", "a"));
2650        assert_eq!(split_last_segment("a/"), ("", "a"));
2651        assert_eq!(split_last_segment("a/b"), ("a", "b"));
2652        assert_eq!(split_last_segment("a/b/"), ("a", "b"));
2653        assert_eq!(split_last_segment("a/b/c"), ("a/b", "c"));
2654        assert_eq!(split_last_segment("a/b/."), ("a", "b"));
2655        assert_eq!(split_last_segment("a/b/.."), ("", "a"));
2656        assert_eq!(split_last_segment("a/b/c/.."), ("a", "b"));
2657        assert_eq!(split_last_segment("a/b/c/../.."), ("", "a"));
2658        assert_eq!(split_last_segment("a/b/c/d/../.."), ("a", "b"));
2659        assert_eq!(split_last_segment("a/b/c/../d/.."), ("a", "b"));
2660        assert_eq!(split_last_segment("a/b/../c/d/.."), ("a/b/..", "c"));
2661        assert_eq!(split_last_segment("."), ("", ""));
2662        assert_eq!(split_last_segment("./"), ("", ""));
2663        assert_eq!(split_last_segment(".."), ("..", ""));
2664        assert_eq!(split_last_segment("../"), ("..", ""));
2665        assert_eq!(split_last_segment("./../"), ("./..", ""));
2666        assert_eq!(split_last_segment("../../"), ("../..", ""));
2667        assert_eq!(split_last_segment("../../."), ("../..", ""));
2668        assert_eq!(split_last_segment("../.././"), ("../..", ""));
2669        assert_eq!(split_last_segment("a/.."), ("", ""));
2670        assert_eq!(split_last_segment("a/../"), ("", ""));
2671        assert_eq!(split_last_segment("a/../.."), ("a/../..", ""));
2672        assert_eq!(split_last_segment("a/../../"), ("a/../..", ""));
2673        assert_eq!(split_last_segment("a/././../"), ("", ""));
2674        assert_eq!(split_last_segment("../a"), ("..", "a"));
2675        assert_eq!(split_last_segment("../a/"), ("..", "a"));
2676        assert_eq!(split_last_segment("../../a"), ("../..", "a"));
2677        assert_eq!(split_last_segment("../../a/"), ("../..", "a"));
2678    }
2679
2680    #[cfg(all(unix, debug_assertions))]
2681    #[tokio::test(flavor = "multi_thread", worker_threads = 2)]
2682    async fn test_read_matches_resolves_lookup_dir_for_enumeration() {
2683        use std::{fs::create_dir_all, os::unix::fs::symlink};
2684
2685        let scratch = tempfile::tempdir().unwrap();
2686        let root = scratch.path();
2687        create_dir_all(root.join("real")).unwrap();
2688        std::fs::write(root.join("real/file.js"), "content").unwrap();
2689        symlink("real", root.join("alias")).unwrap();
2690        symlink("real/file.js", root.join("file-alias")).unwrap();
2691
2692        #[turbo_tasks::function(operation, root)]
2693        async fn operation(disk_root: RcStr) -> anyhow::Result<()> {
2694            let root = DiskFileSystem::new(rcstr!("test"), Vc::cell(disk_root))
2695                .root()
2696                .owned()
2697                .await?;
2698            let logical_dir = root.join("alias")?;
2699            let matches = read_matches(
2700                logical_dir.clone(),
2701                rcstr!(""),
2702                true,
2703                Pattern::new(Pattern::Dynamic),
2704            )
2705            .await?;
2706            assert!(matches.iter().any(|m| m
2707                == &PatternMatch::File(rcstr!("file.js"), logical_dir.join("file.js").unwrap(),)));
2708
2709            let file_probe = read_matches(
2710                root.join("file-alias")?,
2711                rcstr!(""),
2712                true,
2713                Pattern::new(Pattern::Dynamic),
2714            )
2715            .await?;
2716            assert!(file_probe.is_empty());
2717
2718            Ok(())
2719        }
2720
2721        let tt = turbo_tasks::TurboTasks::new(TurboTasksBackend::new(
2722            BackendOptions::default(),
2723            noop_backing_storage(),
2724        ));
2725        let disk_root: RcStr = root.to_str().unwrap().into();
2726        tt.run_once(async move {
2727            operation(disk_root).read_strongly_consistent().await?;
2728            anyhow::Ok(())
2729        })
2730        .await
2731        .unwrap();
2732    }
2733
2734    #[tokio::test(flavor = "multi_thread", worker_threads = 2)]
2735    async fn test_read_matches() {
2736        let tt = turbo_tasks::TurboTasks::new(TurboTasksBackend::new(
2737            BackendOptions::default(),
2738            noop_backing_storage(),
2739        ));
2740        tt.run_once(async {
2741            #[turbo_tasks::value]
2742            struct ReadMatchesOutput {
2743                dynamic: Vec<String>,
2744                dynamic_file_suffix: Vec<String>,
2745                node_modules_dynamic: Vec<String>,
2746                extension_ordering: Vec<String>,
2747                subpath_ordering: Vec<String>,
2748            }
2749
2750            #[turbo_tasks::function(operation, root)]
2751            async fn read_matches_operation() -> anyhow::Result<Vc<ReadMatchesOutput>> {
2752                let root = DiskFileSystem::new(
2753                    rcstr!("test"),
2754                    Vc::cell(
2755                        Path::new(env!("CARGO_MANIFEST_DIR"))
2756                            .join("tests/pattern/read_matches")
2757                            .to_str()
2758                            .unwrap()
2759                            .into(),
2760                    ),
2761                )
2762                .root()
2763                .owned()
2764                .await?;
2765
2766                let dynamic = read_matches(
2767                    root.clone(),
2768                    rcstr!(""),
2769                    false,
2770                    Pattern::new(Pattern::Dynamic),
2771                )
2772                .await?
2773                .into_iter()
2774                .map(|m| m.name().to_string())
2775                .collect::<Vec<_>>();
2776
2777                let dynamic_file_suffix = read_matches(
2778                    root.clone(),
2779                    rcstr!(""),
2780                    false,
2781                    Pattern::new(Pattern::concat([
2782                        Pattern::Constant(rcstr!("sub/foo")),
2783                        Pattern::Dynamic,
2784                    ])),
2785                )
2786                .await?
2787                .into_iter()
2788                .map(|m| m.name().to_string())
2789                .collect::<Vec<_>>();
2790
2791                let node_modules_dynamic = read_matches(
2792                    root.clone(),
2793                    rcstr!(""),
2794                    false,
2795                    Pattern::new(Pattern::Constant(rcstr!("node_modules")).or_any_nested_file()),
2796                )
2797                .await?
2798                .into_iter()
2799                .map(|m| m.name().to_string())
2800                .collect::<Vec<_>>();
2801
2802                // Test: extension ordering is preserved (fast path, until_end=true)
2803                // When both Component.web.tsx and Component.tsx exist, the order of
2804                // alternatives determines which comes first in results.
2805                let extension_ordering = read_matches(
2806                    root.clone(),
2807                    rcstr!(""),
2808                    false,
2809                    Pattern::new(Pattern::Alternatives(vec![
2810                        Pattern::Constant(rcstr!("extensions/Component")),
2811                        Pattern::Constant(rcstr!("extensions/Component.web.tsx")),
2812                        Pattern::Constant(rcstr!("extensions/Component.tsx")),
2813                    ])),
2814                )
2815                .await?
2816                .into_iter()
2817                .map(|m| m.name().to_string())
2818                .collect::<Vec<_>>();
2819
2820                // Test: subpath ordering is preserved (fast path, until_end=false)
2821                // When alternatives route to different subdirectories, the index ordering
2822                // must be respected. This exercises the fix for the hardcoded `0` bug.
2823                let subpath_ordering = read_matches(
2824                    root.clone(),
2825                    rcstr!(""),
2826                    false,
2827                    Pattern::new({
2828                        let mut p = Pattern::Alternatives(vec![
2829                            Pattern::Concatenation(vec![
2830                                Pattern::Constant(rcstr!("prio/a/")),
2831                                Pattern::Dynamic,
2832                            ]),
2833                            Pattern::Concatenation(vec![
2834                                Pattern::Constant(rcstr!("prio/b/")),
2835                                Pattern::Dynamic,
2836                            ]),
2837                        ]);
2838                        p.normalize();
2839                        p
2840                    }),
2841                )
2842                .await?
2843                .into_iter()
2844                .map(|m| m.name().to_string())
2845                .collect::<Vec<_>>();
2846
2847                Ok(ReadMatchesOutput {
2848                    dynamic,
2849                    dynamic_file_suffix,
2850                    node_modules_dynamic,
2851                    extension_ordering,
2852                    subpath_ordering,
2853                }
2854                .cell())
2855            }
2856
2857            let matches = read_matches_operation().read_strongly_consistent().await?;
2858
2859            // node_modules shouldn't be matched by Dynamic here
2860            assert_eq!(
2861                matches.dynamic,
2862                &[
2863                    "extensions",
2864                    "extensions/",
2865                    "extensions/Component.tsx",
2866                    "extensions/Component.web.tsx",
2867                    "index.js",
2868                    "prio",
2869                    "prio/",
2870                    "prio/a",
2871                    "prio/a/",
2872                    "prio/a/Component.tsx",
2873                    "prio/b",
2874                    "prio/b/",
2875                    "prio/b/Component.tsx",
2876                    "sub",
2877                    "sub/",
2878                    "sub/foo-a.js",
2879                    "sub/foo-b.js",
2880                ]
2881            );
2882
2883            // basic dynamic file suffix
2884            assert_eq!(
2885                matches.dynamic_file_suffix,
2886                &["sub/foo-a.js", "sub/foo-b.js"]
2887            );
2888
2889            // read_matches "node_modules/<dynamic>" should not return anything inside. We never
2890            // want to enumerate the list of packages here.
2891            assert_eq!(matches.node_modules_dynamic, &["node_modules"]);
2892
2893            // extension ordering: .web.tsx (index 1) must come before .tsx (index 2)
2894            assert_eq!(
2895                matches.extension_ordering,
2896                &["extensions/Component.web.tsx", "extensions/Component.tsx",]
2897            );
2898
2899            // subpath ordering: prio/a/ alternatives (index 0) must come before prio/b/
2900            // alternatives (index 1). This verifies the fix for the hardcoded `0` bug in
2901            // the until_end=false branch of the fast path.
2902            assert!(
2903                matches
2904                    .subpath_ordering
2905                    .iter()
2906                    .position(|s| s.starts_with("prio/a/"))
2907                    .unwrap()
2908                    < matches
2909                        .subpath_ordering
2910                        .iter()
2911                        .position(|s| s.starts_with("prio/b/"))
2912                        .unwrap(),
2913                "Expected prio/a/ results before prio/b/ results, got: {:?}",
2914                matches.subpath_ordering
2915            );
2916
2917            Ok(())
2918        })
2919        .await
2920        .unwrap();
2921    }
2922}
turbopack_core/resolve/pattern.rs

turbopack_core/resolve/
pattern.rs
