java-topology/docs/tickets/nestjs-0001-scanner-ctxregistry-array-includes.md

nestjs-0001: CWE-407 — scanner ctxRegistry Array.includes() in module scan loop

Project: NestJS (@nestjs/core) File: packages/core/scanner.ts Line: 155 Symbol: DependenciesScanner.scanForModules — ctxRegistry.includes(innerModule) Severity: HIGH Status: PATCHED

Description

DependenciesScanner.scanForModules() is the recursive function that walks the entire module import tree at application startup. It uses a shared mutable ctxRegistry array (passed by reference into every recursive call) as a visited-set to detect already-registered modules and break cycles.

For each module in the current modules list (line 147 for...of), the code calls ctxRegistry.includes(innerModule) at line 155. Because ctxRegistry is a plain Array, .includes() performs a linear O(n) scan. The array grows by one on every new module visit (line 126 ctxRegistry.push(moduleDefinition)).

For an application with N modules:

• Module 1: includes() scans 0 elements
• Module 2: includes() scans 1 element
• ...
• Module N: includes() scans N-1 elements

Total comparisons ≈ N×(N-1)/2 = O(N²).

NestJS enterprise applications routinely have hundreds of modules (NestJS docs show monorepos with 50-200+ modules; large applications with feature modules, shared libraries, third-party integrations can exceed 300). At N=300: defective = 44,850 comparisons; fixed = 300.

This runs at application startup, not per-request, but it directly increases cold-start time — critical for serverless (Lambda, Cloud Run) where cold starts are charged and affect tail latency.

Root Cause

// packages/core/scanner.ts line 110 — ctxRegistry typed as Array
ctxRegistry = [],

// line 126 — pushed into the Array
ctxRegistry.push(moduleDefinition);

// line 155 — O(n) linear scan on every loop iteration
if (ctxRegistry.includes(innerModule)) {
  continue;
}

The ModulesScanParameters interface types ctxRegistry as:

ctxRegistry?: (ForwardReference | DynamicModule | Type<unknown>)[];

Fix

Change ctxRegistry from Array to Set. The Set.has() operation is O(1) average. Since ctxRegistry is only used for membership testing and is never iterated, the Array API is not needed.

See patch: defects/nestjs/patch/nestjs-0001-scanner-ctxregistry-set.patch

Complexity

Scenario	Defective	Fixed
N=50 modules	1,225 comparisons	50
N=100 modules	4,950 comparisons	100
N=300 modules	44,850 comparisons	300
Ratio at N=300	—	150x

References

• CWE-407: Inefficient Algorithmic Complexity
• packages/core/scanner.ts commit 0fddd2e