engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/tools/tickets/defects/javac-0001.md
russell@unturf.com db29a08762 undefect. CWE-407 — 92 sites, 42 ecosystems 
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections.
Squash of 94 local commits onto remote master.
2026-03-26 19:48:18 -04:00

1.1 KiB
Raw Permalink Blame History

id repo severity status created
javac-0001 openjdk HIGH patched 2026-03-23

Defect

File: src/jdk.compiler/.../javac/comp/GraphUtils.java:186 Pattern: stack.contains(n) in Tarjan SCC Complexity: O(V²) Language: Java

Description

Tarjan's strongly connected components algorithm maintains a stack of nodes currently under exploration. At line 186, the implementation tests stack membership using stack.contains(n) on a List, requiring a linear scan of the stack for every node visited. Since this check is performed for every edge in the graph, the overall algorithm degrades from O(V+E) to O(V²+VE) for dense graphs.

Fix

Replace: stack.contains(n) With: onStack.contains(n) Data structure change: List<Node> stack → HashSet<Node> onStack + Deque<Node> stack

Work required

  • Patch in defects/javac/patch/
  • Unit test — asserts exact operation counts before/after (in defects/javac/unit/)
  • Integration test (in defects/javac/integration/)
  • Benchmark — before/after on V=100,200,400,800 (in defects/javac/bench/)
  • White paper section