java-topology/docs/tickets/0003-module-hasher-topo-deque-contains.md

0003 — ModuleHashesBuilder$TopoSorter: O(N) Deque.contains() for cycle detection

Status: open Severity: performance — medium Component: java.base / jdk.internal.module.ModuleHashesBuilder$TopoSorter Module: java.base — ships in every JDK and JRE

---

Root Cause

ModuleHashesBuilder.java (inner class TopoSorter.visit()), bytecode instruction 57:

invokeinterface java/util/Deque.contains:(Ljava/lang/Object;)Z

The visit() method uses an ArrayDeque as a DFS stack and calls Deque.contains() to detect back edges (cycles in the module dependency graph). ArrayDeque.contains() is a linear scan — O(N).

This is the same structural defect as ticket 0001 (GraphUtils.Tarjan) in a different module and a different layer of the stack.

Source pattern (reconstructed from bytecode):

private void visit(T node, Set<T> visited, Deque<T> stack) {
    if (visited.contains(node)) {
        if (stack.contains(node)) {          // O(N) — THE DEFECT
            throw new IllegalArgumentException("Cycle detected: " + node + " -> " + children(node));
        }
        return;
    }
    visited.add(node);
    stack.push(node);
    children(node).forEach(child -> visit(child, visited, stack));
    stack.pop();
    result.addLast(node);
}

Fix — one boolean field per node, or a HashSet<T> onStack:

Set<T> onStack = new HashSet<>();   // O(1) contains

private void visit(T node, Set<T> visited, Deque<T> stack, Set<T> onStack) {
    if (visited.contains(node)) {
        if (onStack.contains(node)) {        // O(1)
            throw new IllegalArgumentException("Cycle: " + node);
        }
        return;
    }
    visited.add(node);
    stack.push(node);
    onStack.add(node);                       // O(1)
    children(node).forEach(...);
    stack.pop();
    onStack.remove(node);                    // O(1)
    result.addLast(node);
}

---

Where This Fires

ModuleHashesBuilder is called by jlink during custom runtime image creation:

jlink → ModuleHashesBuilder.computeHashes() → new TopoSorter(graph) → visit()

The module dependency graph fed to this sorter is the full transitive closure of the modules included in the image. For a typical server JDK image with 20–50 modules, this is manageable. For large multi-module applications using jlink with 100+ modules, the O(N²) degradation is measurable.

---

Significance

This defect lives in java.base — the lowest-level module present in every JDK/JRE. The same pattern (Deque.contains() for on-stack check) replicated here independently of GraphUtils.Tarjan shows this is a systemic pattern in the JDK codebase, not an isolated incident.

---

Complexity

V (modules)	Defective contains() calls	Fixed contains() calls
20	≤ 190	≤ 20
50	≤ 1,225	≤ 50
100	≤ 4,950	≤ 100

For small module graphs, impact is negligible. For large jlink builds or module graphs with deep dependency chains, this compounds with other O(N²) patterns.