guppy/graph/feature/
resolve.rs

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

guppy/graph/feature/
resolve.rs
