# UNDF: UNDF-2026-000000579
# UNDF: (pending)
# typescript-0004: resolvedProjectReferenceUptoDate — seenResolvedRefs Array O(N²) linear scan

## CWE-407 — Algorithmic Complexity: O(N) contains() on Array in recursive project reference traversal

| Field        | Value |
|--------------|-------|
| ID           | typescript-0004 |
| Severity     | LOW |
| Ecosystem    | typescript |
| Package      | typescript |
| File         | `src/compiler/program.ts` |
| Lines        | 1246, 1288, 1303 |
| Complexity   | O(N²) where N = number of project references |
| Hot path     | TypeScript `--build` mode incremental compilation, called per project reference |

## Defect

`resolvedProjectReferenceUptoDate` uses `seenResolvedRefs: ResolvedProjectReference[] | undefined`
as a cycle-detection guard. The membership check uses `contains(seenResolvedRefs, ...)` which is
a linear scan (O(N)) implemented in `core.ts`:

```typescript
// src/compiler/program.ts:1246 (DEFECT)
let seenResolvedRefs: ResolvedProjectReference[] | undefined;

function resolvedProjectReferenceUptoDate(oldResolvedRef, oldRef): boolean {
    if (oldResolvedRef) {
        if (contains(seenResolvedRefs, oldResolvedRef)) return true;  // O(N) linear scan!
        // ...
        (seenResolvedRefs || (seenResolvedRefs = [])).push(oldResolvedRef);  // array push
        return !forEach(oldResolvedRef.references, (childResolvedRef, index) =>
            !resolvedProjectReferenceUptoDate(childResolvedRef, ...));  // recursive
    }
}
```

`contains()` in `core.ts:220` is a for-loop linear scan:
```typescript
export function contains<T>(array: readonly T[] | undefined, value: T, ...): boolean {
    if (array !== undefined) {
        for (let i = 0; i < array.length; i++) {
            if (equalityComparer(array[i], value)) return true;
        }
    }
    return false;
}
```

With N project references: each `resolvedProjectReferenceUptoDate` call does an O(N) scan,
total cost O(N²) for the full traversal.

## Fix

Replace `seenResolvedRefs: ResolvedProjectReference[] | undefined` with
`Set<ResolvedProjectReference>`:

```typescript
// AFTER — O(N) total
const seenResolvedRefs = new Set<ResolvedProjectReference>();

function resolvedProjectReferenceUptoDate(oldResolvedRef, oldRef): boolean {
    if (oldResolvedRef) {
        if (seenResolvedRefs.has(oldResolvedRef)) return true;  // O(1) Set.has()
        seenResolvedRefs.add(oldResolvedRef);                    // O(1) Set.add()
        // ...recurse...
    }
}
```

## Speedup

| Project references (N) | Before (checks) | After (checks) | Speedup |
|------------------------|----------------|----------------|---------|
| 10                     | 55             | 10             | 5.5×    |
| 50                     | 1,275          | 50             | 25.5×   |
| 100                    | 5,050          | 100            | 50.5×   |
| 500                    | 125,250        | 500            | 250.5×  |

Growth before: O(N²). Growth after: O(N).

**Note:** In practice, TypeScript projects rarely have >50 project references, so the
performance impact is low in normal use. The defect is classified LOW severity.
