# UNDF: UNDF-2026-000000597
# UNDF: (pending)
# jackson-0002: ClassUtil._addRawSuperTypes — ArrayList.contains() O(N²) in recursive supertype collection

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

| Field        | Value |
|--------------|-------|
| ID           | jackson-0002 |
| Severity     | MEDIUM |
| Ecosystem    | jackson-databind |
| Package      | com.fasterxml.jackson.databind |
| File         | `src/main/java/tools/jackson/databind/util/ClassUtil.java` |
| Lines        | 61–107 |
| Complexity   | O(N) per type; O(N²) to collect N-type hierarchy |
| Hot path     | Called from `findRawSuperTypes()` during mixin class resolution |

## Defect

`ClassUtil._addRawSuperTypes` recursively collects the full class/interface hierarchy. To deduplicate it
calls `result.contains(cls)` where `result` is an `ArrayList<Class<?>>` — an O(N) linear scan:

```java
// ClassUtil.java:61-107 (DEFECT)
public static List<Class<?>> findRawSuperTypes(Class<?> cls, Class<?> endBefore, boolean addClassItself) {
    // ...
    List<Class<?>> result = new ArrayList<Class<?>>(8);   // ArrayList → contains() is O(N)
    _addRawSuperTypes(cls, endBefore, result, addClassItself);
    return result;
}

private static void _addRawSuperTypes(Class<?> cls, Class<?> endBefore,
        Collection<Class<?>> result, boolean addClassItself) {
    if (cls == endBefore || cls == null || cls == Object.class) { return; }
    if (addClassItself) {
        if (result.contains(cls)) {     // O(N) linear scan
            return;
        }
        result.add(cls);
    }
    for (Class<?> intCls : cls.getInterfaces()) {
        _addRawSuperTypes(intCls, endBefore, result, true);   // recurses into each interface
    }
    _addRawSuperTypes(cls.getSuperclass(), endBefore, result, true);   // recurses up superclass chain
}
```

For a class hierarchy with N types (classes + interfaces), `result.contains()` is called N times against
a growing ArrayList, giving O(N²) total comparisons. Diamond hierarchies (A implements B and C, both
extend D) are correctly deduplicated, but the dedup cost is O(N) per call.

## Fix

Change `findRawSuperTypes` to use a `LinkedHashSet` internally for O(1) membership and preserved
insertion order, then convert to List before returning:

```java
// AFTER — O(N) total for N-type hierarchy
public static List<Class<?>> findRawSuperTypes(Class<?> cls, Class<?> endBefore, boolean addClassItself) {
    if ((cls == null) || (cls == endBefore) || (cls == Object.class)) {
        return Collections.emptyList();
    }
    LinkedHashSet<Class<?>> result = new LinkedHashSet<>(8);   // O(1) contains, preserves order
    _addRawSuperTypes(cls, endBefore, result, addClassItself);
    return new ArrayList<>(result);
}

private static void _addRawSuperTypes(Class<?> cls, Class<?> endBefore,
        Collection<Class<?>> result, boolean addClassItself) {
    if (cls == endBefore || cls == null || cls == Object.class) { return; }
    if (addClassItself) {
        if (!result.add(cls)) {    // O(1): LinkedHashSet.add() returns false if already present
            return;
        }
        // No separate result.add(cls) needed — add() already inserted it
    }
    for (Class<?> intCls : cls.getInterfaces()) {
        _addRawSuperTypes(intCls, endBefore, result, true);
    }
    _addRawSuperTypes(cls.getSuperclass(), endBefore, result, true);
}
```

## Speedup

| Types in hierarchy (N) | Before (comparisons) | After (comparisons) | Speedup |
|------------------------|----------------------|---------------------|---------|
| 10                     | 55                   | 10                  | 5.5×    |
| 30                     | 465                  | 30                  | 15.5×   |
| 50                     | 1,275                | 50                  | 25.5×   |

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