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(
40        options.max_entries_or(crate::api::DEFAULT_DIRECTORY_MAX_ENTRIES),
41        options.max_path_bytes_or(crate::api::DEFAULT_DIRECTORY_MAX_PATH_BYTES),
42    );
43    budget.charge(root.path())?;
44    let kind = if root.attrs().is_dir() {
45        WalkEventKind::Enter
46    } else {
47        WalkEventKind::Entry
48    };
49    let mut pending = vec![WalkEvent {
50        kind,
51        entry: root,
52        depth: 0,
53    }];
54    while let Some(mut event) = pending.pop() {
55        match callback(&event)? {
56            WalkControl::Stop => return Ok(TraversalCompletion::Stopped),
57            decision if event.kind == WalkEventKind::Enter => {
58                event.kind = WalkEventKind::Leave;
59                if decision == WalkControl::SkipSubtree {
60                    pending.push(event);
61                    continue;
62                }
63                if event.depth > options.max_depth_or(Default::default()).get() {
64                    if options.truncate_at_max_depth() {
65                        pending.push(event);
66                        continue;
67                    }
68                    return Err(VfError::client(0, libc::EFBIG as u32)
69                        .with_context("walk_events", event.entry.path()));
70                }
71                let remaining = budget.remaining_options(ListDirOptions::new());
72                let mut entries = read_dir(event.entry.path(), remaining)?;
73                for entry in &entries {
74                    budget
75                        .charge(entry.path())
76                        .map_err(|error| error.with_context("walk_events", entry.path()))?;
77                }
78                if sort_by_name {
79                    entries.sort_by(|a, b| a.file_name().cmp(&b.file_name()));
80                }
81                let child_depth = event.depth + 1;
82                pending.push(event);
83                for entry in entries.into_iter().rev() {
84                    let kind = if entry.attrs().is_dir() {
85                        WalkEventKind::Enter
86                    } else {
87                        WalkEventKind::Entry
88                    };
89                    pending.push(WalkEvent {
90                        kind,
91                        entry,
92                        depth: child_depth,
93                    });
94                }
95            }
96            _ => {}
97        }
98    }
99    Ok(TraversalCompletion::Complete)
100}
101
102#[cfg(test)]
103mod tests {
104    use std::path::PathBuf;
105
106    use super::*;
107    use crate::{AttrMask, FileOperand, VfAttrs, VfType};
108    fn entry(path: &str, dir: bool) -> DirEntry {
109        DirEntry::new(
110            path.into(),
111            crate::metadata_from_attrs(VfAttrs {
112                file: FileOperand::from_path(path),
113                masks: AttrMask::MODE,
114                ftype: if dir {
115                    VfType::Directory
116                } else {
117                    VfType::Regular
118                },
119                ..Default::default()
120            }),
121        )
122    }
123    #[test]
124    fn prune_prevents_io_and_events_have_depth_first_order() {
125        let mut events = Vec::new();
126        walk_events(
127            entry("/", true),
128            ListDirOptions::default().with_recursive(true),
129            true,
130            |path, _| {
131                assert_eq!(path, Path::new("/"), "pruned directory must not be read");
132                Ok(vec![entry("/z", false), entry("/a", true)])
133            },
134            |event| {
135                events.push((event.kind, event.entry.path().to_path_buf(), event.depth));
136                Ok(if event.entry.path() == Path::new("/a") {
137                    WalkControl::SkipSubtree
138                } else {
139                    WalkControl::Continue
140                })
141            },
142        )
143        .unwrap();
144        assert_eq!(
145            events
146                .iter()
147                .map(|e| (e.0, e.1.as_path(), e.2))
148                .collect::<Vec<_>>(),
149            vec![
150                (WalkEventKind::Enter, Path::new("/"), 0),
151                (WalkEventKind::Enter, Path::new("/a"), 1),
152                (WalkEventKind::Leave, Path::new("/a"), 1),
153                (WalkEventKind::Entry, Path::new("/z"), 1),
154                (WalkEventKind::Leave, Path::new("/"), 0)
155            ]
156        );
157    }
158    #[test]
159    fn depth_limit_allows_boundary_entries_and_only_blocks_directory_descent() {
160        let options = ListDirOptions::new()
161            .with_recursive(true)
162            .with_max_depth(crate::api::DepthLimit::new(0).expect("finite depth"));
163        let mut events = Vec::new();
164        assert_eq!(
165            walk_events(
166                entry("/", true),
167                options,
168                false,
169                |path, _| {
170                    assert_eq!(path, Path::new("/"));
171                    Ok(vec![entry("/file", false)])
172                },
173                |event| {
174                    events.push((event.kind, event.entry.path().to_path_buf(), event.depth));
175                    Ok(WalkControl::Continue)
176                },
177            )
178            .unwrap(),
179            TraversalCompletion::Complete
180        );
181        assert_eq!(
182            events,
183            vec![
184                (WalkEventKind::Enter, PathBuf::from("/"), 0),
185                (WalkEventKind::Entry, PathBuf::from("/file"), 1),
186                (WalkEventKind::Leave, PathBuf::from("/"), 0),
187            ]
188        );
189
190        let mut strict_entries = Vec::new();
191        let error = walk_events(
192            entry("/", true),
193            options,
194            false,
195            |path, _| {
196                assert_eq!(path, Path::new("/"));
197                Ok(vec![entry("/file", false), entry("/child", true)])
198            },
199            |event| {
200                strict_entries.push(event.entry.path().to_path_buf());
201                Ok(WalkControl::Continue)
202            },
203        )
204        .unwrap_err();
205        assert_eq!(error.raw_code(), libc::EFBIG as u32);
206        assert!(strict_entries.contains(&PathBuf::from("/file")));
207
208        let mut truncated_events = Vec::new();
209        let mut listed = Vec::new();
210        assert_eq!(
211            walk_events(
212                entry("/", true),
213                options.with_truncate_at_max_depth(true),
214                false,
215                |path, _| {
216                    listed.push(path.to_path_buf());
217                    assert_eq!(path, Path::new("/"));
218                    Ok(vec![entry("/file", false), entry("/child", true)])
219                },
220                |event| {
221                    truncated_events.push((event.kind, event.entry.path().to_path_buf()));
222                    Ok(WalkControl::Continue)
223                },
224            )
225            .unwrap(),
226            TraversalCompletion::Complete
227        );
228        assert_eq!(listed, [PathBuf::from("/")]);
229        assert!(truncated_events.contains(&(WalkEventKind::Entry, PathBuf::from("/file"))));
230        assert!(truncated_events.contains(&(WalkEventKind::Enter, PathBuf::from("/child"))));
231    }
232
233    #[test]
234    fn stop_error_and_limits_do_not_read_descendants() {
235        assert_eq!(
236            walk_events(
237                entry("/", true),
238                ListDirOptions::default().with_recursive(true),
239                false,
240                |_, _| panic!("stopped"),
241                |_| Ok(WalkControl::Stop)
242            )
243            .unwrap(),
244            TraversalCompletion::Stopped
245        );
246        assert!(
247            walk_events(
248                entry("/", true),
249                ListDirOptions::default().with_recursive(true),
250                false,
251                |_, _| panic!("callback failed"),
252                |_| Err(VfError::client(0, libc::EIO as u32))
253            )
254            .is_err()
255        );
256        for options in [
257            ListDirOptions::new()
258                .with_recursive(true)
259                .with_max_entries(1),
260            ListDirOptions::new()
261                .with_recursive(true)
262                .with_max_path_bytes(1),
263            ListDirOptions::new()
264                .with_recursive(true)
265                .with_max_depth(crate::api::DepthLimit::new(0).expect("finite depth")),
266        ] {
267            assert_eq!(
268                walk_events(
269                    entry("/", true),
270                    options,
271                    false,
272                    |path, _| {
273                        assert_eq!(path, Path::new("/"));
274                        Ok(vec![entry("/a", true)])
275                    },
276                    |_| Ok(WalkControl::Continue)
277                )
278                .unwrap_err()
279                .raw_code(),
280                libc::EFBIG as u32
281            );
282        }
283    }
284}
vfsi_core/api/traversal.rs

vfsi_core/api/
traversal.rs
