Repository: vercel/next.js
Pull request: [turbopack] Avoid returning multiple requests when performing file extension substitution

If we modify user patterns with filename extension alternates, we should ensure we only produce one result.

e.g. given

```
src/
     foo.js
     foo.ts
     foo.json
```

If `fullySpecified=false` then `import foo` should produce `foo.js`, not `foo.js` and `foo.json`

similarly if your tsconfig sets `"moduleResolution":"nodeNext"` and you import `foo.js` it should produce `foo.ts`, but not `[foo.ts, foo.js]`.

The core problem is that we expand a user supplied pattern with alternates and then we need to only produce matches that 'correspond' to the original pattern.  To accomplish this I implemented an 'undo stack' so that when we examine a match produced by `read_matches` we can transform the request key back into something that matches the original pattern.

This neatly solves the issue of accidentally producing multiple matches with the same base filename.  Consider the pattern `./foo.js`, we expand the pattern to `./foo.{ts,tsx,js}` and then produce two matches `[(./foo.ts, foo.ts), (./foo.js, foo.js)]` our undo stack will transform the `./foo.ts` key back into `./foo.js` and then the alternate merging logic will pick the first one for each key!

The nice thing about the 'key' based approach is that it does the right thing for dynamic requests as well.

Finally, the new 'undo stack' based approach is much more composable than the old 'sequence of conditions' based approach so now it is trivial to produce all matches in parallel.

Changed files:
filename: turbopack/crates/turbopack-core/src/resolve/mod.rs
patch: @@ -3,14 +3,17 @@ use std::{
     collections::BTreeMap,
     fmt::{Display, Formatter, Write},
     future::Future,
-    iter::once,
+    iter::{empty, once},
 };
 
 use anyhow::{Result, bail};
 use auto_hash_map::AutoSet;
 use bincode::{Decode, Encode};
+use either::Either;
+use once_cell::sync::Lazy;
 use rustc_hash::{FxHashMap, FxHashSet};
 use serde::{Deserialize, Serialize};
