# UNDF: UNDF-2026-000000721
# UNDF: (pending)
# spidermonkey-0005: `GatherAvailableModuleAncestors` — O(M²) execList scan in async-module BFS

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | spidermonkey-0005 |
| Severity | MEDIUM |
| Ecosystem | SpiderMonkey (Firefox JavaScript Engine) |
| File | `js/src/vm/Modules.cpp` |
| Lines | 1898–1954 (`GatherAvailableModuleAncestors`), 1917–1918 (`ContainsElement(execList, m)`) |
| Complexity | O(M × P) where M = modules in execList, P = async-parent pointer count |
| Hot path | Called on every top-level async module completion (async `import()`, ES modules with `await`) |

## Defect

`GatherAvailableModuleAncestors` implements ECMAScript §16.2.1.5.2.3
(GatherAvailableAncestors). It walks `asyncParentModules` links recursively,
accumulating modules into `execList` — a `GCVector<ModuleObject*, 0>` (plain
growable array). Before appending each module `m`, it calls
`ContainsElement(execList, m)` to avoid duplicates:

```cpp
// js/src/vm/Modules.cpp
static bool ContainsElement(Handle<ModuleVector> stack, ModuleObject* module) {
    for (ModuleObject* m : stack) {   // O(M) linear scan — CWE-407
        if (m == module) return true;
    }
    return false;
}

static bool GatherAvailableModuleAncestors(
    JSContext* cx, Handle<ModuleObject*> module,
    MutableHandle<ModuleVector> execList) {

    Rooted<ListObject*> asyncParentModules(cx, module->asyncParentModules());
    for (uint32_t i = 0; i != asyncParentModules->length(); i++) {
        m = ...asyncParentModules->getDenseElement(i)...;

        if (!m->hadEvaluationError() && ... &&
            !ContainsElement(execList, m)) {  // O(|execList|) scan — CWE-407
            ...
            if (!execList.append(m)) { ... }          // execList grows
            if (!m->hasTopLevelAwait() &&
                !GatherAvailableModuleAncestors(cx, m, execList)) { ... }  // recurse
        }
    }
}
```

The same `execList` vector is passed by mutable reference through all recursive
calls. Each recursive invocation calls `ContainsElement(execList, m)` for every
async parent, where `execList` grows monotonically. With M async modules and P
total `asyncParentModules` edges:

- Each `ContainsElement` call: O(|execList|) = O(M) in the worst case
- Total `ContainsElement` calls: O(P) (one per parent edge visited)
- **Total cost: O(M × P)**

In a large bundled application with N async ES modules in a single execution
cycle, P ≈ N and M ≈ N (every module appears in execList), giving **O(N²)**.

`GatherAvailableModuleAncestors` is called from `AsyncModuleExecutionFulfilled`
(line 2008) — the callback that fires when an `await`-using top-level module
resolves. With N async modules simultaneously resolving (e.g., parallel
`import()` calls for a large app), this function runs O(N²) total.

## Reproduction

Large web applications that use many async ES modules in parallel:
- Bundled SPA apps with 100–500 async ES modules using top-level `await`
- Server-side module loading (e.g., Node.js with SpiderMonkey embedding)
- Module graphs with diamond re-export patterns

At M=500 modules: 500 × 500 = 250,000 pointer comparisons for execList
deduplication, vs. 500 hash lookups with a set-based approach.

## Fix

Add a shadow `HashSet<ModuleObject*>` to `GatherAvailableModuleAncestors` for
O(1) membership testing. Since the same `execList` is shared across all
recursive calls, the set must also be passed through recursion:

```cpp
// CWE-407 fix: add execSet shadow for O(1) dedup of execList
static bool GatherAvailableModuleAncestors(
    JSContext* cx, Handle<ModuleObject*> module,
    MutableHandle<ModuleVector> execList,
    js::HashSet<ModuleObject*>& execSet) {  // <-- shadow set

    Rooted<ListObject*> asyncParentModules(cx, module->asyncParentModules());
    Rooted<ModuleObject*> m(cx);
    for (uint32_t i = 0; i != asyncParentModules->length(); i++) {
        m = &asyncParentModules->getDenseElement(i).toObject().as<ModuleObject>();

        if (!m->hadEvaluationError() && !m->getCycleRoot()->hadEvaluationError() &&
            !execSet.has(m)) {             // O(1) hash lookup — fixed
            // ... assertions ...
            m->setPendingAsyncDependencies(m->pendingAsyncDependencies() - 1);
            if (m->pendingAsyncDependencies() == 0) {
                if (!execList.append(m)) return false;
                if (!execSet.put(m)) return false;  // O(1) insert
                if (!m->hasTopLevelAwait() &&
                    !GatherAvailableModuleAncestors(cx, m, execList, execSet)) {
                    return false;
                }
            }
        }
    }
    return true;
}

// Call site (AsyncModuleExecutionFulfilled):
Rooted<ModuleVector> execList(cx);
js::HashSet<ModuleObject*> execSet(cx);  // shadow set
if (!GatherAvailableModuleAncestors(cx, module, &execList, execSet)) { ... }
```

`js::HashSet` is SpiderMonkey's arena-allocated hash set, already used
throughout `Modules.cpp` (e.g., the `exportStarSet` parameter in
`ModuleGetExportedNames`).

## Speedup

| Async modules (M) | Before (comparisons) | After (comparisons) | Ratio |
|-------------------|---------------------|--------------------|----|
| M=50, P=50        | 2,500               | 50                 | 50× |
| M=200, P=200      | 40,000              | 200                | 200× |
| M=500, P=500      | 250,000             | 500                | 500× |

## Notes

The `ContainsElement(stack, module)` overload for the `stack` parameter
(module-linking DFS at lines 1464, 1767) follows the same pattern but is
bounded by the DFS depth (typically small). The `execList` path is the
hot one for large async module graphs.
