fix(audit): compute reachable vulnerabilities with Tarjan SCC by chentsulin · Pull Request #12467 · pnpm/pnpm

chentsulin · 2026-06-17T08:23:47Z

Summary

pnpm audit became dramatically slower (CPU-bound, ~5–6×) starting in 11.5.1 on workspaces whose lockfiles contain dependency cycles. This PR restores linear-time behaviour while keeping the path-pruning optimisation introduced in #12087.

The reachability pruning added in 11.5.1 (createReachableVulnerabilitiesGetter) only memoised acyclic subtrees. A node whose subtree touched a cycle — and every one of its ancestors up to the importer roots — was therefore recomputed from scratch on every query, turning the path walk into O(N²). Reachability is now computed once per node with Tarjan's strongly-connected-components algorithm: every node is scanned exactly once, and all members of a cycle share a single reachable-vulnerability set, so cyclic graphs are handled in O(N + E).

The reachable set is used only to prune, so it must never be an under-approximation (that would hide a real finding). Tarjan yields the exact set for every node, so no finding can be dropped; the path-recording logic in walkForPaths is unchanged.

Closes #12212.

Squash Commit Body

fix(audit): compute reachable vulnerabilities with Tarjan SCC

`pnpm audit` enumerates the install paths to every vulnerable package. The
reachability-based pruning added in 11.5.1 (pnpm/pnpm#12087) lets the walker
skip subtrees that reach no unsaturated finding by precomputing, per node, the
set of vulnerabilities reachable from it.

That getter only memoised acyclic subtrees: a node whose subtree contained a
cycle was `complete === false`, and so was every ancestor up to the importer
roots. None of them were cached, so their reachable set was recomputed on every
query. Real dependency graphs commonly contain cycles, and a single cycle high
in the graph makes a large fraction of nodes non-memoisable, yielding an O(N^2)
walk. This matched the report in pnpm/pnpm#12212 exactly (CPU-bound, identical
audit output across versions).

Reachability is now computed with Tarjan's strongly-connected-components
algorithm. Every node is scanned once; all members of an SCC reach the same set
of vulnerabilities and share one set, finalised in reverse-topological order.
Cyclic graphs are handled in O(N + E).

The reachable set is used only to prune, so it must never under-approximate
(that would hide a real finding). Tarjan yields the exact set for every node,
so no finding can be dropped, and the path-recording logic is unchanged. The
getter returns ReadonlySet<string> so the shared sets cannot be mutated by
callers, and a missing memo entry (an impossible-by-construction state) throws
rather than silently returning an empty set.

A regression test asserts the read-count growth ratio between two cycle sizes
(L=200 and L=400) is sub-quadratic: the fix scales ~2x (linear), the previous
code ~4x (quadratic). Asserting the ratio cancels the per-node constant, so the
test is not brittle to constant-factor changes.

Closes pnpm/pnpm#12212.

Checklist

The change is implemented in both the TypeScript CLI and the Rust
pacquet/ port, or the description notes what still needs porting. — audit
is a TypeScript-only command (outside pacquet's current
install/add/update/remove surface), so no pacquet-side port is needed.
Added a changeset (pnpm changeset) if this PR changes any published
package. Keep it short and written for pnpm users — it becomes a release note.
Added or updated tests. — New sub-quadratic scalability regression test in
@pnpm/deps.compliance.audit; all 23 tests pass.

Summary by CodeRabbit

Bug Fixes
- Improved pnpm audit performance on lockfiles with dependency cycles by computing reachability per cyclic group only once, reducing redundant work.
- Prevented call-stack overflows on very deep dependency graphs during audit path indexing.
Tests
- Added Jest coverage for large cyclic graphs to ensure audit indexing scales sub-quadratically.
- Added a deep-chain regression test to verify stack-safe audit path indexing.
Chores
- Updated spellchecking allowlist and published patch release notes for the compliance/audit improvements.

welcome · 2026-06-17T08:23:50Z

💖 Thanks for opening this pull request! 💖
Please be patient and we will get back to you as soon as we can.

qodo-free-for-open-source-projects · 2026-06-17T08:24:23Z

Code Review by Qodo

🐞 Bugs (2) 📘 Rule violations (0) 📎 Requirement gaps (1) 📜 Skill insights (0)

Context used

✅ Tickets: 🎫 pnpm audit is ~6x slower in 11.5.1+ than 11.4.0 on a large monorepo

1. strongconnect() recursion stack overflow 📎 Requirement gap ⛨ Security

Description

createReachableVulnerabilitiesGetter() uses a recursive Tarjan DFS (strongconnect() calls
itself), which can overflow the JS call stack on sufficiently deep (but valid) dependency graphs
derived from attacker-controlled lockfiles, crashing pnpm audit (DoS) instead of completing
efficiently.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R260-291]

+  const strongconnect = (edge: { name: string, depPath: DepPath }): void => {
+    const idx = counter++
+    index.set(edge.depPath, idx)
+    lowlink.set(edge.depPath, idx)
+    sccStack.push(edge.depPath)
 onStack.add(edge.depPath)
-    const result = new Set<string>()
-    let complete = true
-    const { name, version } = nameVerFromPkgSnapshot(edge.depPath, pkgSnapshot)
-    const resolvedName = name ?? edge.name
-    if (version && vulnerableNames.has(resolvedName)) {
-      result.add(vulnerabilityKey(resolvedName, version, edge.depPath))
-    }
-    const collect = (child: { name: string, depPath: DepPath }): void => {
-      const childResult = compute(child)
-      addAll(result, childResult.result)
-      if (!childResult.complete) complete = false
+
+    // Derive children from this single read rather than via a helper that would
+    // read the snapshot again.
+    const pkgSnapshot = packages[edge.depPath]
+    const own = new Set<string>()
+    const children: Array<{ name: string, depPath: DepPath }> = []
+    if (pkgSnapshot != null) {
+      const { name, version } = nameVerFromPkgSnapshot(edge.depPath, pkgSnapshot)
+      const resolvedName = name ?? edge.name
+      if (version && vulnerableNames.has(resolvedName)) {
+        own.add(vulnerabilityKey(resolvedName, version, edge.depPath))
+      }
+      appendNamedDepPaths(children, pkgSnapshot.dependencies ?? {})
+      if (includeOptDeps) {
+        appendNamedDepPaths(children, pkgSnapshot.optionalDependencies ?? {})
+      }
 }
-    for (const child of resolvedDepsToNamedDepPaths(pkgSnapshot.dependencies ?? {})) {
-      collect(child)
+    partial.set(edge.depPath, own)
+
+    for (const child of children) {
+      if (!index.has(child.depPath)) {
+        strongconnect(child)
+        lowlink.set(edge.depPath, Math.min(lowlink.get(edge.depPath)!, lowlink.get(child.depPath)!))
+      } else if (onStack.has(child.depPath)) {
+        lowlink.set(edge.depPath, Math.min(lowlink.get(edge.depPath)!, index.get(child.depPath)!))
+      }

Evidence
PR Compliance ID 2 requires the reachability/saturation pruning logic not to degrade on
lockfile-specific graph shapes. The new implementation performs recursive DFS
(strongconnect(child)), and deep graphs from untrusted lockfiles can exceed the JS call stack
limit, causing a crash/DoS and breaking the intended bounded performance behavior.
Audit reachability/saturation pruning does not degrade performance on lockfile-specific graphs
deps/compliance/audit/src/lockfileToAuditIndex.ts[260-291]
REVIEW_GUIDE.md[30-60]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`createReachableVulnerabilitiesGetter()` implements Tarjan SCC with recursive DFS (`strongconnect()`), which risks call-stack overflow on deep lockfile graphs (lockfiles are attacker-controlled input). This can crash `pnpm audit` (DoS) on certain lockfile shapes instead of keeping traversal bounded.
## Issue Context
The compliance requirement is to avoid lockfile-shape-specific regressions/slowdowns; crashing due to stack overflow is a severe regression for deep graphs.
## Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[260-291]

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

2. Spread push argument overflow 🐞 Bug ⛨ Security

Description

In createReachableVulnerabilitiesGetter(), children.push(...resolvedDepsToNamedDepPaths(...))
spreads an attacker-controlled dependency list into function arguments; sufficiently large lists can
exceed the JS engine argument limit and throw, failing pnpm audit (DoS). This was avoidable
because a simple loop/concat appends children without argument expansion.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R278-281]

+      children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.dependencies ?? {}))
+      if (includeOptDeps) {
+        children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.optionalDependencies ?? {}))
+      }

