java-topology/docs/tickets/nestjs-0002-get-injection-providers-array-includes.md

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:

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

// 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