# UNDF: UNDF-2026-000000613
# UNDF: (pending)
# solang-0001: add_external_functions emits_events Vec::contains O(F×E²) → O(F×E)

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | solang-0001 |
| Severity | MEDIUM |
| Ecosystem | Solidity compiler (Solang) |
| Package | sema |
| File | `src/sema/external_functions.rs` |
| Lines | 93–103 |
| Complexity | O(F×E²) → O(F×E) with HashSet |
| Hot path | Per contract compilation — called once per contract in `add_external_functions` |

## Defect

```rust
// BEFORE (DEFECT) — Vec::contains is O(E) scan, called E times per function × F functions
let mut emits_events = Vec::new();

for function_no in ns.contracts[contract_no].all_functions.keys() {
    let func = &ns.functions[*function_no];

    for event_no in &func.emits_events {
        if !emits_events.contains(event_no) {   // O(E) linear scan per event
            emits_events.push(*event_no);
        }
    }
}
```

The accumulator `emits_events` is a `Vec<usize>`. For each of F functions, for each of E
events the function emits, `Vec::contains` performs a linear scan of the accumulator
(already up to E entries). Total cost: O(F × E²).

For a contract with F=50 functions and each emitting E=20 events, the inner dedup
scans up to 1000 elements per event check — 50 × 20 × 20 = 20,000 comparisons instead
of 1,000.

## Fix

```rust
// AFTER — IndexSet (insertion-ordered HashSet) dedup in O(1), preserving order
use indexmap::IndexSet;

let mut emits_events_set: IndexSet<usize> = IndexSet::new();

for function_no in ns.contracts[contract_no].all_functions.keys() {
    let func = &ns.functions[*function_no];

    for event_no in &func.emits_events {
        emits_events_set.insert(*event_no);   // O(1) amortized
    }
}

ns.contracts[contract_no].emits_events = emits_events_set.into_iter().collect();
```

`IndexSet` is already used in this file (`CallList.solidity` on line 10), so no new
dependency is required.

Alternatively, a plain `HashSet` followed by a `Vec` collect works if order does not
matter (the original Vec ordering is not documented as significant):

```rust
use std::collections::HashSet;

let mut seen: HashSet<usize> = HashSet::new();
let mut emits_events = Vec::new();

for function_no in ns.contracts[contract_no].all_functions.keys() {
    let func = &ns.functions[*function_no];
    for event_no in &func.emits_events {
        if seen.insert(*event_no) {
            emits_events.push(*event_no);
        }
    }
}
```

## Speedup

| F (functions) | E (events/fn) | Before (ops) | After (ops) | Speedup |
|---------------|---------------|-------------|-------------|---------|
| 10 | 5 | 250 | 50 | 5× |
| 50 | 20 | 20,000 | 1,000 | 20× |
| 200 | 50 | 500,000 | 10,000 | 50× |
| 500 | 100 | 5,000,000 | 50,000 | 100× |

A contract with 500 functions (possible in generated Solidity or large proxy contracts)
and 100 event types accumulates 5 million membership comparisons vs 50,000 with the fix.

## Notes

`IndexSet` is already a dependency of the `solang` crate (imported on line 5 of this
file as `use indexmap::IndexSet`), making this a zero-dependency fix. The same
`IndexSet` pattern is already used on line 10 for `CallList.solidity`.
