russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
40 lines
2 KiB
Markdown
40 lines
2 KiB
Markdown
# Tickets
|
||
|
||
| # | Title | Module | Severity | Status |
|
||
|---|-------|--------|----------|--------|
|
||
| [0001](0001-tarjan-ov2-stack-contains.md) | Tarjan SCC: `stack.contains(n)` — O(V²) | jdk.compiler | high | open |
|
||
| [0002](0002-inference-graph-findnode-linear-scan.md) | `InferenceGraph.findNode()` O(N) scan, called O(N³) total | jdk.compiler | high | open |
|
||
| [0003](0003-module-hasher-topo-deque-contains.md) | `ModuleHashesBuilder$TopoSorter` `Deque.contains()` | **java.base** | medium | open |
|
||
| [0004](0004-dependencies-node-list-contains.md) | `Dependencies$Node.addDependency()` `List.contains()` dedup | jdk.compiler | low | open |
|
||
| [0005](0005-inference-context-isequiv-containsall.md) | `InferenceContext.isEquiv()` `List.containsAll()` bound comparison | jdk.compiler | low | open |
|
||
|
||
## Pattern
|
||
|
||
Same defect replicated in 4 locations across 2 modules:
|
||
**O(n) linear collection membership check where O(1) is available.**
|
||
|
||
In every case a flag field, HashSet, or dedicated boolean already exists or is trivially addable.
|
||
The background bytecode scan of all 69 JDK modules confirmed no additional hits beyond these five.
|
||
The `active` field in `TarjanNode` (0001) is the most direct evidence: maintained correctly, never read.
|
||
|
||
## Cascade
|
||
|
||
```
|
||
javac compilation
|
||
└─ type inference (Infer.java)
|
||
├─ GraphSolver.solve()
|
||
│ └─ InferenceGraph.initNodes()
|
||
│ └─ GraphUtils.tarjan() ← DEFECT 0001: O(V²)
|
||
└─ DeferredAttr.buildStuckGraph()
|
||
└─ canInfluence() × N²
|
||
├─ findNode() ← DEFECT 0002: O(N) per call → O(N³) total
|
||
└─ closure() ← DEFECT 0002: uncached O(V+E) per call
|
||
|
||
jlink image creation
|
||
└─ ModuleHashesBuilder.computeHashes()
|
||
└─ TopoSorter.visit() ← DEFECT 0003: Deque.contains() O(N)
|
||
|
||
debug compilation (-XDcompletionDeps)
|
||
└─ Dependencies$GraphDependencies
|
||
└─ Node.addDependency() ← DEFECT 0004: List.contains() O(N)
|
||
```
|