UNDF: UNDF-2026-000000290

spark-deeper — Scheduler + Catalyst + Physical Plan + Storage + Shuffle CLEAN

Areas Scanned

Core Scheduler

core/src/main/scala/org/apache/spark/scheduler/DAGScheduler.scala — BFS traversals (spark-0002), waitingStages filter (spark-0004), submitWaitingChildStages, stageDependsOn, getMissingParentStages, all 6 BFS methods — all already covered by existing defects
core/src/main/scala/org/apache/spark/scheduler/TaskSchedulerImpl.scala — all contains/exists calls use HashMap/mutable.Map → O(1)
core/src/main/scala/org/apache/spark/scheduler/TaskSetManager.scala — no List.contains in hot paths
core/src/main/scala/org/apache/spark/scheduler/TaskSetExcludeList.scala — excludedExecs, excludedNodes are HashSet → O(1)
core/src/main/scala/org/apache/spark/scheduler/HealthTracker.scala — clean
core/src/main/scala/org/apache/spark/scheduler/LiveListenerBus.scala — queues.asScala.find(_.name == queue) on bounded small list (typically 4 queues)

Catalyst Optimizer

sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala — excludeList is AttributeSet (O(1)), projectList.exists(...) is O(E) but called once per plan node, not in a nested loop
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/analysis/Analyzer.scala — all projectList.exists() / aggList.exists() calls are O(E) single-pass pattern-match guards
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/v2Commands.scala — assignments.exists(isEqual(_, fieldPath)) is O(A×F) in filterSchema, but this is a schema-time operation on small data
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/CapturesConfig.scala — configPrefixDenyList has ~11 fixed entries, not a scaling concern

Physical Plan Operators

sql/core/src/main/scala/org/apache/spark/sql/execution/joins/ — all contains/exists calls use HashSet, OpenHashSet, AttributeSet, or ExpressionSet → O(1)
sql/core/src/main/scala/org/apache/spark/sql/execution/exchange/EnsureRequirements.scala — childrenIndexes is bounded (≤ 2 for joins)
sql/core/src/main/scala/org/apache/spark/sql/execution/adaptive/ — clean
sql/core/src/main/scala/org/apache/spark/sql/execution/aggregate/ — modes.contains(Final) etc. is on a small fixed-size list

Dynamic Partition Pruning (Spark SQL)

sql/core/src/main/scala/org/apache/spark/sql/execution/dynamicpruning/PartitionPruning.scala — joinKeys.indexOf(filteringKeys.head) is O(K) single call, not in a loop

Storage and Shuffle

core/src/main/scala/org/apache/spark/storage/ — no list.contains patterns in hot paths
core/src/main/scala/org/apache/spark/shuffle/ — no list.contains patterns in hot paths

RDD Operations

core/src/main/scala/org/apache/spark/rdd/RDD.scala — getNarrowAncestors uses mutable.HashSet → O(1)
core/src/main/scala/org/apache/spark/rdd/OrderedRDDFunctions.scala — partitionIndices.contains uses Scala Range.contains → O(1)
core/src/main/scala/org/apache/spark/rdd/CoalescedRDD.scala — all contains calls use HashMap-backed structures

MLlib (spot check)

mllib/src/main/scala/org/apache/spark/ml/feature/RFormulaParser.scala — dotTerms.contains is O(D) per filter call on plan-time formula parsing — negligible at runtime

Verdict: No new CWE-407 defects found beyond spark-0001 through spark-0004

All identified contains/exists/find calls in hot paths either:

Operate on hash-based structures (O(1) lookup), or
Are called once per plan node / RDD construction (not in a doubly-nested loop), or
Operate on bounded-size data (≤ join side count, ≤ mode count, etc.)

The 6 BFS ListBuffer.remove(0) defects are already captured as spark-0002. The submitWaitingChildStages O(W×P) defect is already captured as spark-0004.

3.9 KiB Raw Permalink Blame History Unescape Escape