guppy/graph/
query_core.rs

Help
1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use crate::{
5    graph::{DependencyDirection, GraphSpec},
6    petgraph_support::dfs::{dfs_next_buffered_filter, BufferedEdgeFilter},
7    sorted_set::SortedSet,
8};
9use fixedbitset::FixedBitSet;
10use petgraph::{
11    graph::IndexType,
12    prelude::*,
13    visit::{IntoEdges, IntoNeighbors, Visitable},
14};
15use std::fmt;
16
17pub(super) enum QueryParams<G: GraphSpec> {
18    Forward(SortedSet<NodeIndex<G::Ix>>),
19    Reverse(SortedSet<NodeIndex<G::Ix>>),
20}
21
22impl<G: GraphSpec> QueryParams<G> {
23    pub(super) fn direction(&self) -> DependencyDirection {
24        match self {
25            QueryParams::Forward(_) => DependencyDirection::Forward,
26            QueryParams::Reverse(_) => DependencyDirection::Reverse,
27        }
28    }
29
30    /// Returns true if this query specifies this package as an initial.
31    pub(super) fn has_initial(&self, initial: NodeIndex<G::Ix>) -> bool {
32        match self {
33            QueryParams::Forward(v) => v.contains(&initial),
34            QueryParams::Reverse(v) => v.contains(&initial),
35        }
36    }
37
38    pub(super) fn initials(&self) -> &[NodeIndex<G::Ix>] {
39        match self {
40            QueryParams::Forward(v) => v,
41            QueryParams::Reverse(v) => v,
42        }
43    }
44}
45
46impl<G: GraphSpec> Clone for QueryParams<G>
47where
48    G::Ix: Clone,
49{
50    fn clone(&self) -> Self {
51        match self {
52            QueryParams::Forward(v) => QueryParams::Forward(v.clone()),
53            QueryParams::Reverse(v) => QueryParams::Reverse(v.clone()),
54        }
55    }
56}
57
58impl<G: GraphSpec> fmt::Debug for QueryParams<G>
59where
60    G::Ix: fmt::Debug,
61{
62    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
63        match self {
64            QueryParams::Forward(v) => f.debug_tuple("Forward").field(v).finish(),
65            QueryParams::Reverse(v) => f.debug_tuple("Reverse").field(v).finish(),
66        }
67    }
68}
69
70pub(super) fn all_visit_map<G, Ix>(graph: G) -> (FixedBitSet, usize)
71where
72    G: Visitable<NodeId = NodeIndex<Ix>, Map = FixedBitSet>,
73    Ix: IndexType,
74{
75    let mut visit_map = graph.visit_map();
76    // Mark all nodes visited.
77    visit_map.insert_range(..);
78    let len = visit_map.len();
79    (visit_map, len)
80}
81
82pub(super) fn reachable_map<G, Ix>(
83    graph: G,
84    roots: impl Into<Vec<G::NodeId>>,
85) -> (FixedBitSet, usize)
86where
87    G: Visitable<NodeId = NodeIndex<Ix>, Map = FixedBitSet> + IntoNeighbors,
88    Ix: IndexType,
89{
90    // To figure out what nodes are reachable, run a DFS starting from the roots.
91    // This is DfsPostOrder since that handles cycles while a regular DFS doesn't.
92    let mut dfs = DfsPostOrder::empty(graph);
93    dfs.stack = roots.into();
94    while dfs.next(graph).is_some() {}
95
96    // Once the DFS is done, the discovered map (or the finished map) is what's reachable.
97    debug_assert_eq!(
98        dfs.discovered, dfs.finished,
99        "discovered and finished maps match at the end"
100    );
101    let reachable = dfs.discovered;
102    let len = reachable.count_ones(..);
103    (reachable, len)
104}
105
106pub(super) fn reachable_map_buffered_filter<G, Ix>(
107    graph: G,
108    mut filter: impl BufferedEdgeFilter<G>,
109    roots: impl Into<Vec<G::NodeId>>,
110) -> (FixedBitSet, usize)
111where
112    G: Visitable<NodeId = NodeIndex<Ix>, Map = FixedBitSet> + IntoEdges,
113    Ix: IndexType,
114{
115    // To figure out what nodes are reachable, run a DFS starting from the roots.
116    // This is DfsPostOrder since that handles cycles while a regular DFS doesn't.
117    let mut dfs = DfsPostOrder::empty(graph);
118    dfs.stack = roots.into();
119    while dfs_next_buffered_filter(&mut dfs, graph, &mut filter).is_some() {}
120
121    // Once the DFS is done, the discovered map (or the finished map) is what's reachable.
122    debug_assert_eq!(
123        dfs.discovered, dfs.finished,
124        "discovered and finished maps match at the end"
125    );
126    let reachable = dfs.discovered;
127    let len = reachable.count_ones(..);
128    (reachable, len)
129}
guppy/graph/query_core.rs

guppy/graph/
query_core.rs
