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                        let is_match = if let Some(request) = self.request.as_constant_string() {
566                            // The request is a constant string, so the PatriciaMap lookup already
567                            // ensured that the prefix is matching the request.
568                            let remaining = &request[prefix.len()..];
569                            remaining.ends_with(&**suffix)
570                        } else if let Pattern::Concatenation(req) = self.request
571                            && let [
572                                Pattern::Constant(req_prefix),
573                                Pattern::Dynamic | Pattern::DynamicNoSlash,
574                            ] = req.as_slice()
575                        {
576                            // This and the following special case for commonly used subdir aliases
577                            // correspond to what Pattern::match_apply_template can achieve as well.
578
579                            // The request might be more specific than the mapping, e.g. for
580                            // `require('@/foo/' + dyn)` into a `@/*` mapping
581                            req_prefix.starts_with(&**prefix)
582                        } else if let Pattern::Concatenation(req) = self.request
583                            && let [
584                                Pattern::Constant(req_prefix),
585                                Pattern::Dynamic | Pattern::DynamicNoSlash,
586                                Pattern::Constant(req_suffix),
587                            ] = req.as_slice()
588                        {
589                            req_prefix.starts_with(&**prefix) && req_suffix.ends_with(&**suffix)
590                        } else {
591                            return Some(Err(anyhow::anyhow!(
592                                "complex patterns into wildcard exports fields are not \
593                                 implemented yet: {} into '{}*{}'",
594                                self.request.describe_as_string(),
595                                prefix,
596                                suffix,
597                            )));
598                        };
599
600                        if is_match {
601                            let mut remaining = self.request.clone();
602                            remaining.strip_prefix_len(prefix.len());
603                            remaining.strip_suffix_len(suffix.len());
604
605                            let output = template.replace(&remaining);
606                            return Some(Ok(AliasMatch {
607                                prefix: prefix.clone(),
608                                key,
609                                output,
610                            }));
611                        }
612                    }
613                }
614            }
615
616            let (new_prefix, new_current_prefix_iterator) = self.prefixes_stack.pop()?;
617            *prefix = new_prefix;
618            *current_prefix_iterator = new_current_prefix_iterator.iter();
619        }
620    }
621}
622
623/// An alias pattern.
624#[derive(Debug, Serialize, Deserialize, Clone, PartialEq, Eq)]
625pub enum AliasPattern {
626    /// Will match an exact string.
627    Exact(RcStr),
628    /// Will match a pattern with a single wildcard.
629    Wildcard { prefix: RcStr, suffix: RcStr },
630}
631
632impl AliasPattern {
633    /// Parses an alias pattern from a string.
634    ///
635    /// Wildcard characters (*) present in the string will match any number of
636    /// characters, including path separators.
637    pub fn parse<'a, T>(pattern: T) -> Self
638    where
639        T: Into<RcStr> + 'a,
640    {
641        let pattern = pattern.into();
642        if let Some(wildcard_index) = pattern.find('*') {
643            let mut pattern = pattern.into_owned();
644
645            let suffix = pattern[wildcard_index + 1..].into();
646            pattern.truncate(wildcard_index);
647            AliasPattern::Wildcard {
648                prefix: pattern.into(),
649                suffix,
650            }
651        } else {
652            AliasPattern::Exact(pattern)
653        }
654    }
655
656    /// Creates a pattern that will only match exactly what was passed in.
657    pub fn exact<'a, T>(pattern: T) -> Self
658    where
659        T: Into<RcStr> + 'a,
660    {
661        AliasPattern::Exact(pattern.into())
662    }
663
664    /// Creates a pattern that will match, sequentially:
665    /// 1. a prefix; then
666    /// 2. any number of characters, including path separators; then
667    /// 3. a suffix.
668    pub fn wildcard<'p, 's, P, S>(prefix: P, suffix: S) -> Self
669    where
670        P: Into<RcStr> + 'p,
671        S: Into<RcStr> + 's,
672    {
673        AliasPattern::Wildcard {
674            prefix: prefix.into(),
675            suffix: suffix.into(),
676        }
677    }
678}
679
680#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize, TraceRawVcs, NonLocalValue)]
681pub enum AliasKey {
682    Exact,
683    Wildcard { suffix: RcStr },
684}
685
686/// Result of a lookup in the alias map.
687#[derive(Debug, PartialEq, Clone)]
688pub struct AliasMatch<'a, T>
689where
690    T: AliasTemplate + Clone + 'a,
691{
692    pub prefix: Cow<'a, str>,
693    pub key: &'a AliasKey,
694    pub output: T::Output<'a>,
695}
696
697impl PartialOrd for AliasKey {
698    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
699        Some(self.cmp(other))
700    }
701}
702
703impl Ord for AliasKey {
704    /// According to [PATTERN_KEY_COMPARE].
705    ///
706    /// [PATTERN_KEY_COMPARE]: https://nodejs.org/api/esm.html#resolver-algorithm-specification
707    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
708        match (self, other) {
709            (AliasKey::Wildcard { suffix: l_suffix }, AliasKey::Wildcard { suffix: r_suffix }) => {
710                l_suffix
711                    .len()
712                    .cmp(&r_suffix.len())
713                    .reverse()
714                    .then_with(|| l_suffix.cmp(r_suffix))
715            }
716            (AliasKey::Wildcard { .. }, _) => std::cmp::Ordering::Less,
717            (_, AliasKey::Wildcard { .. }) => std::cmp::Ordering::Greater,
718            _ => std::cmp::Ordering::Equal,
719        }
720    }
721}
722
723/// A trait for types that can be used as a template for an alias.
724pub trait AliasTemplate {
725    /// The type of the output of the replacement.
726    type Output<'a>
727    where
728        Self: 'a;
729
730    /// Turn `self` into a `Self::Output`
731    fn convert(&self) -> Self::Output<'_>;
732
733    /// Replaces `capture` within `self`.
734    fn replace<'a>(&'a self, capture: &Pattern) -> Self::Output<'a>;
735}
736
737#[cfg(test)]
738mod test {
739    use std::assert_matches::assert_matches;
740
741    use anyhow::Result;
742    use turbo_rcstr::rcstr;
743
744    use super::{AliasMap, AliasPattern, AliasTemplate};
745    use crate::resolve::{alias_map::AliasKey, pattern::Pattern};
746
747    /// Asserts that an [`AliasMap`] lookup yields the expected results. The
748    /// order of the results is important.
749    ///
750    /// See below for usage examples.
751    macro_rules! assert_alias_matches {
752        ($map:expr, $request:expr$(, $($tail:tt)*)?) => {
753            let request = Pattern::Constant($request.into());
754            let mut lookup = $map.lookup(&request);
755
756            $(assert_alias_matches!(@next lookup, $($tail)*);)?
757            assert_matches!(lookup.next(), None);
758        };
759
760        (@next $lookup:ident, exact($pattern:expr)$(, $($tail:tt)*)?) => {
761            match $lookup.next().unwrap().unwrap() {
762                super::AliasMatch{key: super::AliasKey::Exact, output: Pattern::Constant(c), ..} if c == $pattern => {}
763                m => panic!("unexpected match {:?}", m),
764            }
765            $(assert_alias_matches!(@next $lookup, $($tail)*);)?
766        };
767
768        (@next $lookup:ident, replaced($pattern:expr)$(, $($tail:tt)*)?) => {
769            match $lookup.next().unwrap().unwrap() {
770                super::AliasMatch{key: super::AliasKey::Wildcard{..}, output: Pattern::Constant(c), ..} if c == $pattern => {}
771                m => panic!("unexpected match {:?}", m),
772            }
773            $(assert_alias_matches!(@next $lookup, $($tail)*);)?
774        };
775
776        (@next $lookup:ident, replaced_owned($value:expr)$(, $($tail:tt)*)?) => {
777            match $lookup.next().unwrap().unwrap() {
778                super::AliasMatch{key: super::AliasKey::Wildcard{..}, output: Pattern::Constant(c), ..} if c == $value => {}
779                m => panic!("unexpected match {:?}", m),
780            }
781            $(assert_alias_matches!(@next $lookup, $($tail)*);)?
782        };
783
784        // Handle trailing comma.
785        (@next $lookup:ident,) => {};
786    }
787
788    impl<'a> AliasTemplate for &'a str {
789        type Output<'b>
790            = Pattern
791        where
792            Self: 'b;
793
794        fn replace(&self, capture: &Pattern) -> Self::Output<'a> {
795            capture.spread_into_star(self)
796        }
797
798        fn convert(&self) -> Self::Output<'a> {
799            Pattern::Constant(self.to_string().into())
800        }
801    }
802
803    #[test]
804    fn test_one_exact() {
805        let mut map = AliasMap::new();
806        map.insert(AliasPattern::parse("foo"), "bar");
807
808        assert_alias_matches!(map, "");
809        assert_alias_matches!(map, "foo", exact("bar"));
810        assert_alias_matches!(map, "foobar");
811    }
812
813    #[test]
814    fn test_many_exact() {
815        let mut map = AliasMap::new();
816        map.insert(AliasPattern::parse("foo"), "bar");
817        map.insert(AliasPattern::parse("bar"), "foo");
818        map.insert(AliasPattern::parse("foobar"), "barfoo");
819
820        assert_alias_matches!(map, "");
821        assert_alias_matches!(map, "foo", exact("bar"));
822        assert_alias_matches!(map, "bar", exact("foo"));
823        assert_alias_matches!(map, "foobar", exact("barfoo"));
824    }
825
826    #[test]
827    fn test_empty() {
828        let mut map = AliasMap::new();
829        map.insert(AliasPattern::parse(""), "empty");
830        map.insert(AliasPattern::parse("foo"), "bar");
831
832        assert_alias_matches!(map, "", exact("empty"));
833        assert_alias_matches!(map, "foo", exact("bar"));
834    }
835
836    #[test]
837    fn test_left_wildcard() {
838        let mut map = AliasMap::new();
839        map.insert(AliasPattern::parse("foo*"), "bar");
840
841        assert_alias_matches!(map, "");
842        assert_alias_matches!(map, "foo", replaced("bar"));
843        assert_alias_matches!(map, "foobar", replaced("bar"));
844    }
845
846    #[test]
847    fn test_wildcard_replace_suffix() {
848        let mut map = AliasMap::new();
849        map.insert(AliasPattern::parse("foo*"), "bar*");
850        map.insert(AliasPattern::parse("foofoo*"), "barbar*");
851
852        assert_alias_matches!(map, "");
853        assert_alias_matches!(map, "foo", replaced_owned("bar"));
854        assert_alias_matches!(map, "foobar", replaced_owned("barbar"));
855        assert_alias_matches!(
856            map,
857            "foofoobar",
858            // The longer prefix should come first.
859            replaced_owned("barbarbar"),
860            replaced_owned("barfoobar"),
861        );
862    }
863
864    #[test]
865    fn test_wildcard_replace_prefix() {
866        let mut map = AliasMap::new();
867        map.insert(AliasPattern::parse("*foo"), "*bar");
868        map.insert(AliasPattern::parse("*foofoo"), "*barbar");
869
870        assert_alias_matches!(map, "");
871        assert_alias_matches!(map, "foo", replaced_owned("bar"));
872        assert_alias_matches!(map, "barfoo", replaced_owned("barbar"));
873        assert_alias_matches!(
874            map,
875            "barfoofoo",
876            // The longer suffix should come first.
877            replaced_owned("barbarbar"),
878            replaced_owned("barfoobar"),
879        );
880    }
881
882    #[test]
883    fn test_wildcard_replace_infix() {
884        let mut map = AliasMap::new();
885        map.insert(AliasPattern::parse("foo*foo"), "bar*bar");
886        map.insert(AliasPattern::parse("foo*foofoo"), "bar*barbar");
887        map.insert(AliasPattern::parse("foofoo*foo"), "bazbaz*baz");
888
889        assert_alias_matches!(map, "");
890        assert_alias_matches!(map, "foo");
891        assert_alias_matches!(map, "foofoo", replaced_owned("barbar"));
892        assert_alias_matches!(map, "foobazfoo", replaced_owned("barbazbar"));
893        assert_alias_matches!(
894            map,
895            "foofoofoo",
896            // The longer prefix should come first.
897            replaced_owned("bazbazbaz"),
898            // Then the longer suffix.
899            replaced_owned("barbarbar"),
900            replaced_owned("barfoobar"),
901        );
902        assert_alias_matches!(
903            map,
904            "foobazfoofoo",
905            // The longer suffix should come first.
906            replaced_owned("barbazbarbar"),
907            replaced_owned("barbazfoobar"),
908        );
909        assert_alias_matches!(
910            map,
911            "foofoobarfoo",
912            // The longer prefix should come first.
913            replaced_owned("bazbazbarbaz"),
914            replaced_owned("barfoobarbar"),
915        );
916        assert_alias_matches!(
917            map,
918            "foofoofoofoofoo",
919            // The longer prefix should come first.
920            replaced_owned("bazbazfoofoobaz"),
921            // Then the longer suffix.
922            replaced_owned("barfoofoobarbar"),
923            replaced_owned("barfoofoofoobar"),
924        );
925    }
926
927    #[test]
928    fn test_wildcard_replace_only() {
929        let mut map = AliasMap::new();
930        map.insert(AliasPattern::parse("*"), "foo*foo");
931        map.insert(AliasPattern::parse("**"), "bar*foo");
932
933        assert_alias_matches!(map, "", replaced_owned("foofoo"));
934        assert_alias_matches!(map, "bar", replaced_owned("foobarfoo"));
935        assert_alias_matches!(
936            map,
937            "*",
938            replaced_owned("barfoo"),
939            replaced_owned("foo*foo"),
940        );
941        assert_alias_matches!(
942            map,
943            "**",
944            replaced_owned("bar*foo"),
945            replaced_owned("foo**foo")
946        );
947    }
948
949    #[test]
950    fn test_pattern() {
951        let mut map = AliasMap::new();
952        map.insert(AliasPattern::parse("card/*"), "src/cards/*");
953        map.insert(AliasPattern::parse("comp/*/x"), "src/comps/*/x");
954        map.insert(AliasPattern::parse("head/*/x"), "src/heads/*");
955
956        assert_eq!(
957            map.lookup(&Pattern::Concatenation(vec![
958                Pattern::Constant(rcstr!("card/")),
959                Pattern::Dynamic
960            ]))
961            .collect::<Result<Vec<_>>>()
962            .unwrap(),
963            vec![super::AliasMatch {
964                prefix: "card/".into(),
965                key: &super::AliasKey::Wildcard { suffix: rcstr!("") },
966                output: Pattern::Concatenation(vec![
967                    Pattern::Constant(rcstr!("src/cards/")),
968                    Pattern::Dynamic
969                ]),
970            }]
971        );
972        assert_eq!(
973            map.lookup(&Pattern::Concatenation(vec![
974                Pattern::Constant(rcstr!("comp/")),
975                Pattern::Dynamic,
976                Pattern::Constant(rcstr!("/x")),
977            ]))
978            .collect::<Result<Vec<_>>>()
979            .unwrap(),
980            vec![super::AliasMatch {
981                prefix: "comp/".into(),
982                key: &super::AliasKey::Wildcard {
983                    suffix: rcstr!("/x")
984                },
985                output: Pattern::Concatenation(vec![
986                    Pattern::Constant(rcstr!("src/comps/")),
987                    Pattern::Dynamic,
988                    Pattern::Constant(rcstr!("/x")),
989                ]),
990            }]
991        );
992        assert_eq!(
993            map.lookup(&Pattern::Concatenation(vec![
994                Pattern::Constant(rcstr!("head/")),
995                Pattern::Dynamic,
996                Pattern::Constant(rcstr!("/x")),
997            ]))
998            .collect::<Result<Vec<_>>>()
999            .unwrap(),
1000            vec![super::AliasMatch {
1001                prefix: "head/".into(),
1002                key: &super::AliasKey::Wildcard {
1003                    suffix: rcstr!("/x")
1004                },
1005                output: Pattern::Concatenation(vec![
1006                    Pattern::Constant(rcstr!("src/heads/")),
1007                    Pattern::Dynamic,
1008                ]),
1009            }]
1010        );
1011    }
1012
1013    #[test]
1014    fn test_pattern_very_dynamic() {
1015        let mut map = AliasMap::new();
1016        // map.insert(AliasPattern::parse("foo-*"), "src/foo/*");
1017        map.insert(AliasPattern::parse("bar-a"), "src/bar/a");
1018        map.insert(AliasPattern::parse("bar-b"), "src/bar/b");
1019
1020        // TODO requesting `<dynamic>bar-a` from an exports map containing a wildcard is not
1021        // implemented currently
1022        // assert_eq!(
1023        //     map.lookup(&Pattern::Concatenation(vec![
1024        //         Pattern::Constant(rcstr!("foo-")),
1025        //         Pattern::Dynamic,
1026        //     ]))
1027        //     .collect::<Vec<_>>(),
1028        //     vec![super::AliasMatch {
1029        //         prefix: "foo-".into(),
1030        //         key: &super::AliasKey::Wildcard { suffix: rcstr!("") },
1031        //         output: Pattern::Concatenation(vec![
1032        //             Pattern::Constant(rcstr!("src/foo/")),
1033        //             Pattern::Dynamic,
1034        //         ]),
1035        //     }]
1036        // );
1037
1038        assert_eq!(
1039            map.lookup(&Pattern::Concatenation(vec![
1040                Pattern::Dynamic,
1041                Pattern::Constant(rcstr!("bar-a")),
1042            ]))
1043            .collect::<Result<Vec<_>>>()
1044            .unwrap(),
1045            vec![super::AliasMatch {
1046                prefix: "bar-a".into(),
1047                key: &AliasKey::Exact,
1048                output: Pattern::Constant(rcstr!("src/bar/a"))
1049            }]
1050        );
1051        assert_eq!(
1052            map.lookup(&Pattern::Concatenation(vec![
1053                Pattern::Constant(rcstr!("bar-")),
1054                Pattern::Dynamic,
1055            ]))
1056            .collect::<Result<Vec<_>>>()
1057            .unwrap(),
1058            vec![
1059                super::AliasMatch {
1060                    prefix: "bar-b".into(),
1061                    key: &AliasKey::Exact,
1062                    output: Pattern::Constant(rcstr!("src/bar/b"))
1063                },
1064                super::AliasMatch {
1065                    prefix: "bar-a".into(),
1066                    key: &AliasKey::Exact,
1067                    output: Pattern::Constant(rcstr!("src/bar/a"))
1068                }
1069            ]
1070        );
1071    }
1072}
turbopack_core/resolve/alias_map.rs

turbopack_core/resolve/
alias_map.rs
