# UNDF: UNDF-2026-000000464
# hibernate-0007: buildRecursiveOrderedFkSecondPasses diamond recursion O(2^D)

## Summary

**Severity:** HIGH
**Component:** `hibernate-core`
**File:** `org/hibernate/boot/internal/InFlightMetadataCollectorImpl.java`
**Method:** `buildRecursiveOrderedFkSecondPasses` (line 1835)
**CWE:** CWE-407 (Algorithmic Complexity — Exponential)

## Defect

`buildRecursiveOrderedFkSecondPasses` recurses over FK dependency tables without a
visited-table set. The only cycle guard is a `startTable` identity check
(`dependentTable.compareTo(startTable) != 0`), which only prevents re-entering the
single starting table — it does **not** prevent exponential re-visitation of
intermediate diamond nodes.

```java
// DEFECT: no Set<String> visitedTables parameter — exponential on diamond graphs
private void buildRecursiveOrderedFkSecondPasses(
        LinkedHashSet<FkSecondPass> orderedFkSecondPasses,
        Map<String, Set<FkSecondPass>> isADependencyOf,
        String startTable,
        String currentTable) {
    final Set<FkSecondPass> dependencies = isADependencyOf.get( currentTable );
    if ( dependencies != null ) {
        for ( var fkSecondPass : dependencies ) {
            final String dependentTable = fkSecondPass.getValue().getTable()...;
            if ( dependentTable.compareTo( startTable ) != 0 ) {
                // recurse with no visitedTables guard — each diamond node visited 2^D times
                buildRecursiveOrderedFkSecondPasses( orderedFkSecondPasses, isADependencyOf,
                        startTable, dependentTable );
            }
            orderedFkSecondPasses.add( fkSecondPass );
        }
    }
}
```

## Diamond Graph Scenario

```
isADependencyOf["T2"] = {fk_T1_to_T2}
isADependencyOf["T3"] = {fk_T1_to_T3}
isADependencyOf["T4"] = {fk_T2_to_T4, fk_T3_to_T4}  ← diamond join
```

When outer loop processes `"T4"`:
- Recurse into T2 → recurse into T1 (1st visit)
- Recurse into T3 → recurse into T1 (2nd visit — **redundant**)

With D diamond levels: T1 (the common ancestor) is visited `2^D` times.

## Complexity

| Depth | Recursive calls to `buildRecursive` |
|-------|--------------------------------------|
| 1     | 3 (T4→T2→T1, T4→T3→T1)              |
| 2     | 7                                    |
| D     | 2^(D+1) − 1                          |

At D=20 diamond chains → >2 million redundant recursive calls.

## Fix

Add a `Set<String> visitedTables` parameter. Pass it into every recursive call.
Skip tables already in `visitedTables`. This reduces complexity to O(T+E).

```java
private void buildRecursiveOrderedFkSecondPasses(
        LinkedHashSet<FkSecondPass> orderedFkSecondPasses,
        Map<String, Set<FkSecondPass>> isADependencyOf,
        String startTable,
        String currentTable,
        Set<String> visitedTables) {        // ← NEW PARAMETER
    if ( !visitedTables.add( currentTable ) ) {  // ← O(1) dedup
        return;
    }
    final Set<FkSecondPass> dependencies = isADependencyOf.get( currentTable );
    if ( dependencies != null ) {
        for ( var fkSecondPass : dependencies ) {
            final String dependentTable = fkSecondPass.getValue().getTable()...;
            if ( dependentTable.compareTo( startTable ) != 0 ) {
                buildRecursiveOrderedFkSecondPasses( orderedFkSecondPasses, isADependencyOf,
                        startTable, dependentTable, visitedTables );  // ← pass along
            }
            orderedFkSecondPasses.add( fkSecondPass );
        }
    }
}
```

Caller initialises: `new HashSet<>()` per outer-loop iteration.

## Speedup

At D=10 diamond depth: **1023x** fewer recursive calls.
At D=20 diamond depth: **1,048,575x** fewer recursive calls.
