java-topology/defects/bun/patch/bun-0001-bin-folders-dedup-set.md

UNDF: UNDF-2026-000000359

bun-0001 — CWE-407 in dirInfoUncached bin_folders dedup

Severity: MEDIUM File: src/resolver/resolver.zig Symbol: dirInfoUncached — for (bin_folders.constSlice()) |existing_folder|

Defect

During module resolution, dirInfoCachedMaybeLog walks the directory tree from the target path up to the filesystem root, calling dirInfoUncached for each uncached directory level (up to D levels).

Inside dirInfoUncached, when a .bin directory is found under node_modules, the path is deduplicated against a shared bin_folders array using a linear scan before appending:

// Called inside while (queue_slice.len > 0) loop — D iterations
fn dirInfoUncached(...) {
    // ...
    for (bin_folders.constSlice()) |existing_folder| {  // O(B) scan
        if (strings.eql(existing_folder, bin_path)) {
            break :append_bin_dir;
        }
    }
    bin_folders.append(...);  // B grows up to D
}

bin_folders is a shared array that accumulates all .bin folder paths found across the entire directory tree traversal. Each call to dirInfoUncached performs an O(B) scan where B grows with each new .bin directory found. With D directory levels each contributing one .bin entry, total dedup cost is O(D²).

In a monorepo with deep nesting (D=50 directories, each with node_modules/.bin), this generates ~1,250 comparisons per require() call instead of ~50.

Fix

Replace bin_folders linear scan with a std.StringHashMap or std.BufSet for O(1) membership:

var bin_folders_set = std.StringHashMap(void).init(allocator);
defer bin_folders_set.deinit();

// In the dedup check:
const gop = try bin_folders_set.getOrPut(bin_path);
if (!gop.found_existing) {
    bin_folders.append(stored_path) catch {};
}

Complexity

Scenario	Before	After
D=50 nested node_modules dirs	O(D²) = ~1,250 ops	O(D) = 50 ops
D=200 deep monorepo	O(D²) = ~20,000 ops	O(D) = 200 ops
Ratio at D=200	~100× overhead	1×

Source location

src/resolver/resolver.zig — fn dirInfoUncached, in the if (r.care_about_bin_folder) / append_bin_dir blocks (~lines 4024–4073), called from within the while (queue_slice.len > 0) loop in dirInfoCachedMaybeLog (~line 2956).