guppy/graph/feature/
cycles.rs

1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! Code for handling cycles in feature graphs.
5
6use crate::{
7    Error,
8    graph::{
9        FeatureIx,
10        feature::{FeatureGraph, FeatureId},
11    },
12    petgraph_support::scc::Sccs,
13};
14
15/// Contains information about dependency cycles in feature graphs.
16///
17/// Cargo permits cycles if at least one of the links is dev-only. `Cycles` exposes information
18/// about such dependencies.
19///
20/// Constructed through `PackageGraph::cycles`.
21pub struct Cycles<'g> {
22    feature_graph: FeatureGraph<'g>,
23    sccs: &'g Sccs<FeatureIx>,
24}
25
26impl<'g> Cycles<'g> {
27    pub(super) fn new(feature_graph: FeatureGraph<'g>) -> Self {
28        Self {
29            feature_graph,
30            sccs: feature_graph.sccs(),
31        }
32    }
33
34    /// Returns true if `a` and `b` lie on a common directed cycle in the
35    /// feature graph.
36    ///
37    /// "Lie on a common cycle" means: in the same Strongly Connected
38    /// Component *and* that SCC is non-trivial.
39    ///
40    /// * For distinct feature IDs, that's the same as being in a multi-node SCC.
41    /// * For the same feature ID, the node must either be in a multi-node SCC,
42    ///   or have a self-loop edge in the dependency graph (e.g., from a `path`
43    ///   dev-dependency on the package's own crate).
44    ///
45    /// In particular, `is_cyclic(a, a)` is *not* reflexively true: it
46    /// returns `false` for features that aren't on any cycle.
47    pub fn is_cyclic<'a>(
48        &self,
49        a: impl Into<FeatureId<'a>>,
50        b: impl Into<FeatureId<'a>>,
51    ) -> Result<bool, Error> {
52        let a = a.into();
53        let b = b.into();
54        let a_ix = self.feature_graph.feature_ix(a)?;
55        let b_ix = self.feature_graph.feature_ix(b)?;
56
57        if a_ix != b_ix {
58            // Different features lie on a common cycle iff they're in the
59            // same SCC -- which, for distinct features, can only be a
60            // multi-node SCC.
61            return Ok(self.sccs.is_same_scc(a_ix, b_ix));
62        }
63
64        // Same feature: on a cycle iff its SCC is non-trivial.
65        Ok(
66            self.sccs.in_multi_scc(a_ix)
67                || self.feature_graph.dep_graph().contains_edge(a_ix, a_ix),
68        )
69    }
70
71    /// Returns all the cyclic Strongly Connected Components of this graph:
72    /// every multi-node SCC, plus every single-node SCC whose feature has
73    /// a self-loop edge.
74    ///
75    /// Cycles are returned in topological order: if features in cycle B
76    /// depend on features in cycle A, A is returned before B.
77    ///
78    /// Within a cycle, nodes are returned in non-dev order: if feature Foo
79    /// has a dependency on Bar, and Bar has a dev-dependency on Foo, then
80    /// Foo is returned before Bar.
81    pub fn all_cycles(&self) -> impl Iterator<Item = Vec<FeatureId<'g>>> + 'g + use<'g> {
82        let dep_graph = self.feature_graph.dep_graph();
83        let package_graph = self.feature_graph.package_graph;
84        self.sccs.all_sccs().filter_map(move |class| {
85            let is_cyclic = match class {
86                [_, _, ..] => true,
87                &[ix] => dep_graph.contains_edge(ix, ix),
88                [] => false,
89            };
90            is_cyclic.then(|| {
91                class
92                    .iter()
93                    .map(move |feature_ix| {
94                        FeatureId::from_node(package_graph, &dep_graph[*feature_ix])
95                    })
96                    .collect()
97            })
98        })
99    }
100}
guppy/graph/feature/cycles.rs

guppy/graph/feature/
cycles.rs
