Scala — CWE-407 Language Analysis
===================================

.. contents:: :local:

Overview
--------

Scala's ``List[T].contains(elem)`` is O(n) — it is a linear scan of the linked list. The Scala
3 compiler (Dotty) uses ``List[TypeParamRef]`` for constraint lattice operations in its type
inference engine. One CRITICAL CWE-407 defect site was found: ``OrderingConstraint.scala:243``.

This is the highest-severity defect in the survey. The defect is **CRITICAL** because it
produces O(n³) behavior in the number of type parameters — not O(n²) — due to nested constraint
lattice traversal. It is unpatched.

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

.. code-block:: scala

   // Defective — O(n³) nested constraint traversal
   def isLess(tp1: TypeParamRef, tp2: TypeParamRef): Boolean = {
     val minUpper = minUpper(tp1)   // returns List[TypeParamRef]
     val minLower = minLower(tp2)   // returns List[TypeParamRef]
     minUpper.exists(tp => minLower.contains(tp))  // O(|minUpper| × |minLower|)
     // Both minUpper and minLower are O(n) in the number of type params
     // isLess is called O(n) times during constraint solving → O(n³) total
   }

.. code-block:: scala

   // Fixed — O(n) with Set
   def isLess(tp1: TypeParamRef, tp2: TypeParamRef): Boolean = {
     val minUpperSet = minUpper(tp1).toSet   // build once: O(n)
     val minLower = minLower(tp2)
     minLower.exists(tp => minUpperSet.contains(tp))  // O(1) per test
   }
   // Or: precompute both as Set[TypeParamRef] at constraint construction time

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

scala3-0001
~~~~~~~~~~~

**File:** ``compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala:243``

**Pattern:**

.. code-block:: scala

   // isLess — constraint lattice comparison with List.contains in nested loop
   def isLess(param1: TypeParamRef, param2: TypeParamRef)(using Context): Boolean =
     minLower(param2).exists(p => minUpper(param1).contains(p))
     //                                             ^^^^^^^^
     //                              O(|minUpper(param1)|) per test
     //              O(|minLower(param2)|) outer calls per isLess invocation
     //  isLess called O(n) times → O(n³) total

**Why this is O(n):** ``List.contains`` inside ``List.exists`` inside a loop: three nested O(n)
factors.

**Complexity:** ``O(n³)`` where n = number of type parameters in the constraint system

**Patch:**

.. code-block:: scala

   def isLess(param1: TypeParamRef, param2: TypeParamRef)(using Context): Boolean = {
     val upper1 = minUpper(param1).toSet   // O(n) to build, O(1) per lookup
     minLower(param2).exists(p => upper1.contains(p))
   }

**Data structure change:** ``List[TypeParamRef]`` + ``contains`` → ``Set[TypeParamRef]`` + ``contains``

**Status:** Unpatched

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

.. TODO: benchmark pending patch — requires Scala 3 compiler test harness with
.. parameterized type inference workload

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

Let n = number of type parameters. ``minUpper`` and ``minLower`` each return lists of up to n
elements. ``List.contains`` inside ``List.exists`` costs O(n) × O(n) = O(n²) per ``isLess``
call. ``isLess`` is called O(n) times during constraint solving: O(n³) total. Converting
``minUpper(param1)`` to a ``Set`` once per ``isLess`` call: construction O(n), each
``exists`` test O(1), total per call O(n). Over O(n) calls: O(n²). QED.

An upstream fix that precomputes set representations at constraint-object construction time
would reduce this to O(n) total, eliminating the constraint lattice as a scaling bottleneck
entirely.

References
----------

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