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
// Copyright (c) The cargo-guppy Contributors
// SPDX-License-Identifier: MIT OR Apache-2.0
//! Code for handling cycles in dependency graphs.
use crate::{
graph::{PackageGraph, PackageIx},
petgraph_support::scc::Sccs,
Error, PackageId,
};
/// Contains information about dependency cycles.
///
/// 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> {
package_graph: &'g PackageGraph,
sccs: &'g Sccs<PackageIx>,
}
impl<'g> Cycles<'g> {
pub(super) fn new(package_graph: &'g PackageGraph) -> Self {
Self {
package_graph,
sccs: package_graph.sccs(),
}
}
/// Returns true if these two IDs are in the same cycle.
pub fn is_cyclic(&self, a: &PackageId, b: &PackageId) -> Result<bool, Error> {
let a_ix = self.package_graph.package_ix(a)?;
let b_ix = self.package_graph.package_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 packages in cycle B depend on packages in cycle
/// A, A is returned before B.
///
/// Within a cycle, nodes are returned in non-dev order: if package Foo has a dependency on Bar,
/// and Bar has a cyclic dev-dependency on Foo, then Foo is returned before Bar.
pub fn all_cycles(
&self,
) -> impl Iterator<Item = Vec<&'g PackageId>> + DoubleEndedIterator + 'g {
let dep_graph = &self.package_graph.dep_graph;
self.sccs
.multi_sccs()
.map(move |scc| scc.iter().map(move |ix| &dep_graph[*ix]).collect())
}
}