guppy 0.18.0

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

use crate::{
    graph::{DependencyDirection, GraphSpec, ix_set::IxSet},
    petgraph_support::{
        dfs::{
            BufferedEdgeFilter, ReversedBufferedFilter, SimpleEdgeFilterFn,
            dfs_next_buffered_filter,
        },
        scc::{NodeIter, Sccs},
        walk::EdgeDfs,
    },
};
use debug_ignore::DebugIgnore;
use fixedbitset::FixedBitSet;
use petgraph::{
    graph::{EdgeReference, IndexType},
    prelude::*,
    visit::{IntoEdges, IntoNeighbors, NodeFiltered, Reversed, Visitable},
};
use std::fmt;

/// Core logic for queries that have been resolved into a known set of packages.
///
/// The `G` param ensures that package and feature resolutions aren't mixed up accidentally.
#[derive(Clone)]
pub(super) struct ResolveCore<G> {
    pub(super) included: IxSet<G>,
}

// A manual impl avoids a G: Debug bound from the derive.
impl<G: GraphSpec> fmt::Debug for ResolveCore<G> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("ResolveCore")
            .field("included", &self.included)
            .finish()
    }
}

impl<G: GraphSpec> ResolveCore<G> {
    pub(super) fn new(
        graph: &Graph<G::Node, G::Edge, Directed, G::Ix>,
        initials: impl IntoIterator<Item = NodeIndex<G::Ix>>,
        direction: DependencyDirection,
    ) -> Self {
        let (included, len) = match direction {
            DependencyDirection::Forward => reachable_map(graph, initials),
            DependencyDirection::Reverse => reachable_map(Reversed(graph), initials),
        };
        Self {
            included: IxSet::from_visit_map(included, len, graph.node_count()),
        }
    }

    pub(super) fn all_nodes(graph: &Graph<G::Node, G::Edge, Directed, G::Ix>) -> Self {
        let (included, len) = all_visit_map(graph);
        Self {
            included: IxSet::from_visit_map(included, len, graph.node_count()),
        }
    }

    pub(super) fn empty(graph: &Graph<G::Node, G::Edge, Directed, G::Ix>) -> Self {
        Self {
            included: IxSet::empty(graph.node_count()),
        }
    }

    /// The arguments to the edge filter are the (source, target, edge ix), unreversed.
    pub(super) fn with_edge_filter<'g>(
        graph: &'g Graph<G::Node, G::Edge, Directed, G::Ix>,
        initials: impl IntoIterator<Item = NodeIndex<G::Ix>>,
        direction: DependencyDirection,
        edge_filter: impl FnMut(EdgeReference<'g, G::Edge, G::Ix>) -> bool,
    ) -> Self {
        let (included, len) = match direction {
            DependencyDirection::Forward => {
                reachable_map_buffered_filter(graph, SimpleEdgeFilterFn(edge_filter), initials)
            }
            DependencyDirection::Reverse => reachable_map_buffered_filter(
                Reversed(graph),
                ReversedBufferedFilter(SimpleEdgeFilterFn(edge_filter)),
                initials,
            ),
        };
        Self {
            included: IxSet::from_visit_map(included, len, graph.node_count()),
        }
    }

