java-topology/tools/tickets/defects/minecraft-0001.md

id	repo	file	line	status	severity	complexity	pattern	source	created
minecraft-0001	Mojang/minecraft-java-edition	net/minecraft/util/DependencySorter.java (decompiled from server-26.1.jar)	isCyclic method	unpatched	HIGH	O(E^D) worst case — exponential, no visited set in recursive DFS	recursive DFS cycle check with no visited tracking; diamond graphs cause exponential revisiting	decompiled from ~/Downloads/server.jar (server-26.1)	2026-03-24

Defect

File: net/minecraft/util/DependencySorter (decompiled) Method: isCyclic(Multimap, K from, K to) Called from: net/minecraft/tags/TagLoader — tag dependency resolution Trigger: Every world load, every /reload command, every datapack change

Description

DependencySorter.isCyclic() checks whether adding a dependency edge from → to would create a cycle. It does this via recursive DFS — but with no visited set:

private static <K> boolean isCyclic(Multimap<K, K> directDependencies, K from, K to) {
    Collection dependencies = directDependencies.get(to);
    if (dependencies.contains(from)) {
        return true;
    }
    return dependencies.stream().anyMatch(
        dep -> DependencySorter.isCyclic(directDependencies, from, dep)
    );
}

Without a visited set, the DFS revisits nodes on every branch that can reach them. For a diamond dependency graph — A depends on B and C; B and C both depend on D — isCyclic(X, A) explores D twice: once via B and once via C. For deeper diamond chains of depth D, the number of visits is 2^D.

isCyclic is called from addDependencyIfNotCyclic for every dependency edge:

private static <K> void addDependencyIfNotCyclic(Multimap<K, K> directDependencies, K from, K to) {
    if (!DependencySorter.isCyclic(directDependencies, from, to)) {
        directDependencies.put(from, to);
    }
}

And addDependencyIfNotCyclic is called for every required and optional dependency of every entry in the sorter:

this.contents.forEach((id, value) ->
    value.visitRequiredDependencies(dep ->
        DependencySorter.addDependencyIfNotCyclic(directDependencies, id, dep)));
this.contents.forEach((id, value) ->
    value.visitOptionalDependencies(dep ->
        DependencySorter.addDependencyIfNotCyclic(directDependencies, id, dep)));

Call context — TagLoader

DependencySorter is instantiated and used in net/minecraft/tags/TagLoader to order tag definitions by dependency. Tags are Minecraft's classification system: #minecraft:logs, #minecraft:planks, #forge:ores/iron, etc. Tags can reference other tags as members. The dependency sort ensures tags are resolved in order.

Trigger: Every world load, every /reload command, every /datapack enable.

Vanilla Minecraft: Hundreds of tags — tolerable. Large modpacks (Create, Thermal Expansion, Applied Energistics 2, Mekanism): thousands of tags with cross-mod dependencies. Diamond dependency patterns are endemic in modpack tag inheritance. At scale, isCyclic with exponential revisiting causes multi-second tag loading delays reported by modpack users as "lag on reload."

Fix

Add a Set<K> visited parameter to isCyclic to prevent revisiting nodes:

private static <K> boolean isCyclic(Multimap<K, K> directDependencies,
                                     K from, K to, Set<K> visited) {
    if (!visited.add(to)) {
        return false;  // already explored this node in this DFS — no cycle via here
    }
    Collection<K> dependencies = directDependencies.get(to);
    if (dependencies.contains(from)) {
        return true;
    }
    return dependencies.stream().anyMatch(
        dep -> DependencySorter.isCyclic(directDependencies, from, dep, visited)
    );
}

// Callsite:
private static <K> void addDependencyIfNotCyclic(Multimap<K, K> directDependencies,
                                                   K from, K to) {
    if (!DependencySorter.isCyclic(directDependencies, from, to, new HashSet<>())) {
        directDependencies.put(from, to);
    }
}

Complexity after fix: O(E) per isCyclic call (each node visited at most once), O(E²) total for building the dependency graph (isCyclic called once per edge, each O(E) worst case). Still not optimal, but no longer exponential.

Better fix (single-pass): Replace the per-edge cycle check with a single SCC pass over the complete dependency graph after all edges are added. This reduces total cost to O(V+E) using Tarjan or Kosaraju. The current approach (check before add) was likely chosen to produce better error messages, but the cost is too high.

Severity note

Minecraft is not open source — this is from decompiled bytecode of server-26.1.jar. Disclosure path: Mojang bug tracker (bugs.mojang.com) under "Performance" category. This affects the server jar directly and is reproducible with large modpacks.

Work items

• Reproduce: time DependencySorter execution on a modpack server with 1000+ tags
• Confirm exponential revisiting with diamond tag graph
• Patch proposal for Mojang bug tracker
• Unit test (operation count: O(E^D) before vs O(E) after on diamond-4 graph)