# UNDF: UNDF-2026-000000267
# UNDF: (pending)
# hibernate-validator-0003: ClassHierarchyHelper.getImplementedInterfaces — O(2^D) diamond re-traversal

## CWE-407 — Algorithmic Complexity: O(2^D) recursive diamond re-traversal

| Field | Value |
|-------|-------|
| ID | hibernate-validator-0003 |
| Severity | HIGH |
| Ecosystem | hibernate-validator |
| Package | org.hibernate.validator.internal.util.classhierarchy |
| File | `engine/src/main/java/org/hibernate/validator/internal/util/classhierarchy/ClassHierarchyHelper.java` |
| Lines | 114–121 |
| Complexity | O(2^D) on diamond interface hierarchies |
| Hot path | Bean validation constraint discovery — every constrained bean validation call |

## Defect

```java
// DEFECT: Set.add() return value IGNORED, then unconditional recursion
private static <T> void getImplementedInterfaces(
        Class<? super T> clazz, Set<Class<? super T>> classes) {
    for (Class<?> currentInterface : clazz.getInterfaces()) {
        @SuppressWarnings("unchecked")
        Class<? super T> currentInterfaceCasted = (Class<? super T>) currentInterface;
        classes.add(currentInterfaceCasted);                    // return value IGNORED
        getImplementedInterfaces(currentInterfaceCasted, classes); // UNCONDITIONAL → O(2^D)
    }
}
```

`Set.add()` returns `true` if the element was newly inserted, `false` if it
was already present. The return value is discarded, and `getImplementedInterfaces`
is called unconditionally on every interface including already-visited ones.

For a diamond interface hierarchy `A implements B,C; B extends D; C extends D`:
- Processing `B`: adds `D`, recurses into `D` (adds D's interfaces)
- Processing `C`: adds `D` (already there, add returns false — IGNORED), then
  recurses into `D` again → full re-traversal of D's subtree

At diamond depth D, 2^D recursive calls occur.

## Fix

```java
// CORRECT: check Set.add() return value — skip if already visited
private static <T> void getImplementedInterfaces(
        Class<? super T> clazz, Set<Class<? super T>> classes) {
    for (Class<?> currentInterface : clazz.getInterfaces()) {
        @SuppressWarnings("unchecked")
        Class<? super T> currentInterfaceCasted = (Class<? super T>) currentInterface;
        if (classes.add(currentInterfaceCasted)) {              // guard: only recurse if newly added
            getImplementedInterfaces(currentInterfaceCasted, classes);
        }
    }
}
```

## Speedup

| Diamond depth (D) | Before (traversals) | After (traversals) | Speedup |
|------------------|--------------------|--------------------|---------|
| 5 | 31 | 5 | 6× |
| 10 | 1,023 | 10 | 102× |
| 15 | 32,767 | 15 | 2,184× |
| 20 | 1,048,575 | 20 | 52,428× |

## Impact

`getImplementedInterfaces` is called from `getDirectlyImplementedInterfaces`,
which is used during Hibernate Validator constraint metadata discovery. Beans
with deep interface diamond hierarchies (common in layered service architectures
or generic repository patterns) will experience exponential constraint discovery
time. In extreme cases this causes application startup to hang.

Note: `getHierarchy` (lines 65–81) also lacks a proper guard — it uses
`classes.contains(current)` (O(N) List search) and only checks `current` in
the superclass walk, not before recurring into interface subtrees — but this
is a separate O(N²) issue, not a diamond O(2^D) defect.
