guppy/graph/feature/
resolve.rs

1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use std::fmt;
5
6use crate::{
7    Error, PackageId,
8    graph::{
9        DependencyDirection, FeatureGraphSpec, FeatureIx, PackageIx, PackageMetadata, PackageSet,
10        cargo::{CargoOptions, CargoSet},
11        feature::{
12            ConditionalLink, FeatureEdge, FeatureGraph, FeatureId, FeatureLinkContext,
13            FeatureLinkVisitor, FeatureList, FeatureMetadata, FeatureQuery,
14            build::{FeatureEdgeReference, FeaturePetgraph},
15            weak::WeakBufferStates,
16        },
17        resolve_core::ResolveCore,
18    },
19    petgraph_support::{IxBitSet, dfs::BufferedEdgeFilter},
20};
21use debug_ignore::DebugIgnore;
22use fixedbitset::FixedBitSet;
23use itertools::Either;
24use petgraph::{graph::NodeIndex, visit::EdgeRef};
25
26impl<'g> FeatureGraph<'g> {
27    /// Creates a new `FeatureSet` consisting of all members of this feature graph.
28    ///
29    /// This will include features that aren't depended on by any workspace packages.
30    ///
31    /// In most situations, `query_workspace().resolve()` is preferred. Use `resolve_all` if you
32    /// know you need parts of the graph that aren't accessible from the workspace.
33    pub fn resolve_all(&self) -> FeatureSet<'g> {
34        FeatureSet {
35            graph: DebugIgnore(*self),
36            core: ResolveCore::all_nodes(self.dep_graph()),
37        }
38    }
39
40    /// Creates a new, empty `FeatureSet` associated with this feature graph.
41    pub fn resolve_none(&self) -> FeatureSet<'g> {
42        FeatureSet {
43            graph: DebugIgnore(*self),
44            core: ResolveCore::empty(self.dep_graph()),
45        }
46    }
47
48    /// Creates a new `FeatureSet` consisting of the specified feature IDs.
49    ///
50    /// Returns an error if any feature IDs are unknown.
51    pub fn resolve_ids<'a>(
52        &self,
53        feature_ids: impl IntoIterator<Item = impl Into<FeatureId<'a>>>,
54    ) -> Result<FeatureSet<'g>, Error> {
55        let included: IxBitSet =
56            self.feature_ixs(feature_ids.into_iter().map(|feature| feature.into()))?;
57        Ok(FeatureSet::from_included(*self, included))
58    }
59}
60
61/// A set of feature IDs in a feature graph.
62///
63/// Created by `FeatureQuery::resolve`, the `FeatureGraph::resolve_` methods, or from
64/// `PackageSet::to_feature_set`.
65#[derive(Clone)]
66pub struct FeatureSet<'g> {
67    graph: DebugIgnore<FeatureGraph<'g>>,
68    core: ResolveCore<FeatureGraphSpec>,
69}
70
71impl fmt::Debug for FeatureSet<'_> {
72    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
73        f.debug_set()
74            .entries(self.packages_with_features(DependencyDirection::Forward))
75            .finish()
76    }
77}
78
79assert_covariant!(FeatureSet);
80
81struct FeatureEdgeFilter<'g, 'a, F> {
82    graph: FeatureGraph<'g>,
83    buffer_states: WeakBufferStates<'g, 'a, F>,
84}
85
86impl<'g, F> BufferedEdgeFilter<&'g FeaturePetgraph> for FeatureEdgeFilter<'g, '_, F>
87where
88    F: FnMut(ConditionalLink<'g>) -> bool,
89{
90    type Iter = Either<
91        std::option::IntoIter<FeatureEdgeReference<'g>>,
92        std::vec::IntoIter<FeatureEdgeReference<'g>>,
93    >;
94
95    fn filter(&mut self, edge_ref: FeatureEdgeReference<'g>) -> Self::Iter {
96        match self.graph.edge_to_links(
97            edge_ref.source(),
98            edge_ref.target(),
99            edge_ref.id(),
100            Some(edge_ref.weight()),
101        ) {
102            Some(links) => Either::Left(self.buffer_states.track(edge_ref, links).into_iter()),
103            None => {
104                // Feature links within the same package are always followed.
105                Either::Left(Some(edge_ref).into_iter())
106            }
107        }
108    }
109
110    fn discover(&mut self, feature_ix: NodeIndex<FeatureIx>) -> Self::Iter {
111        Either::Right(self.buffer_states.discover(feature_ix).into_iter())
112    }
113}
114
115impl<'g> FeatureSet<'g> {
116    pub(super) fn new(query: FeatureQuery<'g>) -> Self {
117        let graph = query.initials.graph;
118        Self {
119            graph,
120            core: ResolveCore::new(
121                graph.dep_graph(),
122                query.initials().sorted_ixs(),
123                query.direction,
124            ),
125        }
126    }
127
128    pub(super) fn with_link_visitor(
129        query: FeatureQuery<'g>,
130        mut visitor: impl FeatureLinkVisitor<'g>,
131    ) -> Self {
132        let graph = query.initials.graph;
133        let cx = FeatureLinkContext::new(query);
134
135        // State used by the callback below.
136        let buffer_states = WeakBufferStates::new(&graph.inner.weak, cx.direction(), |link| {
137            visitor.visit_link(&cx, link)
138        });
139
140        let core = ResolveCore::with_buffered_edge_filter(
141            graph.dep_graph(),
142            cx.query().initials().sorted_ixs(),
143            cx.direction(),
144            FeatureEdgeFilter {
145                graph: *graph,
146                buffer_states,
147            },
148        );
149
150        Self { graph, core }
151    }
152
153    pub(super) fn from_ixs(
154        graph: FeatureGraph<'g>,
155        feature_ixs: impl IntoIterator<Item = NodeIndex<FeatureIx>>,
156    ) -> Self {
157        Self {
158            graph: DebugIgnore(graph),
159            core: ResolveCore::from_ixs(feature_ixs, graph.dep_graph()),
160        }
161    }
162
163    pub(in crate::graph) fn from_included(
164        graph: FeatureGraph<'g>,
165        included: impl Into<FixedBitSet>,
166    ) -> Self {
167        Self {
168            graph: DebugIgnore(graph),
169            core: ResolveCore::from_included(included.into(), graph.dep_graph()),
170        }
171    }
172
173    /// Returns the `FeatureGraph` that this feature set was computed against.
174    pub fn graph(&self) -> &FeatureGraph<'g> {
175        &self.graph.0
176    }
177
178    /// Returns the number of feature IDs in this set.
179    pub fn len(&self) -> usize {
180        self.core.len()
181    }
182
183    /// Returns true if there are no feature IDs in this set.
184    pub fn is_empty(&self) -> bool {
185        self.core.is_empty()
186    }
187
188    /// Returns true if this set contains the given feature ID.
189    ///
190    /// Returns an error if this feature ID was unknown.
191    pub fn contains<'a>(&self, feature_id: impl Into<FeatureId<'a>>) -> Result<bool, Error> {
192        Ok(self.contains_ix(self.graph.feature_ix(feature_id.into())?))
193    }
194
195    /// Returns true if this set contains this package.
196    ///
197    /// Returns an error if this package ID was unknown.
198    pub fn contains_package(&self, package_id: &PackageId) -> Result<bool, Error> {
199        let package = self.graph.package_graph.metadata(package_id)?;
200        Ok(self
201            .graph
202            .feature_ixs_for_package_ix(package.package_ix())
203            .any(|feature_ix| self.core.contains(feature_ix)))
204    }
205
206    /// Creates a new `FeatureQuery` from this set in the specified direction.
207    ///
208    /// This is equivalent to constructing a query from all the feature IDs in this set.
209    pub fn to_feature_query(&self, direction: DependencyDirection) -> FeatureQuery<'g> {
210        FeatureQuery {
211            initials: self.clone(),
212            direction,
213        }
214    }
215
216    // ---
217    // Set operations
218    // ---
219
220    /// Returns a `FeatureSet` that contains all features present in at least one of `self`
221    /// and `other`.
222    ///
223    /// ## Panics
224    ///
225    /// Panics if the package graphs associated with `self` and `other` don't match.
226    pub fn union(&self, other: &Self) -> Self {
227        assert!(
228            ::std::ptr::eq(self.graph.package_graph, other.graph.package_graph),
229            "package graphs passed into union() match"
230        );
231        let mut res = self.clone();
232        res.core.union_with(&other.core);
233        res
234    }
235
236    /// Returns a `FeatureSet` that contains all features present in both `self` and `other`.
237    ///
238    /// ## Panics
239    ///
240    /// Panics if the package graphs associated with `self` and `other` don't match.
241    pub fn intersection(&self, other: &Self) -> Self {
242        assert!(
243            ::std::ptr::eq(self.graph.package_graph, other.graph.package_graph),
244            "package graphs passed into intersection() match"
245        );
246        let mut res = self.clone();
247        res.core.intersect_with(&other.core);
248        res
249    }
250
251    /// Returns a `FeatureSet` that contains all features present in `self` but not `other`.
252    ///
253    /// ## Panics
254    ///
255    /// Panics if the package graphs associated with `self` and `other` don't match.
256    pub fn difference(&self, other: &Self) -> Self {
257        assert!(
258            ::std::ptr::eq(self.graph.package_graph, other.graph.package_graph),
259            "package graphs passed into difference() match"
260        );
261        Self {
262            graph: self.graph,
263            core: self.core.difference(&other.core),
264        }
265    }
266
267    /// Returns a `FeatureSet` that contains all features present in exactly one of `self` and
268    /// `other`.
269    ///
270    /// ## Panics
271    ///
272    /// Panics if the package graphs associated with `self` and `other` don't match.
273    pub fn symmetric_difference(&self, other: &Self) -> Self {
274        assert!(
275            ::std::ptr::eq(self.graph.package_graph, other.graph.package_graph),
276            "package graphs passed into symmetric_difference() match"
277        );
278        let mut res = self.clone();
279        res.core.symmetric_difference_with(&other.core);
280        res
281    }
282
283    /// Returns a `FeatureSet` on which a filter has been applied.
284    ///
285    /// Filters out all values for which the callback returns false.
286    ///
287    /// ## Cycles
288    ///
289    /// For features within a dependency cycle, the callback will be called in non-dev order. When
290    /// the direction is forward, if feature Foo has a dependency on Bar, and Bar has a cyclic
291    /// dev-dependency on Foo, then Foo is returned before Bar.
292    pub fn filter(
293        &self,
294        direction: DependencyDirection,
295        mut callback: impl FnMut(FeatureMetadata<'g>) -> bool,
296    ) -> Self {
297        let graph = self.graph;
298        let included: IxBitSet = self
299            .features(direction)
300            .filter_map(move |feature| {
301                let feature_ix = feature.feature_ix();
302                if callback(feature) {
303                    Some(feature_ix)
304                } else {
305                    None
306                }
307            })
308            .collect();
309        Self::from_included(*graph, included)
310    }
311
312    /// Partitions this `FeatureSet` into two.
313    ///
314    /// The first `FeatureSet` contains features for which the callback returned true, and the
315    /// second one contains features for which the callback returned false.
316    ///
317    /// ## Cycles
318    ///
319    /// For features within a dependency cycle, the callback will be called in non-dev order. When
320    /// the direction is forward, if feature Foo has a dependency on Bar, and Bar has a cyclic
321    /// dev-dependency on Foo, then Foo is returned before Bar.
322    pub fn partition(
323        &self,
324        direction: DependencyDirection,
325        mut callback: impl FnMut(FeatureMetadata<'g>) -> bool,
326    ) -> (Self, Self) {
327        let graph = self.graph;
328        let mut left = IxBitSet::with_capacity(graph.dep_graph().node_count());
329        let mut right = left.clone();
330
331        self.features(direction).for_each(|feature| {
332            let feature_ix = feature.feature_ix();
333            match callback(feature) {
334                true => left.insert_node_ix(feature_ix),
335                false => right.insert_node_ix(feature_ix),
336            }
337        });
338        (
339            Self::from_included(*graph, left),
340            Self::from_included(*graph, right),
341        )
342    }
343
344    /// Performs filtering and partitioning at the same time.
345    ///
346    /// The first `FeatureSet` contains features for which the callback returned `Some(true)`, and
347    /// the second one contains features for which the callback returned `Some(false)`. Features
348    /// for which the callback returned `None` are dropped.
349    ///
350    /// ## Cycles
351    ///
352    /// For features within a dependency cycle, the callback will be called in non-dev order. When
353    /// the direction is forward, if feature Foo has a dependency on Bar, and Bar has a cyclic
354    /// dev-dependency on Foo, then Foo is returned before Bar.
355    pub fn filter_partition(
356        &self,
357        direction: DependencyDirection,
358        mut callback: impl FnMut(FeatureMetadata<'g>) -> Option<bool>,
359    ) -> (Self, Self) {
360        let graph = self.graph;
361        let mut left = IxBitSet::with_capacity(graph.dep_graph().node_count());
362        let mut right = left.clone();
363
364        self.features(direction).for_each(|feature| {
365            let feature_ix = feature.feature_ix();
366            match callback(feature) {
367                Some(true) => left.insert_node_ix(feature_ix),
368                Some(false) => right.insert_node_ix(feature_ix),
369                None => {}
370            }
371        });
372        (
373            Self::from_included(*graph, left),
374            Self::from_included(*graph, right),
375        )
376    }
377
378    // ---
379    // Queries around packages
380    // ---
381
382    /// Returns a list of features present for this package, or `None` if this package is not
383    /// present in the feature set.
384    ///
385    /// Returns an error if the package ID was unknown.
386    pub fn features_for(&self, package_id: &PackageId) -> Result<Option<FeatureList<'g>>, Error> {
387        let package = self.graph.package_graph.metadata(package_id)?;
388        Ok(self.features_for_package_impl(package))
389    }
390
391    /// Converts this `FeatureSet` into a `PackageSet` containing all packages with any selected
392    /// features (including the "base" feature).
393    pub fn to_package_set(&self) -> PackageSet<'g> {
394        let included: IxBitSet = self
395            .core
396            .included
397            .ones()
398            .map(|feature_ix| self.graph.package_ix_for_feature_ix(feature_ix))
399            .collect();
400        PackageSet::from_included(self.graph.package_graph, included.0)
401    }
402
403    // ---
404    // Cargo set creation
405    // ---
406
407    /// Converts this feature set into a Cargo set, simulating a Cargo build for it.
408    ///
409    /// The feature set is expected to be entirely within the workspace. Its behavior outside the
410    /// workspace isn't defined and may be surprising.
411    ///
412    /// Returns an error if the `CargoOptions` weren't valid in some way (for example if an omitted
413    /// package ID wasn't known to this graph.)
414    pub fn into_cargo_set(self, opts: &CargoOptions<'_>) -> Result<CargoSet<'g>, Error> {
415        let features_only = self.graph.resolve_none();
416        CargoSet::new(self, features_only, opts)
417    }
418
419    // ---
420    // Iterators
421    // ---
422
423    /// Iterates over feature IDs, in topological order in the direction specified.
424    ///
425    /// ## Cycles
426    ///
427    /// The features within a dependency cycle will be returned in non-dev order. When the direction
428    /// is forward, if feature Foo has a dependency on Bar, and Bar has a cyclic dev-dependency on
429    /// Foo, then Foo is returned before Bar.
430    pub fn feature_ids<'a>(
431        &'a self,
432        direction: DependencyDirection,
433    ) -> impl ExactSizeIterator<Item = FeatureId<'g>> + 'a {
434        let graph = self.graph;
435        self.core
436            .topo(graph.sccs(), direction)
437            .map(move |feature_ix| {
438                FeatureId::from_node(graph.package_graph(), &graph.dep_graph()[feature_ix])
439            })
440    }
441
442    /// Iterates over feature metadatas, in topological order in the direction specified.
443    ///
444    /// ## Cycles
445    ///
446    /// The features within a dependency cycle will be returned in non-dev order. When the direction
447    /// is forward, if feature Foo has a dependency on Bar, and Bar has a cyclic dev-dependency on
448    /// Foo, then Foo is returned before Bar.
449    pub fn features<'a>(
450        &'a self,
451        direction: DependencyDirection,
452    ) -> impl ExactSizeIterator<Item = FeatureMetadata<'g>> + 'a {
453        let graph = self.graph;
454        self.core
455            .topo(graph.sccs(), direction)
456            .map(move |feature_ix| {
457                graph
458                    .metadata_for_node(graph.dep_graph()[feature_ix])
459                    .expect("feature node should be known")
460            })
461    }
462
463    /// Iterates over package metadatas and their corresponding features, in topological order in
464    /// the direction specified.
465    ///
466    /// ## Cycles
467    ///
468    /// The packages within a dependency cycle will be returned in non-dev order. When the direction
469    /// is forward, if package Foo has a dependency on Bar, and Bar has a cyclic dev-dependency on
470    /// Foo, then Foo is returned before Bar.
471    pub fn packages_with_features<'a>(
472        &'a self,
473        direction: DependencyDirection,
474    ) -> impl Iterator<Item = FeatureList<'g>> + 'a {
475        let package_graph = self.graph.package_graph;
476
477        // Use the package graph's SCCs for the topo order guarantee.
478        package_graph
479            .sccs()
480            .node_iter(direction.into())
481            .filter_map(move |package_ix| {
482                let package_id = &package_graph.dep_graph()[package_ix];
483                let package = package_graph
484                    .metadata(package_id)
485                    .expect("valid package ID");
486                self.features_for_package_impl(package)
487            })
488    }
489
490    /// Returns the set of "root feature" IDs in the specified direction.
491    ///
492    /// * If direction is Forward, return the set of feature IDs that do not have any dependencies
493    ///   within the selected graph.
494    /// * If direction is Reverse, return the set of feature IDs that do not have any dependents
495    ///   within the selected graph.
496    ///
497    /// ## Cycles
498    ///
499    /// If a root consists of a dependency cycle, all the features in it will be returned in
500    /// non-dev order (when the direction is forward).
501    pub fn root_ids<'a>(
502        &'a self,
503        direction: DependencyDirection,
504    ) -> impl ExactSizeIterator<Item = FeatureId<'g>> + 'a {
505        let dep_graph = self.graph.dep_graph();
506        let package_graph = self.graph.package_graph;
507        self.core
508            .roots(dep_graph, self.graph.sccs(), direction)
509            .into_iter()
510            .map(move |feature_ix| FeatureId::from_node(package_graph, &dep_graph[feature_ix]))
511    }
512
513    /// Returns the set of "root feature" metadatas in the specified direction.
514    ///
515    /// * If direction is Forward, return the set of metadatas that do not have any dependencies
516    ///   within the selected graph.
517    /// * If direction is Reverse, return the set of metadatas that do not have any dependents
518    ///   within the selected graph.
519    ///
520    /// ## Cycles
521    ///
522    /// If a root consists of a dependency cycle, all the features in it will be returned in
523    /// non-dev order (when the direction is forward).
524    pub fn root_features<'a>(
525        &'a self,
526        direction: DependencyDirection,
527    ) -> impl Iterator<Item = FeatureMetadata<'g>> + 'a {
528        let feature_graph = self.graph;
529        self.core
530            .roots(feature_graph.dep_graph(), feature_graph.sccs(), direction)
531            .into_iter()
532            .map(move |feature_ix| {
533                feature_graph
534                    .metadata_for_node(feature_graph.dep_graph()[feature_ix])
535                    .expect("feature node should be known")
536            })
537    }
538
539    /// Creates an iterator over `ConditionalLink` instances in the direction specified.
540    ///
541    /// ## Cycles
542    ///
543    /// The links in a dependency cycle will be returned in non-dev order. When the direction is
544    /// forward, if feature Foo has a dependency on Bar, and Bar has a cyclic dev-dependency on Foo,
545    /// then the link Foo -> Bar is returned before the link Bar -> Foo.
546    pub fn conditional_links<'a>(
547        &'a self,
548        direction: DependencyDirection,
549    ) -> impl Iterator<Item = ConditionalLink<'g>> + 'a {
550        let graph = self.graph;
551        self.core
552            .links(graph.dep_graph(), graph.sccs(), direction)
553            .filter_map(move |(source_ix, target_ix, edge_ix)| {
554                graph.edge_to_full_link(source_ix, target_ix, edge_ix, None)
555            })
556    }
557
558    // ---
559    // Helper methods
560    // ---
561
562    fn features_for_package_impl<'a>(
563        &'a self,
564        package: PackageMetadata<'g>,
565    ) -> Option<FeatureList<'g>> {
566        let dep_graph = self.graph.dep_graph();
567        let core = &self.core;
568
569        let mut features = self
570            .graph
571            .feature_ixs_for_package_ix(package.package_ix())
572            .filter_map(|feature_ix| {
573                if core.contains(feature_ix) {
574                    Some(FeatureId::node_to_feature(package, &dep_graph[feature_ix]))
575                } else {
576                    None
577                }
578            })
579            .peekable();
580        if features.peek().is_some() {
581            // At least one feature was returned.
582            Some(FeatureList::new(package, features))
583        } else {
584            None
585        }
586    }
587
588    /// Returns all the feature ixs in ascending index order.
589    pub(in crate::graph) fn sorted_ixs(&self) -> impl Iterator<Item = NodeIndex<FeatureIx>> + '_ {
590        self.core.included.ones()
591    }
592
593    pub(in crate::graph) fn contains_ix(&self, feature_ix: NodeIndex<FeatureIx>) -> bool {
594        self.core.contains(feature_ix)
595    }
596
597    /// Returns true if this feature set contains the given package ix.
598    #[allow(dead_code)]
599    pub(in crate::graph) fn contains_package_ix(&self, package_ix: NodeIndex<PackageIx>) -> bool {
600        self.graph
601            .feature_ixs_for_package_ix(package_ix)
602            .any(|feature_ix| self.core.contains(feature_ix))
603    }
604
605    // Currently a helper for debugging -- will be made public in the future.
606    #[doc(hidden)]
607    pub fn links<'a>(
608        &'a self,
609        direction: DependencyDirection,
610    ) -> impl Iterator<Item = (FeatureId<'g>, FeatureId<'g>, &'g FeatureEdge)> + 'a {
611        let feature_graph = self.graph;
612
613        self.core
614            .links(feature_graph.dep_graph(), feature_graph.sccs(), direction)
615            .map(move |(source_ix, target_ix, edge_ix)| {
616                (
617                    FeatureId::from_node(
618                        feature_graph.package_graph(),
619                        &feature_graph.dep_graph()[source_ix],
620                    ),
621                    FeatureId::from_node(
622                        feature_graph.package_graph(),
623                        &feature_graph.dep_graph()[target_ix],
624                    ),
625                    &feature_graph.dep_graph()[edge_ix],
626                )
627            })
628    }
629}
630
631impl PartialEq for FeatureSet<'_> {
632    fn eq(&self, other: &Self) -> bool {
633        ::std::ptr::eq(self.graph.package_graph, other.graph.package_graph)
634            && self.core == other.core
635    }
636}
637
638impl Eq for FeatureSet<'_> {}
guppy/graph/feature/resolve.rs

guppy/graph/feature/
resolve.rs
