Kotlin — CWE-407 Language Analysis
=====================================

.. contents:: :local:

Overview
--------

Kotlin's ``List<T>.contains(element)`` and the ``in`` operator on lists are O(n) — they
delegate to ``AbstractList.contains()``, which performs a linear scan. This is the canonical
Kotlin CWE-407 pattern.

The fix is to use ``HashSet<T>`` or ``LinkedHashSet<T>``. The ``in`` operator is polymorphic in
Kotlin: ``x in hashSet`` calls ``HashSet.contains()``, which is O(1) amortized. No change to
call-site syntax is required beyond changing the collection type.

Canonical Defect Pattern
------------------------

.. code-block:: kotlin

   // Defective — O(V²)
   val visited = mutableListOf<ClassDescriptor>()

   fun dfs(node: ClassDescriptor) {
       if (node in visited) return   // O(|visited|) — List.contains()
       visited.add(node)
       for (parent in node.supertypes()) dfs(parent.declarationDescriptor)
   }

.. code-block:: kotlin

   // Fixed — O(V)
   val visited = HashSet<ClassDescriptor>()

   fun dfs(node: ClassDescriptor) {
       if (!visited.add(node)) return   // O(1) — HashSet.add() returns false if duplicate
       for (parent in node.supertypes()) dfs(parent.declarationDescriptor)
   }

Confirmed Defects
-----------------

One defect in the Kotlin compiler's inheritance restriction checker. Unpatched. See
:doc:`../compiler/kotlinc` for full analysis.

| Defect      | File                                                    | Complexity | Status    |
|-------------|----------------------------------------------------------|------------|-----------|
| kotlin-0001 | ``NonExpansiveInheritanceRestrictionChecker.kt:150``    | O(E×V)     | Unpatched |

References
----------

* :doc:`../compiler/kotlinc`
