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

turbopack_core/resolve/
alias_map.rs
