# UNDF: UNDF-2026-000000384
# UNDF: (pending)
# eclipse-jdt-0001: Scope.getCommonSuperType — ArrayList.contains() O(N²) in BFS supertypes collection

## CWE-407 — Algorithmic Complexity: O(N) ArrayList.contains() per node in BFS type hierarchy traversal

| Field        | Value |
|--------------|-------|
| ID           | eclipse-jdt-0001 |
| Severity     | HIGH |
| Ecosystem    | eclipse-jdt |
| Package      | org.eclipse.jdt.core.compiler.batch |
| File         | `org.eclipse.jdt.core.compiler.batch/src/org/eclipse/jdt/internal/compiler/lookup/Scope.java` |
| Lines        | 4273–4383 |
| Complexity   | O(N) per node; O(N²) to collect N-node supertype set |
| Hot path     | Called during type inference and common-supertype computation in the JDT compiler |

## Defect

`Scope.getCommonSuperType` performs a BFS over the complete type hierarchy of `firstType` to collect
all supertypes into `typesToVisit`. The collection is an `ArrayList<TypeBinding>`, and the dedup
guard uses `typesToVisit.contains()` — an O(N) linear scan — at every BFS step:

```java
// Scope.java:4273-4383 (DEFECT)
List<TypeBinding> typesToVisit = new ArrayList<>();   // ArrayList → contains() is O(N)
// ...
typesToVisit.add(firstType);
int max = 1;
for (int i = 0; i < max; i++) {
    TypeBinding typeToVisit = typesToVisit.get(i);
    // ...
    // Each of these contains() calls is O(i) — grows as BFS expands:
    if (!typesToVisit.contains(elementType)) {         // O(N) scan
        typesToVisit.add(elementType); max++;
    }
    // ...
    if (!typesToVisit.contains(superType)) {           // O(N) scan (×4 in different branches)
        typesToVisit.add(superType); max++;
    }
    // ... (multiple more contains() calls for interfaces and superclass)
}
```

For N types in the hierarchy, the BFS loop runs N iterations; each iteration performs one or more
`contains()` calls that scan up to i elements. Total: O(N²) comparisons.

`ReferenceBinding` confirms identity semantics (its comment says "ALL ReferenceBindings are unique
when created so equals() is the same as =="), so a `HashSet<TypeBinding>` using the existing
`hashCode()` (name-based) provides O(1) contains with correct dedup semantics.

## Fix

Add a parallel `Set<TypeBinding>` for O(1) membership testing alongside the `ArrayList` (kept for
indexed iteration via `.get(i)`):

```java
// AFTER — O(N) total for N-node BFS
List<TypeBinding> typesToVisit = new ArrayList<>();
Set<TypeBinding> typesToVisitSet = new HashSet<>();   // ADD: O(1) membership guard

typesToVisit.add(firstType);
typesToVisitSet.add(firstType);                       // ADD
int max = 1;
for (int i = 0; i < max; i++) {
    TypeBinding typeToVisit = typesToVisit.get(i);
    // ...
    // Replace all: if (!typesToVisit.contains(x)) { typesToVisit.add(x); max++; }
    // With:        if (typesToVisitSet.add(x))    { typesToVisit.add(x); max++; }
    if (typesToVisitSet.add(elementType)) {            // O(1) HashSet.add returns false if present
        typesToVisit.add(elementType); max++;
    }
    // ... (apply same replacement to all ~7 contains() checks)
}
```

## Speedup

| Types in hierarchy (N) | Before (comparisons) | After (comparisons) | Speedup |
|------------------------|----------------------|---------------------|---------|
| 20                     | ~200                 | 20                  | 10×     |
| 50                     | ~1,250               | 50                  | 25×     |
| 100                    | ~5,000               | 100                 | 50×     |

Growth before: O(N²). Growth after: O(N).
