russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
34 lines
1.2 KiB
Markdown
34 lines
1.2 KiB
Markdown
---
|
|
id: ts-0002
|
|
repo: TypeScript
|
|
severity: HIGH
|
|
status: PATCHED
|
|
patched: 2026-03-23
|
|
patch: defects/typescript/patch/ts-checker-set-visited.patch
|
|
created: 2026-03-23
|
|
---
|
|
|
|
## Defect
|
|
|
|
**File:** `src/compiler/checker.ts:5256`
|
|
**Pattern:** `pushIfUnique(visitedSymbols, ...)` array linear scan in export-star resolution
|
|
**Complexity:** `O(V²)`
|
|
**Language:** TypeScript
|
|
|
|
## Description
|
|
|
|
During export-star resolution, the checker tracks which symbols have already been visited using `pushIfUnique` on a plain array. `pushIfUnique` performs a linear search through the array before pushing to ensure uniqueness. With V symbols to resolve, each needing a visited check, the total cost of all membership tests is O(V²).
|
|
|
|
## Fix
|
|
|
|
**Replace:** `pushIfUnique(visitedSymbols, symbol)`
|
|
**With:** `visitedSymbols.add(symbol)` (with early-return on `has` check)
|
|
**Data structure change:** `visitedSymbols: Symbol[] → visitedSymbols: Set<Symbol>`
|
|
|
|
## Work required
|
|
|
|
- [ ] Patch in `defects/typescript/patch/`
|
|
- [ ] Unit test — asserts exact operation counts before/after (in `defects/typescript/unit/`)
|
|
- [ ] Integration test (in `defects/typescript/integration/`)
|
|
- [ ] Benchmark — before/after on V=100,200,400,800 (in `defects/typescript/bench/`)
|
|
- [ ] White paper section
|