engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/tools/tickets/defects/ghc-0002.md
russell@unturf.com db29a08762 undefect. CWE-407 — 92 sites, 42 ecosystems 
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections.
Squash of 94 local commits onto remote master.
2026-03-26 19:48:18 -04:00

1.2 KiB
Raw Permalink Blame History

id repo severity status created patched patch
ghc-0002 ghc HIGH PATCHED 2026-03-23 2026-03-23 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