vfsi_core/api/
traversal.rs

1//! Incremental, no-follow traversal shared by application adapters.
2use crate::api::{DirEntry, ListDirOptions, TraversalCompletion};
3use crate::{VfError, VfResult, internal::TraversalBudget};
4use std::path::Path;
5
6/// Callback decision. Pruning never reads the directory's contents.
7#[derive(Debug, Clone, Copy, PartialEq, Eq)]
8pub enum WalkControl {
9    Continue,
10    SkipSubtree,
11    Stop,
12}
13/// Enter/Leave surround a directory, including a pruned directory.
14#[derive(Debug, Clone, Copy, PartialEq, Eq)]
15pub enum WalkEventKind {
16    Enter,
17    Entry,
18    Leave,
19}
20/// Root is depth zero. Symlinks are Entry events and are never followed.
21#[derive(Debug, Clone)]
22pub struct WalkEvent {
23    pub kind: WalkEventKind,
24    pub entry: DirEntry,
25    pub depth: usize,
26}
27
28/// Adapter hook; application callers should use their client's method.
29/// Each directory is bounded before sorting; only the active frontier is kept.
30/// Limits charge fetched entries (including the root), even if later pruned.
31#[doc(hidden)]
32pub fn walk_events(
33    root: DirEntry,
34    options: ListDirOptions,
35    sort_by_name: bool,
36    mut read_dir: impl FnMut(&Path, ListDirOptions) -> VfResult<Vec<DirEntry>>,
37    mut callback: impl FnMut(&WalkEvent) -> VfResult<WalkControl>,
38) -> VfResult<TraversalCompletion> {
39    let mut budget = TraversalBudget::new(options.max_entries(), options.max_path_bytes());
40    budget.charge(root.path())?;
41    let kind = if root.attrs().is_dir() {
42        WalkEventKind::Enter
43    } else {
44        WalkEventKind::Entry
45    };
46    let mut pending = vec![WalkEvent {
47        kind,
48        entry: root,
49        depth: 0,
50    }];
51    while let Some(event) = pending.pop() {
52        match callback(&event)? {
53            WalkControl::Stop => return Ok(TraversalCompletion::Stopped),
54            decision if event.kind == WalkEventKind::Enter => {
55                pending.push(WalkEvent {
56                    kind: WalkEventKind::Leave,
57                    ..event.clone()
58                });
59                if decision == WalkControl::SkipSubtree {
60                    continue;
61                }
62                if event.depth > options.max_depth().get() {
63                    if options.truncate_at_max_depth() {
64                        continue;
65                    }
66                    return Err(VfError::client(0, libc::EFBIG as u32)
67                        .with_context("walk_events", event.entry.path()));
68                }
69                let remaining = budget.remaining_options(ListDirOptions::new());
70                let mut entries = read_dir(event.entry.path(), remaining)?;
71                for entry in &entries {
72                    budget
73                        .charge(entry.path())
74                        .map_err(|error| error.with_context("walk_events", entry.path()))?;
75                }
76                if sort_by_name {
77                    entries.sort_by(|a, b| a.file_name().cmp(&b.file_name()));
78                }
79                for entry in entries.into_iter().rev() {
80                    let kind = if entry.attrs().is_dir() {
81                        WalkEventKind::Enter
82                    } else {
83                        WalkEventKind::Entry
84                    };
85                    pending.push(WalkEvent {
86                        kind,
87                        entry,
88                        depth: event.depth + 1,
89                    });
90                }
91            }
92            _ => {}
93        }
94    }
95    Ok(TraversalCompletion::Complete)
96}
97
98#[cfg(test)]
99mod tests {
100    use std::path::PathBuf;
101
102    use super::*;
103    use crate::{AttrMask, FileOperand, VfAttrs, VfType};
104    fn entry(path: &str, dir: bool) -> DirEntry {
105        DirEntry::new(
106            path.into(),
107            crate::metadata_from_attrs(VfAttrs {
108                file: FileOperand::from_path(path),
109                masks: AttrMask::MODE,
110                ftype: if dir {
111                    VfType::Directory
112                } else {
113                    VfType::Regular
114                },
115                ..Default::default()
116            }),
117        )
118    }
119    #[test]
120    fn prune_prevents_io_and_events_have_depth_first_order() {
121        let mut events = Vec::new();
122        walk_events(
123            entry("/", true),
124            ListDirOptions::default().with_recursive(true),
125            true,
126            |path, _| {
127                assert_eq!(path, Path::new("/"), "pruned directory must not be read");
128                Ok(vec![entry("/z", false), entry("/a", true)])
129            },
130            |event| {
131                events.push((event.kind, event.entry.path().to_path_buf(), event.depth));
132                Ok(if event.entry.path() == Path::new("/a") {
133                    WalkControl::SkipSubtree
134                } else {
135                    WalkControl::Continue
136                })
137            },
138        )
139        .unwrap();
140        assert_eq!(
141            events
142                .iter()
143                .map(|e| (e.0, e.1.as_path(), e.2))
144                .collect::<Vec<_>>(),
145            vec![
146                (WalkEventKind::Enter, Path::new("/"), 0),
147                (WalkEventKind::Enter, Path::new("/a"), 1),
148                (WalkEventKind::Leave, Path::new("/a"), 1),
149                (WalkEventKind::Entry, Path::new("/z"), 1),
150                (WalkEventKind::Leave, Path::new("/"), 0)
151            ]
152        );
153    }
154    #[test]
155    fn depth_limit_allows_boundary_entries_and_only_blocks_directory_descent() {
156        let options = ListDirOptions::new()
157            .with_recursive(true)
158            .with_max_depth(crate::api::DepthLimit::new(0).expect("finite depth"));
159        let mut events = Vec::new();
160        assert_eq!(
161            walk_events(
162                entry("/", true),
163                options,
164                false,
165                |path, _| {
166                    assert_eq!(path, Path::new("/"));
167                    Ok(vec![entry("/file", false)])
168                },
169                |event| {
170                    events.push((event.kind, event.entry.path().to_path_buf(), event.depth));
171                    Ok(WalkControl::Continue)
172                },
173            )
174            .unwrap(),
175            TraversalCompletion::Complete
176        );
177        assert_eq!(
178            events,
179            vec![
180                (WalkEventKind::Enter, PathBuf::from("/"), 0),
181                (WalkEventKind::Entry, PathBuf::from("/file"), 1),
182                (WalkEventKind::Leave, PathBuf::from("/"), 0),
183            ]
184        );
185
186        let mut strict_entries = Vec::new();
187        let error = walk_events(
188            entry("/", true),
189            options,
190            false,
191            |path, _| {
192                assert_eq!(path, Path::new("/"));
193                Ok(vec![entry("/file", false), entry("/child", true)])
194            },
195            |event| {
196                strict_entries.push(event.entry.path().to_path_buf());
197                Ok(WalkControl::Continue)
198            },
199        )
200        .unwrap_err();
201        assert_eq!(error.raw_code(), libc::EFBIG as u32);
202        assert!(strict_entries.contains(&PathBuf::from("/file")));
203
204        let mut truncated_events = Vec::new();
205        let mut listed = Vec::new();
206        assert_eq!(
207            walk_events(
208                entry("/", true),
209                options.with_truncate_at_max_depth(true),
210                false,
211                |path, _| {
212                    listed.push(path.to_path_buf());
213                    assert_eq!(path, Path::new("/"));
214                    Ok(vec![entry("/file", false), entry("/child", true)])
215                },
216                |event| {
217                    truncated_events.push((event.kind, event.entry.path().to_path_buf()));
218                    Ok(WalkControl::Continue)
219                },
220            )
221            .unwrap(),
222            TraversalCompletion::Complete
223        );
224        assert_eq!(listed, [PathBuf::from("/")]);
225        assert!(truncated_events.contains(&(WalkEventKind::Entry, PathBuf::from("/file"))));
226        assert!(truncated_events.contains(&(WalkEventKind::Enter, PathBuf::from("/child"))));
227    }
228
229    #[test]
230    fn stop_error_and_limits_do_not_read_descendants() {
231        assert_eq!(
232            walk_events(
233                entry("/", true),
234                ListDirOptions::default().with_recursive(true),
235                false,
236                |_, _| panic!("stopped"),
237                |_| Ok(WalkControl::Stop)
238            )
239            .unwrap(),
240            TraversalCompletion::Stopped
241        );
242        assert!(
243            walk_events(
244                entry("/", true),
245                ListDirOptions::default().with_recursive(true),
246                false,
247                |_, _| panic!("callback failed"),
248                |_| Err(VfError::client(0, libc::EIO as u32))
249            )
250            .is_err()
251        );
252        for options in [
253            ListDirOptions::new()
254                .with_recursive(true)
255                .with_max_entries(1),
256            ListDirOptions::new()
257                .with_recursive(true)
258                .with_max_path_bytes(1),
259            ListDirOptions::new()
260                .with_recursive(true)
261                .with_max_depth(crate::api::DepthLimit::new(0).expect("finite depth")),
262        ] {
263            assert_eq!(
264                walk_events(
265                    entry("/", true),
266                    options,
267                    false,
268                    |path, _| {
269                        assert_eq!(path, Path::new("/"));
270                        Ok(vec![entry("/a", true)])
271                    },
272                    |_| Ok(WalkControl::Continue)
273                )
274                .unwrap_err()
275                .raw_code(),
276                libc::EFBIG as u32
277            );
278        }
279    }
280}
vfsi_core/api/traversal.rs

vfsi_core/api/
traversal.rs
