turbopack_core/resolve/
pattern.rs

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

turbopack_core/resolve/
pattern.rs
