# UNDF: UNDF-2026-000000538
# SM-0004: Modules.cpp ContainsElement(exportedNames) O(N) linear scan in GetExportedNames

**File:** `js/src/vm/Modules.cpp`
**Lines:** 510–518 (`ContainsElement` for ExportNameVector), 631 (call site in inner loop)
**Severity:** MEDIUM
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)

## Description

`ModuleGetExportedNames` implements the ECMAScript `GetExportedNames` abstract
operation (ES2023 §16.2.1.6.2).  When resolving `export *` entries it
accumulates all exported names from re-exported modules into `exportedNames`,
a `GCVector<JSAtom*, 0, SystemAllocPolicy>` (i.e. a plain growable array):

```cpp
static bool ContainsElement(const ExportNameVector& list, JSAtom* atom) {
  for (JSAtom* a : list) {    // O(N) linear scan — CWE-407
    if (a == atom) return true;
  }
  return false;
}

// Inside ModuleGetExportedNames():
for (const ExportEntry& e : module->starExportEntries()) {          // outer: E modules
  ...
  Rooted<ExportNameVector> starNames(cx);
  if (!ModuleGetExportedNames(cx, requestedModule, exportStarSet, &starNames)) ...

  for (JSAtom* name : starNames) {                                  // inner: S names
    if (name != cx->names().default_) {
      if (!ContainsElement(exportedNames, name)) {  // O(N) scan over growing list
        if (!exportedNames.append(name)) ...
      }
    }
  }
}
```

With E star-export modules each re-exporting S names, and the `exportedNames`
list growing toward E×S items, the dedup cost is:

```
O(E × S × (E×S)) = O(E² × S²)
```

In real-world module bundles (e.g. barrel files re-exporting many libraries),
E=10, S=100 gives 1 000 000 pointer comparisons per `GetExportedNames` call,
versus O(E×S) = 1 000 with a HashSet.

A secondary linear-scan defect exists in `GatherAvailableModuleAncestors`:

```cpp
// line ~1918
if (!ContainsElement(execList, m)) {    // O(L) per async parent module check
  execList.append(m);
  GatherAvailableModuleAncestors(cx, m, execList);   // recursive
}
```

`execList` is a `ModuleVector` (linear array).  With L modules in execList and
P async parent modules per call, and the recursion propagating the same list,
the total cost is O(L×P) per invocation vs. O(P) with a HashSet guard.

## Fix

Introduce a `HashSet<JSAtom*>` shadow set for the dedup check in
`ModuleGetExportedNames`:

```cpp
// In ModuleGetExportedNames, replace ContainsElement(exportedNames, name) with:
//   exportedNameSet.has(name)
// and add exportedNameSet.put(name) on append.

using ExportNameSet =
    GCHashSet<JSAtom*, DefaultHasher<JSAtom*>, SystemAllocPolicy>;

static bool ModuleGetExportedNames(
    JSContext* cx, Handle<ModuleObject*> module,
    MutableHandle<ModuleSet> exportStarSet,
    MutableHandle<ExportNameVector> exportedNames) {
  ...
  Rooted<ExportNameSet> exportedNameSet(cx);   // FIX: O(1) dedup guard

  // seed from already-known local/indirect exports:
  for (const ExportEntry& e : module->localExportEntries()) {
    if (!exportedNames.append(e.exportName())) return false;
    if (!exportedNameSet.put(e.exportName())) return false;
  }
  ...
  for (JSAtom* name : starNames) {
    if (name != cx->names().default_) {
      if (!exportedNameSet.has(name)) {        // O(1) — fixed
        if (!exportedNames.append(name)) return false;
        if (!exportedNameSet.put(name))  return false;
      }
    }
  }
  ...
}
```

For `GatherAvailableModuleAncestors`, pass a `HashSet<ModuleObject*>` alongside
`execList` or switch `execList` itself to a type that supports O(1) membership.

## Complexity

| Path | Before | After |
|------|--------|-------|
| `ContainsElement(exportedNames, name)` | O(N) | O(1) |
| Total for E=10, S=100 | ~1 000 000 ops | ~1 000 ops |
| `GatherAvailableModuleAncestors` check | O(L) | O(1) |

**Speedup:** ~1 000× at E=10, S=100 (barrel-file scenario)

## References

- `ExportNameVector` typedef: `js/src/vm/ModuleObject.h`
- `ModuleSet` is already a `GCHashSet` — same pattern can be applied to exportedNames
- SM-0003: same file's `SimpleSet` pattern