    /// The arguments to the edge filter are the (source, target, edge ix), unreversed.
    pub(super) fn with_buffered_edge_filter<'g>(
        graph: &'g Graph<G::Node, G::Edge, Directed, G::Ix>,
        initials: impl IntoIterator<Item = NodeIndex<G::Ix>>,
        direction: DependencyDirection,
        filter: impl BufferedEdgeFilter<&'g Graph<G::Node, G::Edge, Directed, G::Ix>>,
    ) -> Self {
        let (included, len) = match direction {
            DependencyDirection::Forward => reachable_map_buffered_filter(graph, filter, initials),
            DependencyDirection::Reverse => reachable_map_buffered_filter(
                Reversed(graph),
                ReversedBufferedFilter(filter),
                initials,
            ),
        };
        Self {
            included: IxSet::from_visit_map(included, len, graph.node_count()),
        }
    }

    pub(super) fn from_ixs(
        ixs: impl IntoIterator<Item = NodeIndex<G::Ix>>,
        graph: &Graph<G::Node, G::Edge, Directed, G::Ix>,
    ) -> Self {
        Self {
            included: IxSet::from_ixs(ixs, graph.node_count()),
        }
    }

    pub(super) fn from_included<T: Into<FixedBitSet>>(
        included: T,
        graph: &Graph<G::Node, G::Edge, Directed, G::Ix>,
    ) -> Self {
        Self {
            included: IxSet::from_bits(included.into(), graph.node_count()),
        }
    }

    pub(super) fn len(&self) -> usize {
        self.included.len()
    }

    pub(super) fn is_empty(&self) -> bool {
        self.included.is_empty()
    }

    pub(super) fn contains(&self, ix: NodeIndex<G::Ix>) -> bool {
        self.included.contains(ix)
    }

    // ---
    // Set operations
    // ---

    pub(super) fn union_with(&mut self, other: &Self) {
        self.included.union_with(&other.included);
    }

    pub(super) fn intersect_with(&mut self, other: &Self) {
        self.included.intersect_with(&other.included);
    }

    pub(super) fn difference(&self, other: &Self) -> Self {
        Self {
            included: self.included.difference(&other.included),
        }
    }

    pub(super) fn symmetric_difference_with(&mut self, other: &Self) {
        self.included.symmetric_difference_with(&other.included);
    }

    /// Returns the root metadatas in the specified direction.
    pub(super) fn roots(
        &self,
        graph: &Graph<G::Node, G::Edge, Directed, G::Ix>,
        sccs: &Sccs<G::Ix>,
        direction: DependencyDirection,
    ) -> Vec<NodeIndex<G::Ix>> {
        // This uses the SCCs in self.sccs. If any node in an SCC is a root, so is any other.
        match direction {
            DependencyDirection::Forward => sccs
                .externals(&NodeFiltered(graph, &self.included))
                .collect(),
            DependencyDirection::Reverse => sccs
                .externals(&NodeFiltered(Reversed(graph), &self.included))
                .collect(),
        }
    }

    pub(super) fn topo<'g>(
        &'g self,
        sccs: &'g Sccs<G::Ix>,
        direction: DependencyDirection,
    ) -> Topo<'g, G> {
        // ---
        // IMPORTANT
        // ---
        //
        // This uses the same list of sccs that's computed for the entire graph. This is fine for
        // resolve() -- over there, if one element of an SCC is present all others will be present
        // as well.
        //
        // * However, with resolve_with() and a custom resolver, it is possible that SCCs in the
        //   main graph aren't in the subgraph. That makes the returned order "incorrect", but it's
        //   a very minor sin and probably not worth the extra complexity to deal with.
        // * This requires iterating over every node in the graph even if the set of returned nodes
        //   is very small. There's a tradeoff here between allocating memory to store a custom list
        //   of SCCs and just using the one available. More benchmarking is required to figure out
        //   the best approach.
        //
        // Note that the SCCs can be computed in reachable_map by adapting parts of kosaraju_scc.
        let node_iter = sccs.node_iter(direction.into());

        Topo {
            node_iter,
            included: &self.included,
            remaining: self.included.len(),
        }
    }

    pub(super) fn links<'g>(
        &'g self,
        graph: &'g Graph<G::Node, G::Edge, Directed, G::Ix>,
        sccs: &Sccs<G::Ix>,
        direction: DependencyDirection,
    ) -> Links<'g, G> {
        let edge_dfs = match direction {
            DependencyDirection::Forward => {
                let filtered_graph = NodeFiltered(graph, &self.included);
                EdgeDfs::new(&filtered_graph, sccs.externals(&filtered_graph))
            }
            DependencyDirection::Reverse => {
                let filtered_reversed_graph = NodeFiltered(Reversed(graph), &self.included);
                EdgeDfs::new(
                    &filtered_reversed_graph,
                    sccs.externals(&filtered_reversed_graph),
                )
            }
        };

        Links {
            graph: DebugIgnore(graph),
            included: &self.included,
            edge_dfs,
            direction,
        }
    }
}

impl<G: GraphSpec> PartialEq for ResolveCore<G> {
    fn eq(&self, other: &Self) -> bool {
        self.included == other.included
    }
}

impl<G: GraphSpec> Eq for ResolveCore<G> {}

/// An iterator over package nodes in topological order.
#[derive(Clone, Debug)]
pub(super) struct Topo<'g, G: GraphSpec> {
    node_iter: NodeIter<'g, G::Ix>,
    included: &'g IxSet<G>,
    remaining: usize,
}

