# UNDF: UNDF-2026-000000596
# UNDF: (pending)
# jackson-0001: AnnotatedClassResolver._addSuperTypes/Interfaces — O(N²) custom _contains() list scan in type hierarchy collection

## CWE-407 — Algorithmic Complexity: O(N) custom list scan per type in recursive supertype/interface collection

| Field        | Value |
|--------------|-------|
| ID           | jackson-0001 |
| Severity     | MEDIUM |
| Ecosystem    | jackson-databind |
| Package      | com.fasterxml.jackson.databind |
| File         | `src/main/java/tools/jackson/databind/introspect/AnnotatedClassResolver.java` |
| Lines        | 164–216 |
| Complexity   | O(N) per type; O(N²) to collect N-type hierarchy |
| Hot path     | Called during Jackson class binding — once per deserialized/serialized class |

## Defect

`AnnotatedClassResolver._addSuperTypes` and `_addSuperInterfaces` collect the full type hierarchy into a
`List<JavaType> result`. To avoid duplicates they call a custom `_contains(result, cls)` that performs an
O(N) linear scan using reference equality on each element's raw class:

```java
// AnnotatedClassResolver.java:164-216 (DEFECT)
private static void _addSuperTypes(JavaType type, List<JavaType> result, boolean addClassItself) {
    // ...
    if (addClassItself) {
        if (_contains(result, cls)) {        // O(N) linear scan
            return;
        }
        result.add(type);
    }
    for (JavaType intCls : type.getInterfaces()) {
        _addSuperInterfaces(intCls, result, true);   // recurses
    }
    _addSuperTypes(type.getSuperClass(), result, true);   // recurses
}

private static void _addSuperInterfaces(JavaType type, List<JavaType> result, boolean addClassItself) {
    // ...
    if (addClassItself) {
        if (_contains(result, cls)) {        // O(N) linear scan
            return;
        }
        result.add(type);
        // ...
    }
    for (JavaType intCls : type.getInterfaces()) {
        _addSuperInterfaces(intCls, result, true);   // recurses
    }
}

private static boolean _contains(List<JavaType> found, Class<?> raw) {
    for (int i = 0, end = found.size(); i < end; ++i) {
        if (found.get(i).getRawClass() == raw) {   // O(N) scan
            return true;
        }
    }
    return false;
}
```

For a type hierarchy with N supertypes/interfaces, `_contains` is called N times against a growing list,
giving O(N²) total scan operations. Diamond hierarchies (interface A extends B and C; both extend D)
are deduped correctly, but the dedup cost is O(N) per check.

## Fix

Add a parallel `Set<Class<?>>` for O(1) membership testing alongside the result list (which must be
kept for ordered output):

```java
// AFTER — O(N) total for N-type hierarchy
// Entry point: allocate seen set
private static List<JavaType> collectSuperTypes(JavaType type) {
    List<JavaType> result = new ArrayList<>();
    Set<Class<?>> seen = new HashSet<>();   // ADD: O(1) membership guard
    _addSuperTypes(type, result, seen, false);
    return result;
}

private static void _addSuperTypes(JavaType type, List<JavaType> result, Set<Class<?>> seen,
        boolean addClassItself)
{
    if (type == null) { return; }
    final Class<?> cls = type.getRawClass();
    if ((cls == CLS_OBJECT) || (cls == CLS_ENUM)) { return; }
    if (addClassItself) {
        if (!seen.add(cls)) {   // O(1): add returns false if already present
            return;
        }
        result.add(type);
    }
    for (JavaType intCls : type.getInterfaces()) {
        _addSuperInterfaces(intCls, result, seen, true);
    }
    _addSuperTypes(type.getSuperClass(), result, seen, true);
}
// _contains() helper no longer needed
```

## 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).