Evidence

The new Tarjan implementation appends dependency edges using spread into push, which can throw on
large arrays. The repo’s review guide explicitly treats lockfiles as attacker-controlled input,
making this a plausible DoS vector when auditing untrusted/project-supplied lockfiles.

deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
REVIEW_GUIDE.md[30-35]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`children.push(...array)` expands the array into positional arguments. With attacker-controlled lockfile/package snapshot data, a very large dependency list can exceed the engine’s max argument count and throw, causing `pnpm audit` to fail (denial of service).
## Issue Context
This is in the new Tarjan SCC reachability computation path. The review guide treats lockfiles as attacker-controlled input, so crashing on pathological shapes is a security/reliability concern.
## Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
## Suggested fix
Replace the spread-based appends with a safe append strategy that doesn’t expand into arguments, e.g.:
- iterate and `children.push(child)` in a `for...of`, or
- use `children = children.concat(resolvedDepsToNamedDepPaths(...))` (or push in a loop) for both dependencies and optionalDependencies.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

3. Extra reachable-set copying 🐞 Bug ➹ Performance

Description

When an SCC closes, the code always allocates a new shared Set and copies each member’s partial
Set into it, including the common singleton-SCC case. This adds an extra full Set
traversal/allocation per SCC and can increase CPU/GC overhead on large lockfiles where most nodes
are not in cycles.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R300-313]

+    if (lowlink.get(edge.depPath) === idx) {
+      const shared = new Set<string>()
+      const members: DepPath[] = []
+      let member: DepPath
+      do {
+        member = sccStack.pop()!
+        onStack.delete(member)
+        members.push(member)
+        addAll(shared, partial.get(member)!)
+        partial.delete(member)
+      } while (member !== edge.depPath)
+      for (const m of members) {
+        memo.set(m, shared)
}

Evidence

The new Tarjan implementation stores each node’s accumulated reachable vulnerabilities in partial
(partial.set(edge.depPath, own)) and then, on SCC close, creates a fresh shared Set and unions
every member’s partial Set into it via addAll. For SCC size 1, this is a full extra copy of the
reachable Set that wasn’t necessary.

deps/compliance/audit/src/lockfileToAuditIndex.ts[272-313]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`createReachableVulnerabilitiesGetter()` builds an `own` Set per node and stores it in `partial`. When an SCC closes, it always creates a new `shared` Set and copies (`addAll`) every member’s partial Set into it. For singleton SCCs (the typical case in mostly-acyclic graphs), this adds an avoidable extra allocation and full iteration over the node’s reachable set.
### Issue Context
This code runs on the `pnpm audit` path-walk hot path. Even though Tarjan fixes the asymptotic cycle blow-up, this SCC-finalization copy is a constant-factor overhead that can matter on large lockfiles.
### Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[300-313]
### Suggested fix approach
- Avoid copying for singleton SCCs: if the SCC has only one member, directly `memo.set(member, partial.get(member)!)` and delete from `partial`.
- For multi-member SCCs, reuse one member’s Set as the `shared` accumulator (pick the first popped member’s partial Set as `shared`, then `addAll(shared, otherPartial)`), then set `memo` for all members to that same Set.
- Keep the invariant that successors outside the SCC are already merged into each member’s partial Set before SCC close.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

Previous review results

Review updated until commit f52aa6b

Results up to commit f52aa6b

🐞 Bugs (2) 📘 Rule violations (0) 📎 Requirement gaps (1) 📜 Skill insights (0)

Context used

✅ Tickets: 🎫 pnpm audit is ~6x slower in 11.5.1+ than 11.4.0 on a large monorepo

1. strongconnect() recursion stack overflow 📎 Requirement gap ⛨ Security

Description

createReachableVulnerabilitiesGetter() uses a recursive Tarjan DFS (strongconnect() calls
itself), which can overflow the JS call stack on sufficiently deep (but valid) dependency graphs
derived from attacker-controlled lockfiles, crashing pnpm audit (DoS) instead of completing
efficiently.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R260-291]

+  const strongconnect = (edge: { name: string, depPath: DepPath }): void => {
+    const idx = counter++
+    index.set(edge.depPath, idx)
+    lowlink.set(edge.depPath, idx)
+    sccStack.push(edge.depPath)
  onStack.add(edge.depPath)
-    const result = new Set<string>()
-    let complete = true
-    const { name, version } = nameVerFromPkgSnapshot(edge.depPath, pkgSnapshot)
-    const resolvedName = name ?? edge.name
-    if (version && vulnerableNames.has(resolvedName)) {
-      result.add(vulnerabilityKey(resolvedName, version, edge.depPath))
-    }
-    const collect = (child: { name: string, depPath: DepPath }): void => {
-      const childResult = compute(child)
-      addAll(result, childResult.result)
-      if (!childResult.complete) complete = false
+
+    // Derive children from this single read rather than via a helper that would
+    // read the snapshot again.
+    const pkgSnapshot = packages[edge.depPath]
+    const own = new Set<string>()
+    const children: Array<{ name: string, depPath: DepPath }> = []
+    if (pkgSnapshot != null) {
+      const { name, version } = nameVerFromPkgSnapshot(edge.depPath, pkgSnapshot)
+      const resolvedName = name ?? edge.name
+      if (version && vulnerableNames.has(resolvedName)) {
+        own.add(vulnerabilityKey(resolvedName, version, edge.depPath))
+      }
+      appendNamedDepPaths(children, pkgSnapshot.dependencies ?? {})
+      if (includeOptDeps) {
+        appendNamedDepPaths(children, pkgSnapshot.optionalDependencies ?? {})
+      }
  }
-    for (const child of resolvedDepsToNamedDepPaths(pkgSnapshot.dependencies ?? {})) {
-      collect(child)
+    partial.set(edge.depPath, own)
+
+    for (const child of children) {
+      if (!index.has(child.depPath)) {
+        strongconnect(child)
+        lowlink.set(edge.depPath, Math.min(lowlink.get(edge.depPath)!, lowlink.get(child.depPath)!))
+      } else if (onStack.has(child.depPath)) {
+        lowlink.set(edge.depPath, Math.min(lowlink.get(edge.depPath)!, index.get(child.depPath)!))
+      }

Evidence
PR Compliance ID 2 requires the reachability/saturation pruning logic not to degrade on
lockfile-specific graph shapes. The new implementation performs recursive DFS
(strongconnect(child)), and deep graphs from untrusted lockfiles can exceed the JS call stack
limit, causing a crash/DoS and breaking the intended bounded performance behavior.
Audit reachability/saturation pruning does not degrade performance on lockfile-specific graphs
deps/compliance/audit/src/lockfileToAuditIndex.ts[260-291]
REVIEW_GUIDE.md[30-60]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`createReachableVulnerabilitiesGetter()` implements Tarjan SCC with recursive DFS (`strongconnect()`), which risks call-stack overflow on deep lockfile graphs (lockfiles are attacker-controlled input). This can crash `pnpm audit` (DoS) on certain lockfile shapes instead of keeping traversal bounded.
## Issue Context
The compliance requirement is to avoid lockfile-shape-specific regressions/slowdowns; crashing due to stack overflow is a severe regression for deep graphs.
## Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[260-291]

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

2. Spread push argument overflow 🐞 Bug ⛨ Security

Description

In createReachableVulnerabilitiesGetter(), children.push(...resolvedDepsToNamedDepPaths(...))
spreads an attacker-controlled dependency list into function arguments; sufficiently large lists can
exceed the JS engine argument limit and throw, failing pnpm audit (DoS). This was avoidable
because a simple loop/concat appends children without argument expansion.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R278-281]

+      children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.dependencies ?? {}))
+      if (includeOptDeps) {
+        children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.optionalDependencies ?? {}))
+      }

