85 lines
3 KiB
Markdown
85 lines
3 KiB
Markdown
# nestjs-0002: CWE-407 — getInjectionProviders Array.includes() in while-loop filter
|
||
|
||
**Project:** NestJS (`@nestjs/common`)
|
||
**File:** `packages/common/module-utils/utils/get-injection-providers.util.ts`
|
||
**Lines:** 41-42
|
||
**Symbol:** `getInjectionProviders` — `result.includes(p)`, `search.includes(p as any)`, `search.includes((p as any)?.provide)`
|
||
**Severity:** MEDIUM
|
||
**Status:** PATCHED
|
||
|
||
## Description
|
||
|
||
`getInjectionProviders()` resolves the full provider dependency tree for
|
||
`ConfigurableModuleBuilder` async providers (used by `forRootAsync()` in most
|
||
NestJS ecosystem modules: `@nestjs/config`, `@nestjs/typeorm`,
|
||
`@nestjs/mongoose`, etc.).
|
||
|
||
The function has a `while (search.length > 0)` outer loop. In each iteration it
|
||
calls `providers.filter()` with a predicate that performs three `Array.includes()`
|
||
checks:
|
||
|
||
```typescript
|
||
const match = (providers ?? []).filter(
|
||
p =>
|
||
!result.includes(p) && // O(result.length)
|
||
(search.includes(p as any) || // O(search.length)
|
||
search.includes((p as any)?.provide)), // O(search.length)
|
||
);
|
||
```
|
||
|
||
For each call to `getInjectionProviders(providers, tokens)`:
|
||
- `providers.filter()` iterates all P providers
|
||
- For each provider, up to 3 Array.includes() scans of R (result) and S (search)
|
||
- Worst case per outer-loop iteration: P × (R + 2S) comparisons
|
||
- Over W iterations: P × W × (R + 2S) = **O(P × W × (R+S))**
|
||
|
||
In practice with P=50 providers, R=20 accumulated results, S=10 search tokens,
|
||
W=10 iterations: 50 × 10 × 30 = 15,000 comparisons vs. ~500 with Sets.
|
||
|
||
## Root Cause
|
||
|
||
```typescript
|
||
// packages/common/module-utils/utils/get-injection-providers.util.ts
|
||
export function getInjectionProviders(
|
||
providers: Provider[],
|
||
tokens: FactoryProvider['inject'],
|
||
): Provider[] {
|
||
const result: Provider[] = []; // plain Array — O(n) .includes()
|
||
let search: InjectionToken[] = tokens!.map(mapInjectToTokens);
|
||
while (search.length > 0) {
|
||
const match = (providers ?? []).filter(
|
||
p =>
|
||
!result.includes(p) && // O(result.length) scan
|
||
(search.includes(p as any) || // O(search.length) scan
|
||
search.includes((p as any)?.provide)),
|
||
);
|
||
result.push(...match);
|
||
search = match
|
||
.filter(p => (p as any)?.inject)
|
||
.flatMap(p => (p as FactoryProvider).inject!)
|
||
.map(mapInjectToTokens);
|
||
}
|
||
return result;
|
||
}
|
||
```
|
||
|
||
## Fix
|
||
|
||
Introduce `resultSet: Set<Provider>` and `searchSet: Set<InjectionToken>` as
|
||
companions to the existing arrays. Replace `.includes()` with `.has()`.
|
||
|
||
See patch: `defects/nestjs/patch/nestjs-0002-get-injection-providers-set.patch`
|
||
|
||
## Complexity
|
||
|
||
| P providers, R results, S search, W iterations | Defective | Fixed |
|
||
|---|---|---|
|
||
| P=20, R=5, S=5, W=3 | 900 | ~75 |
|
||
| P=50, R=20, S=10, W=10 | 15,000 | ~500 |
|
||
| Ratio at larger scale | — | **~30x** |
|
||
|
||
## References
|
||
|
||
- CWE-407: Inefficient Algorithmic Complexity
|
||
- `packages/common/module-utils/utils/get-injection-providers.util.ts` commit `0fddd2e`
|
||
- Called from `configurable-module.builder.ts:308` via `createAsyncProviders`
|