fs_tree/
iter.rs

1//! Iterators for [`FsTree`].
2//!
3//! Iterators traverse in [Depth-First Order](https://en.wikipedia.org/wiki/Binary_tree#Depth-first_order).
4//!
5//! There are three [`FsTree`] methods for creating an iterator:
6//! 1. [`Iter`](iter::Iter) from [`.iter()`](FsTree::iter) yields `(&FsTree, PathBuf)`.
7//! 2. [`NodesIter`](iter::NodesIter) from [`.nodes()`](FsTree::nodes) yields `&FsTree`.
8//! 3. [`PathsIter`](iter::PathsIter) from [`.paths()`](FsTree::paths) yields `PathBuf`.
9//!
10//! The yielded [`PathBuf`]s correspond to the full relative path to the current node, which is the
11//! result of concatenating the paths of every parent, and the current node.
12//!
13//! [`PathBuf`]: std::path::PathBuf
14//!
15//! # Examples:
16//!
17//! ```
18//! use fs_tree::tree;
19//! use std::path::PathBuf;
20//!
21//! let tree = tree! {
22//!     dir: {
23//!         file1
24//!         file2
25//!         file3
26//!     }
27//! };
28//!
29//!
30//! let mut paths = tree.paths();
31//! assert_eq!(paths.next(), Some(PathBuf::from(""))); // Root can be skipped with `.min_depth(1)`
32//! assert_eq!(paths.next(), Some(PathBuf::from("dir")));
33//! assert_eq!(paths.next(), Some(PathBuf::from("dir/file1")));
34//! assert_eq!(paths.next(), Some(PathBuf::from("dir/file2")));
35//! assert_eq!(paths.next(), Some(PathBuf::from("dir/file3")));
36//! assert_eq!(paths.next(), None);
37//!
38//! let mut nodes = tree.nodes();
39//! assert_eq!(nodes.next(), Some(&tree));
40//! assert_eq!(nodes.next(), Some(&tree["dir"]));
41//! assert_eq!(nodes.next(), Some(&tree["dir/file1"]));
42//! assert_eq!(nodes.next(), Some(&tree["dir/file2"]));
43//! assert_eq!(nodes.next(), Some(&tree["dir/file3"]));
44//! assert_eq!(nodes.next(), None);
45//! ```
46
47use std::{
48    collections::VecDeque,
49    path::{Path, PathBuf},
50};
51
52use crate::FsTree;
53
54type NodeWithPathAndDepth<'a> = (&'a FsTree, usize, &'a Path);
55type NodesIterDeque<'a> = VecDeque<NodeWithPathAndDepth<'a>>;
56
57/// This is the underlying iterator implementation for the other iterators.
58///
59/// It does not implement the `Iterator` trait, instead, it has its own `.next()` method, because
60/// GATs is not stabilized and returning `&Path` makes this a lending iterator.
61#[derive(Debug, Clone)]
62struct InnerIter<'a> {
63    // Always pop from the front
64    // Push to front or back, if it's a directory or not, respectively, to yield in DFS-order
65    file_deque: NodesIterDeque<'a>,
66    // Accessed by the `depth` method, determined by the last yielded element
67    current_depth: usize,
68    // Filters togglable with methods
69    skip_regular_files: bool,
70    skip_dirs: bool,
71    skip_symlinks: bool,
72    min_depth: usize,
73    max_depth: usize,
74
75    /// TODO: what is this
76    last_path: &'a Path,
77}
78
79impl<'a> InnerIter<'a> {
80    fn new(start_file: &'a FsTree) -> Self {
81        // Deque used for iterate in recursive structure
82        let mut file_deque = VecDeque::new();
83        // Starting deque from `start_file`, at depth 0, which can increase for each directory found
84        file_deque.push_back((start_file, 0, Path::new("")));
85
86        Self {
87            file_deque,
88            current_depth: 0,
89            skip_dirs: false,
90            skip_regular_files: false,
91            skip_symlinks: false,
92            min_depth: usize::MIN,
93            max_depth: usize::MAX,
94            last_path: Path::new(""),
95        }
96    }
97
98    /// Let other iterators access the inner Path reference.
99    fn last_path(&self) -> &Path {
100        self.last_path
101    }
102
103    fn depth(&self) -> usize {
104        self.current_depth
105    }
106}
107
108impl<'a> Iterator for InnerIter<'a> {
109    type Item = &'a FsTree;
110
111    fn next(&mut self) -> Option<Self::Item> {
112        // Pop last element, if any
113        let (file, depth, last_path) = self.file_deque.pop_front()?;
114
115        // Update current_depth, for `.depth()` method
116        self.current_depth = depth;
117
118        // If directory, add children
119        if let Some(children) = file.children() {
120            // Reversed, to preserve order (push_front is different)
121            for (path, child) in children.iter().rev() {
122                self.file_deque.push_front((child, depth + 1, path));
123            }
124        }
125
126        // If should skip due to any filter
127        if self.skip_regular_files && file.is_regular()
128            || self.skip_dirs && file.is_dir()
129            || self.skip_symlinks && file.is_symlink()
130            || self.min_depth > depth
131            || self.max_depth < depth
132        {
133            // Skipping and calling the next one, if any
134            return self.next();
135        }
136
137        self.last_path = last_path;
138
139        Some(file)
140    }
141}
142
143macro_rules! impl_iter_methods {
144    ($($path_to_the_inner_iter:tt)*) => {
145        /// Return depth for the last yielded element.
146        ///
147        /// Depth `0` corresponds to the root element (first `.next()` call).
148        ///
149        /// # Corner cases:
150        /// - If you call this function before `.next()` is called, you'll get `0`.
151        /// - If `None` is yielded by this iterator, the depth value will remain immutable, and
152        ///   correspond to the depth of the last yielded element.
153        pub fn depth(&self) -> usize {
154            self.$($path_to_the_inner_iter)*.depth()
155        }
156
157        /// Filter out regular files.
158        pub fn skip_regular_files(mut self, arg: bool) -> Self {
159            self.$($path_to_the_inner_iter)*.skip_regular_files = arg;
160            self
161        }
162
163        /// Filter out directories.
164        pub fn skip_dirs(mut self, arg: bool) -> Self {
165            self.$($path_to_the_inner_iter)*.skip_dirs = arg;
166            self
167        }
168
169        /// Filter out symlinks.
170        pub fn skip_symlinks(mut self, arg: bool) -> Self {
171            self.$($path_to_the_inner_iter)*.skip_symlinks = arg;
172            self
173        }
174
175        /// Filter out entries below the given minimum [depth](Self::depth).
176        pub fn min_depth(mut self, min: usize) -> Self {
177            self.$($path_to_the_inner_iter)*.min_depth = min;
178            self
179        }
180
181        /// Filter out entries above the given maximum [depth](Self::depth).
182        pub fn max_depth(mut self, max: usize) -> Self {
183            self.$($path_to_the_inner_iter)*.max_depth = max;
184            self
185        }
186    };
187}
188
189/// Tree nodes iterator.
190///
191/// Yields `(&FsTree, PathBuf)`.
192///
193/// Created by `FsTree::iter`.
194#[derive(Debug, Clone)]
195pub struct NodesIter<'a> {
196    inner_iter: InnerIter<'a>,
197}
198
199impl<'a> NodesIter<'a> {
200    pub(crate) fn new(root: &'a FsTree) -> Self {
201        Self {
202            inner_iter: InnerIter::new(root),
203        }
204    }
205
206    impl_iter_methods!(inner_iter);
207}
208
209impl<'a> Iterator for NodesIter<'a> {
210    type Item = &'a FsTree;
211
212    fn next(&mut self) -> Option<Self::Item> {
213        self.inner_iter.next()
214    }
215}
216
217/// Tree iterator.
218///
219/// Yields `(&FsTree, PathBuf)`.
220///
221/// Created by `FsTree::iter`.
222#[derive(Debug, Clone)]
223pub struct Iter<'a> {
224    inner_iter: InnerIter<'a>,
225    path_builder: PathBuf,
226    previous_depth: usize,
227}
228
229impl<'a> Iter<'a> {
230    pub(crate) fn new(root: &'a FsTree) -> Self {
231        Self {
232            inner_iter: InnerIter::new(root),
233            path_builder: PathBuf::new(),
234            previous_depth: 0,
235        }
236    }
237
238    impl_iter_methods!(inner_iter);
239}
240
241impl<'a> Iterator for Iter<'a> {
242    // I'd like to return `&Path`, but the `Iterator` trait blocks putting a lifetime on `self`
243    type Item = (&'a FsTree, PathBuf);
244
245    fn next(&mut self) -> Option<Self::Item> {
246        let node = self.inner_iter.next()?;
247        let new_depth = self.inner_iter.depth();
248        let last_path = self.inner_iter.last_path();
249
250        for _ in new_depth..=self.previous_depth {
251            self.path_builder.pop();
252        }
253
254        self.path_builder.push(last_path);
255
256        self.previous_depth = new_depth;
257
258        Some((node, self.path_builder.clone()))
259    }
260}
261
262/// Iterator for each path inside of the recursive struct
263#[derive(Debug, Clone)]
264pub struct PathsIter<'a> {
265    iter: Iter<'a>,
266}
267
268impl<'a> PathsIter<'a> {
269    pub(crate) fn new(root: &'a crate::FsTree) -> Self {
270        Self {
271            iter: Iter::new(root),
272        }
273    }
274
275    impl_iter_methods!(iter.inner_iter);
276}
277
278impl Iterator for PathsIter<'_> {
279    // Can't return `&Path` because we don't have GATs yet
280    type Item = PathBuf;
281
282    fn next(&mut self) -> Option<Self::Item> {
283        self.iter.next().map(|(_, path)| path)
284    }
285}
286
287#[cfg(test)]
288mod tests {
289    use pretty_assertions::assert_eq;
290
291    use crate::tree;
292
293    #[test]
294    #[rustfmt::skip]
295    fn testing_files_and_paths_iters() {
296        // Create the strucutre
297        let tree = tree! {
298            ".config": {
299                i3: {
300                    file1
301                    file2
302                    dir: {
303                        innerfile1
304                        innerfile2
305                    }
306                    file3
307                }
308                outerfile1
309                outerfile2
310            }
311        };
312
313        // Get the references in ascending order
314        let refs = [
315            /* 0 */ &tree,
316            /* 1 */ &tree[".config/"],
317            /* 2 */ &tree[".config/i3/"],
318            /* 5 */ &tree[".config/i3/dir/"],
319            /* 6 */ &tree[".config/i3/dir/innerfile1"],
320            /* 7 */ &tree[".config/i3/dir/innerfile2"],
321            /* 3 */ &tree[".config/i3/file1"],
322            /* 4 */ &tree[".config/i3/file2"],
323            /* 8 */ &tree[".config/i3/file3"],
324            /* 9 */ &tree[".config/outerfile1"],
325            /* 0 */ &tree[".config/outerfile2"],
326        ];
327
328        // Paths iterator testing
329        let mut it = tree.paths();
330        assert_eq!(it.next(), Some("".into()));
331        assert_eq!(it.next(), Some(".config/".into()));
332        assert_eq!(it.next(), Some(".config/i3/".into()));
333        assert_eq!(it.next(), Some(".config/i3/dir/".into()));
334        assert_eq!(it.next(), Some(".config/i3/dir/innerfile1".into()));
335        assert_eq!(it.next(), Some(".config/i3/dir/innerfile2".into()));
336        assert_eq!(it.next(), Some(".config/i3/file1".into()));
337        assert_eq!(it.next(), Some(".config/i3/file2".into()));
338        assert_eq!(it.next(), Some(".config/i3/file3".into()));
339        assert_eq!(it.next(), Some(".config/outerfile1".into()));
340        assert_eq!(it.next(), Some(".config/outerfile2".into()) );
341        assert_eq!(it.next(), None);
342
343        // This
344        let mut it = tree.nodes();
345        assert_eq!(it.next(), Some(refs[0]));  // ""
346        assert_eq!(it.depth(), 0);             //
347        assert_eq!(it.next(), Some(refs[1]));  // ".config/"
348        assert_eq!(it.depth(), 1);             //  1
349        assert_eq!(it.next(), Some(refs[2]));  // ".config/i3/"
350        assert_eq!(it.depth(), 2);             //  1       2
351        assert_eq!(it.next(), Some(refs[3]));  // ".config/i3/dir/"
352        assert_eq!(it.depth(), 3);             //  1       2
353        assert_eq!(it.next(), Some(refs[4]));  // ".config/i3/dir/innerfile1"
354        assert_eq!(it.depth(), 4);             //  1       2  3   4
355        assert_eq!(it.next(), Some(refs[5]));  // ".config/i3/dir/innerfile2"
356        assert_eq!(it.depth(), 4);             //  1       2  3   4
357        assert_eq!(it.next(), Some(refs[6]));  // ".config/i3/file1"
358        assert_eq!(it.depth(), 3);             //  1       2  3
359        assert_eq!(it.next(), Some(refs[7]));  // ".config/i3/file2"
360        assert_eq!(it.depth(), 3);             //  1       2  3
361        assert_eq!(it.next(), Some(refs[8]));  // ".config/i3/file3"
362        assert_eq!(it.depth(), 3);             //  1       2  3
363        assert_eq!(it.next(), Some(refs[9]));  // ".config/outerfile1"
364        assert_eq!(it.depth(), 2);             //  1       2
365        assert_eq!(it.next(), Some(refs[10])); // ".config/outerfile2"
366        assert_eq!(it.depth(), 2);             //  1       2
367        assert_eq!(it.next(), None);
368
369        let mut it = tree.nodes().skip_regular_files(true);
370        assert_eq!(it.next(), Some(refs[0]));  // ""
371        assert_eq!(it.next(), Some(refs[1]));  // ".config/"
372        assert_eq!(it.next(), Some(refs[2]));  // ".config/i3/"
373        assert_eq!(it.next(), Some(refs[3]));  // ".config/i3/dir/"
374        assert_eq!(it.next(), None);
375
376        let mut it = tree.nodes().skip_dirs(true);
377        assert_eq!(it.next(), Some(refs[4]));  // ".config/i3/dir/innerfile1"
378        assert_eq!(it.next(), Some(refs[5]));  // ".config/i3/dir/innerfile2"
379        assert_eq!(it.next(), Some(refs[6]));  // ".config/i3/file1"
380        assert_eq!(it.next(), Some(refs[7]));  // ".config/i3/file2"
381        assert_eq!(it.next(), Some(refs[8]));  // ".config/i3/file3"
382        assert_eq!(it.next(), Some(refs[9]));  // ".config/outerfile1"
383        assert_eq!(it.next(), Some(refs[10])); // ".config/outerfile2"
384        assert_eq!(it.next(), None);
385
386        // min and max depth (2 <= d <= 2  =>  d == 2)
387        //
388        // skips:
389        // ""
390        // ".config/"
391        // ".config/i3/dir/innerfile1"
392        // ".config/i3/dir/innerfile2"
393        let mut it = tree.nodes().min_depth(2).max_depth(2);
394        assert_eq!(it.next(), Some(refs[2]));  // ".config/i3/"
395        assert_eq!(it.next(), Some(refs[9]));  // ".config/outerfile1"
396        assert_eq!(it.next(), Some(refs[10])); // ".config/outerfile2"
397        assert_eq!(it.next(), None);
398    }
399}
fs_tree/iter.rs

fs_tree/
iter.rs
