guppy/graph/feature/
weak.rs

Help
1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! Support for weak features.
5
6use crate::graph::{
7    feature::{ConditionalLink, FeatureEdgeReference},
8    PackageIx,
9};
10use indexmap::IndexSet;
11use itertools::Either;
12use petgraph::graph::EdgeIndex;
13use smallvec::SmallVec;
14
15/// Data structure that tracks pairs of package indexes that form weak dependencies.
16#[derive(Clone, Debug)]
17pub(super) struct WeakDependencies {
18    ixs: IndexSet<EdgeIndex<PackageIx>>,
19}
20
21impl WeakDependencies {
22    pub(super) fn new() -> Self {
23        Self {
24            ixs: IndexSet::new(),
25        }
26    }
27
28    pub(super) fn insert(&mut self, edge_ix: EdgeIndex<PackageIx>) -> WeakIndex {
29        WeakIndex(self.ixs.insert_full(edge_ix).0)
30    }
31
32    pub(super) fn get(&self, edge_ix: EdgeIndex<PackageIx>) -> Option<WeakIndex> {
33        self.ixs.get_index_of(&edge_ix).map(WeakIndex)
34    }
35
36    #[inline]
37    pub(super) fn new_buffer_states<'g, F>(&self, accept_fn: F) -> WeakBufferStates<'g, '_, F>
38    where
39        F: FnMut(ConditionalLink<'g>) -> bool,
40    {
41        WeakBufferStates::new(self, self.ixs.len(), accept_fn)
42    }
43}
44
45// Not part of the public API -- exposed for testing.
46#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
47#[doc(hidden)]
48pub struct WeakIndex(pub(super) usize);
49
50/// Buffer states for weak indexes, to be used during a feature resolver traversal.
51pub(super) struct WeakBufferStates<'g, 'a, F> {
52    deps: &'a WeakDependencies,
53    states: SmallVec<[SingleBufferState<'g>; 8]>,
54    accept_fn: F,
55}
56
57impl<'g, 'a, F> WeakBufferStates<'g, 'a, F>
58where
59    F: FnMut(ConditionalLink<'g>) -> bool,
60{
61    #[inline]
62    fn new(deps: &'a WeakDependencies, len: usize, accept_fn: F) -> Self {
63        let mut states = SmallVec::with_capacity(len);
64        states.resize_with(len, Default::default);
65        Self {
66            deps,
67            states,
68            accept_fn,
69        }
70    }
71
72    pub(super) fn track(
73        &mut self,
74        edge_ref: FeatureEdgeReference<'g>,
75        link: ConditionalLink<'g>,
76        weak_index: Option<WeakIndex>,
77    ) -> Either<Option<FeatureEdgeReference<'g>>, Vec<FeatureEdgeReference<'g>>> {
78        match weak_index {
79            Some(index) => {
80                match &mut self.states[index.0] {
81                    SingleBufferState::Buffered(buffer) => {
82                        // Package not currently accepted -- add to the buffer.
83                        buffer.push((link, edge_ref));
84                        Either::Left(None)
85                    }
86                    SingleBufferState::Accepted => {
87                        // Weak link, but package already accepted.
88                        Either::Left((self.accept_fn)(link).then_some(edge_ref))
89                    }
90                }
91            }
92            None => {
93                if !(self.accept_fn)(link) {
94                    // This link was not accepted -- ignore its presence.
95                    return Either::Left(None);
96                }
97
98                match self.deps.get(link.package_edge_ix()) {
99                    Some(weak_index) => {
100                        match std::mem::replace(
101                            &mut self.states[weak_index.0],
102                            SingleBufferState::Accepted,
103                        ) {
104                            SingleBufferState::Buffered(buffer) => {
105                                // Transition from buffered to accepted.
106                                let mut edge_refs: Vec<_> = buffer
107                                    .into_iter()
108                                    .filter_map(|(link, edge_ref)| {
109                                        // Filter buffered links.
110                                        (self.accept_fn)(link).then_some(edge_ref)
111                                    })
112                                    .collect();
113                                edge_refs.push(edge_ref);
114                                Either::Right(edge_refs)
115                            }
116                            SingleBufferState::Accepted => {
117                                // Weak link, but package already accepted.
118                                Either::Left(Some(edge_ref))
119                            }
120                        }
121                    }
122                    None => {
123                        // Not a weak link.
124                        Either::Left(Some(edge_ref))
125                    }
126                }
127            }
128        }
129    }
130}
131
132/// Buffer state for a single weak index in an in-progress resolver.
133pub(super) enum SingleBufferState<'g> {
134    Buffered(SingleBufferVec<'g>),
135    Accepted,
136}
137
138impl Default for SingleBufferState<'_> {
139    fn default() -> Self {
140        Self::Buffered(SingleBufferVec::new())
141    }
142}
143
144type SingleBufferVec<'g> = Vec<(ConditionalLink<'g>, FeatureEdgeReference<'g>)>;
guppy/graph/feature/weak.rs

guppy/graph/feature/
weak.rs
