java-topology/defects/spidermonkey/patch/sm-0004-modules-exportnames-hashset.md

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):

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:

// 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:

// 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