java-topology/defects/meson/meson-0001-extra-files-ticket.md

meson-0001 — add_deps: O(n²) list membership check for extra_files deduplication

Severity: MEDIUM File: mesonbuild/build.py Line: 1572 CWE: CWE-407 (Algorithmic Complexity — Quadratic)

Description

BuildTarget.add_deps() iterates over dependencies. For each InternalDependency, it extends self.extra_files while deduplicating using a generator expression with not in:

# mesonbuild/build.py:1572
self.extra_files.extend(f for f in dep.extra_files if f not in self.extra_files)

self.extra_files is a plain list. The not in test is O(len(extra_files)) per element. If there are D dependencies each contributing F extra files, and the total unique set grows to E files, the cost is O(D × F × E) — cubic in the worst case, quadratic when all deps contribute the same files.

extra_files is used by IDE generators (VS, Xcode, Eclipse) to list non-compiled files (headers, docs, assets). Projects with many submodules sharing a common set of headers trigger this.

Fix

Add a shadow set self._extra_files_set: Set[File] = set() in BuildTarget.__init__. In add_deps, replace the list-scan generator with a set-guarded append.

Patch: patch/meson-0001-extra-files-dedup-set.patch Unit test: unit/ExtraFilesAlgorithm.java

Complexity

	Time
Before	O(D × F × E)
After	O(D × F) amortised