# Scala 3 Compiler — Diamond Recursion CWE-407 Scan: CLEAN

**Pattern:** Recursive cycle/reachability without visited set (O(2^D) on diamond DAGs)
**Scan date:** 2026-03-29
**Scope:** `compiler/src/dotty/`

## Method

Searched for `isCyclic`, `hasCycle`, `createsCycle`, `isReachable`, `canReach`,
`hasPath`, `detectCycle` across all Scala sources. Examined recursive functions
for missing visited-accumulator parameters.

## Key candidates reviewed

### `SymDenotations.computeBaseType()` — `recur()` inner function
`compiler/src/dotty/tools/dotc/core/SymDenotations.scala` around line 2265.

`recur(tp)` is called recursively but uses `btrCache` as a memoization cache.
Before recursing, it checks `btrCache.lookup(tp)` for a sentinel value (`NoPrefix`)
that indicates a cycle in progress. This is a memo-table anti-cycle pattern. CLEAN.

### `OrderingConstraint.dependsOn()`
`compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala` line 286.

Uses `deps.at(param).exists(qualifies)` — direct set lookup, not recursive. CLEAN.

### `Checking.CheckNonCyclicMap`
`compiler/src/dotty/tools/dotc/typer/Checking.scala` line 257.

`CheckNonCyclicMap` extends `TypeMap` and uses a `cycleOK` flag plus
`CyclicReference` exception for cycle detection. Not diamond recursion — uses
exception-based unwinding, not unbounded recursion. CLEAN.

### `SymUtils.isReachable`
`compiler/src/dotty/tools/dotc/core/SymUtils.scala` line 211.

Returns `ctx.owner.isContainedIn(sym)` — single O(depth) tree traversal.
Not a DAG traversal. CLEAN.

## Verdict

CLEAN for diamond recursion pattern. Scala 3 compiler uses `btrCache` memo tables,
exception-based cycle detection, and O(depth) tree traversals. No unprotected
recursive DAG traversal found.
