Merge pull request #311122 from phaer/catch-conflicts-exponential

pythonCatchConflictsHook: prevent exponential worst-case

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'";
 }