diff options
author | lassulus <github@lassul.us> | 2024-05-12 22:07:45 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-05-12 22:07:45 +0200 |
commit | 3501d3565eab09961dfa2376cffa26d997090764 (patch) | |
tree | caedc615ac9038abd39eeb5cf91ce9f9ef0f6cf8 /pkgs | |
parent | 474925d022a71d3fca76e238cf2b5a14a88010f0 (diff) | |
parent | f9de72f24776538e7e2243f54ab46f3e3a921ab5 (diff) |
Merge pull request #311122 from phaer/catch-conflicts-exponential
pythonCatchConflictsHook: prevent exponential worst-case
Diffstat (limited to 'pkgs')
-rw-r--r-- | pkgs/development/interpreters/python/catch_conflicts/catch_conflicts.py | 31 | ||||
-rw-r--r-- | pkgs/development/interpreters/python/hooks/python-catch-conflicts-hook-tests.nix | 42 |
2 files changed, 58 insertions, 15 deletions
diff --git a/pkgs/development/interpreters/python/catch_conflicts/catch_conflicts.py b/pkgs/development/interpreters/python/catch_conflicts/catch_conflicts.py index ad679d9f9f99e..4713cfb7026e5 100644 --- a/pkgs/development/interpreters/python/catch_conflicts/catch_conflicts.py +++ b/pkgs/development/interpreters/python/catch_conflicts/catch_conflicts.py @@ -3,9 +3,10 @@ from pathlib import Path import collections import sys import os -from typing import Dict, List, Tuple +from typing import Dict, List, Set, Tuple do_abort: bool = False -packages: Dict[str, Dict[str, List[Dict[str, List[str]]]]] = collections.defaultdict(list) +packages: Dict[str, Dict[str, Dict[str, List[str]]]] = collections.defaultdict(dict) +found_paths: Set[Path] = set() out_path: Path = Path(os.getenv("out")) version: Tuple[int, int] = sys.version_info site_packages_path: str = f'lib/python{version[0]}.{version[1]}/site-packages' @@ -31,14 +32,10 @@ def describe_parents(parents: List[str]) -> str: # inserts an entry into 'packages' def add_entry(name: str, version: str, store_path: str, parents: List[str]) -> None: - if name not in packages: - packages[name] = {} - if store_path not in packages[name]: - packages[name][store_path] = [] - packages[name][store_path].append(dict( + packages[name][store_path] = dict( version=version, parents=parents, - )) + ) # transitively discover python dependencies and store them in 'packages' @@ -46,6 +43,12 @@ def find_packages(store_path: Path, site_packages_path: str, parents: List[str]) site_packages: Path = (store_path / site_packages_path) propagated_build_inputs: Path = (store_path / "nix-support/propagated-build-inputs") + # only visit each path once, to avoid exponential complexity with highly + # connected dependency graphs + if store_path in found_paths: + return + found_paths.add(store_path) + # add the current package to the list if site_packages.exists(): for dist_info in site_packages.glob("*.dist-info"): @@ -55,10 +58,9 @@ def find_packages(store_path: Path, site_packages_path: str, parents: List[str]) # recursively add dependencies if propagated_build_inputs.exists(): with open(propagated_build_inputs, "r") as f: - build_inputs: List[str] = f.read().strip().split(" ") + build_inputs: List[str] = f.read().split() for build_input in build_inputs: - if build_input not in parents: - find_packages(Path(build_input), site_packages_path, parents + [build_input]) + find_packages(Path(build_input), site_packages_path, parents + [build_input]) find_packages(out_path, site_packages_path, [f"this derivation: {out_path}"]) @@ -68,10 +70,9 @@ for name, store_paths in packages.items(): if len(store_paths) > 1: do_abort = True print("Found duplicated packages in closure for dependency '{}': ".format(name)) - for store_path, candidates in store_paths.items(): - for candidate in candidates: - print(f" {name} {candidate['version']} ({store_path})") - print(describe_parents(candidate['parents'])) + for store_path, candidate in store_paths.items(): + print(f" {name} {candidate['version']} ({store_path})") + print(describe_parents(candidate['parents'])) # fail if duplicates were found if do_abort: diff --git a/pkgs/development/interpreters/python/hooks/python-catch-conflicts-hook-tests.nix b/pkgs/development/interpreters/python/hooks/python-catch-conflicts-hook-tests.nix index cba1034e0963d..3890df40cb742 100644 --- a/pkgs/development/interpreters/python/hooks/python-catch-conflicts-hook-tests.nix +++ b/pkgs/development/interpreters/python/hooks/python-catch-conflicts-hook-tests.nix @@ -143,4 +143,46 @@ in { }; in expectFailure toplevel "Found duplicated packages in closure for dependency 'leaf'"; + + /* + Transitive conflict with multiple dependency chains leading to the + conflicting package. + + Test sets up this dependency tree: + + toplevel + ├── dep1 + │ └── leaf + ├── dep2 + │ └── leaf + └── dep3 + └── leaf (customized version -> conflicting) + */ + catches-conflict-multiple-chains = let + # package depending on dependency1, dependency2 and dependency3 + toplevel = generatePythonPackage { + pname = "catches-conflict-multiple-chains"; + propagatedBuildInputs = [ dep1 dep2 dep3 ]; + }; + # dep1 package depending on leaf + dep1 = generatePythonPackage { + pname = "dependency1"; + propagatedBuildInputs = [ leaf ]; + }; + # dep2 package depending on leaf + dep2 = generatePythonPackage { + pname = "dependency2"; + propagatedBuildInputs = [ leaf ]; + }; + # dep3 package depending on conflicting version of leaf + dep3 = generatePythonPackage { + pname = "dependency3"; + propagatedBuildInputs = [ (customize leaf) ]; + }; + # some leaf package + leaf = generatePythonPackage { + pname = "leaf"; + }; + in + expectFailure toplevel "Found duplicated packages in closure for dependency 'leaf'"; } |