Repository: denoland/deno
Pull request: fix(npm): memoize peer cache hit checks to prevent combinatorial explosion

## Summary

- Fixes `deno add npm:@aws-cdk/aws-ecs` (and similar large peer dep trees) hanging indefinitely
- Root cause: `find_peers_cache_hit_inner` in `libs/npm/resolution/graph.rs` recursively checks whether cached peer resolutions match the current context. For packages with many mutual peer dependencies (like AWS CDK v1 with ~33 packages and 1200+ cache entries), this causes **combinatorial explosion** — a single cache lookup for `@aws-cdk/aws-kms` triggered **2.5 million recursive calls** taking 17+ seconds
- Fix: since `parent_pkgs` is constant within a single `find_peers_cache_hit` call, the answer for any given `nv` never changes. A `HashMap` memo eliminates all redundant recursive work

## Before/After

| | Before | After |
|---|---|---|
| `deno add npm:@aws-cdk/aws-ecs` | Hangs indefinitely (killed at 120s) | Completes in seconds |

## Test plan

- [x] All 182 `deno_npm` unit tests pass
- [x] Manual test: `deno add npm:@aws-cdk/aws-ecs` completes successfully

Closes #26430

🤖 Generated with [Claude Code](https://claude.com/claude-code)

Changed files:
filename: libs/npm/resolution/graph.rs
patch: @@ -2298,18 +2298,33 @@ impl<'a, TNpmRegistryApi: NpmRegistryApi>
     parent_pkgs: &BTreeMap<StackString, NodeId>,
   ) -> Option<PeersResolution> {
     let mut checking = HashSet::new();
-    self.find_peers_cache_hit_inner(nv, parent_pkgs, &mut checking)
+    // Memoize recursive equivalence checks within this call.
+    // `parent_pkgs` is constant throughout, so the result of
+    // "does nv X have a matching cache entry?" is the same every
+    // time we ask. Without this memo, mutually-dependent packages
+    // (like the AWS CDK v1 suite) cause combinatorial explosion:
+    // each cache entry re-checks the same peers, each of which
+    // re-checks their peers, leading to millions of redundant calls.
+    let mut memo = HashMap::new();
+    self.find_peers_cache_hit_inner(nv, parent_pkgs, &mut checking, &mut memo)
   }
 
   fn find_peers_cache_hit_inner(
     &self,
     nv: &PackageNv,
     parent_pkgs: &BTreeMap<StackString, NodeId>,
     checking: &mut HashSet<PackageNv>,
+    memo: &mut HashMap<PackageNv, Option<PeersResolution>>,
   ) -> Option<PeersResolution> {
+    // Return memoized result if we've already fully evaluated this nv.
+    if let Some(result) = memo.get(nv) {
+      return result.clone();
+    }
     let entries = self.peers_cache.get(nv)?;
     if !checking.insert(nv.clone()) {
-      // Prevent infinite recursion for circular deps
+      // Prevent infinite recursion for circular deps.
+      // Don't memoize this — the result is context-dependent
+      // (it depends on which ancestors are currently being checked).
       return None;
     }
     for entry in entries {
@@ -2337,7 +2352,7 @@ impl<'a, TNpmRegistryApi: NpmRegistryApi>
               // Not pure. Check recursively if the non-pure
               // package would resolve the same way in this context.
               if self
-                .find_peers_cache_hit_inner(cnv, parent_pkgs, checking)
+                .find_peers_cache_hit_inner(cnv, parent_pkgs, checking, memo)
                 .is_some()
               {
                 continue;
@@ -2384,10 +2399,13 @@ impl<'a, TNpmRegistryApi: NpmRegistryApi>
 
       if all_match {
         checking.remove(nv);
-        return Some(entry.clone());
+        let result = Some(entry.clone());
+        memo.insert(nv.clone(), result.clone());
+        return result;
       }
     }
     checking.remove(nv);
+    memo.insert(nv.clone(), None);
     None
   }
 
@@ -9158,6 +9176,86 @@ mod test {
     );
   }
 
+  /// Test that mutual peer dependencies between many packages don't cause
+  /// combinatorial explosion in `find_peers_cache_hit_inner`.
+  /// Simulates the AWS CDK v1 pattern where ~30 packages all peer-depend
+  /// on each other (e.g. @aws-cdk/aws-ecs peers with aws-iam, aws-ec2,
+  /// aws-logs, etc., and each of those peers back).
+  /// Without memoization in `find_peers_cache_hit_inner`, this causes
+  /// millions of redundant recursive calls and hangs indefinitely.
+  /// Regression test for https://github.com/denoland/deno/issues/26430
+  #[tokio::test]
+  async fn peer_deps_mutual_many_packages_no_hang() {
+    let api = TestNpmRegistryApi::default();
+
+    // Create a "core" package that all CDK packages depend on
+    api.ensure_package_version("cdk-core", "1.0.0");
+
+    // Create N packages that mutually peer-depend on each other.
+    // With N=25, without memoization this causes combinatorial explosion
+    // in find_peers_cache_hit_inner (hangs indefinitely).
+    let n = 25;
+    let pkg_names: Vec<String> =
+      (0..n).map(|i| format!("cdk-pkg-{}", i)).collect();
+
+    for name in &pkg_names {
+      api.ensure_package_version(name, "1.0.0");
+      // Each package depends on cdk-core
+      api.add_dependency((name, "1.0.0"), ("cdk-core", "1"));
+    }
+
+    // Each package peer-depends on every other package
+    for i in 0..n {
+      for j in 0..n {
+        if i != j {
+          api.add_peer_dependency(
+            (&pkg_names[i], "1.0.0"),
+            (&pkg_names[j], "*"),
+          );
+        }
+      }
+    }
+
+    // A root package that depends on all of them
+    api.ensure_package_version("cdk-app", "1.0.0");
+    for name in &pkg_names {
+      api.add_dependency(("cdk-app", "1.0.0"), (name, "1"));
+    }
+
+    // Build root reqs: cdk-app + all cdk-pkg-N (to provide the peers)
+    let owned_reqs: Vec<String> =
+      pkg_names.iter().map(|n| format!("{}@1", n)).collect();
+    let mut root_reqs: Vec<&str> = vec!["cdk-app@1", "cdk-core@1"];
+    root_reqs.extend(owned_reqs.iter().map(|s| s.as_str()));
+
+    // Without memoization this would hang; with it, completes in < 5s
+    let result = tokio::time::timeout(
+      std::time::Duration::from_secs(30),
+      run_resolver_and_get_output(api, root_reqs),
+    )
+    .await;
+
+    let (packages, _) = result.expect(
+      "Resolution timed out — find_peers_cache_hit likely has \
+       combinatorial explosion (missing memoization)",
+    );
+
+    // Verify all packages resolved
+    assert!(
+      packages.iter().any(|p| p.pkg_id.starts_with("cdk-core@")),
+      "should have cdk-core"
+    );
+    for name in &pkg_names {
+      assert!(
+        packages
+          .iter()
+          .any(|p| p.pkg_id.starts_with(&format!("{}@", name))),
+        "should have {}",
+        name
+      );
+    }
+  }
+
   /// Test that NpmPackageId serialization length stays bounded.
   /// With the Expo-like pattern of many plugins with circular peer deps,
   /// no single package ID should exceed a reasonable length.