# UNDF: UNDF-2026-000000600
# UNDF: (pending)
# graal-0002: ClassfileConstant.resolveMethod/resolveField — O(2^D) diamond re-traversal without visited set

## CWE-407 — Algorithmic Complexity: O(2^D) recursive interface re-traversal in classfile method/field resolution

| Field        | Value |
|--------------|-------|
| ID           | graal-0002 |
| Severity     | MEDIUM |
| Ecosystem    | graal |
| Package      | jdk.graal.compiler |
| File         | `compiler/src/jdk.graal.compiler/src/jdk/graal/compiler/replacements/classfile/ClassfileConstant.java` |
| Lines        | 281–319 |
| Complexity   | O(2^D) on interface diamond hierarchies |
| Hot path     | Called during classfile-based bytecode provider method/field resolution for Graal substitutions |

## Defect

`ClassfileConstant.resolveMethod` and `resolveField` recursively traverse the type hierarchy to find
a matching method/field. They have NO visited set — on a diamond interface hierarchy, shared ancestor
interfaces are traversed exponentially:

```java
// ClassfileConstant.java:281-299 (DEFECT)
static ResolvedJavaMethod resolveMethod(ClassfileBytecodeProvider context, ResolvedJavaType c,
        String name, String descriptor, boolean isStatic) {
    ResolvedJavaMethod method = context.findMethod(c, name, descriptor, isStatic);
    if (method != null) { return method; }

    if (!c.isJavaLangObject() && !c.isInterface()) {
        method = resolveMethod(context, c.getSuperclass(), name, descriptor, isStatic);
        if (method != null) { return method; }
    }
    for (ResolvedJavaType i : c.getInterfaces()) {
        method = resolveMethod(context, i, name, descriptor, isStatic);  // DEFECT: no visited guard
        if (method != null) { return method; }
    }
    return null;
}

// ClassfileConstant.java:301-319 — identical pattern for fields (DEFECT)
static ResolvedJavaField resolveField(ClassfileBytecodeProvider context, ResolvedJavaType c,
        String name, String fieldType, boolean isStatic) {
    // ... same structure, no visited set
}
```

For a diamond (class C implements I1 and I2; both I1 and I2 extend I_base):
- `resolveMethod(C)` → `resolveMethod(I1)` → `resolveMethod(I_base)` → not found
- Back in C: → `resolveMethod(I2)` → `resolveMethod(I_base)` → traversed AGAIN

At diamond depth D, `I_base` is visited 2^D times when the method is not found.

## Fix

Add a `Set<ResolvedJavaType> visited` parameter with a public entry-point wrapper:

```java
// AFTER — O(N+E) where N=types, E=hierarchy edges
static ResolvedJavaMethod resolveMethod(ClassfileBytecodeProvider context, ResolvedJavaType c,
        String name, String descriptor, boolean isStatic) {
    return resolveMethod(context, c, name, descriptor, isStatic, new HashSet<>());
}

private static ResolvedJavaMethod resolveMethod(ClassfileBytecodeProvider context, ResolvedJavaType c,
        String name, String descriptor, boolean isStatic, Set<ResolvedJavaType> visited) {
    if (!visited.add(c)) { return null; }              // skip already-visited types
    ResolvedJavaMethod method = context.findMethod(c, name, descriptor, isStatic);
    if (method != null) { return method; }
    if (!c.isJavaLangObject() && !c.isInterface()) {
        method = resolveMethod(context, c.getSuperclass(), name, descriptor, isStatic, visited);
        if (method != null) { return method; }
    }
    for (ResolvedJavaType i : c.getInterfaces()) {
        method = resolveMethod(context, i, name, descriptor, isStatic, visited);
        if (method != null) { return method; }
    }
    return null;
}
// Same fix applies to resolveField
```

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