swh_graph_stdlib/collections/
paths.rs

1// Copyright (C) 2024  The Software Heritage developers
2// See the AUTHORS file at the top-level directory of this distribution
3// License: GNU General Public License version 3, or any later version
4// See top-level LICENSE file for more information
5
6use swh_graph::labels::LabelNameId;
7
8/// Value in the path_stack between two lists of path parts
9const PATH_SEPARATOR: LabelNameId = LabelNameId(u64::MAX);
10
11/// A stack that stores sequences of [`LabelNameId`] as a single array
12///
13/// Internally, it is a flattened array of paths. Each sequence is made of parts represented
14/// by an id, and sequences are separated by PATH_SEPARATOR.
15///
16/// Parts are in the reverse order of insertion, to avoid lazily popping without peeking.
17///
18/// ```
19/// use swh_graph::labels::LabelNameId;
20/// use swh_graph_stdlib::collections::PathStack;
21///
22/// let path1 = [LabelNameId(0), LabelNameId(10)];
23/// let path2 = [LabelNameId(1)];
24///
25/// let mut stack = PathStack::new();
26/// stack.push(path1);
27/// stack.push(path2);
28/// assert_eq!(stack.pop().unwrap().collect::<Vec<_>>(), path2);
29/// assert_eq!(stack.pop().unwrap().collect::<Vec<_>>(), path1);
30/// assert!(stack.pop().is_none());
31/// ```
32#[derive(Debug, Clone, Eq, PartialEq, Default)]
33pub struct PathStack(Vec<LabelNameId>);
34
35impl PathStack {
36    pub fn new() -> PathStack {
37        PathStack(Vec::new())
38    }
39
40    /// Creates a new empty [`PathStack`] pre-allocated for this many paths plus path parts.
41    pub fn with_capacity(capacity: usize) -> PathStack {
42        PathStack(Vec::with_capacity(capacity))
43    }
44
45    /// Adds a path to this stack
46    ///
47    /// # Panics
48    ///
49    /// If any of the [`LabelNameId`] path parts was manually built from `u64::MAX`.
50    #[inline]
51    pub fn push<Iter: IntoIterator<Item = LabelNameId>>(&mut self, path: Iter)
52    where
53        <Iter as IntoIterator>::IntoIter: DoubleEndedIterator,
54    {
55        self.0.push(PATH_SEPARATOR);
56        for item in path.into_iter().rev() {
57            assert_ne!(
58                item, PATH_SEPARATOR,
59                "u64::MAX may not be used as path part"
60            );
61            self.0.push(item);
62        }
63    }
64
65    /// Adds a path part to the last path on this stack
66    ///
67    /// # Panics
68    ///
69    /// If the [`LabelNameId`] path parts was manually built from `u64::MAX`.
70    #[inline]
71    pub fn push_filename(&mut self, item: LabelNameId) {
72        assert_ne!(
73            item, PATH_SEPARATOR,
74            "u64::MAX may not be used as path part"
75        );
76        self.0.push(item);
77    }
78
79    /// Removes the last path of this stack
80    ///
81    /// Returns an iterator that pops parts from the part as the iterator is consumed.
82    /// It is safe to drop the iterator without consuming it.
83    #[inline]
84    pub fn pop(&mut self) -> Option<PopPathStack<'_>> {
85        if self.0.is_empty() {
86            None
87        } else {
88            Some(PopPathStack(self))
89        }
90    }
91}
92
93/// Returned by [`PathStack::pop`]
94pub struct PopPathStack<'a>(&'a mut PathStack);
95
96impl Iterator for PopPathStack<'_> {
97    type Item = LabelNameId;
98
99    #[inline]
100    fn next(&mut self) -> Option<Self::Item> {
101        if *self
102            .0
103             .0
104            .last()
105            .expect("PopPathStack reached the bottom of the stack")
106            == PATH_SEPARATOR
107        {
108            None
109        } else {
110            Some(self.0 .0.pop().unwrap())
111        }
112    }
113}
114
115impl Drop for PopPathStack<'_> {
116    fn drop(&mut self) {
117        // Finish popping from the stack so a partial path does not remain on top of it
118        while self
119            .0
120             .0
121            .pop()
122            .expect("PopPathStack reached the bottom of the stack")
123            != PATH_SEPARATOR
124        {}
125    }
126}
127
128#[test]
129fn test_path_stack_empty() {
130    let mut stack = PathStack::new();
131    assert!(stack.pop().is_none());
132    assert!(stack.pop().is_none());
133}
134
135#[test]
136/// Checks that dropping PopPathStack does pop the rest of the path from the stack
137fn test_path_stack_drop() {
138    let path1 = [LabelNameId(0), LabelNameId(10)];
139    let path2 = [LabelNameId(1)];
140
141    let mut stack = PathStack::new();
142    stack.push(path1);
143    stack.push(path2);
144    stack.pop().unwrap(); // not consumed
145    assert_eq!(stack.pop().unwrap().collect::<Vec<_>>(), path1);
146    assert!(stack.pop().is_none());
147}
swh_graph_stdlib/collections/paths.rs

swh_graph_stdlib/collections/
paths.rs
