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

turbopack_core/resolve/
alias_map.rs
