Repository: tox-dev/pipdeptree (python)

Issue:
Implement `--exclude-dependencies` to make `--exclude` exclude a package's dependencies
### Describe the feature

Related discussions are [here](https://github.com/tox-dev/pipdeptree/discussions/434) and [here](https://github.com/tox-dev/pipdeptree/issues/452).

Currently, `--exclude` does its job of excluding packages from the dependency tree. This is fine, but when there are times when we also want to remove their dependencies from the output the current implementation doesn't make this possible.

This issue proposes an `--exclude-dependencies` flag that will have pipdeptree take this additional step of removing dependencies from the output.

In the future major versions, it may make sense to just make this the default behavior of `--exclude`. But to avoid a breaking change, it should just be a flag for now.

Pull request description:
Implement --exclude-dependencies
Resolves #453.

Much harder than I expected to implement, but I think my logic and implementation checks out. The algorithm is the following:

- Take the _exclude_ set from CLI input and resolve it to actual nodes in the graph
- Determine all possible candidates for exclusion by performing DFS
  - So we add the direct and transitive dependencies of the exclude nodes we gathered in Step 1 into a `candidates` set, but **we aren't sure yet** if they should be excluded since a non-excluded node maybe using it. **This is the reason** why we have more steps below
- Create a reversed graph so that we know all the nodes that depend on a specific node
- Iterate over `candidates`, **counting** the number of dependents for each node using the reversed graph
- Now iterate over the explicitly-excluded nodes that we created in Step 1, where for each node:
  - Add it to the **new excluded set**
  - Iterate over their children. For each child, get the dependent count of that child and decrement it by 1
    - If the count equals 0, we haven't added it to the new set, and it isn't apart of the original resolved set created in Step 1, this child is a candidate for exclusion so let's add it (and in effect, also add their applicable children)
    - If this specific branch is never reached, it means that **their is a non-excluded node that has an outgoing edge to child**. We should not remove it
- Return the **new excluded set**, which will contain both the explicitly-excluded nodes and the dependency nodes associated to them

Patch:
diff --git a/.pre-commit-config.yaml b/.pre-commit-config.yaml
index 5944e06..af3e67c 100644
--- a/.pre-commit-config.yaml
+++ b/.pre-commit-config.yaml
@@ -5,7 +5,7 @@ repos:
       - id: end-of-file-fixer
       - id: trailing-whitespace
   - repo: https://github.com/python-jsonschema/check-jsonschema
-    rev: 0.33.1
+    rev: 0.33.2
     hooks:
       - id: check-github-workflows
         args: ["--verbose"]
@@ -23,7 +23,7 @@ repos:
     hooks:
       - id: pyproject-fmt
   - repo: https://github.com/astral-sh/ruff-pre-commit
-    rev: "v0.12.1"
+    rev: "v0.12.2"
     hooks:
       - id: ruff-format
       - id: ruff
diff --git a/src/pipdeptree/__main__.py b/src/pipdeptree/__main__.py
index 0cea4cf..2f8a24b 100644
--- a/src/pipdeptree/__main__.py
+++ b/src/pipdeptree/__main__.py
@@ -57,7 +57,7 @@ def main(args: Sequence[str] | None = None) -> int | None:
 
     if show_only is not None or exclude is not None:
         try:
-            tree = tree.filter_nodes(show_only, exclude)
+            tree = tree.filter_nodes(show_only, exclude, exclude_deps=options.exclude_dependencies)
         except ValueError as e:
             if warning_printer.should_warn():
                 warning_printer.print_single_line(str(e))
diff --git a/src/pipdeptree/_cli.py b/src/pipdeptree/_cli.py
index ea9fb92..8dfdd2d 100644
--- a/src/pipdeptree/_cli.py
+++ b/src/pipdeptree/_cli.py
@@ -24,6 +24,7 @@ class Options(Namespace):
     reverse: bool
     packages: str
     exclude: str
+    exclude_dependencies: bool
     json: bool
     json_tree: bool
     mermaid: bool
@@ -82,6 +83,11 @@ def build_parser() -> ArgumentParser:
         "(cannot combine with -p or -a)",
         metavar="P",
     )
