# UNDF: UNDF-2026-000000578
# liquibase-0001: DependencyUtil.DependencyGraph.recursiveSizeDepth — O(2^D) diamond re-traversal + O(N²) evaluatedNodes list scan

## CWE-407 — Algorithmic Complexity: O(2^D) recursive diamond re-traversal; O(N²) list scan in evaluated-node guard

| Field        | Value |
|--------------|-------|
| ID           | liquibase-0001 |
| Severity     | MEDIUM |
| Ecosystem    | liquibase |
| Package      | liquibase-standard |
| File         | `liquibase-standard/src/main/java/liquibase/util/DependencyUtil.java` |
| Lines        | 132–155 |
| Complexity   | O(2^D) re-traversal on diamond dependency graphs; O(N) guard scan |
| Hot path     | Called during `computeDependencies()` at changelog load time |

## Defect

`DependencyGraph.recursiveSizeDepth(GraphNode<T> node, int safetyCounter)` recursively
computes the total number of pending (not yet evaluated) nodes reachable from a starting
node. It uses `isAlreadyEvaluated(node)` as an early-exit guard, which calls
`evaluatedNodes.contains(node)` — an **O(N) linear scan** on an `ArrayList<GraphNode<T>>`.

On a diamond-shaped dependency graph (node A depends on B and C; both B and C depend on D),
D is NOT in `evaluatedNodes` during the estimation phase, so the guard does not fire for D.
The traversal visits D once via B and once via C — **2^D visits** at depth D.

```java
// liquibase-standard/src/main/java/liquibase/util/DependencyUtil.java:132-154 (DEFECT)
private final List<GraphNode<T>> evaluatedNodes = new ArrayList<>();   // O(N) contains()

private int recursiveSizeDepth(GraphNode<T> node, int safetyCounter) {
    if (safetyCounter > 1000) { return -1; }
    if (isAlreadyEvaluated(node)) {              // O(N) scan — misses diamond nodes
        return 0;
    } else if (node.getGoingOutNodes() == null || node.getGoingOutNodes().isEmpty()) {
        return 1;
    }
    int sum = 0;
    safetyCounter++;
    for (GraphNode<T> n : node.getGoingOutNodes()) {
        int depth = recursiveSizeDepth(n, safetyCounter);   // recurse — no visited guard
        if (depth < 0) return -1;
        sum += depth;
    }
    return node.getGoingOutNodes().size() + sum;
}

private boolean isAlreadyEvaluated(GraphNode<T> node) {
    return evaluatedNodes.contains(node);          // O(N) linear scan
}
```

Two distinct defects:

1. **Diamond re-traversal:** `recursiveSizeDepth` has no visited set.  On a diamond graph
   it visits shared nodes 2^D times. The existing `safetyCounter > 1000` guard is an
   emergency brake, not a fix — it truncates the estimate incorrectly and fires only
   when recursion nesting exceeds 1000, not when nodes are revisited.

2. **O(N) evaluatedNodes scan:** `evaluatedNodes` is an `ArrayList`. Each call to
   `isAlreadyEvaluated` or `areAlreadyEvaluated` is an O(N) scan.
   With E edges in the graph, total cost: O(E × N).

## Fix

Replace `evaluatedNodes: List<GraphNode<T>>` with a `Set<GraphNode<T>>` for O(1) membership,
and add a persistent `Set<GraphNode<T>> seen` parameter to `recursiveSizeDepth`. The `seen`
set is **not** cleared on backtrack — it accumulates all visited nodes across the entire
call tree, preventing any node from being counted twice regardless of how many paths lead
to it (diamond, fan-out, or any DAG shape).

```java
// AFTER — O(N+E) total
private final Set<GraphNode<T>> evaluatedNodes = new LinkedHashSet<>();  // O(1) contains()

// Public entry point: allocate seen set once per depth-check call
private int recursiveSizeDepth(List<GraphNode<T>> nodes) {
    if (nodes == null) return 0;
    Set<GraphNode<T>> seen = new HashSet<>();
    int sum = 0;
    for (GraphNode<T> node : nodes) {
        int depth = recursiveSizeDepth(node, 0, seen);
        if (depth < 0) return -1;
        sum += depth;
    }
    return sum;
}

private int recursiveSizeDepth(GraphNode<T> node, int safetyCounter,
                                Set<GraphNode<T>> seen) {
    if (safetyCounter > 1000) { return -1; }
    if (evaluatedNodes.contains(node)) { return 0; }  // O(1) — already emitted
    if (!seen.add(node)) { return 0; }                // O(1) — already counted this call
    // NOTE: do NOT remove from `seen` on return — persistent across all branches
    if (node.getGoingOutNodes() == null || node.getGoingOutNodes().isEmpty()) {
        return 1;
    }
    int sum = 0;
    for (GraphNode<T> n : node.getGoingOutNodes()) {
        int depth = recursiveSizeDepth(n, safetyCounter + 1, seen);
        if (depth < 0) return -1;
        sum += depth;
    }
    return node.getGoingOutNodes().size() + sum;
}
```

Also change `areAlreadyEvaluated` to use the Set:
```java
private boolean areAlreadyEvaluated(List<GraphNode<T>> nodes) {
    return evaluatedNodes.containsAll(nodes);  // O(K) with Set backing, vs O(K×N) with List
}
```

## Speedup

| Diamond depth (D) | Before (visits) | After (visits) | Speedup |
|------------------|----------------|----------------|---------|
| 10               | 4,093          | 41             | 100×    |
| 12               | 16,381         | 49             | 334×    |
| 15               | 131,069        | 61             | 2,148×  |

Measured by unit test: `defects/liquibase/unit/unit/test_liquibase_0001.py`

Growth before: O(2^D). Growth after: O(D+nodes) linear.
