fixtures/
dep_helpers.rs

1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use crate::details::PackageDetails;
5use guppy::{
6    DependencyKind, Error, PackageId,
7    graph::{
8        DependencyDirection, DependencyReq, PackageGraph, PackageLink, PackageLinkPtrs,
9        PackageMetadata, PackageQuery, PackageSet,
10        feature::{FeatureGraph, FeatureId, FeatureMetadata, FeatureQuery, FeatureSet},
11    },
12    platform::PlatformSpec,
13};
14use pretty_assertions::assert_eq;
15use std::{
16    collections::{BTreeSet, HashSet},
17    fmt,
18    hash::Hash,
19    iter,
20};
21
22fn __from_metadata<'a>(link: &PackageLink<'a>) -> PackageMetadata<'a> {
23    link.from()
24}
25fn __to_metadata<'a>(link: &PackageLink<'a>) -> PackageMetadata<'a> {
26    link.to()
27}
28type LinkToMetadata<'a> = fn(&PackageLink<'a>) -> PackageMetadata<'a>;
29
30/// Some of the messages are different based on whether we're testing forward deps or reverse
31/// ones. For forward deps, we use the terms "known" for 'from' and "variable" for 'to'. For
32/// reverse deps it's the other way round.
33#[derive(Clone, Copy)]
34pub struct DirectionDesc<'a> {
35    direction_desc: &'static str,
36    known_desc: &'static str,
37    variable_desc: &'static str,
38    known_metadata: LinkToMetadata<'a>,
39    variable_metadata: LinkToMetadata<'a>,
40}
41
42impl<'a> DirectionDesc<'a> {
43    fn new(direction: DependencyDirection) -> Self {
44        match direction {
45            DependencyDirection::Forward => Self::forward(),
46            DependencyDirection::Reverse => Self::reverse(),
47        }
48    }
49
50    fn forward() -> Self {
51        Self {
52            direction_desc: "forward",
53            known_desc: "from",
54            variable_desc: "to",
55            known_metadata: __from_metadata as LinkToMetadata<'a>,
56            variable_metadata: __to_metadata as LinkToMetadata<'a>,
57        }
58    }
59
60    fn reverse() -> Self {
61        Self {
62            direction_desc: "reverse",
63            known_desc: "to",
64            variable_desc: "from",
65            known_metadata: __to_metadata as LinkToMetadata<'a>,
66            variable_metadata: __from_metadata as LinkToMetadata<'a>,
67        }
68    }
69
70    fn known_metadata(&self, dep: &PackageLink<'a>) -> PackageMetadata<'a> {
71        (self.known_metadata)(dep)
72    }
73
74    fn variable_metadata(&self, dep: &PackageLink<'a>) -> PackageMetadata<'a> {
75        (self.variable_metadata)(dep)
76    }
77}
78
79impl From<DependencyDirection> for DirectionDesc<'_> {
80    fn from(direction: DependencyDirection) -> Self {
81        Self::new(direction)
82    }
83}
84
85pub(crate) fn assert_deps_internal(
86    graph: &PackageGraph,
87    direction: DependencyDirection,
88    known_details: &PackageDetails,
89    msg: &str,
90) {
91    let desc = DirectionDesc::new(direction);
92
93    // Compare (dep_name, resolved_name, id) triples.
94    let expected_dep_ids: Vec<_> = known_details
95        .deps(direction)
96        .unwrap_or_else(|| {
97            panic!(
98                "{}: {} dependencies must be present",
99                msg, desc.direction_desc
100            )
101        })
102        .iter()
103        .map(|(dep_name, id)| (*dep_name, dep_name.replace('-', "_"), id))
104        .collect();
105    let actual_deps: Vec<_> = graph
106        .metadata(known_details.id())
107        .unwrap_or_else(|err| panic!("{msg}: {err}"))
108        .direct_links_directed(direction)
109        .collect();
110    let mut actual_dep_ids: Vec<_> = actual_deps
111        .iter()
112        .map(|link| {
113            (
114                link.dep_name(),
115                link.resolved_name().to_string(),
116                desc.variable_metadata(link).id(),
117            )
118        })
119        .collect();
120    actual_dep_ids.sort();
121    assert_eq!(
122        expected_dep_ids, actual_dep_ids,
123        "{}: expected {} dependencies",
124        msg, desc.direction_desc,
125    );
126
127    for (_, _, dep_id) in &actual_dep_ids {
128        // depends_on should agree with the dependencies returned.
129        graph.assert_depends_on(known_details.id(), dep_id, direction, msg);
130        graph.assert_directly_depends_on(known_details.id(), dep_id, direction, msg);
131    }
132
133    // Check that the dependency metadata returned is consistent with what we expect.
134    let known_msg = format!(
135        "{}: {} dependency edge {} this package",
136        msg, desc.direction_desc, desc.known_desc
137    );
138    for actual_dep in &actual_deps {
139        known_details.assert_metadata(desc.known_metadata(actual_dep), &known_msg);
140        // XXX maybe compare version requirements?
141    }
142}
143
144pub(crate) fn assert_transitive_deps_internal(
145    graph: &PackageGraph,
146    direction: DependencyDirection,
147    known_details: &PackageDetails,
148    msg: &str,
149) {
150    let desc = DirectionDesc::new(direction);
151
152    let expected_dep_ids = known_details.transitive_deps(direction).unwrap_or_else(|| {
153        panic!(
154            "{}: {} transitive dependencies must be present",
155            msg, desc.direction_desc
156        )
157    });
158
159    let query = graph
160        .query_directed(iter::once(known_details.id()), direction)
161        .unwrap_or_else(|err| {
162            panic!(
163                "{}: {} transitive dep query failed: {}",
164                msg, desc.direction_desc, err
165            )
166        });
167    let package_set = query.resolve();
168
169    let package_ids = package_set.package_ids(direction);
170    let mut actual_dep_ids: Vec<_> = package_ids.collect();
171    actual_dep_ids.sort();
172
173    let actual_deps: Vec<_> = package_set.links(direction).collect();
174    let actual_ptrs = dep_link_ptrs(actual_deps.iter().copied());
175
176    // Use a BTreeSet for unique identifiers. This is also used later for set operations.
177    let ids_from_links_set: BTreeSet<_> = actual_deps
178        .iter()
179        .flat_map(|link| vec![link.from().id(), link.to().id()])
180        .collect();
181    let ids_from_links: Vec<_> = ids_from_links_set.iter().copied().collect();
182
183    assert_eq!(
184        expected_dep_ids,
185        actual_dep_ids.as_slice(),
186        "{}: expected {} transitive dependency IDs",
187        msg,
188        desc.direction_desc
189    );
190    assert_eq!(
191        expected_dep_ids,
192        ids_from_links.as_slice(),
193        "{}: expected {} transitive dependency infos",
194        msg,
195        desc.direction_desc
196    );
197
198    // The order requirements are weaker than topological -- for forward queries, a dep should show
199    // up at least once in 'to' before it ever shows up in 'from'.
200    assert_link_order(
201        actual_deps,
202        package_set.root_ids(direction),
203        desc,
204        &format!("{msg}: actual link order"),
205    );
206
207    // Do a query in the opposite direction as well to test link order.
208    let opposite = direction.opposite();
209    let opposite_desc = DirectionDesc::new(opposite);
210    let opposite_deps: Vec<_> = package_set.links(opposite).collect();
211    let opposite_ptrs = dep_link_ptrs(opposite_deps.iter().copied());
212
213    // Checking for pointer equivalence is enough since they both use the same graph as a base.
214    assert_eq!(
215        actual_ptrs, opposite_ptrs,
216        "{}: actual and opposite links should return the same pointer triples",
217        msg,
218    );
219
220    assert_link_order(
221        opposite_deps,
222        package_set.root_ids(opposite),
223        opposite_desc,
224        &format!("{msg}: opposite link order"),
225    );
226
227    for dep_id in expected_dep_ids {
228        // depends_on should agree with this.
229        graph.assert_depends_on(known_details.id(), dep_id, direction, msg);
230
231        // Transitive deps should be transitively closed.
232        let dep_actual_dep_ids: BTreeSet<_> = graph
233            .query_directed(iter::once(dep_id), direction)
234            .unwrap_or_else(|err| {
235                panic!(
236                    "{}: {} transitive dep id query failed for dependency '{}': {}",
237                    msg, desc.direction_desc, dep_id, err
238                )
239            })
240            .resolve()
241            .package_ids(direction)
242            .collect();
243        // Use difference instead of is_subset/is_superset for better error messages.
244        let difference: Vec<_> = dep_actual_dep_ids.difference(&ids_from_links_set).collect();
245        assert!(
246            difference.is_empty(),
247            "{}: unexpected extra {} transitive dependency IDs for dep '{}': {:?}",
248            msg,
249            desc.direction_desc,
250            dep_id,
251            difference
252        );
253
254        let dep_ids_from_links: BTreeSet<_> = graph
255            .query_directed(iter::once(dep_id), direction)
256            .unwrap_or_else(|err| {
257                panic!(
258                    "{}: {} transitive dep query failed for dependency '{}': {}",
259                    msg, desc.direction_desc, dep_id, err
260                )
261            })
262            .resolve()
263            .links(direction)
264            .flat_map(|dep| vec![dep.from().id(), dep.to().id()])
265            .collect();
266        // Use difference instead of is_subset/is_superset for better error messages.
267        let difference: Vec<_> = dep_ids_from_links.difference(&ids_from_links_set).collect();
268        assert!(
269            difference.is_empty(),
270            "{}: unexpected extra {} transitive dependencies for dep '{}': {:?}",
271            msg,
272            desc.direction_desc,
273            dep_id,
274            difference
275        );
276    }
277}
278
279pub(crate) fn assert_topo_ids(graph: &PackageGraph, direction: DependencyDirection, msg: &str) {
280    let all_set = graph.resolve_all();
281    let topo_ids = all_set.package_ids(direction);
282    assert_eq!(
283        topo_ids.len(),
284        graph.package_count(),
285        "{}: topo sort returns all packages",
286        msg
287    );
288
289    // A package that comes later cannot depend on one that comes earlier.
290    graph.assert_topo_order(topo_ids, direction, msg);
291}
292
293pub(crate) fn assert_topo_metadatas(
294    graph: &PackageGraph,
295    direction: DependencyDirection,
296    msg: &str,
297) {
298    let all_set = graph.resolve_all();
299    let topo_metadatas = all_set.packages(direction);
300    assert_eq!(
301        topo_metadatas.len(),
302        graph.package_count(),
303        "{}: topo sort returns all packages",
304        msg
305    );
306    let topo_ids = topo_metadatas.map(|metadata| metadata.id());
307
308    // A package that comes later cannot depend on one that comes earlier.
309    graph.assert_topo_order(topo_ids, direction, msg);
310}
311
312pub(crate) fn assert_all_links(graph: &PackageGraph, direction: DependencyDirection, msg: &str) {
313    let desc = DirectionDesc::new(direction);
314    let all_links: Vec<_> = graph.resolve_all().links(direction).collect();
315    assert_eq!(
316        all_links.len(),
317        graph.link_count(),
318        "{}: all links should be returned",
319        msg
320    );
321
322    // The enabled status can't be unknown on the current platform.
323    for link in &all_links {
324        for dep_kind in &[
325            DependencyKind::Normal,
326            DependencyKind::Build,
327            DependencyKind::Development,
328        ] {
329            assert_enabled_status_is_known(
330                link.req_for_kind(*dep_kind),
331                &format!(
332                    "{}: {} -> {} ({})",
333                    msg,
334                    link.from().id(),
335                    link.to().id(),
336                    dep_kind,
337                ),
338            );
339        }
340    }
341
342    // all_links should be in the correct order.
343    assert_link_order(
344        all_links,
345        graph.resolve_all().root_ids(direction),
346        desc,
347        msg,
348    );
349}
350
351fn assert_enabled_status_is_known(req: DependencyReq<'_>, msg: &str) {
352    let current_platform = PlatformSpec::build_target().expect("current platform is known");
353    assert!(
354        req.status().enabled_on(&current_platform).is_known(),
355        "{msg}: enabled status known for current platform"
356    );
357    assert!(
358        req.default_features()
359            .enabled_on(&current_platform)
360            .is_known(),
361        "{msg}: default feature status known for current platform"
362    );
363    for feature in req.features() {
364        assert!(
365            req.feature_status(feature)
366                .enabled_on(&current_platform)
367                .is_known(),
368            "{msg}: for feature '{feature}', status known for current platform"
369        );
370    }
371}
372
373pub trait GraphAssert<'g>: Copy + fmt::Debug {
374    type Id: Copy + Eq + Hash + fmt::Debug;
375    type Metadata: GraphMetadata<'g, Id = Self::Id>;
376    type Query: GraphQuery<'g, Id = Self::Id, Set = Self::Set>;
377    type Set: GraphSet<'g, Id = Self::Id, Metadata = Self::Metadata>;
378    const NAME: &'static str;
379
380    // TODO: Add support for checks around links once they're defined for feature graphs.
381
382    fn depends_on(&self, a_id: Self::Id, b_id: Self::Id) -> Result<bool, Error>;
383
384    fn directly_depends_on(&self, a_id: Self::Id, b_id: Self::Id) -> Result<bool, Error>;
385
386    /// Returns true if there is a self-loop edge on `id` in the graph,
387    /// computed via a different code path than `directly_depends_on` so it
388    /// can be used as an independent oracle.
389    fn has_self_edge(&self, id: Self::Id) -> bool;
390
391    fn is_cyclic(&self, a_id: Self::Id, b_id: Self::Id) -> Result<bool, Error>;
392
393    /// Returns every cycle in the graph as a list of node IDs. Used by
394    /// cycle-consistency proptests to cross-check against `is_cyclic`.
395    fn all_cycles(&self) -> Vec<Vec<Self::Id>>;
396
397    fn query(
398        &self,
399        initials: impl IntoIterator<Item = Self::Id>,
400        direction: DependencyDirection,
401    ) -> Self::Query;
402
403    fn resolve(&self, initials: &[Self::Id], direction: DependencyDirection) -> Self::Set {
404        self.query(initials.iter().copied(), direction).resolve()
405    }
406
407    fn ids(
408        &self,
409        initials: &[Self::Id],
410        query_direction: DependencyDirection,
411        iter_direction: DependencyDirection,
412    ) -> Vec<Self::Id> {
413        let package_set = self.resolve(initials, query_direction);
414        let resolve_len = package_set.len();
415        let ids = package_set.ids(iter_direction);
416        assert_eq!(resolve_len, ids.len(), "resolve.len() is correct");
417        ids
418    }
419
420    fn root_ids(
421        &self,
422        initials: &[Self::Id],
423        query_direction: DependencyDirection,
424        iter_direction: DependencyDirection,
425    ) -> Vec<Self::Id> {
426        self.resolve(initials, query_direction)
427            .root_ids(iter_direction)
428    }
429
430    fn root_metadatas(
431        &self,
432        initials: &[Self::Id],
433        query_direction: DependencyDirection,
434        iter_direction: DependencyDirection,
435    ) -> Vec<Self::Metadata> {
436        self.resolve(initials, query_direction)
437            .root_metadatas(iter_direction)
438    }
439
440    fn assert_topo_order(
441        &self,
442        topo_ids: impl IntoIterator<Item = Self::Id>,
443        direction: DependencyDirection,
444        msg: &str,
445    ) {
446        let topo_ids: Vec<_> = topo_ids.into_iter().collect();
447        for (idx, earlier_package) in topo_ids.iter().enumerate() {
448            // Note that this skips over idx + 1 entries to avoid earlier_package == later_package.
449            // Doing an exhaustive search would be O(n**2) in the number of packages, so just do a
450            // maximum of 20.
451            // TODO: use proptest to generate random queries on the corpus.
452            for later_package in topo_ids.iter().skip(idx + 1).take(20) {
453                self.assert_not_depends_on(*later_package, *earlier_package, direction, msg);
454            }
455        }
456    }
457
458    fn assert_depends_on_any(
459        &self,
460        source_ids: &[Self::Id],
461        query_id: Self::Id,
462        direction: DependencyDirection,
463        msg: &str,
464    ) {
465        let any_depends_on = source_ids.iter().any(|source_id| match direction {
466            DependencyDirection::Forward => self.depends_on(*source_id, query_id).unwrap(),
467            DependencyDirection::Reverse => self.depends_on(query_id, *source_id).unwrap(),
468        });
469        match direction {
470            DependencyDirection::Forward => {
471                assert!(
472                    any_depends_on,
473                    "{}: {} '{:?}' should be a dependency of any of '{:?}'",
474                    msg,
475                    Self::NAME,
476                    query_id,
477                    source_ids
478                );
479            }
480            DependencyDirection::Reverse => {
481                assert!(
482                    any_depends_on,
483                    "{}: {} '{:?}' should depend on any of '{:?}'",
484                    msg,
485                    Self::NAME,
486                    query_id,
487                    source_ids
488                );
489            }
490        }
491    }
492
493    fn assert_depends_on(
494        &self,
495        a_id: Self::Id,
496        b_id: Self::Id,
497        direction: DependencyDirection,
498        msg: &str,
499    ) {
500        match direction {
501            DependencyDirection::Forward => assert!(
502                self.depends_on(a_id, b_id).unwrap(),
503                "{}: {} '{:?}' should depend on '{:?}'",
504                msg,
505                Self::NAME,
506                a_id,
507                b_id,
508            ),
509            DependencyDirection::Reverse => assert!(
510                self.depends_on(b_id, a_id).unwrap(),
511                "{}: {} '{:?}' should be a dependency of '{:?}'",
512                msg,
513                Self::NAME,
514                a_id,
515                b_id,
516            ),
517        }
518    }
519
520    fn assert_not_depends_on(
521        &self,
522        a_id: Self::Id,
523        b_id: Self::Id,
524        direction: DependencyDirection,
525        msg: &str,
526    ) {
527        if self.is_cyclic(a_id, b_id).unwrap() {
528            // This is a dependency cycle -- ignore it in not-depends-on checks.
529            // TODO: make this smarter now that cycles are handled in non-dev order.
530            return;
531        }
532
533        match direction {
534            DependencyDirection::Forward => assert!(
535                !self.depends_on(a_id, b_id).unwrap(),
536                "{}: {} '{:?}' should not depend on '{:?}'",
537                msg,
538                Self::NAME,
539                a_id,
540                b_id,
541            ),
542            DependencyDirection::Reverse => assert!(
543                !self.depends_on(b_id, a_id).unwrap(),
544                "{}: {} '{:?}' should not be a dependency of '{:?}'",
545                msg,
546                Self::NAME,
547                a_id,
548                b_id,
549            ),
550        }
551    }
552
553    fn assert_directly_depends_on(
554        &self,
555        a_id: Self::Id,
556        b_id: Self::Id,
557        direction: DependencyDirection,
558        msg: &str,
559    ) {
560        match direction {
561            DependencyDirection::Forward => assert!(
562                self.directly_depends_on(a_id, b_id).unwrap(),
563                "{}: {} '{:?}' should directly depend on '{:?}'",
564                msg,
565                Self::NAME,
566                a_id,
567                b_id,
568            ),
569            DependencyDirection::Reverse => assert!(
570                self.directly_depends_on(b_id, a_id).unwrap(),
571                "{}: {} '{:?}' should be a direct dependency of '{:?}'",
572                msg,
573                Self::NAME,
574                a_id,
575                b_id,
576            ),
577        }
578    }
579}
580
581pub trait GraphMetadata<'g> {
582    type Id: Copy + Eq + Hash + fmt::Debug;
583    fn id(&self) -> Self::Id;
584}
585
586pub trait GraphQuery<'g> {
587    type Id: Copy + Eq + Hash + fmt::Debug;
588    type Set: GraphSet<'g, Id = Self::Id>;
589
590    fn direction(&self) -> DependencyDirection;
591
592    fn starts_from(&self, id: Self::Id) -> bool;
593
594    fn resolve(self) -> Self::Set;
595}
596
597pub trait GraphSet<'g>: Clone + fmt::Debug {
598    type Id: Copy + Eq + Hash + fmt::Debug;
599    type Metadata: GraphMetadata<'g, Id = Self::Id>;
600    fn len(&self) -> usize;
601
602    fn is_empty(&self) -> bool {
603        self.len() == 0
604    }
605
606    fn contains(&self, id: Self::Id) -> bool;
607
608    fn union(&self, other: &Self) -> Self;
609    fn intersection(&self, other: &Self) -> Self;
610    fn difference(&self, other: &Self) -> Self;
611    fn symmetric_difference(&self, other: &Self) -> Self;
612
613    fn ids(&self, direction: DependencyDirection) -> Vec<Self::Id>;
614    fn metadatas(&self, direction: DependencyDirection) -> Vec<Self::Metadata>;
615    fn root_ids(&self, direction: DependencyDirection) -> Vec<Self::Id>;
616    fn root_metadatas(&self, direction: DependencyDirection) -> Vec<Self::Metadata>;
617}
618
619impl<'g> GraphAssert<'g> for &'g PackageGraph {
620    type Id = &'g PackageId;
621    type Metadata = PackageMetadata<'g>;
622    type Query = PackageQuery<'g>;
623    type Set = PackageSet<'g>;
624    const NAME: &'static str = "package";
625
626    fn depends_on(&self, a_id: Self::Id, b_id: Self::Id) -> Result<bool, Error> {
627        PackageGraph::depends_on(self, a_id, b_id)
628    }
629
630    fn directly_depends_on(&self, a_id: Self::Id, b_id: Self::Id) -> Result<bool, Error> {
631        PackageGraph::directly_depends_on(self, a_id, b_id)
632    }
633
634    fn has_self_edge(&self, id: Self::Id) -> bool {
635        // Cross-check via `direct_links()` (which iterates outgoing edges)
636        // rather than `directly_depends_on` (which calls `contains_edge`).
637        self.metadata(id)
638            .expect("valid ID")
639            .direct_links()
640            .any(|link| link.to().id() == id)
641    }
642
643    fn is_cyclic(&self, a_id: Self::Id, b_id: Self::Id) -> Result<bool, Error> {
644        let cycles = self.cycles();
645        cycles.is_cyclic(a_id, b_id)
646    }
647
648    fn all_cycles(&self) -> Vec<Vec<Self::Id>> {
649        self.cycles().all_cycles().map(|c| c.to_vec()).collect()
650    }
651
652    fn query(
653        &self,
654        initials: impl IntoIterator<Item = Self::Id>,
655        direction: DependencyDirection,
656    ) -> Self::Query {
657        self.query_directed(initials, direction)
658            .expect("valid initials")
659    }
660}
661
662impl<'g> GraphMetadata<'g> for PackageMetadata<'g> {
663    type Id = &'g PackageId;
664    fn id(&self) -> Self::Id {
665        PackageMetadata::id(self)
666    }
667}
668
669impl<'g> GraphQuery<'g> for PackageQuery<'g> {
670    type Id = &'g PackageId;
671    type Set = PackageSet<'g>;
672
673    fn direction(&self) -> DependencyDirection {
674        self.direction()
675    }
676
677    fn starts_from(&self, id: Self::Id) -> bool {
678        self.initials().contains(id).expect("valid ID")
679    }
680
681    fn resolve(self) -> Self::Set {
682        self.resolve()
683    }
684}
685
686impl<'g> GraphSet<'g> for PackageSet<'g> {
687    type Id = &'g PackageId;
688    type Metadata = PackageMetadata<'g>;
689
690    fn len(&self) -> usize {
691        self.len()
692    }
693
694    fn contains(&self, id: Self::Id) -> bool {
695        self.contains(id).unwrap()
696    }
697
698    fn union(&self, other: &Self) -> Self {
699        self.union(other)
700    }
701
702    fn intersection(&self, other: &Self) -> Self {
703        self.intersection(other)
704    }
705
706    fn difference(&self, other: &Self) -> Self {
707        self.difference(other)
708    }
709
710    fn symmetric_difference(&self, other: &Self) -> Self {
711        self.symmetric_difference(other)
712    }
713
714    fn ids(&self, direction: DependencyDirection) -> Vec<Self::Id> {
715        self.package_ids(direction).collect()
716    }
717
718    fn metadatas(&self, direction: DependencyDirection) -> Vec<Self::Metadata> {
719        self.packages(direction).collect()
720    }
721
722    fn root_ids(&self, direction: DependencyDirection) -> Vec<Self::Id> {
723        Self::root_ids(self, direction).collect()
724    }
725
726    fn root_metadatas(&self, direction: DependencyDirection) -> Vec<Self::Metadata> {
727        Self::root_packages(self, direction).collect()
728    }
729}
730
731impl<'g> GraphAssert<'g> for FeatureGraph<'g> {
732    type Id = FeatureId<'g>;
733    type Metadata = FeatureMetadata<'g>;
734    type Query = FeatureQuery<'g>;
735    type Set = FeatureSet<'g>;
736    const NAME: &'static str = "feature";
737
738    fn depends_on(&self, a_id: Self::Id, b_id: Self::Id) -> Result<bool, Error> {
739        FeatureGraph::depends_on(self, a_id, b_id)
740    }
741
742    fn directly_depends_on(&self, a_id: Self::Id, b_id: Self::Id) -> Result<bool, Error> {
743        FeatureGraph::directly_depends_on(self, a_id, b_id)
744    }
745
746    fn has_self_edge(&self, id: Self::Id) -> bool {
747        // Cross-check by iterating outgoing links from a forward query rooted
748        // at `id`. The only link with both endpoints equal to `id` is a
749        // self-loop edge; this is independent of `directly_depends_on`'s
750        // `contains_edge` path.
751        let set = self
752            .query_directed([id], DependencyDirection::Forward)
753            .expect("valid ID")
754            .resolve();
755        set.links(DependencyDirection::Forward)
756            .any(|(from, to, _edge)| from == id && to == id)
757    }
758
759    fn is_cyclic(&self, a_id: Self::Id, b_id: Self::Id) -> Result<bool, Error> {
760        let cycles = self.cycles();
761        cycles.is_cyclic(a_id, b_id)
762    }
763
764    fn all_cycles(&self) -> Vec<Vec<Self::Id>> {
765        self.cycles().all_cycles().collect()
766    }
767
768    fn query(
769        &self,
770        initials: impl IntoIterator<Item = Self::Id>,
771        direction: DependencyDirection,
772    ) -> Self::Query {
773        self.query_directed(initials, direction)
774            .expect("valid initials")
775    }
776}
777
778impl<'g> GraphMetadata<'g> for FeatureMetadata<'g> {
779    type Id = FeatureId<'g>;
780    fn id(&self) -> Self::Id {
781        self.feature_id()
782    }
783}
784
785impl<'g> GraphQuery<'g> for FeatureQuery<'g> {
786    type Id = FeatureId<'g>;
787    type Set = FeatureSet<'g>;
788
789    fn direction(&self) -> DependencyDirection {
790        self.direction()
791    }
792
793    fn starts_from(&self, id: Self::Id) -> bool {
794        self.initials().contains(id).expect("valid feature ID")
795    }
796
797    fn resolve(self) -> Self::Set {
798        self.resolve()
799    }
800}
801
802impl<'g> GraphSet<'g> for FeatureSet<'g> {
803    type Id = FeatureId<'g>;
804    type Metadata = FeatureMetadata<'g>;
805
806    fn len(&self) -> usize {
807        self.len()
808    }
809
810    fn contains(&self, id: Self::Id) -> bool {
811        self.contains(id).unwrap()
812    }
813
814    fn union(&self, other: &Self) -> Self {
815        self.union(other)
816    }
817
818    fn intersection(&self, other: &Self) -> Self {
819        self.intersection(other)
820    }
821
822    fn difference(&self, other: &Self) -> Self {
823        self.difference(other)
824    }
825
826    fn symmetric_difference(&self, other: &Self) -> Self {
827        self.symmetric_difference(other)
828    }
829
830    fn ids(&self, direction: DependencyDirection) -> Vec<Self::Id> {
831        self.feature_ids(direction).collect()
832    }
833
834    fn metadatas(&self, direction: DependencyDirection) -> Vec<Self::Metadata> {
835        self.features(direction).collect()
836    }
837
838    fn root_ids(&self, direction: DependencyDirection) -> Vec<Self::Id> {
839        Self::root_ids(self, direction).collect()
840    }
841
842    fn root_metadatas(&self, direction: DependencyDirection) -> Vec<Self::Metadata> {
843        Self::root_features(self, direction).collect()
844    }
845}
846
847/// Assert that links are presented in the expected order.
848///
849/// For any given package not in the initial set:
850/// * If direction is Forward, the package should appear in the `to` of a link at least once
851///   before it appears in the `from` of a link.
852/// * If direction is Reverse, the package should appear in the `from` of a link at least once
853///   before it appears in the `to` of a link.
854pub fn assert_link_order<'g>(
855    links: impl IntoIterator<Item = PackageLink<'g>>,
856    initial: impl IntoIterator<Item = &'g PackageId>,
857    desc: impl Into<DirectionDesc<'g>>,
858    msg: &str,
859) {
860    let desc = desc.into();
861
862    // for forward, 'from' is known and 'to' is variable.
863    let mut variable_seen: HashSet<_> = initial.into_iter().collect();
864
865    for link in links {
866        let known_id = desc.known_metadata(&link).id();
867        let variable_id = desc.variable_metadata(&link).id();
868
869        variable_seen.insert(variable_id);
870        assert!(
871            variable_seen.contains(&known_id),
872            "{}: for package '{}': unexpected link {} package seen before any links {} package",
873            msg,
874            known_id,
875            desc.known_desc,
876            desc.variable_desc,
877        );
878    }
879}
880
881fn dep_link_ptrs<'g>(dep_links: impl IntoIterator<Item = PackageLink<'g>>) -> Vec<PackageLinkPtrs> {
882    let mut triples: Vec<_> = dep_links
883        .into_iter()
884        .map(|link| link.as_inner_ptrs())
885        .collect();
886    triples.sort();
887    triples
888}
fixtures/dep_helpers.rs

fixtures/
dep_helpers.rs
