java-topology/defects/kotlin/patch/kotlin-0002-constraint-system-bounds-linkedhashset.md

UNDF: UNDF-2026-000000135

UNDF: (pending)

kotlin-0002: ConstraintSystemBuilderImpl.addBound — O(B) ArrayList scan per constraint during type inference

CWE-407 — Algorithmic Complexity: Inefficient Algorithmic Complexity

Field	Value
ID	kotlin-0002
Severity	MEDIUM
Ecosystem	kotlin
Package	org.jetbrains.kotlin.resolve.calls.inference
File	compiler/frontend/src/org/jetbrains/kotlin/resolve/calls/inference/ConstraintSystemBuilderImpl.kt
Lines	266–279
Complexity	O(B) duplicate-check per addBound call; O(B²) total per type variable during constraint incorporation
Hot path	Type inference for every generic call site

Defect

ConstraintSystemBuilderImpl.addBound() deduplicates bounds before adding them to prevent the constraint incorporation loop from diverging. The dedup check uses ArrayList.contains():

// TypeBoundsImpl.kt:31
override val bounds = ArrayList<Bound>()           // BUG: ArrayList

// ConstraintSystemBuilderImpl.kt:277
val typeBounds = getTypeBounds(typeVariable)
if (typeBounds.bounds.contains(bound)) return     // O(B) linear scan per call
typeBounds.addBound(bound)

TypeBounds.Bound defines equals() and hashCode() (comparing typeVariable, constrainingType, kind, and position.isStrong()), making it fully eligible for storage in a hash-based collection.

During constraint incorporation (constraintIncorporation.kt), incorporateBound() is called once per new bound and may call addBound O(B) times as it cross-multiplies with existing bounds. Each addBound performs an O(B) contains scan, yielding O(B²) total duplicate-check work per type variable per incorporation round. For functions with many type parameters and complex bounds (e.g. higher-kinded types, SAM conversions with many overloads), B can reach 30–50 during a single call resolution.

Fix

Change TypeBoundsImpl.bounds from ArrayList<Bound> to LinkedHashSet<Bound> to provide O(1) contains and maintain insertion order for deterministic value computation:

// TypeBoundsImpl.kt — change bounds to LinkedHashSet
class TypeBoundsImpl(override val typeVariable: TypeVariable) : TypeBounds {
    override val bounds: MutableSet<Bound> = LinkedHashSet()   // was: ArrayList<Bound>()

    fun addBound(bound: Bound) {
        resultValues = null
        assert(bound.typeVariable == typeVariable) { ... }
        bounds.add(bound)
    }
    // ... rest unchanged
}

The TypeBounds interface declares bounds: Collection<Bound>, so changing the concrete type to LinkedHashSet is a compatible implementation change. All iteration patterns (bounds.indices, bounds.filter, bounds.any, bounds.flatMap) work identically on Set as on List.

The dedup guard in ConstraintSystemBuilderImpl.addBound() can then rely on LinkedHashSet.add() returning false on duplicate, or retain the explicit check — both become O(1).

Speedup

B (bounds per type var)	Before (contains ops)	After (contains ops)	Speedup
10	100	10	10×
30	900	30	30×
50	2,500	50	50×

Typical Kotlin inference sessions for moderate generics see B ≈ 5–15; complex higher-kinded scenarios can reach B = 30–50. The patch provides consistent O(1) dedup across all cases.

Affected Versions

All Kotlin compiler versions with ConstraintSystemBuilderImpl / TypeBoundsImpl (Kotlin 1.0+; still present in K1 frontend used by kotlinc and IntelliJ IDEA K1 mode).

References

• JetBrains YouTrack (none filed)
• Upstream source: compiler/frontend/src/org/jetbrains/kotlin/resolve/calls/inference/
• CWE-407: https://cwe.mitre.org/data/definitions/407.html