guppy/graph/
resolve.rs

Help
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        feature::{FeatureFilter, FeatureSet},
8        resolve_core::{ResolveCore, Topo},
9        DependencyDirection, PackageGraph, PackageIx, PackageLink, PackageLinkImpl,
10        PackageMetadata, PackageQuery,
11    },
12    petgraph_support::{
13        dot::{DotFmt, DotVisitor, DotWrite},
14        edge_ref::GraphEdgeRef,
15        IxBitSet,
16    },
17    sorted_set::SortedSet,
18    Error, PackageId,
19};
20use camino::Utf8Path;
21use fixedbitset::FixedBitSet;
22use petgraph::{
23    prelude::*,
24    visit::{NodeFiltered, NodeRef},
25};
26use std::fmt;
27
28impl PackageGraph {
29    /// Creates a new `PackageSet` consisting of all members of this package graph.
30    ///
31    /// This is normally the same as `query_workspace().resolve()`, but can differ if packages have
32    /// been replaced with `[patch]` or `[replace]`.
33    ///
34    /// In most situations, `query_workspace` is preferred. Use `resolve_all` if you know you need
35    /// parts of the graph that aren't accessible from the workspace.
36    pub fn resolve_all(&self) -> PackageSet {
37        PackageSet {
38            graph: DebugIgnore(self),
39            core: ResolveCore::all_nodes(&self.dep_graph),
40        }
41    }
42
43    /// Creates a new, empty `PackageSet` associated with this package graph.
44    pub fn resolve_none(&self) -> PackageSet {
45        PackageSet {
46            graph: DebugIgnore(self),
47            core: ResolveCore::empty(),
48        }
49    }
50
51    /// Creates a new `PackageSet` consisting of the specified package IDs.
52    ///
53    /// This does not include transitive dependencies. To do so, use the `query_` methods.
54    ///
55    /// Returns an error if any package IDs are unknown.
56    pub fn resolve_ids<'a>(
57        &self,
58        package_ids: impl IntoIterator<Item = &'a PackageId>,
59    ) -> Result<PackageSet, Error> {
60        Ok(PackageSet {
61            graph: DebugIgnore(self),
62            core: ResolveCore::from_included::<IxBitSet>(self.package_ixs(package_ids)?),
63        })
64    }
65
66    /// Creates a new `PackageSet` consisting of all packages in this workspace.
67    ///
68    /// This does not include transitive dependencies. To do so, use `query_workspace`.
69    pub fn resolve_workspace(&self) -> PackageSet {
70        let included: IxBitSet = self
71            .workspace()
72            .iter_by_path()
73            .map(|(_, package)| package.package_ix())
74            .collect();
75        PackageSet {
76            graph: DebugIgnore(self),
77            core: ResolveCore::from_included(included),
78        }
79    }
80
81    /// Creates a new `PackageSet` consisting of the specified workspace packages by path.
82    ///
83    /// This does not include transitive dependencies. To do so, use `query_workspace_paths`.
84    ///
85    /// Returns an error if any workspace paths are unknown.
86    pub fn resolve_workspace_paths(
87        &self,
88        paths: impl IntoIterator<Item = impl AsRef<Utf8Path>>,
89    ) -> Result<PackageSet, Error> {
90        let workspace = self.workspace();
91        let included: IxBitSet = paths
92            .into_iter()
93            .map(|path| {
94                workspace
95                    .member_by_path(path.as_ref())
96                    .map(|package| package.package_ix())
97            })
98            .collect::<Result<_, Error>>()?;
99        Ok(PackageSet {
100            graph: DebugIgnore(self),
101            core: ResolveCore::from_included(included),
102        })
103    }
104
105    /// Creates a new `PackageSet` consisting of the specified workspace packages by name.
106    ///
107    /// This does not include transitive dependencies. To do so, use `query_workspace_names`.
108    ///
109    /// Returns an error if any workspace names are unknown.
110    pub fn resolve_workspace_names(
111        &self,
112        names: impl IntoIterator<Item = impl AsRef<str>>,
113    ) -> Result<PackageSet, Error> {
114        let workspace = self.workspace();
115        let included: IxBitSet = names
116            .into_iter()
117            .map(|name| {
118                workspace
119                    .member_by_name(name.as_ref())
120                    .map(|package| package.package_ix())
121            })
122            .collect::<Result<_, _>>()?;
123        Ok(PackageSet {
124            graph: DebugIgnore(self),
125            core: ResolveCore::from_included(included),
126        })
127    }
128
129    /// Creates a new `PackageSet` consisting of packages with the given name.
130    ///
131    /// The result is empty if there are no packages with the given name.
132    pub fn resolve_package_name(&self, name: impl AsRef<str>) -> PackageSet {
133        // Turns out that for reasonably-sized graphs, a linear search across package names is
134        // extremely fast: much faster than trying to do something fancy like use an FST or trie.
135        //
136        // TODO: optimize this in the future, possibly through some sort of hashmap variant that
137        // doesn't require a borrow.
138        let name = name.as_ref();
139        let included: IxBitSet = self
140            .packages()
141            .filter_map(|package| {
142                if package.name() == name {
143                    Some(package.package_ix())
144                } else {
145                    None
146                }
147            })
148            .collect();
149        PackageSet::from_included(self, included)
150    }
151}
152
153/// A set of resolved packages in a package graph.
154///
155/// Created by `PackageQuery::resolve`.
156#[derive(Clone, Debug)]
157pub struct PackageSet<'g> {
158    graph: DebugIgnore<&'g PackageGraph>,
159    core: ResolveCore<PackageGraph>,
160}
161
162assert_covariant!(PackageSet);
163
164impl<'g> PackageSet<'g> {
165    pub(super) fn new(query: PackageQuery<'g>) -> Self {
166        let graph = query.graph;
167        Self {
168            graph: DebugIgnore(graph),
169            core: ResolveCore::new(graph.dep_graph(), query.params),
170        }
171    }
172
173    pub(super) fn from_included(graph: &'g PackageGraph, included: impl Into<FixedBitSet>) -> Self {
174        Self {
175            graph: DebugIgnore(graph),
176            core: ResolveCore::from_included(included),
177        }
178    }
179
180    pub(super) fn with_resolver(
181        query: PackageQuery<'g>,
182        mut resolver: impl PackageResolver<'g>,
183    ) -> Self {
184        let graph = query.graph;
185        let params = query.params.clone();
186        Self {
187            graph: DebugIgnore(graph),
188            core: ResolveCore::with_edge_filter(graph.dep_graph(), params, |edge| {
189                let link = graph.edge_ref_to_link(edge);
190                resolver.accept(&query, link)
191            }),
192        }
193    }
194
195    /// Returns the number of packages in this set.
196    pub fn len(&self) -> usize {
197        self.core.len()
198    }
199
200    /// Returns true if no packages were resolved in this set.
201    pub fn is_empty(&self) -> bool {
202        self.core.is_empty()
203    }
204
205    /// Returns true if this package ID is contained in this resolve set.
206    ///
207    /// Returns an error if the package ID is unknown.
208    pub fn contains(&self, package_id: &PackageId) -> Result<bool, Error> {
209        Ok(self.contains_ix(self.graph.package_ix(package_id)?))
210    }
211
212    /// Creates a new `PackageQuery` from this set in the specified direction.
213    ///
214    /// This is equivalent to constructing a query from all the `package_ids`.
215    pub fn to_package_query(&self, direction: DependencyDirection) -> PackageQuery<'g> {
216        let package_ixs = SortedSet::new(
217            self.core
218                .included
219                .ones()
220                .map(NodeIndex::new)
221                .collect::<Vec<_>>(),
222        );
223        self.graph.query_from_parts(package_ixs, direction)
224    }
225
226    // ---
227    // Set operations
228    // ---
229
230    /// Returns a `PackageSet` that contains all packages present in at least one of `self`
231    /// and `other`.
232    ///
233    /// ## Panics
234    ///
235    /// Panics if the package graphs associated with `self` and `other` don't match.
236    pub fn union(&self, other: &Self) -> Self {
237        assert!(
238            ::std::ptr::eq(self.graph.0, other.graph.0),
239            "package graphs passed into union() match"
240        );
241        let mut res = self.clone();
242        res.core.union_with(&other.core);
243        res
244    }
245
246    /// Returns a `PackageSet` that contains all packages present in both `self` and `other`.
247    ///
248    /// ## Panics
249    ///
250    /// Panics if the package graphs associated with `self` and `other` don't match.
251    pub fn intersection(&self, other: &Self) -> Self {
252        assert!(
253            ::std::ptr::eq(self.graph.0, other.graph.0),
254            "package graphs passed into intersection() match"
255        );
256        let mut res = self.clone();
257        res.core.intersect_with(&other.core);
258        res
259    }
260
261    /// Returns a `PackageSet` that contains all packages present in `self` but not `other`.
262    ///
263    /// ## Panics
264    ///
265    /// Panics if the package graphs associated with `self` and `other` don't match.
266    pub fn difference(&self, other: &Self) -> Self {
267        assert!(
268            ::std::ptr::eq(self.graph.0, other.graph.0),
269            "package graphs passed into difference() match"
270        );
271        Self {
272            graph: self.graph,
273            core: self.core.difference(&other.core),
274        }
275    }
276
277    /// Returns a `PackageSet` that contains all packages present in exactly one of `self` and
278    /// `other`.
279    ///
280    /// ## Panics
281    ///
282    /// Panics if the package graphs associated with `self` and `other` don't match.
283    pub fn symmetric_difference(&self, other: &Self) -> Self {
284        assert!(
285            ::std::ptr::eq(self.graph.0, other.graph.0),
286            "package graphs passed into symmetric_difference() match"
287        );
288        let mut res = self.clone();
289        res.core.symmetric_difference_with(&other.core);
290        res
291    }
292
293    /// Returns a `PackageSet` on which a filter has been applied.
294    ///
295    /// Filters out all values for which the callback returns false.
296    ///
297    /// ## Cycles
298    ///
299    /// For packages within a dependency cycle, the callback will be called in non-dev order. When
300    /// the direction is forward, if package Foo has a dependency on Bar, and Bar has a cyclic
301    /// dev-dependency on Foo, then Foo is returned before Bar.
302    pub fn filter(
303        &self,
304        direction: DependencyDirection,
305        mut callback: impl FnMut(PackageMetadata<'g>) -> bool,
306    ) -> Self {
307        let graph = *self.graph;
308        let included: IxBitSet = self
309            .packages(direction)
310            .filter_map(move |package| {
311                let package_ix = package.package_ix();
312                if callback(package) {
313                    Some(package_ix)
314                } else {
315                    None
316                }
317            })
318            .collect();
319        Self::from_included(graph, included)
320    }
321
322    /// Partitions this `PackageSet` into two.
323    ///
324    /// The first `PackageSet` contains packages for which the callback returned true, and the
325    /// second one contains packages for which the callback returned false.
326    ///
327    /// ## Cycles
328    ///
329    /// For packages within a dependency cycle, the callback will be called in non-dev order. When
330    /// the direction is forward, if package Foo has a dependency on Bar, and Bar has a cyclic
331    /// dev-dependency on Foo, then Foo is returned before Bar.
332    pub fn partition(
333        &self,
334        direction: DependencyDirection,
335        mut callback: impl FnMut(PackageMetadata<'g>) -> bool,
336    ) -> (Self, Self) {
337        let graph = *self.graph;
338        let mut left = IxBitSet::with_capacity(self.core.included.len());
339        let mut right = left.clone();
340
341        self.packages(direction).for_each(|package| {
342            let package_ix = package.package_ix();
343            match callback(package) {
344                true => left.insert_node_ix(package_ix),
345                false => right.insert_node_ix(package_ix),
346            }
347        });
348        (
349            Self::from_included(graph, left),
350            Self::from_included(graph, right),
351        )
352    }
353
354    /// Performs filtering and partitioning at the same time.
355    ///
356    /// The first `PackageSet` contains packages for which the callback returned `Some(true)`, and
357    /// the second one contains packages for which the callback returned `Some(false)`. Packages
358    /// for which the callback returned `None` are dropped.
359    ///
360    /// ## Cycles
361    ///
362    /// For packages within a dependency cycle, the callback will be called in non-dev order. When
363    /// the direction is forward, if package Foo has a dependency on Bar, and Bar has a cyclic
364    /// dev-dependency on Foo, then Foo is returned before Bar.
365    pub fn filter_partition(
366        &self,
367        direction: DependencyDirection,
368        mut callback: impl FnMut(PackageMetadata<'g>) -> Option<bool>,
369    ) -> (Self, Self) {
370        let graph = *self.graph;
371        let mut left = IxBitSet::with_capacity(self.core.included.len());
372        let mut right = left.clone();
373
374        self.packages(direction).for_each(|package| {
375            let package_ix = package.package_ix();
376            match callback(package) {
377                Some(true) => left.insert_node_ix(package_ix),
378                Some(false) => right.insert_node_ix(package_ix),
379                None => {}
380            }
381        });
382        (
383            Self::from_included(graph, left),
384            Self::from_included(graph, right),
385        )
386    }
387
388    // ---
389    // Conversion to FeatureSet
390    // ---
391
392    /// Creates a new `FeatureSet` consisting of all packages in this `PackageSet`, using the given
393    /// feature filter.
394    ///
395    /// This will cause the feature graph to be constructed if it hasn't been done so already.
396    pub fn to_feature_set(&self, filter: impl FeatureFilter<'g>) -> FeatureSet<'g> {
397        let feature_graph = self.graph.feature_graph();
398        let included: IxBitSet = feature_graph.feature_ixs_for_package_ixs_filtered(
399            // The direction of iteration doesn't matter.
400            self.ixs(DependencyDirection::Forward),
401            filter,
402        );
403        FeatureSet::from_included(feature_graph, included)
404    }
405
406    // ---
407    // Iterators
408    // ---
409
410    /// Iterates over package IDs, in topological order in the direction specified.
411    ///
412    /// ## Cycles
413    ///
414    /// The packages within a dependency cycle will be returned in non-dev order. When the direction
415    /// is forward, if package Foo has a dependency on Bar, and Bar has a cyclic dev-dependency on
416    /// Foo, then Foo is returned before Bar.
417    pub fn package_ids<'a>(
418        &'a self,
419        direction: DependencyDirection,
420    ) -> impl ExactSizeIterator<Item = &'g PackageId> + 'a {
421        let graph = self.graph;
422        self.core
423            .topo(self.graph.sccs(), direction)
424            .map(move |package_ix| &graph.dep_graph[package_ix])
425    }
426
427    pub(super) fn ixs(&'g self, direction: DependencyDirection) -> Topo<'g, PackageGraph> {
428        self.core.topo(self.graph.sccs(), direction)
429    }
430
431    /// Iterates over package metadatas, in topological order in the direction specified.
432    ///
433    /// ## Cycles
434    ///
435    /// The packages within a dependency cycle will be returned in non-dev order. When the direction
436    /// is forward, if package Foo has a dependency on Bar, and Bar has a cyclic dev-dependency on
437    /// Foo, then Foo is returned before Bar.
438    pub fn packages<'a>(
439        &'a self,
440        direction: DependencyDirection,
441    ) -> impl ExactSizeIterator<Item = PackageMetadata<'g>> + 'a {
442        let graph = self.graph;
443        self.package_ids(direction)
444            .map(move |package_id| graph.metadata(package_id).expect("known package IDs"))
445    }
446
447    /// Returns the set of "root package" IDs in the specified direction.
448    ///
449    /// * If direction is Forward, return the set of packages that do not have any dependencies
450    ///   within the selected graph.
451    /// * If direction is Reverse, return the set of packages that do not have any dependents within
452    ///   the selected graph.
453    ///
454    /// ## Cycles
455    ///
456    /// If a root consists of a dependency cycle, all the packages in it will be returned in
457    /// non-dev order (when the direction is forward).
458    pub fn root_ids<'a>(
459        &'a self,
460        direction: DependencyDirection,
461    ) -> impl ExactSizeIterator<Item = &'g PackageId> + 'a {
462        let dep_graph = &self.graph.dep_graph;
463        self.core
464            .roots(self.graph.dep_graph(), self.graph.sccs(), direction)
465            .into_iter()
466            .map(move |package_ix| &dep_graph[package_ix])
467    }
468
469    /// Returns the set of "root package" metadatas in the specified direction.
470    ///
471    /// * If direction is Forward, return the set of packages that do not have any dependencies
472    ///   within the selected graph.
473    /// * If direction is Reverse, return the set of packages that do not have any dependents within
474    ///   the selected graph.
475    ///
476    /// ## Cycles
477    ///
478    /// If a root consists of a dependency cycle, all the packages in it will be returned in
479    /// non-dev order (when the direction is forward).
480    pub fn root_packages<'a>(
481        &'a self,
482        direction: DependencyDirection,
483    ) -> impl ExactSizeIterator<Item = PackageMetadata<'g>> + 'a {
484        let package_graph = self.graph;
485        self.core
486            .roots(self.graph.dep_graph(), self.graph.sccs(), direction)
487            .into_iter()
488            .map(move |package_ix| {
489                package_graph
490                    .metadata(&package_graph.dep_graph[package_ix])
491                    .expect("invalid node index")
492            })
493    }
494
495    /// Creates an iterator over `PackageLink` instances.
496    ///
497    /// If the iteration is in forward order, for any given package, at least one link where the
498    /// package is on the `to` end is returned before any links where the package is on the
499    /// `from` end.
500    ///
501    /// If the iteration is in reverse order, for any given package, at least one link where the
502    /// package is on the `from` end is returned before any links where the package is on the `to`
503    /// end.
504    ///
505    /// ## Cycles
506    ///
507    /// The links in a dependency cycle will be returned in non-dev order. When the direction is
508    /// forward, if package Foo has a dependency on Bar, and Bar has a cyclic dev-dependency on Foo,
509    /// then the link Foo -> Bar is returned before the link Bar -> Foo.
510    pub fn links<'a>(
511        &'a self,
512        direction: DependencyDirection,
513    ) -> impl Iterator<Item = PackageLink<'g>> + 'a {
514        let graph = self.graph.0;
515        self.core
516            .links(graph.dep_graph(), graph.sccs(), direction)
517            .map(move |(source_ix, target_ix, edge_ix)| {
518                PackageLink::new(graph, source_ix, target_ix, edge_ix, None)
519            })
520    }
521
522    /// Constructs a representation of the selected packages in `dot` format.
523    pub fn display_dot<'a, V: PackageDotVisitor + 'g>(
524        &'a self,
525        visitor: V,
526    ) -> impl fmt::Display + 'a {
527        let node_filtered = NodeFiltered(self.graph.dep_graph(), &self.core.included);
528        DotFmt::new(node_filtered, VisitorWrap::new(self.graph.0, visitor))
529    }
530
531    // ---
532    // Helper methods
533    // ---
534
535    /// Returns all the package ixs without topologically sorting them.
536    #[allow(dead_code)]
537    pub(super) fn ixs_unordered(&self) -> impl Iterator<Item = NodeIndex<PackageIx>> + '_ {
538        self.core.included.ones().map(NodeIndex::new)
539    }
540
541    pub(super) fn contains_ix(&self, package_ix: NodeIndex<PackageIx>) -> bool {
542        self.core.contains(package_ix)
543    }
544}
545
546impl PartialEq for PackageSet<'_> {
547    fn eq(&self, other: &Self) -> bool {
548        ::std::ptr::eq(self.graph.0, other.graph.0) && self.core == other.core
549    }
550}
551
552impl Eq for PackageSet<'_> {}
553
554/// Represents whether a particular link within a package graph should be followed during a
555/// resolve operation.
556pub trait PackageResolver<'g> {
557    /// Returns true if this link should be followed during a resolve operation.
558    ///
559    /// Returning false does not prevent the `to` package (or `from` package with `query_reverse`)
560    /// from being included if it's reachable through other means.
561    fn accept(&mut self, query: &PackageQuery<'g>, link: PackageLink<'g>) -> bool;
562}
563
564impl<'g, T> PackageResolver<'g> for &mut T
565where
566    T: PackageResolver<'g>,
567{
568    fn accept(&mut self, query: &PackageQuery<'g>, link: PackageLink<'g>) -> bool {
569        (**self).accept(query, link)
570    }
571}
572
573impl<'g> PackageResolver<'g> for Box<dyn PackageResolver<'g> + '_> {
574    fn accept(&mut self, query: &PackageQuery<'g>, link: PackageLink<'g>) -> bool {
575        (**self).accept(query, link)
576    }
577}
578
579impl<'g> PackageResolver<'g> for &mut dyn PackageResolver<'g> {
580    fn accept(&mut self, query: &PackageQuery<'g>, link: PackageLink<'g>) -> bool {
581        (**self).accept(query, link)
582    }
583}
584
585pub(super) struct ResolverFn<F>(pub(super) F);
586
587impl<'g, F> PackageResolver<'g> for ResolverFn<F>
588where
589    F: FnMut(&PackageQuery<'g>, PackageLink<'g>) -> bool,
590{
591    fn accept(&mut self, query: &PackageQuery<'g>, link: PackageLink<'g>) -> bool {
592        (self.0)(query, link)
593    }
594}
595
596/// A visitor used for formatting `dot` graphs.
597pub trait PackageDotVisitor {
598    /// Visits this package. The implementation may output a label for this package to the given
599    /// `DotWrite`.
600    fn visit_package(&self, package: PackageMetadata<'_>, f: &mut DotWrite<'_, '_>) -> fmt::Result;
601
602    /// Visits this dependency link. The implementation may output a label for this link to the
603    /// given `DotWrite`.
604    fn visit_link(&self, link: PackageLink<'_>, f: &mut DotWrite<'_, '_>) -> fmt::Result;
605}
606
607struct VisitorWrap<'g, V> {
608    graph: &'g PackageGraph,
609    inner: V,
610}
611
612impl<'g, V> VisitorWrap<'g, V> {
613    fn new(graph: &'g PackageGraph, inner: V) -> Self {
614        Self { graph, inner }
615    }
616}
617
618impl<'g, V, NR, ER> DotVisitor<NR, ER> for VisitorWrap<'g, V>
619where
620    V: PackageDotVisitor,
621    NR: NodeRef<NodeId = NodeIndex<PackageIx>, Weight = PackageId>,
622    ER: GraphEdgeRef<'g, PackageLinkImpl, PackageIx>,
623{
624    fn visit_node(&self, node: NR, f: &mut DotWrite<'_, '_>) -> fmt::Result {
625        let metadata = self
626            .graph
627            .metadata(node.weight())
628            .expect("visited node should have associated metadata");
629        self.inner.visit_package(metadata, f)
630    }
631
632    fn visit_edge(&self, edge: ER, f: &mut DotWrite<'_, '_>) -> fmt::Result {
633        let link = self.graph.edge_ref_to_link(edge.into_edge_reference());
634        self.inner.visit_link(link, f)
635    }
636}
guppy/graph/resolve.rs

guppy/graph/
resolve.rs
