vfsi_core/api/
traversal.rs

1//! Incremental, no-follow traversal shared by application adapters.
2use crate::api::{DirEntry, ReadDirOptions, TraversalCompletion, WalkOptions};
3use crate::{VfError, VfResult};
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: WalkOptions,
35    sort_by_name: bool,
36    mut read_dir: impl FnMut(&Path, ReadDirOptions) -> VfResult<Vec<DirEntry>>,
37    mut callback: impl FnMut(&WalkEvent) -> VfResult<WalkControl>,
38) -> VfResult<TraversalCompletion> {
39    let mut count = 1usize;
40    let mut bytes = root.path().as_os_str().len();
41    if count > options.entry_limit() || bytes > options.path_byte_limit() {
42        return Err(VfError::client(0, libc::EFBIG as u32));
43    }
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(event) = pending.pop() {
55        match callback(&event)? {
56            WalkControl::Stop => return Ok(TraversalCompletion::Stopped),
57            decision if event.kind == WalkEventKind::Enter => {
58                pending.push(WalkEvent {
59                    kind: WalkEventKind::Leave,
60                    ..event.clone()
61                });
62                if decision == WalkControl::SkipSubtree {
63                    continue;
64                }
65                if event.depth >= options.depth_limit() && options.truncates_at_depth_limit() {
66                    continue;
67                }
68                let remaining = ReadDirOptions::new()
69                    .max_entries(options.entry_limit().saturating_sub(count))
70                    .max_path_bytes(options.path_byte_limit().saturating_sub(bytes));
71                let mut entries = read_dir(event.entry.path(), remaining)?;
72                for entry in &entries {
73                    count = count
74                        .checked_add(1)
75                        .ok_or_else(|| VfError::client(0, libc::EFBIG as u32))?;
76                    bytes = bytes
77                        .checked_add(entry.path().as_os_str().len())
78                        .ok_or_else(|| VfError::client(0, libc::EFBIG as u32))?;
79                    if count > options.entry_limit()
80                        || bytes > options.path_byte_limit()
81                        || event.depth >= options.depth_limit()
82                    {
83                        return Err(VfError::client(0, libc::EFBIG as u32)
84                            .with_context("walk_events", entry.path()));
85                    }
86                }
87                if sort_by_name {
88                    entries.sort_by(|a, b| a.file_name().cmp(&b.file_name()));
89                }
90                for entry in entries.into_iter().rev() {
91                    let kind = if entry.attrs().is_dir() {
92                        WalkEventKind::Enter
93                    } else {
94                        WalkEventKind::Entry
95                    };
96                    pending.push(WalkEvent {
97                        kind,
98                        entry,
99                        depth: event.depth + 1,
100                    });
101                }
102            }
103            _ => {}
104        }
105    }
106    Ok(TraversalCompletion::Complete)
107}
108
109#[cfg(test)]
110mod tests {
111    use super::*;
112    use crate::{AttrMask, VfAttrs, VfFile, VfType};
113    fn entry(path: &str, dir: bool) -> DirEntry {
114        DirEntry::new(
115            path.into(),
116            crate::metadata_from_attrs(VfAttrs {
117                file: VfFile::from_path(path),
118                masks: AttrMask::MODE,
119                ftype: if dir {
120                    VfType::Directory
121                } else {
122                    VfType::Regular
123                },
124                ..Default::default()
125            }),
126        )
127    }
128    #[test]
129    fn prune_prevents_io_and_events_have_depth_first_order() {
130        let mut events = Vec::new();
131        walk_events(
132            entry("/", true),
133            WalkOptions::default(),
134            true,
135            |path, _| {
136                assert_eq!(path, Path::new("/"), "pruned directory must not be read");
137                Ok(vec![entry("/z", false), entry("/a", true)])
138            },
139            |event| {
140                events.push((event.kind, event.entry.path().to_path_buf(), event.depth));
141                Ok(if event.entry.path() == Path::new("/a") {
142                    WalkControl::SkipSubtree
143                } else {
144                    WalkControl::Continue
145                })
146            },
147        )
148        .unwrap();
149        assert_eq!(
150            events
151                .iter()
152                .map(|e| (e.0, e.1.as_path(), e.2))
153                .collect::<Vec<_>>(),
154            vec![
155                (WalkEventKind::Enter, Path::new("/"), 0),
156                (WalkEventKind::Enter, Path::new("/a"), 1),
157                (WalkEventKind::Leave, Path::new("/a"), 1),
158                (WalkEventKind::Entry, Path::new("/z"), 1),
159                (WalkEventKind::Leave, Path::new("/"), 0)
160            ]
161        );
162    }
163    #[test]
164    fn stop_error_and_limits_do_not_read_descendants() {
165        assert_eq!(
166            walk_events(
167                entry("/", true),
168                WalkOptions::default(),
169                false,
170                |_, _| panic!("stopped"),
171                |_| Ok(WalkControl::Stop)
172            )
173            .unwrap(),
174            TraversalCompletion::Stopped
175        );
176        assert!(
177            walk_events(
178                entry("/", true),
179                WalkOptions::default(),
180                false,
181                |_, _| panic!("callback failed"),
182                |_| Err(VfError::client(0, libc::EIO as u32))
183            )
184            .is_err()
185        );
186        for options in [
187            WalkOptions::new().max_entries(1),
188            WalkOptions::new().max_path_bytes(1),
189            WalkOptions::new().max_depth(0),
190        ] {
191            assert_eq!(
192                walk_events(
193                    entry("/", true),
194                    options,
195                    false,
196                    |path, _| {
197                        assert_eq!(path, Path::new("/"));
198                        Ok(vec![entry("/a", true)])
199                    },
200                    |_| Ok(WalkControl::Continue)
201                )
202                .unwrap_err()
203                .err_no(),
204                libc::EFBIG as u32
205            );
206        }
207    }
208}
vfsi_core/api/traversal.rs

vfsi_core/api/
traversal.rs