impl<G: GraphSpec> Iterator for Topo<'_, G> {
    type Item = NodeIndex<G::Ix>;

    fn next(&mut self) -> Option<Self::Item> {
        for ix in &mut self.node_iter {
            if !self.included.contains(ix) {
                continue;
            }
            self.remaining -= 1;
            return Some(ix);
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

impl<G: GraphSpec> ExactSizeIterator for Topo<'_, G> {
    fn len(&self) -> usize {
        self.remaining
    }
}

/// An iterator over dependency links.
#[derive(Clone, Debug)]
#[allow(clippy::type_complexity)]
pub(super) struct Links<'g, G: GraphSpec> {
    graph: DebugIgnore<&'g Graph<G::Node, G::Edge, Directed, G::Ix>>,
    included: &'g IxSet<G>,
    edge_dfs: EdgeDfs<EdgeIndex<G::Ix>, NodeIndex<G::Ix>, FixedBitSet>,
    direction: DependencyDirection,
}

impl<G: GraphSpec> Iterator for Links<'_, G> {
    #[allow(clippy::type_complexity)]
    type Item = (NodeIndex<G::Ix>, NodeIndex<G::Ix>, EdgeIndex<G::Ix>);

    fn next(&mut self) -> Option<Self::Item> {
        match self.direction {
            DependencyDirection::Forward => {
                let filtered = NodeFiltered(self.graph.0, self.included);
                self.edge_dfs.next(&filtered)
            }
            DependencyDirection::Reverse => {
                let filtered_reversed = NodeFiltered(Reversed(self.graph.0), self.included);
                self.edge_dfs
                    .next(&filtered_reversed)
                    .map(|(source_ix, target_ix, edge_ix)| {
                        // Flip the source and target around since this is a reversed graph, since the
                        // 'from' and 'to' are always right way up.
                        (target_ix, source_ix, edge_ix)
                    })
            }
        }
    }
}

fn all_visit_map<G, Ix>(graph: G) -> (FixedBitSet, usize)
where
    G: Visitable<NodeId = NodeIndex<Ix>, Map = FixedBitSet>,
    Ix: IndexType,
{
    let mut visit_map = graph.visit_map();
    // Mark all nodes visited.
    visit_map.insert_range(..);
    let len = visit_map.len();
    (visit_map, len)
}

fn reachable_map<G, Ix>(
    graph: G,
    roots: impl IntoIterator<Item = G::NodeId>,
) -> (FixedBitSet, usize)
where
    G: Visitable<NodeId = NodeIndex<Ix>, Map = FixedBitSet> + IntoNeighbors,
    Ix: IndexType,
{
    // To figure out what nodes are reachable, run a DFS starting from the roots.
    // This is DfsPostOrder since that handles cycles while a regular DFS doesn't.
    let mut dfs = DfsPostOrder::empty(graph);
    dfs.stack = roots.into_iter().collect();
    while dfs.next(graph).is_some() {}

    // Once the DFS is done, the discovered map (or the finished map) is what's reachable.
    debug_assert_eq!(
        dfs.discovered, dfs.finished,
        "discovered and finished maps match at the end"
    );
    let reachable = dfs.discovered;
    let len = reachable.count_ones(..);
    (reachable, len)
}

fn reachable_map_buffered_filter<G, Ix>(
    graph: G,
    mut filter: impl BufferedEdgeFilter<G>,
    roots: impl IntoIterator<Item = G::NodeId>,
) -> (FixedBitSet, usize)
where
    G: Visitable<NodeId = NodeIndex<Ix>, Map = FixedBitSet> + IntoEdges,
    Ix: IndexType,
{
    // To figure out what nodes are reachable, run a DFS starting from the roots.
    // This is DfsPostOrder since that handles cycles while a regular DFS doesn't.
    let mut dfs = DfsPostOrder::empty(graph);
    dfs.stack = roots.into_iter().collect();
    while dfs_next_buffered_filter(&mut dfs, graph, &mut filter).is_some() {}

    // Once the DFS is done, the discovered map (or the finished map) is what's reachable.
    debug_assert_eq!(
        dfs.discovered, dfs.finished,
        "discovered and finished maps match at the end"
    );
    let reachable = dfs.discovered;
    let len = reachable.count_ones(..);
    (reachable, len)
}