+use smallvec::SmallVec;
 use tracing::{Instrument, Level};
 use turbo_rcstr::{RcStr, rcstr};
 use turbo_tasks::{
@@ -2247,19 +2250,133 @@ async fn resolve_relative_request(
 
     let mut new_path = path_pattern.clone();
 
+    // A small tree to 'undo' the set of modifications we make to patterns, ensuring that we produce
+    // correct request keys
+    #[derive(Eq, PartialEq, Clone, Hash, Debug)]
+    enum RequestKeyTransform {
+        /// A leaf node for 'no change'
+        None,
+        /// We added a fragment to the request and thus need to potentially remove it when matching
+        AddedFragment,
+        // We added an extension to the request and thus need to potentially remove it when
+        // matching
+        AddedExtension {
+            /// The extension that was added
+            ext: RcStr,
+            /// This modification can be composed with others
+            /// In reality just `None' or `AddedFragment``
+            next: Vec<RequestKeyTransform>,
+        },
+        ReplacedExtension {
+            /// The extension that was replaced, to figure out the original you need to query
+            /// [TS_EXTENSION_REPLACEMENTS]
+            ext: RcStr,
+            /// This modification can be composed with others
+            /// In just [AddedExtension], [None] or [AddedFragment]
+            next: Vec<RequestKeyTransform>,
+        },
+    }
+
+    impl RequestKeyTransform {
+        /// Modifies the matched pattern using the modification rules and produces results if they
+        /// match the supplied [pattern]
+        fn undo(
+            &self,
+            matched_pattern: &RcStr,
+            fragment: &RcStr,
+            pattern: &Pattern,
+        ) -> impl Iterator<Item = (RcStr, RcStr)> {
+            let mut result = SmallVec::new();
+            self.apply_internal(matched_pattern, fragment, pattern, &mut result);
+            result.into_iter()
+        }
+
+        fn apply_internal(
+            &self,
+            matched_pattern: &RcStr,
+            fragment: &RcStr,
+            pattern: &Pattern,
+            result: &mut SmallVec<[(RcStr, RcStr); 2]>,
+        ) {
+            match self {
+                RequestKeyTransform::None => {
+                    if pattern.is_match(matched_pattern.as_str()) {
+                        result.push((matched_pattern.clone(), fragment.clone()));
+                    }
+                }
+                RequestKeyTransform::AddedFragment => {
+                    debug_assert!(
+                        !fragment.is_empty(),
+                        "can only have an AddedFragment modification if there was a fragment"
+                    );
+                    if let Some(stripped_pattern) = matched_pattern.strip_suffix(fragment.as_str())
+                        && pattern.is_match(stripped_pattern)
+                    {
+                        result.push((stripped_pattern.into(), RcStr::default()));
+                    }
+                }
+                RequestKeyTransform::AddedExtension { ext, next } => {
+                    if let Some(stripped_pattern) = matched_pattern.strip_suffix(ext.as_str()) {
+                        let stripped_pattern: RcStr = stripped_pattern.into();
+                        Self::apply_all(next, &stripped_pattern, fragment, pattern, result);
+                    }
+                }
+                RequestKeyTransform::ReplacedExtension { ext, next } => {
+                    if let Some(stripped_pattern) = matched_pattern.strip_suffix(ext.as_str()) {
+                        let replaced_pattern: RcStr = format!(
+                            "{stripped_pattern}{old_ext}",
+                            old_ext = TS_EXTENSION_REPLACEMENTS.reverse.get(ext).unwrap()
+                        )
+                        .into();
+                        Self::apply_all(next, &replaced_pattern, fragment, pattern, result);
+                    }
+                }
+            }
+        }
+
+        fn apply_all(
+            list: &[RequestKeyTransform],
+            matched_pattern: &RcStr,
+            fragment: &RcStr,
+            pattern: &Pattern,
+            result: &mut SmallVec<[(RcStr, RcStr); 2]>,
+        ) {
+            list.iter()
+                .for_each(|pm| pm.apply_internal(matched_pattern, fragment, pattern, result));
+        }
+    }
+
+    let mut modifications = Vec::new();
+    modifications.push(RequestKeyTransform::None);
+
     // Fragments are a bit odd. `require()` allows importing files with literal `#` characters in
     // them, but `import` treats it like a url and drops it from resolution. So we need to consider
     // both cases here.
     if !fragment.is_empty() {
+        modifications.push(RequestKeyTransform::AddedFragment);
         new_path.push(Pattern::Alternatives(vec![
             Pattern::Constant(RcStr::default()),
             Pattern::Constant(fragment.clone()),
         ]));
     }
 
     if !options_value.fully_specified {
+        // For each current set of modifications append an extension modification
+        modifications =
+            modifications
+                .iter()
+                .cloned()
+                .chain(options_value.extensions.iter().map(|ext| {
+                    RequestKeyTransform::AddedExtension {
+                        ext: ext.clone(),
+                        next: modifications.clone(),
+                    }
+                }))
+                .collect();
         // Add the extensions as alternatives to the path
         // read_matches keeps the order of alternatives intact
+        // TODO: if the pattern has a dynamic suffix then this 'ordering' doesn't work since we just
+        // take the slowpath and return everything from the directory in `read_matches`
         new_path.push(Pattern::Alternatives(
             once(Pattern::Constant(RcStr::default()))
                 .chain(
@@ -2273,48 +2390,78 @@ async fn resolve_relative_request(
         new_path.normalize();
     };
 
+    struct ExtensionReplacements {
+        forward: FxHashMap<RcStr, SmallVec<[RcStr; 3]>>,
+        reverse: FxHashMap<RcStr, RcStr>,
+    }
+    static TS_EXTENSION_REPLACEMENTS: Lazy<ExtensionReplacements> = Lazy::new(|| {
+        let mut forward = FxHashMap::default();
+        forward.insert(
+            rcstr!(".js"),
+            SmallVec::from_vec(vec![rcstr!(".ts"), rcstr!(".tsx"), rcstr!(".js")]),
+        );
+
+        forward.insert(
+            rcstr!(".mjs"),
+            SmallVec::from_vec(vec![rcstr!(".mts"), rcstr!(".mjs")]),
+        );
+
+        forward.insert(
+            rcstr!(".cjs"),
+            SmallVec::from_vec(vec![rcstr!(".cts"), rcstr!(".cjs")]),
+        );
+        let reverse = forward
+            .iter()
+            .flat_map(|(k, v)| v.iter().map(|v: &RcStr| (v.clone(), k.clone())))
+            .collect::<FxHashMap<_, _>>();
+        ExtensionReplacements { forward, reverse }
+    });
+
     if options_value.enable_typescript_with_output_extension {
-        new_path.replace_final_constants(&|c: &RcStr| -> Option<Pattern> {
-            let (base, replacement) = match c.rsplit_once(".") {
-                Some((base, "js")) => (
-                    base,
-                    vec![
-                        Pattern::Constant(rcstr!(".ts")),
-                        Pattern::Constant(rcstr!(".tsx")),
-                        Pattern::Constant(rcstr!(".js")),
-                    ],
-                ),
-                Some((base, "mjs")) => (
-                    base,
-                    vec![
-                        Pattern::Constant(rcstr!(".mts")),
-                        Pattern::Constant(rcstr!(".mjs")),
-                    ],
-                ),
-                Some((base, "cjs")) => (
-                    base,
-                    vec![
-                        Pattern::Constant(rcstr!(".cts")),
-                        Pattern::Constant(rcstr!(".cjs")),
-                    ],
-                ),
-                _ => {
-                    return None;
+        // there are at most 4 possible replacements (the size of the reverse map)
+        let mut replaced_extensions = SmallVec::<[RcStr; 4]>::new();
+        let replaced = new_path.replace_final_constants(&mut |c: &RcStr| -> Option<Pattern> {
+            let (base, ext) = c.split_at(c.rfind('.')?);
+
+            let (ext, replacements) = TS_EXTENSION_REPLACEMENTS.forward.get_key_value(ext)?;
+            for replacement in replacements {
+                if replacement != ext && !replaced_extensions.contains(replacement) {
+                    replaced_extensions.push(replacement.clone());
+                    debug_assert!(replaced_extensions.len() <= replaced_extensions.inline_size());
                 }
-            };
+            }
+
+            let replacements = replacements
+                .iter()
+                .cloned()
+                .map(Pattern::Constant)
+                .collect();
+
             if base.is_empty() {
-                Some(Pattern::Alternatives(replacement))
+                Some(Pattern::Alternatives(replacements))
             } else {
                 Some(Pattern::Concatenation(vec![
                     Pattern::Constant(base.into()),
-                    Pattern::Alternatives(replacement),
+                    Pattern::Alternatives(replacements),
                 ]))
             }
         });
-        new_path.normalize();
+        if replaced {
+            // For each current set of modifications append an extension replacement modification
+            modifications = modifications
+                .iter()
+                .cloned()
+                .chain(replaced_extensions.iter().map(|ext| {
+                    RequestKeyTransform::ReplacedExtension {
+                        ext: ext.clone(),
+                        next: modifications.clone(),
+                    }
+                }))
+                .collect();
+            new_path.normalize();
+        }
     }
 
-    let mut results = Vec::new();
     let matches = read_matches(
         lookup_path.clone(),
         rcstr!(""),
@@ -2324,100 +2471,40 @@ async fn resolve_relative_request(
     .await?;
 
     // This loop is necessary to 'undo' the modifications to 'new_path' that were performed above.
-    // e.g. we added extensions but these shouldn't be part of the request key so remove them
-    // TODO: this logic is not completely correct because it fails to account for the extension
-    // replacement logic that we perform conditionally.
-
-    for m in matches.iter() {
-        if let PatternMatch::File(matched_pattern, path) = m {
-            let mut pushed = false;
-            if !options_value.fully_specified {
-                for ext in options_value.extensions.iter() {
-                    let Some(matched_pattern) = matched_pattern.strip_suffix(&**ext) else {
-                        continue;
-                    };
-
-                    if !fragment.is_empty() {
-                        // If the fragment is not empty, we need to strip it from the matched
-                        // pattern so it matches path_pattern
-                        if let Some(matched_pattern) =
-                            matched_pattern.strip_suffix(fragment.as_str())
-                            && path_pattern.is_match(matched_pattern)
-                        {
-                            results.push(
-                                resolved(
-                                    RequestKey::new(matched_pattern.into()),
-                                    path.clone(),
-                                    lookup_path.clone(),
-                                    request,
-                                    options_value,
-                                    options,
-                                    query.clone(),
-                                    RcStr::default(),
-                                )
-                                .await?,
-                            );
-                            pushed = true;
-                        }
-                    }
-                    if path_pattern.is_match(matched_pattern) {
-                        results.push(
-                            resolved(
-                                RequestKey::new(matched_pattern.into()),
-                                path.clone(),
-                                lookup_path.clone(),
-                                request,
-                                options_value,
-                                options,
-                                query.clone(),
-                                fragment.clone(),
-                            )
-                            .await?,
-                        );
-                        pushed = true;
-                    }
-                }
-            }
-            if !fragment.is_empty() {
-                // If the fragment is not empty, we need to strip it from the matched pattern so it
-                // matches the original pattern
-                if let Some(matched_pattern) = matched_pattern.strip_suffix(fragment.as_str())
-                    && path_pattern.is_match(matched_pattern)
-                {
-                    results.push(
-                        resolved(
-                            RequestKey::new(matched_pattern.into()),
-                            path.clone(),
-                            lookup_path.clone(),
-                            request,
-                            options_value,
-                            options,
-                            query.clone(),
-                            RcStr::default(),
-                        )
-                        .await?,
-                    );
-                    pushed = true;
-                }
+    // e.g. we added extensions but these shouldn't be part of the request key so remove them.
+
+    let mut keys = FxHashSet::default();
+    let mut results = matches
+        .iter()
+        .flat_map(|m| {
+            if let PatternMatch::File(matched_pattern, path) = m {
+                Either::Left(
+                    modifications
+                        .iter()
+                        .flat_map(|m| m.undo(matched_pattern, &fragment, path_pattern))
+                        .map(move |result| (result, path)),
+                )
+            } else {
+                Either::Right(empty())
             }
+        })
+        // Dedupe here before calling `resolved`
+        .filter(move |((matched_pattern, _), _)| keys.insert(matched_pattern.clone()))
+        .map(|((matched_pattern, fragment), path)| {
+            resolved(
+                RequestKey::new(matched_pattern),
+                path.clone(),
+                lookup_path.clone(),
+                request,
+                options_value,
+                options,
+                query.clone(),
+                fragment,
+            )
+        })
+        .try_join()
+        .await?;
 
-            if !pushed || path_pattern.is_match(matched_pattern) {
-                results.push(
-                    resolved(
-                        RequestKey::new(matched_pattern.clone()),
-                        path.clone(),
-                        lookup_path.clone(),
-                        request,
-                        options_value,
-                        options,
-                        query.clone(),
-                        fragment.clone(),
-                    )
-                    .await?,
-                );
-            }
-        }
-    }
     // Directory matches must be resolved AFTER file matches
     for m in matches.iter() {
         if let PatternMatch::Directory(matched_pattern, path) = m {
@@ -3375,12 +3462,7 @@ mod tests {
             pattern: rcstr!("./foo.js").into(),
             enable_typescript_with_output_extension: true,
             fully_specified: false,
-            expected: vec![
-                // WRONG: request key is incorrect
-                ("./foo.ts", "foo.ts"),
-                // WRONG: shouldn't produce the .js file
-                ("./foo.js", "foo.js"),
-            ],
+            expected: vec![("./foo.js", "foo.ts")],
         })
         .await;
     }
@@ -3454,13 +3536,9 @@ mod tests {
             pattern: rcstr!("./client#component.js").into(),
             enable_typescript_with_output_extension: true,
             fully_specified: false,
-            expected: vec![
-                // The request key is fundamentally ambiguous.  It depends on whether or not we
-                // consider this fragment to be part of the request pattern
-                ("./client#component.ts", "client#component.ts"),
-                // WRONG: js file should not be produced
-                ("./client", "client#component.js"),
-            ],
+            // Whether or not this request key is correct somewhat ambiguous.  It depends on whether
+            // or not we consider this fragment to be part of the request pattern
+            expected: vec![("./client", "client#component.ts")],
         })
         .await;
     }
@@ -3506,11 +3584,8 @@ mod tests {
             enable_typescript_with_output_extension: true,
             fully_specified: false,
             expected: vec![
-                // WRONG: request key doesn't match pattern
-                ("./src/foo.ts", "src/foo.ts"),
+                ("./src/foo.js", "src/foo.ts"),
                 ("./src/bar.js", "src/bar.js"),
-                // WRONG: source file is redundant with extension rewriting
-                ("./src/foo.js", "src/foo.js"),
             ],
         })
         .await;
@@ -3530,11 +3605,15 @@ mod tests {
             enable_typescript_with_output_extension: true,
             fully_specified: false,
             expected: vec![
-                ("./src/bar", "src/bar.js"),
                 ("./src/bar.js", "src/bar.js"),
-                // WRONG: all three should point at the .ts file
-                ("./src/foo", "src/foo.js"),
+                ("./src/bar", "src/bar.js"),
+                // TODO: all three should point at the .ts file
+                // This happens because read_matches returns the `.js` file first simply because we
+                // match every file in the directory with this pattern. To address we would need to
+                // sort read_matches after the fact, or otherwise change how we modify dynamic
+                // patterns.
                 ("./src/foo.js", "src/foo.js"),
+                ("./src/foo", "src/foo.js"),
                 ("./src/foo.ts", "src/foo.ts"),
             ],
         })

filename: turbopack/crates/turbopack-core/src/resolve/pattern.rs
patch: @@ -1229,7 +1229,10 @@ impl Pattern {
     /// Calls `cb` on all constants that are at the end of the pattern and
     /// replaces the given final constant with the returned pattern. Returns
     /// true if replacements were performed.
-    pub fn replace_final_constants(&mut self, cb: &impl Fn(&RcStr) -> Option<Pattern>) -> bool {
+    pub fn replace_final_constants(
+        &mut self,
+        cb: &mut impl FnMut(&RcStr) -> Option<Pattern>,
+    ) -> bool {
         let mut replaced = false;
         match self {
             Pattern::Constant(c) => {
@@ -1524,6 +1527,7 @@ impl PatternMatch {
 // TODO this isn't super efficient
 // avoid storing a large list of matches
 #[turbo_tasks::value(transparent)]
+#[derive(Debug)]
 pub struct PatternMatches(Vec<PatternMatch>);
 
 /// Find all files or directories that match the provided `pattern` with the
@@ -2492,12 +2496,12 @@ mod tests {
 
     #[test]
     fn replace_final_constants() {
-        fn f(mut p: Pattern, cb: &impl Fn(&RcStr) -> Option<Pattern>) -> Pattern {
+        fn f(mut p: Pattern, cb: &mut impl FnMut(&RcStr) -> Option<Pattern>) -> Pattern {
             p.replace_final_constants(cb);
             p
         }
 
-        let js_to_ts_tsx = |c: &RcStr| -> Option<Pattern> {
+        let mut js_to_ts_tsx = |c: &RcStr| -> Option<Pattern> {
             c.strip_suffix(".js").map(|rest| {
                 let new_ending = Pattern::Alternatives(vec![
                     Pattern::Constant(rcstr!(".ts")),
@@ -2523,7 +2527,7 @@ mod tests {
                         Pattern::Constant(rcstr!(".node")),
                     ])
                 ]),
-                &js_to_ts_tsx
+                &mut js_to_ts_tsx
             ),
             Pattern::Concatenation(vec![
                 Pattern::Constant(rcstr!(".")),
@@ -2546,7 +2550,7 @@ mod tests {
                     Pattern::Constant(rcstr!("/")),
                     Pattern::Constant(rcstr!("abc.js")),
                 ]),
-                &js_to_ts_tsx
+                &mut js_to_ts_tsx
             ),
             Pattern::Concatenation(vec![
                 Pattern::Constant(rcstr!(".")),

filename: turbopack/crates/turbopack-tracing/tests/node-file-trace.rs
patch: @@ -40,6 +40,7 @@ use turbopack::{
     },
 };
 use turbopack_core::{
+    chunk::SourceMapsType,
     compile_time_info::CompileTimeInfo,
     context::AssetContext,
     environment::{Environment, ExecutionEnvironment, NodeJsEnvironment},
@@ -373,10 +374,12 @@ async fn node_file_trace_operation(
                 enable_typescript_transform: Some(
                     TypescriptTransformOptions::default().resolved_cell(),
                 ),
+                // enable_types is required here to ensure .d.ts files are collected.
                 enable_types: true,
                 ..Default::default()
             },
             css: CssOptionsContext {
+                source_maps: SourceMapsType::None,
                 enable_raw_css: true,
                 ..Default::default()
             },

filename: turbopack/crates/turbopack-tracing/tests/unit.rs
patch: @@ -21,6 +21,7 @@ use turbopack::{
     },
 };
 use turbopack_core::{
+    chunk::SourceMapsType,
     compile_time_info::CompileTimeInfo,
     context::AssetContext,
     environment::{Environment, ExecutionEnvironment, NodeJsEnvironment},
@@ -212,6 +213,7 @@ async fn node_file_trace_operation(package_root: RcStr, input: RcStr) -> Result<
                 ..Default::default()
             },
             css: CssOptionsContext {
+                source_maps: SourceMapsType::None,
                 enable_raw_css: true,
                 ..Default::default()
             },