java-topology/whitepaper/outreach/kotlin.md

Kotlin Compiler — CWE-407 Disclosure Brief

2026-03-27 · Patch available — awaiting upstream merge

Finding

One O(n²) defect in the Kotlin compiler's non-expansive inheritance restriction checker. Patched. Patch ready for upstream review. The defect is in a post-DFS membership check that uses a List<TypeConstructor> where a set is required.

The Defect

kotlin-0001 (PATCHED — HIGH): compiler/resolution/src/.../NonExpansiveInheritanceRestrictionChecker.kt:150

// In NonExpansiveInheritanceRestrictionChecker — post-DFS phase:
// Called during type inheritance validation for every class with generic supertypes:
val visited: MutableList<TypeConstructor> = mutableListOf()
// ...
for (typeConstructor in typeConstructors) {
    if (typeConstructor in visited) {  // O(V) — List<TypeConstructor> linear scan
        continue
    }
    visited.add(typeConstructor)
    // ... DFS exploration
}

visited is a MutableList<TypeConstructor>. The in operator on a List is O(V) per check. Called in a post-DFS membership check over all type constructors in an inheritance graph. Total: O(V²) where V = number of type constructors in the inheritance graph.

Complexity Proof

For V type constructors in the inheritance graph:

• Per constructor: O(V) in visited list scan
• Total: O(V²)

The Kotlin non-expansive inheritance restriction checker validates that generic type inheritance does not lead to expansive (infinite type) patterns — a soundness requirement. It runs on every class declaration with generic supertypes during compilation.

Kotlin codebases with complex generic inheritance hierarchies — common in framework code, DSL implementations, and heavily-generic library code — maximize V and hit worst case on every compilation.

Fix: replace mutableListOf<TypeConstructor>() with mutableSetOf<TypeConstructor>(). Kotlin's MutableSet.contains() is O(1). No behavioral change — MutableSet provides the same semantics as a deduplicated list for the visited-set use case.

Impact

Kotlin is the official language for Android development and is widely used for server-side JVM applications (Ktor, Spring Boot with Kotlin, Micronaut). The Kotlin compiler runs on every Android project build (the largest developer ecosystem using Kotlin) and every Kotlin JVM application build.

kotlin-0001 affects compilations with generic inheritance chains — common in:

• Android library development (generic base classes, extension functions, type-safe DSLs)
• Kotlin multiplatform projects with complex type hierarchies
• Framework code using Kotlin generics extensively (Ktor, Exposed, Kotlin coroutines internals)
• Jetpack Compose internals and Compose library development

The compiler soundness check runs at compile time on every class — in large Kotlin projects with hundreds of generic classes, this path runs thousands of times per compilation.

The Fix

Replace mutableListOf() with mutableSetOf():

// Before
val visited: MutableList<TypeConstructor> = mutableListOf()
if (typeConstructor in visited) { continue }  // O(V) list scan
visited.add(typeConstructor)

// After
// CWE-407 fix: mutableSetOf for O(1) contains() instead of O(V) List scan.
val visited: MutableSet<TypeConstructor> = mutableSetOf()
if (typeConstructor in visited) { continue }  // O(1) set lookup
visited.add(typeConstructor)

TypeConstructor is the Kotlin compiler's interface for type constructors — it implements equals()/hashCode() as required for use in hash-based collections.

Patch

Fix available: defects/kotlin/patch/kotlin-0001-inheritance-checker-mutableset.patch

Single-variable declaration change in NonExpansiveInheritanceRestrictionChecker.kt.

Unit test: O(V²) → O(V) growth confirmed on synthetic generic inheritance hierarchy. Compilation time improvement measurable on large Kotlin library projects.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a YouTrack reference (youtrack.jetbrains.com, Kotlin project).
2. Assess severity — kotlin-0001 fires on every compilation of classes with generic supertypes; Android library codebases and Kotlin framework code are worst case.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Kotlin team in the public disclosure. Preferred acknowledgment format welcome.

Contact: see cover email. This brief is confidential until coordinated disclosure.