1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

// Copyright (c) The cargo-guppy Contributors
// SPDX-License-Identifier: MIT OR Apache-2.0

//! Code for handling cycles in feature graphs.

use crate::{
    graph::{
        feature::{FeatureGraph, FeatureId},
        FeatureIx,
    },
    petgraph_support::scc::Sccs,
    Error,
};

/// Contains information about dependency cycles in feature graphs.
///
/// Cargo permits cycles if at least one of the links is dev-only. `Cycles` exposes information
/// about such dependencies.
///
/// Constructed through `PackageGraph::cycles`.
pub struct Cycles<'g> {
    feature_graph: FeatureGraph<'g>,
    sccs: &'g Sccs<FeatureIx>,
}

impl<'g> Cycles<'g> {
    pub(super) fn new(feature_graph: FeatureGraph<'g>) -> Self {
        Self {
            feature_graph,
            sccs: feature_graph.sccs(),
        }
    }

    /// Returns true if these two IDs are in the same cycle.
    pub fn is_cyclic<'a>(
        &self,
        a: impl Into<FeatureId<'a>>,
        b: impl Into<FeatureId<'a>>,
    ) -> Result<bool, Error> {
        let a = a.into();
        let b = b.into();
        let a_ix = self.feature_graph.feature_ix(a)?;
        let b_ix = self.feature_graph.feature_ix(b)?;
        Ok(self.sccs.is_same_scc(a_ix, b_ix))
    }

    /// Returns all the cycles of 2 or more elements in this graph.
    ///
    /// Cycles are returned in topological order: if features in cycle B depend on features in cycle
    /// A, A is returned before B.
    ///
    /// Within a cycle, nodes are returned in non-dev order: if feature Foo has a dependency on Bar,
    /// and Bar has a dev-dependency on Foo, then Foo is returned before Bar.
    pub fn all_cycles(&self) -> impl Iterator<Item = Vec<FeatureId<'g>>> + 'g {
        let dep_graph = self.feature_graph.dep_graph();
        let package_graph = self.feature_graph.package_graph;
        self.sccs.multi_sccs().map(move |class| {
            class
                .iter()
                .map(move |feature_ix| FeatureId::from_node(package_graph, &dep_graph[*feature_ix]))
                .collect()
        })
    }
}