Evidence

The new Tarjan implementation appends dependency edges using spread into push, which can throw on
large arrays. The repo’s review guide explicitly treats lockfiles as attacker-controlled input,
making this a plausible DoS vector when auditing untrusted/project-supplied lockfiles.

deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
REVIEW_GUIDE.md[30-35]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`children.push(...array)` expands the array into positional arguments. With attacker-controlled lockfile/package snapshot data, a very large dependency list can exceed the engine’s max argument count and throw, causing `pnpm audit` to fail (denial of service).
## Issue Context
This is in the new Tarjan SCC reachability computation path. The review guide treats lockfiles as attacker-controlled input, so crashing on pathological shapes is a security/reliability concern.
## Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
## Suggested fix
Replace the spread-based appends with a safe append strategy that doesn’t expand into arguments, e.g.:
- iterate and `children.push(child)` in a `for...of`, or
- use `children = children.concat(resolvedDepsToNamedDepPaths(...))` (or push in a loop) for both dependencies and optionalDependencies.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

3. Extra reachable-set copying 🐞 Bug ➹ Performance

Description

When an SCC closes, the code always allocates a new shared Set and copies each member’s partial
Set into it, including the common singleton-SCC case. This adds an extra full Set
traversal/allocation per SCC and can increase CPU/GC overhead on large lockfiles where most nodes
are not in cycles.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R300-313]

+    if (lowlink.get(edge.depPath) === idx) {
+      const shared = new Set<string>()
+      const members: DepPath[] = []
+      let member: DepPath
+      do {
+        member = sccStack.pop()!
+        onStack.delete(member)
+        members.push(member)
+        addAll(shared, partial.get(member)!)
+        partial.delete(member)
+      } while (member !== edge.depPath)
+      for (const m of members) {
+        memo.set(m, shared)
 }

Evidence

The new Tarjan implementation stores each node’s accumulated reachable vulnerabilities in partial
(partial.set(edge.depPath, own)) and then, on SCC close, creates a fresh shared Set and unions
every member’s partial Set into it via addAll. For SCC size 1, this is a full extra copy of the
reachable Set that wasn’t necessary.

deps/compliance/audit/src/lockfileToAuditIndex.ts[272-313]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`createReachableVulnerabilitiesGetter()` builds an `own` Set per node and stores it in `partial`. When an SCC closes, it always creates a new `shared` Set and copies (`addAll`) every member’s partial Set into it. For singleton SCCs (the typical case in mostly-acyclic graphs), this adds an avoidable extra allocation and full iteration over the node’s reachable set.
### Issue Context
This code runs on the `pnpm audit` path-walk hot path. Even though Tarjan fixes the asymptotic cycle blow-up, this SCC-finalization copy is a constant-factor overhead that can matter on large lockfiles.
### Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[300-313]
### Suggested fix approach
- Avoid copying for singleton SCCs: if the SCC has only one member, directly `memo.set(member, partial.get(member)!)` and delete from `partial`.
- For multi-member SCCs, reuse one member’s Set as the `shared` accumulator (pick the first popped member’s partial Set as `shared`, then `addAll(shared, otherPartial)`), then set `memo` for all members to that same Set.
- Keep the invariant that successors outside the SCC are already merged into each member’s partial Set before SCC close.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

Results up to commit 07f8246

🐞 Bugs (2) 📘 Rule violations (0) 📎 Requirement gaps (1) 📜 Skill insights (0)

Context used

✅ Tickets: 🎫 pnpm audit is ~6x slower in 11.5.1+ than 11.4.0 on a large monorepo

1. strongconnect() recursion stack overflow 📎 Requirement gap ⛨ Security

Description

createReachableVulnerabilitiesGetter() uses a recursive Tarjan DFS (strongconnect() calls
itself), which can overflow the JS call stack on sufficiently deep (but valid) dependency graphs
derived from attacker-controlled lockfiles, crashing pnpm audit (DoS) instead of completing
efficiently.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R260-291]

+  const strongconnect = (edge: { name: string, depPath: DepPath }): void => {
+    const idx = counter++
+    index.set(edge.depPath, idx)
+    lowlink.set(edge.depPath, idx)
+    sccStack.push(edge.depPath)
   onStack.add(edge.depPath)
-    const result = new Set<string>()
-    let complete = true
-    const { name, version } = nameVerFromPkgSnapshot(edge.depPath, pkgSnapshot)
-    const resolvedName = name ?? edge.name
-    if (version && vulnerableNames.has(resolvedName)) {
-      result.add(vulnerabilityKey(resolvedName, version, edge.depPath))
-    }
-    const collect = (child: { name: string, depPath: DepPath }): void => {
-      const childResult = compute(child)
-      addAll(result, childResult.result)
-      if (!childResult.complete) complete = false
+
+    // Derive children from this single read rather than via a helper that would
+    // read the snapshot again.
+    const pkgSnapshot = packages[edge.depPath]
+    const own = new Set<string>()
+    const children: Array<{ name: string, depPath: DepPath }> = []
+    if (pkgSnapshot != null) {
+      const { name, version } = nameVerFromPkgSnapshot(edge.depPath, pkgSnapshot)
+      const resolvedName = name ?? edge.name
+      if (version && vulnerableNames.has(resolvedName)) {
+        own.add(vulnerabilityKey(resolvedName, version, edge.depPath))
+      }
+      appendNamedDepPaths(children, pkgSnapshot.dependencies ?? {})
+      if (includeOptDeps) {
+        appendNamedDepPaths(children, pkgSnapshot.optionalDependencies ?? {})
+      }
   }
-    for (const child of resolvedDepsToNamedDepPaths(pkgSnapshot.dependencies ?? {})) {
-      collect(child)
+    partial.set(edge.depPath, own)
+
+    for (const child of children) {
+      if (!index.has(child.depPath)) {
+        strongconnect(child)
+        lowlink.set(edge.depPath, Math.min(lowlink.get(edge.depPath)!, lowlink.get(child.depPath)!))
+      } else if (onStack.has(child.depPath)) {
+        lowlink.set(edge.depPath, Math.min(lowlink.get(edge.depPath)!, index.get(child.depPath)!))
+      }

Evidence
PR Compliance ID 2 requires the reachability/saturation pruning logic not to degrade on
lockfile-specific graph shapes. The new implementation performs recursive DFS
(strongconnect(child)), and deep graphs from untrusted lockfiles can exceed the JS call stack
limit, causing a crash/DoS and breaking the intended bounded performance behavior.
Audit reachability/saturation pruning does not degrade performance on lockfile-specific graphs
deps/compliance/audit/src/lockfileToAuditIndex.ts[260-291]
REVIEW_GUIDE.md[30-60]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`createReachableVulnerabilitiesGetter()` implements Tarjan SCC with recursive DFS (`strongconnect()`), which risks call-stack overflow on deep lockfile graphs (lockfiles are attacker-controlled input). This can crash `pnpm audit` (DoS) on certain lockfile shapes instead of keeping traversal bounded.
## Issue Context
The compliance requirement is to avoid lockfile-shape-specific regressions/slowdowns; crashing due to stack overflow is a severe regression for deep graphs.
## Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[260-291]

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

2. Spread push argument overflow 🐞 Bug ⛨ Security

Description

In createReachableVulnerabilitiesGetter(), children.push(...resolvedDepsToNamedDepPaths(...))
spreads an attacker-controlled dependency list into function arguments; sufficiently large lists can
exceed the JS engine argument limit and throw, failing pnpm audit (DoS). This was avoidable
because a simple loop/concat appends children without argument expansion.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R278-281]

+      children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.dependencies ?? {}))
+      if (includeOptDeps) {
+        children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.optionalDependencies ?? {}))
+      }

