# UNDF: UNDF-2026-000000545
# swift-0001: QualifiedLookupRequest — O(2^D) diamond re-traversal via unguarded protocol superclass push

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

| Field | Value |
|-------|-------|
| ID | swift-0001 |
| Severity | MEDIUM |
| Ecosystem | swift |
| Package | lib/AST |
| File | `lib/AST/NameLookup.cpp` |
| Lines | 2858–2861 |
| Complexity | O(2^D) on diamond protocol+class hierarchies |
| Hot path | qualified name lookup (every member access, every type check) |

## Defect

`QualifiedLookupRequest::evaluate` (NameLookup.cpp) walks a nominal type's
inheritance graph via a BFS worklist. When the current node is a
`ProtocolDecl` that has a class superclass, lines 2858–2861 push that
superclass onto the stack **without checking** whether it was already
visited:

```cpp
// lib/AST/NameLookup.cpp lines 2858–2861 (DEFECT)
if (auto superclassDecl = protoDecl->getSuperclassDecl()) {
    visited.insert(superclassDecl);   // .second NOT checked
    stack.push_back(superclassDecl);  // unconditional push → O(2^D)
}
```

The identical operation 27 lines earlier (line 2833–2834, for the
`ClassDecl` arm) is written correctly:

```cpp
// line 2833–2834 (CORRECT — nearby, same function)
if (visited.insert(superclassDecl).second)
    stack.push_back(superclassDecl);
```

### Diamond scenario

Consider a protocol diamond where two protocols both have the same class
superclass `Base`:

```
protocol PA: Base {}   // PA.getSuperclassDecl() == Base
protocol PB: Base {}   // PB.getSuperclassDecl() == Base
protocol P: PA, PB {}  // inherits both
```

When looking up a member on `P`:

1. BFS pops `P` → enqueues `PA`, `PB` via `addNominalType` (correctly guarded).
2. BFS pops `PA` → `protoDecl->getSuperclassDecl()` returns `Base`.
   `visited.insert(Base)` succeeds, `Base` pushed. **stack = [PB, Base]**
3. BFS pops `Base` → processed normally.
4. BFS pops `PB` → `protoDecl->getSuperclassDecl()` returns `Base` again.
   `visited.insert(Base)` silently returns `{iter, false}` (already present)
   but the return value is **ignored** → `Base` pushed again.
   **stack = [Base]** — `Base` re-processed.

For a depth-D diamond this re-visits `Base` 2^D times.

Hot path: `QualifiedLookupRequest` is evaluated on every qualified member
expression (`.foo`, `.bar`), every protocol conformance check, and every
type-checker constraint solve. In large codebases with deep protocol
hierarchies this fires frequently per compilation.

## Fix

```cpp
// lib/AST/NameLookup.cpp lines 2858–2861 (AFTER — O(D))
if (auto superclassDecl = protoDecl->getSuperclassDecl()) {
    if (visited.insert(superclassDecl).second)   // guard: only if newly inserted
        stack.push_back(superclassDecl);
}
```

One-line change matching the existing correct pattern on line 2833.

## Speedup

| Diamond depth (D) | Shared superclass visits (before) | After | Speedup |
|------------------|-----------------------------------|-------|---------|
| 2 | 2 | 1 | 2× |
| 5 | 16 | 1 | 16× |
| 10 | 512 | 1 | 512× |
| 15 | 16,384 | 1 | 16,384× |

(Speedup is specifically for the superclass re-traversal component; total
lookup speedup depends on hierarchy breadth.)

## Context

```cpp
// Full function context: lib/AST/NameLookup.cpp
QualifiedLookupResult
QualifiedLookupRequest::evaluate(Evaluator &eval, const DeclContext *DC,
                                 SmallVector<NominalTypeDecl *, 4> typeDecls,
                                 DeclNameRef member, NLOptions options) const {
  SmallVector<NominalTypeDecl *, 4> stack;
  llvm::SmallPtrSet<NominalTypeDecl *, 4> visited;    // line 2753

  auto addNominalType = [&](NominalTypeDecl *nominal) {
    if (!visited.insert(nominal).second)               // CORRECT guard
      return false;
    stack.push_back(nominal);
    return true;
  };
  ...
  while (!stack.empty()) {
    auto current = stack.back();
    stack.pop_back();
    ...
    if (auto classDecl = dyn_cast<ClassDecl>(current)) {
      if (visitSuperclass) {
        if (auto superclassDecl = classDecl->getSuperclassDecl())
          if (visited.insert(superclassDecl).second)   // line 2833: CORRECT
            stack.push_back(superclassDecl);
      }
    }
    ...
    if (auto *protoDecl = dyn_cast<ProtocolDecl>(current)) {
      if (!sawClassDecl) {
        if (auto superclassDecl = protoDecl->getSuperclassDecl()) {
          visited.insert(superclassDecl);              // line 2860: DEFECT — .second not checked
          stack.push_back(superclassDecl);             // line 2861: unconditional push
        }
      }
    }
  }
}
```
