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

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

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

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.

3.2 KiB Raw Permalink Blame History Unescape Escape