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: ghc-0002
|
|
repo: ghc
|
|
severity: HIGH
|
|
status: PATCHED
|
|
created: 2026-03-23
|
|
patched: 2026-03-23
|
|
patch: defects/ghc/patch/ghc-cwe407-set-membership.patch
|
|
---
|
|
|
|
## Defect
|
|
|
|
**File:** `compiler/GHC/Data/Graph/Inductive/Graph.hs:489-501`
|
|
**Pattern:** `elem` x4 edge-existence checks in codegen
|
|
**Complexity:** `O(degree) per query`
|
|
**Language:** Haskell
|
|
|
|
## Description
|
|
|
|
Four separate `elem` calls are used to check edge existence in the inductive graph representation used during code generation. Each `elem` call scans a list of adjacency entries linearly. Although each individual check is O(degree), these checks are performed repeatedly during code generation traversals, and the pattern compounds across all queries made on the graph during a compilation pass.
|
|
|
|
## Fix
|
|
|
|
**Replace:** `e `elem` edges`
|
|
**With:** `e `S.member` edgeSet`
|
|
**Data structure change:** `edge lists → Set-backed adjacency structure`
|
|
|
|
## Work required
|
|
|
|
- [ ] Patch in `defects/ghc/patch/`
|
|
- [ ] Unit test — asserts exact operation counts before/after (in `defects/ghc/unit/`)
|
|
- [ ] Integration test (in `defects/ghc/integration/`)
|
|
- [ ] Benchmark — before/after on V=100,200,400,800 (in `defects/ghc/bench/`)
|
|
- [ ] White paper section
|