russell@unturf.com
1dee074618
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).
1.7 KiB
GraalVM — 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: compiler/src/, truffle/src/, substratevm/src/
Method
Searched for isCyclic, hasCycle, createsCycle, isReachable, canReach,
hasPath, detectCycle across all Java sources. Examined recursive functions
for missing visited-accumulator parameters.
Key candidates reviewed
CFGLoop.isAncestorOrSelf()
compiler/src/.../cfg/CFGLoop.java line 125.
Iterative traversal up a tree via getParent() chain — not a DAG traversal. CLEAN.
SimpleCyclesIterator.findCyclesInSCG()
platform/core-impl/.../graph/impl/SimpleCyclesIterator.java line 237.
Johnson's algorithm implementation. Uses myBlocked (HashSet) as visited/blocked set.
Recursive calls pass startIndex and vertexIndex for the subgraph indexing.
Full state is tracked in instance fields (myVIndex, myVLowlink, myPathSet). CLEAN.
Truffle DSL SpecializationData.getBoundCachesImpl()
truffle/src/.../model/SpecializationData.java line 471.
Signature: private Set<CacheExpression> getBoundCachesImpl(Set<DSLExpression> visitedExpressions, ...)
Explicitly takes and uses a visitedExpressions Set. CLEAN.
BytecodeParser.Target.isReachable()
compiler/src/.../java/BytecodeParser.java line 906.
Returns a stored field — not a graph traversal. CLEAN.
Verdict
CLEAN for diamond recursion pattern. GraalVM uses EconomicSet, NodeBitMap,
instance-field visited tracking (Tarjan/Johnson algorithms), and explicit Set
parameters throughout. No unprotected recursive DAG traversal found.