Evidence

The new Tarjan implementation appends dependency edges using spread into push, which can throw on
large arrays. The repo’s review guide explicitly treats lockfiles as attacker-controlled input,
making this a plausible DoS vector when auditing untrusted/project-supplied lockfiles.

deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
REVIEW_GUIDE.md[30-35]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`children.push(...array)` expands the array into positional arguments. With attacker-controlled lockfile/package snapshot data, a very large dependency list can exceed the engine’s max argument count and throw, causing `pnpm audit` to fail (denial of service).
## Issue Context
This is in the new Tarjan SCC reachability computation path. The review guide treats lockfiles as attacker-controlled input, so crashing on pathological shapes is a security/reliability concern.
## Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
## Suggested fix
Replace the spread-based appends with a safe append strategy that doesn’t expand into arguments, e.g.:
- iterate and `children.push(child)` in a `for...of`, or
- use `children = children.concat(resolvedDepsToNamedDepPaths(...))` (or push in a loop) for both dependencies and optionalDependencies.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

3. Extra reachable-set copying 🐞 Bug ➹ Performance

Description

When an SCC closes, the code always allocates a new shared Set and copies each member’s partial
Set into it, including the common singleton-SCC case. This adds an extra full Set
traversal/allocation per SCC and can increase CPU/GC overhead on large lockfiles where most nodes
are not in cycles.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R300-313]

+    if (lowlink.get(edge.depPath) === idx) {
+      const shared = new Set<string>()
+      const members: DepPath[] = []
+      let member: DepPath
+      do {
+        member = sccStack.pop()!
+        onStack.delete(member)
+        members.push(member)
+        addAll(shared, partial.get(member)!)
+        partial.delete(member)
+      } while (member !== edge.depPath)
+      for (const m of members) {
+        memo.set(m, shared)
  }

Evidence

The new Tarjan implementation stores each node’s accumulated reachable vulnerabilities in partial
(partial.set(edge.depPath, own)) and then, on SCC close, creates a fresh shared Set and unions
every member’s partial Set into it via addAll. For SCC size 1, this is a full extra copy of the
reachable Set that wasn’t necessary.

deps/compliance/audit/src/lockfileToAuditIndex.ts[272-313]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`createReachableVulnerabilitiesGetter()` builds an `own` Set per node and stores it in `partial`. When an SCC closes, it always creates a new `shared` Set and copies (`addAll`) every member’s partial Set into it. For singleton SCCs (the typical case in mostly-acyclic graphs), this adds an avoidable extra allocation and full iteration over the node’s reachable set.
### Issue Context
This code runs on the `pnpm audit` path-walk hot path. Even though Tarjan fixes the asymptotic cycle blow-up, this SCC-finalization copy is a constant-factor overhead that can matter on large lockfiles.
### Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[300-313]
### Suggested fix approach
- Avoid copying for singleton SCCs: if the SCC has only one member, directly `memo.set(member, partial.get(member)!)` and delete from `partial`.
- For multi-member SCCs, reuse one member’s Set as the `shared` accumulator (pick the first popped member’s partial Set as `shared`, then `addAll(shared, otherPartial)`), then set `memo` for all members to that same Set.
- Keep the invariant that successors outside the SCC are already merged into each member’s partial Set before SCC close.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

Results up to commit 07f8246

🐞 Bugs (2) 📘 Rule violations (0) 📎 Requirement gaps (1) 📜 Skill insights (0)

Context used

✅ Tickets: 🎫 pnpm audit is ~6x slower in 11.5.1+ than 11.4.0 on a large monorepo

1. strongconnect() recursion stack overflow 📎 Requirement gap ⛨ Security ⭐ New

Description

createReachableVulnerabilitiesGetter() uses a recursive Tarjan DFS (strongconnect() calls
itself), which can overflow the JS call stack on sufficiently deep (but valid) dependency graphs
derived from attacker-controlled lockfiles, crashing pnpm audit (DoS) instead of completing
efficiently.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R260-291]

+  const strongconnect = (edge: { name: string, depPath: DepPath }): void => {
+    const idx = counter++
+    index.set(edge.depPath, idx)
+    lowlink.set(edge.depPath, idx)
+    sccStack.push(edge.depPath)
    onStack.add(edge.depPath)
-    const result = new Set<string>()
-    let complete = true
-    const { name, version } = nameVerFromPkgSnapshot(edge.depPath, pkgSnapshot)
-    const resolvedName = name ?? edge.name
-    if (version && vulnerableNames.has(resolvedName)) {
-      result.add(vulnerabilityKey(resolvedName, version, edge.depPath))
-    }
-    const collect = (child: { name: string, depPath: DepPath }): void => {
-      const childResult = compute(child)
-      addAll(result, childResult.result)
-      if (!childResult.complete) complete = false
+
+    // Derive children from this single read rather than via a helper that would
+    // read the snapshot again.
+    const pkgSnapshot = packages[edge.depPath]
+    const own = new Set<string>()
+    const children: Array<{ name: string, depPath: DepPath }> = []
+    if (pkgSnapshot != null) {
+      const { name, version } = nameVerFromPkgSnapshot(edge.depPath, pkgSnapshot)
+      const resolvedName = name ?? edge.name
+      if (version && vulnerableNames.has(resolvedName)) {
+        own.add(vulnerabilityKey(resolvedName, version, edge.depPath))
+      }
+      appendNamedDepPaths(children, pkgSnapshot.dependencies ?? {})
+      if (includeOptDeps) {
+        appendNamedDepPaths(children, pkgSnapshot.optionalDependencies ?? {})
+      }
    }
-    for (const child of resolvedDepsToNamedDepPaths(pkgSnapshot.dependencies ?? {})) {
-      collect(child)
+    partial.set(edge.depPath, own)
+
+    for (const child of children) {
+      if (!index.has(child.depPath)) {
+        strongconnect(child)
+        lowlink.set(edge.depPath, Math.min(lowlink.get(edge.depPath)!, lowlink.get(child.depPath)!))
+      } else if (onStack.has(child.depPath)) {
+        lowlink.set(edge.depPath, Math.min(lowlink.get(edge.depPath)!, index.get(child.depPath)!))
+      }

Evidence
PR Compliance ID 2 requires the reachability/saturation pruning logic not to degrade on
lockfile-specific graph shapes. The new implementation performs recursive DFS
(strongconnect(child)), and deep graphs from untrusted lockfiles can exceed the JS call stack
limit, causing a crash/DoS and breaking the intended bounded performance behavior.
Audit reachability/saturation pruning does not degrade performance on lockfile-specific graphs
deps/compliance/audit/src/lockfileToAuditIndex.ts[260-291]
REVIEW_GUIDE.md[30-60]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`createReachableVulnerabilitiesGetter()` implements Tarjan SCC with recursive DFS (`strongconnect()`), which risks call-stack overflow on deep lockfile graphs (lockfiles are attacker-controlled input). This can crash `pnpm audit` (DoS) on certain lockfile shapes instead of keeping traversal bounded.

## Issue Context
The compliance requirement is to avoid lockfile-shape-specific regressions/slowdowns; crashing due to stack overflow is a severe regression for deep graphs.

## Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[260-291]

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

2. Spread push argument overflow 🐞 Bug ⛨ Security

Description

In createReachableVulnerabilitiesGetter(), children.push(...resolvedDepsToNamedDepPaths(...))
spreads an attacker-controlled dependency list into function arguments; sufficiently large lists can
exceed the JS engine argument limit and throw, failing pnpm audit (DoS). This was avoidable
because a simple loop/concat appends children without argument expansion.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R278-281]

+      children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.dependencies ?? {}))
+      if (includeOptDeps) {
+        children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.optionalDependencies ?? {}))
+      }

