# UNDF: UNDF-2026-000000472
# nifi-0001: Controller Service topological sort O(S²) → O(S)

## Location
Primary:
`nifi-framework-bundle/nifi-framework/nifi-framework-components/src/main/java/org/apache/nifi/controller/service/StandardControllerServiceProvider.java`
Lines 431–465 (`determineEnablingOrder`)

Duplicate:
`nifi-framework-bundle/nifi-framework/nifi-web/nifi-web-api/src/main/java/org/apache/nifi/web/util/LocalComponentLifecycle.java`
Lines 410–438 (same function, copy-pasted)

## Severity
HIGH — triggered every time controller services are enabled (startup, flow deployment, restart)

## Description
`determineEnablingOrder` performs a depth-first topological sort of controller service
dependencies. The `orderedNodes` accumulator is a `List<ControllerServiceNode>`, and
every node addition is guarded by `orderedNodes.contains(node)` — an O(N) scan.

The public method iterates over all S services, calling the recursive private method
for each. In the worst case (a chain of S services), the list grows to S entries and
each `contains()` check scans the whole list → O(S²) total.

## Root Cause
```java
// StandardControllerServiceProvider.java line 431–441
static List<List<ControllerServiceNode>> determineEnablingOrder(
        final Map<String, ControllerServiceNode> serviceNodeMap) {
    final List<List<ControllerServiceNode>> orderedNodeLists = new ArrayList<>();
    for (final ControllerServiceNode node : serviceNodeMap.values()) {  // O(S) outer
        final List<ControllerServiceNode> branch = new ArrayList<>();
        determineEnablingOrder(serviceNodeMap, node, branch, new HashSet<>());
        orderedNodeLists.add(branch);
    }
    return orderedNodeLists;
}

private static void determineEnablingOrder(...,
        final List<ControllerServiceNode> orderedNodes,   // ← List, not Set
        final Set<ControllerServiceNode> visited) {
    ...
    for (final Map.Entry<PropertyDescriptor, String> entry : ...) {  // O(P) props
        ...
        if (!orderedNodes.contains(referencedNode)) {  // O(N) scan → O(S×P×N) total
            ...
            determineEnablingOrder(...);
        }
    }
    if (!orderedNodes.contains(contextNode)) {          // O(N) scan again
        orderedNodes.add(contextNode);
    }
}
```

## Fix
Track membership in a companion `Set<ControllerServiceNode>` alongside the ordered list:

```java
private static void determineEnablingOrder(
        final Map<String, ControllerServiceNode> serviceNodeMap,
        final ControllerServiceNode contextNode,
        final List<ControllerServiceNode> orderedNodes,
        final Set<ControllerServiceNode> orderedSet,   // ← new parameter
        final Set<ControllerServiceNode> visited) {

    if (visited.contains(contextNode)) return;

    for (final Map.Entry<PropertyDescriptor, String> entry : ...) {
        if (entry.getKey().getControllerServiceDefinition() != null) {
            final String referencedServiceId = entry.getValue();
            if (referencedServiceId != null) {
                final ControllerServiceNode referencedNode = serviceNodeMap.get(referencedServiceId);
                if (!orderedSet.contains(referencedNode)) {      // O(1)
                    visited.add(contextNode);
                    determineEnablingOrder(serviceNodeMap, referencedNode, orderedNodes, orderedSet, visited);
                }
            }
        }
    }

    if (!orderedSet.contains(contextNode)) {                     // O(1)
        orderedNodes.add(contextNode);
        orderedSet.add(contextNode);
    }
}
```

Apply the same fix to `LocalComponentLifecycle.java`.

## Complexity
| | Before | After |
|---|---|---|
| determineEnablingOrder | O(S²×P) | O(S×P) |

Where S=services, P=properties per service.
At S=200 services, P=10 props: 400,000 ops → 2,000 ops (200x improvement).

## Note
This is structurally identical to the Airflow (airflow-0001) and Maven topological sort
defects found in previous waves. The fix pattern is the same: companion HashSet for
O(1) membership, ordered List for sequence.
