engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/defects/eclipse-jdt/patch/eclipse-jdt-diamond-recursion-CLEAN.md
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

2.2 KiB
Raw Permalink Blame History

Eclipse JDT — 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: org.eclipse.jdt.core/, org.eclipse.jdt.core.compiler.batch/

Method

Searched for hasCycle, isCyclic, isReachable, canReach, hasPath, detectCycle across all Java sources. Examined each recursive function for a missing visited-accumulator parameter.

Key candidates reviewed

ClassScope.detectHierarchyCycle()

org.eclipse.jdt.core.compiler.batch/.../lookup/ClassScope.java line 1474.

Recursive — calls itself at lines 1517 and 1535. However, it avoids diamond blowup via per-node memoization embedded in TagBits:

  • Sets TagBits.BeginHierarchyCheck on each node before descending
  • Checks isHierarchyBeingActivelyConnected() (an IN_PROGRESS flag) before recursing
  • Checks (superType.tagBits & TagBits.BeginHierarchyCheck) == 0 to skip already-visited nodes
  • For binary supertypes, propagates TagBits.HierarchyHasProblems upward to avoid re-expansion

This is a "colored node" visited-set pattern where the visited state lives on the node object itself rather than in an external set. Equivalent complexity to DFS with a visited set — O(V+E). Not the diamond recursion anti-pattern.

InferenceContext18.isReachable()

org.eclipse.jdt.core.compiler.batch/.../lookup/InferenceContext18.java line 1688.

Signature: private boolean isReachable(Map<ConstraintFormula,Set<ConstraintFormula>> deps, ConstraintFormula from, ConstraintFormula to, Set<ConstraintFormula> nodesVisited, Set<ConstraintFormula> nodesInCycle)

Explicitly takes a nodesVisited set parameter — nodesVisited.add(from) at line 1695 is the visited guard. CLEAN.

ModuleBinding.collectAllDependencies() / collectTransitiveDependencies()

org.eclipse.jdt.core.compiler.batch/.../lookup/ModuleBinding.java lines 419, 426.

Uses deps.add(m) — the Set parameter itself is the visited accumulator. If add() returns false (already present), the recursive call is skipped. CLEAN.

Verdict

CLEAN for diamond recursion pattern. Eclipse JDT uses either per-node TagBits memoization or explicit Set parameters to prevent diamond blowup. No unprotected recursive DAG traversal found.