Evidence

The new Tarjan implementation appends dependency edges using spread into push, which can throw on
large arrays. The repo’s review guide explicitly treats lockfiles as attacker-controlled input,
making this a plausible DoS vector when auditing untrusted/project-supplied lockfiles.

deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
REVIEW_GUIDE.md[30-35]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`children.push(...array)` expands the array into positional arguments. With attacker-controlled lockfile/package snapshot data, a very large dependency list can exceed the engine’s max argument count and throw, causing `pnpm audit` to fail (denial of service).
## Issue Context
This is in the new Tarjan SCC reachability computation path. The review guide treats lockfiles as attacker-controlled input, so crashing on pathological shapes is a security/reliability concern.
## Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
## Suggested fix
Replace the spread-based appends with a safe append strategy that doesn’t expand into arguments, e.g.:
- iterate and `children.push(child)` in a `for...of`, or
- use `children = children.concat(resolvedDepsToNamedDepPaths(...))` (or push in a loop) for both dependencies and optionalDependencies.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

3. Extra reachable-set copying 🐞 Bug ➹ Performance

Description

When an SCC closes, the code always allocates a new shared Set and copies each member’s partial
Set into it, including the common singleton-SCC case. This adds an extra full Set
traversal/allocation per SCC and can increase CPU/GC overhead on large lockfiles where most nodes
are not in cycles.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R300-313]

+    if (lowlink.get(edge.depPath) === idx) {
+      const shared = new Set<string>()
+      const members: DepPath[] = []
+      let member: DepPath
+      do {
+        member = sccStack.pop()!
+        onStack.delete(member)
+        members.push(member)
+        addAll(shared, partial.get(member)!)
+        partial.delete(member)
+      } while (member !== edge.depPath)
+      for (const m of members) {
+        memo.set(m, shared)
   }

Evidence

The new Tarjan implementation stores each node’s accumulated reachable vulnerabilities in partial
(partial.set(edge.depPath, own)) and then, on SCC close, creates a fresh shared Set and unions
every member’s partial Set into it via addAll. For SCC size 1, this is a full extra copy of the
reachable Set that wasn’t necessary.

deps/compliance/audit/src/lockfileToAuditIndex.ts[272-313]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`createReachableVulnerabilitiesGetter()` builds an `own` Set per node and stores it in `partial`. When an SCC closes, it always creates a new `shared` Set and copies (`addAll`) every member’s partial Set into it. For singleton SCCs (the typical case in mostly-acyclic graphs), this adds an avoidable extra allocation and full iteration over the node’s reachable set.
### Issue Context
This code runs on the `pnpm audit` path-walk hot path. Even though Tarjan fixes the asymptotic cycle blow-up, this SCC-finalization copy is a constant-factor overhead that can matter on large lockfiles.
### Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[300-313]
### Suggested fix approach
- Avoid copying for singleton SCCs: if the SCC has only one member, directly `memo.set(member, partial.get(member)!)` and delete from `partial`.
- For multi-member SCCs, reuse one member’s Set as the `shared` accumulator (pick the first popped member’s partial Set as `shared`, then `addAll(shared, otherPartial)`), then set `memo` for all members to that same Set.
- Keep the invariant that successors outside the SCC are already merged into each member’s partial Set before SCC close.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

Results up to commit 977230b

🐞 Bugs (2) 📘 Rule violations (0) 📎 Requirement gaps (0) 📜 Skill insights (0)

Context used

✅ Tickets: 🎫 pnpm audit is ~6x slower in 11.5.1+ than 11.4.0 on a large monorepo

1. Spread push argument overflow 🐞 Bug ⛨ Security

Description

In createReachableVulnerabilitiesGetter(), children.push(...resolvedDepsToNamedDepPaths(...))
spreads an attacker-controlled dependency list into function arguments; sufficiently large lists can
exceed the JS engine argument limit and throw, failing pnpm audit (DoS). This was avoidable
because a simple loop/concat appends children without argument expansion.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R278-281]

+      children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.dependencies ?? {}))
+      if (includeOptDeps) {
+        children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.optionalDependencies ?? {}))
+      }

Evidence

The new Tarjan implementation appends dependency edges using spread into push, which can throw on
large arrays. The repo’s review guide explicitly treats lockfiles as attacker-controlled input,
making this a plausible DoS vector when auditing untrusted/project-supplied lockfiles.

deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
REVIEW_GUIDE.md[30-35]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`children.push(...array)` expands the array into positional arguments. With attacker-controlled lockfile/package snapshot data, a very large dependency list can exceed the engine’s max argument count and throw, causing `pnpm audit` to fail (denial of service).
## Issue Context
This is in the new Tarjan SCC reachability computation path. The review guide treats lockfiles as attacker-controlled input, so crashing on pathological shapes is a security/reliability concern.
## Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
## Suggested fix
Replace the spread-based appends with a safe append strategy that doesn’t expand into arguments, e.g.:
- iterate and `children.push(child)` in a `for...of`, or
- use `children = children.concat(resolvedDepsToNamedDepPaths(...))` (or push in a loop) for both dependencies and optionalDependencies.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

2. Extra reachable-set copying 🐞 Bug ➹ Performance

Description

When an SCC closes, the code always allocates a new shared Set and copies each member’s partial
Set into it, including the common singleton-SCC case. This adds an extra full Set
traversal/allocation per SCC and can increase CPU/GC overhead on large lockfiles where most nodes
are not in cycles.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R300-313]

