turbopack_core/resolve/
pattern.rs

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