russell@unturf.com
9934133dcf
Add 88 new defect entries to HIGH and MEDIUM tables:
HIGH: mysql-0001/0002, mariadb-0001, redis-0001/0002, valkey-0001/0002, openvpn-0001,
vlc-0001, prometheus-0001, otel-collector-0001, cockroachdb-0001..0004,
tidb-0001..0008, kubernetes-0001/0002, go-0001, kotlin-0002, scala-0001,
allegro5-0001, sdl2-0001, grafana-0001, clickhouse-0001, duckdb-0001,
mongodb-0001, envoy-0001, istio-0001, cilium-0001, linkerd2-0001,
linux-0001/0002/0003, tor-0002/0003, curl-0001, julia-0001, lua-0001,
perl5-0001, nats-0001, spring-0003/0004, tomcat-0001, onos-0002, odl-0002
MEDIUM: helm-0001, mariadb-0002, openssl-0001/0002, memcached-0001,
cassandra-0001..0004, flink-0001, storm-0001/0002, zookeeper-0001..0003,
pip-0001, gradle-0001, nginx-0001, haproxy-0001, caddy-0001, varnish-0001,
ffmpeg-0001, gstreamer-0001, raylib-0001, love2d-0001, php-0001/0002,
r-source-0001, cpython-0002, ruby-0001, rabbitmq-0003/0004, activemq-0001,
ovs-0001, onos-0003, odl-0002, jetty-0001
PDF: 976K
2.1 KiB
scala-0001 — CWE-407: Checkable propagateKnownTypes baseClasses O(n²) nested scan
Target: scala/scala — src/compiler/scala/tools/nsc/typechecker/Checkable.scala
Severity: HIGH
Complexity: O(n²) → O(n)
Defect
propagateKnownTypes (Checkable.scala:98) performs a nested O(n²) scan:
from.baseClasses foreach { bc => if (to.baseClasses.contains(bc)){
Both from.baseClasses and to.baseClasses return List[Symbol]. The outer
foreach iterates over from.baseClasses (length M), and for each element calls
to.baseClasses.contains(bc) which is O(N) linear scan. Total: O(M×N).
In Scala's type system, class hierarchy depth determines M and N. For typical
Scala projects this is 10–50 base classes per type; for framework-heavy code
(Akka, Play, Cats) it can reach 100+. The outer loop is called during pattern
match type-checking for every match/isInstanceOf in source.
propagateKnownTypes is called from CheckabilityChecker during Typers
pattern match elaboration — a hot path for Scala programs that use match
extensively.
Fix
Convert to.baseClasses to a Set before the loop:
def propagateKnownTypes(from: Type, to: Symbol): Type = {
def tparams = to.typeParams
val tvars = tparams map (p => TypeVar(p))
val tvarType = appliedType(to, tvars)
val toBaseClassSet = to.baseClasses.toSet // O(n) once
from.baseClasses foreach { bc => if (toBaseClassSet.contains(bc)){
Symbol implements hashCode/equals by identity (object reference), so
Set[Symbol] gives O(1) membership. The one-time conversion cost is O(N) and
the outer loop becomes O(M) total.
Impact
- Every pattern match expression in Scala source triggers
propagateKnownTypes - Deep class hierarchies (trait-heavy Scala libraries) magnify the defect
- O(n²) in hierarchy depth per match arm, multiplied by number of match expressions
- Compile time for large Scala codebases (Spark, Akka, Cats) is meaningfully
affected — particularly files with many
matchexpressions over typed hierarchies
Files
- Patch:
defects/scala/patch/scala-0001.patch - Unit:
defects/scala/unit/ScalaCheckableTest.java