+    if (lowlink.get(edge.depPath) === idx) {
+      const shared = new Set<string>()
+      const members: DepPath[] = []
+      let member: DepPath
+      do {
+        member = sccStack.pop()!
+        onStack.delete(member)
+        members.push(member)
+        addAll(shared, partial.get(member)!)
+        partial.delete(member)
+      } while (member !== edge.depPath)
+      for (const m of members) {
+        memo.set(m, shared)
    }

Evidence

The new Tarjan implementation stores each node’s accumulated reachable vulnerabilities in partial
(partial.set(edge.depPath, own)) and then, on SCC close, creates a fresh shared Set and unions
every member’s partial Set into it via addAll. For SCC size 1, this is a full extra copy of the
reachable Set that wasn’t necessary.

deps/compliance/audit/src/lockfileToAuditIndex.ts[272-313]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`createReachableVulnerabilitiesGetter()` builds an `own` Set per node and stores it in `partial`. When an SCC closes, it always creates a new `shared` Set and copies (`addAll`) every member’s partial Set into it. For singleton SCCs (the typical case in mostly-acyclic graphs), this adds an avoidable extra allocation and full iteration over the node’s reachable set.
### Issue Context
This code runs on the `pnpm audit` path-walk hot path. Even though Tarjan fixes the asymptotic cycle blow-up, this SCC-finalization copy is a constant-factor overhead that can matter on large lockfiles.
### Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[300-313]
### Suggested fix approach
- Avoid copying for singleton SCCs: if the SCC has only one member, directly `memo.set(member, partial.get(member)!)` and delete from `partial`.
- For multi-member SCCs, reuse one member’s Set as the `shared` accumulator (pick the first popped member’s partial Set as `shared`, then `addAll(shared, otherPartial)`), then set `memo` for all members to that same Set.
- Keep the invariant that successors outside the SCC are already merged into each member’s partial Set before SCC close.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

Results up to commit 977230b

🐞 Bugs (2) 📘 Rule violations (0) 📎 Requirement gaps (0) 📜 Skill insights (0)

Context used

✅ Tickets: 🎫 pnpm audit is ~6x slower in 11.5.1+ than 11.4.0 on a large monorepo

1. Spread push argument overflow 🐞 Bug ⛨ Security ⭐ New

Description

In createReachableVulnerabilitiesGetter(), children.push(...resolvedDepsToNamedDepPaths(...))
spreads an attacker-controlled dependency list into function arguments; sufficiently large lists can
exceed the JS engine argument limit and throw, failing pnpm audit (DoS). This was avoidable
because a simple loop/concat appends children without argument expansion.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R278-281]

+      children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.dependencies ?? {}))
+      if (includeOptDeps) {
+        children.push(...resolvedDepsToNamedDepPaths(pkgSnapshot.optionalDependencies ?? {}))
+      }

Evidence

The new Tarjan implementation appends dependency edges using spread into push, which can throw on
large arrays. The repo’s review guide explicitly treats lockfiles as attacker-controlled input,
making this a plausible DoS vector when auditing untrusted/project-supplied lockfiles.

deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]
REVIEW_GUIDE.md[30-35]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`children.push(...array)` expands the array into positional arguments. With attacker-controlled lockfile/package snapshot data, a very large dependency list can exceed the engine’s max argument count and throw, causing `pnpm audit` to fail (denial of service).

## Issue Context
This is in the new Tarjan SCC reachability computation path. The review guide treats lockfiles as attacker-controlled input, so crashing on pathological shapes is a security/reliability concern.

## Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[267-282]

## Suggested fix
Replace the spread-based appends with a safe append strategy that doesn’t expand into arguments, e.g.:
- iterate and `children.push(child)` in a `for...of`, or
- use `children = children.concat(resolvedDepsToNamedDepPaths(...))` (or push in a loop) for both dependencies and optionalDependencies.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

2. Extra reachable-set copying 🐞 Bug ➹ Performance

Description

When an SCC closes, the code always allocates a new shared Set and copies each member’s partial
Set into it, including the common singleton-SCC case. This adds an extra full Set
traversal/allocation per SCC and can increase CPU/GC overhead on large lockfiles where most nodes
are not in cycles.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R300-313]

