Repository: tox-dev/pipdeptree (python)

Issue:
Doesn't detect dependency cycles
I created a dep cycle on test.pypi.org:  jd_circular_a -> jd_circular_b -> jd_circular_c -> jd_circular_a

```
$ pip install -q --index-url=https://test.pypi.org/simple jd_circular_a
$ pip freeze
jd_circular_a==0.1.2
jd_circular_b==0.1.2
jd_circular_c==0.1.2
pipdeptree==2.3.3
```

pipdeptree recognises the packages are installed, but fails to detect the cyclic dependency.

```
>>> import pipdeptree
>>> pkgs = pipdeptree.get_installed_distributions()
>>> tree = pipdeptree.PackageDAG.from_pkgs(pkgs)
>>> for node in tree:
...     print(node)
... 
<DistPackage("wheel")>
<DistPackage("setuptools")>
<DistPackage("pipdeptree")>
<DistPackage("pip")>
<DistPackage("jd-circular-c")>
<DistPackage("jd-circular-b")>
<DistPackage("jd-circular-a")>
>>> pipdeptree.cyclic_deps(tree)
[]
```

moreover it doesn't render them at all by default:

```
$ pipdeptree
pip==22.3.1
pipdeptree==2.3.3
setuptools==66.0.0
wheel==0.38.4
```

Pull request description:
Detect dependency cycles beyond a depth = 2
Should resolve #191.

The previous implementation of `cyclic_deps()` only detected a dependency cycle when a dependency of a `DistPackage` was dependent on that `DistPackage` (e.g. a -> b -> a). Sadly, this did not bid well when you have a cycle such as a -> b -> c -> d -> e -> a (i.e. it has a depth > 2 with "a" as the root).

This CL reimplements it to use DFS, where we perform DFS on each `DistPackage` and just check to see if this `DistPackage` (think of it as the root node) was revisited (by comparing the current node's key that were are visiting to the root node's key).

Patch:
diff --git a/src/pipdeptree/_validate.py b/src/pipdeptree/_validate.py
index bbf2c25..f4dd3e3 100644
--- a/src/pipdeptree/_validate.py
+++ b/src/pipdeptree/_validate.py
@@ -5,6 +5,8 @@ from collections import defaultdict
 from typing import TYPE_CHECKING
 
 if TYPE_CHECKING:
+    from pipdeptree._models.package import Package
+
     from ._cli import Options
     from ._models import DistPackage, PackageDAG, ReqPackage
 
@@ -59,36 +61,61 @@ def render_conflicts_text(conflicts: dict[DistPackage, list[ReqPackage]]) -> Non
                 print(f" - {req_str}", file=sys.stderr)  # noqa: T201
 
 
-def cyclic_deps(tree: PackageDAG) -> list[tuple[DistPackage, ReqPackage, ReqPackage]]:
+def cyclic_deps(tree: PackageDAG) -> list[list[Package]]:
     """
-    Return cyclic dependencies as list of tuples.
+    Return cyclic dependencies as list of lists.
 
     :param  tree: package tree/dag
-    :returns: list of tuples representing cyclic dependencies
-
+    :returns: list of lists, where each list represents a cycle
     """
-    index = {p.key: {r.key for r in rs} for p, rs in tree.items()}
-    cyclic: list[tuple[DistPackage, ReqPackage, ReqPackage]] = []
-    for p, rs in tree.items():
-        for r in rs:
-            if p.key in index.get(r.key, []):
-                val = tree.get_node_as_parent(r.key)
-                if val is not None:
-                    entry = tree.get(val)
-                    if entry is not None:
-                        p_as_dep_of_r = next(x for x in entry if x.key == p.key)
-                        cyclic.append((p, r, p_as_dep_of_r))
-    return cyclic
-
-
-def render_cycles_text(cycles: list[tuple[DistPackage, ReqPackage, ReqPackage]]) -> None:
+
+    def dfs(root: DistPackage, current: Package, visited: set[str], cdeps: list[Package]) -> bool:
+        if current.key not in visited:
+            visited.add(current.key)
+            current_dist = tree.get_node_as_parent(current.key)
+            if not current_dist:
+                return False
+
+            reqs = tree.get(current_dist)
+            if not reqs:
+                return False
+
+            for req in reqs:
+                if dfs(root, req, visited, cdeps):
+                    cdeps.append(current)
+                    return True
+        elif current.key == root.key:
+            cdeps.append(current)
+            return True
+        return False
+
+    cycles: list[list[Package]] = []
+
+    for p in tree:
+        cdeps: list[Package] = []
+        visited: set[str] = set()
+        if dfs(p, p, visited, cdeps):
+            cdeps.reverse()
+            cycles.append(cdeps)
+
+    return cycles
+
+
+def render_cycles_text(cycles: list[list[Package]]) -> None:
     if cycles:
         print("Warning!! Cyclic dependencies found:", file=sys.stderr)  # noqa: T201
