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