# UNDF: UNDF-2026-000000315
# UNDF: (pending)
# tomcat-0001: BeanSupportFull.populateFromInterfaces — O(2^D) diamond re-traversal without visited set

## CWE-407 — Algorithmic Complexity: O(2^D) recursive diamond re-traversal in Jakarta EL bean property collection

| Field        | Value |
|--------------|-------|
| ID           | tomcat-0001 |
| Severity     | MEDIUM |
| Ecosystem    | tomcat |
| Package      | jakarta.el |
| File         | `java/jakarta/el/BeanSupportFull.java` |
| Lines        | 57–73 |
| Complexity   | O(2^D) on diamond interface hierarchies |
| Hot path     | Called during EL expression evaluation for first access to a bean type (cached after first use) |

## Defect

`BeanSupportFull.populateFromInterfaces` recursively collects bean property descriptors from a class's
full interface hierarchy. It has NO visited set — it recurses unconditionally into every interface and
every superclass, causing diamond hierarchies to be traversed exponentially:

```java
// BeanSupportFull.java:57-73 (DEFECT)
private void populateFromInterfaces(Class<?> aClass) throws IntrospectionException {
    Class<?>[] interfaces = aClass.getInterfaces();
    for (Class<?> ifs : interfaces) {
        BeanInfo info = Introspector.getBeanInfo(ifs);
        PropertyDescriptor[] pds = info.getPropertyDescriptors();
        for (PropertyDescriptor pd : pds) {
            if (!this.properties.containsKey(pd.getName())) {
                this.properties.put(pd.getName(), new BeanPropertyFull(this.type, pd));
            }
        }
        populateFromInterfaces(ifs);      // DEFECT: unconditional recursion — no visited guard
    }
    Class<?> superclass = aClass.getSuperclass();
    if (superclass != null) {
        populateFromInterfaces(superclass); // DEFECT: unconditional recursion — no visited guard
    }
}
```

On a diamond (I1 and I2 both extend Base; class C implements I1 and I2):
- `populateFromInterfaces(C)`:
  - Recurse into I1: `populateFromInterfaces(I1)` → processes Base, recurses into Base's interfaces
  - Recurse into I2: `populateFromInterfaces(I2)` → processes Base AGAIN, recurses into Base's interfaces AGAIN

The property dedup at line 63 (`properties.containsKey`) prevents duplicate property additions but does
NOT prevent re-traversal — the recursive calls at lines 67 and 71 still happen. Every `Introspector.getBeanInfo(ifs)` and subsequent loop re-executes for already-visited nodes.

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

## Fix

Add a `Set<Class<?>> visited` parameter with a public wrapper:

```java
// AFTER — O(N+E) where N=interfaces, E=hierarchy edges
private void populateFromInterfaces(Class<?> aClass) throws IntrospectionException {
    populateFromInterfaces(aClass, new HashSet<>());
}

private void populateFromInterfaces(Class<?> aClass, Set<Class<?>> visited)
        throws IntrospectionException {
    if (!visited.add(aClass)) { return; }   // skip already-traversed types

    Class<?>[] interfaces = aClass.getInterfaces();
    for (Class<?> ifs : interfaces) {
        BeanInfo info = Introspector.getBeanInfo(ifs);
        PropertyDescriptor[] pds = info.getPropertyDescriptors();
        for (PropertyDescriptor pd : pds) {
            if (!this.properties.containsKey(pd.getName())) {
                this.properties.put(pd.getName(), new BeanPropertyFull(this.type, pd));
            }
        }
        populateFromInterfaces(ifs, visited);
    }
    Class<?> superclass = aClass.getSuperclass();
    if (superclass != null) {
        populateFromInterfaces(superclass, visited);
    }
}
```

## Speedup

| Diamond depth (D) | Before (traversals) | After (traversals) | 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).
