java-topology/tools/tickets/defects/scala3-0001.md

id	repo	severity	status	created	patched	patch
scala3-0001	scala3	CRITICAL	PATCHED	2026-03-23	2026-03-23	defects/scala3/patch/scala3-0001-ordering-constraint-set.patch

Defect

File: compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala:248 (post-patch; was line 243) Pattern: List[TypeParamRef].contains in isLess called from minLower/minUpper during type inference constraint solving Complexity: O(n³) → O(n²) after fix Language: Scala

Description

During type inference, isLess is called repeatedly from minLower and minUpper to resolve ordering constraints between type parameter references. Each call performs a linear contains scan over a List[TypeParamRef] to test membership. Because minLower/minUpper invoke isLess in a loop over all constraint pairs, the combined complexity becomes O(n³) in the number of type parameters under constraint.

// isLess — THE DEFECT
def isLess(param1: TypeParamRef, param2: TypeParamRef): Boolean =
  upper(param1).contains(param2)  // O(n) List scan

// minUpper — calls isLess O(n²) times total
def minUpper(param: TypeParamRef): List[TypeParamRef] = {
  val all = upper(param)                            // O(n)
  all.filterNot(p => all.exists(isLess(_, p)))     // O(n) × O(n) = O(n²)
}
// Across n params: O(n³)

Fix

Storage change: ParamOrdering = ArrayValuedMap[List[TypeParamRef]] → ArrayValuedMap[Set[TypeParamRef]] Key change: isLess uses upperSet(param1).contains(param2) — O(1) hash lookup

Public API (lower(), upper(), minLower(), minUpper(), exclusiveLower(), exclusiveUpper()) unchanged — all still return List[TypeParamRef] via .toList conversion at the boundary.

Changed sites

Site	Before	After
ParamOrdering type	ArrayValuedMap[List[TypeParamRef]]	ArrayValuedMap[Set[TypeParamRef]]
lowerLens/upperLens initial	Nil	Set.empty
isLess	upper(p1).contains(p2) O(n)	upperSet(p1).contains(p2) O(1)
order() concat	newUpper ::: existing	existing ++ newUpper
removeParamFrom in replace()	ps.filterConserve(param ne _)	ps - param
removeFromBoundss in remove()	filterConserve on List	filterNot on Set

Complexity proof

Let V = number of type parameters constrained.

• Before: isLess = O(V); minUpper/minLower = O(V²); total per constraint solve = O(V³)
• After: isLess = O(1); minUpper/minLower = O(V); total per constraint solve = O(V²)
• Ratio at V=50: 125,000 → 2,500 ops (50×); at V=100: 1,000,000 → 10,000 ops (100×)

Work remaining

• Patch — defects/scala3/patch/scala3-0001-ordering-constraint-set.patch
• Unit test — asserts exact isLess call counts + contains counts before/after
• Integration test — compile Cats/Shapeless HKT-heavy module before/after
• Benchmark — before/after on synthetic chain A1 <: A2 <: ... <: An, n=50,100,200,400
• White paper section