guppy/graph/feature/
cycles.rs

Help
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    graph::{
8        feature::{FeatureGraph, FeatureId},
9        FeatureIx,
10    },
11    petgraph_support::scc::Sccs,
12    Error,
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 these two IDs are in the same cycle.
35    pub fn is_cyclic<'a>(
36        &self,
37        a: impl Into<FeatureId<'a>>,
38        b: impl Into<FeatureId<'a>>,
39    ) -> Result<bool, Error> {
40        let a = a.into();
41        let b = b.into();
42        let a_ix = self.feature_graph.feature_ix(a)?;
43        let b_ix = self.feature_graph.feature_ix(b)?;
44        Ok(self.sccs.is_same_scc(a_ix, b_ix))
45    }
46
47    /// Returns all the cycles of 2 or more elements in this graph.
48    ///
49    /// Cycles are returned in topological order: if features in cycle B depend on features in cycle
50    /// A, A is returned before B.
51    ///
52    /// Within a cycle, nodes are returned in non-dev order: if feature Foo has a dependency on Bar,
53    /// and Bar has a dev-dependency on Foo, then Foo is returned before Bar.
54    pub fn all_cycles(&self) -> impl Iterator<Item = Vec<FeatureId<'g>>> + 'g {
55        let dep_graph = self.feature_graph.dep_graph();
56        let package_graph = self.feature_graph.package_graph;
57        self.sccs.multi_sccs().map(move |class| {
58            class
59                .iter()
60                .map(move |feature_ix| FeatureId::from_node(package_graph, &dep_graph[*feature_ix]))
61                .collect()
62        })
63    }
64}
guppy/graph/feature/cycles.rs

guppy/graph/feature/
cycles.rs
