Repository: vercel/next.js
Pull request: Unroll recursion in `RuleCondition::matches` This trades allocations due to `Box::pin` calls during recursion for an explicit stack and a tiny interpreter loop.

### What?
Replace recursion with an explicit stack to reduce allocations.  Also, add tests!

This trims peak heap in a build of `vercel-site` by 100-300m, see https://vercel.slack.com/archives/C06PPGZ0FD3/p1747438469043789?thread_ts=1746823119.596949&cid=C06PPGZ0FD3


### Why?
This replaces a lot of `Box::pin` calls during evaluation, instead we can amortize the heap allocation cost by pushing items onto explicit stack. This is managed as a SmallVec so in many cases we should be able to avoid allocations.

### How?
Tediously introduce a small bytecode machine... sigh.  The main alternatives considered were:

* pulling all `awaits` up to the top level and using a normal recursive function.  This works, but would be limiting when we inevitably add another async dependency on the `Source::content`
* eliminating asynchrony from `Source::ident`.  This turned out to be controversial (see discussion in linear) and incredibly complex to implement so it is deferred.

Closes PACK-4560



Changed files:
filename: Cargo.lock
patch: @@ -9896,6 +9896,7 @@ dependencies = [
  "turbo-esregex",
  "turbo-rcstr",
  "turbo-tasks",
+ "turbo-tasks-backend",
  "turbo-tasks-build",
  "turbo-tasks-env",
  "turbo-tasks-fs",

filename: turbopack/crates/turbopack/Cargo.toml
patch: @@ -54,6 +54,7 @@ rstest_reuse = "0.5.0"
 tokio = { workspace = true }
 turbo-tasks-malloc = { workspace = true, default-features = false }
 turbo-tasks-memory = { workspace = true }
+turbo-tasks-backend = { workspace = true }
 
 [build-dependencies]
 turbo-tasks-build = { workspace = true }

filename: turbopack/crates/turbopack/src/module_options/rule_condition.rs
patch: @@ -1,5 +1,6 @@
 use anyhow::{Result, bail};
 use serde::{Deserialize, Serialize};
+use smallvec::SmallVec;
 use turbo_esregex::EsRegex;
 use turbo_tasks::{NonLocalValue, ReadRef, ResolvedVc, primitives::Regex, trace::TraceRawVcs};
 use turbo_tasks_fs::{FileSystemPath, glob::Glob};
@@ -59,75 +60,465 @@ impl RuleCondition {
         path: &FileSystemPath,
         reference_type: &ReferenceType,
     ) -> Result<bool> {
-        Ok(match self {
-            RuleCondition::All(conditions) => {
-                for condition in conditions {
-                    if !Box::pin(condition.matches(source, path, reference_type)).await? {
-                        return Ok(false);
+        enum Op<'a> {
+            All(&'a [RuleCondition]), // Remaining conditions in an All
+            Any(&'a [RuleCondition]), // Remaining conditions in an Any
+            Not,                      // Inverts the previous condition
+        }
+
+        // Evaluates the condition returning the result and possibly pushing additional operations
+        // onto the stack as a kind of continuation.
+        async fn process_condition<'a, const SZ: usize>(
+            source: ResolvedVc<Box<dyn Source + 'static>>,
+            path: &FileSystemPath,
+            reference_type: &ReferenceType,
+            stack: &mut SmallVec<[Op<'a>; SZ]>,
+            mut cond: &'a RuleCondition,
+        ) -> Result<bool, anyhow::Error> {
+            // Use a loop to avoid recursion and unnecessary stack operations.
+            loop {
+                match cond {
+                    RuleCondition::All(conditions) => {
+                        if conditions.is_empty() {
+                            return Ok(true);
+                        } else {
+                            if conditions.len() > 1 {
+                                stack.push(Op::All(&conditions[1..]));
+                            }
+                            cond = &conditions[0];
+                            // jump directly to the next condition, no need to deal with
+                            // the stack.
+                            continue;
+                        }
+                    }
+                    RuleCondition::Any(conditions) => {
+                        if conditions.is_empty() {
+                            return Ok(false);
+                        } else {
+                            if conditions.len() > 1 {
+                                stack.push(Op::Any(&conditions[1..]));
+                            }
+                            cond = &conditions[0];
+                            continue;
+                        }
+                    }
+                    RuleCondition::Not(inner) => {
+                        stack.push(Op::Not);
+                        cond = inner.as_ref();
+                        continue;
+                    }
+                    RuleCondition::ReferenceType(condition_ty) => {
+                        return Ok(condition_ty.includes(reference_type));
+                    }
+                    RuleCondition::ResourceIsVirtualSource => {
+                        return Ok(ResolvedVc::try_downcast_type::<VirtualSource>(source).is_some());
+                    }
+                    RuleCondition::ResourcePathEquals(other) => {
+                        return Ok(path == &**other);
+                    }
+                    RuleCondition::ResourcePathEndsWith(end) => {
+                        return Ok(path.path.ends_with(end));
+                    }
+                    RuleCondition::ResourcePathHasNoExtension => {
+                        return Ok(if let Some(i) = path.path.rfind('.') {
+                            if let Some(j) = path.path.rfind('/') {
+                                j > i
+                            } else {
+                                false
+                            }
+                        } else {
+                            true
+                        });
+                    }
+                    RuleCondition::ResourcePathInDirectory(dir) => {
+                        return Ok(path.path.starts_with(&format!("{dir}/"))
+                            || path.path.contains(&format!("/{dir}/")));
+                    }
+                    RuleCondition::ResourcePathInExactDirectory(parent_path) => {
+                        return Ok(path.is_inside_ref(parent_path));
+                    }
+                    RuleCondition::ContentTypeStartsWith(start) => {
+                        let content_type = &source.ident().await?.content_type;
+                        return Ok(content_type
+                            .as_ref()
+                            .is_some_and(|ct| ct.starts_with(start)));
+                    }
+                    RuleCondition::ContentTypeEmpty => {
+                        return Ok(source.ident().await?.content_type.is_none());
+                    }
+                    RuleCondition::ResourcePathGlob { glob, base } => {
+                        return Ok(if let Some(rel_path) = base.get_relative_path_to(path) {
+                            glob.execute(&rel_path)
+                        } else {
+                            glob.execute(&path.path)
+                        });
+                    }
+                    RuleCondition::ResourceBasePathGlob(glob) => {
+                        let basename = path
+                            .path
+                            .rsplit_once('/')
+                            .map_or(path.path.as_str(), |(_, b)| b);
+                        return Ok(glob.execute(basename));
+                    }
+                    RuleCondition::ResourcePathRegex(_) => {
+                        bail!("ResourcePathRegex not implemented yet");
+                    }
+                    RuleCondition::ResourcePathEsRegex(regex) => {
+                        return Ok(regex.is_match(&path.path));
                     }
                 }
-                true
             }
-            RuleCondition::Any(conditions) => {
-                for condition in conditions {
-                    if Box::pin(condition.matches(source, path, reference_type)).await? {
-                        return Ok(true);
+        }
+        // Allocate a small inline stack to avoid heap allocations in the common case where
+        // conditions are not deeply stacked.  Additionally we take care to avoid stack
+        // operations unless strictly necessary.
+        const EXPECTED_SIZE: usize = 8;
+        let mut stack = SmallVec::<[Op; EXPECTED_SIZE]>::with_capacity(EXPECTED_SIZE);
+        let mut result = process_condition(source, path, reference_type, &mut stack, self).await?;
+        while let Some(op) = stack.pop() {
+            match op {
+                Op::All(remaining) => {
+                    // Previous was true, keep going
+                    if result {
+                        if remaining.len() > 1 {
+                            stack.push(Op::All(&remaining[1..]));
+                        }
+                        result = process_condition(
+                            source,
+                            path,
+                            reference_type,
+                            &mut stack,
+                            &remaining[0],
+                        )
+                        .await?;
+                    }
+                }
+                Op::Any(remaining) => {
+                    // Previous was false, keep going
+                    if !result {
+                        if remaining.len() > 1 {
+                            stack.push(Op::Any(&remaining[1..]));
+                        }
+                        // If the stack didn't change, we can loop inline, but we would still need
+                        // to pop the item.  This might be faster since we would avoid the `match`
+                        // but overall, that is quite minor for an enum with 3 cases.
+                        result = process_condition(
+                            source,
+                            path,
+                            reference_type,
+                            &mut stack,
+                            &remaining[0],
+                        )
+                        .await?;
                     }
                 }
-                false
+                Op::Not => {
+                    result = !result;
+                }
             }
-            RuleCondition::Not(condition) => {
-                !Box::pin(condition.matches(source, path, reference_type)).await?
+        }
+        Ok(result)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use turbo_tasks::Vc;
+    use turbo_tasks_backend::{BackendOptions, TurboTasksBackend, noop_backing_storage};
+    use turbo_tasks_fs::{FileContent, FileSystem, VirtualFileSystem};
+    use turbopack_core::{asset::AssetContent, file_source::FileSource};
+
+    use super::*;
+
+    #[tokio::test]
+    async fn test_rule_condition_leaves() {
+        crate::register();
+        let tt = turbo_tasks::TurboTasks::new(TurboTasksBackend::new(
+            BackendOptions::default(),
+            noop_backing_storage(),
+        ));
+        tt.run_once(async {
+            let fs = VirtualFileSystem::new();
+            let virtual_path = fs.root().join("foo.js".into());
+            let virtual_source = Vc::upcast::<Box<dyn Source>>(VirtualSource::new(
+                virtual_path,
+                AssetContent::File(FileContent::NotFound.cell().to_resolved().await?).cell(),
+            ))
+            .to_resolved()
+            .await?;
+
+            let non_virtual_path = fs.root().join("bar.js".into());
+            let non_virtual_source =
+                Vc::upcast::<Box<dyn Source>>(FileSource::new(non_virtual_path))
+                    .to_resolved()
+                    .await?;
+
+            {
+                let condition = RuleCondition::ReferenceType(ReferenceType::Runtime);
+                assert!(
+                    condition
+                        .matches(
+                            virtual_source,
+                            &*virtual_path.await?,
+                            &ReferenceType::Runtime
+                        )
+                        .await
+                        .unwrap()
+                );
+                assert!(
+                    !condition
+                        .matches(
+                            non_virtual_source,
+                            &*non_virtual_path.await?,
+                            &ReferenceType::Css(
+                                turbopack_core::reference_type::CssReferenceSubType::Compose
+                            )
+                        )
+                        .await
+                        .unwrap()
+                );
             }
-            RuleCondition::ResourcePathEquals(other) => path == &**other,
-            RuleCondition::ResourcePathEndsWith(end) => path.path.ends_with(end),
-            RuleCondition::ResourcePathHasNoExtension => {
-                if let Some(i) = path.path.rfind('.') {
-                    if let Some(j) = path.path.rfind('/') {
-                        j > i
-                    } else {
-                        false
-                    }
-                } else {
-                    true
-                }
+
+            {
+                let condition = RuleCondition::ResourceIsVirtualSource;
+                assert!(
+                    condition
+                        .matches(
+                            virtual_source,
+                            &*virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
+                assert!(
+                    !condition
+                        .matches(
+                            non_virtual_source,
+                            &*non_virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
             }
-            RuleCondition::ResourcePathInDirectory(dir) => {
-                path.path.starts_with(&format!("{dir}/")) || path.path.contains(&format!("/{dir}/"))
+            {
+                let condition = RuleCondition::ResourcePathEquals(virtual_path.await?);
+                assert!(
+                    condition
+                        .matches(
+                            virtual_source,
+                            &*virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
+                assert!(
+                    !condition
+                        .matches(
+                            non_virtual_source,
+                            &*non_virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
             }
-            RuleCondition::ResourcePathInExactDirectory(parent_path) => {
-                path.is_inside_ref(parent_path)
+            {
+                let condition = RuleCondition::ResourcePathHasNoExtension;
+                assert!(
+                    condition
+                        .matches(
+                            virtual_source,
+                            &*fs.root().join("foo".into()).await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
+                assert!(
+                    !condition
+                        .matches(
+                            non_virtual_source,
+                            &*non_virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
             }
-            RuleCondition::ReferenceType(condition_ty) => condition_ty.includes(reference_type),
-            RuleCondition::ResourceIsVirtualSource => {
-                ResolvedVc::try_downcast_type::<VirtualSource>(source).is_some()
+            {
+                let condition = RuleCondition::ResourcePathEndsWith("foo.js".to_string());
+                assert!(
+                    condition
+                        .matches(
+                            virtual_source,
+                            &*virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
+                assert!(
+                    !condition
+                        .matches(
+                            non_virtual_source,
+                            &*non_virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
             }
-            RuleCondition::ContentTypeStartsWith(start) => {
-                if let Some(content_type) = source.ident().await?.content_type.as_ref() {
-                    content_type.starts_with(start)
-                } else {
-                    false
-                }
+            anyhow::Ok(())
+        })
+        .await
+        .unwrap();
+    }
+
+    #[tokio::test]
+    async fn test_rule_condition_tree() {
+        crate::register();
+        let tt = turbo_tasks::TurboTasks::new(TurboTasksBackend::new(
+            BackendOptions::default(),
+            noop_backing_storage(),
+        ));
+        tt.run_once(async {
+            let fs = VirtualFileSystem::new();
+            let virtual_path = fs.root().join("foo.js".into());
+            let virtual_source = Vc::upcast::<Box<dyn Source>>(VirtualSource::new(
+                virtual_path,
+                AssetContent::File(FileContent::NotFound.cell().to_resolved().await?).cell(),
+            ))
+            .to_resolved()
+            .await?;
+
+            let non_virtual_path = fs.root().join("bar.js".into());
+            let non_virtual_source =
+                Vc::upcast::<Box<dyn Source>>(FileSource::new(non_virtual_path))
+                    .to_resolved()
+                    .await?;
+
+            {
+                // not
+                let condition = RuleCondition::not(RuleCondition::ResourceIsVirtualSource);
+                assert!(
+                    !condition
+                        .matches(
+                            virtual_source,
+                            &*virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
+                assert!(
+                    condition
+                        .matches(
+                            non_virtual_source,
+                            &*non_virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
             }
-            RuleCondition::ContentTypeEmpty => source.ident().await?.content_type.is_none(),
-            RuleCondition::ResourcePathGlob { glob, base } => {
-                if let Some(path) = base.get_relative_path_to(path) {
-                    glob.execute(&path)
-                } else {
-                    glob.execute(&path.path)
-                }
+            {
+                // any
+                // Only one of the conditions matches our virtual source
+                let condition = RuleCondition::any(vec![
+                    RuleCondition::ResourcePathInDirectory("doesnt/exist".to_string()),
+                    RuleCondition::ResourceIsVirtualSource,
+                    RuleCondition::ResourcePathHasNoExtension,
+                ]);
+                assert!(
+                    condition
+                        .matches(
+                            virtual_source,
+                            &*virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
+                assert!(
+                    !condition
+                        .matches(
+                            non_virtual_source,
+                            &*non_virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
             }
-            RuleCondition::ResourceBasePathGlob(glob) => {
-                let basename = path
-                    .path
-                    .rsplit_once('/')
-                    .map_or(path.path.as_str(), |(_, b)| b);
-                glob.execute(basename)
+            {
+                // all
+                // Only one of the conditions matches our virtual source
+                let condition = RuleCondition::all(vec![
+                    RuleCondition::ResourcePathEndsWith("foo.js".to_string()),
+                    RuleCondition::ResourceIsVirtualSource,
+                    RuleCondition::ResourcePathEquals(virtual_path.await?),
+                ]);
+                assert!(
+                    condition
+                        .matches(
+                            virtual_source,
+                            &*virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
+                assert!(
+                    !condition
+                        .matches(
+                            non_virtual_source,
+                            &*non_virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
             }
-            RuleCondition::ResourcePathRegex(_) => {
-                bail!("ResourcePathRegex not implemented yet")
+            {
+                // bigger tree
+
+                // Build a simple tree to cover our various composite conditions
+                let condition = RuleCondition::all(vec![
+                    RuleCondition::ResourceIsVirtualSource,
+                    RuleCondition::ResourcePathEquals(virtual_path.await?),
+                    RuleCondition::Not(Box::new(RuleCondition::ResourcePathHasNoExtension)),
+                    RuleCondition::Any(vec![
+                        RuleCondition::ResourcePathEndsWith("foo.js".to_string()),
+                        RuleCondition::ContentTypeEmpty,
+                    ]),
+                ]);
+                assert!(
+                    condition
+                        .matches(
+                            virtual_source,
+                            &*virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
+                assert!(
+                    !condition
+                        .matches(
+                            non_virtual_source,
+                            &*non_virtual_path.await?,
+                            &ReferenceType::Undefined
+                        )
+                        .await
+                        .unwrap()
+                );
             }
-            RuleCondition::ResourcePathEsRegex(regex) => regex.is_match(&path.path),
+            anyhow::Ok(())
         })
+        .await
+        .unwrap();
     }
 }