+    select.add_argument(
+        "--exclude-dependencies",
+        help="Used along with --exclude to also exclude dependencies of packages",
+        action="store_true",
+    )
 
     scope = select.add_mutually_exclusive_group()
     scope.add_argument(
@@ -166,6 +172,8 @@ def get_options(args: Sequence[str] | None) -> Options:
 
     if parsed_args.exclude and (parsed_args.all or parsed_args.packages):
         return parser.error("cannot use --exclude with --packages or --all")
+    if parsed_args.exclude_dependencies and not parsed_args.exclude:
+        return parser.error("must use --exclude-dependencies with --exclude")
     if parsed_args.license and parsed_args.freeze:
         return parser.error("cannot use --license with --freeze")
     if parsed_args.path and (parsed_args.local_only or parsed_args.user_only):
diff --git a/src/pipdeptree/_models/dag.py b/src/pipdeptree/_models/dag.py
index 41c1cf8..eda363c 100644
--- a/src/pipdeptree/_models/dag.py
+++ b/src/pipdeptree/_models/dag.py
@@ -126,7 +126,12 @@ class PackageDAG(Mapping[DistPackage, list[ReqPackage]]):
         node = self.get_node_as_parent(node_key)
         return self._obj[node] if node else []
 
-    def filter_nodes(self, include: list[str] | None, exclude: set[str] | None) -> PackageDAG:  # noqa: C901, PLR0912
+    def filter_nodes(  # noqa: C901, PLR0912
+        self,
+        include: list[str] | None,
+        exclude: set[str] | None,
+        exclude_deps: bool = False,  # noqa: FBT001, FBT002
+    ) -> PackageDAG:
         """
         Filter nodes in a graph by given parameters.
 
@@ -153,14 +158,16 @@ class PackageDAG(Mapping[DistPackage, list[ReqPackage]]):
         if include and exclude:
             assert not (set(include) & exclude)
 
-        # Traverse the graph in a depth first manner and filter the
-        # nodes according to `show_only` and `exclude` sets
+        if exclude_deps:
+            exclude = self._build_exclusion_set_with_dependencies(exclude)
+
+        # Filter nodes that are explicitly included/excluded
         stack: deque[DistPackage] = deque()
         m: dict[DistPackage, list[ReqPackage]] = {}
         seen = set()
         matched_includes: set[str] = set()
         for node in self._obj:
-            if any(fnmatch(node.key, e) for e in exclude):
+            if should_exclude_node(node.key, exclude):
                 continue
             if include is None:
                 stack.append(node)
@@ -176,9 +183,10 @@ class PackageDAG(Mapping[DistPackage, list[ReqPackage]]):
                 if should_append:
                     stack.append(node)
 
+            # Perform DFS on the explicitly included nodes so that we can also include their dependencies, if applicable
             while stack:
                 n = stack.pop()
-                cldn = [c for c in self._obj[n] if not any(fnmatch(c.key, e) for e in exclude)]
+                cldn = [c for c in self._obj[n] if not should_exclude_node(c.key, exclude)]
                 m[n] = cldn
                 seen.add(n.key)
                 for c in cldn:
@@ -199,6 +207,63 @@ class PackageDAG(Mapping[DistPackage, list[ReqPackage]]):
 
         return self.__class__(m)
 
+    def _build_exclusion_set_with_dependencies(self, old_exclude: set[str]) -> set[str]:
+        """
+        Build a new exclusion set using the fnmatch patterns in `old_exclude` to also grab dependencies.
+
+        Note that it will actually resolve the patterns in old_exclude to actual nodes and use that result instead of
+        keeping the patterns.
+        """
+        # First, resolve old_exclude to actual nodes in the graph as old_exclude may instead contain patterns that are
+        # used by fnmatch (or the exclusion may not even exist in the graph)
+        resolved_exclude: set[str] = set()
+
+        resolved_exclude.update(node.key for node in self._obj if should_exclude_node(node.key, old_exclude))
+
+        # Find all possible candidate nodes for exclusion using DFS
+        candidates: set[str] = set()
+        stack = list(resolved_exclude)
+        while stack:
+            candidate = stack.pop()
+            if candidate not in candidates:
+                candidates.add(candidate)
+                stack.extend(dep.key for dep in self.get_children(candidate))
+
+        # Build a reverse graph to know the dependents of a candidate node
+        reverse_graph = self.reverse()
+
+        # Precompute number of dependents for each candidate
+        dependents_count: defaultdict[str, int] = defaultdict(int)
+        for node in candidates:
+            dependents_count[node] += len(reverse_graph.get_children(node))
+
+        new_exclude = set()
+
+        # Determine what nodes should actually be excluded
+        # Use the resolved exclude set as a starting point as these nodes are explicitly excluded
+        queue = deque(resolved_exclude)
+        while queue:
+            node = queue.popleft()
+            new_exclude.add(node)
+            for child in self.get_children(node):
+                child_key = child.key
+                dependents_count[child_key] -= 1
+
+                # If all dependents of child are excluded, it itself is now eligible for exclusion
+                # If this branch is never reached, this means there is a dependant that is outside the exclusion set
+                # that needs child
+                #
+                # We also don't want to add child nodes that are in the resolved exclude set, as they are explicitly
+                # excluded and have either already been processed or are in the queue awaiting processing
+                if (
+                    dependents_count[child_key] == 0
+                    and child_key not in new_exclude
+                    and child_key not in resolved_exclude
+                ):
+                    queue.append(child_key)
+
+        return new_exclude
+
     def reverse(self) -> ReversedPackageDAG:
         """
         Reverse the DAG, or turn it upside-down.
@@ -247,6 +312,10 @@ class PackageDAG(Mapping[DistPackage, list[ReqPackage]]):
         return len(self._obj)
 
 
+def should_exclude_node(key: str, exclude: set[str]) -> bool:
+    return any(fnmatch(key, e) for e in exclude)
+
+
 class ReversedPackageDAG(PackageDAG):
     """
     Representation of Package dependencies in the reverse order.


Test patch:
diff --git a/tests/_models/test_dag.py b/tests/_models/test_dag.py
index 509fc83..d139845 100644
--- a/tests/_models/test_dag.py
+++ b/tests/_models/test_dag.py
@@ -88,6 +88,83 @@ def test_package_dag_filter_packages_uses_pep503normalize(
     assert len(pkgs) == 0
 
 
+@pytest.mark.parametrize(
+    ("graph", "exclude", "expected"),
+    [
+        pytest.param(
+            {
+                ("a", "1.0.0"): [("b", []), ("c", []), ("d", []), ("e", [])],
+                ("b", "2.0.0"): [("x", []), ("y", []), ("z", [])],
+                ("c", "3.0.0"): [("d", [])],
+                ("d", "4.0.0"): [],
+                ("e", "5.0.0"): [("y", [])],
+                ("f", "6.0.0"): [("d", [])],  # Make sure that "d" is not removed since "f" is not excluded
+                ("g", "7.0.0"): [],
+                ("x", "8.0.0"): [],
+                ("y", "9.0.0"): [],
+                ("z", "10.0.0"): [],
+            },
+            {"a"},
+            {"d", "f", "g"},
+            id="with-dependencies",
+        ),
+        pytest.param(
+            {
+                ("acorn", "1.0.0"): [("b", []), ("c", []), ("d", []), ("e", [])],
+                ("b", "2.0.0"): [("x", []), ("y", []), ("z", [])],
+                ("c", "3.0.0"): [("d", [])],
+                ("d", "4.0.0"): [],
+                ("e", "5.0.0"): [("y", [])],
+                ("f", "6.0.0"): [("d", [])],
+                ("g", "7.0.0"): [],
+                ("x", "8.0.0"): [],
+                ("y", "9.0.0"): [],
+                ("z", "10.0.0"): [],
+            },
+            {"a*", "g"},
+            {"d", "f"},
+            id="with-multiple-excludes-and-with-patterns",
+        ),
+        pytest.param(
+            {
+                ("b", "2.0.0"): [("x", []), ("y", []), ("z", [])],
+                ("x", "8.0.0"): [],
+                ("y", "9.0.0"): [],
+                ("z", "10.0.0"): [],
+            },
+            {"dontexist"},
+            {"b", "x", "y", "z"},
+            id="with-non-existent-exclude",
+        ),
+        pytest.param(
+            {
+                ("a", "1.0.0"): [("b", [])],
+                ("b", "2.0.0"): [("c", [])],
+                ("c", "3.0.0"): [("d", [])],
+                ("d", "4.0.0"): [("e", [])],
+                ("e", "5.0.0"): [("f", [])],
+                ("f", "6.0.0"): [("g", [])],
+                ("g", "7.0.0"): [("x", [])],
+                ("x", "8.0.0"): [("y", [])],
+                ("y", "9.0.0"): [("z", [])],
+                ("z", "10.0.0"): [],
+            },
+            {"c"},
+            {"a", "b"},
+            id="with-package-having-large-depth",
+        ),
+    ],
+)
+def test_package_dag_filter_packages_given_exclude_dependencies(
+    mock_pkgs: Callable[[MockGraph], Iterator[Mock]], graph: MockGraph, exclude: set[str], expected: list[str]
+) -> None:
+    pkgs = PackageDAG.from_pkgs(list(mock_pkgs(graph)))
+    pkgs = pkgs.filter_nodes(None, exclude, exclude_deps=True)
+
+    assert len(pkgs) == len(expected)
+    assert all(p.key in expected for p in pkgs)
+
+
 def test_package_dag_reverse(example_dag: PackageDAG) -> None:
     def sort_map_values(m: dict[str, Any]) -> dict[str, Any]:
         return {k: sorted(v) for k, v in m.items()}
diff --git a/tests/test_cli.py b/tests/test_cli.py
index a7e95d4..fd7a528 100644
--- a/tests/test_cli.py
+++ b/tests/test_cli.py
@@ -130,6 +130,15 @@ def test_parser_get_options_path_with_either_local_or_user_not_supported(
     assert "cannot use --path with --user-only or --local-only" in err
 
 
+def test_parser_get_options_exclude_dependencies_without_exclude(capsys: pytest.CaptureFixture[str]) -> None:
+    with pytest.raises(SystemExit, match="2"):
+        get_options(["--exclude-dependencies"])
+
+    out, err = capsys.readouterr()
+    assert not out
+    assert "must use --exclude-dependencies with --exclude" in err
+
+
 @pytest.mark.parametrize(("bad_type"), [None, str])
 def test_enum_action_type_argument(bad_type: Any) -> None:
     with pytest.raises(TypeError, match="type must be a subclass of Enum"):