+    if (lowlink.get(edge.depPath) === idx) {
+      const shared = new Set<string>()
+      const members: DepPath[] = []
+      let member: DepPath
+      do {
+        member = sccStack.pop()!
+        onStack.delete(member)
+        members.push(member)
+        addAll(shared, partial.get(member)!)
+        partial.delete(member)
+      } while (member !== edge.depPath)
+      for (const m of members) {
+        memo.set(m, shared)
     }

Evidence

The new Tarjan implementation stores each node’s accumulated reachable vulnerabilities in partial
(partial.set(edge.depPath, own)) and then, on SCC close, creates a fresh shared Set and unions
every member’s partial Set into it via addAll. For SCC size 1, this is a full extra copy of the
reachable Set that wasn’t necessary.

deps/compliance/audit/src/lockfileToAuditIndex.ts[272-313]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`createReachableVulnerabilitiesGetter()` builds an `own` Set per node and stores it in `partial`. When an SCC closes, it always creates a new `shared` Set and copies (`addAll`) every member’s partial Set into it. For singleton SCCs (the typical case in mostly-acyclic graphs), this adds an avoidable extra allocation and full iteration over the node’s reachable set.
### Issue Context
This code runs on the `pnpm audit` path-walk hot path. Even though Tarjan fixes the asymptotic cycle blow-up, this SCC-finalization copy is a constant-factor overhead that can matter on large lockfiles.
### Fix Focus Areas
- deps/compliance/audit/src/lockfileToAuditIndex.ts[300-313]
### Suggested fix approach
- Avoid copying for singleton SCCs: if the SCC has only one member, directly `memo.set(member, partial.get(member)!)` and delete from `partial`.
- For multi-member SCCs, reuse one member’s Set as the `shared` accumulator (pick the first popped member’s partial Set as `shared`, then `addAll(shared, otherPartial)`), then set `memo` for all members to that same Set.
- Keep the invariant that successors outside the SCC are already merged into each member’s partial Set before SCC close.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

Results up to commit 490c73f

🐞 Bugs (1) 📘 Rule violations (0) 📎 Requirement gaps (0) 📜 Skill insights (0)

Context used

✅ Tickets: 🎫 pnpm audit is ~6x slower in 11.5.1+ than 11.4.0 on a large monorepo

1. Extra reachable-set copying 🐞 Bug ➹ Performance

Description

When an SCC closes, the code always allocates a new shared Set and copies each member’s partial
Set into it, including the common singleton-SCC case. This adds an extra full Set
traversal/allocation per SCC and can increase CPU/GC overhead on large lockfiles where most nodes
are not in cycles.

Code

deps/compliance/audit/src/lockfileToAuditIndex.ts[R300-313]

+    if (lowlink.get(edge.depPath) === idx) {
+      const shared = new Set<string>()
+      const members: DepPath[] = []
+      let member: DepPath
+     ...

Copilot

Pull request overview

Note

Copilot was unable to run its full agentic suite in this review.

Improves pnpm audit performance on cyclic lockfiles by switching reachability computation to a linear-time SCC approach and adds a regression test to guard against quadratic behavior.

Changes:

Compute reachable vulnerabilities using Tarjan’s strongly-connected-components algorithm to avoid quadratic recomputation on cycles.
Add a performance/correctness regression test that constructs a large cyclic dependency graph.
Add a changeset documenting the patch release fix.

Reviewed changes

Copilot reviewed 3 out of 3 changed files in this pull request and generated 3 comments.

File	Description
deps/compliance/audit/src/lockfileToAuditIndex.ts	Replaces cycle-prone reachability memoization with SCC-based reachability sets shared across cycles.
deps/compliance/audit/test/index.ts	Adds a regression test to ensure cyclic graphs are scanned a bounded number of times and paths remain correct.
.changeset/fix-audit-cyclic-path-traversal-perf.md	Documents the performance regression fix and release impact.

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

qodo-free-for-open-source-projects · 2026-06-17T08:38:05Z

Code review by qodo was updated up to the latest commit e68ea52

Copilot

Pull request overview

Copilot reviewed 4 out of 4 changed files in this pull request and generated 1 comment.

qodo-free-for-open-source-projects · 2026-06-17T08:44:15Z

Code review by qodo was updated up to the latest commit adbfaa8

qodo-free-for-open-source-projects · 2026-06-17T08:53:26Z

Code review by qodo was updated up to the latest commit 7ab65ad

Copilot

Pull request overview

Copilot reviewed 4 out of 4 changed files in this pull request and generated 2 comments.

coderabbitai · 2026-06-17T09:17:55Z

Note

Reviews paused

It looks like this branch is under active development. To avoid overwhelming you with review comments due to an influx of new commits, CodeRabbit has automatically paused this review. You can configure this behavior by changing the reviews.auto_review.auto_pause_after_reviewed_commits setting.

Use the following commands to manage reviews:

@coderabbitai resume to resume automatic reviews.
@coderabbitai review to trigger a single review.

Use the checkboxes below for quick actions:

▶️ Resume reviews
🔍 Trigger review

📝 Walkthrough

Walkthrough

Replaces the reachability memoization logic inside createReachableVulnerabilitiesGetter with Tarjan's strongly-connected-components algorithm, computing one shared reachable-vulnerabilities set per SCC instead of recomputing per edge. Converts recursive traversals in makeVisitor, walkForPaths, and walkReachable to iterative stack-based implementations to prevent call-stack overflow on deeply nested graphs. Introduces appendNamedDepPaths helper to reduce large array spread operations. Adds sub-quadratic scalability and deep-chain regression tests, changeset entry, and spell-check words.

Changes

Tarjan SCC reachability fix for audit cycle performance

Layer / File(s)	Summary
Tarjan SCC algorithm and reachability refactor `deps/compliance/audit/src/lockfileToAuditIndex.ts`	Replaces per-edge reachability memoization with iterative Tarjan SCC algorithm that computes a single shared `ReadonlySet<string>` per SCC and memoizes it across all SCC members. Updates `allReachableVulnerabilitiesSaturated` parameter type from `Set<string>` to `ReadonlySet<string>`. Eliminates quadratic recomputation on cyclic subgraphs and ancestors.
Non-recursive graph traversals and helpers `deps/compliance/audit/src/lockfileToAuditIndex.ts`	Converts `makeVisitor`, `walkForPaths`, and `walkReachable` from recursive calls to explicit frame-stack loops to avoid call-stack overflow. Introduces `appendNamedDepPaths(target, deps)` helper that appends dependency entries in a loop instead of returning spread-constructed arrays, reducing engine argument-limit risk.
Scalability and deep-chain regression tests `deps/compliance/audit/test/index.ts`	New Jest tests synthesize large cyclic and deeply nested lockfiles, validate vulnerable leaf paths are correct, and verify sub-quadratic read-count growth (ratio < 3 for cycle size doubling) and stack-safe traversal of tens of thousands of nodes.
Changeset and spell-check dictionary updates `.changeset/fix-audit-cyclic-path-traversal-perf.md`, `cspell.json`	Adds `.changeset` entry with patch releases for `@pnpm/deps.compliance.audit` and `pnpm` documenting SCC-based audit performance fix. Adds `"lowlink"`, `"strongconnect"`, and `"Tarjan"` to cspell word allowlist.

Sequence Diagram

sequenceDiagram
  participant Caller
  participant createReachableVulnerabilitiesGetter
  participant strongconnect
  participant sccReachable as SCC shared set

  Caller->>createReachableVulnerabilitiesGetter: getReachable(node)
  createReachableVulnerabilitiesGetter->>strongconnect: visit(node, index, lowlink)
  strongconnect->>strongconnect: iterate neighbors via explicit stack
  strongconnect-->>sccReachable: fold member vulnerabilities into shared set
  strongconnect-->>createReachableVulnerabilitiesGetter: memoize set for each SCC member
  createReachableVulnerabilitiesGetter-->>Caller: ReadonlySet<string>
  Caller->>allReachableVulnerabilitiesSaturated: check(ReadonlySet<string>)

Estimated code review effort

🎯 3 (Moderate) | ⏱️ ~25 minutes

Assessment against linked issues

Objective	Addressed	Explanation
Fix the ~6x performance regression in `pnpm audit` on lockfiles with cyclic dependencies introduced in 11.5.1 [`#12212`]	✅	Tarjan SCC algorithm replaces quadratic per-edge reachability recomputation with linear per-SCC computation, directly eliminating the repeated traversal of cyclic subgraphs and their ancestors that caused the 6x slowdown.

Possibly related PRs

pnpm/pnpm#12087: Introduced the reachability memoization and saturation-based pruning logic that this PR replaces with the Tarjan SCC implementation to fix the resulting performance regression.

Suggested reviewers

zkochan

🚥 Pre-merge checks | ✅ 5

✅ Passed checks (5 passed)

Check name	Status	Explanation
Description Check	✅ Passed	Check skipped - CodeRabbit’s high-level summary is enabled.
Title check	✅ Passed	The PR title follows Conventional Commits specification with 'fix:' prefix and clearly describes the main change: computing reachable vulnerabilities using Tarjan SCC algorithm.
Linked Issues check	✅ Passed	The PR fully addresses issue `#12212` by restoring linear-time performance in pnpm audit on cyclic dependency graphs while preserving the path-pruning optimization, with regression tests confirming sub-quadratic scaling.
Out of Scope Changes check	✅ Passed	All changes are directly scoped to fixing the audit performance regression: algorithm implementation, configuration updates, and regression testing. No unrelated modifications detected.
Docstring Coverage	✅ Passed	No functions found in the changed files to evaluate docstring coverage. Skipping docstring coverage check.

_{✏️ Tip: You can configure your own custom pre-merge checks in the settings.}

✨ Finishing Touches

🧪 Generate unit tests (beta)

Create PR with unit tests

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

_{Comment @coderabbitai help to get the list of available commands and usage tips.}

qodo-free-for-open-source-projects · 2026-06-20T00:48:33Z

Code review by qodo was updated up to the latest commit 490c73f

qodo-free-for-open-source-projects · 2026-06-20T00:51:37Z

Code review by qodo was updated up to the latest commit 490c73f

Copilot

Copilot was unable to review this pull request because the user who requested the review has reached their quota limit.

qodo-free-for-open-source-projects · 2026-06-20T10:03:52Z

Code review by qodo was updated up to the latest commit 977230b

qodo-free-for-open-source-projects · 2026-06-20T10:07:50Z

Code review by qodo was updated up to the latest commit 977230b

qodo-free-for-open-source-projects · 2026-06-20T10:15:06Z

Code review by qodo was updated up to the latest commit 07f8246

qodo-free-for-open-source-projects · 2026-06-20T10:18:30Z

Code review by qodo was updated up to the latest commit 07f8246

Copilot

Copilot was unable to review this pull request because the user who requested the review has reached their quota limit.

qodo-free-for-open-source-projects · 2026-06-20T11:59:21Z

Code review by qodo was updated up to the latest commit f52aa6b

qodo-free-for-open-source-projects · 2026-06-20T12:03:33Z

Code review by qodo was updated up to the latest commit f52aa6b

The reachable-vulnerability pruning added in 11.5.1 (pnpm#12087) only memoized acyclic subtrees, so any node whose subtree touched a dependency cycle, and all of its ancestors, was recomputed on every query. That made the audit path walk O(N^2) on lockfiles that contain cycles, which is the common case. Reachability is now computed once per node with Tarjan's strongly-connected-components algorithm. Every member of a cycle shares one reachable set, so cyclic graphs are handled in linear time. Closes pnpm#12212 Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

`lowlink`, `strongconnect`, and `Tarjan` are used by the audit reachability fix and must be accepted by the spell checker. Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

Make the read-only contract of the reachable-vulnerability sets explicit so callers cannot mutate the shared per-SCC sets or the empty singleton. Also narrow the cyclic-scan regression test name to what it asserts. Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

Compare snapshot reads at two cycle sizes and assert the growth ratio is sub-quadratic, instead of a fixed read-count threshold. The ratio cancels the per-node constant, so the test stays robust to constant-factor changes in future linear-time refactors while still catching a quadratic regression. Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

Closing a strongly-connected component allocated a fresh set and copied every member's contribution into it, even for the common singleton-SCC case in a mostly-acyclic graph. Reuse the first popped member's own set as the shared accumulator so singleton SCCs finalize with no extra allocation or copy, trimming constant-factor overhead on the audit path walk.

After strongconnect finalizes the queried node's SCC, its reachable set is always present in the memo. The previous `?? EMPTY_REACHABLE` fallback would, if that invariant were ever broken by a future refactor, silently return an empty set — pruning valid install paths and hiding a real vulnerability. Replace the shared empty-set fallback with an explicit throw so the bug surfaces instead of under-reporting, and drop the now-unused EMPTY_REACHABLE singleton.

A lockfile is untrusted input. Building the children/roots arrays with `target.push(...resolvedDepsToNamedDepPaths(deps))` spreads a lockfile-derived dependency list into push() arguments; a pathologically large list can exceed the JS engine's argument-count limit and throw, crashing pnpm audit. Append via a loop helper instead, which also drops the intermediate array allocation.

…flow A lockfile is untrusted input, so a deeply nested dependency chain could overflow the JS call stack and crash pnpm audit. All four DFS traversals on the audit path — the bulk-request visitor, the reachable-vulnerability Tarjan SCC builder, the path walker, and the optional-only reachability walk — now use explicit work stacks instead of recursion. The path walker also tracked the install trail by copying the whole path array into every node (O(depth) per node, O(depth^2) for a deep chain). It now links each trail node to its parent and materializes the path string only when a finding is recorded, keeping memory linear in the depth. Adds a 60k-deep-chain regression test that completes without overflowing the stack or exhausting memory.

welcome · 2026-06-20T13:34:09Z

Congrats on merging your first pull request! 🎉🎉🎉

Copilot AI review requested due to automatic review settings June 17, 2026 08:23

chentsulin requested a review from zkochan as a code owner June 17, 2026 08:23

Copilot AI reviewed Jun 17, 2026

View reviewed changes

Comment thread deps/compliance/audit/src/lockfileToAuditIndex.ts Outdated

Comment thread pnpm11/deps/compliance/audit/src/lockfileToAuditIndex.ts

Comment thread deps/compliance/audit/test/index.ts Outdated

Copilot AI review requested due to automatic review settings June 17, 2026 08:40

Copilot AI reviewed Jun 17, 2026

View reviewed changes

Comment thread deps/compliance/audit/test/index.ts Outdated

chentsulin requested a review from Copilot June 17, 2026 08:53

Copilot AI reviewed Jun 17, 2026

View reviewed changes

Comment thread deps/compliance/audit/src/lockfileToAuditIndex.ts Outdated

Comment thread pnpm11/deps/compliance/audit/src/lockfileToAuditIndex.ts

coderabbitai Bot added the product: pnpm@11 label Jun 17, 2026

zkochan force-pushed the fix-audit-cyclic-reachability-perf branch from 7ab65ad to 490c73f Compare June 20, 2026 00:45

coderabbitai Bot approved these changes Jun 20, 2026

View reviewed changes

github-actions Bot added the reviewed: coderabbit CodeRabbit submitted an approving review label Jun 20, 2026

qodo-free-for-open-source-projects Bot approved these changes Jun 20, 2026

View reviewed changes

github-actions Bot added the reviewed: qodo label Jun 20, 2026

qodo-free-for-open-source-projects Bot reviewed Jun 20, 2026

View reviewed changes

Comment thread deps/compliance/audit/src/lockfileToAuditIndex.ts Outdated

Copilot AI review requested due to automatic review settings June 20, 2026 09:59

Copilot AI reviewed Jun 20, 2026

zkochan enabled auto-merge (squash) June 20, 2026 10:00

zkochan approved these changes Jun 20, 2026

View reviewed changes

github-actions Bot added the state: automerge label Jun 20, 2026

qodo-free-for-open-source-projects Bot reviewed Jun 20, 2026

View reviewed changes

Comment thread deps/compliance/audit/src/lockfileToAuditIndex.ts Outdated

qodo-free-for-open-source-projects Bot reviewed Jun 20, 2026

View reviewed changes

Comment thread deps/compliance/audit/src/lockfileToAuditIndex.ts Outdated

Copilot AI review requested due to automatic review settings June 20, 2026 11:54

Copilot AI reviewed Jun 20, 2026

chentsulin and others added 8 commits June 20, 2026 14:39

chore: allow Tarjan SCC terms in cspell dictionary

a234be1

`lowlink`, `strongconnect`, and `Tarjan` are used by the audit reachability fix and must be accepted by the spell checker. Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

zkochan force-pushed the fix-audit-cyclic-reachability-perf branch from f52aa6b to e3aa3f6 Compare June 20, 2026 12:42

zkochan merged commit d3f68e2 into pnpm:main Jun 20, 2026
20 of 21 checks passed

Uh oh!

Uh oh!

Conversation

chentsulin commented Jun 17, 2026 • edited by coderabbitai Bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Squash Commit Body

Checklist

Summary by CodeRabbit

Uh oh!

welcome Bot commented Jun 17, 2026

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 17, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Review by Qodo

Previous review results

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

Uh oh!

Uh oh!

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 17, 2026

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Uh oh!

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 17, 2026

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 17, 2026

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Uh oh!

Uh oh!

Uh oh!

coderabbitai Bot commented Jun 17, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Reviews paused

Walkthrough

Changes

Sequence Diagram

Estimated code review effort

Assessment against linked issues

Possibly related PRs

Suggested reviewers

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 20, 2026

Uh oh!

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 20, 2026

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 20, 2026

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 20, 2026

Uh oh!

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 20, 2026

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 20, 2026

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 20, 2026

Uh oh!

qodo-free-for-open-source-projects Bot commented Jun 20, 2026

Uh oh!

Uh oh!

welcome Bot commented Jun 20, 2026

chentsulin commented Jun 17, 2026 •

edited by coderabbitai Bot

Loading

qodo-free-for-open-source-projects Bot commented Jun 17, 2026 •

edited

Loading

coderabbitai Bot commented Jun 17, 2026 •

edited

Loading