# 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 via `NameSet`. 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.
