# UNDF: UNDF-2026-000000601
# UNDF: (pending)
# hazelcast-0003: ProbeUtils.flatten — O(2^D) diamond re-traversal; result.add() return value ignored before recursion

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

| Field        | Value |
|--------------|-------|
| ID           | hazelcast-0003 |
| Severity     | MEDIUM |
| Ecosystem    | hazelcast |
| Package      | hazelcast |
| File         | `hazelcast/src/main/java/com/hazelcast/internal/metrics/impl/ProbeUtils.java` |
| Lines        | 28–39 |
| Complexity   | O(2^D) on diamond interface hierarchies |
| Hot path     | Called during metrics probe registration (`SourceMetadata`, `ProbeType`) — initialization/startup path |

## Defect

`ProbeUtils.flatten` recursively collects all classes and interfaces in a type's hierarchy into
a `Collection<Class<?>> result` (backed by `LinkedHashSet` at both call sites). Although a Set
is used, the recursion guard is MISSING — `result.add(clazz)` return value at the top of the
method is IGNORED, so the method recurses into superclass AND all interfaces unconditionally even
when `clazz` was already fully traversed:

```java
// ProbeUtils.java:28-39 (DEFECT)
static void flatten(final Class<?> clazz, final Collection<Class<?>> result) {
    result.add(clazz);                            // return value IGNORED

    if (clazz.getSuperclass() != null) {
        flatten(clazz.getSuperclass(), result);   // recurses unconditionally
    }

    for (final Class<?> interfaze : clazz.getInterfaces()) {
        result.add(interfaze);                    // return value IGNORED
        flatten(interfaze, result);               // DEFECT: recurses unconditionally
    }
}
```

On a diamond (I1 and I2 both extend Base; clazz implements I1 and I2):
- `flatten(I1)` adds Base to result; recurses into Base (traverses Base's hierarchy)
- `flatten(I2)` attempts to add Base: `result.add(Base)` returns false (already present) — IGNORED;
  then `flatten(Base, result)` is called AGAIN → re-traverses Base's full hierarchy

At diamond depth D, Base is visited 2^D times.

Callers: `SourceMetadata` (line 50) and `ProbeType` (line 92) both use `LinkedHashSet`.

## Fix

Check `result.add()` return value at the top of the method to short-circuit already-visited nodes:

```java
// AFTER — O(N+E) where N=types, E=hierarchy edges
static void flatten(final Class<?> clazz, final Collection<Class<?>> result) {
    if (!result.add(clazz)) { return; }  // already visited — skip entire subtree

    if (clazz.getSuperclass() != null) {
        flatten(clazz.getSuperclass(), result);
    }

    for (final Class<?> interfaze : clazz.getInterfaces()) {
        flatten(interfaze, result);   // result.add happens at top of recursion
    }
}
```

## Speedup

| Diamond depth (D) | Before (visits) | After (visits) | Speedup |
|------------------|----------------|----------------|---------|
| 5                | 31             | 5              | 6×      |
| 10               | 1,023          | 10             | 102×    |
| 15               | 32,767         | 15             | 2,184×  |

Growth before: O(2^D). Growth after: O(D).
