russell@unturf.com
78f834e1e7
InFlightMetadataCollectorImpl.buildRecursiveOrderedFkSecondPasses() lacks a visited-table set — only guards against direct self-cycles (startTable check). On diamond FK dependency graphs (A references B and C, both B and C reference D), node D is visited 2^depth times. At depth=10: 25.9x overhead; at depth=13: 124x. Fix: add Set<String> visitedTables parameter; skip re-entry with visited.add(). Unit test: HibernateFkDiamondRecursionTest.java — confirms exponential growth and correctness (both algorithms produce identical FK sets). 4/4 assertions PASS. Separate from hibernate-0004 (which addressed the O(N^2) ArrayList.contains() in the same method); that patch uses LinkedHashSet to deduplicate output but does not prevent exponential recursive traversal of intermediate diamond nodes. spring and ant: diamond recursion scan CLEAN markers added.
215 lines
7.9 KiB
Java
215 lines
7.9 KiB
Java
package unit;
|
|
|
|
import java.util.*;
|
|
|
|
/**
|
|
* Unit test for hibernate-0007: buildRecursiveOrderedFkSecondPasses diamond recursion O(2^D).
|
|
*
|
|
* The diamond structure (each level doubles paths back to a common ancestor):
|
|
*
|
|
* bottom
|
|
* / \
|
|
* left_0 right_0
|
|
* \ /
|
|
* mid_1
|
|
* / \
|
|
* left_1 right_1
|
|
* \ /
|
|
* mid_2
|
|
* ...
|
|
* top <-- startTable for outer loop iteration
|
|
*
|
|
* isADependencyOf["bottom"] = {(left_0 -> bottom), (right_0 -> bottom)}
|
|
* isADependencyOf["left_0"] = {(mid_1 -> left_0)}
|
|
* isADependencyOf["right_0"] = {(mid_1 -> right_0)}
|
|
* isADependencyOf["mid_1"] = {(left_1 -> mid_1), (right_1 -> mid_1)}
|
|
* ...
|
|
*
|
|
* "bottom" will be visited 2^D times by the buggy algorithm because there are 2^D
|
|
* paths from "top" down to "bottom" through the diamond chain.
|
|
*/
|
|
public class HibernateFkDiamondRecursionTest {
|
|
|
|
// Pair: (fromTable, toTable) representing "fromTable has FK referencing toTable"
|
|
static class FK {
|
|
final String from;
|
|
final String to;
|
|
FK(String from, String to) { this.from = from; this.to = to; }
|
|
|
|
@Override public String toString() { return from + "->" + to; }
|
|
|
|
@Override public boolean equals(Object o) {
|
|
if (!(o instanceof FK)) return false;
|
|
FK f = (FK) o;
|
|
return from.equals(f.from) && to.equals(f.to);
|
|
}
|
|
|
|
@Override public int hashCode() { return Objects.hash(from, to); }
|
|
}
|
|
|
|
static int buggyCount;
|
|
static int fixedCount;
|
|
|
|
// ---- BUGGY IMPLEMENTATION (no visitedTables) ----
|
|
static void buildOrdered_BUGGY(
|
|
LinkedHashSet<FK> ordered,
|
|
Map<String, Set<FK>> isADependencyOf,
|
|
String startTable,
|
|
String currentTable) {
|
|
buggyCount++;
|
|
Set<FK> deps = isADependencyOf.get(currentTable);
|
|
if (deps != null) {
|
|
for (FK fk : sorted(deps)) {
|
|
String dependentTable = fk.from;
|
|
if (!dependentTable.equals(startTable)) {
|
|
buildOrdered_BUGGY(ordered, isADependencyOf, startTable, dependentTable);
|
|
}
|
|
ordered.add(fk);
|
|
}
|
|
}
|
|
}
|
|
|
|
// ---- FIXED IMPLEMENTATION (visitedTables prevents re-entry) ----
|
|
static void buildOrdered_FIXED(
|
|
LinkedHashSet<FK> ordered,
|
|
Map<String, Set<FK>> isADependencyOf,
|
|
String startTable,
|
|
String currentTable,
|
|
Set<String> visitedTables) {
|
|
fixedCount++;
|
|
if (!visitedTables.add(currentTable)) {
|
|
return; // already visited this table — skip to avoid O(2^D) blowup
|
|
}
|
|
Set<FK> deps = isADependencyOf.get(currentTable);
|
|
if (deps != null) {
|
|
for (FK fk : sorted(deps)) {
|
|
String dependentTable = fk.from;
|
|
if (!dependentTable.equals(startTable)) {
|
|
buildOrdered_FIXED(ordered, isADependencyOf, startTable, dependentTable, visitedTables);
|
|
}
|
|
ordered.add(fk);
|
|
}
|
|
}
|
|
}
|
|
|
|
static List<FK> sorted(Set<FK> fks) {
|
|
List<FK> list = new ArrayList<>(fks);
|
|
list.sort(Comparator.comparing((FK f) -> f.from).thenComparing(f -> f.to));
|
|
return list;
|
|
}
|
|
|
|
/**
|
|
* Build a diamond chain of depth D.
|
|
* Returns the map and the name of the "top" table (used as startTable).
|
|
*/
|
|
static Map<String, Set<FK>> buildDiamondGraph(int depth) {
|
|
Map<String, Set<FK>> map = new LinkedHashMap<>();
|
|
String prev = "bottom";
|
|
for (int i = 0; i < depth; i++) {
|
|
String left = "left_" + i;
|
|
String right = "right_" + i;
|
|
String top = (i < depth - 1) ? "mid_" + (i + 1) : "top";
|
|
|
|
// left and right both have FKs referencing prev
|
|
// -> isADependencyOf[prev] gets two entries
|
|
map.computeIfAbsent(prev, k -> new LinkedHashSet<>()).add(new FK(left, prev));
|
|
map.computeIfAbsent(prev, k -> new LinkedHashSet<>()).add(new FK(right, prev));
|
|
|
|
// top has FKs referencing left and right
|
|
map.computeIfAbsent(left, k -> new LinkedHashSet<>()).add(new FK(top, left));
|
|
map.computeIfAbsent(right, k -> new LinkedHashSet<>()).add(new FK(top, right));
|
|
|
|
prev = top;
|
|
}
|
|
return map;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
System.out.println("=== hibernate-0007: Diamond Recursion Test ===\n");
|
|
|
|
// Test 1: Measure exponential growth across depths
|
|
System.out.printf("%-8s %-12s %-12s %-10s%n", "Depth", "Buggy calls", "Fixed calls", "Ratio");
|
|
for (int d = 1; d <= 13; d++) {
|
|
Map<String, Set<FK>> map = buildDiamondGraph(d);
|
|
|
|
buggyCount = 0;
|
|
LinkedHashSet<FK> buggyRes = new LinkedHashSet<>();
|
|
for (String tbl : map.keySet()) {
|
|
buildOrdered_BUGGY(buggyRes, map, tbl, tbl);
|
|
}
|
|
int bCalls = buggyCount;
|
|
|
|
fixedCount = 0;
|
|
LinkedHashSet<FK> fixedRes = new LinkedHashSet<>();
|
|
for (String tbl : map.keySet()) {
|
|
buildOrdered_FIXED(fixedRes, map, tbl, tbl, new HashSet<>());
|
|
}
|
|
int fCalls = fixedCount;
|
|
|
|
double ratio = (fCalls > 0) ? (double) bCalls / fCalls : 0;
|
|
System.out.printf("%-8d %-12d %-12d %-10.1fx%n", d, bCalls, fCalls, ratio);
|
|
}
|
|
|
|
// Test 2: At depth >= 10, buggy should be at least 20x more calls than fixed
|
|
{
|
|
Map<String, Set<FK>> map = buildDiamondGraph(10);
|
|
|
|
buggyCount = 0;
|
|
LinkedHashSet<FK> buggyRes = new LinkedHashSet<>();
|
|
for (String tbl : map.keySet()) {
|
|
buildOrdered_BUGGY(buggyRes, map, tbl, tbl);
|
|
}
|
|
int bCalls = buggyCount;
|
|
|
|
fixedCount = 0;
|
|
LinkedHashSet<FK> fixedRes = new LinkedHashSet<>();
|
|
for (String tbl : map.keySet()) {
|
|
buildOrdered_FIXED(fixedRes, map, tbl, tbl, new HashSet<>());
|
|
}
|
|
int fCalls = fixedCount;
|
|
|
|
double ratio = (double) bCalls / fCalls;
|
|
System.out.printf("%nDepth-10: buggy=%d, fixed=%d, ratio=%.1fx%n", bCalls, fCalls, ratio);
|
|
|
|
assert ratio >= 20.0 : "Expected >=20x blowup at depth=10, got " + ratio;
|
|
System.out.println("ASSERT PASS: buggy/fixed ratio >= 20x at depth=10");
|
|
}
|
|
|
|
// Test 3: Correctness — both produce identical FK sets
|
|
for (int d = 1; d <= 6; d++) {
|
|
Map<String, Set<FK>> map = buildDiamondGraph(d);
|
|
|
|
buggyCount = 0;
|
|
LinkedHashSet<FK> buggyRes = new LinkedHashSet<>();
|
|
for (String tbl : map.keySet()) {
|
|
buildOrdered_BUGGY(buggyRes, map, tbl, tbl);
|
|
}
|
|
|
|
fixedCount = 0;
|
|
LinkedHashSet<FK> fixedRes = new LinkedHashSet<>();
|
|
for (String tbl : map.keySet()) {
|
|
buildOrdered_FIXED(fixedRes, map, tbl, tbl, new HashSet<>());
|
|
}
|
|
|
|
assert buggyRes.equals(fixedRes) :
|
|
"depth=" + d + ": buggy=" + buggyRes + " fixed=" + fixedRes;
|
|
}
|
|
System.out.println("ASSERT PASS: buggy and fixed produce identical FK sets at depths 1-6");
|
|
|
|
// Test 4: Fixed should complete depth=20 quickly; buggy would need ~2M calls
|
|
{
|
|
Map<String, Set<FK>> map = buildDiamondGraph(20);
|
|
fixedCount = 0;
|
|
LinkedHashSet<FK> fixedRes = new LinkedHashSet<>();
|
|
for (String tbl : map.keySet()) {
|
|
buildOrdered_FIXED(fixedRes, map, tbl, tbl, new HashSet<>());
|
|
}
|
|
int fCalls = fixedCount;
|
|
System.out.printf("%nDepth-20 fixed calls: %d (should be small)%n", fCalls);
|
|
assert fCalls < 100_000 : "Fixed should be O(N) at depth=20: " + fCalls;
|
|
System.out.println("ASSERT PASS: fixed is O(N) even at depth=20");
|
|
}
|
|
|
|
System.out.println("\n=== ALL ASSERTIONS PASSED ===");
|
|
}
|
|
}
|