guppy/graph/
resolve.rs

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

guppy/graph/
resolve.rs
