turbopack_core/resolve/
pattern.rs

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

turbopack_core/resolve/
pattern.rs
