turbopack_core/resolve/
alias_map.rs

1use std::{
2    borrow::Cow,
3    collections::BTreeMap,
4    fmt::{Debug, Formatter},
5};
6
7use anyhow::Result;
8use bincode::{Decode, Encode};
9use patricia_tree::PatriciaMap;
10use serde::{Deserialize, Serialize, de::DeserializeOwned};
11use turbo_rcstr::RcStr;
12use turbo_tasks::{
13    NonLocalValue,
14    debug::ValueDebugFormat,
15    trace::{TraceRawVcs, TraceRawVcsContext},
16};
17
18use crate::resolve::pattern::Pattern;
19
20/// A map of [`AliasPattern`]s as keys implemented using [`PatriciaMap`].
21///
22/// If a pattern has a wildcard character (*) within it, it will capture any
23/// number of characters, including path separators. The result of the capture
24/// will then be passed to the template.
25///
26/// If the pattern does not have a wildcard character, it will only match the
27/// exact string, and return the template as-is.
28#[derive(Clone, Encode, Decode)]
29#[bincode(
30    encode_bounds = "T: Serialize",
31    decode_bounds = "T: DeserializeOwned",
32    borrow_decode_bounds = "T: Deserialize<'__de>"
33)]
34pub struct AliasMap<T> {
35    #[bincode(with_serde)]
36    map: PatriciaMap<BTreeMap<AliasKey, T>>,
37}
38
39impl<T> Default for AliasMap<T> {
40    fn default() -> Self {
41        Self::new()
42    }
43}
44
45impl<T> PartialEq for AliasMap<T>
46where
47    T: PartialEq,
48{
49    fn eq(&self, other: &Self) -> bool {
50        if self.map.len() != other.map.len() {
51            return false;
52        }
53
54        self.map.iter().zip(other.map.iter()).all(|(a, b)| a == b)
55    }
56}
57
58impl<T> Eq for AliasMap<T> where T: Eq {}
59
60impl<T> TraceRawVcs for AliasMap<T>
61where
62    T: TraceRawVcs,
63{
64    fn trace_raw_vcs(&self, trace_context: &mut TraceRawVcsContext) {
65        for (_, map) in self.map.iter() {
66            for value in map.values() {
67                value.trace_raw_vcs(trace_context);
68            }
69        }
70    }
71}
72
73unsafe impl<T: NonLocalValue> NonLocalValue for AliasMap<T> {}
74
75#[cfg(debug_assertions)]
76impl<T> ValueDebugFormat for AliasMap<T>
77where
78    T: ValueDebugFormat,
79{
80    fn value_debug_format(&self, depth: usize) -> turbo_tasks::debug::ValueDebugFormatString<'_> {
81        use turbo_tasks::debug::{ValueDebugFormatString, internal::PassthroughDebug};
82        if depth == 0 {
83            return ValueDebugFormatString::Sync(std::any::type_name::<Self>().to_string());
84        }
85
86        let values = self
87            .map
88            .iter()
89            .flat_map(|(key, map)| {
90                let key = String::from_utf8(key).expect("invalid UTF-8 key in AliasMap");
91                map.iter().map(move |(alias_key, value)| match alias_key {
92                    AliasKey::Exact => (
93                        key.clone(),
94                        value.value_debug_format(depth.saturating_sub(1)),
95                    ),
96                    AliasKey::Wildcard { suffix } => (
97                        format!("{key}*{suffix}"),
98                        value.value_debug_format(depth.saturating_sub(1)),
99                    ),
100                })
101            })
102            .collect::<Vec<_>>();
103
104        ValueDebugFormatString::Async(Box::pin(async move {
105            let mut values_string = std::collections::HashMap::new();
106            for (key, value) in values {
107                match value {
108                    ValueDebugFormatString::Sync(string) => {
109                        values_string.insert(key, PassthroughDebug::new_string(string));
110                    }
111                    ValueDebugFormatString::Async(future) => {
112                        values_string.insert(key, PassthroughDebug::new_string(future.await?));
113                    }
114                }
115            }
116            Ok(format!("{values_string:#?}"))
117        }))
118    }
119}
120
121#[cfg(not(debug_assertions))]
122impl<T> ValueDebugFormat for AliasMap<T> {}
123
124impl<T> Debug for AliasMap<T>
125where
126    T: Debug,
127{
128    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
129        f.debug_map()
130            .entries(self.map.iter().flat_map(|(key, map)| {
131                let key = String::from_utf8(key).expect("invalid UTF-8 key in AliasMap");
132                map.iter().map(move |(alias_key, value)| match alias_key {
133                    AliasKey::Exact => (key.clone(), value),
134                    AliasKey::Wildcard { suffix } => (format!("{key}*{suffix}"), value),
135                })
136            }))
137            .finish()
138    }
139}
140
141impl<T> AliasMap<T> {
142    /// Creates a new alias map.
143    pub fn new() -> Self {
144        AliasMap {
145            map: PatriciaMap::new(),
146        }
147    }
148
149    /// Looks up a request in the alias map.
150    ///
151    /// Returns an iterator to all the matching aliases.
152    pub fn lookup<'a>(&'a self, request: &'a Pattern) -> AliasMapLookupIterator<'a, T>
153    where
154        T: Debug,
155    {
156        if matches!(request, Pattern::Alternatives(_)) {
157            panic!("AliasMap::lookup must not be called on alternatives, received {request:?}");
158        }
159
160        // Invariant: prefixes should be sorted by increasing length (base lengths),
161        // according to PATTERN_KEY_COMPARE. Since we're using a prefix tree, this is
162        // the default behavior of the common prefix iterator.
163        let mut prefixes_stack = if let Some(request) = request.as_constant_string() {
164            // Fast path: the request is a singular constant string
165            let common_prefixes = self.map.common_prefixes(request.as_bytes());
166            common_prefixes
167                .map(|(p, tree)| {
168                    let s = match std::str::from_utf8(p) {
169                        Ok(s) => s,
170                        Err(e) => std::str::from_utf8(&p[..e.valid_up_to()]).unwrap(),
171                    };
172                    (Cow::Borrowed(s), tree)
173                })
174                .collect::<Vec<_>>()
175        } else {
176            // Slow path: the pattern isn't constant, so we have to check every entry.
177            // With a dynamic pattern, we cannot use common_prefixes at all because matching
178            // Concatenation([Constant("./explicit-"), Dynamic]) results in the constant prefix
179            // "./explicit-" would not match the exact map entry "./explicit-a" (it's not a prefix).
180            self.map
181                .iter()
182                .map(|(p, tree)| {
183                    let s = match String::from_utf8(p) {
184                        Ok(s) => s,
185                        Err(e) => {
186                            let valid_up_to = e.utf8_error().valid_up_to();
187                            let mut p = e.into_bytes();
188                            p.drain(valid_up_to..);
189                            String::from_utf8(p).unwrap()
190                        }
191                    };
192                    (Cow::Owned(s), tree)
193                })
194                .collect::<Vec<_>>()
195        };
196
197        // `prefixes_stack` is now a prefiltered list of potential matches. `AliasMapLookupIterator`
198        // internally will perform a final check if an entry matches or not
199
200        AliasMapLookupIterator {
201            request,
202            current_prefix_iterator: prefixes_stack
203                .pop()
204                .map(|(prefix, map)| (prefix, map.iter())),
205            prefixes_stack,
206        }
207    }
208
209    /// Looks up a request in the alias map, but only returns aliases where the
210    /// prefix matches a certain predicate.
211    ///
212    /// Returns an iterator to all the matching aliases.
213    pub fn lookup_with_prefix_predicate<'a>(
214        &'a self,
215        request: &'a Pattern,
216        mut prefix_predicate: impl FnMut(&str) -> bool,
217    ) -> AliasMapLookupIterator<'a, T>
218    where
219        T: Debug,
220    {
221        if matches!(request, Pattern::Alternatives(_)) {
222            panic!("AliasMap::lookup must not be called on alternatives, received {request:?}");
223        }
224
225        // Invariant: prefixes should be sorted by increasing length (base lengths),
226        // according to PATTERN_KEY_COMPARE. Since we're using a prefix tree, this is
227        // the default behavior of the common prefix iterator.
228        let mut prefixes_stack = if let Some(request) = request.as_constant_string() {
229            // Fast path: the request is a singular constant string
230            let common_prefixes = self.map.common_prefixes(request.as_bytes());
231            common_prefixes
232                .filter_map(|(p, tree)| {
233                    let s = match std::str::from_utf8(p) {
234                        Ok(s) => s,
235                        Err(e) => std::str::from_utf8(&p[..e.valid_up_to()]).unwrap(),
236                    };
237                    if prefix_predicate(s) {
238                        Some((Cow::Borrowed(s), tree))
239                    } else {
240                        None
241                    }
242                })
243                .collect::<Vec<_>>()
244        } else {
245            // Slow path: the pattern isn't constant, so we have to check every entry
246            // With a dynamic pattern, we cannot use common_prefixes at all because matching
247            // Concatenation([Constant("./explicit-"), Dynamic]) results in the constant prefix
248            // "./explicit-" would not match the exact map entry "./explicit-a" (it's not a prefix).
249            self.map
250                .iter()
251                .filter_map(|(p, tree)| {
252                    let s = match String::from_utf8(p) {
253                        Ok(s) => s,
254                        Err(e) => {
255                            let valid_up_to = e.utf8_error().valid_up_to();
256                            let mut p = e.into_bytes();
257                            p.drain(valid_up_to..);
258                            String::from_utf8(p).unwrap()
259                        }
260                    };
261                    if prefix_predicate(&s) {
262                        Some((Cow::Owned(s), tree))
263                    } else {
264                        None
265                    }
266                })
267                .collect::<Vec<_>>()
268        };
269
270        // `prefixes_stack` is now a prefiltered list of potential matches. `AliasMapLookupIterator`
271        // internally will perform a final check if an entry matches or not
272
273        AliasMapLookupIterator {
274            request,
275            current_prefix_iterator: prefixes_stack
276                .pop()
277                .map(|(prefix, map)| (prefix, map.iter())),
278            prefixes_stack,
279        }
280    }
281
282    /// Inserts a new alias into the map.
283    ///
284    /// If the map did not have this alias already, `None` is returned.
285    ///
286    /// If the map had this alias, the template is updated, and the old template
287    /// is returned.
288    pub fn insert(&mut self, pattern: AliasPattern, template: T) -> Option<T> {
289        let (prefix_key, alias_key, value) = match pattern {
290            AliasPattern::Exact(exact) => (exact, AliasKey::Exact, template),
291            AliasPattern::Wildcard { prefix, suffix } => {
292                (prefix, AliasKey::Wildcard { suffix }, template)
293            }
294        };
295        // NOTE(alexkirsz) patricia_tree doesn't implement std's `Entry` API,
296        // where we could do:
297        // self.trie
298        //     .entry(key.into())
299        //     .or_insert_with(BTreeSet::new)
300        //     .insert(value)
301        if let Some(map) = self.map.get_mut(&prefix_key) {
302            map.insert(alias_key, value)
303        } else {
304            let mut map = BTreeMap::new();
305            map.insert(alias_key, value);
306            self.map.insert(prefix_key, map);
307            None
308        }
309    }
310}
311
312impl<T> IntoIterator for AliasMap<T> {
313    type Item = (AliasPattern, T);
314
315    type IntoIter = AliasMapIntoIter<T>;
316
317    fn into_iter(self) -> Self::IntoIter {
318        AliasMapIntoIter {
319            iter: self.map.into_iter(),
320            current_prefix_iterator: None,
321        }
322    }
323}
324
325impl<'a, T> IntoIterator for &'a AliasMap<T> {
326    type Item = (AliasPattern, &'a T);
327
328    type IntoIter = AliasMapIter<'a, T>;
329
330    fn into_iter(self) -> Self::IntoIter {
331        AliasMapIter {
332            iter: self.map.iter(),
333            current_prefix_iterator: None,
334        }
335    }
336}
337
338/// An owning iterator over the entries of an `AliasMap`.
339///
340/// Beware: The items are *NOT* returned in the order defined by
341/// [PATTERN_KEY_COMPARE].
342///
343/// [PATTERN_KEY_COMPARE]: https://nodejs.org/api/esm.html#resolver-algorithm-specification
344pub struct AliasMapIntoIter<T> {
345    iter: patricia_tree::map::IntoIter<Vec<u8>, BTreeMap<AliasKey, T>>,
346    current_prefix_iterator: Option<AliasMapIntoIterItem<T>>,
347}
348
349struct AliasMapIntoIterItem<T> {
350    prefix: RcStr,
351    iterator: std::collections::btree_map::IntoIter<AliasKey, T>,
352}
353
354impl<T> AliasMapIntoIter<T> {
355    fn advance_iter(&mut self) -> Option<&mut AliasMapIntoIterItem<T>> {
356        let (prefix, map) = self.iter.next()?;
357        let prefix = String::from_utf8(prefix)
358            .expect("invalid UTF-8 key in AliasMap")
359            .into();
360        self.current_prefix_iterator = Some(AliasMapIntoIterItem {
361            prefix,
362            iterator: map.into_iter(),
363        });
364        self.current_prefix_iterator.as_mut()
365    }
366}
367
368impl<T> Iterator for AliasMapIntoIter<T> {
369    type Item = (AliasPattern, T);
370
371    fn next(&mut self) -> Option<Self::Item> {
372        let mut current_prefix_iterator = match self.current_prefix_iterator {
373            None => self.advance_iter()?,
374            Some(ref mut current_prefix_iterator) => current_prefix_iterator,
375        };
376        let mut current_value = current_prefix_iterator.iterator.next();
377        loop {
378            match current_value {
379                None => {
380                    current_prefix_iterator = self.advance_iter()?;
381                    current_value = current_prefix_iterator.iterator.next();
382                }
383                Some(current_value) => {
384                    return Some(match current_value {
385                        (AliasKey::Exact, value) => (
386                            AliasPattern::Exact(current_prefix_iterator.prefix.clone()),
387                            value,
388                        ),
389                        (AliasKey::Wildcard { suffix }, value) => (
390                            AliasPattern::Wildcard {
391                                prefix: current_prefix_iterator.prefix.clone(),
392                                suffix,
393                            },
394                            value,
395                        ),
396                    });
397                }
398            }
399        }
400    }
401}
402
403/// A borrowing iterator over the entries of an `AliasMap`.
404///
405/// Beware: The items are *NOT* returned in the order defined by
406/// [PATTERN_KEY_COMPARE].
407///
408/// [PATTERN_KEY_COMPARE]: https://nodejs.org/api/esm.html#resolver-algorithm-specification
409pub struct AliasMapIter<'a, T> {
410    iter: patricia_tree::map::Iter<'a, Vec<u8>, BTreeMap<AliasKey, T>>,
411    current_prefix_iterator: Option<AliasMapIterItem<'a, T>>,
412}
413
414struct AliasMapIterItem<'a, T> {
415    prefix: RcStr,
416    iterator: std::collections::btree_map::Iter<'a, AliasKey, T>,
417}
418
419impl<T> AliasMapIter<'_, T> {
420    fn advance_iter(&mut self) -> bool {
421        let Some((prefix, map)) = self.iter.next() else {
422            return false;
423        };
424        let prefix = String::from_utf8(prefix)
425            .expect("invalid UTF-8 key in AliasMap")
426            .into();
427        self.current_prefix_iterator = Some(AliasMapIterItem {
428            prefix,
429            iterator: map.iter(),
430        });
431        true
432    }
433}
434
435impl<'a, T> Iterator for AliasMapIter<'a, T> {
436    type Item = (AliasPattern, &'a T);
437
438    fn next(&mut self) -> Option<Self::Item> {
439        let (current_prefix_iterator, current_value) = loop {
440            let Some(current_prefix_iterator) = &mut self.current_prefix_iterator else {
441                if !self.advance_iter() {
442                    return None;
443                }
444                continue;
445            };
446            if let Some(current_value) = current_prefix_iterator.iterator.next() {
447                break (&*current_prefix_iterator, current_value);
448            }
449            self.current_prefix_iterator = None;
450            continue;
451        };
452        Some(match current_value {
453            (AliasKey::Exact, value) => (
454                AliasPattern::Exact(current_prefix_iterator.prefix.clone()),
455                value,
456            ),
457            (AliasKey::Wildcard { suffix }, value) => (
458                AliasPattern::Wildcard {
459                    prefix: current_prefix_iterator.prefix.clone(),
460                    suffix: suffix.clone(),
461                },
462                value,
463            ),
464        })
465    }
466}
467
468impl<T> Extend<(AliasPattern, T)> for AliasMap<T> {
469    fn extend<It>(&mut self, iter: It)
470    where
471        It: IntoIterator<Item = (AliasPattern, T)>,
472    {
473        for (pattern, value) in iter {
474            self.insert(pattern, value);
475        }
476    }
477}
478
479/// An iterator over the aliases that match a request.
480///
481/// The items are returned in the order defined by [PATTERN_KEY_COMPARE].
482///
483/// [PATTERN_KEY_COMPARE]: https://nodejs.org/api/esm.html#resolution-algorithm-specification
484pub struct AliasMapLookupIterator<'a, T> {
485    request: &'a Pattern,
486    prefixes_stack: Vec<(Cow<'a, str>, &'a BTreeMap<AliasKey, T>)>,
487    current_prefix_iterator: Option<(
488        Cow<'a, str>,
489        std::collections::btree_map::Iter<'a, AliasKey, T>,
490    )>,
491}
492
493impl<'a, T> Iterator for AliasMapLookupIterator<'a, T>
494where
495    T: AliasTemplate + Clone,
496{
497    type Item = Result<AliasMatch<'a, T>>;
498
499    fn next(&mut self) -> Option<Self::Item> {
500        let (prefix, current_prefix_iterator) = self.current_prefix_iterator.as_mut()?;
501
502        loop {
503            for (key, template) in &mut *current_prefix_iterator {
504                match key {
505                    AliasKey::Exact => {
506                        if self.request.is_match(prefix) {
507                            return Some(Ok(AliasMatch {
508                                prefix: prefix.clone(),
509                                key,
510                                output: template.convert(),
511                            }));
512                        }
513                    }
514                    AliasKey::Wildcard { suffix } => {
515                        // This is quite messy as we'd have to match against the FS to do this
516                        // properly. For now, try to support as many cases as possible (and as are
517                        // actually used).
518
519                        let is_match = if let Some(request) = self.request.as_constant_string() {
520                            // The request is a constant string, so the PatriciaMap lookup already
521                            // ensured that the prefix is matching the request.
522                            let remaining = &request[prefix.len()..];
523                            remaining.ends_with(&**suffix)
524                        } else if let Pattern::Concatenation(req) = self.request
525                            && let [
526                                Pattern::Constant(req_prefix),
527                                Pattern::Dynamic | Pattern::DynamicNoSlash,
528                            ] = req.as_slice()
529                        {
530                            // This and the following special case for commonly used subdir aliases
531                            // correspond to what Pattern::match_apply_template can achieve as well.
532
533                            // The request might be more specific than the mapping, e.g. for
534                            // `require('@/foo/' + dyn)` into a `@/*` mapping
535                            req_prefix.starts_with(&**prefix)
536                        } else if let Pattern::Concatenation(req) = self.request
537                            && let [
538                                Pattern::Constant(req_prefix),
539                                Pattern::Dynamic | Pattern::DynamicNoSlash,
540                                Pattern::Constant(req_suffix),
541                            ] = req.as_slice()
542                        {
543                            req_prefix.starts_with(&**prefix) && req_suffix.ends_with(&**suffix)
544                        } else if !self.request.could_match(prefix) {
545                            // There's no way it could match if the prefix can't match.
546                            false
547                        } else if suffix.is_empty() {
548                            // Prefix matches the request, and suffix is empty.
549                            true
550                        } else {
551                            // It may or may not match, throw an error.
552                            return Some(Err(anyhow::anyhow!(
553                                "Complex patterns into wildcard exports fields are not \
554                                 implemented yet: {} into '{}*{}'",
555                                self.request.describe_as_string(),
556                                prefix,
557                                suffix,
558                            )));
559                        };
560
561                        if is_match {
562                            let mut remaining = self.request.clone();
563                            if let Err(e) = remaining.strip_prefix_len(prefix.len()) {
564                                return Some(Err(e.context(self.request.describe_as_string())));
565                            }
566                            remaining.strip_suffix_len(suffix.len());
567
568                            let output = template.replace(&remaining);
569                            return Some(Ok(AliasMatch {
570                                prefix: prefix.clone(),
571                                key,
572                                output,
573                            }));
574                        }
575                    }
576                }
577            }
578
579            let (new_prefix, new_current_prefix_iterator) = self.prefixes_stack.pop()?;
580            *prefix = new_prefix;
581            *current_prefix_iterator = new_current_prefix_iterator.iter();
582        }
583    }
584}
585
586/// An alias pattern commonly used for import paths. This should support [the functionality used in
587/// Typescript's tsconfig file][tsconfig].
588///
589/// [tsconfig]: https://www.typescriptlang.org/tsconfig/#paths
590#[derive(Debug, Serialize, Deserialize, Clone, PartialEq, Eq)]
591pub enum AliasPattern {
592    /// Will match an exact string.
593    Exact(RcStr),
594    /// Will match a pattern with a single wildcard.
595    Wildcard { prefix: RcStr, suffix: RcStr },
596}
597
598impl AliasPattern {
599    /// Parses an alias pattern from a string.
600    ///
601    /// Wildcard characters (*) present in the string will match any number of
602    /// characters, including path separators.
603    pub fn parse<'a, T>(pattern: T) -> Self
604    where
605        T: Into<RcStr> + 'a,
606    {
607        let pattern = pattern.into();
608        if let Some(wildcard_index) = pattern.find('*') {
609            let mut pattern = pattern.into_owned();
610
611            let suffix = pattern[wildcard_index + 1..].into();
612            pattern.truncate(wildcard_index);
613            AliasPattern::Wildcard {
614                prefix: pattern.into(),
615                suffix,
616            }
617        } else {
618            AliasPattern::Exact(pattern)
619        }
620    }
621
622    /// Creates a pattern that will only match exactly what was passed in.
623    pub fn exact<'a, T>(pattern: T) -> Self
624    where
625        T: Into<RcStr> + 'a,
626    {
627        AliasPattern::Exact(pattern.into())
628    }
629
630    /// Creates a pattern that will match, sequentially:
631    /// 1. a prefix; then
632    /// 2. any number of characters, including path separators; then
633    /// 3. a suffix.
634    pub fn wildcard<'p, 's, P, S>(prefix: P, suffix: S) -> Self
635    where
636        P: Into<RcStr> + 'p,
637        S: Into<RcStr> + 's,
638    {
639        AliasPattern::Wildcard {
640            prefix: prefix.into(),
641            suffix: suffix.into(),
642        }
643    }
644}
645
646#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize, TraceRawVcs, NonLocalValue)]
647pub enum AliasKey {
648    Exact,
649    Wildcard { suffix: RcStr },
650}
651
652/// Result of a lookup in the alias map.
653#[derive(Debug, PartialEq, Clone)]
654pub struct AliasMatch<'a, T>
655where
656    T: AliasTemplate + Clone + 'a,
657{
658    pub prefix: Cow<'a, str>,
659    pub key: &'a AliasKey,
660    pub output: T::Output<'a>,
661}
662
663impl PartialOrd for AliasKey {
664    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
665        Some(self.cmp(other))
666    }
667}
668
669impl Ord for AliasKey {
670    /// According to [PATTERN_KEY_COMPARE].
671    ///
672    /// [PATTERN_KEY_COMPARE]: https://nodejs.org/api/esm.html#resolver-algorithm-specification
673    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
674        match (self, other) {
675            (AliasKey::Wildcard { suffix: l_suffix }, AliasKey::Wildcard { suffix: r_suffix }) => {
676                l_suffix
677                    .len()
678                    .cmp(&r_suffix.len())
679                    .reverse()
680                    .then_with(|| l_suffix.cmp(r_suffix))
681            }
682            (AliasKey::Wildcard { .. }, _) => std::cmp::Ordering::Less,
683            (_, AliasKey::Wildcard { .. }) => std::cmp::Ordering::Greater,
684            _ => std::cmp::Ordering::Equal,
685        }
686    }
687}
688
689/// A trait for types that can be used as a template for an alias.
690pub trait AliasTemplate {
691    /// The type of the output of the replacement.
692    type Output<'a>
693    where
694        Self: 'a;
695
696    /// Turn `self` into a `Self::Output`
697    fn convert(&self) -> Self::Output<'_>;
698
699    /// Replaces `capture` within `self`.
700    fn replace<'a>(&'a self, capture: &Pattern) -> Self::Output<'a>;
701}
702
703#[cfg(test)]
704mod test {
705    use core::assert_matches;
706
707    use anyhow::Result;
708    use turbo_rcstr::rcstr;
709
710    use super::{AliasMap, AliasPattern, AliasTemplate};
711    use crate::resolve::{alias_map::AliasKey, pattern::Pattern};
712
713    /// Asserts that an [`AliasMap`] lookup yields the expected results. The
714    /// order of the results is important.
715    ///
716    /// See below for usage examples.
717    macro_rules! assert_alias_matches {
718        ($map:expr, $request:expr$(, $($tail:tt)*)?) => {
719            let request = Pattern::Constant($request.into());
720            let mut lookup = $map.lookup(&request);
721
722            $(assert_alias_matches!(@next lookup, $($tail)*);)?
723            assert_matches!(lookup.next(), None);
724        };
725
726        (@next $lookup:ident, exact($pattern:expr)$(, $($tail:tt)*)?) => {
727            match $lookup.next().unwrap().unwrap() {
728                super::AliasMatch{key: super::AliasKey::Exact, output: Pattern::Constant(c), ..} if c == $pattern => {}
729                m => panic!("unexpected match {:?}", m),
730            }
731            $(assert_alias_matches!(@next $lookup, $($tail)*);)?
732        };
733
734        (@next $lookup:ident, replaced($pattern:expr)$(, $($tail:tt)*)?) => {
735            match $lookup.next().unwrap().unwrap() {
736                super::AliasMatch{key: super::AliasKey::Wildcard{..}, output: Pattern::Constant(c), ..} if c == $pattern => {}
737                m => panic!("unexpected match {:?}", m),
738            }
739            $(assert_alias_matches!(@next $lookup, $($tail)*);)?
740        };
741
742        (@next $lookup:ident, replaced_owned($value:expr)$(, $($tail:tt)*)?) => {
743            match $lookup.next().unwrap().unwrap() {
744                super::AliasMatch{key: super::AliasKey::Wildcard{..}, output: Pattern::Constant(c), ..} if c == $value => {}
745                m => panic!("unexpected match {:?}", m),
746            }
747            $(assert_alias_matches!(@next $lookup, $($tail)*);)?
748        };
749
750        // Handle trailing comma.
751        (@next $lookup:ident,) => {};
752    }
753
754    impl<'a> AliasTemplate for &'a str {
755        type Output<'b>
756            = Pattern
757        where
758            Self: 'b;
759
760        fn replace(&self, capture: &Pattern) -> Self::Output<'a> {
761            capture.spread_into_star(self)
762        }
763
764        fn convert(&self) -> Self::Output<'a> {
765            Pattern::Constant(self.to_string().into())
766        }
767    }
768
769    #[test]
770    fn test_one_exact() {
771        let mut map = AliasMap::new();
772        map.insert(AliasPattern::parse("foo"), "bar");
773
774        assert_alias_matches!(map, "");
775        assert_alias_matches!(map, "foo", exact("bar"));
776        assert_alias_matches!(map, "foobar");
777    }
778
779    #[test]
780    fn test_many_exact() {
781        let mut map = AliasMap::new();
782        map.insert(AliasPattern::parse("foo"), "bar");
783        map.insert(AliasPattern::parse("bar"), "foo");
784        map.insert(AliasPattern::parse("foobar"), "barfoo");
785
786        assert_alias_matches!(map, "");
787        assert_alias_matches!(map, "foo", exact("bar"));
788        assert_alias_matches!(map, "bar", exact("foo"));
789        assert_alias_matches!(map, "foobar", exact("barfoo"));
790    }
791
792    #[test]
793    fn test_empty() {
794        let mut map = AliasMap::new();
795        map.insert(AliasPattern::parse(""), "empty");
796        map.insert(AliasPattern::parse("foo"), "bar");
797
798        assert_alias_matches!(map, "", exact("empty"));
799        assert_alias_matches!(map, "foo", exact("bar"));
800    }
801
802    #[test]
803    fn test_left_wildcard() {
804        let mut map = AliasMap::new();
805        map.insert(AliasPattern::parse("foo*"), "bar");
806
807        assert_alias_matches!(map, "");
808        assert_alias_matches!(map, "foo", replaced("bar"));
809        assert_alias_matches!(map, "foobar", replaced("bar"));
810    }
811
812    #[test]
813    fn test_wildcard_replace_suffix() {
814        let mut map = AliasMap::new();
815        map.insert(AliasPattern::parse("foo*"), "bar*");
816        map.insert(AliasPattern::parse("foofoo*"), "barbar*");
817
818        assert_alias_matches!(map, "");
819        assert_alias_matches!(map, "foo", replaced_owned("bar"));
820        assert_alias_matches!(map, "foobar", replaced_owned("barbar"));
821        assert_alias_matches!(
822            map,
823            "foofoobar",
824            // The longer prefix should come first.
825            replaced_owned("barbarbar"),
826            replaced_owned("barfoobar"),
827        );
828    }
829
830    #[test]
831    fn test_wildcard_replace_prefix() {
832        let mut map = AliasMap::new();
833        map.insert(AliasPattern::parse("*foo"), "*bar");
834        map.insert(AliasPattern::parse("*foofoo"), "*barbar");
835
836        assert_alias_matches!(map, "");
837        assert_alias_matches!(map, "foo", replaced_owned("bar"));
838        assert_alias_matches!(map, "barfoo", replaced_owned("barbar"));
839        assert_alias_matches!(
840            map,
841            "barfoofoo",
842            // The longer suffix should come first.
843            replaced_owned("barbarbar"),
844            replaced_owned("barfoobar"),
845        );
846    }
847
848    #[test]
849    fn test_wildcard_replace_infix() {
850        let mut map = AliasMap::new();
851        map.insert(AliasPattern::parse("foo*foo"), "bar*bar");
852        map.insert(AliasPattern::parse("foo*foofoo"), "bar*barbar");
853        map.insert(AliasPattern::parse("foofoo*foo"), "bazbaz*baz");
854
855        assert_alias_matches!(map, "");
856        assert_alias_matches!(map, "foo");
857        assert_alias_matches!(map, "foofoo", replaced_owned("barbar"));
858        assert_alias_matches!(map, "foobazfoo", replaced_owned("barbazbar"));
859        assert_alias_matches!(
860            map,
861            "foofoofoo",
862            // The longer prefix should come first.
863            replaced_owned("bazbazbaz"),
864            // Then the longer suffix.
865            replaced_owned("barbarbar"),
866            replaced_owned("barfoobar"),
867        );
868        assert_alias_matches!(
869            map,
870            "foobazfoofoo",
871            // The longer suffix should come first.
872            replaced_owned("barbazbarbar"),
873            replaced_owned("barbazfoobar"),
874        );
875        assert_alias_matches!(
876            map,
877            "foofoobarfoo",
878            // The longer prefix should come first.
879            replaced_owned("bazbazbarbaz"),
880            replaced_owned("barfoobarbar"),
881        );
882        assert_alias_matches!(
883            map,
884            "foofoofoofoofoo",
885            // The longer prefix should come first.
886            replaced_owned("bazbazfoofoobaz"),
887            // Then the longer suffix.
888            replaced_owned("barfoofoobarbar"),
889            replaced_owned("barfoofoofoobar"),
890        );
891    }
892
893    #[test]
894    fn test_wildcard_replace_only() {
895        let mut map = AliasMap::new();
896        map.insert(AliasPattern::parse("*"), "foo*foo");
897        map.insert(AliasPattern::parse("**"), "bar*foo");
898
899        assert_alias_matches!(map, "", replaced_owned("foofoo"));
900        assert_alias_matches!(map, "bar", replaced_owned("foobarfoo"));
901        assert_alias_matches!(
902            map,
903            "*",
904            replaced_owned("barfoo"),
905            replaced_owned("foo*foo"),
906        );
907        assert_alias_matches!(
908            map,
909            "**",
910            replaced_owned("bar*foo"),
911            replaced_owned("foo**foo")
912        );
913    }
914
915    #[test]
916    fn test_pattern() {
917        let mut map = AliasMap::new();
918        map.insert(AliasPattern::parse("card/*"), "src/cards/*");
919        map.insert(AliasPattern::parse("comp/*/x"), "src/comps/*/x");
920        map.insert(AliasPattern::parse("head/*/x"), "src/heads/*");
921
922        assert_eq!(
923            map.lookup(&Pattern::Concatenation(vec![
924                Pattern::Constant(rcstr!("card/")),
925                Pattern::Dynamic
926            ]))
927            .collect::<Result<Vec<_>>>()
928            .unwrap(),
929            vec![super::AliasMatch {
930                prefix: "card/".into(),
931                key: &super::AliasKey::Wildcard { suffix: rcstr!("") },
932                output: Pattern::Concatenation(vec![
933                    Pattern::Constant(rcstr!("src/cards/")),
934                    Pattern::Dynamic
935                ]),
936            }]
937        );
938        assert_eq!(
939            map.lookup(&Pattern::Concatenation(vec![
940                Pattern::Constant(rcstr!("comp/")),
941                Pattern::Dynamic,
942                Pattern::Constant(rcstr!("/x")),
943            ]))
944            .collect::<Result<Vec<_>>>()
945            .unwrap(),
946            vec![super::AliasMatch {
947                prefix: "comp/".into(),
948                key: &super::AliasKey::Wildcard {
949                    suffix: rcstr!("/x")
950                },
951                output: Pattern::Concatenation(vec![
952                    Pattern::Constant(rcstr!("src/comps/")),
953                    Pattern::Dynamic,
954                    Pattern::Constant(rcstr!("/x")),
955                ]),
956            }]
957        );
958        assert_eq!(
959            map.lookup(&Pattern::Concatenation(vec![
960                Pattern::Constant(rcstr!("head/")),
961                Pattern::Dynamic,
962                Pattern::Constant(rcstr!("/x")),
963            ]))
964            .collect::<Result<Vec<_>>>()
965            .unwrap(),
966            vec![super::AliasMatch {
967                prefix: "head/".into(),
968                key: &super::AliasKey::Wildcard {
969                    suffix: rcstr!("/x")
970                },
971                output: Pattern::Concatenation(vec![
972                    Pattern::Constant(rcstr!("src/heads/")),
973                    Pattern::Dynamic,
974                ]),
975            }]
976        );
977    }
978
979    #[test]
980    fn test_pattern_very_dynamic() {
981        let mut map = AliasMap::new();
982        // map.insert(AliasPattern::parse("foo-*"), "src/foo/*");
983        map.insert(AliasPattern::parse("bar-a"), "src/bar/a");
984        map.insert(AliasPattern::parse("bar-b"), "src/bar/b");
985
986        // TODO requesting `<dynamic>bar-a` from an exports map containing a wildcard is not
987        // implemented currently
988        // assert_eq!(
989        //     map.lookup(&Pattern::Concatenation(vec![
990        //         Pattern::Constant(rcstr!("foo-")),
991        //         Pattern::Dynamic,
992        //     ]))
993        //     .collect::<Vec<_>>(),
994        //     vec![super::AliasMatch {
995        //         prefix: "foo-".into(),
996        //         key: &super::AliasKey::Wildcard { suffix: rcstr!("") },
997        //         output: Pattern::Concatenation(vec![
998        //             Pattern::Constant(rcstr!("src/foo/")),
999        //             Pattern::Dynamic,
1000        //         ]),
1001        //     }]
1002        // );
1003
1004        assert_eq!(
1005            map.lookup(&Pattern::Concatenation(vec![
1006                Pattern::Dynamic,
1007                Pattern::Constant(rcstr!("bar-a")),
1008            ]))
1009            .collect::<Result<Vec<_>>>()
1010            .unwrap(),
1011            vec![super::AliasMatch {
1012                prefix: "bar-a".into(),
1013                key: &AliasKey::Exact,
1014                output: Pattern::Constant(rcstr!("src/bar/a"))
1015            }]
1016        );
1017        assert_eq!(
1018            map.lookup(&Pattern::Concatenation(vec![
1019                Pattern::Constant(rcstr!("bar-")),
1020                Pattern::Dynamic,
1021            ]))
1022            .collect::<Result<Vec<_>>>()
1023            .unwrap(),
1024            vec![
1025                super::AliasMatch {
1026                    prefix: "bar-b".into(),
1027                    key: &AliasKey::Exact,
1028                    output: Pattern::Constant(rcstr!("src/bar/b"))
1029                },
1030                super::AliasMatch {
1031                    prefix: "bar-a".into(),
1032                    key: &AliasKey::Exact,
1033                    output: Pattern::Constant(rcstr!("src/bar/a"))
1034                }
1035            ]
1036        );
1037    }
1038}
turbopack_core/resolve/alias_map.rs

turbopack_core/resolve/
alias_map.rs
