russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
54 lines
1.7 KiB
ReStructuredText
54 lines
1.7 KiB
ReStructuredText
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`
|