russell@unturf.com 1dee074618 kafka-0009: GraphGraceSearchUtil diamond recursion O(2^D) → O(N); count 621→622

findAndVerifyWindowGrace() recurses over parent GraphNodes without a visited
accumulator. Kafka Streams GraphNode is a genuine DAG (addChild wires
parent→child with multiple parents allowed), so a diamond topology causes
2^D recursive calls. Fix: thread an IdentityHashMap<GraphNode,Long> memo
through recursion; memoize on first visit, return cached result on revisit.
8/8 unit tests PASS; D=10 defect count=3071 vs patched O(N).

Diamond-recursion CLEAN markers added for: flink, neo4j, janusgraph,
tinkerpop, dgraph, zookeeper, storm, ant, gradle, graal, eclipse-jdt,
exposed, intellij, kotlin, scala3, hibernate-0007 (prior session work
now committed).

2026-03-29 16:59:50 -04:00

1.4 KiB

Raw Permalink Blame History

Exposed — Diamond Recursion CWE-407 Scan: CLEAN

Pattern: Recursive cycle/reachability without visited set (O(2^D) on diamond DAGs) Scan date: 2026-03-29 Scope: exposed-core/src/, exposed-jdbc/src/, exposed-r2dbc/src/

Method

Searched for isCyclic, hasCycle, createsCycle, isReachable, canReach, hasPath, detectCycle across all Kotlin sources. Examined each recursive function for missing visited-accumulator parameters.

Key candidates reviewed

`TableDepthGraph.hasCycle()`

exposed-core/src/.../core/TableDepthGraph.kt line 44.

Uses two mutable sets: visited and recursion. Both are mutableSetOf<Table>(). The recursion set tracks the current DFS path (IN_PROGRESS nodes); visited tracks completed nodes. Recursive traverse() checks both before proceeding. Classic 3-state DFS cycle detection. CLEAN.

`TableDepthGraph.sorted()`

exposed-core/src/.../core/TableDepthGraph.kt line 25.

Uses visited: mutableSetOf<Table>(). Recursive traverse() checks if (table !in visited) before visiting. CLEAN.

`fetchAllTables()`

exposed-core/src/.../core/TableDepthGraph.kt line 14.

Uses result = HashSet<Table>(). Recursive parseTable() checks if (result.add(table)) — the Set itself is the visited guard. CLEAN.

Verdict

CLEAN for diamond recursion pattern. All table dependency graph traversals use proper visited sets (mutableSetOf or HashSet). No unprotected recursive DAG traversal found.

1.4 KiB Raw Permalink Blame History