79 lines
2.6 KiB
Markdown
79 lines
2.6 KiB
Markdown
# 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
|
||
|
||
```typescript
|
||
// 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:
|
||
```typescript
|
||
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`
|