Kotlin Compiler (kotlinc) — CWE-407 Analysis
============================================

.. contents:: :local:

Overview
--------

``kotlinc`` is the Kotlin compiler developed by JetBrains. It performs type checking,
inheritance analysis, and constraint resolution for the Kotlin language. One CWE-407 defect
site was found in the type-class inheritance restriction checker. It is unpatched.

Defect Sites
------------

kotlin-0001
~~~~~~~~~~~

**File:** ``compiler/frontend/src/org/jetbrains/kotlin/resolve/NonExpansiveInheritanceRestrictionChecker.kt:150``

**Pattern:**

.. code-block:: kotlin

   // Inheritance expansion check — linear membership test on visited list
   private fun checkNonExpansive(
       descriptor: ClassDescriptor,
       visited: List<ClassDescriptor>
   ) {
       if (descriptor in visited) return   // O(V) — `in` on List is linear scan
       val newVisited = visited + descriptor
       for (supertype in descriptor.defaultType.supertypes()) {
           checkNonExpansive(supertype.constructor.declarationDescriptor, newVisited)
       }
   }

**Why this is O(n):** ``in`` on a Kotlin ``List`` is a linear scan — ``List.contains()``
underneath. Called recursively for each supertype: O(E×V) total where E = edges (supertype
relationships) and V = distinct classes visited.

**Complexity:** ``O(E×V)`` where E = supertype edges, V = classes in the inheritance graph

**Patch:**

.. code-block:: kotlin

   private fun checkNonExpansive(
       descriptor: ClassDescriptor,
       visited: HashSet<ClassDescriptor>
   ) {
       if (descriptor in visited) return   // O(1) — `in` on HashSet is O(1)
       visited.add(descriptor)
       for (supertype in descriptor.defaultType.supertypes()) {
           checkNonExpansive(supertype.constructor.declarationDescriptor, visited)
       }
   }

**Data structure change:** ``List<ClassDescriptor>`` + ``in`` → ``HashSet<ClassDescriptor>`` + ``in``

**Status:** Unpatched

Benchmark Results
-----------------

.. TODO: benchmark pending patch

Complexity Proof
----------------

Let V = number of distinct class descriptors visited, E = supertype edges. The defective code
passes an immutable list down the call stack and tests membership with ``in``, which calls
``List.contains()``: O(V) per test. With one test per edge: O(E×V) total. The patched code
uses a mutable ``HashSet``, sharing state across the recursion: O(1) per membership test,
O(V + E) total. QED.

References
----------

* Defect ticket: ``tools/tickets/defects/kotlin-0001.md``
