engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/defects/ghc/patch/ghc-diamond-recursion-CLEAN.md
russell@unturf.com 61a717bfcc diamond-scan-deeper: kotlin/scala3/groovy/ghc O(2^D) hierarchy traversal — CLEAN + groovy-0001/0002 patches 
Kotlin: confirmed CLEAN (DFS.VisitedWithSet throughout, existing marker valid)
Scala3: confirmed CLEAN (BaseDataBuilder.addAll deduplicates, existing marker valid)
GHC: CLEAN — NameSet/UniqSet/ExpansionFuel tracking in all superclass expansion paths
  (checkClassCycles, mk_strict_superclasses, transSuperClasses, closeWrtFunDeps)
Groovy: CLEAN for diamond — getAllInterfaces/collectAllInterfacesReverseOrder/addAllInterfaces
  all use if(set.add(node)) guards (GROOVY-11036)
  groovy-0001/0002 patch docs created (O(N²) membership scans, pre-existing UNDF assigned)
Clojure: CLEAN (set-based BFS, supers/ancestors use set-based worklist)
2026-03-29 20:30:49 -04:00

3.1 KiB
Raw Permalink Blame History

GHC Compiler — Diamond Recursion CWE-407 Scan: CLEAN

Pattern: Recursive traversal of typeclass constraint hierarchy without visited set (O(2^D)) Scan date: 2026-03-29 Scope: compiler/GHC/Tc/, compiler/GHC/Core/, compiler/GHC/Tc/Instance/

Method

Searched for recursive superclass/typeclass expansion without proper cycle/duplicate tracking across the GHC type-checker (GHC/Tc/) and core (GHC/Core/). Traced all callers of immSuperClasses, classSCTheta, transSuperClasses, expandSuperClasses, and mk_strict_superclasses. Verified cycle-breaking mechanism in each path.

Key candidates reviewed

GHC.Tc.TyCl.Utils.checkClassCycles — go_cls

compiler/GHC/Tc/TyCl/Utils.hs lines 295–340.

Recursive function that expands superclass predicates. Uses ClassSet (UniqSet Class) threaded as so_far. Before recursing, checks cls \elementOfUniqSet` so_far`. Correct visited tracking. CLEAN.

GHC.Tc.Utils.TcType.transSuperClasses — go

compiler/GHC/Tc/Utils/TcType.hs lines 1931–1948.

Recursive superclass expansion for constraint solving. Uses go emptyNameSet with extendNameSet cls_nm and not (cls_nm \elemNameSet` rec_clss)guard before recursing. Correct visited tracking viaNameSet`. CLEAN.

GHC.Tc.Solver.Dict.mk_strict_superclasses / mk_superclasses_of

compiler/GHC/Tc/Solver/Dict.hs lines 1658–1820.

Superclass expansion for Given/Wanted constraints during solving. Uses NameSet rec_clss threaded through mk_superclasses → mk_superclasses_of → mk_strict_superclasses. Guard: loop_found = not (isCTupleClass cls) && cls_nm \elemNameSet` rec_clss. Also uses ExpansionFuel` counter to prevent infinite expansion. Correct. CLEAN.

GHC.Tc.Instance.FunDeps.closeWrtFunDeps

compiler/GHC/Tc/Instance/FunDeps.hs lines 547–584.

Calls transSuperClasses pred (line 570) which already has proper NameSet tracking. fixVarSet outer loop terminates on fixpoint. CLEAN.

GHC.Tc.Instance.FunDeps.checkFunDeps

compiler/GHC/Tc/Instance/FunDeps.hs lines 644–650.

Uses nubBy eq_inst to deduplicate instances — O(N²) but N is bounded by number of instances in scope, not a type hierarchy depth. Not O(2^D). CLEAN.

GHC.Tc.Utils.TcType.mkMinimalBySCs

compiler/GHC/Tc/Utils/TcType.hs lines 1874–1925.

Calls transSuperClasses pred for each predicate to build superclass sets, then uses list scan in_cloud. O(N × |superclasses|) where superclasses are deduplicated by transSuperClasses. Not O(2^D). CLEAN.

Verdict

CLEAN for diamond O(2^D) recursion. GHC uses:

  • ClassSet / NameSet / UniqSet throughout typeclass hierarchy traversal
  • elemNameSet / elementOfUniqSet guards before recursing
  • ExpansionFuel counter as belt-and-suspenders against infinite expansion
  • transSuperClasses with go emptyNameSet for all transitive expansion

No unprotected recursive DAG traversal found. Previous ghc-0001/ghc-0003 UNDF entries (UNDF-2026-000000078, UNDF-2026-000000079) represent pre-existing CWE-407 issues from earlier scan passes; diamond recursion is not present in GHC's typeclass hierarchy code.