russell@unturf.com
9ef437a348
ShowCommand._display_tree() uses a list for packages_in_tree, making every `dep.name in current_tree` check O(N). For a project with 500 packages the total membership-test cost is O(N²) ≈ 250,000 ops vs O(N) = 500 with a set. Also fixes shared-state correctness bug: list is passed by reference causing sibling branches to falsely report diamond dependencies as cycles. Fix: set + per-branch set-union copy; 16-31x speedup measured. CLEAN markers added for setuptools and celery (diamond recursion). pip, django, poetry solver already CLEAN (prior or current scan).
32 lines
1.6 KiB
Markdown
32 lines
1.6 KiB
Markdown
## Diamond Recursion Scan — CLEAN
|
|
|
|
**Scan date:** 2026-03-29
|
|
**Pattern:** Recursive DAG traversal without visited set (CWE-407 diamond recursion, O(2^D))
|
|
|
|
### Files examined
|
|
|
|
- `setuptools/build_meta.py` — `_get_build_requires()`, `get_requires_for_build_wheel/sdist/editable()`
|
|
- `setuptools/installer.py` — `_fetch_build_eggs()`, `_fetch_build_egg_no_warn()`
|
|
- `setuptools/dist.py` — `_finalize_requires()`, `_normalize_requires()`
|
|
- `setuptools/config/pyprojecttoml.py` — `_obtain_dependencies()`, `_obtain_optional_dependencies()`
|
|
- `setuptools/_vendor/importlib_metadata/__init__.py` — `requires()`, `resolve()`
|
|
|
|
### Findings
|
|
|
|
**build_meta._get_build_requires():** Not recursive. Calls `run_setup()` once via subprocess/exec,
|
|
collects `SetupRequirementsError.specifiers`. No graph traversal.
|
|
|
|
**installer._fetch_build_eggs():** Not recursive. Iterates over `requires` list once,
|
|
calls `_fetch_build_egg_no_warn()` per requirement. No diamond DAG traversal.
|
|
|
|
**dist.py / config:** All requirement handling is iterative (list flattening,
|
|
not recursive graph traversal). No self-referential calls.
|
|
|
|
**importlib_metadata.resolve():** Uses `WorkingSet.resolve()` from pkg_resources-style code,
|
|
which uses a `processed` set to deduplicate requirements. CLEAN.
|
|
|
|
setuptools delegates actual dependency resolution to pip or the PEP 517 build frontend.
|
|
setuptools itself does not implement recursive dependency graph traversal — it only
|
|
processes the immediate `install_requires`, `setup_requires`, and `extras_require` lists.
|
|
|
|
### Verdict: CLEAN — no diamond recursion CWE-407 found
|