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