-        # List in alphabetical order of the dependency that's cycling
-        # (2nd item in the tuple)
-        cycles = sorted(cycles, key=lambda xs: xs[1].key)
-        for a, b, c in cycles:
-            print(f"* {a.project_name} => {b.project_name} => {c.project_name}", file=sys.stderr)  # noqa: T201
+        # List in alphabetical order the dependency that caused the cycle (i.e. the second-to-last Package element)
+        cycles = sorted(cycles, key=lambda c: c[len(c) - 2].key)
+        for cycle in cycles:
+            print("*", end=" ", file=sys.stderr)  # noqa: T201
+
+            size = len(cycle) - 1
+            for idx, pkg in enumerate(cycle):
+                if idx == size:
+                    print(f"{pkg.project_name}", end="", file=sys.stderr)  # noqa: T201
+                else:
+                    print(f"{pkg.project_name} =>", end=" ", file=sys.stderr)  # noqa: T201
+            print(file=sys.stderr)  # noqa: T201
 
 
 __all__ = [


Test patch:
diff --git a/tests/test_validate.py b/tests/test_validate.py
index 107267d..03755fb 100644
--- a/tests/test_validate.py
+++ b/tests/test_validate.py
@@ -16,35 +16,67 @@ if TYPE_CHECKING:
 @pytest.mark.parametrize(
     ("mpkgs", "expected_keys", "expected_output"),
     [
-        (
+        pytest.param(
             {
                 ("a", "1.0.1"): [("b", [(">=", "2.0.0")])],
                 ("b", "2.3.0"): [("a", [(">=", "1.0.1")])],
                 ("c", "4.5.0"): [("d", [("==", "2.0")])],
                 ("d", "2.0"): [],
             },
-            [("a", "b", "a"), ("b", "a", "b")],
+            [["a", "b", "a"], ["b", "a", "b"]],
             ["Warning!! Cyclic dependencies found:", "* b => a => b", "* a => b => a"],
+            id="depth-of-2",
+        ),
+        pytest.param(
+            {
+                ("a", "1.0.1"): [("b", [(">=", "2.0.0")]), ("e", [("==", "2.0")])],
+                ("b", "2.3.0"): [("c", [(">=", "4.5.0")])],
+                ("c", "4.5.0"): [("d", [("==", "1.0.1")])],
+                ("d", "1.0.0"): [("a", [("==", "1.0.1")]), ("e", [("==", "2.0")])],
+                ("e", "2.0"): [],
+            },
+            [
+                ["b", "c", "d", "a", "b"],
+                ["c", "d", "a", "b", "c"],
+                ["d", "a", "b", "c", "d"],
+                ["a", "b", "c", "d", "a"],
+            ],
+            [
+                "Warning!! Cyclic dependencies found:",
+                "* b => c => d => a => b",
+                "* c => d => a => b => c",
+                "* d => a => b => c => d",
+                "* a => b => c => d => a",
+            ],
+            id="depth-greater-than-2",
+        ),
+        pytest.param(
+            {("a", "1.0.1"): [("b", [(">=", "2.0.0")])], ("b", "2.0.0"): []},
+            [],
+            [],
+            id="no-cycle",
         ),
-        (  # if a dependency isn't installed, cannot verify cycles
+        pytest.param(
             {
                 ("a", "1.0.1"): [("b", [(">=", "2.0.0")])],
             },
             [],
-            [],  # no output expected
+            [],
+            id="dependency-not-installed",
         ),
+        pytest.param({("a", "1.0.1"): []}, [], [], id="no-dependencies"),
     ],
 )
 def test_cyclic_deps(
     capsys: pytest.CaptureFixture[str],
     mpkgs: dict[tuple[str, str], list[tuple[str, list[tuple[str, str]]]]],
-    expected_keys: list[tuple[str, ...]],
+    expected_keys: list[list[str]],
     expected_output: list[str],
     mock_pkgs: Callable[[MockGraph], Iterator[Mock]],
 ) -> None:
     tree = PackageDAG.from_pkgs(list(mock_pkgs(mpkgs)))
     result = cyclic_deps(tree)
-    result_keys = [(a.key, b.key, c.key) for (a, b, c) in result]
+    result_keys = [[dep.key for dep in deps] for deps in result]
     assert sorted(expected_keys) == sorted(result_keys)
     render_cycles_text(result)
     captured = capsys.readouterr()