guppy/graph/
resolve_core.rs

1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use crate::{
5    debug_ignore::DebugIgnore,
6    graph::{
7        DependencyDirection, GraphSpec,
8        query_core::{QueryParams, all_visit_map, reachable_map, reachable_map_buffered_filter},
9    },
10    petgraph_support::{
11        dfs::{BufferedEdgeFilter, ReversedBufferedFilter, SimpleEdgeFilterFn},
12        scc::{NodeIter, Sccs},
13        walk::EdgeDfs,
14    },
15};
16use fixedbitset::FixedBitSet;
17use petgraph::{
18    graph::EdgeReference,
19    prelude::*,
20    visit::{NodeFiltered, Reversed, VisitMap},
21};
22use std::marker::PhantomData;
23
24/// Core logic for queries that have been resolved into a known set of packages.
25///
26/// The `G` param ensures that package and feature resolutions aren't mixed up accidentally.
27#[derive(Clone, Debug)]
28pub(super) struct ResolveCore<G> {
29    pub(super) included: FixedBitSet,
30    pub(super) len: usize,
31    _phantom: PhantomData<G>,
32}
33
34impl<G: GraphSpec> ResolveCore<G> {
35    pub(super) fn new(
36        graph: &Graph<G::Node, G::Edge, Directed, G::Ix>,
37        params: QueryParams<G>,
38    ) -> Self {
39        let (included, len) = match params {
40            QueryParams::Forward(initials) => reachable_map(graph, initials.into_inner()),
41            QueryParams::Reverse(initials) => reachable_map(Reversed(graph), initials.into_inner()),
42        };
43        Self {
44            included,
45            len,
46            _phantom: PhantomData,
47        }
48    }
49
50    pub(super) fn all_nodes(graph: &Graph<G::Node, G::Edge, Directed, G::Ix>) -> Self {
51        let (included, len) = all_visit_map(graph);
52        Self {
53            included,
54            len,
55            _phantom: PhantomData,
56        }
57    }
58
59    pub(super) fn empty() -> Self {
60        Self {
61            included: FixedBitSet::with_capacity(0),
62            len: 0,
63            _phantom: PhantomData,
64        }
65    }
66
67    /// The arguments to the edge filter are the (source, target, edge ix), unreversed.
68    pub(super) fn with_edge_filter<'g>(
69        graph: &'g Graph<G::Node, G::Edge, Directed, G::Ix>,
70        params: QueryParams<G>,
71        edge_filter: impl FnMut(EdgeReference<'g, G::Edge, G::Ix>) -> bool,
72    ) -> Self {
73        let (included, len) = match params {
74            QueryParams::Forward(initials) => reachable_map_buffered_filter(
75                graph,
76                SimpleEdgeFilterFn(edge_filter),
77                initials.into_inner(),
78            ),
79            QueryParams::Reverse(initials) => reachable_map_buffered_filter(
80                Reversed(graph),
81                ReversedBufferedFilter(SimpleEdgeFilterFn(edge_filter)),
82                initials.into_inner(),
83            ),
84        };
85        Self {
86            included,
87            len,
88            _phantom: PhantomData,
89        }
90    }
91
92    /// The arguments to the edge filter are the (source, target, edge ix), unreversed.
93    pub(super) fn with_buffered_edge_filter<'g>(
94        graph: &'g Graph<G::Node, G::Edge, Directed, G::Ix>,
95        params: QueryParams<G>,
96        filter: impl BufferedEdgeFilter<&'g Graph<G::Node, G::Edge, Directed, G::Ix>>,
97    ) -> Self {
98        let (included, len) = match params {
99            QueryParams::Forward(initials) => {
100                reachable_map_buffered_filter(graph, filter, initials.into_inner())
101            }
102            QueryParams::Reverse(initials) => reachable_map_buffered_filter(
103                Reversed(graph),
104                ReversedBufferedFilter(filter),
105                initials.into_inner(),
106            ),
107        };
108        Self {
109            included,
110            len,
111            _phantom: PhantomData,
112        }
113    }
114
115    pub(super) fn from_included<T: Into<FixedBitSet>>(included: T) -> Self {
116        let included = included.into();
117        let len = included.count_ones(..);
118        Self {
119            included,
120            len,
121            _phantom: PhantomData,
122        }
123    }
124
125    pub(super) fn len(&self) -> usize {
126        self.len
127    }
128
129    pub(super) fn is_empty(&self) -> bool {
130        self.len == 0
131    }
132
133    pub(super) fn contains(&self, ix: NodeIndex<G::Ix>) -> bool {
134        self.included.is_visited(&ix)
135    }
136
137    // ---
138    // Set operations
139    // ---
140
141    pub(super) fn union_with(&mut self, other: &Self) {
142        self.included.union_with(&other.included);
143        self.invalidate_caches();
144    }
145
146    pub(super) fn intersect_with(&mut self, other: &Self) {
147        self.included.intersect_with(&other.included);
148        self.invalidate_caches();
149    }
150
151    // fixedbitset 0.2.0 doesn't have a difference_with :(
152    pub(super) fn difference(&self, other: &Self) -> Self {
153        Self::from_included(
154            self.included
155                .difference(&other.included)
156                .collect::<FixedBitSet>(),
157        )
158    }
159
160    pub(super) fn symmetric_difference_with(&mut self, other: &Self) {
161        self.included.symmetric_difference_with(&other.included);
162        self.invalidate_caches();
163    }
164
165    pub(super) fn invalidate_caches(&mut self) {
166        self.len = self.included.count_ones(..);
167    }
168
169    /// Returns the root metadatas in the specified direction.
170    pub(super) fn roots(
171        &self,
172        graph: &Graph<G::Node, G::Edge, Directed, G::Ix>,
173        sccs: &Sccs<G::Ix>,
174        direction: DependencyDirection,
175    ) -> Vec<NodeIndex<G::Ix>> {
176        // This uses the SCCs in self.sccs. If any node in an SCC is a root, so is any other.
177        match direction {
178            DependencyDirection::Forward => sccs
179                .externals(&NodeFiltered(graph, &self.included))
180                .collect(),
181            DependencyDirection::Reverse => sccs
182                .externals(&NodeFiltered(Reversed(graph), &self.included))
183                .collect(),
184        }
185    }
186
187    pub(super) fn topo<'g>(
188        &'g self,
189        sccs: &'g Sccs<G::Ix>,
190        direction: DependencyDirection,
191    ) -> Topo<'g, G> {
192        // ---
193        // IMPORTANT
194        // ---
195        //
196        // This uses the same list of sccs that's computed for the entire graph. This is fine for
197        // resolve() -- over there, if one element of an SCC is present all others will be present
198        // as well.
199        //
200        // * However, with resolve_with() and a custom resolver, it is possible that SCCs in the
201        //   main graph aren't in the subgraph. That makes the returned order "incorrect", but it's
202        //   a very minor sin and probably not worth the extra complexity to deal with.
203        // * This requires iterating over every node in the graph even if the set of returned nodes
204        //   is very small. There's a tradeoff here between allocating memory to store a custom list
205        //   of SCCs and just using the one available. More benchmarking is required to figure out
206        //   the best approach.
207        //
208        // Note that the SCCs can be computed in reachable_map by adapting parts of kosaraju_scc.
209        let node_iter = sccs.node_iter(direction.into());
210
211        Topo {
212            node_iter,
213            included: &self.included,
214            remaining: self.len,
215        }
216    }
217
218    pub(super) fn links<'g>(
219        &'g self,
220        graph: &'g Graph<G::Node, G::Edge, Directed, G::Ix>,
221        sccs: &Sccs<G::Ix>,
222        direction: DependencyDirection,
223    ) -> Links<'g, G> {
224        let edge_dfs = match direction {
225            DependencyDirection::Forward => {
226                let filtered_graph = NodeFiltered(graph, &self.included);
227                EdgeDfs::new(&filtered_graph, sccs.externals(&filtered_graph))
228            }
229            DependencyDirection::Reverse => {
230                let filtered_reversed_graph = NodeFiltered(Reversed(graph), &self.included);
231                EdgeDfs::new(
232                    &filtered_reversed_graph,
233                    sccs.externals(&filtered_reversed_graph),
234                )
235            }
236        };
237
238        Links {
239            graph: DebugIgnore(graph),
240            included: &self.included,
241            edge_dfs,
242            direction,
243        }
244    }
245}
246
247impl<G: GraphSpec> PartialEq for ResolveCore<G> {
248    fn eq(&self, other: &Self) -> bool {
249        if self.len != other.len {
250            return false;
251        }
252        if self.included == other.included {
253            return true;
254        }
255        // At the moment we don't normalize the capacity across self.included instances, so check
256        // the symmetric difference.
257        self.included
258            .symmetric_difference(&other.included)
259            .next()
260            .is_none()
261    }
262}
263
264impl<G: GraphSpec> Eq for ResolveCore<G> {}
265
266/// An iterator over package nodes in topological order.
267#[derive(Clone, Debug)]
268pub(super) struct Topo<'g, G: GraphSpec> {
269    node_iter: NodeIter<'g, G::Ix>,
270    included: &'g FixedBitSet,
271    remaining: usize,
272}
273
274impl<G: GraphSpec> Iterator for Topo<'_, G> {
275    type Item = NodeIndex<G::Ix>;
276
277    fn next(&mut self) -> Option<Self::Item> {
278        for ix in &mut self.node_iter {
279            if !self.included.is_visited(&ix) {
280                continue;
281            }
282            self.remaining -= 1;
283            return Some(ix);
284        }
285        None
286    }
287
288    fn size_hint(&self) -> (usize, Option<usize>) {
289        (self.remaining, Some(self.remaining))
290    }
291}
292
293impl<G: GraphSpec> ExactSizeIterator for Topo<'_, G> {
294    fn len(&self) -> usize {
295        self.remaining
296    }
297}
298
299/// An iterator over dependency links.
300#[derive(Clone, Debug)]
301#[allow(clippy::type_complexity)]
302pub(super) struct Links<'g, G: GraphSpec> {
303    graph: DebugIgnore<&'g Graph<G::Node, G::Edge, Directed, G::Ix>>,
304    included: &'g FixedBitSet,
305    edge_dfs: EdgeDfs<EdgeIndex<G::Ix>, NodeIndex<G::Ix>, FixedBitSet>,
306    direction: DependencyDirection,
307}
308
309impl<G: GraphSpec> Iterator for Links<'_, G> {
310    #[allow(clippy::type_complexity)]
311    type Item = (NodeIndex<G::Ix>, NodeIndex<G::Ix>, EdgeIndex<G::Ix>);
312
313    fn next(&mut self) -> Option<Self::Item> {
314        match self.direction {
315            DependencyDirection::Forward => {
316                let filtered = NodeFiltered(self.graph.0, self.included);
317                self.edge_dfs.next(&filtered)
318            }
319            DependencyDirection::Reverse => {
320                let filtered_reversed = NodeFiltered(Reversed(self.graph.0), self.included);
321                self.edge_dfs
322                    .next(&filtered_reversed)
323                    .map(|(source_ix, target_ix, edge_ix)| {
324                        // Flip the source and target around since this is a reversed graph, since the
325                        // 'from' and 'to' are always right way up.
326                        (target_ix, source_ix, edge_ix)
327                    })
328            }
329        }
330    }
331}
guppy/graph/resolve_core.rs

guppy/graph/
resolve_core.rs
