# UNDF: UNDF-2026-000000237
# cxf-0001: parseImports ArrayList.contains visited-guard O(N²) — two sites

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Component**: Apache CXF — `rt/wsdl`
- **Files**:
  - `rt/wsdl/src/main/java/org/apache/cxf/wsdl11/SchemaUtil.java`
  - `rt/wsdl/src/main/java/org/apache/cxf/wsdl11/WSDLServiceBuilder.java`
- **Methods**: `parseImports(Definition, List<Definition>)` (both files)

## Description

Both `SchemaUtil` and `WSDLServiceBuilder` contain an identical `parseImports` helper that
traverses the WSDL import graph recursively. The cycle guard uses `ArrayList.contains()`, which
is O(N) per check. For a graph of N total imported WSDL definitions the total guard cost is
O(N²) — one linear scan per edge traversal.

Additionally, `WSDLServiceBuilder.buildService` (line 305) uses a separate `ArrayList done`
for a second traversal of the same import graph, again with `done.contains()` as the guard.

## Defect Code

### SchemaUtil.java — lines 159-172

```java
private void parseImports(Definition def, List<Definition> defList) {
    List<Import> importList = new ArrayList<>();

    Collection<List<Import>> ilist = cast(def.getImports().values());
    for (List<Import> list : ilist) {
        importList.addAll(list);
    }
    for (Import impt : importList) {
        if (!defList.contains(impt.getDefinition())) {  // O(N) ArrayList.contains
            defList.add(impt.getDefinition());
            parseImports(impt.getDefinition(), defList);
        }
    }
}
```

### WSDLServiceBuilder.java — lines 393-406 (identical pattern)

```java
private void parseImports(Definition def, List<Definition> defList) {
    List<Import> importList = new ArrayList<>();

    Collection<List<Import>> ilist = cast(def.getImports().values());
    for (List<Import> list : ilist) {
        importList.addAll(list);
    }
    for (Import impt : importList) {
        if (!defList.contains(impt.getDefinition())) {  // O(N) ArrayList.contains
            defList.add(impt.getDefinition());
            parseImports(impt.getDefinition(), defList);
        }
    }
}
```

## Impact

WSDL imports form a DAG. An enterprise WSDL with N=100 shared definition imports incurs
~10,000 identity comparisons instead of ~100 hash lookups. This occurs at service startup
and WSDL parsing time. The fix is a one-line change in each file.

## Complexity

| N (WSDL definitions) | ArrayList.contains cost | HashSet cost | Overhead ratio |
|---|---|---|---|
| 10 | ~55 | ~10 | 5.5x |
| 50 | ~1275 | ~50 | 25.5x |
| 100 | ~5050 | ~100 | 50.5x |
| 500 | ~125250 | ~500 | 250.5x |

## Fix

Change the accumulator parameter from `List<Definition>` to `Set<Definition>` (using
`LinkedHashSet` to preserve insertion order for the subsequent iteration):

```java
// SchemaUtil.java — caller at line 73
List<Definition> defList = new ArrayList<>();
parseImports(def, defList);
// → change to:
Set<Definition> defList = new LinkedHashSet<>();
parseImports(def, defList);

// parseImports body — no change needed; Set.contains() and Set.add() are already O(1)
// change parameter type from List<Definition> to Set<Definition>
```

Same change in `WSDLServiceBuilder.java` lines 393-406 and its caller at line 214.

For the `buildService` traversal at line 300-313, `done` is already declared as
`Set<Definition> done = new HashSet<>()` — that path is CLEAN. Only `parseImports` is affected.

## Evidence

- `SchemaUtil.java:167`: `if (!defList.contains(impt.getDefinition()))` — `defList` is `ArrayList`
- `SchemaUtil.java:72`: caller allocates `new ArrayList<>()` and passes as `List<Definition>`
- `WSDLServiceBuilder.java:401`: same pattern
- `WSDLServiceBuilder.java:214`: caller allocates `new ArrayList<>()`
- `WSDLServiceBuilder.java:300`: `Set<Definition> done = new HashSet<>()` — CLEAN (different traversal)
