# 0002 — InferenceGraph.findNode(): O(N) linear scan, called O(N²·S) times

**Status:** open
**Severity:** performance — high
**Component:** `jdk.compiler / com.sun.tools.javac.comp.Infer$GraphSolver$InferenceGraph`
**Depends on:** 0001 (Tarjan fix removes some pressure, but this is independent)

---

## Root Cause

`Infer.java:1850` — `InferenceGraph.findNode()`:

```java
public Node findNode(Type t) {
    for (Node n : nodes) {          // O(N) linear scan over ArrayList
        if (n.data.contains(t)) {
            return n;
        }
    }
    return null;
}
```

`nodes` is an `ArrayList<Node>`. Every lookup is a full scan. There is no index.

---

## Call Site: `DeferredAttr.buildStuckGraph()`

`DeferredAttr.java:690-695` — nested loop:

```java
for (StuckNode sn1 : nodes) {
    for (StuckNode sn2 : nodes) {
        if (sn1 != sn2 && canInfluence(graph, sn2, sn1)) { // O(N²) calls
            sn1.deps.add(sn2);
        }
    }
}
```

`canInfluence()` (`DeferredAttr.java:700-715`):

```java
boolean canInfluence(InferenceGraph graph, StuckNode sn1, StuckNode sn2) {
    for (Type inputVar : sn2.data.deferredStuckPolicy.stuckVars()) {
        InferenceGraph.Node inputNode = graph.findNode(inputVar);   // O(N) scan
        if (inputNode != null) {
            Set<InferenceGraph.Node> inputClosure = inputNode.closure(); // O(V+E) DFS, NOT cached
            if (outputVars.stream()
                    .map(graph::findNode)   // O(N) scan per output var
                    .anyMatch(inputClosure::contains)) {
                return true;
            }
        }
    }
    return false;
}
```

---

## Complexity

| Layer | Defect | Cost |
|-------|--------|------|
| `buildStuckGraph()` outer loop | O(N²) calls to `canInfluence()` | inherent |
| `canInfluence()` → `findNode()` | O(N) scan per call | should be O(1) |
| `canInfluence()` → `closure()` | O(V+E) per call, **recomputed every time** | should be cached |
| `canInfluence()` → `outputVars.map(findNode)` | O(S·N) per call | should be O(S) |

**Total: O(N² · S · N) = O(N³)** where N = inference variable count, S = stuck variables per node.

With a HashMap index: `findNode()` becomes O(1) → total drops to **O(N² · S · (V+E))**.
With closure caching: drops further to **O(N² · S)**.

---

## Fix

**Fix 1 — index `nodes` by type:**
```java
// Replace ArrayList<Node> nodes with:
Map<Type, Node> nodeIndex = new LinkedHashMap<>();

public Node findNode(Type t) {
    return nodeIndex.get(t);   // O(1)
}
```

**Fix 2 — cache `closure()` per node:**
```java
private Set<Node> cachedClosure = null;

protected Set<Node> closure() {
    if (cachedClosure == null) {
        cachedClosure = new LinkedHashSet<>();
        closureInternal(cachedClosure);
    }
    return cachedClosure;
}
// invalidate cachedClosure in graphChanged() and mergeWith()
```

---

## Relationship to 0001

Ticket 0001 fixes Tarjan from O(V²) to O(V+E). This ticket fixes the caller layer:
`buildStuckGraph()` calls Tarjan AFTER `canInfluence()` builds the stuck graph.
Both defects are independent and compound: fixing 0001 alone doesn't fix 0002.