turbopack_core/resolve/
alias_map.rs

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

turbopack_core/resolve/
alias_map.rs
