# UNDF: UNDF-2026-000000271
# UNDF: (pending)
# scala3-0001: Namer.addWildcardForwarders — O(M×S) List[TermName] seen-scan for Given export forwarders

## CWE-407 — Algorithmic Complexity: Inefficient Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | scala3-0001 |
| Severity | MEDIUM |
| Ecosystem | scala3 |
| Package | dotty.tools.dotc.typer |
| File | `compiler/src/dotty/tools/dotc/typer/Namer.scala` |
| Lines | 1418–1448 |
| Complexity | O(M × S) — O(S) list scan per member for Given exports |
| Hot path | `export` clause compilation — executed once per export statement |

## Defect

`Namer.addWildcardForwarders` is called when an `export path.*` wildcard clause is
compiled. It receives `seen: List[TermName]` — the names of explicitly-listed selectors
that precede the wildcard in the same export clause (built by prepending in
`addForwarders`).

For **non-Given** members the code correctly materializes `seen` into a `mutable.HashSet`
at the top of the function (`nonContextual`). But for **Given** members, it falls back to
the raw `List.contains()` O(S) scan on every member:

```scala
def addWildcardForwarders(seen: List[TermName], span: Span): Unit =
  val nonContextual = mutable.HashSet(seen*)          // O(S) one-time copy — OK for non-Given branch
  ...
  for mbr <- pathType.membersBasedOnFlags(...) do
    ...
    val alias = mbr.name.toTermName
    if mbr.symbol.is(Given) then
      if !seen.contains(alias) && mbr.matchesImportBound(givenBound) then   // BUG: O(S) per member
        addForwarder(alias, mbr, span)
    else if !nonContextual.contains(alias) ...                              // OK: O(1)
```

With M members in `pathType` and S explicit selectors in `seen`, the Given branch
performs **O(M × S)** comparisons. The non-Given branch already pays this cost to
construct `nonContextual`, but does it only once (O(S)) then O(1) per lookup.
The Given branch neglects to reuse `nonContextual` and re-scans the original list
per member.

`TermName` is a value type with a stable `hashCode`, making it safe in `HashSet`.

## Fix

Reuse `nonContextual` (which already contains all names from `seen`) for the Given branch
lookup. Both branches then pay O(1) per member:

```scala
def addWildcardForwarders(seen: List[TermName], span: Span): Unit =
  val nonContextual = mutable.HashSet(seen*)          // covers both Given and non-Given
  ...
  for mbr <- pathType.membersBasedOnFlags(...) do
    ...
    val alias = mbr.name.toTermName
    if mbr.symbol.is(Given) then
      if !nonContextual.contains(alias) && mbr.matchesImportBound(givenBound) then   // FIX: O(1)
        addForwarder(alias, mbr, span)
    else if !nonContextual.contains(alias) && mbr.matchesImportBound(wildcardBound) then
      nonContextual += alias
      addWildcardForwardersNamed(alias, span)
```

The semantics are identical: `seen` contains the names of all explicit selectors, and
`nonContextual` is initialized to exactly `seen*`, so `nonContextual.contains(alias)` is
equivalent to `seen.contains(alias)` but O(1) instead of O(S).

## Speedup

| M (members) | S (selectors) | Before (Given ops) | After (Given ops) | Speedup |
|-------------|---------------|-------------------|-------------------|---------|
| 50 | 10 | 500 | 50 | 10× |
| 200 | 20 | 4,000 | 200 | 20× |
| 500 | 50 | 25,000 | 500 | 50× |

Typical Scala 3 `export` clauses target trait-rich objects with O(100–500) members
and O(5–30) explicit selectors. The pathological case is a large typeclass object
with many given instances and a long list of explicit `export` selectors.

## Affected Versions

Scala 3.x (dotty) — `addWildcardForwarders` present since `export` was introduced
in Scala 3.0; affects all versions through current main branch.

## References

- Scala 3 issue tracker (none filed)
- Upstream source: `compiler/src/dotty/tools/dotc/typer/Namer.scala`
- CWE-407: https://cwe.mitre.org/data/definitions/407.html
