turbopack_core/resolve/
alias_map.rs

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

turbopack_core/resolve/
alias_map.rs
